Redis 高阶数据类型重温

2021 年 10 月 22 日
筆記
Redis

今天这个专题接着上一篇 Redis 的基本数据类型继续讲解剩下的高阶数据类型：BitMap、HyperLogLog 和 GEO hash。这些数据结构的底层也都是基于我们前面说的 5 种基本类型，但是实现上有很多 Redis 自己的创意。下面我们一起进入高阶数据结构的世界。

BitMap

BitMap 从字面意义上能看出是一个字节组成的集合。由于一个比特位只有 0 和 1 两种状态，所以 BitMap 能应用的场景是有限的，只能对这种二值的场景进行使用。BitMap 底层是怎么实现的呢？

Redis 底层只有我们上文说的 5 种基本数据类型，BitMap 并不是一种新型的数据结构，而是基于 Redis 的 string 类型的 SDS 结构来实现的。

SDS 的数据存储在 buf 字节数组中，1 byte = 8 bit。那么将这个字节数组连起来就是很多个 8 bit 组成的比特位数组。我们可以将数组的下标当做要存储的 key，数组的值 0 或者 1 就是 value。

为了验证这个存储逻辑，我们可以使用 Redis 命令行来手动调试一下：

# 首先将偏移量是0的位置设为1
127.0.0.1:6379> setbit csx:key:1 0 1
(integer) 0
# 通过STRLEN命令，我们可以看到字符串的长度是1
127.0.0.1:6379> STRLEN csx:key:1
(integer) 1
# 将偏移量是1的位置设置为1
127.0.0.1:6379> setbit csx:key:1 1 1
(integer) 0
# 此时字符串的长度还是为1，以为一个字符串有8个比特位，不需要再开辟新的内存空间
127.0.0.1:6379> STRLEN csx:key:1
(integer) 1
# 将偏移量是8的位置设置成1
127.0.0.1:6379> setbit csx:key:1 8 1
(integer) 0
# 此时字符串的长度编程2，因为一个字节存不下9个比特位，需要再开辟一个字节的空间
127.0.0.1:6379> STRLEN csx:key:1
(integer) 2

通过上面的实验我们可以看出，BitMap 占用的空间，就是底层字符串占用的空间。假如 BitMap 偏移量的最大值是 OFFSET_MAX，那么它底层占用的空间就是：

(OFFSET_MAX/8)+1 = 占用字节数

因为字符串内存只能以字节分配，所以上面的单位是字节。

但是需要注意，Redis 中字符串的最大长度是 512M，所以 BitMap 的 offset 值也是有上限的，其最大值是：

8 * 1024 * 1024 * 512  =  2^32

由于 C语言中字符串的末尾都要存储一位分隔符，所以实际上 BitMap 的 offset 值上限是：

(8 * 1024 * 1024 * 512) -1  =  2^32 - 1

了解了 BitMap 的实现逻辑以及在 Redis 中的存储逻辑之后我们对 Redis 提供的命令应该就有了更深刻的认识。

HyperLogLog

基数估计(Cardinality Estimation) 一直是大数据领域的重要问题之一。基数估计就是为了估计在一批数据中它的不重复元素有多少个。

这个问题的应用场景非常之多，比如对于百度，谷歌这样的大搜索引擎，要统计每天每个地区有多少人访问网站，在这种统计中十亿和十亿零三千的区别并不是很大，只需要一个近似的值即可。

如果去考虑实现，我们首先想到的就是字典。对于新来的元素，查一下是否已经属于这个字典，不属于则添加进去，这个字典的整体长度就是我们要的结果。方法虽然好并且还精确，但是带来的后果就是空间复杂度会很高，数据量大的情况下，使用的空间可能超过我们的想象。

那么是否存在一些近似的方法，可以估算出大数据的基数呢？伯努利过程可以用来做基数统计。

伯努利过程

伯努利过程就是一个抛硬币实验的过程。抛一枚硬币只会有两种结果：正面，反面，概率都是 1/2。伯努利过程就是一直抛硬币直到出现正面为止，并记录下此时抛掷的次数 K。比如说抛一次硬币就出现了正面， k = 1；或者直到第三次才出现正面，那么 k=3。伯努利试验是在同样的条件下重复地、相互独立地进行的一种随机试验，其中“在相同条件下”意在说明：每一次试验的结果不会受其它实验结果的影响，事件之间相互独立。

对于 n 次伯努利实验，我们会得到 n 个出现正面的投掷次数，k₁, k₂,k₃…k_n。这其中最大的值是 k_max，接下来我们省略一大堆数学推导过程，直接来到结论的部分：

n = 2 ^k_max

即可以根据最大投掷次数来近似估计进行了几次伯努利过程。比如：

第一次实验：抛 3 次出现正面，k = 3，n = 2³;

第二次实验：抛 2 次出现正面，k = 2，n = 2²；

第三次实验：抛 5 次出现正面，k = 5，n = 2⁵；

……

第 n 次实验：抛 7 次出现正面，k = 7，我们根据公式可以预估 n = 2⁷。

根据上面的示例大家基本了解伯努利过程是什么。在实验次数较少的条件下（即进行伯努利过程次数少的情况）我们预估出来的 n 值肯定是有较大误差的。比如上面的抛硬币实验一共就进行了 3 次就出现了正面，此时你预估 n=2³ 这个值可能跟再抛多次出现的值有一定的误差。

Redis 中的 HyperLogLog 就是基于伯努利过程的原理来统计集合基数的，当然对于消除误差， Redis 也做了一些处理。

HyperLogLog 如何模拟伯努利过程

HyperLogLog 基于 LogLog Counting 算法改进而来。在添加元素的时候，HyperLogLog 通过 MurmurHash64A 算法给元素计算出一个 64bit 的 hash 值来模拟伯努利过程。

例如 17， hash Value = 10001，hash value 总共是64 bit 所以前面的位置都是 0。这些 byte 位就类似于一次抛硬币的伯努利过程，0 代表抛硬币落地式反面，1 代表抛硬币落地式正面。LogLog Counting 的基本思想是：

对每个待测集合中的元素 x，计算它的哈希值 hash = H(x)；
将哈希值 hash 通过它们的前 k=logm 个比特分组（即分桶），作为桶的编号，即一共有 m 个桶；
将 hash 的后 L – k 个比特作为真正参与基数估计的串 s，计算并记录下所有桶内的 ρ(s)；
令 M[k] 表示第 k 个桶内所有元素中最大的那个 ρ 值，那么该集合基数的估计量为：

Ñ = αm · m · 2ΣM[i] / m

其中 αm 是修正参数。

LogLog Counting 在误差精简上并没有比它的前辈 F-M 算法小，反而还大了。但是它真正有意义的是降低了空间复杂度，F-M 算法中用 logN 个比特位来存储 hash 值，而 LogLog Counting 算法只存储下标（即 ρ 值）。可以降低为 log(logN) 个比特位，再加上分桶数为 m，所以空间复杂度为：

O[m* log(logN)]

这也是 LogLog Counting 算法名字的由来。

Redis 基于节省内存空间的原因在 LogLog Counting 算法的基础上做了一些优化，优化的目的是减少误差和变态地更加节省内存！Hyper 是“超越”的含义，那么HyperLogLog 到底比前辈超越在哪里呢？

第一是分桶几何平均数改为计算 m 个桶的 调和平均数。

调和平均数

调和平均数区别于几何平均数概念。几何平均数=总数/个数，但是会有一个问题：马云的平均年收入是100 亿，我的平均年收入是 0.00000001 亿，我和马云的平均年收入是100亿，没毛病。

使用调和平均数就能解决这个问题，调和平均数的结果会趋向于集合中比较小的数，x₁ 到 x_n 的调和平均数符合如下公式：

根据这个公式计算我和马云的平均工资：

平均工资 = 2 / (1/1亿 + 1/0.00000001亿) = 20元

这样算起来，我还能接受！

几何平均值受离群值（偏离均值很大的值）的影响非常大，分桶的空桶越多，LLC 的估计值就越不准。使用调和平均值就不会受这种影响。

第二是根据基数估值的大小采用不同的估计方法进行修正。论文中给出了在常见情况：即被估集合的基数在亿级别以下，m 取值在 2[4, 16] 区间下的修正的算法。

对应到 Redis 代码实现，Redis 使用了 2¹⁴= 16384个桶，按照标准差误差为 0.81%，精度相当高。HLL 将 64 bit 的低 14 位拿出来作为对应桶的序号，14 bit 可以表示 2¹⁴ = 16384 个桶。剩下的 50 个比特用来做基数估计。而 2⁶=64，所以只需要用 6 个比特表示下标值。

假设一个字符串的前 14 位是：00 0000 0000 00110，十进制 = 6，那么该基数将会被放到编号为 6 的桶中。在一般情况下，一个 HLL 数据结构占用内存的大小为16384 * 6 / 8 = 12kB，Redis将这种情况称为密集（dense）存储。

为了更高效的说清楚 Redis 的实现，我们先看 Redis 对 HLL 的定义,Redis 使用 hllhdr 来持有一个 HLL：

struct hllhdr {
    char magic[4];      /* "HYLL" */
    // 编码格式：sparse或者dense
    uint8_t encoding;   /* HLL_DENSE or HLL_SPARSE. */
    uint8_t notused[3]; /* Reserved for future use, must be zero. */
    // 缓存的基数统计值
    uint8_t card[8];    /* Cached cardinality, little endian. */
    // 实际的寄存器们，dense有16384个6bit寄存器
    uint8_t registers[]; /* Data bytes. */
};

从上述结构体可以大致看出，Redis 实现的 HLL 结构大致分为两部分：

头部信息
存储桶数据的 registers

为了减少计算的成本，Redis 的 HLL 实现使用 card 来保存基数估计的最新计算结果，card 字段采用小端存储，用最高有效位来标识 card 内存储的结果是否还有效。由于 Redis 的 HLL 实现使用了 16384 个分组，基于前文所述的 HLL 的标准差计算方法，Redis 的 HLL 实现的误差是，也就是 Redis 官方文档中公布的误差率。

encoding 标识当前 HLL 结构所使用的编码方式，一共有两种：

sparse(稀疏存储)
dense(密集存储)

稀疏存储

在 HLL 初始化的时候数据量很少，如果还是使用固定位数来存储 16384 个桶的话大量的空间就被浪费。所以 Redis 使用稀疏编码(HLL_SPARSE)初始化一个新的 HLL 结构，它是具有压缩性质的编码，将重复的分组计数压缩成操作码(opcode)，以此降低内存使用。为了节省空间 Redis 会将连续的全 0 桶压缩成 0 桶计数值。该计数值可以用单字节或双字节表示，高 2bit 为标志位，因此可以分别表示连续 64 个全 0 桶和连续 16384 个全 0 桶。

稀疏编码使用 ZERO、XZERO、VAL 三种操作码对registers存储的数据进行编码，其中 ZERO、VAL 占一个字节，XZERO 占两个字节：

当 多个连续桶的计数值都是零 时，Redis 提供了几种不同的表达形式：

ZERO：操作码为00xxxxxx，前缀两个零表示接下来的 6bit 整数值加 1 就是零值计数器的数量，注意这里要加 1 是因为数量如果为零是没有意义的。6位 xxxxxx 表示有 1 到 64(111111+1，0 没有意义)个连续分组为空。比如 00010101 表示连续 22 个零值计数器。
XZERO：操作码表示为01xxxxxx yyyyyyyy，6bit 最多只能表示连续 64 个零值计数器，这样扩展出的 14bit 可以表示最多连续 16384 个零值计数器。这意味着 HyperLogLog 数据结构中 16384 个桶的初始状态，所有的计数器都是零值，可以直接使用 2 个字节来表示。
VAL：操作码表示为1vvvvvxx，中间 5bit 表示计数值，尾部 2bit 表示连续几个桶。它的意思是连续 (xx +1) 个计数值都是 (vvvvv + 1)。比如 10101011 表示连续 4 个计数值都是 11。

注意 上面第三种方式 的计数值最大只能表示到 32，而 HLL 的密集存储单个计数值用 6bit 表示，最大可以表示到 63。当稀疏存储的某个计数值需要调整到大于 32 时，Redis 就会立即转换 HLL 的存储结构，将稀疏存储转换成密集存储。

密集存储

HLL 的密集编码(HLL_DENSE)结构是由稀疏编码转换而来的，它的结构相对简单，由连续 16384 个桶拼接而成，每个组占用 6 位(16384×6/8，12KB的由来)。不过由于存储采用的是小端模式，所以每个桶的 6bit 计数值是从 LSB(低位) 开始一个接一个地编码到 MSB(高位)(区别于大端模式即正常的数字是从左到右依次是高位到低位，小端模式是从左到右依次是低位到高位)。

密集存储涉及到一个定位字节的问题，因为一个桶是 6bit，而一个字节是 8bit，那么必然会涉及到一个字节持有两个桶的情况。这种情况下给定一个桶的编号如何定位到对应的桶呢？

假设桶的编号为 idx，这个 6bit 计数值的起始字节位置偏移用 offset_bytes 表示，它在这个字节的起始比特位置偏移用 offset_bits 表示。我们有：

offset_bytes = (idx * 6) / 8offset_bits = (idx * 6) % 8

前者是商，后者是余数。比如 bucket 2 的字节偏移是 1，也就是第 2 个字节。它的位偏移是4，也就是第 2 个字节的第 5 个位开始是 bucket 2 的计数值。需要注意的是字节位序是左边低位右边高位。

如果 offset_bits 小于等于 2，那么这 6bit 在一个字节内部，可以直接使用下面的表达式得到计数值 val

val = buffer[offset_bytes] >> offset_bits  # 向右移位

如果 offset_bits 大于 2，那么就会跨越字节边界，这时需要拼接两个字节的位片段。

低位值 low_val = buffer[offset_bytes] >> offset_bits
低位个数 low_bits = 8 - offset_bits 
拼接，保留低6位 val = (high_val << low_bits | low_val) & 0b111111

总体来说，HLL 存储结构将内存使用优化到极致，以 12k 的空间来估算最多 2⁶⁴ 个不同元素的基数。并且优化了基数结果的误差范围为 0.81 %。如果我们有海量数据查询的需求，可以考虑使用 HLL。

GEO

GEO 算法是一种地理位置距离排序算法，将二维的经纬度数据映射到一维的整数上。这样所有的元素都将挂载到一条线上，距离靠近的二维坐标映射到一维后的点之间距离会很接近。当我们想要计算附近的人时，首先将目标位置映射到这条线上，然后在这条一维的线上获取附近的点就行。

对应到我们的地球经纬度信息来说，纬度区间为[-90, 90]，经度区间为 [-180,180]。如何将二维的坐标转换为一维的值呢？下面我们一起演示一下当前的处理手段。首先我们把地球经纬度坐标展开为一张平面：

首先我们将整幅地图分割成四个小块，然后用简单的 01 编码来标识每个小块：

这样整个地图被我们分割为 4 个空间，每个空间用一维的 01 来标识。如果地点 A 坐落于 00 空间，那么它的一维标识就是 00。当然你会说这么大一块空间都用 00 标识这范围也太大了吧。既然我们可以分割为 4 块，你是不是顺推就知道我们可以继续分割为 8,16,100，甚至更大都可以，这样我们每一块空间所标识的范围更精确，搜索地理位置也更精确。

根据这个原理我们可以通过最小逼近的准则来用一维字符串表达相似准确的最小位置。比如北京市区坐标为：北纬39.9”，东经116. 3”，那么我们可以按照如下算法对北京的经纬度进行逼近编码：

纬度区间为[-90, 90]，一分为二为[-90, 0),[0 , 90]，称为左右区间，北京在北纬 39.9，那么在右区间，给标记为 1；
接着将区间[0, 90] 二分为[0, 45), [45, 90]，可以确定 39.9 在左区间，标记为 0；
递归上述过程，可以确定 39.9 总是属于某个细小的区间 [x, y]，随着迭代的越多，那么这个区间会越来越逼近 39.9 ；
通过对纬度这样划分，属于左区间记录 0 ，属于右区间记录 1，那么最终会得到一个关于纬度的 01 编码，编码长度取决于区间划分的粒度。
同理经度也是如此划分。

假设经过上述计算，纬度产生的编码为 1001000101，经度产生的编码为 0100100101。我们把经纬度组合成一个串，这个串的偶数位放经度，奇数位放纬度，把两串编码组合成一个新串：

01100001100000110011

最后使用用 0-9、b-z（去掉a, i, l, o）这 32 个字母进行 base32 编码，首先将 01100 00110 00001 10011 转成十进制，对应着 12、6、1、19 十进制对应的编码就是：MGBT。同理，将编码转换成经纬度的解码算法与之相反。

RFC 4648 Base32 字母表

值	符号	值	符号	值	符号	值	符号
0	A	8	I	16	Q	24	Y
1	B	9	J	17	R	25	Z
2	C	10	K	18	S	26	2
3	D	11	L	19	T	27	3
4	E	12	M	20	U	28	4
5	F	13	N	21	V	29	5
6	G	14	O	22	W	30	6
7	H	15	P	23	X	31	7
填充	=

通过这种加密之后我们就把经纬度转换为很短的几个字母来表示。

空间填充曲线

上面我们将空间划分为很多个小范围之后，我们是按照范围从大到小进行逼近，那么对应到地图逼近的顺序是什么呢？这里就提到了空间曲线的概念，即我们从哪里开始遍历，遍历的顺序又是如何。

在数学分析中，有这样一个难题：能否用一条无限长的线，穿过任意维度空间里面的所有点？ 常见的有： Z阶曲线(Z-order curve)、皮亚诺曲线（Peano curve）、希尔伯特曲线（Hilbert curve），之后还有很多变种的空间填充曲线，龙曲线(Dragon curve)、高斯帕曲线(Gosper curve)、Koch曲线(Koch curve)、摩尔定律曲线(Moore curve)、谢尔宾斯基曲线(Sierpiński curve)、奥斯古德曲线(Osgood curve)等。

Z 阶曲线（Z-order curve）是 GEO hash 目前再用的空间填充曲线：

这个曲线比较简单，生成也比较容易，秩序要把每个 Z 首位相连即可。 Geohash 能够提供任意精度的分段级别。一般分级从 1-12 级。利用 Geohash 的字符串长短来决定要划分区域的大小，一旦选定 cell 的宽和高，那么 Geohash 字符串的长度就确定下来了。地图上虽然把区域划分好了，但是还有一个问题没有解决，那就是如何快速的查找一个点附近邻近的点和区域呢？

Geohash 有一个和 Z 阶曲线相关的性质，那就是一个点附近的地方(但不绝对) hash 字符串总是有公共前缀，并且公共前缀的长度越长，这两个点距离越近。由于这个特性，Geohash 就常常被用来作为唯一标识符。用在数据库里面可用 Geohash 来表示一个点。Geohash 这个公共前缀的特性就可以用来快速的进行邻近点的搜索。越接近的点通常和目标点的 Geohash 字符串公共前缀越长（特殊情况除外）。

前面说 Geohash 编码的时候提到 Geohash 码生成规划： “偶数位放经度，奇数位放纬度”。这个规则就是 Z 阶曲线。看下图：

x 轴就是纬度，y 轴就是经度。经度放偶数位，纬度放奇数位就是这样而来的。

但是 Z 阶曲线有个问题：它的突变性问题会导致某些编码位置相邻但是距离缺很远。比如上图中的 001000 和 000111，编码相邻，距离却很大。

除了 Z 阶曲线外，工人效果最好的是 Hilbert Curve 希尔伯特曲线，希尔伯特曲线是一种能填充满一个平面正方形的分形曲线（空间填充曲线），由大卫·希尔伯特在 1891 年提出。由于它能填满平面，它的豪斯多夫维是2。取它填充的正方形的边长为 1，第 n 步的希尔伯特曲线的长度是 2ⁿ – 2^(-n)。

一阶的希尔伯特曲线，生成方法就是把正方形四等分，从其中一个子正方形的中心开始，依次穿线，穿过其余 3 个正方形的中心。如下图：

二阶的希尔伯特曲线，生成方法就是把之前每个子正方形继续四等分，每 4 个小的正方形先生成一阶希尔伯特曲线。然后把 4 个一阶的希尔伯特曲线首尾相连。

n 阶的希尔伯特曲线 的生成方法也是递归的，先生成 n-1 阶的希尔伯特曲线，然后把 4 个 n-1 阶的希尔伯特曲线首尾相连。

希尔伯特曲线空间曲线的优点在于对多维空间有效的降维。如下图就是希尔伯特曲线在填满一个平面以后，把平面上的点都展开成一维的线了。另外希尔伯特曲线是连续的，所以能保证一定可以填满空间。

Redis 没有选择效果更好的希尔伯特曲线来实现低位位置划分而是使用 Z 阶曲线这个官方并没有说明，大概只是 Z 阶曲线的实现相对来说要简单一些。另外关于 Z 阶曲线边界点距离问题，Redis 也有修正，除了使用定位点的 GEOhash 编码之外，目前比较通行的做法就是我们不仅获取当前我们所在的矩形区域，还获取周围 8 个矩形块中的点。那么怎样定位周围 8 个点呢？关键就是需要获取周围 8 个点的经纬度，那我们已经知道自己的经纬度，只需要用自己的经纬度减去最小划分单位的经纬度就行。因为我们知道经纬度的范围，有知道需要划分的次数，所以很容易就能计算出最小划分单位的经纬度。

通过上面这张图，我们就能很容易的计算出周围 8 个点的经纬度，有了经纬度就能定位到周围 8 个矩形块。这样我们就能获取包括自己所在矩形块的 9 个矩形块中的所有的点。最后分别计算这些点和自己的距离（由于范围很小，点的数量就也很少，计算量就很少）过滤掉不满足条件的点就行。

在 Redis 中，查找某个中心地理位置（longitude,latitude）周围 radius 范围内的点，先根据 latitude 和 radius 计算出经纬度二进制编码的长度 step，即划分的次数，然后根据中心地理位置（longitude,latitude）、radius、step 计算出中心位置的二进制编码，再计算出周边 8 个位置块的二进制编码，再依次计算 9 个位置块中的点是否满足距离要求。

GEOhash 在 Redis 中的实现方式如下：

typedef struct {
    double min;
    double max;
} GeoHashRange;
typedef struct {
    uint64_t bits;
    uint8_t step;
} GeoHashBits;

int geohashEncode(const GeoHashRange *long_range, const GeoHashRange *lat_range,
              double longitude, double latitude, uint8_t step,
              GeoHashBits *hash) {
    /* Check basic arguments sanity. */
    if (hash == NULL || step > 32 || step == 0 ||
        RANGEPISZERO(lat_range) || RANGEPISZERO(long_range)) return 0;

    /* Return an error when trying to index outside the supported
     * constraints. */
    if (longitude > 180 || longitude < -180 ||
        latitude > 85.05112878 || latitude < -85.05112878) return 0;

    hash->bits = 0;
    hash->step = step;

    if (latitude < lat_range->min || latitude > lat_range->max ||
        longitude < long_range->min || longitude > long_range->max) {
        return 0;
    }

    double lat_offset =
        (latitude - lat_range->min) / (lat_range->max - lat_range->min);
    double long_offset =
        (longitude - long_range->min) / (long_range->max - long_range->min);

    /* convert to fixed point based on the step size */
    lat_offset *= (1ULL << step);
    long_offset *= (1ULL << step);
    hash->bits = interleave64(lat_offset, long_offset);
    return 1;
}

long_range 和 lat_range 为地球经纬度的范围；hash->bits 用户保存最终二进制编码结果，hash->step 是经纬度划分的次数，在 Redis 中该值为 26，即经度/纬度的二进制编码长度为 26，最终经交叉组合而成的地理位置的二进制编码为 52 位。Base32 编码为每 5bits 组成一个字符，所以最终的 GeoHash 字符串为 11 位。

为什么是 52 位？因为在 Redis 中是把地理位置编码后的二进制值存入 zset 数据结构中，double 类型的尾数部分长度为 52 位。

上述算法在分别计算经度/纬度的二进制编码时，是先计算所求地理位置的经度/纬度在整个经度/纬度范围内的偏移，再乘以 2 的 step 次方。划分 step 次，会得到 2 的 step 次方个区域，区域值为 0 -（1<<step-1），所以偏移乘以 2 的 step 次方即可得到划分 step 次时改经度/纬度的二进制编码。

Redis 中处理这些地理位置坐标点的思想是: 二维平面坐标点 –> 一维整数编码值 –> zset(score为编码值) –> zrangebyrank(获取score相近的元素)、zrangebyscore –> 通过score(整数编码值)反解坐标点 –> 附近点的地理位置坐标。

Tags: Redis