Redis源码阅读

zipmap

redis旧版小hash使用的数据结构，紧密数组存储结构 用1字节存储总节点数（如果1字节满了，代表需要遍历到底才知道有多少节点） 每个节点存储自己占用的内存空间，修改删除后，标记为闲置空间，闲置空间不压缩不回收，留用节点扩展或者插入节点 这也代表插入没有足够闲置时要O(n)移动后续内存 数据也是占用zipmap内存，所以查找是O(n)（利用len做快表跳跃）

<zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"<ZIPMAP_END>

ziplist

新版小hash使用的数据结构，紧密数组存储结构 用1字节存储总节点数（如果1字节满了，代表需要遍历到底才知道有多少节点） 每个节点存储自己占用的内存空间和前一节点占用内存空间 修改删除后，实时压缩内存（o(N)移动后续节点前移） 数据不占用ziplist内存，ziplist里保存一个entry，entry存储指针指向值对象的动态内存 好处是节点大小固定（sizeof(entry)），随机下标访问可以基于下标直接算内存地址访问

<zlbytes><zltail><zllen><entry><entry><zlend>

adlist

环形双端链表，没啥好说的

dict

这里比较特别的是一个字典里会有最多两个hash表同时存在，目的是rehash的时候可以做渐进式hash table的结构是个数组，每个元素是一条链表，redis最小rehash单位为链表，所以为了避免rehash的时候元素过多需要卡住服务器很久，采取部分rehash，然后用一个标记维护处于rehash中未完成（rehashidx），新增操作和修改操作发现有该标记，新的插入会插入到新hash表，然后在每次查询、修改处，执行单步rehash（单条链表） 也就是把rehash的时间消耗分摊下去，不要一下子卡住服务很久 因为新数据都会到新hash，所以几次下来旧hash就空了，旧hash空了以后就把新hash作为主hash，释放旧hash表了

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;
typedef struct dictht {
    // 哈希表
    dictEntry **table;// (dictEntry * ) table[]
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

typedef struct dict {
    // 哈希表
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

scan算法

redis的全遍历（scan）是按照bucket的顺序遍历（单个bucket同步，多个也是分摊异步） 采用了一些算法保证中间过程触发一次rehash不影响，具体： 从小往大顺序异步遍历，则在缩容时可能导致没有遍历过的大编号bucket被rehash到已经遍历过的小编号bucket，导致遍历遗漏 （扩容不影响） 解决的方法就是在同步遍历某个bucket时，把缩容一次后会聚拢到该bucket的bucket也遍历了，也就是idx与(idx + size/2) % size 比如size是8，缩容后就是4，所以对size为8的遍历就是

0->4
1->5
2->6
3->7

基于idx与idx + size/2这个公式得到的bucket 源码里把这用一个数学公式体现（反序+1后再反序）

//每次从高位进1
000    0 -》 100    4
001    1 -》 101    5
010    2 -》 110    6
011    3- 》 111    7