概述

Redis是一个键-值数据库，其中：

  • 数据库键总是一个字符串对象；
  • 数据库的值可以是字符串对象、列表对象、哈希对象、集合对象、有序集合对象这五种对象中的一种。

以上的五种对象都由各种底层数据结构来实现，接下来就一一介绍。

简单动态字符串

Redis使用C语言编写，但是字符串没有直接使用C语言传统的字符串表示，而是自己构建了一种名为简单动态字符串(SDS)的抽象类型作为默认字符串表示。

SDS的定义

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

SDS中的可用字符串之后会有一个’\0’，用于和C语言的字符串兼容，可以使用C语言中的许多字符串函数。但是SDS并不使用’\0’符号来判断字符串是否结束，而是使用len变量来判断。

简单来说，SDS中有一个buf对象，还有变量len和free，buf.size = len + free + 1(‘\0’占用一个字节)。

SDS与C字符串的区别

常数复杂度获取字符串长度

直接通过len变量即可获得字符串长度

杜绝缓冲区溢出

在使用 char strcat(char dest, const char *src)函数时，C语言默认我们已经为dest分配了足够的内存，而如果我们并未分配，就会发生缓冲区溢出。

而Redis中的字符串拼接前会检查SDS的空间是否满足需求，如果不满足会重新分配以容纳拼接后的字符串。

减少修改字符串时带来的内存重分配次数

SDS通过未使用空间解除字符串长度和底层数组长度之间的关联。使用空间预分配和惰性空间释放两种优化策略。

  • 空间预分配
    空间预分配用于优化SDS的字符串增长操作：当SDS的API对一个SDS进行修改，并需要对SDS进行空间扩展的时候，程序不尽会对SDS分配修改所必要的空间，还会为SDS分配额外的未使用空间。
    分配策略：
    • 如果修改后，SDS的len将小于1MB，则分配和len相同大小的未使用空间
    • 如果修改后，SDS的len大于等于1MB，则分配1MB的未使用空间
      在扩展SDS空间之前，SDS API会先检查未使用空间是否足够，如果足够的话，API就会直接使用未使用空间， 而不会重新分配内存。

  • 惰性空间释放
    惰性空间释放用于优化SDS的字符串缩短操作：当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，等待将来使用。

    与此同时，SDS也提供了相应的API，让我们可以在有需要时真正的释放SDS的未使用空间。

    二进制安全

    SDS使用len的值而不是空字符判断字符串是否结束，所以可以保存任何特殊格式的数据。

    兼容部分C字符串函数

链表

链表被用于实现Redis的各种功能，比如列表键、发布与订阅、慢查询、监视器等。

链表实现

1
2
3
4
5
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
}

由此可见链表底层是一个双向链表。

Redis底层还使用list结构体持有一个链表：

1
2
3
4
5
6
7
8
9
10
11
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;

通过为链表设置不同类型的特定函数，Redis的链表可以保存各种不同类型的值。

字典

字典，又称符号表、关联数组或映射，是一种保存键值对的抽象数据结构。字典在Redis中应用相当广泛，Redis的数据库就是使用字典作为底层实现的，除此之外，字典也是哈希键的实现之一。

字典的实现

字典使用哈希表作为底层实现。一个哈希表里面有多个哈希表节点，每个哈希表节点保存了字典的一个键值对。

哈希表

1
2
3
4
5
6
7
8
9
10
11
typedef struct dictht {
    //哈希表数组
    dictEntry **table;
    //哈希表大小
    unsigned long size;
    //哈希表大小掩码，用于计算索引值
    //总是等于size - 1
    unsigned long sizemask;
    //哈希表已有节点数量
    unsigned long used;
}dictht;

哈希表节点

1
2
3
4
5
6
7
8
9
10
11
typedef struct dictEntry {
    void *key;
    //值，使用联合体保存
    union {
        void *val;
        uint_64t u64;
        int64_t s64;
    } v;
    //指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

由此可知字典使用的是拉链法。

字典

1
2
3
4
5
6
7
8
9
10
typedef struct dict {
    //类型特定函数
    dictType *type;
    //似有数据
    void *privdata;
    //哈希表
    dictht ht[2];
    //rehash索引
    int rehashidx;
}

type和privdata属性是为针对不同类型的键值对，为创建多态字典而设置的。

  • type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数。
  • privdata属性保存了需要传给特定类型函数的可选参数。 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    typedef struct dictType {
        /*
        计算哈希值的函数
        复制键的函数
        复制值的函数
        对比键的函数
        销毁键的函数
        销毁值的函数
        */
    } dictType;

ht属性是一个包含两个项的数组，数组的每个项都是一个哈希表，一般情况下只使用ht[0]哈希表，ht[1]会在对ht[0]进行rehash时使用。

rehashidx用来记录rehash的进度，为-1时表示目前没有进行rehash。

哈希算法

添加值时，程序根据键值对的键计算出哈希值和索引值，再根据索引值将包含心键值对的哈希表节点放到哈希数组指定的索引上面。计算哈希值和索引值方法如下：
hash = dict->type->hashFunction(key);
index - hash & dict->ht[x].sizemask;//根据情况不同，x可以是0或者1
添加一个键值对之后的字典：
dict

解决键冲突

当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时，我们称这些键发生了冲突。
Redis使用拉链法来解决键的冲突，每个哈希表节点都有一个next指针，多个哈希表及诶单可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以通过这个单向链表连接起来，这就解决了键冲突问题。
因为dictEntry节点组成的链表没有指向链表表尾的指针，所以每次将新节点添加到链表的表头位置，排在其他已有节点的前面。

rehash

随着操作的不断执行，哈希表保存的键值对会逐渐地增多或减少，为了让哈希表的负载因子维持在一个合理的范围内，程序需对哈希表的大小进行相应的扩展或者收缩。

Redis对字典的哈希表执行rehash的步骤如下：

  • 为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量；
    • 如果是执行扩展操作，那么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[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备。

渐进式rehash

扩展或收缩哈希表需要rehash，然是这个动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的。

渐进式rehash的详细步骤：

  • 在ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。
  • 在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始。
  • 在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序出了执行指定的操作外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成后，程序将rehashidx属性的值增一。
  • 随着字典操作的不断进行，最终在某个时间点上，ht[0]的所有键值对都会rehash到ht[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作完成。

渐进式rehash期间，字典的删除、查找、更新等操作会在两个哈希表上进行。
新添加到字典的键值对一律被保存到ht[1]里面。

跳跃表

跳跃表是一种有序数据结构，他通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的，跳跃表是有序集合键的底层实现之一。

跳跃表的数据结构实现可参考此处。

跳跃表结构

1
2
3
4
5
6
typedef struct zskiplist {
    zskiplistNode *head;
    zskiplistNode *tail;
    unsigned long length;
    int level;
}zskiplist;

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

跳跃表节点

结构定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct zskiplistNode {
    //层
    struct zskiplistLevel {
        //前进指针
        struct zskiplistNode *forward;
        //跨度
        unsigned int span;
    } level[];
    //后退指针
    struct zskiplistNode *backward;
    //分值
    double score;
    robj *obj;
}zskiplistNode;

层

层:节点中用L1、L2、L3等字样标记节点的各个层，L1代表第一层，L2代表第二层，以此类推。每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离。层的数量越多，访问其他节点的速度就越快。

创建新节点时，程序根据幂次定律随机生成一个介于1和32之间的值作为层数。

跨度

跨度用于记录两个节点之间的距离。
跨度可用于计算排位。只要在查找过程中将沿途访问的层的跨度都累记下来，最后得到的结果就是目标在跳跃表中的排位。

后退指针

后退指针:节点中用BW字样标记节点的后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。逆序遍历时每次只能后退至前一个节点。

分值和成员

分值:各个节点中有一个节点所保存的分值，在跳跃表中，节点按照各自所保存的分值从小到大排列。
成员对象:节点中保存各自的成员对象，如o1、o2、o3。

同一个跳跃表中，节点保存的成员对象必须是唯一的，多个节点保存的分值可以是相同的：分支相同的节点将按照成员对象字典序来排序。

整数集合

证书聚合是集合键的底层实现之一，当一个集合只包含整数值元素，且集合的元素数量不多时，Redis就会使用证书集合作为底层实现。

整数聚合的实现

1
2
3
4
5
typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
}intset;

length就是contents的长度，也就是整数集合中元素的数量。

contents虽然是int8_t类型，但是保存整数的长度取决于encoding的值：

  • 如果encoding = INTSET_ENC_INT16，则每一项都是一个16位的整数值(-32768 - 32767)
  • 如果encoding = INTSET_ENC_INT32，则每一项都是一个32位的整数值(-2147483648 - 2147483647)
  • 如果encoding = INTSET_ENC_INT64，则每一项都是一个64位的整数值

升级

每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有元素的类型都要长时，整数集合需要先进行升级，然后才能添加新元素到整数集合里面。

添加新元素分三步：

  1. 根据新元素类型，扩展数组空间大小，并为新元素分配空间；
  2. 将底层数组的元素都转换为新元素相同的类型，并将其放到正确的位置上；
  3. 将新元素添加到底层数组中。
    添加新元素需要升级时，新元素只可能在第一位或最后一位，此时按照新的元素长度修改之前元素即可。

升级的好处

  1. 提升灵活性
    因为C语言是静态语言类型，为避免类型错误，我们通常不会将两种不同类型的值放在同一个数据结构里面。但是使用升级之后可以随意的在集合中添加16、32、64位的整数，而不用担心类型错误。

  2. 节约内存

压缩列表

压缩列表是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现。

当一个哈希键只包含少量键值对，并且每个键是对的值要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做哈希键的底层实现。

压缩表的构成

zlbytes zltail zllen entry1 entry2 … entryN zlend
属性 类型 长度 用途
zlbytes uint32_t 4字节 记录整个压缩列表占用的内存字节数:在对压缩表进行内存重分配或计算zlend时使用
zltail uint32_t 4字节 记录压缩列表表尾节点举例压缩列表起点位置的字节偏移量
zllen uint16_t 2字节 记录压缩列表包含的节点数量:小于65535时，这个值就是压缩表的节点数量，等于时需遍历计算
entryX 列表节点 不定 压缩列表的各个节点，大小由节点内容决定
zlend uint8_t 1字节 特殊值OxFF(255)，标记压缩列表的末端

根据这些值进行相应的计算即可算出各个位置。设列表起始地址为P，zlbytes的值为X，zltail的值为Y，那么列表总长为X字节，最后一个节点entry[zllen]的地址就是P + Y。

压缩列表节点的构成

每个压缩列表保存一个字节数组或一个整数值。
其中， 字节数组可以是以下三种长度的其中一种：
长度小于等于 63 （2^{6}-1）字节的字节数组；
长度小于等于 16383 （2^{14}-1） 字节的字节数组；
长度小于等于 4294967295 （2^{32}-1）字节的字节数组；

而整数值则可以是以下六种长度的其中一种：
4 位长，介于 0 至 12 之间的无符号整数；
1 字节长的有符号整数；
3 字节长的有符号整数；
int16_t 类型整数；
int32_t 类型整数；
int64_t 类型整数。
每个压缩列表节点都由 previous_entry_length 、 encoding 、 content 三个部分组成， 如下表所示。
| previous_entry_length |encoding |content |
|:—|

prprevious_entry_length

如果前一节点的长度小于 254 字节， 那么 previous_entry_length 属性的长度为 1 字节： 前一节点的长度就保存在这一个字节里面。

如果前一节点的长度大于等于 254 字节， 那么 previous_entry_length 属性的长度为 5 字节： 其中属性的第一字节会被设置为 0xFE （十进制值 254）， 而之后的四个字节则用于保存前一节点的长度。

因为节点的 previous_entry_length 属性记录了前一个节点的长度， 所以程序可以通过指针运算， 根据当前节点的起始地址来计算出前一个节点的起始地址。

如果我们有一个指向当前节点起始地址的指针 c ， 那么我们只要用指针 c 减去当前节点 previous_entry_length 属性的值， 就可以得出一个指向前一个节点起始地址的指针 p 。p = c - current_entry.previous_entry_length

压缩列表通过这个途径进行从尾到头的遍历。从尾到头遍历的好处是在重新分配空间时可直接进行操作。

encoding

节点的 encoding 属性记录了节点的 content 属性所保存数据的类型以及长度：
一字节、两字节或者五字节长， 值的最高位为 00 、 01 或者 10 的是字节数组编码： 这种编码表示节点的 content 属性保存着字节数组， 数组的长度由编码除去最高两位之后的其他位记录；
一字节长， 值的最高位以 11 开头的是整数编码： 这种编码表示节点的 content 属性保存着整数值， 整数值的类型和长度由编码除去最高两位之后的其他位记录；
下表记录了字节数组编码和整数编码。表格中的下划线 _ 表示留空， 而 b 、 x 等变量则代表实际的二进制数据， 为了方便阅读， 多个字节之间用空格隔开。

字节数组编码

编码 编码长度 content属性保存的值
00bbbbbb 1 字节 长度小于等于 63 字节的字节数组。
01bbbbbb xxxxxxxx 2 字节 长度小于等于 16383(2的14次-1) 字节的字节数组。
10________ aaaaaaaa bbbbbbbb cccccccc dddddddd 5 字节 长度小于等于 4294967295(2的32次-1) 的字节数组。

整数编码

编码 编码长度 content属性保存的值
11000000 1 字节 int16_t 类型的整数。
11010000 1 字节 int32_t 类型的整数。
11100000 1 字节 int64_t 类型的整数。
11110000 1 字节 24 位有符号整数。
11111110 1 字节 8 位有符号整数。
1111xxxx 1 字节 使用这一编码的节点没有相应的 content 属性， 因为编码本身的 xxxx四个位已经保存了一个介于 0 和 12 之间的值， 所以它无须 content 属性。

content

节点的 content 属性负责保存节点的值， 节点值可以是一个字节数组或者整数， 值的类型和长度由节点的 encoding 属性决定。

连锁更新

在一个压缩列表中， 有多个连续的、长度介于 250 字节到 253 字节之间的节点 e1 至 eN ，因为 e1 至 eN 的所有节点的长度都小于 254 字节， 所以记录这些节点的长度只需要 1 字节长的 previous_entry_length 属性， 换句话说， e1 至 eN 的所有节点的 previous_entry_length 属性都是 1 字节长的。

这时， 如果我们将一个长度大于等于 254 字节的新节点 new 设置为压缩列表的表头节点， 那么 new 将成为 e1 的前置节点。因为 e1 的 previous_entry_length 属性仅长 1 字节， 它没办法保存新节点 new 的长度， 所以程序将对压缩列表执行空间重分配操作， 并将 e1 节点的 previous_entry_length 属性从原来的 1 字节长扩展为 5 字节长。

现在， 麻烦的事情来了 —— e1 原本的长度介于 250 字节至 253 字节之间， 在为 previous_entry_length 属性新增四个字节的空间之后， e1 的长度就变成了介于 254 字节至 257 字节之间， 而这种长度使用 1 字节长的 previous_entry_length 属性是没办法保存的。

因此， 为了让 e2 的 previous_entry_length 属性可以记录下 e1 的长度， 程序需要再次对压缩列表执行空间重分配操作， 并将 e2 节点的 previous_entry_length 属性从原来的 1 字节长扩展为 5 字节长。这样不断循环，最终每个节点都会进行更新。最坏时间复杂度为O(n2)。删除节点也是如此。

虽然连锁更新的复杂度较高， 但它真正造成性能问题的几率是很低的：

首先， 压缩列表里要恰好有多个连续的、长度介于 250 字节至 253 字节之间的节点， 连锁更新才有可能被引发， 在实际中， 这种情况并不多见；
其次， 即使出现连锁更新， 但只要被更新的节点数量不多， 就不会对性能造成任何影响： 比如说， 对三五个节点进行连锁更新是绝对不会影响性能的；
因为以上原因， ziplistPush 等命令的平均复杂度仅为 O(N) ， 在实际中， 我们可以放心地使用这些函数， 而不必担心连锁更新会影响压缩列表的性能。