【redis】基本数据结构简单源码解析
（我贴的代码是本机6.2.1版本）
string:SDS(简单动态字符串)
redis是以c语⾔编写，但是redis的字符串没有直接使⽤C语⾔的以null结尾的字符串，⽽是采⽤SDS（Simple Dynamic String：简单动态
字符串）
struct SDS<T> {
T capacity; // 数组容量Redis  字符串的长度不得超过 512M 字节。创建字符串时 len 和 capacity ⼀样长，不会多分配冗余空间，这是因为绝⼤多数场景下我们不会使 T len; // 数组长度因为把长度写在头部，不⽤像C语⾔⼀样以\0识别字符串结束符，所以sds是⼆进制安全的
byte flags; // sds类型，5 8 16 32 64位
byte[] content; // 数组内容
}
//追加字符串append
sds sdscatlen(sds s, const void *t, size_t len) {
size_t curlen = sdslen(s);//原字符串长度
s = sdsMakeRoomFor(s,len);//空间调整
if (s == NULL) return NULL;//内存不⾜
memcpy(s+curlen, t, len);//追加字符串到当前的content数组中
sdssetlen(s, curlen+len);//设置追加后的长度值
s[curlen+len] = '\0';//与C语⾔字符串⼀致，可以printf()调试、便于直接使⽤ glibc 的字符串处理函数
return s;
}
/
/按需调整空间
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
size_t avail = sdsavail(s);
size_t len, newlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
size_t usable;
/* 空间⾜够就直接返回新字符串 */
if (avail >= addlen) return s;
//接下来是空间不⾜的操作
len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
newlen = (len+addlen);
assert(newlen > len);  /* Catch size_t overflow */
if (newlen < SDS_MAX_PREALLOC) //⼩于SDS_MAX_PREALLOC（1M）时，每次分配的空间加倍
newlen *= 2;
else //⼤于SDS_MAX_PREALLOC后，每次加1Mredis八种数据结构
newlen += SDS_MAX_PREALLOC;
type = sdsReqType(newlen);//根据长度划分新字符串所属的SDS数据类型
/* 不要使⽤类型5：⽤户正在追加字符串，⽽类型5⽆法记住空格，因此必须在每次追加操作时调⽤sdsMakeRoomFor（） */    if (type == SDS_TYPE_5) type = SDS_TYPE_8;
hdrlen = sdsHdrSize(type);//根据所属SDS数据类型计算所占内存
assert(hdrlen + newlen + 1 > len);  /* Catch size_t overflow */
if (oldtype==type) {//所属的SDS数据类型不变时
newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
if (newsh == NULL) return NULL;
s = (char*)newsh+hdrlen;
} else {
/* Since the header size changes, need to move the string forward,
* and can't use realloc
如果类型发⽣变化，地址内容不可复⽤，所以新的空间
*/
newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
if (newsh == NULL) return NULL;
memcpy((char*)newsh+hdrlen, s, len+1);//将s复制到(char*)newsh+hdrlen  +1是复制上\0
s_free(sh);//释放前⾯的内存空间
s = (char*)newsh+hdrlen;//调整s开始的位置，即地址空间指向新的buf开始的位置
s[-1] = type;//flag位置
sdssetlen(s, len);//分配len的值
}
usable = usable-hdrlen-1;
if (usable > sdsTypeMaxSize(type))//实际占⽤不能⼤于所属SDS数据类型最长占⽤字节
usable = sdsTypeMaxSize(type);
sdssetalloc(s, usable);//(根据类型)设置sds字符串容量
return s;
}
注意sdsMakeRoomFor不仅⽤来增加内存，还可以⽤来修剪字符串.以下是我在sdsIncrLen头部注释看到的：
s = sdsMakeRoomFor(s, BUFFER_SIZE);（BUFFER_SIZE：缓冲区）当前字符串⽐之前缓冲区长度⼩的话，并不直接修剪。直到刷新缓冲区后
/* Increment the sds length and decrements the left free space at the
* end of the string according to 'incr'. Also set the null term
* in the new end of the string.
*
* This function is used in order to fix the string length after the
* user calls sdsMakeRoomFor(), writes something after the end of
* the current string, and finally needs to set the new length.
*
* Note: it is possible to use a negative increment in order to
* right-trim the string.
*
* Usage example:
*
* Using sdsIncrLen() and sdsMakeRoomFor() it is possible to mount the
* following schema, to cat bytes coming from the kernel to the end of an
* sds string without copying into an intermediate buffer:
*
* oldlen = sdslen(s);
* s = sdsMakeRoomFor(s, BUFFER_SIZE);
* nread = read(fd, s+oldlen, BUFFER_SIZE);
* ... check for nread <= 0 and handle it ...
* sdsIncrLen(s, nread);
*/
void sdsIncrLen(sds s, ssize_t incr) {
embstr vs raw
Redis 的字符串有两种存储⽅式，在长度特别短时，使⽤ emb 形式存储 (embeded)，当 长度超过 44 时，使⽤ raw 形式存储。
embstr 存储形式是这样⼀种存储形式，它将 RedisObject 对象头和 SDS 对 象连续存在⼀起，使⽤ malloc ⽅法⼀次分配。⽽ raw 存储形式不⼀样，它需要两次 malloc，两个对象头在内存地址上⼀般是
不连续的。 ⽽内存分配器能分配的最⼤单位内存是64字节，如果总体超出了 64 字节，redis 认为它是⼀个 ⼤字符串，不再使⽤ emdstr 形式存储，⽽该⽤ raw 形式。
在字符串⽐较⼩时，SDS 对象头的⼤⼩是 capacity+3，⾄少是 3。
SDS 结构体中的 content 中的字符串是以字节\0 结尾的字符串。
SDS优势
获取字符串长度时间复杂度O（1）
避免内存溢出
减少内存重分配
空间预分配
惰性空间释放
hash、set、zset：dict(字典)
dict 是 Redis 服务器中出现最为频繁的复合型数据结构，除了 hash 结构的数据会⽤到字典外，整个 Redis 数据库的所有 key 和 value 也组成了⼀个全局字典，还有带过期时间的 key 集合也是⼀个字典。zset 集合中存储 value 和 score 值的映射关系也是通过 dict 结构实现的。
dict 结构内部包含两个 hashtable，通常情况下只有⼀个 hashtable 是有值的。但是在 dict 扩容缩容时，需要分配新的 hashtable，然后进⾏渐进式搬迁，这时候两个 hashtable 存储的分别是旧的 hashtable 和新的 hashtable。待搬迁结束后，旧的 hashtable 被删除，新的hashtable 取⽽代之。
hashtable的结构与java hashMap⼏乎⼀样，都是以数组+链表进⾏分桶的⽅式解决hash冲突。第⼀维是数组，第⼆维是链表。数组中存储的是第⼆维链表的第⼀个元素的指针。
struct dictEntry {
void* key;
void* val;
dictEntry* next; // 链接下⼀个 entry
}
struct dictht {
dictEntry** table; // ⼆维
long size; // 第⼀维数组的长度
long used; // hash 表中的元素个数
...
}
渐进式 rehash
⼤字典的扩容是⽐较耗时间的，需要申请新的数组，然后将旧字典所有链表中的元素挂接到新的数组
下⾯，这是⼀个 O(n)级别的操作，单线程的redis 很难承受这样耗时的过程，所以 Redis 使⽤渐进式 rehash 搬迁。
hash函数
评判hash函数好坏的依据在于其是否可以将key打散的⽐较均匀，并且性能⽐较好。redis 的字典默认的 hash 函数是 siphash。siphash 算法即使在输⼊ key 很⼩的情况下，也可以产⽣随机性特别好的输出，⽽ 且它的性能也⾮常突出。
hash攻击
如果 hash 函数存在偏向性，⿊客就可能利⽤这种偏向性对服务器进⾏攻击。存在偏向 性的 hash 函数在特定模式下的输⼊会导致 hash
第⼆维链表长度极为不均匀，甚⾄所有的元素都集中到个别链表中，直接导致查效率急剧下降，从 O(1)退化到 O(n)。有限的服务器计算能⼒将会被 hashtable 的查效率彻底拖垮。这就是所谓 hash 攻击。
扩容条件
正常情况下，当hash表中元素的个数等于第⼀维数组的长度时，就会开始扩容，扩容的新数组是原数组⼤⼩的2倍。不过如果redis正在做bgsave，为了减少内存页的过多分离 (bgsave涉及Copy On Write)，redis 尽量不去扩容 (dict_can_resize)，但是如果 hash 表已经⾮常满 了，元素的个数已经达到了第⼀维数组长度的 5 倍 (dict_force_resize_ratio)，说明 hash 表 已经过于拥挤了，这个时候就会强制扩容。
缩容条件
当 hash 表因为元素的逐渐删除变得越来越稀疏时，Redis 会对 hash 表进⾏缩容来减少 hash 表的第⼀维数组空间占⽤。缩容的条件是元素个数低于数组长度的 10%。缩容不会考虑 Redis 是否正在做 bgsave。
set（集合）的结构
redis ⾥⾯ set 的结构底层实现也是字典，只不过所有的value都是 NULL，其它的特性和字典⼀模⼀样。
intset
当set中元素都是整数并且元素个数较少（最多64以内）时，采⽤intset，它是紧凑的数组结构
为什么不⽤ziplist？因为set的value全是空值，不需要再单独记录每个元素内容
struct intset<T> {
int32 encoding; // 决定整数位宽是 16 位、32 位还是 64 位
int32 length; // 元素个数
int<T> contents; // 整数数组，可以是 16 位、32 位和 64 位
}
zset、hash：ziplist(压缩列表)
Redis 为了节约内存空间使⽤，zset和 hash容器对象在元素个数较少的时候，采⽤压缩列表 (ziplist) 进⾏存储。压缩列表是⼀块连续的内存空间，元素之间紧挨着存储，没有任何冗余空隙。
struct ziplist<T> {
int32 zlbytes; // 整个压缩列表占⽤字节数
int32 zltail_offset; // 最后⼀个元素距离压缩列表起始位置的偏移量，⽤于快速定位到最后⼀个节点，⽀持双向遍历
int16 zllength; // 元素个数
T[] entries; // 元素内容列表，挨个挨个紧凑存储
int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
}
struct entry {
int<var> prevlen; // 前⼀个 entry 的字节长度
int<var> encoding; // 元素类型编码
optional byte[] content; // 元素内容
}
因为 ziplist 都是紧凑存储，没有冗余空间 (对⽐⼀下 Redis 的字符串结构)。意味着插 ⼊⼀个新的元素就需要调⽤ realloc 扩展内存。取决于内存分配器算法和当前的ziplist 内存 ⼤⼩，realloc 可能会重新分配新的内存空间，并将之前的内容⼀次性拷贝到，也可能在原有的地址上进⾏扩展，这时就不需要进⾏旧内容的内存拷贝。 如果 ziplist 占据内存太⼤，重新分配内存和拷贝内存就会有很⼤的消耗。所以 ziplist 不适合存储⼤型字符串，存储的元素也不宜过多。
级联更新
每个 entry 都会有⼀个 prevlen 字段存储前⼀个 entry 的长度。如果内容⼩于 254 字节，prevlen ⽤ 1 字节存储，否则就是 5 字节。这意味着如果某个 entry 经过了修改 操作从 253 字节变成了 254 字节，那么它的下⼀个 entry 的 prevlen 字段就要更新，从 1 个字节扩展到 5 个字节；如果这个 entry 的长度本来也是 253 字节，那么后⾯ entry 的 prevlen 字段还得继续更新。 如果 ziplist ⾥⾯每个 entry 恰好都存储了 253 字节的内容，那么第⼀个 entry 内容的 修改就会导致后续所有 entry 的级联更新，这就是⼀个⽐较耗费计算资源的操作。
删除中间的某个节点也可能会导致级联更新，某个节点A前⼀个节点B原本是253字节内，它前前节点C⼤于253，B被删除后，A的prevlen就从1字节变成5字节，引发级联更新，A后⾯的假如之前prevlen = 1，现在全部要改为5了。
stream：listpack(紧凑列表)
5.0新增的数据结构，它是对 ziplist 结构的改进，在存储空间上会更加节省，⽽且结构上也⽐ ziplist 要精简。
listpack相对ziplist，字符串内部length放在字符串尾部，并且记录的是当前元素的长度。正因如此，它不需要存zltail_offset，因为可以⽤total_bytes、最后⼀个元素的length来计算。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。