Redis设计与实现数据结构篇 SDS、链表、字典
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实现了空间预分配和惰性空间释放两种优化策略。- 空间预分配
优化字符串增长操作，当对一个SDS字符串进行扩展时，额外分配一定的free空间。
扩展后，如果len <1 Mb，free=len；否则，free= 1 Mb; - 惰性空间释放
优化字符串缩短操作，当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]。
