# Redis的数据结构 `redis是用c语言写的！` ## 一、简单动态字符串 Redis中的字符串并不是使用原生的C语言字符串，而是自己写了一个结构体来表示字符串，在redis中称为简单动态字符串（simple dynamic string）即SDS。其定义如下： ~~~  struct sdshdr {      int len; // 当前的字节长度      int free; // 空闲空间的字节长度      char buf[]; // 字节数组  } ~~~ `这是老版本的redis中的定义，新版本的也采用类似的思想。详细的查看redis开源代码中的src/sds.h` SDS中buf的长度为：len + free + 1。 SDS结构示意： :-:  ### 与C语言字符串的区别 `注意在C语言中并没有严格意义上的字符串类型，而是采用数据的方式来保存字符串。` 1. 获取长度的时间复杂为O（1） c语言的字符串是通过遍历的方式来获取字符串的长度，统计到‘\\0’字符为止，其时间复杂度为O（N）。但是sds结构中本身就有len属性记录了当前的字符串的长度，同时也不是通过'\\0'来表示字符串的结尾，虽然会在字符串的结尾中添加上'\\0'。 2. 杜绝缓冲区的溢出 使用c语言字符串进行拼接的时候strcat(dest, source)，如果dest没有提前分配足够大小的内存，c语言任然会直接加source的内容拼接到dest后面，这样就可能会覆盖掉dest后面的内容。而redis中的sdscat的拼接会提前判断dest中的free属性是否足够大，如果不够，则会`自动的进行空间的扩展`，然后再进行拼接。 3. 减少修改字符串时带来的内存重新分配次数 在C语言中，每次修改字符串的内容，都会重新分配内存空间，这是操作系统本身会进行的系统调用。而在redis中由于本身被修改比较频繁，因此采用了两种策略来减少内存的重新分配次数。 * 空间的预分配 空间预分配规则用于对字符串空间扩展时使用，程序不仅会扩展上足够的空间，还会扩展预留的空间。 ~~~  # 规则  1. 当字符串的长度小于1MB时，会分配和len同样大小的未使用空间，即让len=free。  2. 当字符串长度大于等于1MB时，程序将会分配1MB的未使用空间。 ~~~ `通过预分配策略，SDS使得连续增长N字符串所需的内存重分配次数从必定N次减少到最多N次。` * 惰性空间的释放 惰性空间的使用规则用于对字符串空间缩减时使用，其并不会真正的减少sds的长度，而是将释放出来的空间作为未使用空间继续保存，其`长度保存在free`中。 ~~~  tips: SDS类型存放的字节，并不仅仅是存放ASCII。 ~~~   ## 二、链表（双端链表） 链表节点的定义： ~~~  typedef struct listNode {      // 上一个节点      struct listNode *prev;      // 下一个节点      struct listNode *next;      // 节点的值      void *value;  } listNode; ~~~ 链表的定义： ~~~  typedef struct list {      // 头节点      listNode *head;      // 尾节点      listNode *tail;      // 节点复制函数      void *(*dup)(void *ptr);      // 节点释放函数      void (*free)(void *ptr);      // 节点对比函数      int (*match)(void *ptr, void *key);      // 节点的长度      unsigned long len;  } list; ~~~ * dup函数用于复制链表节点所保存的值。 * free函数用于释放链表节点所保存的值。 * match函数用于比较链表节点所保存的值和另一个输入值是否相等。 结构示意： ### redis链表的特性 1. 获取表尾节点的时间复杂度为O（1），因此在链表尾部添加节点的时间复杂度也是O（1）。 2. 获取链表的长度的时间复杂度为O（1），可以直接通过len属性获取。 3. `多态`：链表节点是通过void\* 指针来保存节点的值，并且可以通过list结构的dup、free、match三个属性为节点值设置特定类型，可以用于保存各种不同的数据类型。   ## 三、字典 redis中的字典使用哈希表作为底层的实现，一个hash table里面的每个hash entry都保留了一个键值对。 哈希表的定义：`dict.h/dictht` ~~~  typedef struct dictht {      dictEntry **table;      // 哈希表的大小      unsigned long size;      // 用于计算哈希索引，大小固定位size - 1      unsigned long sizemask;      // 哈希表中的节点个数      unsigned long used;  } dictht; ~~~ 哈希表的每一项由dictEntry构成： ~~~  typedef struct dictEntry {      // 键      void *key;      // 值      union {          void *val;          uint64_t u64;          int64_t s64;          double d;     } v;      // 下一个节点      struct dictEntry *next;  }dictEntry; ~~~ **next**属性使用了链表的方式解决hash冲突。 字典的定义： ~~~  typedef struct dict {      dictType *type;      void *privdata;      // 保存了两个hash表，用于rehash      dictht ht[2];      // 用于重新hash， 不用重新hash时值为-1      long rehashidx;      // 大于0时暂停rehash      int16_t pauserehash;  } dict; ~~~ **type**属性保存了一系列操作特定类型键值对的函数，**privdata**属性保存了这些函数的可选参数。 ~~~  typedef struct dictType {      // 哈希函数      uint64_t (*hashFunction)(const void *key);      // 复制键      void *(*keyDup)(void *privdata, const void *key);      // 复制值      void *(*valDup)(void *privdata, const void *obj);      // 键比较      int (*keyCompare)(void *privdata, const void *key1, const void *key2);      // 销毁键      void (*keyDestructor)(void *privdata, void *key);      // 销毁值      void (*valDestructor)(void *privdata, void *obj);      int (*expandAllowed)(size_t moreMem, double usedRatio);  } dictType; ~~~ 字典结构： ### 哈希算法 ~~~  1. 计算键对应的hash值  hash = dict->type->hashFunction(key)  2. 计算哈希表的索引  index = hash & dict->ht[x].sizemask; ~~~ x为0或者1，算出来的index就放在0或1中，如果出现冲突，则使用链地址法的方式解决冲突，并且使用头插法的方式往链表中插入节点。 `redis使用murmurHash2算法计算hash值。` ### rehash 当哈希表的负载因子超过一定范围时，字典会进行一次重新散列，减少冲突或者减少空间的浪费。 ~~~  load_factor = dictht[0].used / dictht[0].size; ~~~ 1. 扩展操作 当满足下列情况之一时，字典会进行rehash操作： * 服务器目前没有执行bgsave或者是bgrewriteaof命令时，且负载因子大于等于1. * 服务器目前正在执行bgsave或者是bgrewriteaof命令，且负载因子大于等于5. ~~~  当服务器在执行bgsave或者bgrewriteaof命令时，会fork一个子进程，并且服务器采用写时复制来优化子程序的性能，此时会扩展负载因子，从而尽量避免了在上述命令操作时进行rehash。 ~~~ rehash的扩展操作是通过字典中的另外一个hash table（ht\[1\]）来实现的，对于扩展操作，其会分配的空间大小为： ~~~  第一个大于等于ht[0].used * 2的2的n次幂的大小。  例如：ht[0].used = 3,  则会给ht[1]分配：3 * 2 = 6，比之大的第一个2的n次幂为8，即会分配8个单位的空间大小 ~~~ 之后会采用渐进式的方式在`每次增删改操作时修改rehashIndex的值`，将该rehashIndex索引下的所有键值对rehash到ht\[1\]中去。每次操作都会递增rehashIndex的值，同时对于字典的添加操作，新添加的会放到ht\[1\]中，确保ht\[0\]会被释放完毕。当ht\[0\]为空时设置rehashIndex为-1，结束rehash。 接着将ht\[0\]执行ht\[1\]，重新创建一个新的ht\[1\]。 2. 收缩操作 当负载因子小于0.1时会自动进行收缩操作，此时对ht\[1\]分配的大小为： ~~~  第一个大于等于ht[0].used的2的n次幂。 ~~~ `渐进式rehash操作时，添加在ht[1]中，查找、更新、删除在ht[0]和ht[1]中进行。`