redis数据结构

redisObject

插入/更新流程

zipList

entry-data//实际数据

dictEnty*[3]

quicklistNode *prev

int attempted_compress : 1; //数据能否被压缩

int container : 2; //存储⽅式

sds结构定义在/src/sds.c的47行

listPack数据结构

quickListNode：整体是个双向链表的数据结构，但是每个quicklistNode里面又保存了指向zipList的指针

listPackEnty1

虽然 contents 被声明为 int8_t 类型的数组，但是实际上 contents 数组并不保存何 int8_t 类型的元素，而是取决于encoding字段的设置如果 encoding 属性值为 INTSET_ENC_INT16，那么 contents 就是⼀个 int16_t 类型的数组，数组中每⼀个元素的类型都是 int16_t；（INTSET_ENC_INT32，INTSET_ENC_INT64，也类似）这种编码，可以有效合理的利用内存空间，整数集合的升级操作就实现这种思想，并且不支持降级

阻塞等待客户端的数据到来

uint8_t alloc；1字节

跳表（zskiplist）数据结构

ziplist 压缩列表数据结构

自身的socket由操作系统接管

整数集合

unsigned char flagsspan style=\

int encoding : 2; //编码格式，原⽣字节数组或压缩存储

int sz;//ziplist的字节⼤⼩

zSet数据结构

next

2

unsigned long count;//所有ziplist中的总元素个数

quicklistNode *prev

sds类型

哈希表

sds本质上还是char*数组，只不过新包装了几个基本的数据元sds的几个优点体现在：1、追加的时候由于有len和alloc的存在，所以，可以直接判断当前空间情况追加到末尾2、使用不同的sdshdr（sdshdr8、sdshdr16、sdshdr32 和 sdshdr64）数据类型来标记len和alloc的不同类型，还有一个个sdshdr5弃用了，从sdshdr8(大小不超过2^8字节，即256，其中包括最后一位\\0)开始，这些元数据分别依次占用的字节数为1，2，4，8，可以根据不同大小的数据类型，还使用不同大小的对象头来节约空间；sdshdr本身设计是一个结构体，并且它用__attribute__ ((__packed__))来标记结构体，是的编译器底层放弃使用对齐的方式分配内存而是使用紧凑型（即原来多大就多大不需要对齐）3、结尾还是以\\0来结束，以适配c语言原来的接口

0（存储指向kv的指针）

处理结束

时间轴

在dict.h文件中哈希表结构struct dictht

client2

redis创建监听socket

skipList

和service建立连接

zllen，ziplist元素数量（16位）

int count : 16;//ziplist中的元素个数

refcount; //redisObject的引⽤计数，4个字节

struct zskiplistNode *backward;//后向指针 

char *zl;//quicklistNode指向的ziplist

quicklistNode *next;

buf[]

ziplist entry

int container : 2; //存储⽅式

虽然 ziplist 通过紧凑的内存布局来保存数据，节省了内存空间，但是 ziplist 也⾯临着 随之⽽来的两个不⾜：1、查询效率问题：当查询头节点和尾节点的时候可以很快找到，中间的需要遍历，所以当长度过长的时候，效率会大打折扣2、连锁更新⻛险：ziplist 在插⼊元素时，如果内存空间不够了，ziplist 还需要重新分配⼀块连续的内存空间：所谓的连锁更新：就是指当⼀个元素插⼊后，会引起当前位置元素新增 prevlensize 的空间。⽽当前位置元素的空间增加后，⼜会进⼀步引起该元素的后续元素，其 prevlensize 所需空间的增加。

int count : 16;//ziplist中的元素个数

Redis 规定嵌⼊式字符串最⼤以 64 字节存储，所以 N = 64 - 16(redisObject) - 3(sdshdr8) - 1(\\0)， N = 44 字节用64减是因为64为操作系统中，缓存行的大小为64

int level;//跳表的最大层数

int sz;//ziplist的字节⼤⼩

listPackEnty...

如果前⼀个节点的⻓度⼩于 254 字节，那么 prevlen 属性需要⽤ 1 字节的空间来保存这个⻓度值；如果前⼀个节点的⻓度⼤于等于 254 字节，那么 prevlen 属性需要⽤ 5 字节的空间来保存这个⻓度值；

int extra : 10; //预留的bit位

listPackEnty2

value

通知

quicklistNode

client1

quicklistNode *next;

*zsl

alloc

1、ZSet 当数据⽐较少时，采⽤ ziplist 存储，每个 member/score 元素紧凑排列，节省内存 2、当数据超过阈值（zset-max-ziplist-entries、zset-max-ziplist-value）后，转为 hasht able + skiplist 存储，降低查询的时间复杂度

service处理读写

void *val;

unsigned long length//跳表的⻓度

int recompress : 1; //数据是否被压缩

used//哈希表已使用大小

key

字符数组现有长度

阻塞到client1的数据处理结束

变量后使⽤冒号和数值的定义⽅法。这实际上是 C 语 ⾔中的位域定义⽅法，可以⽤来有效地节省内存开销。

zlend，标识符（结束符号）：固定255（8位）

sds ele;//Sorted Set中的元素

255(结尾标记符号)

int encoding : 2; //编码格式，原⽣字节数组或压缩存储

size //哈希表大小

SDS

哈希冲突

struct zskiplistNode *forward;同一层下一节点的前向指针

type:4//redisObject的数据类型，4个bits

dictEntry **table//哈希表数组

为什么 Sorted Set 既能⽀持⾼效的范围查询，同时还能以 O(1) 复杂度获取元素权重值？？Sorted Set 可以通过哈希计算直接查找到某个元素及其权重值，相较于通过跳表查找单个元素，使⽤哈希表就有效提升了查询效率。范围查询则可以通过跳表来高效查询

unsigned long len; //quicklistNodes的个数

这样⼀来，quicklist 通过控制每个 quicklistNode 中，ziplist 的⼤⼩或是元素个数，就有效减少了在 ziplist 中新增或修改元素后，发⽣连锁更新的情况，从⽽提供了更好的访问性能。

查询流程

跳表的结构定义在/src/server.h的814行其查询、删除、新增、更新的逻辑在/src/t_zset.c的132

dictEntry 结构⾥键值对中的值是⼀个「联合体 v」定义的，因此，键值对中的值可以是⼀个指向实际值的指针，或者是⼀个⽆符号的 64 位整数或有符号的 64 位整数或double 类的值。这么做的好处是可以节省内存空间，因为当「值」是整数或浮点数时，就可以将值的数据内嵌在 dictEntry结构⾥，⽆需再⽤⼀个指针指向实际的值，从⽽节省了内存空间

sdshdr8的具体实现，其他类似

listpack 是为了替代 ziplist 为设计的，但因为 List/Hash/Set/ZSet 都严重依赖 ziplist， 所以这个替换之路很漫⻓，⽬前只有 Stream 数据类型⽤到了 listpack

encoding:4; //redisObject的编码类型，4个bits

*ptr; //指向值的指针，8个字节

//编码⽅式uint32_t encoding;

char buf[]span style=\

rehashidx

哈希表的定义在/src/dict.h的70行开始其dictRehash逻辑在/src/dict.c的188行

redisObject的结构定义，在/src/server.h 的617行

当查询⼀个结点时，跳表会先从头结点的最⾼层开始，查找下⼀个结点。⽽由于跳表 结点同时保存了元素和权重，所以跳表在⽐较结点时，相应地有两个判断条件：1、当查找到的结点保存的元素权重，⽐要查找的权重⼩时，跳表就会继续访问该层上的下⼀个结点。 2、当查找到的结点保存的元素权重，等于要查找的权重时，跳表会再检查该结点保存的 SDS类型数据，是否⽐要查找的 SDS 数据⼩。如果结点数据⼩于要查找的数据时，跳表仍然会继续访问该层上的下⼀个结点。但是，当上述两个条件都不满⾜时，跳表就会⽤到当前查找到的结点的 level 数组了。跳表会使⽤当前结点 level 数组⾥的下⼀层指针，然后沿着下⼀层指针继续查找，这就相当于跳到了下⼀层接着查找。

Redis 的 key 是 String 类型，但 value 可以是很多类型（String/List/Hash/Set/ZSet 等），所以 Redis 要想存储多种数据类型，就要设计⼀个通⽤的对象进⾏封装，这个对象就 是 redisObject。redisObject 更像是连接「上层数据类型」和「底层数据结构」之间的桥梁。

unsigned long span;每一层的跨度

double score;//元素权重值 

zltail，ziplist最后一个元素偏移量（32位）

double d;

整数集合是 Set 对象的底层实现之⼀。当⼀个 Set 对象只包含整数值元素，并且元素数量不时，就会使⽤整数集这个数据结构作为底层实现。整数集合本质上是⼀块连续内存空间

如果当前节点的数据是整数，则 encoding 会使⽤ 1 字节的空间进⾏编码。如果当前节点的数据是字符串，根据字符串的⻓度⼤⼩，encoding 会使⽤ 1 字节/2字节/5字节的空间进⾏编码。

flags

字符数组的空间⻓度

fd就绪

sds数据结构

client2写数据

当sds小于44字节时，sds会和redisObject一起存储，这种存储方式就叫做：嵌入式字符串，这样只分配 1 次内存

zskiplistNode *header//头节点

int attempted_compress : 1; //数据能否被压缩

struct zskiplistLevel;（level[]）//节点的level数组，保存每层上的前向指针和跨度

zskiplistNode数据结构

quickList数据结构

int64_t s64;

sizemask //哈希表⼤⼩掩码，⽤于计算索引值

len

listPack总字节数

entry-len//编码类型+实际数据的总长度

prevlen（前一位的长度）

dictht*[2]

service处理

int extra : 10; //预留的bit位

qucikList

uint8_t len；1字节

//集合包含的元素数量uint32_t length;

listPackRedis 5.0添加

在 listpack 中，因为每个列表项只记录⾃⼰的⻓度，⽽不会像 ziplist 中的列表项那样，会记录前⼀项的⻓度。所以，当我们在 listpack 中新增或修改元素时，实际上只会涉及每个列表 项⾃⼰的操作，⽽不会影响后续列表项的⻓度变化，这就避免了连锁更新。

跳表（skiplist）

rehash时用来交替使用的两个dictht

listpack.c ⽂件中有很多宏定义，这些宏定义其实就对应了 listpack 的元素编码类型。具体来说，listpack 元素会对不同⻓度 的整数和字符串进⾏编码，

font color=\"#323232\

字符数组保存实际的数据

....

zskiplistNode *tail//尾节点

listPack从左到右遍历

uint64_t u64;

当创建⼀个 zset 时，代码中会相继调⽤ dictCreate 函数创建 zset 中的哈希表，以及调⽤ zslCreate 函数创建跳表数据一致性：当往 Sorted Set 中插⼊数据时，zsetAdd 函数就会被调⽤，zsetAdd 函数会判定 Sorted Set 采⽤的是 ziplist 还是 skiplist 的编码⽅式，从而走不同的逻辑。Sorted Set 在执⾏数据插⼊或是数据更新的过程中，会依次在跳表和哈希表中插⼊或更新相应的数据，从⽽保证了跳表和哈希表中记录的信息 ⼀致

value的结构

redis数据类型及其底层实现（基于5.0.13）

*dict

Hash表是否在进⾏rehash的标识，-1表示没有进⾏rehash

rehash过程1、在正常服务请求阶段，所有的键值对写⼊哈希表 ht[0]。 2、当进⾏ rehash 时，键值对被迁移到哈希表 ht[1]中。 最后，当迁移完成后，ht[0]的空间会被释放，并把 ht[1]的地址赋值给 ht[0]，ht[1]的表⼤⼩ 设置为 0。3、这样⼀来，⼜回到了正常服务请求的阶段，ht[0]接收和服务请求，ht[1]作为下 ⼀次 rehash 时的迁移表。

encoding（当前项的长度编码）

1

dictEntry：Hash 表就是⼀个数组，数组⾥的每个元素是⼀个哈希桶（也叫做Bucket），第⼀个数组元素被编为哈希桶 0哈希表是⼀个数组（dictEntry **table），数组的每个元素是⼀个指向「哈希表节点（dictEntry）」的指针

client1写数据

data（实际数据）

level数据结构

在dict.h文件中还有一个结构体：dict

zlbytes，记录整个压缩列表占⽤对内存字节数；（32位）

entry-encoding//编码类型

lru:LRU_BITS; //redisObject的LRU时间，LRU_BITSspan style=\

intset 数据结构

int recompress : 1; //数据是否被压缩

char *zl;//quicklistNode指向的ziplist

listPack的元素数量

//保存元素的数组int8_t contents[];

redis本身就是一个巨大的“hashmap”，哈希表结构存储了所有的健值对，只不过有value的类型不同，引发的各种数据结构由此结构引出哈希表的连个问题？1、哈希冲突：当出现哈希冲突的时候，我们用链式哈希来解决这个问题，这个和hashmap一样，当链条过长时，效率就成了问题，所以引出了rehash操作2、rehash：rehash本身是一个开销很大的操作，所以有了渐近式rehash