redis源码分析（三）：基本数据结构

2018-07-31 本文已影响5人 msrpp

redis中使用的数据结构有:

dict 字典,就是个哈希表,实现和HashMap类似,不做阐述;不同的是在哈希表resize()的时候是分步执行的,后续篇幅再说明。
sds 很多项目都对自己的字符串进行了封装,作用类似于leveldb的slice。
linkedlist 双端链表，迭代器的实现是通过链表的pre和next实现的，是个BidirctionalIterator。代码中只实现了ForwardIterator的功能。
zipmap 已不再使用了
inset 一个紧致的有序整型数组。
ziplist 也是一个链表，但是它的内存是连续的，在数据量小的时候使用，增长到一定的大小会转化成list或者skiplist
skiplist 跳跃表，实现在t_zset.c中

本文只阐述inset，ziplist，skiplist三种数据结构。

1.ziplist

直接借用代码注释上ziplist的存储结构：

/*
area        |<---- ziplist header ---->|<----------- entries ------------->|<-end->|

size          4 bytes  4 bytes  2 bytes    ?        ?        ?        ?     1 byte
            +---------+--------+-------+--------+--------+--------+--------+-------+
component   | zlbytes | zltail | zllen | entry1 | entry2 |  ...   | entryN | zlend |
            +---------+--------+-------+--------+--------+--------+--------+-------+
                                       ^                          ^        ^
address                                |                          |        |
                                ZIPLIST_ENTRY_HEAD                |   ZIPLIST_ENTRY_END
                                                                  |
                                                        ZIPLIST_ENTRY_TAIL

zlbytes 记录了整个ziplist占用的内存大小；
zltail 记录尾节点的相对于ziplist实例指针的偏移量；
zllen 是整个list的节点数量的无符号数，占2个字节，可以最大表示2**16-1，实际使用保留了0xffff ffff ,即大于等于这个数的时候，已经不能通过此值来取得节点的数量了；
zlend 固定为0xff。
entry 的结构并不是代码中给的结构体zlentry。而是如下结构:

size              1/5 bytes      1/2/5 bytes    ?   
            +---------------+---------------+-------+
component   | pre_entry_len | cur_entry_len | value |
            +---------------+---------------+-------+

这是个变长的结构，pre节点小于254则pre_entry_len占用1字节，否则5字节,为什么不是255字节呢？255会和zlend产生冲突；cur_entry_len中包含了编码信息（以字符串编码还是数字，数字编码能减少内存长度)和本节点的长度信息,数字格式编码固定占用1字节；字符串格式编码数据小于127字节占1字节，小于0x3fff 占用2字节，否则5个字节。

因此ziplist有如下特点:

内存连续，数据紧凑。
查找效率o(n)
双端查询，可前后遍历，类似于nodelist.

了解了数据结构，思考下如何对其增加一个节点p，p的大小为sp。

1.ziplist长度发生变化，zlbytes要增加entry的内存大小；
2.zltail也要做相应改变，如果插入的是尾节点，则zltail等于ziplist到新节点p的距离，否则是原值加上新节点p的长度。
3.内存大小发生改变，需要realloc个更大的内存。
4.对于在新节点以后的节点，后移sp个单位。接下来要更新p以后的节点内容:
4.1如果p的前一个节点的长度和p节点的长度一样长，那么皆大欢喜。只需要更新p节点后一个节点的pre_entry_len值；
4.2如果比p节点的长度大(5字节对1字节)，也ok，存下来，浪费4个字节内存。
4.3如果比p节点的长度小(1字节对5字节)，意味着p以后的节点长度会发生变化，增加4个字节来存储p的长度，zltail和ziplist也要同时加4;同时由于p->next节点长度发生变化，p->next->next也要去做一次判断，需要重复步骤4，直到不满足4.3的情况为止。

经过以上步骤，就可以大概还原redis中的代码实现了，也可以看出来ziplist的增删代价是很大的，改变一个节点的复杂度最差是（n^2);一个节点改动，可能牵一发而动全身，所以ziplist是不适合大数据量的存储的。

2.inset

inset 实际是一个整数数组，结构如下:

typedef struct intset {
    
    uint32_t encoding;

    uint32_t length;

    int8_t contents[];

} intset;

其中encoding是编码方式，有16位，32位，64位三种取值；length是inset集合中保存的元素个数，contents为保存的数据。下面是inset的特点和实现方式.

1.初始化的inset是16位编码的，如果inset里面只保存了16位的数字，那么这个编码方式将保持不变。
2.inset是有序不重复的，从小到大排列，每次插入/删除会触发inset的大小调整,length+1。
3.如果插入了比当前编码范围更大的数字，会触发intsetUpgradeAndAdd()，下面以16位-> 32位扩展为例。
3.1 重新调整contents大小，大小为原(size+1)*2，更新encoding的值为INTSET_ENC_INT32;
3.2 新数字肯定是位于数组开头或者结尾，如果是在结尾，将原数组的每个数从原位置pos移到pos2的位置，否则是(pos+1)2；
3.3 插入新的数据，intsetUpgradeAndAdd()过程结束
4.删除不改变inset的编码方式，即如果原inset为32位，删光了inset里的16位不能表示的数字以后，inset也不会恢复到16位，代价太大，即intsetUpgradeAndAdd()的过程是不可逆的。
5.在inset中查找一个数采用二分查找。

根据这些特点，写出inset的实现，想必不难，inset的特点是在存储的数据为小值的时候，占用的内存较小，但是只要插入了一个64位的数据，那么inset就没有优势了，插入和删除的时间复杂度都是o(n)，因此不适合做大数量的存储。

3.skiplist

跳表是一个特殊的有序链表，盗一张网图吧。

跳表结构

结构如下

typedef struct zskiplist {

    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;

    // 表中节点的数量
    unsigned long length;

    // 表中层数最大的节点的层数
    int level;

} zskiplist;

节点的结构

typedef struct zskiplistNode {

    // 成员对象
    robj *obj;

    // 分值
    double score;

    // 后退指针
    struct zskiplistNode *backward;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;

简述下跳表的特点

跳表是一个排序链表，redis中以score的大小做排序，增删改查的效率均是o(logn)，由于其实现更易于理解和简单。所以作用相当于红黑树。
跳表是不稳定的，即同样是创建一个跳表，插入若干相同的值，内部的数据结构可能是不一致的。
每个节点的大小不固定，不固定的原因是节点的拥有的forward指针个数不定，这个数值是在节点创建的时候随机选取的一个正整数，redis实现默认最大层数是32。
redis中的跳表增加了一个指向前节点的backward来往前遍历;一个span，用于计算forward节点和本节点中间的跨度，以方便zcount等命令来计算范围内score的数量。

如何插入一个数据?redis排序顺序是从头到尾，按照score从小到大。如果要增加一个值，首先需要确定插入后的顺序，假设跳表为skl ，新节点为n。

1. 找到每一层比新节点score小，而且距离最近的节点，保存为update[]。
1. 随机产生新节点的层高，对每一层的forward节点复制，令n->level[i]->forward = update[i]->level[i]->forward，给新节点的所有forward指针赋值。令update[i]->forward = n使新节点和其所有前置节点关联;实际上和双向链表操作类似。

如何查找一个节点p?

场景1.根据score范围查找内容，对应zrange命令。查找左界和右界，中间的范围及所求。左界和右界算法类似，从head的顶层forward节点开始，如果比p的score小，那么让head = forward 继续此步骤.如果等于score那么返回。如果小于那么代表需要找的左界在head和forward之间，跳到下一层重复此步骤。
场景2.根据内容查找score，对应zscore命令。redis不查找skiplist，而是额外使用了个hash表来达到o(1)的效率。

迭代器如何设计?

可知n->level[0]->forward的步长是1，循环forward可以遍历整个跳表。
推荐跳表的leveldb版实现。
综上，redis的数据结构分析告一段落。

redis源码分析（三）：基本数据结构

1.ziplist

2.inset

3.skiplist

猜你喜欢

热点阅读