基础数据结构

目录

动态字符串

sds

redis用c语言编写，自己构建了一个名为简单字符串(simple dynamic string,SDS)的抽象类型,作为redis的默认字符串表示.

如:

1
2
redis> SET msg "hello world"
OK

redis在数据库中创建的过程.

  1. 键值对的键是一个字符串对象.对象底层实现保存则字符串msg的SDS.
  2. 键值对的值也是一个字符串对象,也是SDS.

除了用作保存数据库中的字符串,SDS还被用作缓冲区(BUFFER),AOF中的AOF缓冲区.客户端状态的输入缓冲区,都是SDS实现

sds定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct sdshdr {
  // buf数组中已使用的字节数
  // 等于sds字符串长度
  int len;
  // 未使用的字节的数量
  int free;
  // 保存字符串.
  // sds遵循c字符串以空字符结尾的惯例('\0')
  // 保存的空字符串不计算在len中.
  // 好处是可以直接重用一部分c字符串函数库.pintf("%s",s->buf);
  // buf = [r,e,d,i,s,\0], len = 5, free =0;
  char buf[];
}


sds与c字符串的比较

c字符串使用n+1的字符数组表示长为n的字符串,字符数组的最后一个元素总是空字符\0.并不能满足redis对字符串在安全性,效率性及功能方面的需求

  1. c字符串不记录自身长度.获取长度的复杂度为O(N).
  2. 杜绝了缓冲区溢出,stract函数可以拼接字符串,由于c字符串不保存长度,stract在拼接的时候默认用户已经为dest分配了足够的内存.sds的拼接回自动将sds的空间扩展至执行所需的大小.char *stract(char *dest,const char *src);
  3. c字符串不记录自身长度,每次增长或缩短,总要对这个c字符串的数据进行内存重新分配.
    • sds的空间预分配
      1. 如果对sds进行修改,sds长度将小于1mb,那么程序分配和len属性同样大小的未使用空间.sds的len和free相等.
      2. 如果分配的长度大于等于1mb,那么会分配1mb未使用的空间
    • 惰性空间释放
      当sds的api需要缩短sds保存的字符串,程序不会立即使用内存重分配来回收缩短后多出来的字节,而是使用free属性
  4. 二进制安全.c字符串除了字符串的末尾之外,不能包含空字符,不然会被程序读入的空字符误认为字符串结尾.redis会以处理二进制的方式来处理sds存放在buf里的数据.不会对其中的数据进行任何限制,过滤.redis不是用buf来保存字符,而是用来保存一系列二进制数据
  5. 兼容部分c字符串函数.

链表

链表提供了高效的节点重排能力,顺序性节点访问方式(连续内存?),可以通过增删节点来灵活地调整链表长度.

链表在redis中的应用非常广泛.列表键的底层实现之一就是链表.当一个列表键包含了数量比较多的元素或者表中包含的元素都是比较长的字符串,redis就会用链表作为底层实现.

除了列表键,发布订阅,慢查询,监视器也用到了链表.

链表和链表节点的实现.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct listNode{
  struct listNode *prev;
  struct listNode *after;
  void *value;
} listNode;

typedef struct list{
  listNode *head;
  listNode *tail;
  unsigned long len;
  // 节点复制函数
  void *(*dup)(void *ptr);
  // 节点释放函数
  void (*free)(void *ptr);
  // 节点对比函数
  int (*match)(void *ptr,void *key);
}

redis链表特点:

  1. 双端
  2. 无环
  3. 带头指针尾指针
  4. 带长度
  5. 多态,链表节点使用void*指针保存节点值,通过list的dup,free,match属性为节点值设置类型特定函数.

字典

字典,符号表(symbol table),关联数组(associative array),映射(map).

字典在redis数据库中应用相当广泛:

  1. redis数据库就是用字典作为底层实现. 
    1
    2
    redis> SET msg "hello world"
    OK
    在数据库中创建一个key为”msg”,值为”hello world”的键值对,这个键值对就是保存在代表数据库的字典里面的.
  2. 字典也是hash键的底层实现之一,当一个hash键包含的键值对比较多,或者键值对中的元素都是比较长的字符串时,redis就会用字典作为hash键的底层实现.

字典的实现

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct dictht {
  // 哈希表数组
  dictEntry **table;

  // 哈希表大小
  unsigned long size;

  // 哈希表大小掩码,计算索引值
  // 总等于 size-1
  unsigned long sizemask;
  // hash表已又节点的数量
  unsigned long used;
} dictht;

哈希表节点

1
2
3
4
5
6
7
8
typeof struct dictEntry{
  void *key;
  union{
    uint64_tu64;
    int64_ts64;
  }v;
  struct dictEntry *next;
}dictEntry;

字典

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef struct dict {
  // 每个dictType结构保存了一簇用于操作特定类型键值对的函数,redis会为用途不同的字典设置不同的类型特点函数
  dictType *type;
  // 保存了需要传给特点类型函数的参数.
  void *privdate;
  // 包含两个项得数组,每个项都是一个dictht 哈希表.一般情况只是用ht[0]哈市表,ht[1]在rehash时使用.
  dictht ht[2];

  // rehash索引,代表当前得进度.
  // 当rehash不再进行时,值为-1;
  int trehashidx;
}dict;

typedef struct dictType{
  
  // 计算hash的函数
  // 复制键的函数
  // 复制值得函数
  // 对比键得函数
  // 销毁键得函数
  // 销毁值得函数
}

image.png

哈希算法

MurmurHash算法

冲突解决

拉链法解决得冲突

rehash

负载因子计算: load_factor = ht[0].used/ht[0].size
扩展条件

  1. 没有执行bgsave或bgrewriteaof,当负载椅子大于等于1进行扩展
  2. 执行bugszve活bgrewriteaof,

跳表

通过在每个节点维持多个指向其他节点得指针,从而快速访问.

支持平均O(logN),最坏O(N)复杂度得节点查找.有序集合键得底层实现.另一个地方在集群节点中用作内部数据结构.

整数集合

集合键的底层实现之一.

压缩列表

ziplist,列表键和hash键底层实现之一

为了节约内存开发的,由一系列特殊编码的连续内存块组成的顺序型数据结构.一个压缩列表可以包含任意多个节点,每个节点可以保存一个字节数组或者一个整数值.

当一个列表只包含少量列表项, 并且每个列表项要么就是小整数值,要么就是长度短的字符串,redis就会使用ziplist作为列表底层实现.

主要结构

image.png

节点的构成

previous_entry_length encoding length

连锁更新

每个previous_entry_length属性记录了前一个节点的长度,如果前一节点长度小于254,那么,用1字节保存即可,如果大于等于254,则用5字节.

如果将一个大于254的节点设置为压缩列表的表头节点.而e1(原先第一个节点)的previous_entry_length为1,则必然不够放,需要扩充成5字节长度.那么e1的长度从原来的长度(如250-253)则变为254-257.那么e2也需要扩展…这种特殊情况造成的多次扩展空间操作被称为连锁更新

对象

redis基于以上几种数据结构创建了对象系统,这个系统包含字符串对象,列表对象,哈希对象,集合对象和有序集合对象这五种类型的对象,每种对象都用到了至少一种使用到的结构.

redis的对象系统实现了基于引用计数的内存回收机制.不再使用某个对象的时候,这个对所占用的内存就会自动释放.redis还通过引用计数技术实现了对象共享机制,这一机制可以在适当的条件下,通过让多个数据库键共享同一个对象来节约内存.

对象类型与编码

redis使用对象来表似数据库的键和值,每次在redis的库中创建一个新的键值对时,至少会创建两个对象,一个用作键值对的键(对象),另一个对象用作值(对象).

1
2
3
4
5
typedef struct redisObject {
  unsigned type:4;
  unsigned encoding:4;
  void *ptr;// 底层实现数据结构的指针
} robj
类型常量 对象名 type输出
redis_string 字符串 string
redis_list 列表 list
redis_hash 哈希对象 hash
redis_set 集合对象 set
redis_zset 有序集合对象 zset 
1
2
3
4
5
6
7
8
9
10
> set msg "helloworld"
OK
> TYPE msg
string
----
> rpush nl  1 3 5
3
> type nl
list
---

编码与底层实现

image.png

对象的ptr指针指向对象的底层实现数据结构,这些数据结构由对象的encoding属性决定.encoding属性记录了对象所用的编码,也即说这个对象使用了什么数据结构作为对象的底层实现

编码常量 编码所对应的底层数据结构
redis_encoding_int long类型的整数
redis_encoding_embstr embstr编码的简单动态字符串
redis_encoding_raw 简单动态字符串
redis_encoding_ht 字典
redis_encoding_linkedlist 双端链表
redis_encoding_ziplist 压缩列表
redis_ecndoing_intset 整数集合
redis_encoding_skiplist 跳跃表和字典

每种类型的对象都至少使用了两种不同编码,部分对象的编码:

image.png

1
2
3
4
5
6
7
8
9
> object encoding msg
embstr
> object encoding nl
quicklist # redis 3.2之后列表的底层存储只有一种,quicklist
--------------
> set story "long long long long long long long long long long long long long long long ago.............."
OK
> object encoding story
raw

object encoding 命令输出
|对象使用的底层数据结构|编码常量|object encoding命令输出|
|:——————|:——|:——————–|
|整数|redis_encoding_int|int|
|embstr编码的简单动态字符串(sds)|redis_encoding_embstr|embstr|
|简单动态字符串|redis_encoding_raw|raw|
|字典|redis_encoding_ht|hashtable|
|双端链表|redis_encoding_linkedList|linkedlist|

字符串对象

字符串对象的编码可以是 int，raw或embstr

int

1
2
3
4
5
6
7
8
redis> set numer 10086
ok
----------------------------------
redisObject
type        | redis_string
encoding    | redis_encoding_int
ptr         | 10086
----------------------------------

raw

如果字符串对象保存的一个字符串值长度大于32字节,那么将用一个简单的动态字符串(SDS)保存这个字符串值.将这个对象编码设置为raw.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
redis> set numer 10086
ok
----------------------------------
redisObject
type        | redis_string
encoding    | redis_encoding_raw
ptr         | 
----------------------------------

----------------------------------
ptr
sdshdr  |
free    | 0
len     | 37
buf     | 'l','o','n','g'........|
----------------------------------

embstr

如果字符串的值长度小于等于32字节,那么字符串对象使用embstr编码的方式保存这个字符串值.

embstr时专门用来保存短字符串的一种优化编码方式.和raw编码一样,都是用redisObject结构和sdshdr结构表似字符串对象.
raw会调用两次内存分配函数创建redisObject和sdshdr结构,而embstr调用一次内存分配函数,分配一块连续的空间

embstr保存短字符串值得好处:

  1. embstr编码创建字符串对象得内存分配从raw编码得两次降低为1次
  2. 释放embstr编码得字符串对象也只需要释放一次
  3. 连续内存比raw编码字符串对象更好利用缓存优势

编码的转换

int编码和embstr编码的对象在条件满足情况下,会被转为raw编码的字符串对象.

1
2
3
4
5
6
7
8
9
10
> set number 10086
OK
> object encoding number
int
> append number " is a good number!"
23
> get number
10086 is a good number!
> object encoding number
raw

列表对象

快速列表(3.2之后)

在 Redis3.2 之前，linkedlist 和 ziplist 两种编码可以进选择切换，如果需要列表使用 ziplist 编码进行存储，则必须满足以下两个条件：

  1. 列表对象保存的所有字符串元素的长度都小于 64 字节。(list-max-ziplist-value)
  2. 列表对象保存的元素数量小于 512 个。(list-max-ziplist-entries)

redis 3.2版本之后列表只用quicklist了,时linked list 与 ziplist的结合.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
typedef struct quicklistNode {
    struct quicklistNode *prev;//前一个节点
    struct quicklistNode *next;//后一个节点
    unsigned char *zl;//当前指向的ziplist或者quicklistlzf
    unsigned int sz;//当前ziplist占用字节
    unsigned int count : 16;//ziplist中存储的元素个数，16字节(最大65535个)
    unsigned int encoding : 2; //是否采用了LZF压缩算法压缩节点 1：RAW 2:LZF
    unsigned int container : 2; //存储结构，NONE=1, ZIPLIST=2
    unsigned int recompress : 1; //当前ziplist是否需要再次压缩(如果前面被解压过则为true，表示需要再次被压缩)
    unsigned int attempted_compress : 1;//测试用 
    unsigned int extra : 10; //后期留用
} quicklistNode;

typedef struct quicklist {
    quicklistNode *head;//列表头节点
    quicklistNode *tail;//列表尾节点
    unsigned long count;//ziplist中一共存储了多少元素，即:每一个quicklistNode内的count相加
    unsigned long len; //双向链表的长度，即quicklistNode的数量
    int fill : 16;//填充因子
    unsigned int compress : 16;//压缩深度 0-不压缩
} quicklist;

typedef struct quicklistLZF {
    unsigned int sz;// LZF大小，占用4字节
    char compressed[];//被压缩的内容，占用N字节
} quicklistLZF;

quicklist 就是综合平衡考虑了 linkedlist 容易产生空间碎片的问题和 ziplist 的读写性能两个维度而设计出来的一种数据结构。使用 quicklist 需要注意以下 2 点：

  1. 如果 ziplist 中的 entry 个数过少，最极端情况就是只有 1 个 entry 的压缩列表，那么此时 quicklist 就相当于退化成了一个普通的 linkedlist
  2. 如果 ziplist 中的 entry 过多，那么也会导致一次性需要申请的内存空间过大（ziplist 空间是连续的），而且因为 ziplist 本身的就是以时间换空间，所以会过多 entry 也会影响到列表对象的读写性能。

ziplist 中的 entry 个数可以通过参数 list-max-ziplist-size 来控制：list-max-ziplist-size 1,可以设置为负数(-1~-5)

  • -1：每个 ziplist 最多只能为 4KB
  • -2：每个 ziplist 最多只能为 8KB
  • -3：每个 ziplist 最多只能为 16KB
  • -4：每个 ziplist 最多只能为 32KB
  • -5：每个 ziplist 最多只能为 64KB

hash对象

hash对象的编码可以是ziplist或者hashtable

编码转换

  1. hash对象保存的所有键值对的键和值的字符串长度小于64字节
  2. 哈希对象保存的键值对个数小于512.

不能满足这两个条件的hash对象需要使用hashtable编码.
hash-max-ziplist-value
hash-max-ziplist-engries

1
2
3
4
5
6
7
8
> hset book name "Mastering c++ in 21 days"
1
> object encoding book
ziplist
> hset book kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk "content"
1
> object encoding book
hashtable

集合对象

集合对象的编码可以是intset或者hashtable,有点类似java里得hashmap也是用map做底层…
字典的每个key是一个字符串对象,值为null.

编码转换

  1. 集合对象保存的所有元素都是整数值
  2. 集合对象保存的元素数量不超过512
    不能满足的集合对象需要使用hashtable编码.

有序结合对象

编码可以是ziplist或者skiplist

  • ziplist:每个集合元素使用两个紧挨在一起的压缩列表节点来保存,第一个节点保存元素的成员(member),而第二个保存元素的分值(score).压缩列表内的结合元素按分值从小到大进行排序.
1
2
3
4
5
6
7
8
9
10
11

> zadd price 8.5 apple 5.0 banana 6.0 cherry
3
> object encoding price
ziplist
------------------------
reidsobject
type      redis_zset
encoding  redis_encoding_ziplist
ptr       压缩列表
------------------------
zlbytes zltail zllen “banana” 5.0 “cherry” 6.0 “apple” 8.5 zlend

跳表编码的有序集合对象使用zset结构作为底层实现.一个zset结构同时包含一个字典和一个跳跃表:

1
2
3
4
typedef struct zset {
  zskiplist *zsl;
  dict *dict;
} zset;

理论上有序集合可以单独使用字典或者跳表
如果单独使用字典实现有序集合,那么虽然查找成员的复杂度为O(1),但是字典是无序的,所以每次执行范围操作就会对所有元素进行排序,至少需要O(NlogN),以及额外的O(N)的内存空间.
如果使用跳表来实现有序集合,那么查找分值的操作将从O(1)上升为O(LogN).

实际中,字典和跳表会共享元素的成员和分值,不会造成数据重复

类型转换

  1. 有序集合保存的数量小于128
  2. 有序集合保存的所有元素成员长度都小于64字节
    不能满足以上两个条件的有序集合对象将使用skiplist编码
    1
    2
    zset-max-ziplist-entries
    zset-max-ziplist-value