此系列作为redis设计与实现的笔记，会将本人自认为重点部分单独拎出来，并加入本人的一些理解。

SDS

（simple dynamic string）

等同于go里的slice

1
2
3
4
5
6
7
8
9

struct sdshdr {

int len;

int free;

char buf[];

}

优点：

  • 杜绝缓冲区溢出（free检验）
  • 减少修改字符串时的内存分配次数（策略：小于1MB时，len=free，大于1MB时，free=1MB）
  • 惰性空间释放（删除时实际空间并未缩减）
  • 二进制安全（C字符串视/0为结束，不能用来存带/0的二进制数据）
  • 部分兼容C字符串函数（默认在char数组最后加入/0，来兼容C字符串函数）

链表

双向链表，无环，保存头指针和尾指针，保存链表长度字段，链表节点的数据为void*指针

字典

字典有type，每个type实现了一系列操作kv的函数（对比，生成哈希，删除，复制等）

每个字典存有两个哈希表，一般用第一个ht[0]，第二个ht[1]用作rehash时的暂存容器

哈希表由数组实现，数组存放kv链表头节点，链地址法解决冲突，冲突的新键值往表头加（由于没有指向表尾的指针）

rehash标志位，当没有进行rehash时为-1

key–>(hashfunc)–>hash–>(hashmask)–>index

murmurhash算法：输入有规律情况还是能生成随机分布性的hash

rehash

为ht[1]哈希表分配空间，空间的大小取决于当前ht[0]包含的键值数量以及要进行的操作，重新计算所有键值在ht[1]的索引并插入，插入后将ht[1]设置为ht[0]，并ht[1]指向新创的空白hash表

负载因子=ht[0].used/ht[0].size

何时进行扩展?

在进行持久化操作时(BGSAVE,BGREWRITEAOF)，负载因子>=5，普通场景下负载因子>=1

何时进行收缩?

负载因子<0.1

渐进式rehash

开始时rehashidx为0，表示正在进行rehash，rehash期间对字典的CRUD会顺带将ht[0]上的KV rehash到ht[1]，完成后rehashidx置为-1,表示已经完成。rehash期间的CRUD会先在ht[0]上查，查不到再去ht[1]查

跳表

用来实现有序集合键，用作集群节点内部数据结构

优点，相较于平衡树，实现简单，且rebalance的效率高（局部rebalance，只修改搜索路径上的节点）

链表的扩展，维护了多个指向其他节点的指针，类似二分查找

每个节点的层数是随机生成的，遍历时先走最上层的前进指针，若下一条节点的分值比要查找的分值高，则通过回退指针回到原来的节点并走下一层的前进指针，以此类推

前进指针中存有跨度，累加所有跨度，当找到该节点后作为该节点在跳表中的排位（数组的index）

比较分值时，分值可能相同，相同时比较value值（obj指向的sds的字典序）

节点更新时，若score的改变未影响排序，则查找并直接改score，否则进行先删除后插入操作，会进行两次路径搜索

整数集合

底层保存的整数为byte数组(int8)，按照解码类型(encoding)存入int16，int32或int64的数据

只能存一种类型的数据，短int集合中插入长int后，往长int类型兼容（升级）

节约内存，int16不需要分配int64的空间

自适应灵活性，集合中添加长度更长的新元素，会自动升级，但不支持降级

压缩列表

为了节约内存，将键值为小整数值和短字符串的entry按照特殊编排压缩为一段内存块

先略过

对象

创建键值对时，键和值都被封装成对象，并指明对象的类型，编码以及底层数据结构的指针

key总是字符串对象，value可以是字符串对象，列表对象，哈希对象，集合对象，有序集合对象(zset)

编码指定了底层数据结构, 每种对象类型有多种编码的实现

字符串对象

long：value是数字，可以用long存

raw：value是字符串，长度大于32byte，用sds存，sds的内存是另外一块，和redisObject不连续

embstr：value是字符串，长度小于32byte，用sds存，sds的内存与redisObject的内存连续 （好处：减少分配和释放内存的次数，增加缓存命中率；坏处：没有实现写方法，只读，修改的话需要先转raw）

列表对象

ziplist：redisObject的ptr指向压缩列表（条件：每个字符串长度<64byte且列表长度<512）

linkedlist：构造元素为字符串对象的双向链表（列表对象中嵌套了字符串对象）

哈希对象

ziplist: 按照旧键+旧值+新键+新值的顺序添加至压缩列表中

hashtable: 构造键值为字符串对象的字典（哈希对象中嵌套了字符串对象）

集合对象

intset: 整数集合（条件：元素都是整数且个数不超过512）

hashtable: 构造键为字符串对象的字典，值为null（哈希对象中嵌套了字符串对象）

有序集合对象

ziplist: 按分值从小到大排列

skiplist: 构造元素为字符串对象的跳表。同时构造key为字符串对象，值为分值的字典（字符串对象和值与跳表用的是同一内存），用来根据成员查分值

命令的类型检查与多态

先判断type支不支持该命令，再通过encoding决定命令的实现方式

对象通过引用计数(ref)来决定是否被回收，相同字符串对象只对底层对象的引用计数增加而不新创建对象（只有字符串对象有共享机制，其他对象判断对象相同的复杂度太高）

0-9999所有整数在初始化时创建默认字符串对象

对象还有lru属性，用于lru算法老化内存