redis 基础数据结构

1 前言

Redis的5种数据类型（String，Hash，List，Set，Sorted Set），每种数据类型都提供了最少两种内部的编码格式，而且每个数据类型内部编码方式的选择对用户是完全透明的，Redis会根据数据量自适应地选择较优化的内部编码格式。

查看某个键的内部编码格式，使用命令object encoding keyname

Reids的每个键值内部都是使用叫redisObject这个C语言结构体保存的，代码如下：

• type：表示键值的数据类型，也就是那5种基本数据类型。
• encoding：表示键值的内部编码方式，

#define OBJ_ENCODING_RAW 0        /* Raw representation */
#define OBJ_ENCODING_INT 1        /* Encoded as integer */
#define OBJ_ENCODING_HT 2         /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3     /* Encoded as zipmap */
#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
#define OBJ_ENCODING_ZIPLIST 5    /* Encoded as ziplist */
#define OBJ_ENCODING_INTSET 6     /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7   /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8     /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9  /* Encoded as linked list of ziplists */

• refcount：表示该键值被引用的数量，即一个键值可被多个键引用

---

2 string（字符串）

Redis的字符串是简单动态字符串(SDS)，是可以修改的字符串，内部结构实现上类似于 Java 的 ArrayList，采用预分配冗余空间的方式来减少内存的频繁分配。

如图所示，内部为当前字符串实际分配的空间capacity一般是要高于实际字符串长度 len。
当字符串长度小于 1M 时，扩容都是加倍现有的空间，如果超过 1M，扩容时一次只会多扩 1M 的空间。需要注意的是字符串最大长度为 512M。

<1> 内部结构：
在内存中以字节数组的形式存在，SDS的结构是带有长度信息的字节数组。

struct SDS<T> {
  T capacity; // 数组容量
  T len; // 数组长度
  byte flags; // 特殊标识位，不理睬它
  byte[] content; // 数组内容
}

capacity表示所分配数组的长度，len表示字符串的实际长度；
content保存的就是字符串内容，和c语言一样以0x\0作为结束字符，但是这个结束字符不包括在len中。

需要注意的是：
创建字符串时，也就是初次分配时，len和capacity一样长，不会多分配冗余空间。执行append之后开始冗余，因为平时的应用中大多数字符串只有只读的需求，一旦遇到append指令意味着它是需要支持修改的，于是才给分配了冗余空间。

<2> 字符串编码格式：

• int编码（保存long型的64位有符号整数，即长度小于20）
  当储存的值是64 位有符号整数类型的时候将会采用 int 编码，这时可以使用键值自增操作
  Redis启动时会预先建立10000个分别存储0~9999的redisObject变量作为共享对象，这就意味着如果 set字符串的键值在 0~10000 之间的话，则可以直接指向共享对象而不需要再建立新对象，此时键值不占空间！

• embstr编码（保存长度小于44字节的字符串）
  embedded string，表示嵌入式的String，从内存结构上来说，就是字符串 sds 结构体与其对应的 redisObject 对象分配在 同一块连续的内存空间，这就仿佛字符串 sds 嵌入在 redisObject 对象之中一样

• raw编码（保存长度大于44字节的字符串）
  与embstr不同的是，此时态字符串 sds 的内存与其依赖的 redisObject 的内存不再连续了

---

3 list（列表）

Redis 的列表相当于 Java 语言里面的 LinkedList，注意它是双向链表而不是数组。这意味着 list 的插入和删除操作非常快，时间复杂度为 O(1)，获取头结点和尾节点也很快，但是索引定位即随机定位很慢，时间复杂度为 O(n)，这点让人非常意外。常常用作消息队列。

当列表弹出了最后一个元素之后，该数据结构自动被删除，内存被回收。
用作队列，先进先出

在右边push，从左边pop，先进先出。

用作栈，先进后出

rpush books python java golang
(integer) 3
rpop books
"golang"
rpop books
"java"

<1> 内部结构
Redis中链表的内部实现不是简单的双向列表，在数据量较少的时候它的底层存储结构为一块连续内存,称之为ziplist(压缩列表)；当数据量较多的时候将会变成链表的结构，后来因为链表需要 prev 和 next 两个指针占用内存很多（64bit系统的指针是8个字节），改用 ziplist+链表的混合结构,称之为 quicklist(快速链表)。在新的版本中 Redis 链表统一使用 quicklist来存储。

ziplist 压缩列表

struct ziplist<T>{
    int32 zlbytes;          //压缩列表占用字节数
    int32 zltail_offset;    //最后一个元素距离起始位置的偏移量,用于快速定位到最后一个节点
    int16 zllength;         //元素个数
    T[] entries;            //元素内容
    int8 zlend;             //结束位 0xFF
}

如图所示：

有了ztail_offset就可以快读定位到最后一个节点，这样就可以倒序遍历了，ziplist支持双向遍历。

entry的内部实现：

struct entry{
    int<var> prevlen;           //前一个 entry 的长度
    int<var> encoding;          //元素类型编码
    optional byte[] content;    //元素内容
}

当 ziplist 倒序遍历的时候,就是通过这个pervlen定位到前一个元素位置的；
encoding 保存了 content 的编码类型；
content 则是保存的元素内容,它是optional 类型表示是这个字段是可选的.当content 是很小的整数时,他会内联到 encoding 字段的尾部。

增加元素
因为 ziplist 都是紧凑存储，没有冗余空间 (对比一下 Redis 的字符串结构)。意味着插入一个新的元素就需要调用 realloc 扩展内存。取决于内存分配器算法和当前的 ziplist 内存大小，realloc 可能会重新分配新的内存空间，并将之前的内容一次性拷贝到新的地址，也可能在原有的地址上进行扩展，这时就不需要进行旧内容的内存拷贝。
如果 ziplist 占据内存太大，重新分配内存和拷贝内存就会有很大的消耗。所以 ziplist 不适合存储大型字符串，存储的元素也不宜过多。

quicklist 快速列表

quicklist是ziplist和linkedlist的混合体，下面是quicklist和node的数据结构：

struct quicklist{
    quicklistNode* head;    //指向头结点
    quicklistNode* tail;    //指向尾节点
    long count;             //元素总数
    int nodes;              //quicklistNode节点的个数
    int compressDepth;      //压缩算法深度 LZF
    ...
}

将linkedlist按段切分，每一段使用ziplist来紧凑存储，多个ziplist之间使用双向指针串接起来。

quicklist 内部默认单个 ziplist 长度为 8k 字节，超出了这个字节数，就会新起一个 ziplist。ziplist 的长度由配置参数list-max-ziplist-size决定。

---

4 hash（字典）

Redis中的字典相当于Java中的HashMap，无序字典。其内部结构与Java的HashMap也是一致的，同样的数组+链表二维结构。在第一维Hash的数组位置发生碰撞的时候，就会将碰撞的元素使用链表串接起来。

redis的字典的值是能是字符串，不同于Java的HashMap一次性rehash（十分耗时），redis为了高性能，不堵塞服务，所以采用了渐进式rehash策略。

渐进式rehash会在rehash的同时，保留新旧两个hash结构，查询时会同时查询两个hash结构，然后在后续的定时任务中以及 hash 操作指令中，循序渐进地将旧 hash 的内容一点点迁移到新的 hash 结构中。当搬迁完成了，就会使用新的hash结构取而代之。

hashtable[1]在扩容的时候会有数据，并且优先查找hashtable[0]，查不到就再去查hashtable[1]，扩容过程中，新来的数据直接插入到hashtable[1]中

<1> dict内部结构
如上图所示，dict结构内部包含两个hashtable，通常情况下只有一个hashtable是有值的，但是在dict 扩容缩容时，需要分配新的 hashtable，然后进行渐进式搬迁，这时候两个 hashtable 存储的分别是旧的 hashtable 和新的 hashtable。待搬迁结束后，旧的 hashtable 被删除，新的 hashtable 取而代之。

所以，字典数据结构的精华就落在了hashtable结构上，hashtable的结构和Java的HashMap几乎是一样的，都是通过分桶的方式解决 hash 冲突。第一维是数组，第二维是链表。数组中存储的是第二维链表的第一个元素的指针。

struct dictEntry {
    void* key;
    void* val;
    dictEntry* next; // 链接下一个 entry
}
struct dictht {
    dictEntry** table; // 二维
    long size; // 第一维数组的长度
    long used; // hash 表中的元素个数
    ...
}

<2> 渐进式rehash
大字典的扩容是比较耗时间的，需要重新申请新的数组，然后将旧字典所有链表中的元素重新挂接到新的数组下面，这是一个O(n)级别的操作，作为单线程的Redis表示很难承受这样耗时的过程，所以redis使用渐进式rehash。

一般来说，搬迁操作埋伏在当前字典的后续指令中（来自客户端的hset/hdel指令等），但是有可能客户端闲下来了，没有后续指令来触发这个搬迁，这个时候，redis还会在定时任务中对字典进行主动搬迁。

<3> 扩容条件
正常情况下，当hash表中元素的个数在等于第一维数组的长度时，就会开始扩容，扩容的新数组是原数组大小的2倍，不过如果redis正在做 bgsave，为了减少内存页的过多分离 (Copy On Write)，Redis 尽量不去扩容 (dict_can_resize)，但是如果 hash 表已经非常满了，元素的个数已经达到了第一维数组长度的 5 倍 (dict_force_resize_ratio)，说明 hash 表已经过于拥挤了，这个时候就会强制扩容。

什么是bgsave?
bgsave在命令执行之后立即返回ok，然后redis fork出一个新子进程，原来的redis进程(父进程)继续处理客户端请求，而子进程则负责将数据保存到磁盘，然后退出。
而save保存是阻塞主进程，客户端无法连接reids，等save完成后，主进程才开始工作，客户端可以连接。

<4> 缩容条件
当hash表因为元素删除逐渐变得越来越稀疏，Redis 会对 hash 表进行缩容来减少 hash 表的第一维数组空间占用。缩容的条件是元素个数低于数组长度的 10%。

---

5 set（集合）

redis的集合相当于java里面的hashset，其内部的键值对是无序的唯一的，它的内部实现相当于一个特殊的字典 hash，字典中所有的value都是一个值NULL。

---

6 zset（有序集合）

面试时最常问的，其类似于Java的SortedSet和HashMap的结合体，一方面是一个set，保证内部value的唯一性，另一方面它可以给每个value赋予一个score，代表这个value的排序权重，内部实现【跳跃列表】。
zset 可以用来存粉丝列表，value 值是粉丝的用户 ID，score 是关注时间。我们可以对粉丝列表按关注时间进行排序。

<1> 跳跃列表
相关博客：redis-zset内部实现

zset要支持随机的插入和删除，不好用数组来表示，先看一下普通的链表结构。

需要这个链表按照score值进行排序，意味着当有新元素需要插入时，要定位到特定位置的插入点，这样才能保证链表是有序的（那么如何快速查找插入点呢？）

跳跃列表：层级制，最下面一层所有的元素都会串起来。然后每隔几个元素挑选出一个代表来，再将这几个代表使用另外一级指针串起来。然后在这些代表里再挑出二级代表，再串起来。最终就形成了金字塔结构。
跳跃列表的插入，删除，查找的复杂度都是O(logN)

举例：
redis-zset内部实现

skiplist不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是给每个节点随机出一个层数(level)。比如，一个节点随机出的层数是3，那么就把它链入到第1层到第3层这三层链表中，

基于上使得其插入性能上明显优于平衡树。

实际应用中的skiplist每个节点应该包含key和value两部分，上图中没有具体区分key和value，但是实际上列表是按照key(score)进行查询的，查询过程也是根据key在比较。

---