Redis数据库的数据布局
Redis 的键值对中的 key 就是字符串对象，而 value 就是指Redis的数据类型，可以是String，也可以是List、Hash、Set、 Zset 的数据类型。
其实是Redis 底层使用了一个全局哈希表保存所有键值对，哈希表的最大好处就是 O(1) 的时间复杂度快速查找到键值对。哈希表其实就是一个数组，数组中的元素叫做哈希桶。
- 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[2]; //两个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[];
- };
- 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;
- type，标识该对象是什么类型的对象（String 对象、 List 对象、Hash 对象、Set 对象和 Zset 对象）；
- encoding，标识该对象使用了哪种底层的数据布局；
- ptr，指向底层数据布局的指针。
如图，Redis 数据类型（也叫 Redis 对象）和底层数据布局的对应关图：
- 默认环境下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 64
Simple Dynamic String，简朴动态字符串
C语言中的缺陷
获取字符串长度复杂度为O(n)
在 C 语言里，字符数组的结尾位置用“\0”表示，意思是指字符串的结束。
因此c语言获取字符串长度的函数 strlen，就是遍历字符数组中的每一个字符，遇到字符为 “\0” 后，就会停止遍历，然后返回已经统计到的字符个数，即为字符串长度，因此复杂度为O(n)
字符串只能保存文本数据
字符数组的结尾位置用“\0”表示
因此，除了字符串的末尾之外，字符串里面不能含有 “\0” 字符，否则最先被程序读入的 “\0” 字符将被误认为是字符串结尾，这个限定使得 C 语言的字符串只能保存文本数据，不能保存像图片、音频、视频文化这样的二进制数据
有大概发生缓冲区溢出
C 语言的字符串是不会记录自身的缓冲区巨细的，以是 strcat 函数假定程序员在执行这个函数时，已经为 dest 分配了足够多的内存，可以容纳 src 字符串中的所有内容，而一旦这个假定不成立，就会发生缓冲区溢出将大概会造成程序运行终止。
SDS布局
- 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)
- typedef struct listNode {
- //前置节点
- struct listNode *prev;
- //后置节点
- struct listNode *next;
- //节点的值
- void *value;
- } listNode;
负载因子 = 哈希表已保存节点数量/哈希表巨细
触发 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;
- 假如 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[];
- };
跳表的相邻两层的节点数量最抱负的比例是 2:1，查找复杂度可以降低到 O(logN)。
Redis中的跳表是两步两步跳的吗？
假如接纳新增节点大概删除节点时，来调整跳表节点以维持比例2：1的方法的话，显然是会带来额外开销的。
跳表在创建节点时候，会生成范围为[0-1]的一个随机数，假如这个随机数小于 0.25（相当于概率 25%），那么层数就增长 1 层，然后继续生成下一个随机数，直到随机数的效果大于 0.25 结束，最终确定该节点的层数。因为随机数取值在[0,0.25）范围内概率不会凌驾25%，以是这也说明白增长一层的概率不会凌驾25%。这样的话，当插入一个新结点时，只需修改前后结点的指针，而其它结点的层数就不必要随之改变了，这样就降低插入操作的复杂度。
[code]// #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 |
