《数据结构与对象》

Posted on

五种对象（字符串对象、列表对象、哈希对象、集合对象、有序集合对象）的底层数据结构以及对对象的性能和功能的影响，也趁机复习一下数据结构

由于Redis使用的是C语言，很多其他高级语言有的数据结构，都要Redis自己实现，因此在分析Redis原理时，自然就要碰到常见的数据结构

简单动态字符串

Redis没有直接使用C语言的传统的字符串表示（即以空字符结尾的字符数组），而是自己构建了名为简单动态字符串（simple dynamic string，SDS）的抽象类型，除了作为Redis的默认字符串表示，还被用作缓冲区：AOF模块的AOF缓冲区以及客户端状态中的输入缓冲区

1
redis>RPUSH fruits "apple" "banana" "cherry"

上述语句就会创建键值对，键是一个字符串对象，底层实现就是SDS，值是一个列表对象，包含三个字符串对象，也是SDS实现

1
2
3
4
5
struct sdshdr {	
    unsigned int len;
    unsigned int free;
    char buf[];
};
  • len：记录SDS保存字符串长度
  • free：数组未使用字节长度

为什么要记录未使用空间呢？

与C字符串的区别

C获取字符串长度需要O(N)复杂度，而SDS获取长度只要O(1)，因此获取字符串长度不会成为Redis的瓶颈，可以通过STRLEN获取字符串长度

SDS能防止缓冲区溢出。例如对于C的char *strcat(char *dest,char *src);函数，默认用户已经为dest分配了足够的内存，如果假设不成立，就会产生缓冲区溢出

而SDS的空间分配策略杜绝了发生缓冲区的可能性。当SDS API需要对SDS进行修改，会先检查SDS的空间是否满足需求。如果不满足，会自动扩展

1
s = sdsMakeRoomFor(s,len);

但是SDS的分配策略不是只分配缺少的空间，会多分配一些

内存分配策略

对于C语言的字符串，只要涉及字符串长度，就要进行一次内存重分配操作

  • 对于append等增长字符串操作，就需要扩展底层数据的空间大小，否则就有可能发生缓冲区溢出
  • 对于trim等缩短字符串长度操作，就需要释放内存空间，否则就会发生内存泄漏

对于内存重分配，可能需要调用系统调用，这是一种代价很高的执行。

对于Redis这种数据频繁修改的场合，如果每修改一次字符串，都要执行内存重分配，那势必对性能造成影响。当这个地方我们就能回答最开始的问题 为什么要记录未使用空间呢？。

SDS通过记录未使用空间接触字符串长度和底层数组长度之间的关系。字符串长度增加不一定意味着底层数组增加，也就意味着不需要频繁调用内存重分配

空间预分配

额外分配的空间数量根据下面的代码段决定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define SDS_MAX_PREALLOC (1024*1024)

sds sdsMakeRoomFor(sds s, size_t addlen) {
  
    ...

    if (free >= addlen) return s;
    len = sdslen(s);
    sh = (void*) (s-(sizeof(struct sdshdr)));
   
    newlen = (len+addlen);
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
    if (newsh == NULL) return NULL;

    newsh->free = newlen - len;
    
    return newsh->buf;
}

从上面的代码可以看出，如果增加后的长度（newlen）小于1MB，则新长度翻倍；如果大于1MB，则只增加1MB

惰性空间释放

当需要缩短字符串时，程序不会立即使用内存重分配来回收多出来额度字节，而是使用free属性来记录多出来的空间。虽然这样做可以减少重分配操作，但另一方面也是浪费空间。因此SDS提供相应API能直接释放未使用的空间

二进制安全

C字符串除了字符串末尾，不能包含空字符，否则会误读，这就意味着C字符串只能保存文本数据，不能保存图片、音频、视频等二进制数据

而SDS API都是以处理二进制的方式处理存放在buf数组里的数据程序不会对其中的数据做任何限制、过滤或假设。写入时什么样，读取时就是什么样。因为SDS使用len值而不是空字符来判断结尾。这使得Redis能保存任意格式的二进制

虽然SDS不以空字符作为判断条件，但这些API依旧会将SDS保存的数据结尾设置为空字符，并在分配空间时多分配一个字节来容纳空字符，目的就是为了能重用<string.h>中的函数，减少不必要的代码重复

链表

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且通过增删节点灵活调整链表长度

链表除了在列表键应用外，还在发布于订阅、慢查询、监视器等功能应用，服务器本身还使用链表来保存多个客户端的状态信息以及构造客户端输出缓冲区

当一个列表键包含数量较多的元素时，或者列表中包含的元素都是较长的字符串时，就会使用链表作为列表键的底层实现

Redis服务器本身使用链表来保存多个客户端的状态信息，以及使用链表来构建客户端输缓冲区

链表的实现应该不是难题，来看看高手们的代码adlist.h

链表节点的定义

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

把节点封装成list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct list {
    
    listNode *head;
   
    listNode *tail;
    
    void *(*dup)(void *ptr);//节点值复制函数
   
    void (*free)(void *ptr);
    
    int (*match)(void *ptr, void *key);
   
    unsigned long len;
} list;

构造链表函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
list *listCreate(void)
{
    struct list *list;

    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;
   
    list->head = list->tail = NULL;
    list->len = 0;
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}

Redis的实现特性

  • 双向链表，获取前驱节点和后驱节点的复杂度都是O(1)
  • 无环链表，表头和表尾都指向NULL，对链表的访问以NULL为终点
  • 带有指向表头和表尾的指针，获取复杂度为O(1)
  • 链表长度计数器
  • 多态，节点都是使用void *保存节点值，因此列表可以保存不同类型的值

题外话：事实上，C语言通过某种组合方式，可以间接性的实现面对对象和抽象，就像Redis实现链表所做的那样

字典

Redis数据库就是用字典实现的，哈希键也是通过字典实现

Redis字典所使用哈希表的实现在dirt.h中

1
2
3
4
5
6
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

table属性就是一个数组，数组中的元素都是指向dictEntry结构的指针，sizemask总是等于size-1，这个属性和哈希值一起决定一个键应该被放到table数组的哪个索引上

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct dictEntry {

    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;

    struct dictEntry *next;
} dictEntry;

值的定义再一次体现了C语言也能实现类似于多态的性质

next属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一起，解决collision

Redis字典定义

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct dict {
   
    dictType *type;  

    void *privdata;
  
    dictht ht[2];
  
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
  
    int iterators; /* number of iterators currently running */
} dict;

type属性是一个指向dictType结构的指针，每个dictType保存一簇用于操作特定类型键值对的函数，Redis会为不同用途的字典设置不同的类型特定函数？？privdata属性保存需要传给那些类型特定函数的可选参数

上述两个属性为了创建多态字典而设置

ht属性是一个包含两个项的数组，每个元素是一个dictht哈希表，字典一般只是用ht[0]哈希表，ht[1]作为rehash使用

rehashidx记录rehash的进度，如果没有进行rehash，值为-1？？？

哈希算法

程序需要根据键值对计算出哈希值和索引值，再根据索引值，将包含键值对的哈希表节点放到哈希表数组的指定索引上，如下所示，使用的是宏定义

1
#define dictHashKey(d, key) (d)->type->hashFunction(key)

Redis使用MurmurHash2作为计算键的哈希值的算法，但是在最新的版本中使用SipHash

Redis的哈希表直接使用链地址法解决Collision，也就是使用next指针连接键冲突的键值对

rehash

为了让哈希表的负载因子（负载因子=ht[0].used/ht[0].size）维持在一个合理的范围，当哈希表保存的键值对数量太多或太少是，就需要对哈希表的大小进行扩展或收缩

  • 首先给ht[1]分配空间，如果是扩展，ht[1].size = 大于等于ht[0].used两倍的第一个2的幂，如果是收缩，ht[1].size = 大于等于ht[0].used的第一个2的幂
  • 将ht[0]键值对rehash到ht[1]
  • 释放ht[0]

当出现下面两种情况时，会自动开始对哈希表进行扩展

  • 服务器没有执行BGSAVE（在后台异步保存当前数据库的数据到磁盘）或BGREWRITEAOF（异步执行一个 AOF文件重写操作），且负载因子大于等于1
  • 服务器在执行BGSAVE或BGREWRITEAOF，且负载因子大于等于5

而当负载因子小于0.1时，会自动进行收缩操作

Performs N steps of incremental rehashing. Returns 1 if there are still keys to move from the old to the new hash table, otherwise 0 is returned.

上述表明服务器不是一次性将ht[0]rehash到ht[1]，而是分多次、渐进式rehash。这就是前面提到的rehashidx的作用，当开始rehash时，rehashidx设置为0，在rehash期间，每次对字典执行添加、删除、查找或更新操作时，程序除了执行指定操作时，还会顺带将ht[0]在rehashidx索引上的所有键值对rehash到ht[1]，当rehash完成，rehashidx加一，当所有rehash完成，rehashidx设置为-1

上述rehash方式将计算工作平摊到对字典的操作中，避免集中式rehash带来的系统停顿等后果。在渐进式rehash中，对字典的操作会在两个哈希表中进行

跳跃表

跳跃表作为有序集合键的底层实现之一，还作为集群节点中的内部数据结构，如下所示

Redis的跳跃表在server.h/zskiplistNode和server.h/zskiplist，zskiplistNode定义跳跃表节点，zskiplist保存跳跃表节点的信息，如节点数量等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

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

先跳过！！等学一下跳跃表！！

整数集合

当集合只包含整数值元素，并且数量不多时，就会使用整数集合（intset）作为集合键的底层实现

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

集合的元素按照从小到大的顺序无重复的放在contents数组里，虽然数组定义为int8_t，但是真正保存的类型取决于encoding：INISET_ENC_INT16 INISET_ENC_INT32 INISET_ENC_INT64

每当添加到集合的新元素比现有所有元素的类型都要长时，就要进行升级

  • 根据新元素类型，扩展底层数组的空间大小
  • 将现有元素转换成新元素的类型
  • 添加新元素

因为新添加的元素肯定小于或者大于现有所有元素，因此新元素要么放在底层数组的开头要么放在最末尾

由于C是静态类型语言，应该避免将不同类型的数组放在同一个数据结构中。但有了升级，就能随意将不同类型添加到集合中，而不用担心类型出错。另外就是节约内存

压缩列表

是列表键和哈希键的底层实现之一，当列表或者哈希键包含小整数值或者短字符串时，就会使用压缩列表

压缩列表是为了节约内存而开发，是由一系列特殊编码的连续内存块组成的顺序性数据结构，其形式有点类似于数据库的行记录格式

  • zlbytes：整个压缩列表占用的字节数
  • zltail：列表尾节点到头结点的偏移量
  • zllen：节点数量
  • entryX：节点
  • zlend：特殊值0xFF，表示列表末尾

每个节点由previous_entry_length encoding content三部分组成

  • previous_entry_length：当前一个节点的长度小于254字节，该属性长度只有1字节；如果大于等于254字节，该属性就有5字节，其中第一个字节设置为0xFE，后面的字节实际保存前一个节点的长度，例如0xFE00002766，实际长度就是0x0000002766。通过该属性和指针运算，就可以实现从表尾向表头遍历操作
  • encoding：记录节点content保存的数据的类型及长度，编码的开头两位表示类型，例如11表示整数编码，00 01 10表示字节数组编码，其余字节均表示长度。例如11000000表示int16_t类型整数，00bbbbbb长度小于63字节的字节数组
  • content：保存节点的值

连锁更新

该现象的出现就是因为previous_entry_length属性，如果每个节点的长度都接近254字节，当插入一个大于254字节的节点时，就会引起这个现象

虽然连锁更新的最坏复杂度为$O(N^2)$，但是发生的几率很低，因此不会影响性能

可能导致连锁更新的APIziplistPush ziplistInsert ziplistDelete ziplistDeleteRange

对象

Redis使用上面这些数据结构，构造了一个对象系统，这个系统就包含了字符串对象、列表对象、哈希对象、集合对象、有序集合对象五类对象

通过对象

  • 可以判断一个对象是否可以执行给定的命令
  • 可以针对不同的使用场景，对对象设置多种不同的实现，从而优化效率
  • 实现了基于引用计数的内存回收机制，并基于引用计数实现了对象共享机制
  • 对象带有访问时间记录信息

当我们在Redis数据库创建键值对时，至少会创建两个对象，一个对象作为键值对的键，一个作为键值对的值。每个对象都是由以下结构体表示

1
2
3
4
5
6
7
8
9
10
11
// server.h

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;

第一个属性记录对象的类型，可以是REDIS_STRING REDIS_LIST REDIS_HASH REDIS_SET REDIS_ZSET五种类型常量，对于Redis数据库的键值对来说，键总是一个字符串对象，值则可以是多种类型

对象中有一个ptr指针属性，它指向对象的底层实现数据结构，而encoding属性则指明对象使用数据结构的类型，如REDIS_ENCODING_INT REDIS_ENCODING_EMBSTR REDIS_ENCODING_HT等，它对于用户来说是不可见的。用户只能看到上述五种对象类型，而使用哪种数据结构来实现对象，则由服务器自主决定从上图我们还看到了一个新的数据结构quicklist去取代ziplist

通过encoding属性设定对象使用的编码（即底层实现），使得Redis可以根据不同的场景来实现对象，从而优化在该场景下的使用效率

字符串对象

字符串对象的底层编码可以是int、raw（简单动态字符串）和embstr（embstr编码的简单动态字符串）

如果字符串对象保存的是整数值，就可以用一个指向long类型的指针保存到ptr属性中

下图就是使用sdshdr作为底层数据结构实现，且是raw作为编码方式的字符串对象，这种方式就如图中所示，将调用两次内存分配函数来创建两个结构体

另一种也是使用sdshdr作为底层数据结构的字符串对象表示是embstr编码的，如下图所示，这种方式只需要调用一次内存分配函数

对于long double类型的浮点数在Redis中也是作为字符串表示，在有需要的时候转换成浮点数值，去做计算

在某些情况下，int和embstr编码的字符串对象就会转换成raw编码的字符串对象，如为int值后追加一个字符串时，就会从int编码转换成raw编码

列表对象

哈希对象

集合对象

有序集合对象

类型检查与多态

Redis上的命令分为两种，一种是对任何类型的键都执行，如DEL、EXPIRE、RENAME等；另一种就是只能针对特定类型的键执行

为了确保命令和输出键的类型相对应，服务器就需要通过对象中的type属性去检查，如果不符合就会返回类型错误信息

如果类型正确，还需要根据对象的编码方式（即encoding属性），选择合适的API去执行响应的命令

内存回收

Redis在自己的对象系统中构建了一个引用计数计数实现的内存回收机制，通过该机制就能自动释放对象并回收内存

对象共享

上面提到的refcount属性还带有对象共享的作用

每个对象的引用计数信息就记录在refcount属性中。当不同的键指向完全相同的对象时，就不会重新创建一个对象，而是选择共享，并在对象的refcount值+1。这种机制对于节约内存显然很有帮助

在这个基础上，Redis在初始化时，就会创建一万个字符串对象，包含0-9999的所有整数值，当服务器需要这些字符串对象时，就会选择共享对象，而不是新创建对象

但在实际操作中，这种现象好像消失了？？？

这些共享对象不仅只有字符串键可以使用，嵌套了字符串对象的对象都可以使用这些共享对象

由于将共享对象设置为键的值对象时，要检查共享对象和目的对象的完全一致性，对于复杂的共享对象，检查的复杂度就会很高，例如如果共享对象是保存整数值字符串对象，检查复杂度为O(1)；如果是保存字符串的字符串对象，复杂度为O(N)；如果是多个对象的对象，复杂度就是达到O(N^2)。因此Redis只选择对包含整数值的字符串进行共享

对象空转

对象的最后一个属性lru，记录对象最后一次被命令访问的时间，可使用OBJECT IDLETIME命令查看空转时长，但是该命令不会改变lru属性的值

该属性的另一个作用是服务器占用的内存超过了设置参数的上限，空转时长较高的那部分键会被优先被服务器释放掉，从而回收内存

quicklist