[大数据]Redis——底层数据结构原理

摘要

Redis 发展到现在已经有 9 种数据类型了，其中最基础、最常用的数据类型有 5 种，它们分别是：字符串类型、列表类型、哈希表类型、集合类型、有序集合类型，而在这 5 种数据类型中最常用的是字符串类型，所以本文我们先从字符串的使用开始说起。

一、String类型

1.1 int类型

Redis中规定假如存储的是整数型值，比如set num 123这样的类型，就会使用int的存储方式进行存储，在redisObject的ptr属性中就会保存该值。

1.2 SDS类型

假如存储的字符串是一个字符串值并且长度大于32个字节就会使用SDS（simple dynamic string）方式进行存储，并且encoding设置为raw；若是字符串长度小于等于32个字节就会将encoding改为embstr来保存字符串。

Redis使用SDS作为存储字符串的类型肯定是有自己的优势，SDS与c语言的字符串相比，SDS对c语言的字符串做了自己的设计和优化，具体优势有以下几点：

• c语言中的字符串并不会记录自己的长度，因此每次获取字符串的长度都会遍历得到，时间的复杂度是O(n)，而Redis中获取字符串只要读取len的值就可，时间复杂度变为O(1)。
• c语言中两个字符串拼接，若是没有分配足够长度的内存空间就会出现缓冲区溢出的情况；而SDS会先根据len属性判断空间是否满足要求，若是空间不够，就会进行相应的空间扩展，所以不会出现缓冲区溢出的情况。
• SDS还提供空间预分配和惰性空间释放两种策略。在为字符串分配空间时，分配的空间比实际要多，这样就能减少连续的执行字符串增长带来内存重新分配的次数。

????????当字符串被缩短的时候，SDS也不会立即回收不适用的空间，而是通过free属性将不使用的空间记录下来，等后面使用的时候再释放。

????????具体的空间预分配原则是：当修改字符串后的长度len小于1MB，就会预分配和len一样长度的空间，即len=free；若是len大于1MB，free分配的空间大小就为1MB。

• SDS是二进制安全的，除了可以储存字符串以外还可以储存二进制文件（如图片、音频，视频等文件的二进制数据）；而c语言中的字符串是以空字符串作为结束符，一些图片中含有结束符，因此不是二进制安全的。
• redis同时写重写了大量的与sds类型相关的方法，有以下4个优点：降低获取字符串长度的时间复杂度到O(1)、减少了修改字符串时的内存重分配次数、兼容c字符串的同时，提高了一些字符串工具方法的效率、二进制安全（数据写入的格式和读取的格式一致）。

1.3 embstr类型

若是字符串长度小于等于32个字节就会将encoding改为embstr来保存字符串。

1.4 字符串类型的应用场景

字符串类型的使用场景有很多，但从功能的角度来区分，大致可分为以下两种：

• 字符串存储和操作；
• 整数类型和浮点类型的存储和计算。

1.4.1 页面数据缓存

我们知道，一个系统最宝贵的资源就是数据库资源，随着公司业务的发展壮大，数据库的存储量也会越来越大，并且要处理的请求也越来越多，当数据量和并发量到达一定级别之后，数据库就变成了拖慢系统运行的“罪魁祸首”，为了避免这种情况的发生，我们可以把查询结果放入缓存(Redis)中，让下次同样的查询直接去缓存系统取结果，而非查询数据库，这样既减少了数据库的压力，同时也提高了程序的运行速度。介于以上这个思路，我们可以把文章详情页的数据放入缓存系统。具体的做法是先将文章详情页序列化为字符串存入缓存，再从缓存中读取到字符串，反序列化成对象，然后再赋值到页面进行显示 (当然也可以用哈希类型进行存储，这会在下一篇文章中讲到)，这样我们就实现了文章详情页的缓存功能，架构流程对比图如下所示。

1.4.2 数字计算与统计

Redis 可以用来存储整数和浮点类型的数据，并且可以通过命令直接累加并存储整数信息，这样就省去了每次先要取数据、转换数据、拼加数据、再存入数据的麻烦，只需要使用一个命令就可以完成此流程，这样我们就可以使用此功能来实现访问量的统计，当有人访问时访问量 +1 就可以了。

1.4.3 共享 Session 信息

通常我们在开发后台管理系统时，会使用 Session 来保存用户的会话(登录)状态，这些 Session 信息会被保存在服务器端，但这只适用于单系统应用，如果是分布式系统此模式将不再适用。例如用户一的 Session 信息被存储在服务器一，但第二次访问时用户一被分配到服务器二，这个时候服务器并没有用户一的 Session 信息，就会出现需要重复登录的问题。分布式系统每次会把请求随机分配到不同的服务器，因此我们需要借助缓存系统对这些 Session 信息进行统一的存储和管理，这样无论请求发送到那台服务器，服务器都会去统一的缓存系统获取相关的 Session 信息，这样就解决了分布式系统下 Session 存储的问题。

分布式系统使用同一的缓存系统存储 Session 流程图：

1.5 字符串源码分析

Redis 3.2 之前 SDS 源码如下：

struct sds{
    int len; // 已占用的字节数
    int free; // 剩余可以字节数
    char buf[]; // 存储字符串的数据空间
}

Redis 3.2 优化了 SDS 的存储结构

typedef char *sds;

struct __attribute__ ((__packed__)) sdshdr5 { // 对应的字符串长度小于 1<<5
    unsigned char flags;
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 { // 对应的字符串长度小于 1<<8
    uint8_t len; /* 已使用长度，1 字节存储 */
    uint8_t alloc; /* 总长度 */
    unsigned char flags; 
    char buf[]; // 真正存储字符串的数据空间
};
struct __attribute__ ((__packed__)) sdshdr16 { // 对应的字符串长度小于 1<<16
    uint16_t len; /* 已使用长度，2 字节存储 */
    uint16_t alloc; 
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 { // 对应的字符串长度小于 1<<32
    uint32_t len; /* 已使用长度，4 字节存储 */
    uint32_t alloc; 
    unsigned char flags; 
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 { // 对应的字符串长度小于 1<<64
    uint64_t len; /* 已使用长度，8 字节存储 */
    uint64_t alloc; 
    unsigned char flags; 
    char buf[];
};

为什么是 44 字节？

在 Redis 中，如果 SDS 的存储值大于 64 字节时，Redis 的内存分配器会认为此对象为大字符串，并使用 raw 类型来存储，当数据小于 64 字节时(字符串类型)，会使用 embstr 类型存储。既然内存分配器的判断标准是 64 字节，那为什么 embstr 类型和 raw 类型的存储判断值是 44 字节？

这是因为 Redis 在存储对象时，会创建此对象的关联信息，redisObject 对象头和 SDS 自身属性信息，这些信息都会占用一定的存储空间，因此长度判断标准就从 64 字节变成了 44 字节。

在 Redis 中，所有的对象都会包含 redisObject 对象头。我们先来看 redisObject 对象的源码：

typedef struct redisObject {
    unsigned type:4; // 4 bit
    unsigned encoding:4; // 4 bit
    unsigned lru:LRU_BITS; // 3 个字节
    int refcount; // 4 个字节
    void *ptr; // 8 个字节
} robj;

它的参数说明如下：

type：对象的数据类型，例如：string、list、hash 等，占用 4 bits 也就是半个字符的大小；

encoding：对象数据编码，占用 4 bits；

lru：记录对象的 LRU(Least Recently Used 的缩写，即最近最少使用)信息，内存回收时会用到此属性，占用 24 bits(3 字节)；

refcount：引用计数器，占用 32 bits(4 字节)；

*ptr：对象指针用于指向具体的内容，占用 64 bits(8 字节)。

redisObject 总共占用 0.5 bytes + 0.5 bytes + 3 bytes + 4 bytes + 8 bytes = 16 bytes(字节)。

了解了 redisObject 之后，我们再来看 SDS 自身的数据结构，从 SDS 的源码可以看出，SDS 的存储类型一共有 5 种：SDSTYPE5、SDSTYPE8、SDSTYPE16、SDSTYPE32、SDSTYPE64，在这些类型中最小的存储类型为 SDSTYPE５，但 SDSTYPE５ 类型会默认转成 SDSTYPE8，以下源码可以证明，如下图所示：

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; // 1 byte
    uint8_t alloc; // 1 byte
    unsigned char flags; // 1 byte
    char buf[];
};

可以看出除了内容数组(buf)之外，其他三个属性分别占用了 1 个字节，最终分隔字符等于 64 字节，减去 redisObject 的 16 个字节，再减去 SDS 自身的 3 个字节，再减去结束符 \0 结束符占用 1 个字节，最终的结果是 44 字节(64-16-3-1=44)，内存占用如下图所示：

二、Hash类型

redis的hash对象有两种编码（底层实现）方式，字典编码（hashtable）和压缩列表编码(ziplist)。在使用字典编码的时候程序就是将hash表的key存为字典的键，hash的value作为字典的值，字典的键值都是用的是字符串类型。在哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节和哈希对象保存的键值对数量小于 512 个使用的是ziplist，不能满足这个的使用的是hashtable（字典编码）

• hash对象有两种底层实现方式，hashtable（字典） 和 ziplist（压缩链表）。
• 压缩链表由于是连续空间在刚开始数据量小的时候性能是显著的，但是在数据量大的时候就会出现扩容慢的问题。
• 字典通过双hahstable的方式，再加上渐进式hash的方式解决了压缩列表的扩容的问题。
• redis 高性能数据结构我们可以看到他在很对细节的把握很多，如不同的数字大小选用不同的字段类型，不同的存储方式采用不同的。
• 应用场景：哈希表相对于String类型存储信息更加直观，更加方便，经常会用来做用户数据的管理，存储用户的信息。hash也可以用作高并发场景下使用Redis生成唯一的id。

2.1 哈希冲突

字典类型的存储流程是先将键值进行 Hash 计算，得到存储键值对应的数组索引，再根据数组索引进行数据存储，但在小概率事件下可能会出完全不相同的键值进行 Hash 计算之后，得到相同的 Hash 值，这种情况我们称之为哈希冲突。

哈希冲突一般通过链表的形式解决，相同的哈希值会对应一个链表结构，每次有哈希冲突时，就把新的元素插入到链表的尾部，请参考上面数据结构的那张图。

键值查询的流程如下：

• 通过算法 (Hash，计算和取余等) 操作获得数组的索引值，根据索引值找到对应的元素；
• 判断元素和查找的键值是否相等，相等则成功返回数据，否则需要查看 next 指针是否还有对应其他元素，如果没有，则返回 null，如果有的话，重复此步骤。

2.2 渐进式rehash

Redis 为了保证应用的高性能运行，提供了一个重要的机制——渐进式 rehash。 渐进式 rehash 是用来保证字典缩放效率的，也就是说在字典进行扩容或者缩容是会采取渐进式 rehash 的机制。当插入的数据大于的数组时候这个时候需要rehash 。当插入的数据的冲突的概率越来越大。在扩容和收缩的时候，如果哈希字典中有很多元素，一次性将这些键全部rehash到ht[1]的话，可能会导致服务器在一段时间内停止服务。所以，采用渐进式rehash的方式，在进行渐进式 rehash 时，会同时保留两个 hash 结构，新键值对加入时会直接插入到新的 hash 结构中，并会把旧 hash 结构中的元素一点一点的移动到新的 hash 结构中，当移除完最后一个元素时，清空旧 hash 结构。详细步骤如：

• 扩容或者缩容时把字典中的字段 rehashidx 标识为 0；
• 在执行定时任务或者执行客户端的 hset、hdel 等操作指令时，判断是否需要触发 rehash 操作（通过 rehashidx 标识判断），如果需要触发 rehash 操作，也就是调用 dictRehash 函数，dictRehash 函数会把 ht[0] 中的元素依次添加到新的 Hash 表 ht[1] 中；
• rehash 操作完成之后，清空 Hash 表 ht[0]，然后对调 ht[1] 和 ht[0] 的值，把新的数据表 ht[1] 更改为 ht[0]，然后把字典中的 rehashidx 标识为 -1，表示不需要执行 rehash 操作。

渐进式rehash采用的是一种分而治之的方式，将rehash的操作分摊在每一个的访问中，避免集中式rehash而带来的庞大计算量。需要注意的是在渐进式rehash的过程，如果有增删改查操作时，如果index大于rehashindex ,访问ht[0]，否则访问ht[1]。

在rehash的时候有两个数组。 当新的表时候的满了的时候不会造成新的hash，因为在rehashindex=-1(表示的没有的扩容)当大于的是的-1的时候表示的在扩容。所以直接返回不会进行的扩容。只有在一种的情况的时候回造成 san遍历的时候 数据有重复。scan的过程中的有两次缩容的情况。在redis的客户端可以进行的过滤。

2.3 缩容

当字典的使用容量不足总空间的 10% 时就会触发缩容，Redis 在进行缩容时也会把 rehashindex 设置为 0，表示之后需要进行 rehash 操作。

2.4 hash使用场景

哈希字典的典型使用场景如下：

• 商品购物车，购物车非常适合用哈希字典表示，使用人员唯一编号作为字典的 key，value 值可以存储商品的 id 和数量等信息；
• 存储用户的属性信息，使用人员唯一编号作为字典的 key，value 值为属性字段和对应的值；
• 存储文章详情页信息等。

2.5 hash的源码分析

当元素数量等于数组长度时就会进行扩容操作，源码在 dict.c 文件中，从以上源码可以看出，如果需要扩容则会申请一个新的内存地址赋值给 ht[1]，并把字典的 rehashindex 设置为 0，表示之后需要进行 rehash 操作。核心代码如下：

int dictExpand(dict *d, unsigned long size)
{
    /* 需要的容量小于当前容量，则不需要扩容 */
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;
    dictht n; 
    unsigned long realsize = _dictNextPower(size); // 重新计算扩容后的值
    /* 计算新的扩容大小等于当前容量，不需要扩容 */
    if (realsize == d->ht[0].size) return DICT_ERR;
    /* 分配一个新的哈希表，并将所有指针初始化为NULL */
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;
    if (d->ht[0].table == NULL) {
        // 第一次初始化
        d->ht[0] = n;
        return DICT_OK;
    }
    d->ht[1] = n; // 把增量输入放入新 ht[1] 中
    d->rehashidx = 0; // 非默认值 -1，表示需要进行 rehash
    return DICT_OK;
}

?2.6 ZipList（压缩列表）

压缩列表（ziplist）是一组连续内存块组成的顺序的数据结构，压缩列表能够节省空间，压缩列表中使用多个节点来存储数据。压缩列表是列表键和哈希键底层实现的原理之一，压缩列表并不是以某种压缩算法进行压缩存储数据，而是它表示一组连续的内存空间的使用，节省空间，压缩列表的内存结构图如下：

redis 的压缩列表是一块连续的内存空间，元素之间紧挨着存储，没有任何冗余空间

• 压缩列表是支持双向遍历，所以才会有zltail_offset这个字段的，可以进行快速定位到最后一个元素。然后倒序查找(O(1))。
• prevlen 表示的是前一个字段的长度，有人就有疑问了，为什么是前一个entry的长度，为什么不是自己的呢，其实他还有一个作用是在压缩列表倒叙遍历的时候，需要通过这个字段来快速定位到下一个元素的位置，由于他是一个连续的存储空间，已经知道当前元素的位置+这个空间地址就可以确定写一个entry的位置。为什么会这样呢？因为entry的大小是不一样的。如果是一样的话就可以根据下表进行行为（个人理解，有错误还请指出），且prevlen 是一个变长的整数，redis的常规操作，将不同长度使用不同的数据类型。节省内存。
• encoding的意思是元素的编码类型，有了这个字段就可以决定元素内容的设定，内存大小的分配。防止内存分配浪费的一种方式。

三、list类型

Redis中的列表在3.2之前的版本是使用ziplist和linkedlist进行实现的。在3.2之后的版本就是引入了quicklist。数据量少的时候，使用的ziplist数据结构，当数据量较大时候，采用linklist(quicklist)：两个额外的指针 prev 和 next。

3.1? ZipList（压缩列表）

压缩列表（ziplist）是一组连续内存块组成的顺序的数据结构，压缩列表能够节省空间，压缩列表中使用多个节点来存储数据。压缩列表是列表键和哈希键底层实现的原理之一，压缩列表并不是以某种压缩算法进行压缩存储数据，而是它表示一组连续的内存空间的使用，节省空间，压缩列表的内存结构图如下：

?redis 的压缩列表是一块连续的内存空间，元素之间紧挨着存储，没有任何冗余空间

• 压缩列表是支持双向遍历，所以才会有zltail_offset这个字段的，可以进行快速定位到最后一个元素。然后倒序查找(O(1))。
• prevlen 表示的是前一个字段的长度，有人就有疑问了，为什么是前一个entry的长度，为什么不是自己的呢，其实他还有一个作用是在压缩列表倒叙遍历的时候，需要通过这个字段来快速定位到下一个元素的位置，由于他是一个连续的存储空间，已经知道当前元素的位置+这个空间地址就可以确定写一个entry的位置。为什么会这样呢？因为entry的大小是不一样的。如果是一样的话就可以根据下表进行行为（个人理解，有错误还请指出），且prevlen 是一个变长的整数，redis的常规操作，将不同长度使用不同的数据类型。节省内存。
• encoding的意思是元素的编码类型，有了这个字段就可以决定元素内容的设定，内存大小的分配。防止内存分配浪费的一种方式。

3.2 quicklist（linklist）（快速列表）

linkedlist是一个双向链表，他和普通的链表一样都是由指向前后节点的指针。插入、修改、更新的时间复杂度尾O(1)，但是查询的时间复杂度确实O(n)。linkedlist和quicklist的底层实现是采用链表进行实现，在c语言中并没有内置的链表这种数据结构，Redis实现了自己的链表结构。

Redis中链表的特性：

1. 每一个节点都有指向前一个节点和后一个节点的指针。
2. 头节点和尾节点的prev和next指针指向为null，所以链表是无环的。
3. 链表有自己长度的信息，获取长度的时间复杂度为O(1)。

3.3 quicklist 的实现源码

typedef struct quicklist { // src/quicklist.h
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* ziplist 的个数 */
    unsigned long len;          /* quicklist 的节点数 */
    unsigned int compress : 16; /* LZF 压缩算法深度 */
    //...
} quicklist;

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;           /* 对应的 ziplist */
    unsigned int sz;             /* ziplist 字节数 */
    unsigned int count : 16;     /* ziplist 个数 */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* 该节点先前是否被压缩 */
    unsigned int attempted_compress : 1; /* 节点太小无法压缩 */
    //...
} quicklistNode;

typedef struct quicklistLZF {
    unsigned int sz; 
    char compressed[];
} quicklistLZF;

quicklist 添加操作对应函数是 quicklistPush，源码如下：

void quicklistPush(quicklist *quicklist, void *value, const size_t sz,
                   int where) {
    if (where == QUICKLIST_HEAD) {
        // 在列表头部添加元素
        quicklistPushHead(quicklist, value, sz);
    } else if (where == QUICKLIST_TAIL) {
        // 在列表尾部添加元素
        quicklistPushTail(quicklist, value, sz);
    }
}


int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
    quicklistNode *orig_head = quicklist->head;
    if (likely(
            _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
        // 在头部节点插入元素
        quicklist->head->zl =
            ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);
        quicklistNodeUpdateSz(quicklist->head);
    } else {
        // 头部节点不能继续插入，需要新建 quicklistNode、ziplist 进行插入
        quicklistNode *node = quicklistCreateNode();
        node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
        quicklistNodeUpdateSz(node);
        // 将新建的 quicklistNode 插入到 quicklist 结构中
        _quicklistInsertNodeBefore(quicklist, quicklist->head, node);
    }
    quicklist->count++;
    quicklist->head->count++;
    return (orig_head != quicklist->head);
}

quicklistPushHead 函数的执行流程，先判断 quicklist 的 head 节点是否可以插入数据，如果可以插入则使用 ziplist 的接口进行插入，否则就新建 quicklistNode 节点进行插入。函数的入参是待插入的 quicklist，还有需要插入的值 value 以及他的大小 sz。函数的返回值为 int，0 表示没有新建 head，1 表示新建了 head。 quicklistPushHead 执行流程，如下图所示：

quicklist 元素删除分为两种情况：单一元素删除和区间元素删除，它们都位于 src/quicklist.c 文件中。

1、单一元素删除

单一元素的删除函数是 quicklistDelEntry，源码如下：

void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry) {
    quicklistNode *prev = entry->node->prev;
    quicklistNode *next = entry->node->next;
    // 删除指定位置的元素
    int deleted_node = quicklistDelIndex((quicklist *)entry->quicklist,
                                         entry->node, &entry->zi);
    //...
}

可以看出 quicklistDelEntry 函数的底层，依赖 quicklistDelIndex 函数进行元素删除。

2、区间元素删除

区间元素删除的函数是 quicklistDelRange，源码如下：

// start 表示开始删除的下标，count 表示要删除的个数
int quicklistDelRange(quicklist *quicklist, const long start,
                      const long count) {
    if (count <= 0)
        return 0;
    unsigned long extent = count; 
    if (start >= 0 && extent > (quicklist->count - start)) {
        // 删除的元素个数大于已有元素
        extent = quicklist->count - start;
    } else if (start < 0 && extent > (unsigned long)(-start)) {
        // 删除指定的元素个数
        extent = -start; /* c.f. LREM -29 29; just delete until end. */
    }
    //...
    // extent 为剩余需要删除的元素个数，
    while (extent) {
        // 保存下个 quicklistNode，因为本节点可能会被删除
        quicklistNode *next = node->next;
        unsigned long del;
        int delete_entire_node = 0;
        if (entry.offset == 0 && extent >= node->count) {
            // 删除整个 quicklistNode
            delete_entire_node = 1;
            del = node->count;
        } else if (entry.offset >= 0 && extent >= node->count) {
           // 删除本节点的所有元素
            del = node->count - entry.offset;
        } else if (entry.offset < 0) {
            // entry.offset<0 表示从后向前，相反则表示从前向后剩余的元素个数
            del = -entry.offset;
            if (del > extent)
                del = extent;
        } else {
            // 删除本节点部分元素
            del = extent;
        }
        D("[%ld]: asking to del: %ld because offset: %d; (ENTIRE NODE: %d), "
          "node count: %u",
          extent, del, entry.offset, delete_entire_node, node->count);
        if (delete_entire_node) {
            __quicklistDelNode(quicklist, node);
        } else {
            quicklistDecompressNodeForUse(node);
            node->zl = ziplistDeleteRange(node->zl, entry.offset, del);
            quicklistNodeUpdateSz(node);
            node->count -= del;
            quicklist->count -= del;
            quicklistDeleteIfEmpty(quicklist, node);
            if (node)
                quicklistRecompressOnly(quicklist, node);
        }
        // 剩余待删除元素的个数
        extent -= del;
        // 下个 quicklistNode
        node = next;
        // 从下个 quicklistNode 起始位置开始删除
        entry.offset = 0;
    }
    return 1;
}

从上面代码可以看出，quicklist 在区间删除时，会先找到 start 所在的 quicklistNode，计算删除的元素是否小于要删除的 count，如果不满足删除的个数，则会移动至下一个 quicklistNode 继续删除，依次循环直到删除完成为止。

quicklistDelRange 函数的返回值为 int 类型，当返回 1 时表示成功的删除了指定区间的元素，返回 0 时表示没有删除任何元素。

3.4 linklist的应用场景

列表的典型使用场景有以下两个：

• 消息队列：列表类型可以使用 rpush 实现先进先出的功能，同时又可以使用 lpop 轻松的弹出（查询并删除）第一个元素，所以列表类型可以用来实现消息队列；
• 文章列表：对于博客站点来说，当用户和文章都越来越多时，为了加快程序的响应速度，我们可以把用户自己的文章存入到 List 中，因为 List 是有序的结构，所以这样又可以完美的实现分页功能，从而加速了程序的响应速度。

四、set (集合)

Redis 的集合相当于 Java 语言里面的 HashSet，它内部的键值对是无序的唯一的。它的内部实现相当于一个特殊的字典，字典中所有的 value 都是一个值 NULL。当集合中最后一个元素移除之后，数据结构自动删除，内存被回收。 set 结构可以用来存储活动中奖的用户 ID，因为有去重功能，可以保证同一个用户不会中奖两次。Set的底层实现是hahstabale和intset。

4.1 intset类型

在整数集合中，有三个属性值encoding、length、contents[]，分别表示编码方式、整数集合的长度、以及元素内容，length就是记录contents里面的大小。

在整数集合新增元素的时候，若是超出了原集合的长度大小，就会对集合进行升级，具体的升级过程如下：

• ??? 首先扩展底层数组的大小，并且数组的类型为新元素的类型。
• ??? 然后将原来的数组中的元素转为新元素的类型，并放到扩展后数组对应的位置。
• ??? 整数集合升级后就不会再降级，编码会一直保持升级后的状态。

4.2 set源码解析

/* 
 * 添加元素到集合
 * 如果当前值已经存在，则返回 0 不作任何处理，否则就添加该元素，并返回 1。
 */
int setTypeAdd(robj *subject, sds value) {
    long long llval;
    if (subject->encoding == OBJ_ENCODING_HT) { // 字典类型
        dict *ht = subject->ptr;
        dictEntry *de = dictAddRaw(ht,value,NULL);
        if (de) {
            // 把 value 作为字典到 key，将 Null 作为字典到 value，将元素存入到字典
            dictSetKey(ht,de,sdsdup(value));
            dictSetVal(ht,de,NULL);
            return 1;
        }
    } else if (subject->encoding == OBJ_ENCODING_INTSET) { // inset 数据类型
        if (isSdsRepresentableAsLongLong(value,&llval) == C_OK) {
            uint8_t success = 0;
            subject->ptr = intsetAdd(subject->ptr,llval,&success);
            if (success) {
                // 超过 inset 的最大存储数量，则使用字典类型存储
                if (intsetLen(subject->ptr) > server.set_max_intset_entries)
                    setTypeConvert(subject,OBJ_ENCODING_HT);
                return 1;
            }
        } else {
            // 转化为整数类型失败，使用字典类型存储
            setTypeConvert(subject,OBJ_ENCODING_HT);

            serverAssert(dictAdd(subject->ptr,sdsdup(value),NULL) == DICT_OK);
            return 1;
        }
    } else {
        // 未知编码(类型)
        serverPanic("Unknown set encoding");
    }
    return 0;
}

4.3 set集合类型的经典使用场景如下

• 微博关注我的人和我关注的人都适合用集合存储，可以保证人员不会重复；
• 中奖人信息也适合用集合类型存储，这样可以保证一个人不会重复中奖。

五、sort set (有序列表)

sort Set是有序集合，从上面的图中可以看到sort Set的底层实现是ziplist和skiplist实现的，skiplist也叫做「跳跃表」，跳跃表是一种有序的数据结构，它通过每一个节点维持多个指向其它节点的指针，从而达到快速访问的目的。

5.1? ZipList（压缩列表）

压缩列表（ziplist）是一组连续内存块组成的顺序的数据结构，压缩列表能够节省空间，压缩列表中使用多个节点来存储数据。压缩列表是列表键和哈希键底层实现的原理之一，压缩列表并不是以某种压缩算法进行压缩存储数据，而是它表示一组连续的内存空间的使用，节省空间，压缩列表的内存结构图如下：

?redis 的压缩列表是一块连续的内存空间，元素之间紧挨着存储，没有任何冗余空间

• 压缩列表是支持双向遍历，所以才会有zltail_offset这个字段的，可以进行快速定位到最后一个元素。然后倒序查找(O(1))。
• prevlen 表示的是前一个字段的长度，有人就有疑问了，为什么是前一个entry的长度，为什么不是自己的呢，其实他还有一个作用是在压缩列表倒叙遍历的时候，需要通过这个字段来快速定位到下一个元素的位置，由于他是一个连续的存储空间，已经知道当前元素的位置+这个空间地址就可以确定写一个entry的位置。为什么会这样呢？因为entry的大小是不一样的。如果是一样的话就可以根据下表进行行为（个人理解，有错误还请指出），且prevlen 是一个变长的整数，redis的常规操作，将不同长度使用不同的数据类型。节省内存。
• encoding的意思是元素的编码类型，有了这个字段就可以决定元素内容的设定，内存大小的分配。防止内存分配浪费的一种方式。

5.2 skiplist 跳跃列表

有序集合具有唯一性和排序的功能，排序功能是借助分值字段 score 实现的，score 字段不仅可以实现排序功能，还可以实现数据的赛选与过滤的功能。我们还了解到了有序集合是由 压缩列表 (ziplist) 或跳跃列表 (skiplist) 来存储的，当元素个数小于 128 个，并且所有元素的值都小于 64 字节时，有序集合会采取 ziplist 来存储，反之则会用 skiplist 来存储，其中 skiplist 是从上往下、从前往后进行元素查找的，相比于传统的普通列表，可能会快很多，因为普通列表只能从前往后依次查找。

skiplist由如下几个特点：

• ??? 有很多层组成，由上到下节点数逐渐密集，最上层的节点最稀疏，跨度也最大。
• ??? 每一层都是一个有序链表，只扫包含两个节点，头节点和尾节点。
• ??? 每一层的每一个每一个节点都含有指向同一层下一个节点和下一层同一个位置节点的指针。
• ??? 如果一个节点在某一层出现，那么该以下的所有链表同一个位置都会出现该节点。
  ?

5.3 sort set 使用场景

有序集合的经典使用场景如下：

• 学生成绩排名
• 粉丝列表，根据关注的先后时间排序

博文参考