Redis源码阅读笔记

野性酷女 2022-09-11 10:22 256阅读 0赞

### Redis源码阅读笔记 ###

*   *  zipmap
     *  ziplist
     *  adlist
     *  dict
     *  scan算法

## 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)），随机下标访问可以基于下标直接算内存地址访问

## 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

更多文章，请搜索公众号歪歪梯Club  
![更多资料，请搜索公众号歪歪梯Club][Club]

[Club]: /images/20220828/e6f60bdd96254827abb538427f14e691.png