Jelinet

baseball,
console game,
musical&classical&rock,
LEGO,
programmer.

Redis-数据结构

Nov 30, 2021

redis

Redis数据结构与底层实现

redis数据结构底层对应

SDS

不直接使用C字符串(以”\0”结尾)，统一用简单动态字符串(simple dynamic string，SDS)标识字符串。

redis_SDS数据结构

C 字符串	SDS
获取字符串长度的复杂度为 O(N) 。	获取字符串长度的复杂度为 O(1) 。
API 是不安全的，可能会造成缓冲区溢出。	API 是安全的，不会造成缓冲区溢出。
修改字符串长度 `N` 次必然需要执行 `N` 次内存重分配。	修改字符串长度 `N` 次最多需要执行 `N` 次内存重分配。
只能保存文本数据。	可以保存文本或者二进制数据。
可以使用所有 `<string.h>` 库中的函数。	可以使用一部分 `<string.h>` 库中的函数。

链表

typedef struct list {
    // 表头节点
    listNode *head;
    // 表尾节点
    listNode *tail;
    // 链表所包含的节点数量
    unsigned long len;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr, void *key);
} list;

/** 
	* 双向链表,无环
	*/
typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;

redis_list结构

链表被广泛用于实现 Redis 的各种功能，比如列表键，发布与订阅，慢查询，监视器，等等。
双向链表，无环；
通过为链表设置不同的类型特定函数， Redis 的链表可以用于保存各种不同类型的值。

哈希表

/*
 * 哈希表
 */
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

/**
 * 字典
 */
typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

typedef struct dictType {
    // 计算哈希值的函数
    unsigned int (*hashFunction)(const void *key);
    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);
    // 复制值的函数
    void *(*valDup)(void *privdata, const void *obj);
    // 对比键的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);
    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

redis_字典结构

Redis 采用了「链式哈希」来解决哈希冲突

rehash：

为字典的 ht[1] 哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及 ht[0]当前包含的键值对数量（也即ht[0].used属性的值）：
- 如果执行的是扩展操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 \(2^n\)。
- 如果执行的是收缩操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 \(2^n\)。
将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面： rehash 指的是重新计算键的哈希值和索引值，然后将键值对放置到 ht[1] 哈希表的指定位置上。
当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后（ht[0] 变为空表），释放 ht[0] ，将 ht[1] 设置为 ht[0] ，并在 ht[1] 新创建一个空白哈希表，为下一次 rehash 做准备。

rehash条件：

服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 1 ；
服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 5 ；
当哈希表的负载因子小于 0.1 时，程序自动开始对哈希表执行收缩操作。

负载因子公式：

# 负载因子 = 哈希表已保存节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size
# 对于一个大小为 `512` ， 包含 `256` 个键值对的哈希表来说， 这个哈希表的负载因子为：`load_factor = 256 / 512 = 0.5`

渐进式 rehash：也就是将数据的迁移的工作不再是一次性迁移完成，而是分多次迁移。

步骤：

给ht[1] 分配空间；
rehashidx=0,rehash开始；
在 rehash 进行期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis 除会执行对应的操作之外，还会将rehashidx索引上所有键值对迁移到ht[1] 上；新添加到字典的键值对一律会被保存到 ht[1] 里面，而 ht[0] 则不再进行任何添加操作：这一措施保证了 ht[0] 包含的键值对数量会只减不增；
rehash结束，rehashidx++；
随着处理客户端发起的哈希表操作请求数量越多，最终在某个时间点，会把ht[0]的所有 key-value 迁移到ht[1]，从而完成 rehash 操作，rehashidx=-1；

跳跃表

两个地方用到：有序集合键；集群节点中，内部数据结构

实现：一个跳跃表

typedef struct zskiplist {
  // 表头节点和表尾节点
  structz skiplistNode *header, *tail;
  // 表中节点的数量
  unsigned long length;
  // 表中层数最大的节点的层数
  int level;
} zskiplist;

typedef struct zskiplistNode {
  // 层
  struct zskiplistLevel {
      // 前进指针
      struct zskiplistNode *forward;
      // 跨度
      unsigned int span;
  } level[];
  // 后退指针
  struct zskiplistNode *backward;
  // 分值
  double score;
  // 成员对象
  robj *obj;
} zskiplistNode;

zskiplist包含以下属性：head,tail,level(层数最大的节点的层数),length；
zskiplistNode包含以下属性：level(包含前进指针，跨度；1-32随机数，符合幂次定律),backward(后退指针，BW),score,obj;
跨度：计算排位（rank），查找某个节点的过程中，访问过的节点跨度累加；
成员对象obj是一个指针，指向字符串对象，字符串依旧是一个SDS；
obj是唯一的，score相同的，按照obj在字典顺序中大小，小的靠近表头；

整数集合

一个集合包含整数元素，个数不多；
实现
```
typedef struct intset {
  // 编码方式
  uint32_t encoding;
  // 集合包含的元素数量
  uint32_t length;
  // 保存元素的数组
  int8_t contents[];
} intset;
```
1. int16,int32,int64的整数值；有序,无重复元素；
2. contents底层是有序的数据；contents并不保存任何int8_t类型的值，真正类型取决于encoding属性的值;
3. 添加新元素的时间复杂度为O(N)
4. 仅支持升级，不支持降级；

压缩列表

列表键和哈希键的底层实现之一，保存比较小的整数、长度比较短的字符串；

结构

属性	类型	长度	用途
zlbytes	uint32_t	4 字节	记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配，或者计算 zlend 的位置时使用。
zltail	uint32_t	4 字节	记录压缩列表表尾节点距离压缩列表的起始地址有多少字节：通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址。
zllen	uint16_	2 字节	记录了压缩列表包含的节点数量：当这个属性的值小于 UINT16_MAX （65535）时，这个属性的值就是压缩列表包含节点的数量；当这个值等于 UINT16_MAX 时，节点的真实数量需要遍历整个压缩列表才能计算得出。
entryX	列表节点	不定	压缩列表包含的各个节点，节点的长度由节点保存的内容决定。
zlend	uint8_t	1 字节	特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。

对象

字符串对象、列表对象、哈希对象、集合对象和有序集合对象；
引用计数法实现的内存回收和对象共享机制；
创建一个键值对的时候，至少会创造两个对象，键总是一个字符串对象；

结构

typedef struct redisObject {
  // 类型 常量：REDIS_STRING,REDIS_LIST,REDIS_HASH,REDIS_SET,REDIS_ZSET
  unsigned type:4;
  // 编码
  unsigned encoding:4;
  // 指向底层实现数据结构的指针
  void *ptr;
  // ...
} robj;

编码常量	编码所对应的底层数据结构
REDIS_ENCODING_INT	long 类型的整数
REDIS_ENCODING_EMBSTR	embstr 编码的简单动态字符串
REDIS_ENCODING_RAW	简单动态字符串
REDIS_ENCODING_HT	字典
REDIS_ENCODING_LINKEDLIST	双端链表
REDIS_ENCODING_ZIPLIST	压缩列表
REDIS_ENCODING_INTSET	整数集合
REDIS_ENCODING_SKIPLIST	跳跃表和字典

对象会在不同场景使用不同的编码；
1. 字符串对象编码：int,raw,embstr;embstr 是字符串长度小于32时使用的；
2. 列表对象编码：ziplist,linkedlist;ziplist条件：元素长度<=64，元素数量<=512；上限可在配置文件中修改list-max-ziplist-value、list-max-ziplist-entries；
3. 哈希对象编码：ziplist,hashtable;
  
  ziplist条件：键和值长度都<=64，键值对<=512；上限可在配置文件中修改hash-max-ziplist-value、hash-max-ziplist-entries；
4. 集合对象编码：intset,hashtable;hashtable 保存在键中，值都为null；intset条件：所有元素都是整数型，元素数量不超过512个，数量上线可set-max-intset-entries；
5. 有序集合编码：ziplist,skiplist;ziplist中按照score值顺序保存，先成员，后score；

quicklist

在 Redis 3.0 之前，List 对象的底层数据结构是双向链表或者压缩列表。然后在 Redis 3.2 的时候，List 对象的底层改由 quicklist 数据结构实现。

其实 quicklist 就是「双向链表 + 压缩列表」组合，因为一个 quicklist 就是一个链表，而链表中的每个元素又是一个压缩列表。通过控制每个链表节点中的压缩列表的大小或者元素个数，来规避连锁更新的问题。因为压缩列表元素越少或越小，连锁更新带来的影响就越小，从而提供了更好的访问性能。

typedef struct quicklist {
    //quicklist的链表头
    quicklistNode *head;
    //quicklist的链表尾
    quicklistNode *tail; 
    //所有压缩列表中的总元素个数
    unsigned long count;
    //quicklistNodes的个数
    unsigned long len;       
    ...
} quicklist;

typedef struct quicklistNode {
    //前一个quicklistNode
    struct quicklistNode *prev;     //前一个quicklistNode
    //下一个quicklistNode
    struct quicklistNode *next;     //后一个quicklistNode
    //quicklistNode指向的压缩列表
    unsigned int count : 16;
  	unsigned char *entry;
    ....
} quicklistNode;

listpack

一个字符串序列化的list，每个元素是一个string或者intger

 /* Each entry in the listpack is either a string or an integer. */
typedef struct {
    /* When string is used, it is provided with the length (slen). */
    unsigned char *sval;
    uint32_t slen;
    /* When integer is used, 'sval' is NULL, and lval holds the value. */
    long long lval;
} listpackEntry;

Redis 的 Github，在最新 6.2 发行版本中，Redis Hash 对象、Set 对象的底层数据结构的压缩列表还未被替换成 listpack，而 Redis 的最新代码（还未发布版本）已经将所有用到压缩列表底层数据结构的 Redis 对象替换成 listpack 数据结构来实现，估计不久将来，Redis 就会发布一个将压缩列表为 listpack 的发行版本。

listpack 结构设计

<tot-bytes> <num-elements> <element-1> ... <element-N> <listpack-end-byte>

listpack 头包含两个属性，分别记录了 listpack 总字节数和元素数量，然后 listpack 末尾也有个结尾标识。

元素

<encoding-type><element-data><element-tot-len>
|                                            |
+--------------------------------------------+
            (This is an element)