Redis设计与实现数据结构篇 SDS、链表、字典

简单动态字符串SDS

在redis中，只有在一些无需对字符串进行修改的地方，才会使用C字符串，例如打印日志。而在有经常修改需求的情况下，使用SDS来实现数据存储。

redis> SET msg "hello world"
OK

该键值对均以SDS存储。

redis> RPUSH fruits "apple" "banana" "cherry"
(integer) 3

键以SDS存储,值为包含3个SDS的列表。
SDS还被用于缓冲区的实现。

SDS实现

struct sdshdr{
    int len;       //记录SDS中已用长度
    int free;      //未使用字节长度
    char buf[];    //存储字节数组
};

SDS与C字符串区别

常数复杂度获取字符串长度

SDS实现中len记录了字符串长度，因此可以O(1)获取lenth，而C字符串需要O(n)。
杜绝缓冲区溢出

SDS字符串进行修改操作时，会自动判断SDS空间是否满足要求，如果不满足会自动将SDS空间扩展然后再进行修改，避免了缓冲区溢出问题，而C字符串则需要手动修改空间大小容易出现问题。
减少字符串修改带来的内存重分配次数

C字符串在执行拼接(append)前，要先通过内存重分配扩展底层数组的长度，如果忽略这一步会造成缓冲区溢出。在执行截断操作(trim)前，要先通过内存重分配始放不再使用的内存部分，否则会造成内存泄漏。频繁操作内存会产生效率问题，SDS通过free空间解除了字符串长度与底层数组长度之间的关系。
SDS实现了空间预分配和惰性空间释放两种优化策略。
1. 空间预分配
  优化字符串增长操作，当对一个SDS字符串进行扩展时，额外分配一定的free空间。
  扩展后，如果len <1 Mb，free=len；否则，free= 1 Mb;
2. 惰性空间释放
  优化字符串缩短操作，当SDS字符串缩短时，并不立即回收空间，而是记录其free。
  有需要时可以调用相应API进行回收。
二进制安全
SDS API以二进制安全的方式处理buf[]中的数据，程序不会对其中数据做出限制，过滤等操作,而C字符串只能存储文本。
兼容C字符串函数
SDS遵循C字符串中以空字符串 ' \0 '结尾的规范（该结尾占用空间但不计入len），这样可以便于直接重用C字符串的函数。

链表

链表节点及链表实现

typedef struct listNode{
    struct listNode *prev;
    struct listNode *next;
    void *value;
}listNode;

typedef struct list{
    listNode *head;
    listNode *tail;
    unsigned long len;                    //链表长度
    void *(*dup)(void *ptr);              //节点值复制函数
    void (*free)(void *ptr);              //节点值释放函数
    int (*match)(void *ptr, void *key);   //节点值对比函数
}list;

list示意图

Redis链表是实际是双端链表，性质基本与java双端链表相同，这里就不赘言了。但需要注意的是其实现中的节点值复制函数，其入参为 void* ，可以传入多种类型的值，具备多态性。
Redis链表被广泛用于实现Redis中的各种功能，如列表键、发布与订阅、慢查询、监视器等。

字典

哈希表节点及哈希表实现

Redis字典使用哈希表作为底层实现，直接上数据结构。

typedef struct dictEntry{ //哈希表节点
    void *key;
    union{
        void *val;       //值可以为指针，可以为unit_t整数，
        unit64_t u64;     //也可以为int64_t整数
        int64_t s64;
    } v;
    struct dictEntry *next;    //同样以链地址法解决hash冲突
}dictEntry;

typedef struct dictht{       //哈希表
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;  //哈希掩码，总是等于size-1
    unsigned long used;      //已使用大小
}dictht;

typedef struct dict{         //字典
    dictType *type;
    void *privdata;          //type和privdata为实现字典多态设置
    dictht ht[2];            //长度为2的哈希表数组 用于rehash
    int rehashidx;           //标识rehash进度
}dict;

哈希算法要点

首先用哈希函数计算哈希值，后与sizemask进行逻辑与操作得索引值。
解决键冲突方式为链地址法，采用头插法，因为哈希表没有维护尾指针，头插法效率高。

rehash发生于哈希表的扩容或收缩，条件如下

if(load_factor>=5){
  rehash();
}else if(load_factor>=1&&!BGSAVE()&&!BGREWRITEAOF()){
  rehash();      //因为bgsave()或bgrewriteaof()时，redis创建子进程进行
}else if(load_factor<0.1){       //cow操作，消耗大量内存，因此不进行哈希
  rehash();
}

为了防止rehash时服务器停止服务，rehash过程采用渐进式方式，外部请求到来时，删除、查找、更新操作分别在 ht[0] 和 ht[1] 上进行，插入操作在 ht[1] 中进行。rehashidx 记录了rehash进度，每当某哈希节点rehash完成，rehashidx 加一，全部完成时，恢复 -1，并将 ht[1] 赋予 ht[0] ，清空 ht[1]。

Redis设计与实现数据结构篇 SDS、链表、字典

Redis设计与实现数据结构篇 SDS、链表、字典

简单动态字符串SDS

SDS实现

SDS与C字符串区别

链表

链表节点及链表实现

字典

哈希表节点及哈希表实现

哈希算法要点