面向自由编程

redis系列：对象大总结（字符串，列表，哈希，集合，有序集合底层结构）

Posted on Edited on In
Symbols count in article: 2.6k Reading time ≈ 2 mins.

对象类型和编码

在redis中，并没有使用之前学到的数据结构来直接构建数据库，而是基于这些数据结构构建了一个对象系统，这个系统包含了字符串对象，列表对象，哈希对象，集合对象和有序集合对象五种类型。

在redis中，对象的数据结构如下：

1
2
3
4
5
6
7
8
9
10
11
/* The actual Redis Object */
#define REDIS_LRU_BITS 24
#define REDIS_LRU_CLOCK_MAX ((1<<REDIS_LRU_BITS)-1) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    int refcount;
    void *ptr;
} robj;

对象宏定义如下：

对象的ptr指针指向了这个对象的底层数据结构，这些数据结构由对象的encoding属性决定：

不同类型的编码的对象可能有多种形式：

字符串对象

字符串的编码可以是int，raw，embstr。

  • 若为整数并且可用long表示，那么编码设置为int，（void）转为（int）类型。
  • 若为字符串类型，且长度大于32字节，那么用动态字符串存储，编码设置为raw，调用两次内存分配。
  • 如果为字符串类型且长度小于32字节，那么用embstr编码表示，与上面不同的是embstr直接调用一次内存分配，将redisObject和embstr存储在一起。

编码转换

  1. int编码的字符串执行append命令追加一个非整数值或者长度超过限制，那么int将变为raw类型。
  2. embstr为可读类型，也就是不能执行任何更改操作，因此要更改必须转为raw类型。一旦对embstr更改将立即编程raw类型。

字符串命令的实现

列表对象

列表对象通过ziplist或者linkedlist编码实现。
如果是压缩链表，在内存中的布局如下图所示：

如果是双向队列，如下图所示：

链表中存储的是动态字符串对象，字符串对象是Redis五种对象中唯一一种会被其他四种类型对象嵌套的对象。

编码转换

满足下面两个条件，使用ziplist编码：

  • 列表对象保存的所有字符串元素长度小于64字节
  • 列表对象保存的元素数量小于512个
    除此之外使用linkedlist编码。

列表命令实现

哈希对象

哈希对象通过ziplist或者hashtable编码实现。

  • ziplist编码的哈希对象使用压缩链表作为底层实现
    新键值对加入哈希对象是，会先将保存了键的压缩链表节点压到表尾，在将保存了值的节点压到表尾。如下图所示：
  • hashtable编码使用字典作为底层实现
    哈希对象每个键值对使用一个字典键值对来保存。每个键和值都是一个字符串对象。如下图所示：

编码转换

满足下面两个条件使用ziplist编码：

  • 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节。
  • 键值对数量小于512个。

除此之外使用字典存储。

命令的实现

集合对象

集合对象使用intset或者hashtable编码。

  • intset使用整数集合作为底层实现。
  • hashtable使用字典作为底层实现。

编码转换

集合对象满足下面两个条件使用intset编码：

  • 集合对象保存的所有元素都是整数。
  • 集合对象保存的元素数量不超过512个。

除此之外使用hashtable实现。

集合命令的实现

有序集合

有序结合使用ziplist或者skiplist编码。

  • ziplist使用压缩链表作为底层实现。每个集合元素使用两个紧挨在一起的压缩链表节点表示，第一个是元素成员，第二个是元素的分值。
  • skiplist使用zset作为底层实现。

zset

zset有一个字典和一个跳表组成：

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

其中zsl跳表按照分值从小到大保存了所有集合元素，每个跳表节点都保存了一个集合元素，具体的：跳表的obj指针指向元素，score属性保存元素分值。通过跳表可以对有序集合进行范围型操作，比如ZRANK.ZRANGE等命令。dict字典结构为有序结合创建了一个从成员到分值的映射，键保存成员，值保存分值，因此通过字典可以O(1)地查找元素的分值。

为什么要用两个结构来实现zset？

理论上可以使用其中任何一个来实现，但是只使用字典的话，执行ZRANK,ZRANGE命令就需要O(NlogN)的复杂度，单使用跳表的话，查找复杂度会是O(logN)。并且两种数据结构都使用指针来避免了额外的内存开销。

上图所示为了简化，stingObject和score分开表示，但是在实际的实现中，指针都是指向同一块内存区域。

编码转换

同时满足下面两个条件使用压缩链表，否则使用zset：

  • 集合保存的元素数量小于128个
  • 保存的元素成员的长度都小于64字节

命令的实现

内存回收、对象共享和空转时长

  • 内存回收

在对象结构体中

1
2
3
4
5
6
7
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    int refcount;
    void *ptr;
} robj;

有一个refcount字段用来记录对象的引用计数信息。对象的整个生命周期可以分为创建对象，操作对象，释放对象三个阶段。

  • 对象共享

对象的引用计数还能带来对象共享的作用：如果键A创建”100”作为值对象，此时键B如果需要创建一个同样的值对象，就可以直接在A的值对象的引用计数上加1。
redis不共享包含字符串的对象，原因在于每次共享需要比较对象是否完全相同，如果是整数，复杂度为O(1)，如果是字符串，复杂度是O（N），如果是包含了多个值的对象，复杂度会上升为O(N^2)。

  • 空转时长

另外结构体中的lru记录了当前时间减去值对象最后一次被访问的时间，当程序内存超过限制，会优先清理长时间没有访问的元素。