万字长文带你深入Redis底层数据布局
Redis数据库的数据布局Redis 的键值对中的 key 就是字符串对象，而 value 就是指Redis的数据类型，可以是String，也可以是List、Hash、Set、 Zset 的数据类型。
其实是Redis 底层使用了一个全局哈希表保存所有键值对，哈希表的最大好处就是 O(1) 的时间复杂度快速查找到键值对。哈希表其实就是一个数组，数组中的元素叫做哈希桶。
https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202404270802767.png
[*]redisDb 布局，表示 Redis 数据库的布局，布局体里存放了指向了 dict 布局的指针；//默认有16个数据库
[*]dict 布局，布局体里存放了 2 个哈希表，正常环境下都是用哈希表1，哈希表2只有在 rehash 的时候才用；
[*]ditctht 布局，表示哈希表的布局，布局里存放了哈希表数组，数组中的每个元素都是指向一个哈希表节点布局（dictEntry）的指针；
[*]dictEntry 布局，表示哈希表节点的布局，布局里存放了 void* key 和 void* value 指针， key 指向的是 String 对象，而 value 就是指Redis的几种数据类型。
struct redisServer {
//...
redisDb *db;
//...
int dbnum; //默认16个
}
typedef struct redisDb {
dict *dict; //全局hash表
//...
} redisDb;
struct dict {
//...
dictht ht; //两个dictEntry，一个开始为空，rehash迁移时使用
//...
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
};
typedef struct dictht {
dictEntry **table; // 哈希表节点数组
unsigned long size; // 哈希表大小
unsigned long sizemask; // 哈希表大小掩码，用于计算索引值，总是等于size-1
unsigned long used; // 该哈希表已有节点的数量
} dictht;
struct dictEntry {//具体的对象
void *key; //key
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;//value
struct dictEntry *next; //下一个节点的指针
void *metadata[];
};void *key 和 void *value 指针指向的就是 Redis 对象。Redis中有全局hash表，key是String,value是不同类型的对象，假如是Java，那可以直接用Map来通用表示。而Redis直接由C语言实现，因此具体的每个对象都由 redisObject 布局表示，用type来表示具体类型，如下：
typedef struct redisObject {
unsigned type: 4; // 对象类型
unsigned storage: 2; // REDIS_VM_MEMORY or REDIS_VM_SWAPPING
unsigned encoding: 4; // 对象所使用的编码
unsigned lru: 22; // lru time (relative to server.lruclock)
int refcount; // 对象的引用计数
void *ptr; // 指向对象的底层实现数据结构
} robj;https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202404270802790.png
[*]type，标识该对象是什么类型的对象（String 对象、 List 对象、Hash 对象、Set 对象和 Zset 对象）；
[*]encoding，标识该对象使用了哪种底层的数据布局；
[*]ptr，指向底层数据布局的指针。
如图，Redis 数据类型（也叫 Redis 对象）和底层数据布局的对应关图：
https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202404270802383.png
[*]默认环境下hash使用listpack存储，当保存的字段-值的数量大于512个大概单个字段的值大于64个字节时，改为hashtable。
[*]默认环境下zSet使用listpack做为存储布局，当集合中的元素大于等于128个或是单个值的字节数大于等于64，存储布局会修改为skiplist。
这几个值都是可以修改的，没必要记；在redis.conf里
hash-max-listpack-entries 512
hash-max-listpack-value 64
zset-max-listpack-entries 128
zset-max-listpack-value 64SDS
Simple Dynamic String，简朴动态字符串
C语言中的缺陷
获取字符串长度复杂度为O(n)
在 C 语言里，字符数组的结尾位置用“\0”表示，意思是指字符串的结束。
因此c语言获取字符串长度的函数 strlen，就是遍历字符数组中的每一个字符，遇到字符为 “\0” 后，就会停止遍历，然后返回已经统计到的字符个数，即为字符串长度，因此复杂度为O(n)
字符串只能保存文本数据
字符数组的结尾位置用“\0”表示
因此，除了字符串的末尾之外，字符串里面不能含有 “\0” 字符，否则最先被程序读入的 “\0” 字符将被误认为是字符串结尾，这个限定使得 C 语言的字符串只能保存文本数据，不能保存像图片、音频、视频文化这样的二进制数据
有大概发生缓冲区溢出
C 语言的字符串是不会记录自身的缓冲区巨细的，以是 strcat 函数假定程序员在执行这个函数时，已经为 dest 分配了足够多的内存，可以容纳 src 字符串中的所有内容，而一旦这个假定不成立，就会发生缓冲区溢出将大概会造成程序运行终止。
https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202404270802885.png
SDS布局
https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202404270802017.png
[*]len，记录了字符串长度。这样获取字符串长度的时候，只必要返回这个成员变量值就行，时间复杂度只必要 O（1）。
[*]alloc，分配给字符数组的空间长度。这样在修改字符串的时候，可以通过 alloc - len 盘算出剩余的空间巨细，可以用来判断空间是否满足修改需求，假如不满足的话，就会主动将 SDS 的空间扩容至执行修改所需的巨细，然后才执行现实的修改操作。这样就不会发生缓冲区溢出
[*]flags，用来表示不同类型的 SDS。一共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。
[*]buf[]，字符数组，用来保存现实数据。不但可以保存字符串，也可以保存二进制数据。
SDS 的 API 使用二进制的方式来处理 SDS 存放在 buf[] 里的数据，使得 Redis 不但可以保存文本数据，也可以保存任意格式的二进制数据。
SDS的动态其实指的就是动态扩容
hisds hi_sdsMakeRoomFor(hisds s, size_t addlen)
{
... ...
// s目前的剩余空间已足够，无需扩展，直接返回
if (avail >= addlen)
return s;
//获取目前s的长度
len = hi_sdslen(s);
sh = (char *)s - hi_sdsHdrSize(oldtype);
//扩展之后 s 至少需要的长度
newlen = (len + addlen);
//根据新长度，为s分配新空间所需要的大小
if (newlen < HI_SDS_MAX_PREALLOC)
//新长度<HI_SDS_MAX_PREALLOC 则分配所需空间*2的空间
//默认定义HI_SDS_MAX_PREALLOC为(1024*1024)即1M
newlen *= 2;
else
//否则，分配长度为目前长度+1MB
newlen += HI_SDS_MAX_PREALLOC;
...
}
// #define HI_SDS_MAX_PREALLOC (1024*1024)关键在于哈希表插入时会去查抄是都正在Rehash，假如不是，那就往0号hash表中插入；假如是，那就直接往1号hash表中插入，因为假如正在Rehash还往0号hash表中插入，那么最终还是要rehash到1号hash表的
typedef struct listNode {
//前置节点
struct listNode *prev;
//后置节点
struct listNode *next;
//节点的值
void *value;
} listNode;rehash的触发条件
负载因子 = 哈希表已保存节点数量/哈希表巨细
触发 rehash 操作的条件，主要有两个：
[*]当负载因子大于等于 1 ，并且 Redis 没有在执行 bgsave 命令大概 bgrewiteaof 命令，也就是没有执行 RDB 快照或没有举行 AOF 重写的时候，就会举行 rehash 操作。
[*]当负载因子大于等于 5 时，此时说明哈希辩论非常严肃了，不管有没有有在执行 RDB 快照或 AOF 重写，都会强制举行 rehash 操作
整数集合
当一个 Set 对象只包含整数值元素，并且元素数量不大时，就会使用整数集这个数据布局作为底层实现。
typedef struct list {
//链表头节点
listNode *head;
//链表尾节点
listNode *tail;
//节点值复制函数
void *(*dup)(void *ptr);
//节点值释放函数
void (*free)(void *ptr);
//节点值比较函数
int (*match)(void *ptr, void *key);
//链表节点数量
unsigned long len;
} list;保存元素的容器是一个 contents 数组，固然 contents 被声明为 int8_t 类型的数组，但是现实上 contents 数组并不保存任何 int8_t 类型的元素，contents 数组的真正类型取决于 intset 布局体里的 encoding 属性的值。比如：
[*]假如 encoding 属性值为 INTSET_ENC_INT16，那么 contents 就是一个 int16_t 类型的数组，数组中每一个元素的类型都是 int16_t；
[*]假如 encoding 属性值为 INTSET_ENC_INT32，那么 contents 就是一个 int32_t 类型的数组，数组中每一个元素的类型都是 int32_t；
[*]假如 encoding 属性值为 INTSET_ENC_INT64，那么 contents 就是一个 int64_t 类型的数组，数组中每一个元素的类型都是 int64_t；
整数集合升级
将一个新元素加入到整数集合里面，假如新元素的类型（int32_t）比整数集合现有所有元素的类型（int16_t）都要长时，整数集合必要先举行升级，也就是按新元素的类型（int32_t）扩展 contents 数组的空间巨细，然后才能将新元素加入到整数集合里，当然升级的过程中，也要维持整数集合的有序性。
整数集合升级的好处：
假如要让一个数组同时保存 int16_t、int32_t、int64_t 类型的元素，最简朴做法就是直接使用 int64_t 类型的数组。不过这样的话，当假如元素都是 int16_t 类型的，就会造成内存浪费。
使用整数集合主要思想就是为了节省内存开销。
跳表
跳表的上风是能支持平均 O(logN) 复杂度的节点查找。
跳表是在链表基础上改进过来的，实现了一种「多层」的有序链表，这样的好处是能快读定位数据。
struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; /* Next entry in the same hash bucket. */
void *metadata[];
};跳表布局如下：
https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202404270803939.png
跳表的相邻两层的节点数量最抱负的比例是 2:1，查找复杂度可以降低到 O(logN)。
Redis中的跳表是两步两步跳的吗？
假如接纳新增节点大概删除节点时，来调整跳表节点以维持比例2：1的方法的话，显然是会带来额外开销的。
跳表在创建节点时候，会生成范围为的一个随机数，假如这个随机数小于 0.25（相当于概率 25%），那么层数就增长 1 层，然后继续生成下一个随机数，直到随机数的效果大于 0.25 结束，最终确定该节点的层数。因为随机数取值在[0,0.25）范围内概率不会凌驾25%，以是这也说明白增长一层的概率不会凌驾25%。这样的话，当插入一个新结点时，只需修改前后结点的指针，而其它结点的层数就不必要随之改变了，这样就降低插入操作的复杂度。
// #define ZSKIPLIST_P 0.25int zslRandomLevel(void) { static const int threshold = ZSKIPLIST_P*RAND_MAX; int level = 1; //初始化为一级索引 while (random() < threshold) level += 1;//随机数小于 0.25就增长一层 //假如level 没有凌驾最大层数就返回，否则就返回最大层数 return (level
页:
[1]