Redis 数据结构

发表于 更新于 分类于

基本数据结构

String

特点

  1. 最大能存储 512MB == 536870912 B(byte) ；
  2. 二进制安全，在传输数据的时候，能保证二进制数据的信息安全，也就是不会被篡改、破译；如果被攻击，能够及时检测出来
  3. 能存储各种类型的数据，字符串、数字，以至对象（通过json序列化）、位图等。

基本使用

容量：512M

1
2
set aa 'str'
get aa

操作总结

1
2
3
4
5
6
set/get/del/append/strlen key
incr/decr/incrby/decrby key
getrange key start end/setrange key offset value（从offset处开始读取/覆盖）
setex key seconds value(set with expire插入key的同时设置过期时间)/setnx key value(set if not exists如果已存在则直接返回0)
mset/mget/msetnx key value {key value}（设置/读取多个key的值，msetnx比较特殊，要么都成功，要么一个都不执行，可以用来设置一个对象的多个不同字段）
getset key(设置并返回key对应的旧值，可以用于计数器的重置)

常见应用

字符串、jpg图片、序列化对象、一些复杂的计数功能的缓存

Hash

存储 String 类型键值对的映射表、对象

基本使用方法

容量：每个 Hash 可存 2^32 - 1（约 40 亿）个键值对

1
2
3
hmset user username 'name' password '123456' # 定义一个有两个元素的Hash表
hgetall user # 获取user中所有key和value
hget user username # 获取user中key为username的value

常见应用

单点登录（存<CookieId, 用户信息>，设置 30 分钟为缓存过期时间，能很好地模拟出类似 Session 的效果）。

List

String列表

基本使用方法

容量：每个 List 可存 2^32 - 1 个元素

1
2
3
lpush ball basketball soccer # 按顺序从左侧压入，如果ball列表不存在则创建
rpush ball volleyball
lrange 0 1 # 获取索引从0到1的值

操作总结

1
2
3
4
5
6
7
8
9
lpush/rpush/lrange
lpop/rpop
lindex
llen
lrem key
ltrim key
rpoplpush
lset key index value
linsert key before/after val1 val2

常见应用

简单的消息队列
基于 Redis 的分页功能（利用 lrang 命令，性能极佳，用户体验好）

Set

字符串的无序集合，使用 Hash 实现（key 和 value 相同的 Hash）

基本使用方法

容量：2^32 - 1 个成员

1
2
sadd myset li1 # 向集合myset中添加一个元素li1，若不存在则创建
smembers myset

常见应用

全局去重（为什么不用 JDK 自带的 Set 去重？因为我们的系统一般都是集群部署）
计算共同喜好、全部喜好、自己独有的喜好等功能（交集、并集、差集）

ZSet

字符串的有序集合，每个元素都关联一个 double 类型的权重参数 score，集合中的元素能够按 score 进行排列。

基本使用方法

容量：2^32 - 1 个成员

1
2
zadd myzset 0 abc
zrangebyscore myzset 0 10

常见应用

排行榜
取 Top N 操作
延时任务（https://www.cnblogs.com/rjzheng/p/8972725.html）
范围查找

原理

实现上类似于 Java 的 SortedSet 和 HashMap 的结合体，value 唯一（Set 结构的特点），每个 value 一个 score 代表该 value 的排序权重。
zset 内部是使用一种叫做跳跃列表的结构实现的。

Redis 数据结构的实现

数据结构的声明和实现

Redis数据结构及其实现
Redis 中的 set、zset 等结构在 Redis 中并不是由一个单独的数据结构实现的，而是会根据情况有所变化。

set

set和Java中的HashSet有点像，它本身是HashMap的封装，key是集合中的对象，而value直接用NULL代替。
但是注意一些特殊情况：

  • 创建集合对象时，如果发现集合内的元素可以使用整数（longlong）编码，则创建一个intset而不是dict；
  • 之前是intset编码的情况下，插入的新元素如果是非整数的，那么集合会被重新转换成dict编码的；或者插入的元素数量达到了阈值（512），也会自动转换成dict。
    创建代码见：t_set.c/setTypeCreate()

zset

zset同样有两种形态：ziplist编码和skiplist编码。

  • 按ziplist编码的情况下：
    zset本身就是个ziplist对象。
  • 按skiplist编码的情况下：
    zset的集合功能是通过dict实现的，这部分和set并无区别；
    zset的有序性是通过skiplist实现的，skiplist按分值排序成员，支持平均复杂度为O(logN)的按分值定位成员的操作。

执行zadd命令代码：t_zset.c/zaddGenericCommand()
创建zset对象：object.c/createZsetZiplistObject()、object.c/createZsetObject()

SDS(Simple Dynamic String)

Redis 中的动态数组有以下特点：

  • 可动态扩展内存。sds 表示的字符串其内容可以修改，也可以追加。在很多语言中字符串会分为 mutable 和 immutable 两种，显然 sds 属于 mutable 类型的。
  • 减少修改字符串的内存重新分配次数
    C语言由于不记录字符串的长度，所以如果要修改字符串，必须要重新分配内存（先释放再申请），因为如果没有重新分配，字符串长度增大时会造成内存缓冲区溢出，字符串长度减小时会造成内存泄露。
    而对于SDS，由于len属性和free属性的存在，对于修改字符串SDS实现了空间预分配和惰性空间释放两种策略：
    1、空间预分配：对字符串进行空间扩展的时候，扩展的内存比实际需要的多，这样可以减少连续执行字符串增长操作所需的内存重分配次数。
    2、惰性空间释放：对字符串进行缩短操作时，程序不立即使用内存重新分配来回收缩短后多余的字节，而是使用 free 属性将这些字节的数量记录下来，等待后续使用。（当然SDS也提供了相应的API，当我们有需要时，也可以手动释放这些未使用的空间。）
  • 二进制安全（Binary Safe）。sds 能存储任意二进制数据，而不仅仅是可打印字符。
  • 与传统的 C 语言字符串类型兼容。
1
2
3
4
5
6
struct SDS<T> {
  T capacity; // 数组容量
  T len; // 数组当前长度
  byte flags; // 特殊标识位，不理睬它
  byte[] content; // 数组内容
}

下面的函数将 t 数组拷贝到 s 中，如果长度不够则需要进行扩容：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* Append the specified binary-safe string pointed by 't' of 'len' bytes to the
 * end of the specified sds string 's'.
 *
 * After the call, the passed sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */
sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s);  // 原字符串长度

    // 按需调整空间，如果 capacity 不够容纳追加的内容，就会重新分配字节数组并复制原字符串的内容到新数组中
    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL; // 内存不足
    memcpy(s+curlen, t, len);  // 追加目标字符串的内容到字节数组中
    sdssetlen(s, curlen+len); // 设置追加后的长度值
    s[curlen+len] = '\0'; // 让字符串以\0 结尾，便于调试打印，还可以直接使用 glibc 的字符串函数进行操作
    return s;
}

SDS 有 embstr 和 raw 两种存储结构，它们的区别是：

  1. 内存分配上：
    embstr 调用 1 次 malloc, 因此 redisObject 和 SDS 内存是连续分配的；
    raw 需要调用 2 次 malloc, 因此 redisObject 和 SDS 内存不连续分配
  2. 使用上:
    embstr 整体 64 byte, 正好和cpu cache line 64byte 一样, 可以更好的使用缓存, 效率更高

quicklist

Redis 早期版本存储 list 数据结构采用（元素少时 ziplist、多时 linkedlist ）的方案，但是：

  1. 链表的附加空间太高，prev 和 next 指针就要占去 16 个字节（64 位系统）；
  2. 链表每个节点都是单独分配，会加剧内存的碎片化。

因此在之后的版本中转换为了 quicklist 存储。
quicklist 是 ziplist 和 linkedlist 的混合体，它将 linkedlist 按段切分，每一段使用 ziplist 来紧凑存储，多个 ziplist 之间使用双向指针串接起来。
Redis-quicklist结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct ziplist {
    ...
}
struct ziplist_compressed {
    int32 size;
    byte[] compressed_data;
}
struct quicklistNode {
    quicklistNode* prev;
    quicklistNode* next;
    ziplist* zl; // 指向压缩列表
    int32 size; // ziplist 的字节总数
    int16 count; // ziplist 中的元素数量
    int2 encoding; // 存储形式 2bit，原生字节数组还是 LZF 压缩存储
    ...
}
struct quicklist {
    quicklistNode* head;
    quicklistNode* tail;
    long count; // 元素总数
    int nodes; // ziplist 节点的个数
    int compressDepth; // LZF 算法压缩深度
    ...
}

ziplist

ziplist 是一种压缩存储的数组结构，当 Redis 中的集合数据结构很小，则它会使用这种紧凑的存储形式存储，元素之间紧挨着存储，查找就是对数组进行遍历找到目标对象。

  • zset 和 hash 容器在元素个数较少时会采用 ziplist 存储。当存储的对象数量小于 512 且所有 entry 的 value 值长度小于 64，采用 ziplist 存储，否则转为采用 hashtable 存储。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    import redis
    client = redis.StrictRedis()
    client.delete("hello")
    for i in range(512):
        client.hset("hello", str(i), str(i))
    print client.object("encoding", "hello")
    client.hset("hello", "512", "512")
    # 或者插入一个长度为65的值也能起到转化的作用
    print client.object("encoding", "hello")

可以上服务器上使用debug object命令验证数据结构的类型：

1
2
3
4
> zadd hgc_test 1.0 go 2.0 python 2.0 java
...
> debug object hgc_test
Value at:0x7f73c6d673a0 refcount:1 encoding:ziplist serializedlength:36 lru:1381596 lru_seconds_idle:77

结构

Redis-ziplist结构

1
2
3
4
5
6
7
8
9
10
11
12
struct ziplist<T> {
    int32 zlbytes; // 整个压缩列表占用字节数
    int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
    int16 zllength; // 元素个数
    T[] entries; // 元素内容列表，挨个挨个紧凑存储
    int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
}
struct entry {
    int<var> prevlen; // 前一个 entry 的字节长度
    int<var> encoding; // 元素类型编码
    optional byte[] content; // 元素内容
}
  • zltail_offset 字段可以快速定位到 ziplist 中的最后一个节点，可以用于倒序遍历，entry 中的 prevlen 表示前一个 entry 的字节长度，可以用于倒序遍历时找到下一个元素的位置；
  • encoding 记录编码类型，ziplist 利用该字段决定后面的 content 内容的形式，比如用00xxxxxx表示最大长度为 63 的短字符串，01xxxxxx xxxxxxxx表示中等长度的字符串；

插入

ziplist 是紧凑存储的，没有冗余空间，因此插入一个新元素就需要调用 realloc 重新分配内存空间，并将之前的内容一次性拷贝到新的内存空间中。
重新分配空间是比较耗时的，因此 ziplist 不适合存储大量数据。

更新/删除

修改或删除一个元素后其后一个位置的元素中的 prevlen 也需要级联更新，prevlen 字段又是变长的，所以可能会导致连锁反应。

ziplist vs dict

为什么 hash 结构中会采用 ziplist 而不是 dict，主要原因如下：

  1. 数据量小时，ziplist 的速度也很快；
  2. 数据量大时，ziplist 在每次插入或修改时引发的 realloc 操作会有更大的概率造成内存拷贝，从而降低性能，而且数据项过多的时候，在 ziplist 上查找指定数据项的性能会变得很低，因为在 ziplist 上的查找需要进行遍历。

dict（字典）

dict 是 Redis 中使用最广泛的数据结构：

  1. hash 结构的数据会用到字典；
  2. 整个 Redis 数据库的所有 key 和 value 也组成了一个全局字典；
  3. 带过期时间的 key 集合也是一个字典；
  4. set 结构的底层实现也是字典，只是所有 value 都是 NULL；
  5. zset 集合中存储 value 和 score 值的映射关系也是通过 dict 结构实现的。
1
2
3
4
5
6
7
8
9
10
struct RedisDb {
    dict* dict; // all keys  key=>value
    dict* expires; // all expired keys key=>long(timestamp)
    ...
}

struct dict {
    ...
    dictht ht[2];
}
1
2
3
4
struct zset {
    dict *dict; // all values  value=>score
    zskiplist *zsl;
}

hashtable

dict 中的 hashtable 结构和 Java 中的 HashMap 类似，使用一个数组来保存所有的哈希桶，通过siphash函数来将 key 散列到数组中的某个桶上，每个哈希桶都是一个链表，也就是说如果发生哈希冲突，则将新元素直接插入到桶的头部。

1
2
3
4
5
6
7
8
9
10
11
struct dictEntry {
    void* key;
    void* val;
    dictEntry* next; // 链接下一个 entry
}
struct dictht {
    dictEntry** table; // 二维
    long size; // 第一维数组的长度
    long used; // hash 表中的元素个数
    ...
}

扩容：渐进式 rehash

正常情况下，当 hashtable 中元素的个数等于第一维数组的长度时、来了一个新增/修改/删除操作，就会触发扩容，扩容的新数组是原数组大小的 2 倍。

存在一个特殊情况：如果 Redis 正在做 bgsave，为了减少内存页的过多分离 (Copy On Write)，Redis 尽量不去扩容 (dict_can_resize)，但是如果 hash 表已经非常满了，元素的个数已经达到了第一维数组长度的 5 倍 (dict_force_resize_ratio)，说明 hash 表已经过于拥挤了，这个时候就会强制扩容。

Redis-dict扩容rehash
一般情况下 dict 中只有一个 hashtable 有值，但是在扩容时会分配另一个新的 hashtable，然后执行渐进式的数据迁移，避免一次性对所有 key 执行 rehash，而是将 rehash 操作分散到了对 dict 的各个增删改查操作中去了。

  1. 在扩容过程中，如果有新增元素，则该元素会被同时添加到新 hashtable 中；
  2. 查询、删除、修改操作中，会先查询旧 hashtable，若存在则迁移这个 key 所在的桶并返回元素，若不存在则到新 hashtable 中查找元素。
  3. 有一个异步线程执行定时任务对字典主动迁移。

dict 之所以这样设计，是为了避免 rehash 期间单个请求的响应时间剧烈增加。
当旧 hashtable 中无元素时，即代表迁移完毕，这时会将新旧 hashtable 的指针交换，旧的会被删除，而新的则取而代之。

缩容

当 hash 表因为元素的逐渐删除变得越来越稀疏时，Redis 会对 hash 表进行缩容来减少 hash 表的第一维数组空间占用。缩容的条件是元素个数低于数组长度的 10%。
缩容不会考虑 Redis 是否正在做 bgsave，因为 COW 的特性是当内存页上的数据被修改时会复制一页做修改，如果删除操作并不会触发删除内存页的数据，操作系统回收内存机制导致的。

全局哈希表

get a和llen b中的a和b是不同数据结构的对象，他们统统被存储在一个叫全局哈希表的地方。
哈希表中的每个哈希桶存储的不是值本身，而是指向它们的指针。
Redis中的全局哈希表
代码定义在：redis.h/redisDb

缺点：

  1. 过多的哈希冲突容易产生过长的哈希桶（哈希冲突链）。
    为了减少这个问题产生的影响，需要对哈希表进行rehash操作，这个rehash操作和dict数据结构的rehash原理是一样的。

    全局哈希表实际上就是dict，可以看源码中的定义。

优点：

  1. 合适的散列函数和扩容机制可以保证O(1)的操作复杂度。

skiplist

zset 中除了 dict（字典）外，还会用一个 skiplist 来提供按score排序的要求，以实现指定 score 的范围来获取 value 列表的功能。

Redis-skiplist结构

1
2
3
4
5
6
7
8
9
10
11
12
struct zslnode {
  string value;
  double score;
  zslnode*[] forwards;  // 多层连接指针
  zslnode* backward;  // 回溯指针
}

struct zsl {
  zslnode* header; // 跳跃列表头指针
  int maxLevel; // 跳跃列表当前的最高层
  map<string, zslnode*> ht; // hash 结构的所有键值对
}
  • 各层均为一个有序的链表结构；
  • 层数越大，节点越少；
  • 有一个 header 节点作为哨兵，value=null，score=Double.MIN_VALUE。

插入

插入时会先自顶向下找到新节点在跳表中底层的插入位置，插入每一层时都有概率晋升到更高一层，在 Redis 中是 25%。

删除

删除每一层上的对应节点。

更新

如果不影响排序则直接更新，否则会先删除再重新插入。

布隆过滤器

HyperLogLog

布隆过滤器用于实现contains的需求，而 HyperLogLog 主要用于实现count。
同样是一个特别大的位数组，HyperLogLog 将位数组拆分为桶，每个桶是连续的 6 个位，计数时并非单独对某个桶计数，而是：

  • set 操作：计算 key 的散列值，为一个 64 位的数字，前 14 位是桶的位置，桶记录后 50 位中第一个 1 的位置 count，并且count = max(count, oldCount)，即每次记录最大的计数。
  • count 操作：因为是概率算法，每个桶的计数值并不精确，但是所有桶的调和均值非常接近真实的计数值。

pubsub

用于实现轻量级的发布订阅功能。

geohash

QA

使用string还是hash？

当数据量少时，使用hash明显更加节省内存，因为数据少时hash会转成ziplist的结构，而string每个kv都需要一大堆的额外空间存储元数据。

如何使用Redis的数据结构实现统计？

  1. 需要支持集合运算（差集、交集、并集）的场合
    使用set、zset，数据量少时会转成ziplist节省内存。
  2. 需要进行二值统计的场合
    使用bitmap
  3. 需要大规模统计，且不要求精确统计的场合
    使用HyperLogLog

采用渐进式hash时，如果实例暂时没有接收到新请求，是不是就不会做rehash了？

不会，还有一个定时任务每隔100ms执行rehash，而且每次执行时长不会超过1ms，以免影响其他任务。

参考

  1. redis源码解析