Redis 核心数据结构

一、全局 Hash 表

1.1 全局 Hash 表概述

为了实现从键到值的快速访问，Redis 使用了一个哈希表来保存所有键值对。一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。所以，我们常说，一个哈希表是由多个哈希桶组成的，每个哈希桶中保存了键值对数据。

如果值是集合类型的话，作为数组元素的哈希桶怎么来保存呢？其实，哈希桶中的元素保存的并不是值本身，而是指向具体值的指针。这也就是说，不管值是 String，还是集合类型，哈希桶中的元素都是指向它们的指针。

可以看到，哈希桶中的 entry 元素中保存了 *key 和 *value 指针，分别指向了实际的键和值，这样一来，即使值是一个集合，也可以通过 *value 指针被查找到。

因为这个哈希表保存了所有的键值对，所以，我也把它称为全局哈希表。哈希表的最大好处很明显，就是让我们可以用 O(1) 的时间复杂度来快速查找到键值对——我们只需要计算键的哈希值，就可以知道它所对应的哈希桶位置，然后就可以访问相应的 entry 元素。

你看，这个查找过程主要依赖于哈希计算，和数据量的多少并没有直接关系。也就是说，不管哈希表里有 10 万个键还是 100 万个键，我们只需要一次计算就能找到相应的键。

但是，如果你只是了解了哈希表的 O(1) 复杂度和快速查找特性，那么，当你往 Redis 中写入大量数据后，就可能发现操作有时候会突然变慢了。这其实是因为你忽略了一个潜在的风险点，那就是哈希表的冲突问题和 rehash 可能带来的操作阻塞。

1.2 哈希冲突与链式哈希

当你往哈希表中写入更多数据时，哈希冲突是不可避免的问题。这里的哈希冲突，也就是指，两个 key 的哈希值和哈希桶计算对应关系时，正好落在了同一个哈希桶中。毕竟，哈希桶的个数通常要少于 key 的数量，这也就是说，难免会有一些 key 的哈希值对应到了同一个哈希桶中。

Redis 解决哈希冲突的方式，就是链式哈希。链式哈希也很容易理解，就是指同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接。

但是，这里依然存在一个问题，哈希冲突链上的元素只能通过指针逐一查找再操作。如果哈希表里写入的数据越来越多，哈希冲突可能也会越来越多，这就会导致某些哈希冲突链过长，进而导致这个链上的元素查找耗时长，效率降低。对于追求”快”的 Redis 来说，这是不太能接受的。

所以，Redis 会对哈希表做 rehash 操作。rehash 也就是增加现有的哈希桶数量，让逐渐增多的 entry 元素能在更多的桶之间分散保存，减少单个桶中的元素数量，从而减少单个桶中的冲突。

1.3 渐进式 Rehash

1.3.1 Rehash 基本流程

为了使 rehash 操作更高效，Redis 默认使用了两个全局哈希表：哈希表 1 和哈希表 2。一开始，当你刚插入数据时，默认使用哈希表 1，此时的哈希表 2 并没有被分配空间。随着数据逐步增多，Redis 开始执行 rehash，这个过程分为三步：

  1. 给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍
  2. 把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中
  3. 释放哈希表 1 的空间

到此，我们就可以从哈希表 1 切换到哈希表 2，用增大的哈希表 2 保存更多数据，而原来的哈希表 1 留作下一次 rehash 扩容备用。

1.3.2 渐进式 Rehash 机制

这个过程看似简单，但是第二步涉及大量的数据拷贝，如果一次性把哈希表 1 中的数据都迁移完，会造成 Redis 线程阻塞，无法服务其他请求。此时，Redis 就无法快速访问数据了。为了避免这个问题，Redis 采用了渐进式 rehash。

简单来说就是在第二步拷贝数据时，Redis 仍然正常处理客户端请求，每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries。

这样就巧妙地把一次性大量拷贝的开销，分摊到了多次处理请求的过程中，避免了耗时操作，保证了数据的快速访问。

二、Value 的底层结构

2.1 基础数据结构

2.1.1 String 类型

底层实现：SDS（简单动态字符串）

String 类型的底层数据结构实现主要是 SDS（简单动态字符串），SDS 和我们认识的 C 语言的字符串是不一样的：

  1. 二进制安全：SDS 不仅可以保存文本数据，还可以保存二进制数据，因为 SDS 使用 len 属性的值而不是空字符来判断字符串是否结束，是二进制安全的。可以保存的数据的类型更多

  2. O(1) 时间复杂度获取长度：SDS 获取字符串长度的时间复杂度是 O(1)，因为 C 语言的字符串不记录自身长度，所以遍历一遍的时间复杂度是 O(n)，而 SDS 结构中用 len 属性记录了字符串的长度

  3. 安全的 API：Redis 的 SDS API 是安全的，拼接字符串不会造成缓冲区溢出，因为 SDS 在拼接字符串之前会检查 SDS free 空间是否满足要求，如果空间不够会自动扩容

字符串最多可以存多大？

String 是最基本的 key-value 结构，key 是唯一标识，value 是具体的值，value 其实不仅是字符串，也可以是数字（整数或浮点数），value 最多可以容纳的数据长度是 512M。

这个 512M 可以从源码角度分析：

1
2
3
4
5
6
7
static int checkStringLength(client *c, long long size) {
    if (size > 512*1024*1024) {
        addReplyError(c,"string exceeds maximum allowed size (512MB)");
        return C_ERR;
    }
    return C_OK;
}

从设计的角度来看，虽然 Redis 里面有个类型 sdshdr64，len 的类型是 uint64_t，占 8 个字节，但是最大不是 2 的 64 次方。因为为了避免等同于 Redis 最大内存设置的限制造成的问题，Redis 对字符串的长度进行了限制，使其最大长度为 512M。此外，这样的限制也可以避免过多的内存分配和内存复制带来的性能影响。

SDS 底层原理

除了记录实际数据，String 类型还需要额外的内存空间记录数据长度、空间使用等信息，这些信息也叫作元数据。当实际保存的数据较小时，元数据的空间开销就显得比较大了，有点”喧宾夺主”的意思。

当你保存 64 位有符号整数时，String 类型会把它保存为一个 8 字节的 Long 类型整数，这种保存方式通常也叫作 int 编码方式。

但是，当你保存的数据中包含字符时，String 类型就会用简单动态字符串（Simple Dynamic String，SDS）结构体来保存：

  • buf：字节数组，保存实际数据。为了表示字节数组的结束，Redis 会自动在数组最后加一个 “\0”，这就会额外占用 1 个字节的开销
  • len：占 4 个字节，表示 buf 的已用长度
  • alloc：也占 4 个字节，表示 buf 的实际分配长度，一般大于 len

可以看到，在 SDS 中，buf 保存实际数据，而 len 和 alloc 本身其实是 SDS 结构体的额外开销。

另外，对于 String 类型来说，除了 SDS 的额外开销，还有一个来自于 RedisObject 结构体的开销。因为 Redis 的数据类型有很多，而且，不同数据类型都有些相同的元数据要记录（比如最后一次访问的时间、被引用的次数等），所以，Redis 会用一个 RedisObject 结构体来统一记录这些元数据，同时指向实际数据。

一个 RedisObject 包含了 8 字节的元数据和一个 8 字节指针，这个指针再进一步指向具体数据类型的实际数据所在，例如指向 String 类型的 SDS 结构所在的内存地址。

为了节省内存空间，Redis 还对 Long 类型整数和 SDS 的内存布局做了专门的设计：

一方面，当保存的是 Long 类型整数时，RedisObject 中的指针就直接赋值为整数数据了，这样就不用额外的指针再指向整数了，节省了指针的空间开销。

另一方面，当保存的是字符串数据，并且字符串小于等于 44 字节时，RedisObject 中的元数据、指针和 SDS 是一块连续的内存区域，这样就可以避免内存碎片。这种布局方式也被称为 embstr 编码方式。

当然，当字符串大于 44 字节时，SDS 的数据量就开始变多了，Redis 就不再把 SDS 和 RedisObject 布局在一起了，而是会给 SDS 分配独立的空间，并用指针指向 SDS 结构。这种布局方式被称为 raw 编码模式。

embstr 编码详解

embstr 编码将创建字符串对象所需的内存分配次数从 raw 编码的两次降低为一次：

  • 释放 embstr 编码的字符串对象同样只需要调用一次内存释放函数
  • 因为 embstr 编码的字符串对象的所有数据都保存在一块连续的内存里面可以更好的利用 CPU 缓存提升性能

但是 embstr 也有缺点的：如果字符串的长度增加需要重新分配内存时，整个 redisObject 和 sds 都需要重新分配空间，所以 embstr 编码的字符串对象实际上是只读的，redis 没有为 embstr 编码的字符串对象编写任何相应的修改程序。

当我们对 embstr 编码的字符串对象执行任何修改命令（例如 append）时，程序会先将对象的编码从 embstr 转换成 raw，然后再执行修改命令。也就是如果多次修改还是 raw 更好。

为什么是 39 字节和 44 字节界限？

embstr 是一块连续的内存区域，由 redisObject 和 sdshdr 组成。其中 redisObject 占 16 个字节，当 buf 内的字符串长度是 39 时：

1
sdshdr(len 4字节) + sdshdr(free 4字节) + 字符串长度39字节 + 字符串结束符('\0' 1字节) + redisObject 16字节 = 64字节

从 2.4 版本开始，redis 开始使用 jemalloc 内存分配器。这个比 glibc 的 malloc 要好不少，还省内存。在这里可以简单理解，jemalloc 会分配 8，16，32，64 等字节的内存。embstr 最小为 16+8+1=25，虽然可以分配 7 个字节，但是数据一般没这么小。如果设置为 7，那么大多数情况下都不能用这个数据结构了，所以最小分配 64 字节。当字符数小于 39 时，都会分配 64 字节。这个默认 39 就是这样来的。（39+25=64）

Redis 的 embstr 编码方式和 raw 编码方式在 3.0 版本之前是以 39 字节为分界的，也就是说，如果一个字符串值的长度小于等于 39 字节，则按照 embstr 进行编码，否则按照 raw 进行编码。而在 3.2 版本之后，则变成了 44 字节为分界。

Redis 3.2 版本的变化：

原来的 sdshdr 结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:REDIS_LRU_BITS;
    int refcount;
    void *ptr;
} robj;

struct sdshdr {
    unsigned int len;
    unsigned int free;
    char buf[];
};

新的 sdshdr8 结构：

1
2
3
4
5
6
struct sdshdr8 {
    uint8_t len;        // 1字节
    uint8_t alloc;      // 1字节 free = alloc - len
    unsigned char flags; // 1字节 标识SDS的类型
    char buf[];
}

39 → 44 的变化，本质原因只有一个：SDS 头部从 8 字节变成了 3 字节，省下来的 5 字节全让给字符串内容了。

常见内存分配器

作为基础库的 ptmalloc 是最为稳定的内存管理器，无论在什么环境下都能适应，但是分配效率相对较低。GNU Libc 的内存分配器（allocator）—ptmalloc，起源于 Doug Lea 的 malloc。由 Wolfram Gloger 改进得到可以支持多线程。

tcmalloc 针对多核情况有所优化，性能有所提高，但是内存占用稍高，大内存分配容易出现 CPU 飙升，因为 tcmalloc 在内存分配的时候使用自旋锁，在锁冲突严重的时候导致 CPU 飙升。

jemalloc 的内存占用更高，但是在多核多线程下的表现也最为优异。jemalloc 按照内存分配请求的尺寸，分了 small object（例如 1 – 57344B）、large object（例如 57345 – 4MB）、huge object（例如 4MB 以上）。

常见的内存分配器包括普通 malloc、ptmalloc、tcmalloc 和 jemalloc：

  • 普通 malloc：早期单线程模型，也就是 dlmalloc 用的是全局锁/无并发设计
  • ptmalloc：glibc 默认实现，使用 arena + mutex，但是 arena 数量有限，所以支持多线程但锁竞争严重，其实是 ptmalloc = dlmalloc + 多线程改造
  • tcmalloc：针对多核并发优化，使用了自旋锁，但在大内存和高负载下可能导致 CPU 飙升
  • jemalloc：以内存换性能，通过更大的线程缓存、更细粒度的 size class 和延迟回收机制，减少了锁竞争和系统调用次数，但代价是占用更多内存，因此被认为是”用内存换性能”，在多核多线程下表现最稳定，因此被 Redis 采用

RedisObject 底层结构

RedisObject 包括元数据和指针，其中，元数据的一个功能就是用来区分不同的数据类型，指针用来指向具体的数据类型的值。所以，要想开发新数据类型，我们就先来了解下 RedisObject 的元数据和指针。

RedisObject 的内部组成包括了 type、encoding、lru 和 refcount 4 个元数据，以及 1 个 *ptr 指针：

  • type：表示值的类型，涵盖了我们前面学习的五大基本类型
  • encoding：是值的编码方式，用来表示 Redis 中实现各个基本类型的底层数据结构，例如 SDS、压缩列表、哈希表、跳表等
  • lru：记录了这个对象最后一次被访问的时间，用于淘汰过期的键值对
  • refcount：记录了对象的引用计数
  • *ptr：是指向数据的指针

RedisObject 结构借助 *ptr 指针，就可以指向不同的数据类型，例如，*ptr 指向一个 SDS 或一个跳表，就表示键值对中的值是 String 类型或 Sorted Set 类型。

type 和 encoding 的区别：

  • type：表示 Redis 逻辑类型（字符串、列表、集合等），用来区分五大基本类型
  • encoding：表示底层具体实现方式，用于优化不同场景下的数据存储和访问性能

同一个 type 可以有多种 encoding，实现”逻辑类型抽象 + 存储优化策略”的分离。

type 常量 表示内容
REDIS_STRING 字符串
REDIS_LIST 列表
REDIS_SET 集合
REDIS_HASH 哈希
REDIS_ZSET 有序集合

encoding 示例：

  • 字符串可以是 RAW / EMBSTR / INT
  • 列表可以是 ZIPLIST / QUICKLIST
  • 哈希可以是 ZIPLIST / HASHTABLE
  • ZSet 可以是 ZIPLIST / SKIPLIST
  • Set 可以是 INTSET / HASHTABLE

换句话说，type 是抽象逻辑类型，encoding 是底层存储实现。

2.1.2 Hash 类型

在 Redis 7.0 版本之前，Hash 类型的底层数据结构是由压缩列表 ZipList 或哈希表实现的。

如果哈希类型的元素小于 512 个（默认值，可由 hash-max-ziplist-entries 配置），并且所有的值都小于 64 字节（默认值，可由 hash-max-ziplist-value 配置），Redis 会使用压缩列表作为 Hash 的底层数据结构，把 field 和 value 顺序存放，以节省内存，[field1][value1][field2][value2]...，所以一开始查找是 O(N) 的。

不过在 7.0 版本之后，压缩列表的数据结构就被废弃了，交由 listpack 数据结构实现了，但是多了还是哈希表存储。

压缩列表底层

压缩列表实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。和数组不同的是，压缩列表在表头有三个字段 zlbytes、zltail 和 zllen，分别表示：

  • zlbytes：占用内存字节数（避免每次扩容/拷贝都得从头遍历算长度）
  • zltail：最后一个 entry 距离 ziplist 起始地址的偏移（entry 是变长的，你不知道第 N 个从哪开始）
  • zllen：列表中的节点 entry 个数（判断是否需要结构升级 listpack）

压缩列表在表尾还有一个 zlend，表示列表结束。

entry 结构：

entry 本身是个包含三个字段的结构体：

  • prevlen：记录了「前一个节点」的长度，目的是为了实现从后向前遍历
  • encoding：记录了当前节点实际数据的「类型和长度」，类型主要有两种：字符串和整数
  • data：记录了当前节点的实际数据，类型和长度都由 encoding 决定

根据数据大小和类型进行不同的空间大小分配的设计思想。

连锁更新问题：

压缩列表新增某个元素或修改某个元素时，如果空间不够，压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时，可能会导致后续元素的 prevlen 占用空间都发生变化，从而引起「连锁更新」问题（长度变化会影响下一个 prevlen，会导致递归式结构膨胀问题），导致每个元素的空间都要重新分配，造成访问压缩列表性能的下降。

在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了。

正是因为 ziplist 的 prevlen 设计容易产生连锁更新，Redis 后续引入了 listpack，通过去掉 prevlen 字段，从根本上解决了这个问题。

2.1.3 List 类型

在 Redis 3.2 版本之前，List 类型的底层数据结构是由双向链表或压缩列表实现的。

简单的说，如果列表的元素小于 512 个（默认值，可由 list-max-ziplist-entries 配置），且列表每一个元素的值都小于 64 字节（默认值，可由 list-max-ziplist-value 配置），Redis 会使用压缩列表作为 List 底层的数据结构，因为压缩列表都是非常紧凑的数据结构，它比链表占用的内存要更少，而且链表每个节点之间的内存都是不连续的，根据局部性原理，这意味着无法很好利用 CPU 缓存。

如果列表中的元素不满足上面的条件，Redis 会使用双向链表作为 List 类型的底层数据结构。

不过在 Redis 3.2 版本之后，List 的底层数据结构就只由 quicklist 实现了（listpack 作为节点 7.0 之后，之前还是 ziplist 作为节点），替代了双向链表和压缩链表。

跳表原理

有序链表只能逐一查找元素，导致操作起来非常缓慢，于是就出现了跳表。具体来说，跳表在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位。

如果我们要在链表中查找 33 这个元素，只能从头开始遍历链表，查找 6 次，直到找到 33 为止。此时，复杂度是 O(N)，查找效率很低。

为了提高查找速度，我们来增加一级索引：从第一个元素开始，每两个元素选一个出来作为索引。这些索引再通过指针指向原始的链表。例如，从前两个元素中抽取元素 1 作为一级索引，从第三、四个元素中抽取元素 11 作为一级索引。此时，我们只需要 4 次查找就能定位到元素 33 了。

如果我们还想再快，可以再增加二级索引：从一级索引中，再抽取部分元素作为二级索引。例如，从一级索引中抽取 1、27、100 作为二级索引，二级索引指向一级索引。这样，我们只需要 3 次查找，就能定位到元素 33 了。

可以看到，这个查找过程就是在多级索引上跳来跳去，最后定位到元素。这也正好符合”跳”表的叫法。当数据量很大时，跳表的查找复杂度就是 O(logN)。

压缩列表的优化

再来谈谈 quicklist 的实现，quicklistNode 结构体里包含了前一个节点和下一个节点指针，这样每个 quicklistNode 形成了一个双向链表。但是链表节点的元素不再是单纯保存元素值，而是保存了一个压缩列表。

在向 quicklist 添加一个元素的时候，不会像普通的链表那样，直接新建一个链表节点。而是会检查插入位置的压缩列表是否能容纳该元素，如果能容纳就直接保存到 quicklistNode 结构里的压缩列表，如果不能容纳，才会新建一个新的 quicklistNode 结构。

quicklist 会控制 quicklistNode 结构里的压缩列表的大小或者元素个数，来规避潜在的连锁更新的风险，但是这并没有完全解决连锁更新的问题。

listpack 头包含两个属性，分别记录了 listpack 总字节数和元素数量，然后 listpack 末尾也有个结尾标识。listpack 没有压缩列表中记录前一个节点长度的字段了，listpack 只记录当前节点的长度，当我们向 listpack 加入一个新元素的时候，不会影响其他节点的长度字段的变化，从而避免了压缩列表的连锁更新问题。

（listpack 比 ziplist 更像数组了，在 listpack 中，无论是插入、删除还是修改元素（导致节点内存变大或变小），只要当前节点的存储长度发生变化，都可能需要移动后续所有元素的内存位置。这是 listpack 为了彻底解决 ziplist 的连锁更新问题所付出的代价）

ziplist 的连锁更新问题导致后续节点重新分配内存，现在的 listpack 修改节点导致后续节点内存地址偏移量修改，但不是重新分配内存，而且是所有节点内存地址都移动相同的偏移量，在这方面虽然都操作了后续节点，listpack 性能略高！

简单的说，因为结构变化 + 内存移动，ziplist 的 O(N) 连锁更新可能递归、不可控，但是 listpack 只有一次的内存移动，不是不可预测的级联更新。

2.1.4 Set 类型

Set 类型的底层数据结构是由哈希表或整数集合实现的。

如果集合中的元素都是整数且元素个数小于 512 个（默认值，set-maxintset-entries 配置），Redis 使用 intset 整数集合，以连续数组的方式存储，节省内存，因为数组对 CPU 高速缓存支持更友好。

注意为什么是小的时候才会使用数组，因为数组内存分配，要么频繁重新分配内存（性能问题），要么预先过度分配（内存浪费）。

如果 Set 中的元素不满足上面的条件，那么 Redis 会使用哈希表作为 Set 类型的底层数据结构，其中 Set 的 member 存在哈希表的 key 中，value 并不承载实际数据，只是占位，一般为 NULL。

2.1.5 Zset 类型

在 Redis 7.0 版本之前，Zset 的底层数据结构是由压缩列表或跳表实现的。

如果有序集合的元素个数小于 128 个，并且每个元素的值小于 64 字节时，Redis 会使用压缩列表作为 Zset 类型的底层数据结构。

如果集合中的元素不满足上面的条件，Redis 会使用跳表作为 Zset 的底层数据结构。

当然，在 Redis 7.0 之后，压缩列表的数据结构就已经被废弃了，交给 listpack 数据结构来实现了。

因为 Zset 是用来按 score 排序，快速按 rank / score 查找的，所以数据量大了才会使用有序 + 支持快速查找的跳表。

2.2 高级数据结构

2.2.1 GEO 类型

GEO 就非常适合应用在 LBS 服务的场景中，我们主要分析一下 GeoHash 的底层编码。

Redis 采用了业界广泛使用的 GeoHash 编码方法，这个方法的基本原理就是”二分区间，区间编码”。当我们要对一组经纬度进行 GeoHash 编码时，我们要先对经度和纬度分别编码，然后再把经纬度各自的编码组合成一个最终编码。

GeoHash 编码原理：

首先，我们来看下经度和纬度的单独编码过程。对于一个地理位置信息来说，它的经度范围是 [-180,180]。GeoHash 编码会把一个经度值编码成一个 N 位的二进制值，我们来对经度范围 [-180,180] 做 N 次的二分区操作，其中 N 可以自定义。

在进行第一次二分区时，经度范围 [-180,180] 会被分成两个子区间：[-180,0) 和 [0,180]（我称之为左、右分区）。此时，我们可以查看一下要编码的经度值落在了左分区还是右分区。如果是落在左分区，我们就用 0 表示；如果落在右分区，就用 1 表示。这样一来，每做完一次二分区，我们就可以得到 1 位编码值。

然后，我们再对经度值所属的分区再做一次二分区，同时再次查看经度值落在了二分区后的左分区还是右分区，按照刚才的规则再做 1 位编码。当做完 N 次的二分区后，经度值就可以用一个 N bit 的数来表示了。

举个例子：

假设我们要编码的经度值是 116.37，我们用 5 位编码值（也就是 N=5，做 5 次分区）。

  1. 第一次二分区操作，把经度区间 [-180,180] 分成了左分区 [-180,0) 和右分区 [0,180]，此时，经度值 116.37 是属于右分区 [0,180]，所以，我们用 1 表示第一次二分区后的编码值
  2. 第二次二分区：把经度值 116.37 所属的 [0,180] 区间，分成 [0,90) 和 [90, 180]。此时，经度值 116.37 还是属于右分区 [90,180]，所以，第二次分区后的编码值仍然为 1
  3. 第三次对 [90,180] 进行二分区，经度值 116.37 落在了分区后的左分区 [90, 135) 中，所以，第三次分区后的编码值就是 0

按照这种方法，做完 5 次分区后，我们把经度值 116.37 定位在 [112.5, 123.75] 这个区间，并且得到了经度值的 5 位编码值，即 11010。

对纬度的编码方式，和对经度的一样，只是纬度的范围是 [-90，90]。

组合编码：

当一组经纬度值都编完码后，我们再把它们的各自编码值组合在一起，组合的规则是：最终编码值的偶数位上依次是经度的编码值，奇数位上依次是纬度的编码值，其中，偶数位从 0 开始，奇数位从 1 开始。

我们刚刚计算的经纬度（116.37，39.86）的各自编码值是 11010 和 10111，组合之后，第 0 位是经度的第 0 位 1，第 1 位是纬度的第 0 位 1，第 2 位是经度的第 1 位 1，第 3 位是纬度的第 1 位 0，以此类推，就能得到最终编码值 1110011101。

用了 GeoHash 编码后，原来无法用一个权重分数表示的一组经纬度（116.37，39.86）就可以用 1110011101 这一个值来表示，就可以保存为 Sorted Set 的权重分数了。

当然，使用 GeoHash 编码后，我们相当于把整个地理空间划分成了一个个方格，每个方格对应了 GeoHash 中的一个分区。

举个例子：

我们把经度区间 [-180,180] 做一次二分区，把纬度区间 [-90,90] 做一次二分区，就会得到 4 个分区。我们来看下它们的经度和纬度范围以及对应的 GeoHash 组合编码：

  • 分区一：[-180,0) 和 [-90,0)，编码 00
  • 分区二：[-180,0) 和 [0,90]，编码 01
  • 分区三：[0,180] 和 [-90,0)，编码 10
  • 分区四：[0,180] 和 [0,90]，编码 11

这 4 个分区对应了 4 个方格，每个方格覆盖了一定范围内的经纬度值，分区越多，每个方格能覆盖到的地理空间就越小，也就越精准。

我们把所有方格的编码值映射到一维空间时，相邻方格的 GeoHash 编码值基本也是接近的。所以，我们使用 Sorted Set 范围查询得到的相近编码值，在实际的地理空间上，也是相邻的方格，这就可以实现 LBS 应用”搜索附近的人或物”的功能了。

不过，我要提醒你一句，有的编码值虽然在大小上接近，但实际对应的方格却距离比较远。例如，我们用 4 位来做 GeoHash 编码，把经度区间 [-180,180] 和纬度区间 [-90,90] 各分成了 4 个分区，一共 16 个分区，对应了 16 个方格。编码值为 0111 和 1000 的两个方格就离得比较远。

所以，为了避免查询不准确问题，我们可以同时查询给定经纬度所在的方格周围的 4 个或 8 个方格。

好了，到这里，我们就知道了，GEO 类型是把经纬度所在的区间编码作为 Sorted Set 中元素的权重分数，把和经纬度相关的车辆 ID 作为 Sorted Set 中元素本身的值保存下来，这样相邻经纬度的查询就可以通过编码值的大小范围查询来实现了。

2.2.2 Streams 类型

Redis 也可以使用 List 数据类型当做队列使用，一个客户端使用 rpush 生产数据到 Redis 中，另一个客户端使用 lpop 取出数据进行消费，非常方便。但要注意的是，使用 List 当做队列，缺点是没有 ack 机制和不支持多个消费者。

没有 ack 机制会导致从 Redis 中取出的数据后，如果客户端处理失败了，取出的这个数据相当于丢失了，无法重新消费。所以使用 List 用作队列适合于对于丢失数据不敏感的业务场景，但它的优点是，因为都是内存操作，所以非常快和轻量。

而 Redis 提供的 PubSub，可以支持多个消费者进行消费，生产者发布一条消息，多个消费者同时订阅消费。但是它的缺点是，如果任意一个消费者挂了，等恢复过来后，在这期间的生产者的数据就丢失了。PubSub 只把数据发给在线的消费者，消费者一旦下线，就会丢弃数据。另一个缺点是，PubSub 中的数据不支持数据持久化，当 Redis 宕机恢复后，其他类型的数据都可以从 RDB 和 AOF 中恢复回来，但 PubSub 不行，它就是简单的基于内存的多播机制。

之后 Redis 5.0 推出了 Stream 数据结构，它借鉴了 Kafka 的设计思想，弥补了 List 和 PubSub 的不足。Stream 类型数据可以持久化、支持 ack 机制、支持多个消费者、支持回溯消费，基本上实现了队列中间件大部分功能，比 List 和 PubSub 更可靠。

2.2.3 Bitmap 类型

二值状态统计的场景，签到，登录状态。

2.2.4 HyperLogLog 类型

海量数据基数统计的场景，百万级网页 UV、PV 计数。

三、数据结构应用场景

3.1 聚合统计

当你需要对多个集合进行聚合计算时，Set 类型会是一个非常不错的选择。

3.2 排序统计

在面对需要展示最新列表、排行榜等场景时，如果数据更新频繁或者需要分页显示，建议你优先考虑使用 Sorted Set。

3.3 二值状态统计

如果只需要统计数据的二值状态，例如商品有没有、用户在不在等，就可以使用 Bitmap，因为它只用一个 bit 位就能表示 0 或 1。在记录海量数据时，Bitmap 能够有效地节省内存空间。

Roaring Bitmap 优化：

比如我们有一亿个用户 ID，其中只有 1000 个活跃，如果直接用普通位图，可能需要 12MB 内存。使用 Roaring Bitmap，可以把内存压缩到几十 KB，同时支持 AND/OR/XOR 操作，非常适合大数据、高性能分析场景。

Roaring Bitmap = 稀疏 + 高效位运算，适合大规模 ID 集合压缩和快速集合操作，比传统 Bitmap 内存占用少，操作更灵活。

3.4 基数统计

如果集合元素量达到亿级别而且不需要精确统计时，我建议你使用 HyperLogLog。

四、数据结构总结

4.1 基础数据结构对比

数据类型 底层实现 适用场景 时间复杂度
String SDS / int / embstr / raw 缓存、计数器、分布式锁 O(1)
Hash ziplist / hashtable / listpack 对象存储、购物车 O(1)
List ziplist / linkedlist / quicklist 消息队列、时间线 O(1) 头尾，O(N) 中间
Set intset / hashtable 标签、共同好友 O(1)
Zset ziplist / skiplist / listpack 排行榜、延时队列 O(logN)

4.2 高级数据结构对比

数据类型 底层实现 适用场景 特点
GEO Sorted Set + GeoHash LBS 服务、附近的人 地理位置编码
Streams Radix Tree 消息队列、事件溯源 支持 ack、持久化
Bitmap String 签到、布隆过滤器 节省内存
HyperLogLog 概率算法 UV 统计、基数估算 0.81% 误差率

4.3 编码方式选择

String 类型：

  • 整数：int 编码
  • 字符串 ≤ 44 字节：embstr 编码
  • 字符串 > 44 字节：raw 编码

Hash 类型：

  • 元素 < 512 且值 < 64 字节：ziplist/listpack
  • 其他：hashtable

List 类型：

  • Redis 3.2+：quicklist（ziplist/listpack 作为节点）

Set 类型：

  • 全是整数且 < 512 个：intset
  • 其他：hashtable

Zset 类型：

  • 元素 < 128 且值 < 64 字节：ziplist/listpack
  • 其他：skiplist

4.4 性能优化建议

  1. 合理选择数据类型：根据业务场景选择合适的数据结构
  2. 控制 key 的大小：避免使用过长的 key
  3. 注意编码转换：了解不同编码方式的转换条件
  4. 避免大 key：单个 key 的 value 不要过大
  5. 使用 pipeline：批量操作减少网络开销
  6. 合理设置过期时间：避免内存占用过高
  7. 监控内存使用：定期检查内存碎片率

五、总结

Redis 的核心数据结构设计体现了”用空间换时间”和”针对场景优化”的思想：

  1. 全局 Hash 表提供了 O(1) 的快速查找能力，通过渐进式 rehash 避免阻塞
  2. 多种编码方式针对不同数据规模进行优化，在内存和性能之间取得平衡
  3. 压缩列表到 listpack 的演进解决了连锁更新问题，提升了性能
  4. 跳表为有序集合提供了 O(logN) 的查找效率
  5. 高级数据结构如 GEO、Streams 等满足了特定场景的需求

理解这些底层数据结构的实现原理，有助于我们在实际应用中做出更好的技术选型和性能优化。