haxianhe's blog

Redis之数据类型

字数统计: 3k阅读时长: 12 min
2020/05/06 Share

数据类型

Redis 的数据类型有5种,分别是:字符串、列表、哈希表、集合、有序集合。

Redis 的编码(底层实现)有8种,分别是:long 类型的整数、embstr 编码的简单动态字符串、简单动态字符串、字典、双端链表、压缩列表、整数集合、跳跃表和字典。

字符串

字符串对象的编码可以是 int、raw 或者 embstr。

如果一个字符串对象保存的是整数值,并且这个整数值可以用 long 类型来表示,那么字符串对象会将整数值保存在字符串对象结构的 ptr 属性里面(将 void* 转换成 long),并将字符串对象的编码设置为 int。

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

如果字符串对象保存的是一个字符串值,并且这个字符串值的长度小于等于39字节,那么字符串对象将使用 embstr 编码的方式来保存这个字符串值。

1
2
3
4
5
6
7
8
> set hello world
OK
> get hello
"world"
> del hello
(integer) 1
> get hello
(nil)
列表

列表对象的编码可以是 ziplist 或者 linkedlist。

ziplist 编码的列表对象使用压缩列表作为底层实现,每个压缩列表节点保存了一个列表元素。

linkedlist 编码的列表对象使用双端链表作为底层实现,每个双端链表节点都保存了一个字符串对象,而每个字符串对象都保存了一个列表元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
> rpush list-key item
(integer) 1
> rpush list-key item2
(integer) 2
> rpush list-key item
(integer) 3

> lrange list-key 0 -1
1) "item"
2) "item2"
3) "item"

> lindex list-key 1
"item2"

> lpop list-key
"item"

> lrange list-key 0 -1
1) "item2"
2) "item"
集合

集合对象的编码可以是 intset 或者 hashtable。

intset 编码的集合对象使用整数集合作为底层实现。

hashtable 编码的集合对象使用字典作为底层实现,字典的每个键都是一个字符串对象,每个字符串对象包含了一个集合元素,而字典的值则全部被设置为 NULL。

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
> sadd set-key item
(integer) 1
> sadd set-key item2
(integer) 1
> sadd set-key item3
(integer) 1
> sadd set-key item
(integer) 0

> smembers set-key
1) "item"
2) "item2"
3) "item3"

> sismember set-key item4
(integer) 0
> sismember set-key item
(integer) 1

> srem set-key item2
(integer) 1
> srem set-key item2
(integer) 0

> smembers set-key
1) "item"
2) "item3"
哈希

哈希对象的编码可以是 ziplist 或者 hashtable。

ziplist 编码的哈希对象使用压缩列表作为底层实现,每当有新的健值对要加入到哈希对象时,程序会先将保存了键的压缩列表节点推入到压缩列表表尾,然后再将保存了值的压缩列表节点推入到压缩列表表尾。

hashtable 编码的哈希对象使用字典作为底层实现,哈希对象中的每个键值对都适用一个字典键值对来保存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
> hset hash-key sub-key1 value1
(integer) 1
> hset hash-key sub-key2 value2
(integer) 1
> hset hash-key sub-key1 value1
(integer) 0

> hgetall hash-key
1) "sub-key1"
2) "value1"
3) "sub-key2"
4) "value2"

> hdel hash-key sub-key2
(integer) 1
> hdel hash-key sub-key2
(integer) 0

> hget hash-key sub-key1
"value1"

> hgetall hash-key
1) "sub-key1"
2) "value1"
有序集合

有序集合对象的编码可以是 ziplist 或者 skiplist。

ziplist 编码的有序集合对象使用压缩列表作为底层实现,每个集合元素使用两个挨在一起的压缩列表节点来保存,第一个节点保存元素的成员,第二个节点保存元素的分值。

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

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
> zadd zset-key 728 member1
(integer) 1
> zadd zset-key 982 member0
(integer) 1
> zadd zset-key 982 member0
(integer) 0

> zrange zset-key 0 -1 withscores
1) "member1"
2) "728"
3) "member0"
4) "982"

> zrangebyscore zset-key 0 800 withscores
1) "member1"
2) "728"

> zrem zset-key member1
(integer) 1
> zrem zset-key member1
(integer) 0

> zrange zset-key 0 -1 withscores
1) "member0"
2) "982"
底层数据结构

简单动态字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
struct sdshdr {

// 记录 buf 数组中已使用字节的数量
// 等于 SDS 所保存字符串的长度
int len;

// 记录 buf 数组中未使用字节的数量
int free;

// 字节数组,用于保存字符串
char buf[];

};

图 2-1 展示了一个 SDS 示例:

  • free 属性的值为 0 , 表示这个 SDS 没有分配任何未使用空间。
  • len 属性的值为 5 , 表示这个 SDS 保存了一个五字节长的字符串。
  • buf 属性是一个 char 类型的数组, 数组的前五个字节分别保存了 ‘R’ 、 ‘e’ 、 ‘d’ 、 ‘i’ 、 ‘s’ 五个字符, 而最后一个字节则保存了空字符 ‘\0’ 。

链表

每个链表节点使用一个 adlist.h/listNode 结构来表示:

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

// 前置节点
struct listNode *prev;

// 后置节点
struct listNode *next;

// 节点的值
void *value;

} listNode;

多个 listNode 可以通过 prev 和 next 指针组成双端链表, 如图 3-1 所示。

Redis 的链表实现的特性可以总结如下:

  • 双端: 链表节点带有 prev 和 next 指针, 获取某个节点的前置节点和后置节点的复杂度都是 O(1) 。
  • 无环: 表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL , 对链表的访问以 NULL 为终点。
  • 带表头指针和表尾指针: 通过 list 结构的 head 指针和 tail 指针, 程序获取链表的表头节点和表尾节点的复杂度为 O(1) 。
  • 带链表长度计数器: 程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数, 程序获取链表中节点数量的复杂度为 O(1) 。
  • 多态: 链表节点使用 void* 指针来保存节点值, 并且可以通过 list 结构的 dup 、 free 、 match 三个属性为节点值设置类型特定函数, 所以链表可以用于保存各种不同类型的值。

字典

dictht 是一个散列表结构,使用拉链法解决哈希冲突。

1
2
3
4
5
6
7
8
/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
1
2
3
4
5
6
7
8
9
10
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;

Redis 的字典 dict 中包含两个哈希表 dictht,这是为了方便进行 rehash 操作。在扩容时,将其中一个 dictht 上的键值对 rehash 到另一个 dictht 上面,完成之后释放空间并交换两个 dictht 的角色。

1
2
3
4
5
6
7
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;

rehash 操作不是一次性完成,而是采用渐进方式,这是为了避免一次性执行过多的 rehash 操作给服务器带来过大的负担。

渐进式 rehash 通过记录 dict 的 rehashidx 完成,它从 0 开始,然后每执行一次 rehash 都会递增。例如在一次 rehash 中,要把 dict[0] rehash 到 dict[1],这一次会把 dict[0] 上 table[rehashidx] 的键值对 rehash 到 dict[1] 上,dict[0] 的 table[rehashidx] 指向 null,并令 rehashidx++。

在 rehash 期间,每次对字典执行添加、删除、查找或者更新操作时,都会执行一次渐进式 rehash。

采用渐进式 rehash 会导致字典中的数据分散在两个 dictht 上,因此对字典的查找操作也需要到对应的 dictht 去执行。

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/* 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.
*
* Note that a rehashing step consists in moving a bucket (that may have more
* than one key as we use chaining) from the old to the new hash table, however
* since part of the hash table may be composed of empty spaces, it is not
* guaranteed that this function will rehash even a single bucket, since it
* will visit at max N*10 empty buckets in total, otherwise the amount of
* work it does would be unbound and the function may block for a long time. */
int dictRehash(dict *d, int n) {
int empty_visits = n * 10; /* Max number of empty buckets to visit. */
if (!dictIsRehashing(d)) return 0;

while (n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;

/* Note that rehashidx can't overflow as we are sure there are more
* elements because ht[0].used != 0 */
assert(d->ht[0].size > (unsigned long) d->rehashidx);
while (d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
de = d->ht[0].table[d->rehashidx];
/* Move all the keys in this bucket from the old to the new hash HT */
while (de) {
uint64_t h;

nextde = de->next;
/* Get the index in the new hash table */
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = nextde;
}
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}

/* Check if we already rehashed the whole table... */
if (d->ht[0].used == 0) {
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}

/* More to rehash... */
return 1;
}

跳跃表

是有序集合的底层实现之一。

跳跃表是基于多指针有序链表实现的,可以看成多个有序链表。

在查找时,从上层指针开始查找,找到对应的区间之后再到下一层去查找。下图演示了查找 22 的过程。

与红黑树等平衡树相比,跳跃表具有以下优点:

  • 插入速度非常快速,因为不需要进行旋转等操作来维护平衡性;
  • 更容易实现;
  • 支持无锁操作。

整数集合

整数集合(intset)是 Redis 用于保存整数值的集合抽象数据结构, 它可以保存类型为 int16_t 、 int32_t 或者 int64_t 的整数值, 并且保证集合中不会出现重复元素。

每个 intset.h/intset 结构表示一个整数集合:

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

// 编码方式
uint32_t encoding;

// 集合包含的元素数量
uint32_t length;

// 保存元素的数组
int8_t contents[];

} intset;

图 6-1 展示了一个整数集合示例:

  • encoding 属性的值为 INTSET_ENC_INT16 , 表示整数集合的底层实现为 int16_t 类型的数组, 而集合保存的都是 int16_t 类型的整数值。
  • length 属性的值为 5 , 表示整数集合包含五个元素。
  • contents 数组按从小到大的顺序保存着集合中的五个元素。
    因为每个集合元素都是 int16_t 类型的整数值, 所以 contents 数组的大小等于 sizeof(int16_t) 5 = 16 5 = 80 位。

压缩列表

压缩列表是 Redis 为了节约内存而开发的, 由一系列特殊编码的连续内存块组成的顺序型(sequential)数据结构。

一个压缩列表可以包含任意多个节点(entry), 每个节点可以保存一个字节数组或者一个整数值。

图 7-1 展示了压缩列表的各个组成部分, 表 7-1 则记录了各个组成部分的类型、长度、以及用途。

图 7-2 展示了一个压缩列表示例:

  • 列表 zlbytes 属性的值为 0x50 (十进制 80), 表示压缩列表的总长为 80 字节。
  • 列表 zltail 属性的值为 0x3c (十进制 60), 这表示如果我们有一个指向压缩列表起始地址的指针 p , 那么只要用指针 p 加上偏移量 60 , 就可以计算出表尾节点 entry3 的地址。
  • 列表 zllen 属性的值为 0x3 (十进制 3), 表示压缩列表包含三个节点。

CATALOG
  1. 1. 数据类型
    1. 1.1. 字符串
    2. 1.2. 列表
    3. 1.3. 集合
    4. 1.4. 哈希
    5. 1.5. 有序集合
    6. 1.6. 底层数据结构