redis笔记-数据结构篇

1. SDS

• 描述

redis底层是C语言编写，而redis没有直接使用C语言的字符串表示，是自己构建了一种名为简单动态字符串的抽象类型，即SDS（simple dynamic string）。
redis数据库里，包含字符串值的键值对在底层都是SDS实现的，可以说SDS是基石。
AOF模块中的AOF缓冲区，以及客户端状态中的输入缓冲区，都是SDS实现的。

• 定义

struct sdshdr {
        // 记录buf数组中已使用字节的数量
        // 等于SDS所保存字符串的长度
        int len;
        // 记录buf数组中未使用字节的数量
        int free;
        // 字节数组，用于保存字符串
        char buf[];
}

• 结构

• free属性值为0，表示这个SDS没有未使用空间。
• len属性值为5，表示这个SDS保存了一个5字节长的字符串。
• buf属性是char类型数组，数组前5个字节分别保存'R'、'e'、'd'、'i'、's'5个字符，最后1个字节保存了空字符'\0'。
• buf长度=len+free+1。

• 策略

• SDS遵循C字符串以空字符'\0'结尾的惯例好处是可以直接重用一部分C字符串函数。
• 较C字符串SDS在len属性中记录了SDS本身的长度，从而获取SDS长度复杂度仅为O（1）。
• 较C字符串SDS读取字符不是通过结尾空字符'\0'而是len属性因此更安全，使得redis不仅可以保存文本数据，还可以保存任意格式的二进制数据。
• 较C字符串SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能，检查free属性是否满足修改需求，如果不满足，自动拓展空间然后再执行修改操作，如果空间足够，则无需执行内存重分配。
• 空间分配策略优化策略空间预分配和惰性空间释放减少了内存重分配次数。
• 空间预分配公式：
  如果修改SDS后，SDS的len将小于1MB，那么分配和len属性同样大小的free空间；
  如果修改SDS后，SDS的len将大于等于1MB，那么分配1MB的free空间。
• 惰性空间释放策略即SDS空间修改操作释放多出来的空间保留，避免缩短字符串的内存重分配和提供将来有可能的字符串增长。
• SDS提供了释放SDS空间的API，所以不必担心惰性空间释放会造成内存浪费。

2. LIST

• 描述

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。
列表键的底层实现之一就是链表。
发布与订阅、慢查询、监视器等功能也用到了链表，redis服务器本身还使用链表来保存多个客户端的状态信息，以及使用链表来构建客户端输出缓冲区。

• 定义

typeof struct listNode {
        // 前置节点
        struct listNode *prev;
        // 后置节点
        struct listNode *next;
        // 节点的值
        void *value;
} listNode;

typeof struct list {
        // 表头节点
        listNode *head;
        // 表尾节点
        listNode *tail;
        // 链表包含的节点数量
        unsigned long len;
        // 节点值复制函数
        void *(*dup)(void *ptr);
        // 节点值释放函数
        void (*free)(void *ptr);
        // 节点值对比函数
        int (*match)(void *ptr,void *key);
} list;

• 结构

• 策略

双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O（1）。
无环：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点。
带链表长度计数器：list结构的len属性使得获取链表节点数量的复杂度是O（1）。
多态：链表节点使用void *指针来保存节点值，并且可以通过list结构的dup、free、match属性为节点设置类型特定函数，所以链表可以保存各种不同类型的值。

3. HASH

• 描述

字典是一种用于保存键值对的抽象数据结构。
字典中的键都是独一无二的。
redis数据库就是使用字典来作为底层实现的。
字典还是哈希键的底层实现之一。

• 定义

typeof struct dictEntry {
        // 键
        void *key;
        // 值
        union{
                void *val;
                unit64_t u64;
                int64_t s64;
        } v;
        // 下个节点
        struct dictEntry *next;
} dictEntry;

typeof struct dictht {
        // 哈希表数组
        dictEntry **table;
        // 哈希表大小
        unsigned long size;
        // 哈希表大小掩码，用于计算索引值
        // 总是等于size-1
        unsigned long sizemask;
        // 哈希表已有节点的数量
        unsigned long used;
} dictht;

typeof struct dictType {
        // 计算哈希值的函数
        unsigned int (*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 *val);
} dictType;

typeof struct dict {
        // 类型特定函数
        dictType *type;
        // 私有数据
        void *privadata;
        // 哈希表
        dictht ht[2];
        // rehash索引
        // 当不在进行rehash时，值为-1
        int trehashidx;
} dict;

• 结构

• 策略

• ht属性是包含两个项的数组，一般情况下，字典只是用ht[0]，ht[1]只有rehash时使用。
• 哈希算法：
  hash = dict->type->hashFuncton(key);
  index = hash&dict->ht[x].sizemash;
• hash冲突的解决途径是链接地址法。
• 与java数据结构hashMap不同，是单链表，相同是，插入表头位置，新插入的节点更偏向接下来被访问。
• rehash操作：
  如果执行拓展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2的n次方幂；
  如果执行收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2的n次方幂。
• 哈希表负载因子公式：
  负载因子 = 哈希表已保存节点数量 / 哈希表大小
  load_factor = ht[0].used / ht[0].size
• 程序自动执行哈希表拓展操作的条件：
  服务器目前没有在执行BGSAVE或BGREWRITEAOF命令，并且负载因子大于等于1。
  服务器目前正在执行BGSAVE或BGREWRITEAOF命令，并且负载因子大于等于5。
• 程序自动执行哈希表收缩操作的条件：
  哈希表的负载因子小于0.1。
• 哈希表分而治之渐进式rehash步骤：
  1）为ht[1]分配空间，字典同时持有ht[0]和ht[1]。
  2）rehashidx设置为0，表示rehash开始。
  3）rehash进行期间，每次对字典执行删除、查找或者更新操作时，会在两个哈希表上进行，程序除了执行指定的操作外，还会顺带将ht[0]的键值对rehash到ht[1]，每次对字典执行添加操作时，新添加的键值对一律保存到ht[1]而不在对ht[0]添加，当rehash后，将rehashidx值增一。
  4）随着字典操作的不断进行，最终某个时间点，ht[0]的所有键值对都会rehash到ht[1]，将rehashidx设为-1，表示rehash操作完成。
  5）释放ht[0]，并将ht[1]设置为ht[0]，然后为ht[1]分配一个空白哈希表。

4. SKIPLIST

• 描述

跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。
跳跃表支持平均O（logN）、最坏O（N）复杂度的节点查找，还可以通过顺序性来批量处理节点。
大部分情况下，跳跃表的效率和平衡树相媲美，并且实现较为简单。
redis使用跳跃表一个地方是作为有序集合键的底层实现之一，另一个地方是在集群节点中用作内部数据结构。

• 定义

typeof struct zskiplistNode {
        // 后退指针
        struct zskiplistNode *backward;
        // 分值
        double score;
        // 成员对象
        robj *obj;
        // 层
        struct zskiplistLevel {
                // 前进指针
                struct zskiplistNode *forward;
                // 跨度
                unsigned int span;
        } level[];
} zskiplistNode;

typeof struct zskiplist {
        // 表头节点，表尾节点
        struct skiplistNode *header,*tail;
        // 表中节点数量
        unsigned long length;
        // 表中最大层数
        int level;
} zskiplist;

• 结构

• 策略

header指向跳跃表的表头节点。
tail指向跳跃表的表尾节点。
level记录跳跃表内表头外层数最大的节点的层数。
length记录跳跃表内表头外节点的数量。
层：前进指针用于访问位于表尾方向的节点，而跨度则记录前进指针指向节点和当前节点的距离。
后退指针指向位于当前节点的前一个节点，从表尾向表头遍历时使用。
各个节点按各自所保存的分值从小到大排列。

5. INTSET

• 描述

整数集合是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，redis就会使用整数集合作为集合键的底层实现。
可以保存整数值类型有int16_t、int32_t、int64_t。

• 定义

typeof struct intset {
        // 编码方式
        unit32_t encoding;
        // 集合包含的元素数量
        unit32_t lenght;
        // 保存元素的数组
        int8_t contents[];
} intset;

• 结构

INTSET_ENC_INT16表示整数集合的底层实现是int16_t类型的数组，集合保存的都是int16_t类型的整数值。
length属性值为5表示包含五个元素。
contents数组按从小到大属性保存集合的五个元素。
contents数组的大小等于16 * 5 = 80 位。

INTSET_ENC_INT64表示整数集合的底层实现是int64_t类型的数组，集合保存的都是int64_t类型的整数值。
length属性值为4表示包含四个元素。
contents数组按从小到大属性保存集合的四个元素。
contents数组的大小等于64 * 4 = 256 位。

• 策略

升级整数集合并添加新元素分三步：
1）根据新元素类型拓展整数集合底层数组的空间并为新元素分配空间。
2）将底层数组现有的所以元素都转换成与新元素相同的类型，并将类型转换后的元素放到正确的位上，需要维持底层数组的有序性质不变。
3）将新元素添加到底层数组。

6. ZIPLIST

• 描述

压缩列表是列表键和哈希键的底层实现之一。
当一个列表键只包含少量列表项，并且每个列表项要么是小整数值，要么是短字符串，那么redis会使用压缩列表来作为列表键的底层实现。
当一个哈希键只包含少量键值对，并且每个键值对要么是小整数值，要么是短字符串，那么redis会使用压缩列表来作为哈希键的底层实现。

• 定义

一系列特殊编码的连续内存块组成的顺序型数据结构。可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值。

• 结构

zlbytes记录整个压缩列表占用的内存字节数。
zltail记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，通过整个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址。
zllen记录压缩列表的节点数量。
entryX是压缩列表的节点。
zlend用于标记压缩列表的末端。

• 策略

压缩列表从表尾节点倒叙遍历，首先指针通过zltail偏移量指向表尾节点，然后通过指向节点记录的前一个节点的长度依次向前遍历访问整个压缩列表。

以上就是redis基本数据类型的底层数据结构。

参考文献：《redis设计与实现》