Redis 5设计与源码分析读书笔记

引言

Redis是目前最流行的键值对（key-value）数据库，以出色的性能著称，官方提供的数据是可以支持100000以上的+QPS。Redis具有高性能的主要原因如下：

• Redis是基于内存的存储数据库，绝大部分的命令处理只是纯粹的内存操作，内存的读写速度非常快。
• Redis是单进程线程的服务（实际上一个正在运行的Redis Server肯定不止一个线程，但只有一个线程来处理网络请求）​，避免了不必要的上下文切换，同时不存在加锁/释放锁等同步操作。
• Redis使用多路I/O复用模型（select、poll、epoll）​，可以高效处理大量并发连接。
• Redis中的数据结构是专门设计的，增、删、改、查等操作相对简单。

Redis 5.0的新特性

• 新增Streams数据类型，这是Redis 5.0最重要的改进之一。可以把Streams当作消息队列，详细内容参见后续章节。
• 新的模块API、定时器、集群及字典。
• RDB中持久化存储LFU和LRU的信息。
• 将集群管理功能完全用C语言集成到redis-cli中，Redis 3.x和Redis 4.x的集群管理是通过Ruby脚本实现的。
• 有序集合新增命令ZPOPMIN/ZPOPMAX。
• 改进HyperLogLog的实现。
• 新增Client Unblock和Client ID。
• 新增LOLWUT命令。
• Redis主从复制中的从不再称为Slave，改称Replicas。
• Redis 5.0引入动态哈希，以平衡CPU的使用率和相应性能，可以通过配置文件进行配置。Redis 5.0默认使用动态哈希。
• Redis核心代码进行了部分重构和优化。

Redis源码概述

Redis源代码主要存放在src文件夹中，作者没有整理这些文件，统一存放到了一个文件夹中，如图所示。其中server.c为服务端程序，redis-cli.c为客户端程序。

Redis源代码的核心部分主要如下。

1. 基本的数据结构
   • 动态字符串sds.c
   • 整数集合intset.c
   • 压缩列表ziplist.c
   • 快速链表quicklist.c
   • 字典dict.c
   • Streams的底层实现结构listpack.c和rax.c
2. Redis数据类型的底层实现
   • Redis对象object.c
   • 字符串t_string.c
   • 列表t_list.c
   • 字典t_hash.c
   • 集合及有序集合t_set.c和t_zset.c
   • 数据流t_stream.c
3. Redis数据库的实现
   • 数据库的底层实现db.c
   • 持久化rdb.c和aof.c
4. Redis服务端和客户端实现
   • 事件驱动ae.c和ae_epoll.c
   • 网络连接anet.c和networking.c
   • 服务端程序server.c
   • 客户端程序redis-cli.c
5. 其他
   • 主从复制replication.c
   • 哨兵sentinel.c
   • 集群cluster.c
   • 其他数据结构，如hyperloglog.c、geo.c等
   • 其他功能，如pub/sub、Lua脚本

Redis安装与调试

通过网址http://download.redis.io/releases/可以获得各个版本的Redis源码，本书以Redis 5.0为例，下载源码包并编译安装（源码包URL为http://download.redis.io/releases/redis-5.0.0.tar.gz）​。

    $ wget http://download.redis.io/releases/redis-5.0.0.tar.gz
    $ tar -zxvf redis-5.0.0.tar.gz
    $ cd redis-5.0.0
    $ make
    $ cd src
    $make install

到此，我们完成了Redis 5.0的编译安装，生成的可执行文件在/usr/local/bin目录中：
redis-benchmark redis-check-aof redis-check-rdb redis-cli redis-sentinel redis-server。
其中redis-benchmark是官方自带的Redis性能测试工具；当AOF文件或者RDB文件出现语法错误时，可以使用redis-check-aof或者redis-check-rdb修复；redis-cli是客户端命令行工具，可以通过命令redis-cli -h {host} -p {port}连接到指定Redis服务器；redis-sentinel是Redis哨兵启动程序；redis-server是Redis服务端启动程序。

简单动态字符串

简单动态字符串（Simple Dynamic Strings, SDS）是Redis的基本数据结构之一，用于存储字符串和整型数据。SDS兼容C语言标准字符串处理函数，且在此基础上保证了二进制安全。

数据结构

什么是二进制安全？通俗地讲，C语言中，用“\0”表示字符串的结束，如果字符串中本身就有“\0”字符，字符串就会被截断，即非二进制安全；若通过某种机制，保证读写字符串时不损害其内容，则是二进制安全。

SDS既然是字符串，那么首先需要一个字符串指针；为了方便上层的接口调用，该结构还需要记录一些统计信息，如当前数据长度和剩余容量等，例如：

    struct sds {
        int len; // buf中已占用字节数
        int free; // buf中剩余可用字节数
        char buf[]; // 数据空间
    };

SDS结构示意如图所示，在64位系统下，字段len和字段free各占4个字节，紧接着存放字符串:
Redis 3.2之前的SDS也是这样设计的。这样设计有以下几个优点：

• 有单独的统计变量len和free（称为头部）​。可以很方便地得到字符串长度。
• 内容存放在柔性数组buf中，SDS对上层暴露的指针不是指向结构体SDS的指针，而是直接指向柔性数组buf的指针。上层可像读取C字符串一样读取SDS的内容，兼容C语言处理字符串的各种函数。
• 由于有长度统计变量len的存在，读写字符串时不依赖“\0”终止符，保证了二进制安全。

上例中的buf[​]是一个柔性数组。柔性数组成员（flexible array member）​，也叫伸缩性数组成员，只能被放在结构体的末尾。包含柔性数组成员的结构体，通过malloc函数为柔性数组动态分配内存。

之所以用柔性数组存放字符串，是因为柔性数组的地址和结构体是连续的，这样查找内存更快（因为不需要额外通过指针找到字符串的位置）​；可以很方便地通过柔性数组的首地址偏移得到结构体首地址，进而能很方便地获取其余变量。

结合两个问题，5种类型（长度1字节、2字节、4字节、8字节、小于1字节）的SDS至少要用3位来存储类型（23=8）,1个字节8位，剩余的5位存储长度，可以满足长度小于32的短字符串。在Redis 5.0中，我们用如下结构来存储长度小于32的短字符串：

    struct __attribute__ ((__packed__))sdshdr5 {
        unsigned char flags; /＊ 低3位存储类型，高5位存储长度 ＊/
        char buf[]; /＊柔性数组，存放实际内容＊/
    };

sdshdr5结构中，flags占1个字节，其低3位（bit）表示type，高5位（bit）表示长度，能表示的长度区间为0～31（25-1）, flags后面就是字符串的内容。

而长度大于31的字符串，1个字节依然存不下。我们按之前的思路，将len和free单独存放。sdshdr8、sdshdr16、sdshdr32和sdshdr64的结构相同，sdshdr16结构如图所示。

其中“表头”共占用了S[2(len)+2(alloc)+1(flags)]个字节。flags的内容与sdshdr5类似，依然采用3位存储类型，但剩余5位不存储长度。在Redis 5.0中，sdshdr8、sdshdr16、sdshdr32和sdshdr64的数据结构如下：

    struct __attribute__((__packed__))sdshdr8 {
        uint8_t len; /＊ 已使用长度，用1字节存储 ＊/
        uint8_t alloc; /＊ 总长度，用1字节存储＊/
        unsigned char flags; /＊ 低3位存储类型，高5位预留 ＊/
        char buf[]; /＊柔性数组，存放实际内容＊/
    };
    struct __attribute__((__packed__))sdshdr16 {
        uint16_t len; /＊已使用长度，用2字节存储＊/
        uint16_t alloc; /＊ 总长度，用2字节存储＊/
        unsigned char flags; /＊ 低3位存储类型，高5位预留 ＊/
        char buf[]; /＊柔性数组，存放实际内容＊/
    };
    struct __attribute__((__packed__))sdshdr32 {
        uint32_t len; /＊已使用长度，用4字节存储＊/
        uint32_t alloc; /＊ 总长度，用4字节存储＊/
        unsigned char flags; /＊ 低3位存储类型，高5位预留 ＊/
        char buf[]; /＊柔性数组，存放实际内容＊/
    };
    struct __attribute__((__packed__))sdshdr64 {
        uint64_t len; /＊已使用长度，用8字节存储＊/
        uint64_t alloc; /＊ 总长度，用8字节存储＊/
        unsigned char flags; /＊ 低3位存储类型，高5位预留 ＊/
        char buf[]; /＊柔性数组，存放实际内容＊/
    };

可以看到，这4种结构的成员变量类似，唯一的区别是len和alloc的类型不同。结构体中4个字段的具体含义分别如下:

1. len：表示buf中已占用字节数。
2. alloc：表示buf中已分配字节数，不同于free，记录的是为buf分配的总长度。
3. flags：标识当前结构体的类型，低3位用作标识位，高5位预留。
4. buf：柔性数组，真正存储字符串的数据空间。

结构最后的buf依然是柔性数组，通过对数组指针作“减一”操作，能方便地定位到flags。

这样做有以下两个好:

• 节省内存，例如sdshdr32可节省3个字节（12-9）​。
• SDS返回给上层的，不是结构体首地址，而是指向内容的buf指针。因为此时按1字节对齐，故SDS创建成功后，无论是sdshdr8、sdshdr16还是sdshdr32，都能通过(char*)sh+hdrlen得到buf指针地址（其中hdrlen是结构体长度，通过sizeof计算得到）​。修饰后，无论是sdshdr8、sdshdr16还是sdshdr32，都能通过buf[-1]找到flags，因为此时按1字节对齐。若没有packed的修饰，还需要对不同结构进行处理，实现更复杂。

基本操作

数据结构的基本操作不外乎增、删、改、查，SDS也不例外。由于Redis 3.2后的SDS涉及多种类型，修改字符串内容带来的长度变化可能会影响SDS的类型而引发扩容。

创建字符串

创建SDS的大致流程：首先计算好不同类型的头部和初始长度，然后动态分配内存。需要注意以下3点。

1. 创建空字符串时，SDS_TYPE_5被强制转换为SDS_TYPE_8。
2. 长度计算时有“+1”操作，是为了算上结束符“\0”​。
3. 返回值是指向sds结构buf字段的指针。

从源码中我们可以看到，其实s就是一个字符数组的指针，即结构中的buf。这样设计的好处在于直接对上层提供了字符串内容指针，兼容了部分C函数，且通过偏移能迅速定位到SDS结构体的各处成员变量。

释放字符串

SDS提供了直接释放内存的方法——sdsfree，该方法通过对s的偏移，可定位到SDS结构体的首部，然后调用s_free释放内存。

为了优化性能（减少申请内存的开销）, SDS提供了不直接释放内存，而是通过重置统计值达到清空目的的方法——sdsclear。该方法仅将SDS的len归零，此处已存在的buf并没有真正被清除，新的数据可以覆盖写，而不用重新申请内存。

所以真清除，假清除，要看安迪雷斯的心情了

拼接字符串

拼接字符串操作本身不复杂，可用sdscatsds来实现。sdscatsds是暴露给上层的方法，其最终调用的是sdscatlen。由于其中可能涉及SDS的扩容，sdscatlen中调用sdsMakeRoomFor对带拼接的字符串s容量做检查，若无须扩容则直接返回s；若需要扩容，则返回扩容好的新字符串s。函数中的len、curlen等长度值是不含结束符的，而拼接时用memcpy将两个字符串拼接在一起，指定了相关长度，故该过程保证了二进制安全。最后需要加上结束符。

扩容策略

扩容策略如下：

• 若sds中剩余空闲长度avail大于新增内容的长度addlen，直接在柔性数组buf末尾追加即可，无须扩容
• 若sds中剩余空闲长度avail小于或等于新增内容的长度addlen，则分情况讨论：新增后总长度len+addlen<1MB的，按新长度的2倍扩容；新增后总长度len+addlen>1MB的，按新长度加上1MB扩容。
• 最后根据新长度重新选取存储类型，并分配空间。此处若无须更改类型，通过realloc扩大柔性数组即可；否则需要重新开辟内存，并将原字符串的buf内容移动到新位置。

其余API

SDS暴露给上层的是指向柔性数组buf的指针。读操作的复杂度多为O(1)，直接读取成员变量；涉及修改的写操作，则可能会触发扩容。

本章小结

兼容C语言字符串、保证二进制安全

SDS对象中的buf是一个柔性数组，上层调用时，SDS直接返回了buf。由于buf是直接指向内容的指针，故兼容C语言函数。而当真正读取内容时，SDS会通过len来限制读取长度，而非“\0”​，保证了二进制安全。

sdshdr5的特殊之处是什么

sdshdr5只负责存储小于32字节的字符串。一般情况下，小字符串的存储更普遍，故Redis进一步压缩了sdshdr5的数据结构，将sdshdr5的类型和长度放入了同一个属性中，用flags的低3位存储类型，高5位存储长度。创建空字符串时，sdshdr5会被sdshdr8替代。

SDS是如何扩容的

SDS在涉及字符串修改处会调用sdsMakeroomFor函数进行检查，根据不同情况动态扩容，该操作对上层透明。

跳跃表

有序集合在生活中较常见，如根据成绩对学生进行排名、根据得分对游戏玩家进行排名等。对于有序集合的底层实现，我们可以使用数组、链表、平衡树等结构。数组不便于元素的插入和删除；链表的查询效率低，需要遍历所有元素；平衡树或者红黑树等结构虽然效率高但实现复杂。Redis采用了一种新型的数据结构——跳跃表。跳跃表的效率堪比红黑树，然而其实现却远比红黑树简单。

简介

通过将有序集合的部分节点分层，由最上层开始依次向后查找，如果本层的next节点大于要查找的值或next节点为NULL，则从本节点开始，降低一层继续向后查找，依次类推，如果找到则返回节点；否则返回NULL。采用该原理查找节点，在节点数量比较多时，可以跳过一些节点，查询效率大大提升，这就是跳跃表的基本思想。跳跃表的实现过程如图所示：

从图中我们可以看出跳跃表有如下性质：

1. 跳跃表由很多层构成。
2. 跳跃表有一个头（header）节点，头节点中有一个64层的结构，每层的结构包含指向本层的下个节点的指针，指向本层下个节点中间所跨越的节点个数为本层的跨度（span）​。
3. 除头节点外，层数最多的节点的层高为跳跃表的高度（level）​，图中跳跃表的高度为3。
4. 每层都是一个有序链表，数据递增。
5. 除header节点外，一个元素在上层有序链表中出现，则它一定会在下层有序链表中出现。
6. 跳跃表每层最后一个节点指向NULL，表示本层有序链表的结束。
7. 跳跃表拥有一个tail指针，指向跳跃表最后一个节点。
8. 最底层的有序链表包含所有节点，最底层的节点个数为跳跃表的长度（length）​（不包括头节点）​，图中跳跃表的长度为7。
9. 每个节点包含一个后退指针，头节点和第一个节点指向NULL；其他节点指向最底层的前一个节点。

跳跃表每个节点维护了多个指向其他节点的指针，所以在跳跃表进行查找、插入、删除操作时可以跳过一些节点，快速找到操作需要的节点。归根结底，跳跃表是以牺牲空间的形式来达到快速查找的目的。跳跃表与平衡树相比，实现方式更简单，只要熟悉有序链表，就可以轻松地掌握跳跃表。

跳跃表节点与结构

跳跃表节点

下面我们来看跳跃表节点的zskiplistNode结构体:

    typedef struct zskiplistNode {
        sds ele;
        double score;
        struct zskiplistNode ＊backward;
        struct zskiplistLevel {
            struct zskiplistNode ＊forward;
            unsigned int span;
        } level[];
    } zskiplistNode;

该结构体包含如下属性:

1. ele：用于存储字符串类型的数据。
2. score：用于存储排序的分值。
3. backward：后退指针，只能指向当前节点最底层的前一个节点，头节点和第一个节点——backward指向NULL，从后向前遍历跳跃表时使用。
4. level：为柔性数组。每个节点的数组长度不一样，在生成跳跃表节点时，随机生成一个1～64的值，值越大出现的概率越低。level数组的每项包含以下两个元素:
   • orward：指向本层下一个节点，尾节点的forward指向NULL。
   • span:forward指向的节点与本节点之间的元素个数。span值越大，跳过的节点个数越多。

跳跃表是Redis有序集合的底层实现方式之一，所以每个节点的ele存储有序集合的成员member值，score存储成员score值。所有节点的分值是按从小到大的方式排序的，当有序集合的成员分值相同时，节点会按member的字典序进行排序。

跳跃表结构

除了跳跃表节点外，还需要一个跳跃表结构来管理节点，Redis使用zskiplist结构体，定义如下：

    typedef struct zskiplist {
        struct zskiplistNode ＊header, ＊tail;
        unsigned long length;
        int level;
    } zskiplist;

该结构体包含如下属性:

1. header：指向跳跃表头节点。头节点是跳跃表的一个特殊节点，它的level数组元素个数为64。头节点在有序集合中不存储任何member和score值，ele值为NULL, score值为0；也不计入跳跃表的总长度。头节点在初始化时，64个元素的forward都指向NULL, span值都为0。(就是常用的哨兵节点)
2. tail：指向跳跃表尾节点。
3. length：跳跃表长度，表示除头节点之外的节点总数。
4. level：跳跃表的高度。

基本操作

创建跳跃表

节点层高

节点层高的最小值为1，最大值是ZSKIPLIST_MAXLEVEL, Redis5中节点层高的值为64。Redis通过zslRandomLevel函数随机生成一个1～64的值，作为新建节点的高度，值越大出现的概率越低。节点层高确定之后便不会再修改。

创建跳跃表节点

跳跃表的每个节点都是有序集合的一个元素，在创建跳跃表节点时，待创建节点的层高、分值、member等都已确定。对于跳跃表的每个节点，我们需要申请内存来存储。zskiplistNode结构体的最后一个元素为柔性数组，申请内存时需要指定柔性数组的大小，一个节点占用的内存大小为zskiplistNode的内存大小与level个zskiplistLevel的内存大小之和。

头节点

头节点是一个特殊的节点，不存储有序集合的member信息。头节点是跳跃表中第一个插入的节点，其level数组的每项forward都为NULL, span值都为0。

创建跳跃表的步骤

创建完头节点后，就可以创建跳跃表。创建跳跃表的步骤如下。

1. 创建跳跃表结构体对象zsl。
2. 将zsl的头节点指针指向新创建的头节点。
3. 跳跃表层高初始化为1，长度初始化为0，尾节点指向NULL。

插入节点

插入节点的步骤：① 查找要插入的位置；② 调整跳跃表高度；③插入节点；④ 调整backward。

调整跳跃表高度

由上文可知，插入节点的高度是随机的，假设要插入节点的高度为3，大于跳跃表的高度2，所以我们需要调整跳跃表的高度。

调整backward

根据update的赋值过程，新插入节点的前一个节点一定是update[0]​，由于每个节点的后退指针只有一个，与此节点的层数无关，所以当插入节点不是最后一个节点时，需要更新被插入节点的backward指向update[0]​。如果新插入节点是最后一个节点，则需要更新跳跃表的尾节点为新插入节点。

删除节点

删除节点的步骤：1）查找需要更新的节点；2）设置span和forward。

设置span和forward

删除节点需要设置update数组中每个节点的span和forward。

删除跳跃表

获取到跳跃表对象之后，从头节点的第0层开始，通过forward指针逐步向后遍历，每遇到一个节点便将释放其内存。当所有节点的内存都被释放之后，释放跳跃表对象，即完成了跳跃表的删除操作。

跳跃表的应用

在Redis中，跳跃表主要应用于有序集合的底层实现（有序集合的另一种实现方式为压缩列表）​。
Redis的配置文件中关于有序集合底层实现的两个配置:

• zset-max-ziplist-entries 128:zset采用压缩列表时，元素个数最大值。默认值为128。
• zset-max-ziplist-value 64:zset采用压缩列表时，每个元素的字符串长度最大值。默认值为64。

值得注意的是，zset在转为跳跃表之后，即使元素被逐渐删除，也不会重新转为压缩列表。

小结

跳跃表的原理简单，其查询、插入、删除的平均复杂度都为O(logN)。跳跃表主要应用于有序集合的底层实现。

压缩列表

压缩列表ziplist本质上就是一个字节数组，是Redis为了节约内存而设计的一种线性数据结构，可以包含多个元素，每个元素可以是一个字节数组或一个整数。

Redis的有序集合、散列和列表都直接或者间接使用了压缩列表。 当有序集合或散列表的元素个数比较少，且元素都是短字符串时，Redis便使用压缩列表作为其底层数据存储结构。列表使用快速链表（quicklist）数据结构存储，而快速链表就是双向链表与压缩列表的组合。

压缩列表的存储结构

Redis使用字节数组表示一个压缩列表，压缩列表结构示意如图所示：

图中各字段的含义如下：

1. zlbytes：压缩列表的字节长度，占4个字节，因此压缩列表最多有2^32-1个字节。
2. zltail：压缩列表尾元素相对于压缩列表起始地址的偏移量，占4个字节。
3. zllen：压缩列表的元素个数，占2个字节。zllen无法存储元素个数超过65535（216-1）的压缩列表，必须遍历整个压缩列表才能获取到元素个数。
4. entryX：压缩列表存储的元素，可以是字节数组或者整数，长度不限。entry的编码结构将在后面详细介绍。
5. zlend：压缩列表的结尾，占1个字节，恒为0xFF。

压缩列表元素的编码结构：
previous_entry_length字段表示前一个元素的字节长度，占1个或者5个字节，当前一个元素的长度小于254字节时，用1个字节表示；当前一个元素的长度大于或等于254字节时，用5个字节来表示。而此时previous_entry_length字段的第1个字节是固定的0xFE，后面4个字节才真正表示前一个元素的长度。假设已知当前元素的首地址为p，那么p-previous_entry_length就是前一个元素的首地址，从而实现压缩列表从尾到头的遍历。

encoding字段表示当前元素的编码，即content字段存储的数据类型（整数或者字节数组）​，数据内容存储在content字段。为了节约内存，encoding字段同样长度可变。

可以看出，根据encoding字段第1个字节的前2位，可以判断content字段存储的是整数或者字节数组（及其最大长度）​。当content存储的是字节数组时，后续字节标识字节数组的实际长度；当content存储的是整数时，可根据第3、第4位判断整数的具体类型。而当encoding字段标识当前元素存储的是0～12的立即数时，数据直接存储在encoding字段的最后4位，此时没有content字段。

结构体

我们发现对于压缩列表的任意元素，获取前一个元素的长度、判断存储的数据类型、获取数据内容都需要经过复杂的解码运算。解码后的结果应该被缓存起来，为此定义了结构体zlentry，用于表示解码后的压缩列表元素。

    typedef struct zlentry {
        unsigned int prevrawlensize;
        unsigned int prevrawlen;
        unsigned int lensize;
        unsigned int len;
        unsigned char encoding;

       unsigned int headersize;

       unsigned char ＊p;
    } zlentry;

回顾压缩列表元素的编码结构，可变因素实际上不止3个：previous_entry_length字段的长度（prevrawlensize）​、previous_entry_length字段存储的内容（prevrawlen）​、encoding字段的长度（lensize）​、encoding字段的内容（len表示元素数据内容的长度，encoding表示数据类型）和当前元素首地址（p）​；而headersize则表示当前元素的首部长度，即previous_entry_length字段长度与encoding字段长度之和。

连锁更新

压缩列表连锁更新示意如图所示，删除压缩列表zl1位置P1的元素entryX，或者在压缩列表zl2位置P2插入元素entryY时，会出现什么情况呢？

压缩列表zl1中，由于元素entryX+1长度的增大，元素entryX+2的previous_entry_length字段同样需要改变。依此类推，由于删除了元素entryX，之后的所有元素（entryX+1、entryX+2等）的长度都必须扩展，而每次扩展都将重新分配内存，导致效率很低。压缩列表zl2中，插入元素entryY时同样会出现这种情况，称为连锁更新。从以上分析可以看出，连锁更新会导致多次重新分配内存及数据复制，效率很低。但是出现这种情况的概率是很低的，因此对于删除元素和插入元素操作，Redis并没有为了避免连锁更新而采取措施。

字典

基本概念

字典又称散列表，是用来存储键值（key-value）对的一种数据结构，在很多高级语言中都有实现，如PHP的数组。但是C语言没有这种数据结构，Redis是K-V型数据库，整个数据库是用字典来存储的，对Redis数据库进行任何增、删、改、查操作，实际就是对字典中的数据进行增、删、改、查操作。根据Redis数据库的特点，便可知字典有如下特征：

• 可以存储海量数据，键值对是映射关系，可以根据键以O(1)的时间复杂度取出或插入关联值。
• 键值对中键的类型可以是字符串、整型、浮点型等，且键是唯一的。例如：执行set test "hello world"命令，此时的键test类型为字符串，如test这个键存在数据库中，则为修改操作，否则为插入操作。
• 键值对中值的类型可为String、Hash、List、Set、SortedSet。

数组

当需要对数组a中元素进行操作时，C语言需通过下标找到其对应的内存地址，然后才能对这块内存进行对应的操作。例如，读取a[9]的值, C语言实际上会先转换为*(a+9)的形式，a[9]与*(a+9)）这两种形式是等价的，我们对等式两边再取地址，便可得出&a[9]==a+9，也就是说，要得到a[9]的地址，可以通过对数组a的首地址偏移9个元素就行。由此也可以知道，数组根据下标取值时，是通过头指针和偏移量来实现。

通过前文数组介绍可知，​“下标”的含义是数组中第几个元素的意思，只能为整数。根据第2个特征中键的描述：​“键值对中键的类型可以为字符串、整型、浮点型等”​，显然不能直接当成下标使用，此时，需要对键做一些特殊处理，处理过程我们称为Hash。

Hash函数

在应用上，通常使用现成的开源Hash算法，例如Redis自带客户端就是使用“times 33”散列函数来计算字符串的Hash值，Redis服务端的Hash函数使用的是siphash算法，主要功能与客户端Hash函数类似，其优点是针对有规律的键计算出来的Hash值也具有强随机分布性，但算法较为复杂。

那过大的Hash值与较小的数组下标怎么关联呢？最简单的办法是，用Hash值与数组容量取余，会得到一个永远小于数组容量大小的值，此时的值也就恰好可以当作数组下标来使用，我们把取余之后的值称为键在该字典中的索引值，即“索引值==数组下标值”​，拿到“键”的索引值后，我们就知道数组中哪个元素是用来存储键值对中的“值”了。但此方法并不是完美的，还会出现一个问题，Hash冲突。

Hash冲突

为了解决Hash冲突，所以数组中的元素除了应把键值对中的“值”存储外，还应该存储“键”信息和一个next指针，next指针可以把冲突的键值对串成单链表，​“键”信息用于判断是否为当前要查找的键。

Redis字典的实现

Redis字典实现依赖的数据结构主要包含了三部分：字典、Hash表、Hash表节点。字典中嵌入了两个Hash表，Hash表中的table字段存放着Hash表节点，Hash表节点对应存储的是键值对。

Hash表

Hash表，与5.1节设计的字典结构体类似，在Redis源码中取名为Hash表，其数据结构如下：

typedef struct dictht {
    dictEntry ＊＊table;            /＊指针数组，用于存储键值对＊/
    unsigned long size;            /＊table数组的大小＊/
    unsigned long sizemask;        /＊掩码 = size -1 ＊/
    unsigned long used;            /＊table数组已存元素个数，包含next单链表的数据＊/
} dictht;

Hash表的结构体整体占用32字节，其中table字段是数组，作用是存储键值对，该数组中的元素指向的是dictEntry的结构体，每个dictEntry里面存有键值对。size表示table数组的总大小。used字段记录着table数组已存键值对个数。

sizemask字段用来计算键的索引值，sizemask的值恒等于size-1。我们知道，索引值是键Hash值与数组总容量取余之后的值，而Redis为提高性能对这个计算进行了优化，具体计算步骤如下:

• 人为设定Hash表的数组容量初始值为4，随着键值对存储量的增加，就需对Hash表扩容，新扩容的容量大小设定为当前容量大小的一倍，也就是说，Hash表的容量大小只能为4,8,16,32…。而sizemask掩码的值就只能为3,7,15,31…，对应的二进制为11,111,1111,11111…，因此掩码值的二进制肯定是每一位都为1。
• 索引值=Hash值&掩码值，对应Redis源码为：idx = hash & d->ht[table].sizemask，其计算结果等同Hash值与Hash表容量取余，而计算机的位运算要比取余运算快很多。

Hash表节点

Hash表中的元素是用dictEntry结构体来封装的，主要作用是存储键值对，具体结构体如下：

    typedef struct dictEntry {
        void ＊key;                      /＊存储键＊/
        union {
            void ＊val;                  /＊db.dict中的val＊/
            uint64_t u64;
            int64_t s64;                /＊db.expires中存储过期时间＊/
            double d;
        } v;                            /＊值，是个联合体＊/
        struct dictEntry ＊next;        /＊当Hash冲突时，指向冲突的元素，形成单链表＊/
    } dictEntry;

Hash表中元素结构体和我们前面自定义的元素结构体类似，整体占用24字节，key字段存储的是键值对中的键。v字段是个联合体，存储的是键值对中的值，在不同场景下使用不同字段。 例如，用字典存储整个Redis数据库所有的键值对时，用的是*val字段，可以指向不同类型的值；再比如，字典被用作记录键的过期时间时，用的是s64字段存储；当出现了Hash冲突时，next字段用来指向冲突的元素，通过头插法，形成单链表。

字典

Redis字典实现除了包含前面介绍的两个结构体Hash表及Hash表节点外，还在最外面层封装了一个叫字典的数据结构，其主要作用是对散列表再进行一层封装，当字典需要进行一些特殊操作时要用到里面的辅助字段。