Redis|Redis 数据结构总结

Redis [字体···] [宽度···]

SDS 简单动态字符串

两种类型:

enbstr(嵌入字符串) 44byte

embstr类型字符串是嵌入RedisObject类型的,malloc一次分配对象

row(原始字符串) >44byte raw 类型,RedisObject 和 SDS 是分离的,需要 malloc 两次

struct SDS{ int8 capacity; int8 len; int8 flags; byte[] content; }

除了对象体,是 3byte

struct RedisObject{ int4 type; // 类型, list、set、zset int4 encoding; // 编码, 同一个 type 会有不同的编码 int24 lru; // lru
int32 refcount; // 引用次数, 引用计数为 0 就被销毁 void *ptr; //8byte // 数据结构指针,内容 body, }

整个对象头需占用 16 字节

malloc 分配策略是 2、4、8、16、32、64

因此按 64byte 分配,分配完头不 64-(16+3)= 45, 因为 content 的是以\0 结尾的 因此还要耗去一个字节,最后剩下 44byte 留给 embstr。

扩容策略:1M 内,以 2 倍速度扩容,>1M 每次多分配 1M。

dict 字典

使用字典的数据类型,hash、set、zset、RedisDb(kv str)

struct zset{ dict *dict; // all values value => score zskiplist *zsl; }

struct dict{ … dicth ht[2];// 两个字典 }

struct dictEntry{ void *key; void *val; dictEntry *next; // 链接下个节点 }

struct dictht{ dictEntry **table; // 二维 long size; // 一维数组长度 long used; // hash 表中已使用元素数量 }

渐进式 rehash

rehash 不是一次完成的,每次进行一部分。 为什么不一次完成? 因为 redis 的工作线程是单线程的,如果一次进行太多就会阻塞读写请求, 进而导致 redis 不能工作。

工作原理: 1)使用两个 hash 表 2)rehash 过程,查对两个进行,写对新表进行 3)其他,如果 rehash 扩容过程进行 bgsave,则优先进行 bgsave,除非达到 5*size; 缩容(10%⬇️)不会因为 bgsave 被打断

ziplist 压缩列表

struct ziplist{ int32 zlbytes; // 整个压缩列表占用的字节数 int32 zltail_offset; // 最后一个压缩列表元素距离起始位置的偏移量 int16 zllength; // 元素个数 T[] entries; // 元素内容,数组 int8 zlend; // 标志压缩列表的结束,值恒为 0xff }

Top↑