锱铢必较的Redis数据结构
前言
随着redis应用的不断拓展，它早已不再仅仅作为一个分布式缓存存在了，而是作为作为当今最火爆的内存数据库之一。这篇文章主要浅谈一下redis的内部数据结构，这才是锱铢必较！
- RedisObject
- SDS
- ZipList
- QuickList
- Skiplist
- dict
RedisObject
文章开启之前，我们先介绍一下RedisObject.正如其名，Redis中所有对象都是有这么的一个结构头。
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
* LFU data (least significant 8 bits frequency
* and most significant 16 bits access time). */
int refcount;
void *ptr;
} robj;
type 标识每个对象的类型。
encoding 标识对象实际的存储数据结构
lru 记录对象LRU
refcount 标识引用数量，为0的时候就会被销毁
ptr 指针将指向对象内容 (body) 的具体存储位置。
SDS
Redis的字符串叫做SDS，也就是Simple Dynamic String 。它的结构是一个带长度的字符数组。
struct SDS<T> {
T capacity; // 数组容量
T len; // 数组长度
byte flags; // 特殊标识位，不理睬它
byte[] content; // 数组内容
}
REDIS SDS
这个结构很像Java里面的ArrayList。都是有一个capacity 以及一个len。
上面的 SDS 结构使用了范型 T，为什么不直接用 int 呢，这是因为当字符串比较短时，len 和 capacity 可以使用 byte 和 short 来表示，Redis 为了对内存做极致的优化，不同长度的字符串使用不同的结构体来表示。
Redis存储字符串的两种方式——emb and raw
在长度特别短时，redis使用 emb 形式存储 (embeded), 也就是内嵌形式，当长度超过 44 时，使用 raw 形式存储。
为啥是44呢?
这个就要从RedisObject说起了。在之前我们讨论过RedisObject的结构，它内在有很多字段，加起来所占字节长度为16bytes。
而内存分配器 jemalloc/tcmalloc等分配内存大小的单位都是 2、4、8、16、32、64 等等，为了能容纳一个完整的 embstr 对象，jemalloc 最少会分配 32 字节的空间，如果字符串再稍微长一点，那就是 64 字节的空间。如果总体超出了 64 字节，Redis 认为它是一个大字符串，不再使用 emdstr 形式存储，而该用 raw 形式。所以SDS的结构最大只能为64 - 16 也就是 48bytes。在SDS中，capacity，len，flags 三个字段分别占用3个字节长度，C语言中，字符串又都是以\0结尾，所以content的结束符要占用一个byte，所以剩下到实际的content中字符可占用的就只有44byte了
所以，raw与embstr的结构如下所示
raw embstr
ZipList
在抠门的redis中，如果一个集合的数量很小，那么它便不会使用指定的集合类型来管理，而是使用紧凑存储形式压缩存储。
就好像定义了一个map型数据，但是如果它的数据比较少，使用map的结构就会显得很浪费，还不如用一维数组存储。在那个小数量级上，甚至一维数组还会比map更快。
ziplist就是应用于这样的一个场景。
它存在于所有的数据结构中。map,set,zset,list 只要数据量很小，都是使用的ziplist来进行存储。而超过了某个设定的阈值才会使用我们常见的数据结构来存储。
如下便是zipList的结构。
typedef struct ziplist{
/*ziplist分配的内存大小*/
uint32_t bytes;
/*达到尾部的偏移量*/
uint32_t tail_offset;
/*存储元素实体个数*/
uint16_t length;
/*存储内容实体元素*/
unsigned char* content[];
/*尾部标识*/
unsigned char end;
}ziplist;
zipList
Skiplist 跳表
在Redis中，ZSet是一个非常复杂的结构。不仅仅有Hash结构，也有ziplist结构，但是最重要的让Zset成为Zset的便是skipList了。
我们先看一下Zset的结构
struct zsl {
zslnode* header; // 跳跃列表头指针
int maxLevel; // 跳跃列表当前的最高层
map<string, zslnode*> ht; // hash 结构的所有键值对
}
struct zslnode {
string value;
double score;
zslnode*[] forwards; // 多层连接指针
zslnode* backward; // 回溯指针
}
其中zsl就是zset的结构了。zslnode是存入的一个数据结构
- 其中有一个header指针，指向skipList的头指针
- maxLevel指示当前的跳跃表最高的层
- hashtable 用于key val的检索。
其中zslnode结构中的forwards指针以及backward指针就是完全为skipList设计的。
跳表
如图。根据这个跳表的结构，zset可以实现链表的二分查找,直接从最高层开始往下找，每次都是折半了。
这样能够让查找的时间复杂度缩小到logN，能够让增删改的复杂度缩小到logN~n。
dict
dict其实就是字典结构，也可以说是我们经常使用的hash结构，不过他是又一层封装了。dict结构不仅仅用在了hash的结构上，还用在了我们刚刚说的zset结构上。其实连整个redis库的key,val都是一个全局的字典（如下）。
typedef struct redisDb {
dict *dict; /* The keyspace for this DB */
dict *expires; /* Timeout of keys with a timeout set */
dict *blocking_keys; /* Keys with clients waiting for data (BLPOP)*/
dict *ready_keys; /* Blocked keys that received a PUSH */
dict *watched_keys; /* WATCHED keys for MULTI/EXEC CAS */
int id; /* Database ID */
long long avg_ttl; /* Average TTL, just for stats */
list *defrag_later; /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;
暂时不聊redisDB的结构，先来看看dict的结构吧
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;
其中存储的结构便是dictht ht[2]了。可是为啥又两个呢。这个就不得不说dict的渐进式rehash了。
dict 结构内部包含的两个 hashtable，通常情况下只有一个 hashtable 是有值的。但是在 dict 扩容缩容时，需要分配新的 hashtable，然后进行渐进式搬迁，这时候两个 hashtable 存储的分别是旧的 hashtable 和新的 hashtable。待搬迁结束后，旧的 hashtable 被删除，新的 hashtable 取而代之。
但是对于redis的dict来说，扩容实在是太重了。redis又是单线程的，所以根本无法承受大对象的搬迁。所以在出现了渐进式rehash。
在dict需要进行rehash的时候，所有对字典的操作，包括：添加、查找、更新等等，程序除了执行指定的操作之外，还会顺带将ht[0]哈希表索引的所有键值对rehash到ht[1]。还有没有被迁移的，也会有定时任务从字典中主动迁移。
