参考：

• 11 “万金油”的 String，为什么不好用了？| 极客时间 (opens new window)
• 12 有一亿个 keys 要统计，应该用哪种集合？| 极客时间 (opens new window)
• 13 GEO是什么？还可以定义新的数据类型吗？| 极客时间 (opens new window)

这一章将学习“数据结构”，介绍内存开销以及保存和统计海量数据的数据类型及其底层数据结构，还会围绕典型的应用场景（例如地址位置查询、时间序列数据库读写和消息队列存取），跟你分享使用 Redis 的数据类型和 module 扩展功能来满足需求的具体方案。

1. “万金油”的 String，为什么不好用了？

这一节了解一下 String 类型的内存空间消耗问题，以及选择节省内存开销的数据类型的解决方案。

先分享一个实际的需求。当时要开发一个图片存储系统，要求能快速根据图片 ID 找到对应的图片存储对象 ID，即 photo_id -> photo_obj_id。由于图片数量巨大，我们就使用 10 位数来保存这个 ID，例如：

photo_id: 1101000051
photo_obj_id: 3301000051

可以看到 photo_id 与 photo_obj_id 一一对应，是典型的“键-单值”模式。所谓的“单值”，就是指键值对中的值就是一个值，而不是一个集合，这和 String 类型提供的“一个键对应一个值的数据”的保存形式刚好契合。

而且，String 类型可以保存二进制字节流，就像“万金油”一样，只要把数据转成二进制字节数组，就可以保存了。

所以，我们的第一个方案就是用 String 保存数据。我们把图片 ID 和图片存储对象 ID 分别作为键值对的 key 和 value 来保存，其中，图片存储对象 ID 用了 String 类型。

刚开始，我们保存了1亿张图片，大约用了6.4GB的内存。但随着图片数据量的不断增加，Redis 内存使用量也在增加，导致因生成RDB而响应变慢的问题。很显然，String类型并不是一种好的选择，我们还需要进一步寻找能节省内存开销的数据类型方案。

在这个过程中，我们研究发现：String类型并不是适用于所有场合的，它有一个明显的短板，就是它保存数据时所消耗的内存空间较多。

同时，我们还仔细研究了集合类型的数据结构，发现，集合类型有非常节省内存空间的底层实现结构，但是，集合类型保存的数据模式，是一个键对应一系列值，并不适合直接保存单值的键值对。所以，我们就使用二级编码的方法，实现了用集合类型保存单值键值对，Redis 实例的内存空间消耗明显下降了。

这节课，我就把在解决这个问题时学到的经验和方法分享给你，包括 String 类型的内存空间消耗在哪儿了、用什么数据结构可以节省内存，以及如何用集合类型保存单值键值对。如果你在使用String类型时也遇到了内存空间消耗较多的问题，就可以尝试下今天的解决方案了。

接下来，我们先来看看 String 类型的内存都消耗在哪里了。

1.1 为什么 String 类型内存开销大？

在刚才的案例中，我们保存了1亿张图片的信息，用了约6.4GB的内存，一个图片ID和图片存储对象ID的记录平均用了64字节。但问题是，一组图片ID及其存储对象ID的记录，实际只需要16字节就可以了。

我们来分析一下。如果我们可以用两个8字节的 Long 类型表示这两个 ID，因为 8 字节的Long类型最大可以表示 ，所以肯定可以表示10位数。但是，为什么String类型却用了64字节呢？

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

那么，String类型具体是怎么保存数据的呢？

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

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

• buf：char[] 类型，保存实际数据，同时会在尾部加一个 \0。
• len：4 byte，表示 buf 的长度。
• alloc：4 byte，表示 buf 的分配长度。

可以看到，len 和 alloc 就是 SDS 结构体的额外开销。另外，对于 String 类型来说，除了 SDS，还有一个来自于 RedisObject 结构体的开销。

Redis 使用 RedisObject 结构体来统一记录不同的数据结构的元数据和实际数据位置。其结构示意图如下：

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

• 当保存的是 Long 类型时，RedisObject 中的 ptr 就直接赋值为整数数据了，这样就不用额外的指针再指向整数了，节省了指针的开销。这也是前面说的 int 编码方式。
• 当保存的是字符串时，且字符串小于等于 44 byte 时，RedisObject 中的元数据、指针和 SDS 是一块连续的内存区域，这样就可以避免内存碎片。这种布局方式也被称为 embstr编码方式。
• 当字符串大于 44 byte 时，SDS 数据量就开始变多，Redis 就不再把 SDS 和 RedisObject 布局在一起了，而是会给 SDS 分配独立的空间，并用指针指向 SDS 结构。这种布局方式被称为 raw 编码模式。

三种编码方式如下图所示：

现在知道了 RedisObject 的额外开销，我们就可以计算 String 类型的内存使用量了。

因为10位数的图片ID和图片存储对象ID是Long类型整数，所以可以直接用int编码的RedisObject保存。每个int编码的RedisObject元数据部分占8字节，指针部分被直接赋值为8字节的整数了。此时，每个ID会使用16字节，加起来一共是32字节。但是，另外的32字节去哪儿了呢？其实，Redis 是使用一个全局 hash table 来保存所有的键值对的，哈希表的每一项是一个 dictEntry 的结构体，用来指向一个 kv pair。其中 dictEntry 有三个 8 byte 的指针，分别指向 key、value 以及下一个 dictEntry。一个 dictEntry 如下图所示：

但 dictEntry 只占了 24 byte，那为啥会占用 32 byte 呢？这就要提到 Redis 使用的内存分配库 jemalloc 了。

jemalloc 在分配内存时，会根据我们申请的字节数 N，找一个比 N 大，但是最接近 N 的 2 的幂次数作为分配的空间，这样可以减少频繁分配的次数。举个例子。如果你申请6字节空间，jemalloc实际会分配8字节空间；如果你申请24字节空间，jemalloc则会分配32字节。所以，在我们刚刚说的场景里，dictEntry结构就占用了32字节。

好了，到这里你就能理解，为什么用String类型保存图片ID和图片存储对象ID时需要用64个字节了。你看，明明有效信息只有 16 byte，使用 String 类型保存却需要 64 byte 的内存空间，有 48 byte 都是额外开销。那有没有更节省内存的方法呢？

1.2 用什么数据结构可以节省内存？

Redis 有一种底层数据结构，叫压缩列表（ziplist），这是一种非常节省内存的结构。

我们先回顾下压缩列表的构成：表头有三个字段zlbytes、zltail和zllen，分别表示列表长度、列表尾的偏移量，以及列表中的entry个数。压缩列表尾还有一个zlend，表示列表结束。如下图：

压缩列表之所以能节省内存，就在于它是用一系列连续的 entry 保存数据。每个 entry 的元数据包括下面几部分：

• prev_len：表示前一个entry的长度。prev_len有两种取值情况：1字节或5字节。取值1字节时，表示上一个entry的长度小于254字节。虽然1字节的值能表示的数值范围是0到255，但是压缩列表中zlend的取值默认是255，因此，就默认用255表示整个压缩列表的结束，其他表示长度的地方就不能再用255这个值了。所以，当上一个entry长度小于254字节时，prev_len取值为1字节，否则，就取值为5字节。
• len：表示自身长度，4 byte
• encoding：表示编码方式，1 byte
• content：保存实际数据

这些 entry 会挨个儿放置在内存中，不需要再用额外的指针进行连接，这样就可以节省指针所占用的空间。

我们以保存图片存储对象ID为例，来分析一下压缩列表是如何节省内存空间的。每个entry保存一个图片存储对象ID（8字节），此时，每个entry的prev_len只需要1个字节就行，因为每个entry的前一个entry长度都只有8字节，小于254字节。这样一来，一个图片的存储对象ID所占用的内存大小是14字节（1+4+1+8=14），实际分配16字节。

Redis基于压缩列表实现了 List、Hash 和 Sorted Set 这样的集合类型，这样做的最大好处就是节省了 dictEntry 的开销。当你用 String 类型时，一个键值对就有一个 dictEntry，要用 32 字节空间。但采用集合类型时，一个 key 就对应一个集合的数据，能保存的数据多了很多，但也只用了一个 dictEntry，这样就节省了内存。

这个方案听起来很好，但还存在一个问题：在用集合类型保存键值对时，一个键对应了一个集合的数据，但是在我们的场景中，一个图片ID只对应一个图片的存储对象ID，我们该怎么用集合类型呢？换句话说，在一个键对应一个值（也就是单值键值对）的情况下，我们该怎么用集合类型来保存这种单值键值对呢？

1.3 如何用集合类型保存单值的键值对？

在保存单值的键值对时，可以采用基于 Hash 类型的二级编码方法。这里说的二级编码，就是把一个单值的数据拆分成两部分，前一部分作为Hash集合的key，后一部分作为Hash集合的value，这样一来，我们就可以把单值数据保存到Hash集合中了。

以图片ID 1101000060和图片存储对象ID 3302000080为例，我们可以把图片ID的前7位（1101000）作为Hash类型的键，把图片ID的最后3位（060）和图片存储对象ID分别作为Hash类型值中的key和value。

按照这种设计方法，我在Redis中插入了一组图片ID及其存储对象ID的记录，并且用info命令查看了内存开销，我发现，增加一条记录后，内存占用只增加了16字节，如下所示：

127.0.0.1:6379> info memory
# Memory
used_memory:1039120
127.0.0.1:6379> hset 1101000 060 3302000080
(integer) 1
127.0.0.1:6379> info memory
# Memory
used_memory:1039136

在使用 String 类型时，每个记录需要消耗 64 字节，这种方式却只用了 16 字节，所使用的内存空间是原来的 1/4，满足了我们节省内存空间的需求。

不过，你可能也会有疑惑：“二级编码一定要把图片ID的前7位作为Hash类型的键，把最后3位作为Hash类型值中的key吗？” 其实，二级编码方法中采用的ID长度是有讲究的。

我们之前讲过，Redis 的 Hash 类型有两种底层实现结构，分别是压缩列表和哈希表。Hash 类型设置了一个用压缩列表保存数据时的阈值，一旦超过阈值，Hash 类型就会用哈希表来保存数据了。这两个阈值分别对应以下两个配置项：

• hash-max-ziplist-entries：表示用压缩列表保存时哈希集合中的最大元素个数。
• hash-max-ziplist-value：表示用压缩列表保存时哈希集合中单个元素的最大长度。

如果我们往Hash集合中写入的元素个数超过了 hash-max-ziplist-entries，或者写入的单个元素大小超过了 hash-max-ziplist-value，Redis 就会自动把 Hash 类型的实现结构由压缩列表转为哈希表。

一旦从压缩列表转为了哈希表，Hash 类型就会一直用哈希表进行保存，而不会再转回压缩列表了。在节省内存空间方面，哈希表就没有压缩列表那么高效了。

为了能充分使用压缩列表的精简内存布局，我们一般要控制保存在Hash集合中的元素个数。所以，在刚才的二级编码中，我们只用图片ID最后3位作为Hash集合的key，也就保证了Hash集合的元素个数不超过1000，同时，我们把 hash-max-ziplist-entries 设置为 1000，这样一来，Hash 集合就可以一直使用压缩列表来节省内存空间了。

1.4 小结

这一节我们打破了对 String 的认知误区，了解到 String 并非万金油，当保存的 kv pair 本身占用内存空间不大时，String 类型的元数据开销就占据主导了，这包括了 RedisObject、SDS、dictEntry 结构的内存开销。

针对这种情况，我们可以借助压缩列表这种底层结构，使用 Hash 类型的二级编码方法来保存单值 kv pair 的数据。也就是需要将原 kv pair 的 key 拆成两部分，前一部分作为 Hash 集合的 key，后一部分与原 kv pair 的 value 组合成一个新 kv 来作为 Hash 集合的 value。

小妙招：如果你想知道 kv pair 采用不同类型保存时的内存开销，可以在Redis 容量预估 (opens new window)这个网站上进行估计。

2. 有一亿个keys要统计，应该用哪种集合？

很多场景需要保存这样一种数据：一个 key 对应了一个数据集合。比如用户 ID -> 登录设备，员工 -> 一天打卡记录。

Redis 的集合类型很适合存储这些数据，但在这些场景中，除了记录信息，我们往往还需要对集合中的数据进行统计，比如统计每天新增用户数、一个月连续打卡的员工数等。通常我们会面临巨大的访问量，比如百万、千万级别。所以，我们必须要能够选择非常高效地统计大量数据（例如亿级）的集合类型。

要想选择合适的集合，我们就得了解常用的集合统计模式。这一节将介绍集合类型的常见四种统计模式：聚合统计、排序统计、二值状态统计和基数统计，并介绍这些统计场景下什么数据结构更加合适。

2.1 聚合统计 —— Set

聚合统计：指统计多个集合元素的聚合结果，包括：统计多个集合的共有元素（交集统计）；把两个集合相比，统计其中一个集合独有的元素（差集统计）；统计多个集合的所有元素（并集统计）。

比如统计手机 App 每天的新增用户数和第二天的留存用户数就是聚合统计。要完成这个统计任务，我们可以用一个集合记录所有登录过App的用户ID，同时，用另一个集合记录每一天登录过App的用户ID。然后，再对这两个集合做聚合统计。我们来看下具体的操作。

可以使用 Set 类型来记录所有登录过 App 的用户 ID，把 key 设置成 user:id，value 就是保存了所有登陆过 App 的用户 ID 的 Set，如下图：

还需要记录每一天登录的用户 ID，可以让 key 设为 user:id:<datetime>，比如 user:id:20200803，value 是记录了当天登录的所有用户 ID 的 Set。如下图：

在统计每天的新增用户时，我们只用计算每日用户 Set 和累计用户 Set 的差集就行。

当你需要对多个集合进行聚合计算时，Set 类型会是一个非常不错的选择。不过，这里有一个潜在的风险：Set 的差集、并集和交集的计算复杂度较高，在数据量较大的情况下，如果直接执行这些计算，会导致Redis实例阻塞。所以这里给一个小建议：你可以从主从集群中选择一个从库，让它专门负责聚合计算，或者是把数据读取到客户端，在客户端来完成聚合统计，这样就可以规避阻塞主库实例和其他从库实例的风险了。

2.2 排序统计 —— 有序集合

这一小节讲应对集合元素排序的需求的方法，这里以电商网站提供最新评论列表的场景为例进行讲解。

最新评论列表包含了所有评论中的最新留言，这就要求集合类型能对元素保序，这种对元素保序的集合类型叫作有序集合。在 Redis 的四个集合类型中（List、Hash、Set 和 Sorted Set），List 和 Sorted Set 就属于有序集合。

• List 按照元素添加的顺序进行排序；
• Sorted Set 按照元素的权重来排序，其中权重值可以自己决定（比如让插入时间作为权重）。

貌似都符合需求，接下来看一下如何选择。

---

如果使用 List 的话。每个商品对应一个 List，这个 List 包含了该商品的全部评论，并按照评论时间保存，每来一个新评论就用 LPUSH 命令把它插入到 List 的队头。

在只有一页评论的时候，我们可以很清晰地看到最新的评论，但是，在实际应用中，网站一般会分页显示最新的评论列表，一旦涉及到分页操作，List就可能会出现问题了。

假设当前的评论List是{A, B, C, D, E, F}（其中，A是最新的评论，以此类推，F是最早的评论），在展示第一页的3个评论时，我们可以用下面的命令，得到最新的三条评论A、B、C：

LRANGE product1 0 2
1) "A"
2) "B"
3) "C"

然后，再用下面的命令获取第二页的3个评论，也就是D、E、F：

LRANGE product1 3 5
1) "D"
2) "E"
3) "F"

但是，如果在展示第二页前，又产生了一个新评论G，评论G就会被LPUSH命令插入到评论List的队头，评论List就变成了{G, A, B, C, D, E, F}。此时，再用刚才的命令获取第二页评论时，就会发现，评论C又被展示出来了，也就是C、D、E：

LRANGE product1 3 5
1) "C"
2) "D"
3) "E"

之所以会这样，关键原因就在于，List是通过元素在List中的位置来排序的，当有一个新元素插入时，原先的元素在List中的位置都后移了一位，比如说原来在第1位的元素现在排在了第2位。所以，对比新元素插入前后，List 相同位置上的元素就会发生变化，用 LRANGE 读取时，就会读到旧元素。

---

和 List 相比，Sorted Set 就不存在这个问题，因为它是根据元素的实际权重来排序和获取数据的。

我们可以按评论时间的先后给每条评论设置一个权重值，然后再把评论保存到 Sorted Set 中。Sorted Set 的 ZRANGEBYSCORE 命令就可以按权重排序后返回元素。这样的话，即使集合中的元素频繁更新，Sorted Set 也能通过 ZRANGEBYSCORE 命令准确地获取到按序排列的数据。

假设越新的评论权重越大，目前最新评论的权重是N，我们执行下面的命令时，就可以获得最新的10条评论：

ZRANGEBYSCORE comments N-9 N

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

2.3 二值状态统计 —— Bitmap

二值状态就是指集合元素的取值就只有 0 和 1 两种。比如在签到打卡的场景中，只用记录签到（1）或未签到（0），所以这就是非常典型的二值状态。

在签到统计时，每个用户一天的签到用 1 个 bit 位就能表示，一个月（假设是31天）的签到情况用 31 个 bit 位就可以，而一年的签到也只需要用 365 个 bit 位，根本不用太复杂的集合类型。这个时候，我们就可以选择 Bitmap。这是Redis提供的扩展数据类型。接下来介绍 Bitmap 的实现原理。

Bitmap 本身是用 String 类型作为底层数据结构实现的一种统计二值状态的数据类型。String 类型是会保存为二进制的字节数组，所以，Redis 就把字节数组的每个 bit 位利用起来，用来表示一个元素的二值状态。你可以把 Bitmap 看作是一个 bit 数组。

Bitmap 提供了 GETBIT/SETBIT 操作，使用一个偏移值 offset 对 bit 数组的某一个 bit 位进行读和写。不过，需要注意的是，Bitmap 的 offset 是从 0 开始算的，也就是说offset的最小值是0。当使用SETBIT对一个bit位进行写操作时，这个bit位会被设置为1。Bitmap 还提供了 BITCOUNT 操作，用来统计这个bit数组中所有“1”的个数。

那么，具体该怎么用 Bitmap 进行签到统计呢？我还是借助一个具体的例子来说明。假设我们要统计 ID 3000 的用户在2020年8月份的签到情况，就可以按照下面的步骤进行操作：

1. 执行下面的命令，记录该用户8月3号已签到：

SETBIT uid:sign:3000:202008 2 1

2. 检查该用户8月3日是否签到：

GETBIT uid:sign:3000:202008 2

3. 统计该用户在8月份的签到次数：

BITCOUNT uid:sign:3000:202008

这样，我们就知道该用户在8月份的签到情况了，是不是很简单呢？接下来，你可以再思考一个问题：如果记录了1亿个用户10天的签到情况，你有办法统计出这10天连续签到的用户总数吗？

在介绍具体的方法之前，我们要先知道，Bitmap支持用 BITOP 命令对多个Bitmap按位做“与”“或”“异或”的操作，操作的结果会保存到一个新的Bitmap中。比如下图对三个 bitmap 做 AND 操作：

回到刚刚的问题，在统计1亿个用户连续10天的签到情况时，你可以把每天的日期作为key，每个key对应一个1亿位的Bitmap，每一个bit对应一个用户当天的签到情况。

接下来，我们对10个Bitmap做“与”操作，得到的结果也是一个Bitmap。在这个Bitmap中，只有10天都签到的用户对应的bit位上的值才会是1。最后，我们可以用BITCOUNT统计下Bitmap中的1的个数，这就是连续签到10天的用户总数了。

现在，我们可以计算一下记录了10天签到情况后的内存开销。每天使用1个1亿位的Bitmap，大约占12MB的内存（10^8/8/1024/1024），10天的Bitmap的内存开销约为120MB，内存压力不算太大。不过，在实际应用时，最好对Bitmap设置过期时间，让Redis自动删除不再需要的签到记录，以节省内存开销。

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

2.4 基数统计 —— HyperLogLog

基数统计就是指统计一个集合中不重复的元素个数。比如我们统计一个网页的独立访客（Unique Visitor，UV）量。UV 的统计有个独特的地方：需要去重，一个用户一天内的多次访问只能算作一次。

在Redis的集合类型中，Set类型默认支持去重，所以看到有去重需求时，我们可能第一时间就会想到用Set类型。我们来结合一个例子看一看用Set的情况。有一个用户user1访问page1时，你把这个信息加到Set中：

SADD page1:uv user1

用户1再来访问时，Set 的去重功能就保证了不会重复记录用户1的访问次数，这样，用户1就算是一个独立访客。当你需要统计UV时，可以直接用SCARD命令，这个命令会返回一个集合中的元素个数。但是，如果page1非常火爆，UV达到了千万，这个时候，一个Set就要记录千万个用户ID。对于一个搞大促的电商网站而言，这样的页面可能有成千上万个，如果每个页面都用这样的一个Set，就会消耗很大的内存空间。

当然，你也可以用 Hash 类型记录 UV。例如，你可以把用户ID作为Hash集合的key，当用户访问页面时，就用HSET命令（用于设置Hash集合元素的值），对这个用户ID记录一个值“1”，表示一个独立访客，用户1访问page1后，我们就记录为1个独立访客，如下所示：

HSET page1:uv user1 1

即使用户1多次访问页面，重复执行这个HSET命令，也只会把user1的值设置为1，仍然只记为1个独立访客。当要统计 UV 时，我们可以用 HLEN 命令统计 Hash 集合中的所有元素个数。

但是，和Set类型相似，当页面很多时，Hash类型也会消耗很大的内存空间。那么，有什么办法既能完成统计，还能节省内存吗？这时候，就要用到Redis提供的 HyperLogLog 了。

HyperLogLog 是一种用于统计基数的数据集合类型，它的最大优势就在于，当集合元素数量非常多时，它计算基数所需的空间总是固定的，而且还很小。在Redis中，每个 HyperLogLog 只需要花费 12 KB 内存，就可以计算接近 2^64 个元素的基数。你看，和元素越多就越耗费内存的Set和Hash类型相比，HyperLogLog 就非常节省空间。

在统计 UV 时，你可以用 PFADD 命令（用于向 HyperLogLog 中添加新元素）把访问页面的每个用户都添加到 HyperLogLog 中：

PFADD page1:uv user1 user2 user3 user4 user5

接下来，就可以用 PFCOUNT 命令 直接获得 page1 的 UV 值了，这个命令的作用就是返回 HyperLogLog 的统计结果：

PFCOUNT page1:uv

关于 HyperLogLog 的具体实现原理，你不需要重点掌握，不会影响到你的日常使用。想要更多了解的话，可以参考这条链接 (opens new window)。

不过，有一点需要你注意一下，HyperLogLog 的统计规则是基于概率完成的，所以它给出的统计结果是有一定误差的，标准误算率是 0.81%。这也就意味着，你使用 HyperLogLog 统计的 UV 是 100 万，但实际的 UV 可能是 101 万。虽然误差率不算大，但是，如果你需要精确统计结果的话，最好还是继续用 Set 或 Hash 类型。

2.5 小结

这一大节针对聚合统计、排序统计、二值状态统计和基数统计四种场景讲解了多个数据结构，汇总如下：

可以看到：

• Set和Sorted Set都支持多种聚合统计，不过，对于差集计算来说，只有Set支持。Bitmap也能做多个Bitmap间的聚合计算，包括与、或和异或操作。
• 当需要进行排序统计时，List中的元素虽然有序，但是一旦有新元素插入，原来的元素在List中的位置就会移动，那么，按位置读取的排序结果可能就不准确了。而Sorted Set本身是按照集合元素的权重排序，可以准确地按序获取结果，所以建议你优先使用它。
• 如果我们记录的数据只有0和1两个值的状态，Bitmap会是一个很好的选择，这主要归功于Bitmap对于一个数据只用1个bit记录，可以节省内存。
• 对于基数统计来说，如果集合元素量达到亿级别而且不需要精确统计时，我建议你使用HyperLogLog。

当然，Redis的应用场景非常多，这张表中的总结不一定能覆盖到所有场景。我建议你也试着自己画一张表，把你遇到的其他场景添加进去。长久积累下来，你一定能够更加灵活地把集合类型应用到合适的实践项目中。

3. GEO 是什么？还可以定义新的数据类型吗？

我们之前学习了 Redis 的 5 大基本数据类型：String、List、Hash、Set 和 Sorted Set。在面对一些特殊场景时，这些类型无法很好地支持，于是 Redis 还提供了 3 种扩展类型：Bitmap、HyperLogLog 和 GEO。这一节主要讲一些 GEO。

另外节还讲介绍开发自定义的新数据类型的基本步骤，从而满足个人的特殊需求。

3.1 面向 LBS 应用的 GEO 类型

日常的地图搜索、打车等都离不开基于位置信息服务（Location-Based Service，LBS）的应用。LBS 应用访问的数据是和人或物关联的一组经纬度信息，而且要能查询相邻的经纬度范围，GEO 就非常适合应用在 LBS服 务的场景中，我们来看一下它的底层结构。

3.1.1 GEO 的底层结构

一般来说，在设计一个数据类型的底层结构时，我们首先需要知道，要处理的数据有什么访问特点。所以，我们需要先搞清楚位置信息到底是怎么被存取的。

以叫车服务为例，来分析下 LBS 应用中经纬度的存取特点：

1. 每一辆网约车都有一个编号（例如33），网约车需要将自己的经度信息（例如116.034579）和纬度信息（例如39.000452 ）发给叫车应用。
2. 用户在叫车的时候，叫车应用会根据用户的经纬度位置（例如经度116.054579，纬度39.030452），查找用户的附近车辆，并进行匹配。
3. 等把位置相近的用户和车辆匹配上以后，叫车应用就会根据车辆的编号，获取车辆的信息，并返回给用户。

可以看到，一辆车（或一个用户）对应一组经纬度，并且随着车（或用户）的位置移动，相应的经纬度也会变化。这种数据记录模式属于一个key（例如车ID）对应一个value（一组经纬度）。当有很多车辆信息要保存时，就需要有一个集合来保存一系列的key和value。Hash集合类型可以快速存取一系列的key和value，正好可以用来记录一系列车辆ID和经纬度的对应关系，所以，我们可以把不同车辆的ID和它们对应的经纬度信息存在Hash集合中，如下图所示：

同时，Hash类型的HSET操作命令，会根据key来设置相应的value值，所以，我们可以用它来快速地更新车辆变化的经纬度信息。到这里，Hash类型看起来是一个不错的选择。但问题是，对于一个LBS应用来说，除了记录经纬度信息，还需要根据用户的经纬度信息在车辆的Hash集合中进行范围查询。一旦涉及到范围查询，就意味着集合中的元素需要有序，但Hash类型的元素是无序的，显然不能满足我们的要求。

我们再来看看使用 Sorted Set类型是不是合适。

Sorted Set 类型也支持一个 key 对应一个 value 的记录模式，其中，key就是Sorted Set中的元素，而value则是元素的权重分数。更重要的是，Sorted Set可以根据元素的权重分数排序，支持范围查询。这就能满足LBS服务中查找相邻位置的需求了。

实际上，GEO 类型的底层数据结构就是用 Sorted Set 来实现的。咱们还是借着叫车应用的例子来加深下理解。用Sorted Set来保存车辆的经纬度信息时，Sorted Set的元素是车辆ID，元素的权重分数是经纬度信息，如下图所示：

这时问题来了，Sorted Set元素的权重分数是一个浮点数（float类型），而一组经纬度包含的是经度和纬度两个值，是没法直接保存为一个浮点数的，那具体该怎么进行保存呢？这就要用到 GEO 类型中的 GeoHash 编码了。

3.1.2 GeoHash 的编码方法

为了能高效地对经纬度进行比较，Redis 采用了业界广泛使用的 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次分区）。我们先做第一次二分区操作，把经度区间[-180,180]分成了左分区[-180,0)和右分区[0,180]，此时，经度值116.37是属于右分区[0,180]，所以，我们用1表示第一次二分区后的编码值。接下来，我们做第二次二分区：把经度值116.37所属的[0,180]区间，分成[0,90)和[90, 180]。此时，经度值116.37还是属于右分区[90,180]，所以，第二次分区后的编码值仍然为1。等到第三次对[90,180]进行二分区，经度值116.37落在了分区后的左分区[90, 135)中，所以，第三次分区后的编码值就是0。

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

对纬度的编码方式，和对经度的一样，只是纬度的范围是[-90，90]，下面这张表显示了对纬度值39.86的编码过程：

当一组经纬度值都编完码后，我们再把它们的各自编码值组合在一起，组合的规则是：最终编码值的偶数位上依次是经度的编码值，奇数位上依次是纬度的编码值，其中，偶数位从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 中元素本身的值保存下来，这样相邻经纬度的查询就可以通过编码值的大小范围查询来实现了。接下来，我们再来聊聊具体如何操作 GEO 类型。

3.1.3 如何操作 GEO 类型？

操作 GEO 类型经常使用两个命令：

• GEOADD 命令：用于把一组经纬度信息和相对应的一个 ID 记录到 GEO 类型集合中；
• GEORADIUS 命令：会根据输入的经纬度位置，查找以这个经纬度为中心的一定范围内的其他元素。当然，我们可以自己定义这个范围。

我还是以“叫车应用”的车辆匹配场景为例，介绍下具体如何使用这两个命令。

---

GEOADD 命令：

假设车辆ID是33，经纬度位置是（116.034579，39.030452），我们可以用一个 GEO 集合保存所有车辆的经纬度，集合 key 是 cars:locations。执行下面的这个命令，就可以把 ID 号为 33 的车辆的当前经纬度位置存入 GEO 集合中：

GEOADD cars:locations 116.034579 39.030452 33

---

GEORADIUS 命令：

当用户想要寻找自己附近的网约车时，LBS 应用就可以使用 GEORADIUS 命令：

例如，LBS 应用执行下面的命令时，Redis 会根据输入的用户的经纬度信息（116.054579，39.030452 ），查找以这个经纬度为中心的5公里内的车辆信息，并返回给LBS应用。当然， 你可以修改“5”这个参数，来返回更大或更小范围内的车辆信息。

GEORADIUS cars:locations 116.054579 39.030452 5 km ASC COUNT 10

另外，我们还可以进一步限定返回的车辆信息。比如，我们可以使用ASC选项，让返回的车辆信息按照距离这个中心位置从近到远的方式来排序，以方便选择最近的车辆；还可以使用COUNT选项，指定返回的车辆信息的数量。毕竟，5公里范围内的车辆可能有很多，如果返回全部信息，会占用比较多的数据带宽，这个选项可以帮助控制返回的数据量，节省带宽。

可以看到，使用 GEO 数据类型可以非常轻松地操作经纬度这种信息。

尽管 Redis 有如此多数据类型，但是有些场景下，我们对数据类型会有特殊需求。接下来就介绍 Redis 的自定义数据类型。这样你就可以定制符合自己需求的数据类型了。

3.2 如何自定义数据类型

为了实现自定义数据类型，首先，我们需要了解 Redis 的基本对象结构 RedisObject，因为 Redis 键值对中的每一个值都是用 RedisObject 保存的。

3.2.1 Redis 的基本对象结构：RedisObject

RedisObject 主要包括元数据和指针：

• 元数据主要用来区分不同的数据类型；
• 指针用来指向具体的值。

具体而言，RedisObject 内部包含：

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

RedisObject 结构借助 *ptr 指针，就可以指向不同的数据类型，例如， *ptr 指向一个 SDS 或一个跳表，就表示键值对中的值是 String 类型或 Sorted Set 类型。所以，我们在定义了新的数据类型后，也只要在 RedisObject 中设置好新类型的 type 和 encoding，再用 *ptr 指向新类型的实现，就行了。

3.2.2 开发一个新的数据类型

了解了 RedisObject 结构后，定义一个新的数据类型也就不难了。首先，我们需要为新数据类型定义好它的底层结构、type 和 encoding 属性值，然后再实现新数据类型的创建、释放函数和基本命令。

我以开发一个名字叫作 NewTypeObject 的新数据类型为例，来解释下具体的4个操作步骤：

---

第一步：定义新数据类型的底层结构

我们用 newtype.h 文件来保存这个新类型的定义，具体定义的代码如下所示：

struct NewTypeObject {
    struct NewTypeNode *head;
    size_t len;
} NewTypeObject;

其中，NewTypeNode 结构就是我们自定义的新类型的底层结构。我们为底层结构设计两个成员变量：一个是Long类型的value值，用来保存实际数据；一个是 *next 指针，指向下一个 NewTypeNode 结构。

struct NewTypeNode {
    long value;
    struct NewTypeNode *next;
};

从代码中可以看到，NewTypeObject 类型的底层结构其实就是一个 Long 类型的单向链表。当然，你还可以根据自己的需求，把 NewTypeObject 的底层结构定义为其他类型。例如，如果我们想要 NewTypeObject 的查询效率比链表高，就可以把它的底层结构设计成一颗B+树。

---

第二步：在RedisObject的type属性中，增加这个新类型的定义

这个定义是在 Redis 的 server.h 文件中。比如，我们增加一个叫作 OBJ_NEWTYPE 的宏定义，用来在代码中指代 NewTypeObject 这个新类型：

#define OBJ_STRING 0    /* String object. */
#define OBJ_LIST 1      /* List object. */
#define OBJ_SET 2       /* Set object. */
#define OBJ_ZSET 3      /* Sorted set object. */
…
#define OBJ_NEWTYPE 7

---

第三步：开发新类型的创建和释放函数

Redis 把数据类型的创建和释放函数都定义在了 object.c 文件中。所以，我们可以在这个文件中增加 NewTypeObject 的创建函数 createNewTypeObject，如下所示：

robj *createNewTypeObject(void){
   NewTypeObject *h = newtypeNew();
   robj *o = createObject(OBJ_NEWTYPE,h);
   return o;
}

createNewTypeObject 分别调用了 newtypeNew 和 createObject 两个函数，我分别来介绍下：

• newtypeNew 函数：用来为新数据类型初始化内存结构的。这个初始化过程主要是用zmalloc做底层结构分配空间，以便写入数据：

NewTypeObject *newtypeNew(void){
    NewTypeObject *n = zmalloc(sizeof(*n));
    n->head = NULL;
    n->len = 0;
    return n;
}

newtypeNew 函数涉及到新数据类型的具体创建，而 Redis 默认会为每个数据类型定义一个单独文件，实现这个类型的创建和命令操作，例如，t_string.c和t_list.c分别对应String和List类型。按照Redis的惯例，我们就把newtypeNew函数定义在名为 t_newtype.c 的文件中。

• createObject 函数：Redis本身提供的RedisObject创建函数，它的参数是数据类型的type和指向数据类型实现的指针

我们给 createObject 函数中传入了两个参数，分别是新类型的 type 值 OBJ_NEWTYPE，以及指向一个初始化过的 NewTypeObjec 的指针。这样一来，创建的 RedisObject 就能指向我们自定义的新数据类型了：

robj *createObject(int type, void *ptr) {
    robj *o = zmalloc(sizeof(*o));
    o->type = type;
    o->ptr = ptr;
    ...
    return o;
}

对于释放函数来说，它是创建函数的反过程，是用zfree命令把新结构的内存空间释放掉。

第四步：开发新类型的命令操作

简单来说，增加相应的命令操作的过程可以分成三小步：

1. 在 t_newtype.c 文件中增加命令操作的实现。比如说，我们定义 ntinsertCommand 函数，由它实现对 NewTypeObject 单向链表的插入操作：

void ntinsertCommand(client *c){
  //基于客户端传递的参数，实现在NewTypeObject链表头插入元素
}

2. 在 server.h 文件中，声明我们已经实现的命令，以便在 server.c 文件引用这个命令，例如：

void ntinsertCommand(client *c)

3. 在 server.c 文件中的 redisCommandTable 里面，把新增命令和实现函数关联起来。例如，新增的 ntinsert 命令由 ntinsertCommand 函数实现，我们就可以用 ntinsert 命令给 NewTypeObject 数据类型插入元素了：

struct redisCommand redisCommandTable[] = {
    ...
    {"ntinsert",ntinsertCommand,2,"m",...}
}

此时，我们就完成了一个自定义的 NewTypeObject 数据类型，可以实现基本的命令操作了。当然，如果你还希望新的数据类型能被持久化保存，我们还需要在 Redis 的 RDB 和 AOF 模块中增加对新数据类型进行持久化保存的代码，我会在后面的加餐中再和你分享。

3.3 小结

这一节要学习了 Redis 的扩展类型：GEO 类型。它可以记录经纬度形式的地理位置信息，被广泛地应用在LBS服务中。GEO 本身并没有设计新的底层数据结构，而是直接使用了 Sorted Set 集合类型。

GEO类型使用GeoHash编码方法实现了经纬度到Sorted Set中元素权重分数的转换，这其中的两个关键机制就是对二维地图做区间划分，以及对区间进行编码。一组经纬度落在某个区间后，就用区间的编码值来表示，并把编码值作为Sorted Set元素的权重分数。这样一来，我们就可以把经纬度保存到Sorted Set中，利用Sorted Set提供的“按权重进行有序范围查找”的特性，实现LBS服务中频繁使用的“搜索附近”的需求。

之后又讲解了在 Redis 中扩展自定义数据结构的方式。