Redis数据结构源码探秘

迷南。 2023-02-25 13:29 17阅读 0赞

## Redis简介 ##

Redis是一个开源的、使用ANSI C语言编写、遵守BSD协议、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库，并提供多种语言的API。Redis 具有很多优势：

*  性能极高：Redis纯内存读写，读的速度是110000次/s，写的速度是81000次/s 。
 *  丰富的数据类型： Redis支持二进制案例的 String, List, Hash, Set 及 Ordered Set 数据类型操作。
 *  原子： Redis的所有操作都是原子性的，意思就是要么成功执行要么失败完全不执行。单个操作是原子性的。多个操作也支持事务，即原子性，通过MULTI和EXEC指令包起来。
 *  丰富的特性： Redis还支持 publish/subscribe, 通知, key 过期等等特性。

## Redis对象 ##

Redis 使用对象来表示数据库中的键和值， 每次当我们在 Redis 的数据库中新创建一个键值对时， 我们至少会创建两个对象， 一个对象用作键值对的键（键对象）， 另一个对象用作键值对的值（值对象），源码如下：

typedef struct redisObject { 
        // 类型
        unsigned type:4;
        // 编码
        unsigned encoding:4;
        // 指向底层实现数据结构的指针
        void *ptr;
        // ...
    } robj;

下图是一个Redis对象的结构图：  
![1][]  
  对象的 type 属性记录了对象的类型， 这个属性的值是下表列出的常量之一。

<table> 
 <thead> 
  <tr> 
   <th>类型常量</th> 
   <th>对象的名称</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>REDIS_STRING</td> 
   <td>字符串对象</td> 
  </tr> 
  <tr> 
   <td>REDIS_LIST</td> 
   <td>列表对象</td> 
  </tr> 
  <tr> 
   <td>REDIS_HASH</td> 
   <td>哈希对象</td> 
  </tr> 
  <tr> 
   <td>REDIS_SET</td> 
   <td>集合对象</td> 
  </tr> 
  <tr> 
   <td>REDIS_ZSET</td> 
   <td>有序集合对象</td> 
  </tr> 
 </tbody> 
</table>

对象的 ptr 指针指向对象的底层实现数据结构， 而这些数据结构由对象的 encoding 属性决定。  
  encoding 属性记录了对象所使用的编码， 也即是说这个对象使用了什么数据结构作为对象的底层实现， 这个属性的值是下表列出的常量之一。

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

每种类型的对象都至少使用了两种不同的编码， 下表列出了每种类型的对象可以使用的编码。

<table> 
 <thead> 
  <tr> 
   <th>类型</th> 
   <th>编码</th> 
   <th>对象</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>REDIS_STRING</td> 
   <td>REDIS_ENCODING_INT</td> 
   <td>使用整数值实现的字符串对象</td> 
  </tr> 
  <tr> 
   <td>REDIS_STRING</td> 
   <td>REDIS_ENCODING_EMBSTR</td> 
   <td>使用 embstr 编码的简单动态字符串实现的字符串对象</td> 
  </tr> 
  <tr> 
   <td>REDIS_STRING</td> 
   <td>REDIS_ENCODING_RAW</td> 
   <td>使用简单动态字符串实现的字符串对象</td> 
  </tr> 
  <tr> 
   <td>REDIS_LIST</td> 
   <td>REDIS_ENCODING_ZIPLIST</td> 
   <td>使用压缩列表实现的列表对象</td> 
  </tr> 
  <tr> 
   <td>REDIS_LIST</td> 
   <td>REDIS_ENCODING_LINKEDLIST</td> 
   <td>使用双端链表实现的列表对象</td> 
  </tr> 
  <tr> 
   <td>REDIS_HASH</td> 
   <td>REDIS_ENCODING_ZIPLIST</td> 
   <td>使用压缩列表实现的哈希对象</td> 
  </tr> 
  <tr> 
   <td>REDIS_HASH</td> 
   <td>REDIS_ENCODING_HT</td> 
   <td>使用字典实现的哈希对象</td> 
  </tr> 
  <tr> 
   <td>REDIS_SET</td> 
   <td>REDIS_ENCODING_INTSET</td> 
   <td>使用整数集合实现的集合对象</td> 
  </tr> 
  <tr> 
   <td>REDIS_SET</td> 
   <td>REDIS_ENCODING_HT</td> 
   <td>使用字典实现的集合对象</td> 
  </tr> 
  <tr> 
   <td>REDIS_ZSET</td> 
   <td>REDIS_ENCODING_ZIPLIST</td> 
   <td>使用压缩列表实现的有序集合对象</td> 
  </tr> 
  <tr> 
   <td>REDIS_ZSET</td> 
   <td>REDIS_ENCODING_SKIPLIST</td> 
   <td>使用跳跃表和字典实现的有序集合对象</td> 
  </tr> 
 </tbody> 
</table>

## 字符串 ##

Redis 没有直接使用 C 语言传统的字符串表示（以空字符结尾的字符数组）， 而是自己构建了一种名为简单动态字符串（simple dynamic string，SDS）的抽象类型， 并将 SDS 用作 Redis 的默认字符串表示，SDS源码如下：

struct sdshdr { 
        // 记录 buf 数组中已使用字节的数量, 等于 SDS 所保存字符串的长度
        int len;
        // 记录 buf 数组中未使用字节的数量
        int free;
        // 字节数组，用于保存字符串
        char buf[];
    };

![2][]  
  上图展示了一个 SDS 示例，各属性含义如下，SDS 遵循 C 字符串以空字符结尾的惯例， 保存空字符的 1 字节空间不计算在 SDS 的 len 属性里面， 并且为空字符分配额外的 1 字节空间， 以及添加空字符到字符串末尾等操作都是由 SDS 函数自动完成的， 所以这个空字符对于 SDS 的使用者来说是完全透明的。

*  free 属性的值为 0 ， 表示这个 SDS 没有分配任何未使用空间。
 *  len 属性的值为 5 ， 表示这个 SDS 保存了一个五字节长的字符串。
 *  buf 属性是一个 char 类型的数组， 数组的前五个字节分别保存了 ‘R’ 、 ‘e’ 、 ‘d’ 、 ‘i’ 、 ‘s’ 五个字符， 而最后一个字节则保存了空字符 ‘\\0’ 。

![3][]  
  上图展示了另一个 SDS 示例，这个 SDS 和之前展示的 SDS 一样， 都保存了字符串值 “Redis”，区别在于， 这个 SDS 为 buf 数组分配了五字节未使用空间， 所以它的 free 属性的值为 5。

## 列表 ##

链表提供了高效的节点重排能力， 以及顺序性的节点访问方式， 并且可以通过增删节点来灵活地调整链表的长度。作为一种常用数据结构， 链表内置在很多高级的编程语言里面， 因为 Redis 使用的 C 语言并没有内置这种数据结构， 所以 Redis 构建了自己的链表实现。  
  链表节点的源码如下：

typedef struct listNode { 
        // 前置节点
        struct listNode *prev;
        // 后置节点
        struct listNode *next;
        // 节点的值
        void *value;
    } listNode;

从示意图可以看出，多个 listNode 可以通过 prev 和 next 指针组成双端链表。  
![4][]

虽然仅仅使用多个 listNode 结构就可以组成链表， 但使用 adlist.h/list 来持有链表的话， 操作起来会更方便，链表源码如下：

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;

list 结构为链表提供了表头指针 head 、表尾指针 tail ， 以及链表长度计数器 len ， 而 dup 、 free 和 match 成员则是用于实现多态链表所需的类型特定函数。

*  dup 函数用于复制链表节点所保存的值；
 *  free 函数用于释放链表节点所保存的值；
 *  match 函数则用于对比链表节点所保存的值和另一个输入值是否相等。  
      下图是由一个 list 结构和三个 listNode 结构组成的链表：  
    ![5][]

Redis 的链表实现的特性可以总结如下：

*  双端： 链表节点带有 prev 和 next 指针， 获取某个节点的前置节点和后置节点的复杂度都是 O(1) 。
 *  无环： 表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL ， 对链表的访问以 NULL 为终点。
 *  带表头指针和表尾指针： 通过 list 结构的 head 指针和 tail 指针， 程序获取链表的表头节点和表尾节点的复杂度为 O(1) 。
 *  带链表长度计数器： 程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数， 程序获取链表中节点数量的复杂度为 O(1) 。
 *  多态： 链表节点使用 void\* 指针来保存节点值， 并且可以通过 list 结构的 dup 、 free 、 match 三个属性为节点值设置类型特定函数， 所以链表可以用于保存各种不同类型的值。

## 散列 ##

Redis 的字典使用哈希表作为底层实现， 一个哈希表里面可以有多个哈希表节点， 而每个哈希表节点就保存了字典中的一个键值对。  
  Redis 字典所使用的哈希表由 dict.h/dictht 结构定义源码如下：

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

*  table 属性是一个数组， 数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针， 每个 dictEntry 结构保存着一个键值对。
 *  size 属性记录了哈希表的大小， 也即是 table 数组的大小， 而 used 属性则记录了哈希表目前已有节点（键值对）的数量。
 *  sizemask 属性的值总是等于 size - 1 ， 这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。  
      下图展示了一个大小为 4 的空哈希表 （没有包含任何键值对）：  
    ![6][]

哈希表节点使用 dictEntry 结构表示， 每个 dictEntry 结构都保存着一个键值对，源码如下：

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

*  key 属性保存着键值对中的键， 而 v 属性则保存着键值对中的值， 其中键值对的值可以是一个指针， 或者是一个 uint64\_t 整数， 又或者是一个 int64\_t 整数。
 *  next 属性是指向另一个哈希表节点的指针， 这个指针可以将多个哈希值相同的键值对连接在一次， 以此来解决键冲突（collision）的问题。

下图展示了如何通过 next 指针， 将两个索引值相同的键 k1 和 k0 连接在一起。  
![7][]

Redis 中的hash由 dict.h/dict 结构表示，源码如下：

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

*  type 属性是一个指向 dictType 结构的指针， 每个 dictType 结构保存了一簇用于操作特定类型键值对的函数， Redis 会为用途不同的字典设置不同的类型特定函数。
 *  privdata 属性保存了需要传给那些类型特定函数的可选参数。
 *  ht 属性是一个包含两个项的数组， 数组中的每个项都是一个 dictht 哈希表， 一般情况下， 字典只使用 ht\[0\] 哈希表， ht\[1\] 哈希表只会在对 ht\[0\] 哈希表进行 rehash 时使用。
 *  rehashidx 属性记录了 rehash 目前的进度， 如果目前没有在进行 rehash ， 那么它的值为 -1 。

dictType 结构源码如下：

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;

下图展示了一个普通状态下（没有进行 rehash）的hash：  
![8][]

## 集合 ##

集合对象的编码可以是 intset 或者 hash，整数集合（intset）是集合键的底层实现之一，当一个集合只包含整数值元素， 并且这个集合的元素数量不多时， Redis 就会使用整数集合作为集合键的底层实现。  
  整数集合（intset）是 Redis 用于保存整数值的集合抽象数据结构， 它可以保存类型为 int16\_t 、 int32\_t 或者 int64\_t 的整数值， 并且保证集合中不会出现重复元素，源码如下：

typedef struct intset { 
        // 编码方式
        uint32_t encoding;
        // 集合包含的元素数量
        uint32_t length;
        // 保存元素的数组
        int8_t contents[];
    } intset;

下图展示了一个整数集合示例：  
![9][]

*  encoding 属性的值为 INTSET\_ENC\_INT16 ， 表示整数集合的底层实现为 int16\_t 类型的数组， 而集合保存的都是 int16\_t 类型的整数值。
 *  length 属性的值为 5，表示整数集合包含五个元素。
 *  contents 数组按从小到大的顺序保存着集合中的五个元素。  
      因为每个集合元素都是 int16\_t 类型的整数值， 所以 contents 数组的大小等于 sizeof(int16\_t) \* 5 = 16 \* 5 = 80 位。

## 有序集合 ##

Redis 有序集合的编码可以是 ziplist 或者 skiplist 。

### 压缩列表（ziplist） ###

压缩列表是 Redis 为了节约内存而开发的，由一系列特殊编码的连续内存块组成的顺序型数据结构，是列表键和哈希键的底层实现之一。  
  当一个列表键只包含少量列表项， 并且每个列表项要么就是小整数值， 要么就是长度比较短的字符串， 那么 Redis 就会使用压缩列表来做列表键的底层实现。  
  一个压缩列表可以包含任意多个节点（entry）， 每个节点可以保存一个字节数组或者一个整数值，下图展示了压缩列表的各个组成部分。  
![10][]

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

#### 压缩列表示例 ####

![11][]

*  zlbytes 属性的值为 0x50 （十进制 80）， 表示压缩列表的总长为 80 字节。
 *  zltail 属性的值为 0x3c （十进制 60）， 这表示如果我们有一个指向压缩列表起始地址的指针 p ， 那么只要用指针 p 加上偏移量 60 ， 就可以计算出表尾节点 entry3 的地址。
 *  zllen 属性的值为 0x3 （十进制 3）， 表示压缩列表包含三个节点。

#### 压缩列表节点示例 ####

![12][]

<table> 
 <thead> 
  <tr> 
   <th>属性</th> 
   <th>用途</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>previous_entry_length</td> 
   <td>记录压缩列表中前一个节点的长度</td> 
  </tr> 
  <tr> 
   <td>encoding</td> 
   <td>记录节点 content 属性所保存数据的类型以及长度</td> 
  </tr> 
  <tr> 
   <td>content</td> 
   <td>保存节点的值， 节点值可以是一个字节数组或者整数</td> 
  </tr> 
 </tbody> 
</table>

### 跳表（skiplist） ###

跳表是一种有序数据结构， 它通过在每个节点中维持多个指向其他节点的指针， 从而达到快速访问节点的目的。  
  跳表支持平均 O(log N) 最坏 O(N) 复杂度的节点查找， 还可以通过顺序性操作来批量处理节点。在大部分情况下， 跳表的效率可以和平衡树相媲美， 并且因为跳表的实现比平衡树要来得更为简单， 所以有不少程序都使用跳表来代替平衡树。  
  Redis 使用跳表作为有序集合键的底层实现之一： 如果一个有序集合包含的元素数量比较多， 又或者有序集合中元素的成员（member）是比较长的字符串时， Redis 就会使用跳表来作为有序集合键的底层实现。

#### 跳表的实现 ####

Redis 的跳表由 redis.h/zskiplistNode 和 redis.h/zskiplist 两个结构定义， 其中 zskiplistNode 结构用于表示跳表节点， 而 zskiplist 结构则用于保存跳表节点的相关信息， 比如节点的数量， 以及指向表头节点和表尾节点的指针， 源码如下：

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

下图展示了一个跳表示例， 位于图片最左边的是 zskiplist 结构， 该结构包含以下属性：

*  header ：指向跳表的表头节点。
 *  tail ：指向跳表的表尾节点。
 *  level ：记录目前跳表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
 *  length ：记录跳表的长度，也即是，跳表目前包含节点的数量（表头节点不计算在内）。

![13][]

#### 跳表节点的实现 ####

跳表中位于 zskiplist 结构右方的是四个 zskiplistNode 结构， 源码如下：

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

跳表节点包含以下属性：

*  level：节点中用 L1 、 L2 、 L3 等字样标记节点的各个层， L1 代表第一层， L2 代表第二层，以此类推。每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离。在上面的图片中，连线上带有数字的箭头就代表前进指针，而那个数字就是跨度。当程序从表头向表尾进行遍历时，访问会沿着层的前进指针进行。
 *  backward指针：节点中用 BW 字样标记节点的后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。
 *  score：各个节点中的 1.0 、 2.0 和 3.0 是节点所保存的分值。在跳表中，节点按各自所保存的分值从小到大排列。
 *  obj：各个节点中的 o1 、 o2 和 o3 是节点所保存的成员对象。

> 注意表头节点和其他节点的构造是一样的： 表头节点也有后退指针、分值和成员对象， 不过表头节点的这些属性都不会被用到， 所以图中省略了这些部分， 只显示了表头节点的各个层。

### ziplist编码实现ZSet ###

ziplist 编码的有序集合对象使用压缩列表作为底层实现， 每个集合元素使用两个紧挨在一起的压缩列表节点来保存， 第一个节点保存元素的成员（member）， 而第二个元素则保存元素的分值（score）。压缩列表内的集合元素按分值从小到大进行排序， 分值较小的元素被放置在靠近表头的方向， 而分值较大的元素则被放置在靠近表尾的方向。  
![14][]

### skiplist编码实现ZSet ###

skiplist 编码的有序集合对象使用 zset 结构作为底层实现， 一个 zset 结构同时包含一个字典和一个跳跃表，源码如下：

typedef struct zset { 
        // 跳表
        zskiplist *zsl;
        // hash
        dict *dict;
    } zset;

zset 结构中的 zsl 跳表按分值从小到大保存了所有集合元素， 每个跳表节点都保存了一个集合元素： 跳表节点的 object 属性保存了元素的成员， 而跳表节点的 score 属性则保存了元素的分值。 通过这个跳表， 程序可以对有序集合进行范围型操作， 比如 ZRANK 、 ZRANGE 等命令就是基于跳表 API 来实现的。  
  除此之外， zset 结构中的 dict 为`<成员, 分值>`hash， hash中的每个键值对都保存了一个集合元素：hash的键保存了元素的成员， 而hash的值则保存了元素的分值。 通过这个hash， 程序可以用 O(1) 复杂度查找给定成员的分值， ZSCORE 命令就是根据这一特性实现的， 而很多其他有序集合命令都在实现的内部用到了这一特性。  
![15][]

## ZSet的应用场景 ##

### 分布式限流 ###

![16][]

/** * 滑动时间窗口限流通用组件 * @param key 限流标识 * @param bizId 业务id * @param period 窗口大小（单位秒） * @param limit 限定访问次数 * @return 是否被限流 */
    private boolean isPeriodLimited(String key, Long bizId, int period, long limit) { 
        // 当前时间戳
        long millis = System.currentTimeMillis();
        
        // 记录值（用户访问接口的key）和分数（当前时间戳）
        zSetOperations.add(key, String.format("%d@%d", bizId, millis), millis);
        
        // 获取时间窗口内的所有记录
        Set<String> set = zSetOperations.rangeByScore(key, millis - period, millis);
        
        // 清空时间窗口之前的记录
        zSetOperations.removeRangeByScore(key, 0, millis - period);
        
        // 如果时间窗口内无访问记录，则未限流
        if (null == set) { 
            return false;
        }
        
        // 判断是否超过限定次数
        long count = set.stream().filter(e -> e.startsWith(bizId + "@")).count();
        return count > limit;
    }

### 实时排行榜 ###

### 投票计数 ###

### 优先级消息队列 ###

## 十万个为什么 ##

### 丰富的编码格式有什么好处？ ###

通过 encoding 属性来设定对象所使用的编码， 而不是为特定类型的对象关联一种固定的编码， 极大地提升了 Redis 的灵活性和效率， 因为 Redis 可以根据不同的使用场景来为一个对象设置不同的编码， 从而优化对象在某一场景下的效率。  
  举个例子， 在列表对象包含的元素比较少时， Redis 使用压缩列表作为列表对象的底层实现：因为压缩列表比双端链表更节约内存， 并且在元素数量  较少时， 在内存中以连续块方式保存的压缩列表比起双端链表可以更快被载入到缓存中；  
但是，随着列表对象包含的元素越来越多， 使用压缩列表来保存元素的优势逐渐消失时， 对象就会将底层实现从压缩列表转向功能更强、也更适合保存大量元素的双端链表上面。

### SDS有什么好处，为什么不直接用C字符串？ ###

获取一个 C 字符串的长度， 程序必须遍历整个字符串， 对遇到的每个字符进行计数， 直到遇到代表字符串结尾的空字符为止， 这个操作的复杂度为 O(N) ，和 C 字符串不同， SDS 在 len 属性中记录了本身的长度， 所以获取一个 SDS 长度的复杂度仅为 O(1)，通过使用 SDS 而不是 C 字符串， Redis 将获取字符串长度所需的复杂度从 O(N) 降低到了 O(1) ， 这确保了获取字符串长度的工作不会成为 Redis 的性能瓶颈。

### SDS使用过程中是如何扩容的？ ###

设置和更新 SDS 长度的工作是由 SDS 的 API 在执行时自动完成的， 使用 SDS 无须进行任何手动修改长度的工作。

### 为什么跳表要用压缩列表指向头指针？ ###

虽然仅靠多个跳表节点就可以组成一个跳表，但通过使用一个 zskiplist 结构来持有这些节点， 程序可以更方便地对整个跳表进行处理， 比如快速访问跳表的表头节点和表尾节点， 又或者快速地获取跳表节点的数量（也即是跳表的长度）等信息。

### 新增数据的时候，如何确定跳表节点有多少层？ ###

每次创建一个新跳跃表节点的时候， 程序都根据幂次定律 （[Power law][]，越大的数出现的概率越小） 随机生成一个介于 1 和 32 之间的值作为 level 数组的大小， 这个大小就是层的“高度”。

> 幂次定律"也叫2-8法则，由经济学家维尔弗雷多.帕累托在1906年提出，他认为：在任何一组东西中，最重要的只占其中一小部分，约20%，其余80%尽管是多数，却是次要的。幂次定律指的是事物的发展，其规模与次数成反比，规模越大，次数越少

### 如何在遍历跳表时快速得出当前元素排名？ ###

遍历过程中所有的跨度(span)之和即为当前rank。

### ZSet什么时候用ziplist编码什么时候用skiplist编码？ ###

当有序集合对象可以同时满足以下两个条件时， 对象使用 ziplist 编码，不能满足则使用 skiplist 编码。

*  有序集合保存的元素数量小于 128 个；
 *  有序集合保存的所有元素成员的长度都小于 64 字节；

> 以上两个条件的上限值是可以修改的， 具体请看配置文件中关于 zset-max-ziplist-entries 选项和 zset-max-ziplist-value 选项的说明。

### 为什么有序集合需要同时使用跳表和hash来实现？ ###

在理论上来说， 有序集合可以单独使用hash或者跳表的其中一种数据结构来实现， 但无论单独使用hash还是跳表， 在性能上对比起同时使用hash和跳表都会有所降低。  
  如果我们只使用hash来实现有序集合， 那么虽然以 O(1) 复杂度查找成员的分值这一特性会被保留， 但是， 因为hash以无序的方式来保存集合元素， 所以每次在执行范围型操作 —— 比如 ZRANK 、 ZRANGE 等命令时， 程序都需要对hash保存的所有元素进行排序， 完成这种排序需要至少 O(N log N) 时间复杂度， 以及额外的 O(N) 内存空间 （因为要创建一个数组来保存排序后的元素）。  
  如果我们只使用跳表来实现有序集合， 那么跳表执行范围型操作的所有优点都会被保留， 但因为没有了hash， 所以根据成员查找分值这一操作的复杂度将从 O(1) 上升为 O(log N) 。  
  因为以上原因， 为了让有序集合的查找和范围型操作都尽可能快地执行， Redis 选择了同时使用hash和跳表两种数据结构来实现有序集合。

## 命令实现速查 ##

<table> 
 <thead> 
  <tr> 
   <th>命令</th> 
   <th>ziplist 编码的实现方法</th> 
   <th>zset 编码的实现方法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>ZADD</td> 
   <td>调用 ziplistInsert 函数， 将成员和分值作为两个节点分别插入到压缩列表。</td> 
   <td>先调用 zslInsert 函数， 将新元素添加到跳跃表， 然后调用 dictAdd 函数， 将新元素关联到字典。</td> 
  </tr> 
  <tr> 
   <td>ZCARD</td> 
   <td>调用 ziplistLen 函数， 获得压缩列表包含节点的数量， 将这个数量除以 2 得出集合元素的数量。</td> 
   <td>访问跳跃表数据结构的 length 属性， 直接返回集合元素的数量。</td> 
  </tr> 
  <tr> 
   <td>ZCOUNT</td> 
   <td>遍历压缩列表， 统计分值在给定范围内的节点的数量。</td> 
   <td>遍历跳跃表， 统计分值在给定范围内的节点的数量。</td> 
  </tr> 
  <tr> 
   <td>ZRANGE</td> 
   <td>从表头向表尾遍历压缩列表， 返回给定索引范围内的所有元素。</td> 
   <td>从表头向表尾遍历跳跃表， 返回给定索引范围内的所有元素。</td> 
  </tr> 
  <tr> 
   <td>ZREVRANGE</td> 
   <td>从表尾向表头遍历压缩列表， 返回给定索引范围内的所有元素。</td> 
   <td>从表尾向表头遍历跳跃表， 返回给定索引范围内的所有元素。</td> 
  </tr> 
  <tr> 
   <td>ZRANK</td> 
   <td>从表头向表尾遍历压缩列表， 查找给定的成员， 沿途记录经过节点的数量， 当找到给定成员之后， 途经节点的数量就是该成员所对应元素的排名。</td> 
   <td>从表头向表尾遍历跳跃表， 查找给定的成员， 沿途记录经过节点的数量， 当找到给定成员之后， 途经节点的数量就是该成员所对应元素的排名。</td> 
  </tr> 
  <tr> 
   <td>ZREVRANK</td> 
   <td>从表尾向表头遍历压缩列表， 查找给定的成员， 沿途记录经过节点的数量， 当找到给定成员之后， 途经节点的数量就是该成员所对应元素的排名。</td> 
   <td>从表尾向表头遍历跳跃表， 查找给定的成员， 沿途记录经过节点的数量， 当找到给定成员之后， 途经节点的数量就是该成员所对应元素的排名。</td> 
  </tr> 
  <tr> 
   <td>ZREM</td> 
   <td>遍历压缩列表， 删除所有包含给定成员的节点， 以及被删除成员节点旁边的分值节点。</td> 
   <td>遍历跳跃表， 删除所有包含了给定成员的跳跃表节点。 并在字典中解除被删除元素的成员和分值的关联。</td> 
  </tr> 
  <tr> 
   <td>ZSCORE</td> 
   <td>遍历压缩列表， 查找包含了给定成员的节点， 然后取出成员节点旁边的分值节点保存的元素分值。</td> 
   <td>直接从字典中取出给定成员的分值。</td> 
  </tr> 
 </tbody> 
</table>

[1]: /images/20230209/ff762b0a18c44da39496ff55f16d5bbd.png
[2]: /images/20230209/ef1dd307109948299734a491e548478b.png
[3]: /images/20230209/6745214d44fe4feeb1e00d58eef2f8d4.png
[4]: /images/20230209/14113fbb14374790b360df08274aca53.png
[5]: /images/20230209/106c1b2ad4534562880c753305594f97.png
[6]: /images/20230209/6231c921334a4cdf94e9a1d3ebf5b512.png
[7]: /images/20230209/352dfe494e6544b9ba75c330a337ad35.png
[8]: /images/20230209/72c6f813cfbc4d25aed075636f5c03b5.png
[9]: /images/20230209/6bad9431a03243ad8ee866d446d509a5.png
[10]: /images/20230209/63dab84f29ba4558ab4dbe76df937928.png
[11]: https://img-blog.csdnimg.cn/2020071310561118.png
[12]: https://img-blog.csdnimg.cn/20200713105624939.png
[13]: https://img-blog.csdnimg.cn/20200713105637962.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTIxMDIxMDQ=,size_16,color_FFFFFF,t_70
[14]: https://img-blog.csdnimg.cn/20200713105652285.png
[15]: https://img-blog.csdnimg.cn/202007131057032.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTIxMDIxMDQ=,size_16,color_FFFFFF,t_70
[16]: https://img-blog.csdnimg.cn/20200713105713778.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTIxMDIxMDQ=,size_16,color_FFFFFF,t_70
[Power law]: https://en.wikipedia.org/wiki/Power_law