Golomb-coded sets 原理介绍

在我之前的《 H2O 中的 Cache-Aware Server Push 简介》这篇文章中，我写到：

H2O 将要推送的资源路径 + ETag 存入一个集合，采用 Golomb-compressed sets 算法生成指纹，并编码为 Base64 字符串存入 Cookie，之后 H2O 可以通过检查某个资源路径 + ETag 是否存在于 Cookie 指纹对应的集合之中来决定是否推送。

Golomb-compressed sets(GCS) 是一种空间利用率很高的数据结构，可以用于判断一个元素是否属于这个集合。它与 Bloom Filter 非常类似，区别是它的压缩率更高，同时查询效率更低。同样，GCS 也有将原本不属于集合的元素误判为属于的可能（false positive）。

H2O 将 GCS 算法用在记录 Push 过的资源集合非常合理：Cookie 往返于客户端和服务端之间，需要尽可能小；而需要 Push 资源数量通常不多，即使查询效率低一点也无大碍；同时 Server Push 属于锦上添花的功能，允许有一定的误判。

GCS 的实现原理并不复杂，本文试图用最简单的语言带领大家认识一下它。本文属于科普性质，给出的代码仅作示意，要在实际项目中使用 GCS，请参考本文最后给出的开源库。

HASH

首先定义一个数组集合，将它的长度记为 N。允许的误判率记为 1/P，本文假定 P=64，表示允许 1/64 的误判率。这部分准备工作的代码如下：

var encoded_words = ['alpha', 'bravo', 'charlie', 'delta', 'echo', 'foxtrot', 'golf', 'hotel', 'india', 'juliet', 'kilo', 'lima', 'mike', 'november', 'oscar', 'papa', 'quebec', 'romeo', 'sierra', 'tango', 'uniform', 'victor', 'whiskey', 'xray', 'yankee', 'zulu']; var N = encoded_words.length; var P = 64;

接着，将数组每一项都映射为范围在 [0, N * P) 之间的整数。为了让映射后的数字尽可能均匀分布，需要借助 MD5、SHA-1 等 Hash 函数。本文使用 MD5 实现映射函数：

function gcs_hash(str, N, P) {     var h = md5(str);     return parseInt(h.substring(24, 32), 16) % (N * P); }

将前面数组的每一项都进行 gcs_hash 处理：

var hashResult = encoded_words.map(function(word) { return gcs_hash(word, N, P) });

运行这段代码，得到如下结果：

[1017, 591, 1207, 151, 1393, 1005, 526, 208, 461, 1378, 1231, 192, 1630, 1327, 997, 662, 806, 1627, 866, 890, 1134, 269, 512, 831, 1418, 1525]

这样，N 个不定长的字符串被映射成为 N 个取值在 [0, N * P) 之间的整数了。

要检测一个元素是否在集合内，只需将待检测的元素以相同的 N、P 参数调用 gcs_hash ，通过检查 Hash 后的结果是否在前面算好的 Hash 数组即可。例如：

gcs_hash('apple', N, P) // 1535，1535 不在 Hash 数组内，故 apple 不在集合内。

显然，对于集合中存在的元素，Hash 值一定会在 Hash 数组内；但 Hash 值在 Hash 数组内的元素，并不一定在集合内，因为元素到 Hash 值是多对一的映射关系。

压缩

现在我们手头上已经有了一个可以用于检测的 Hash 数组，剩下的工作就是如何压缩它了。

将数组从小到大排序，如果 Hash 结果分布足够均匀，N 个取值为 [0, N * P) 的元素，相邻两者差值一定接近于 P。我们画出图表看一下：

Golomb-coded sets 原理介绍

上图中蓝线是 Hash 数组的各个点，黄线是 64 的倍数，可以看到二者基本能吻合。

接着，保留数组第一项，并将后续每一项都改为与前一项的差值（差值为 0 的情况直接跳过），这样数组每一项都比较接近 64 了。代码示意如下：

hashResult.sort(function(a, b) { return a -b }); var diffResult = [hashResult[0]]; for(var i = 0; i < N - 1; i++) {  var diff = hashResult[i+1] - hashResult[i];  if(diff === 0) {   continue;  }  diffResult.push(diff); }

这段代码运行结果如下：

[151, 41, 16, 61, 192, 51, 14, 65, 71, 144, 25, 35, 24, 107, 8, 12, 117, 73, 24, 96, 51, 15, 25, 107, 102, 3]

GCS 使用了 Golomb encoding（哥伦布编码）对上述数组做进一步处理。哥伦布编码是一个针对整数的变长编码方式，详细介绍可以看维基百科。这里简单介绍下：

哥伦布编码使用指定的整数 M 把输入的整数分成两部分：商数 q、余数 r。商数当做一元编码，而余数放在后面做为可缩短的二进制编码。

将整数变为一元编码非常简单：q 的一元编码结果就是 q 个 1 加上 1 个 0。如下表：

整数	一元编码
0	0
1	10
2	110
3	1110
4	11110
5	111110
6	1111110

一元编码可以用以下代码实现；

function unary_encoding(q) {     return 1 << (q + 1)) - 2; }

将 M 选为 64 时，余数取值区间为 [0, 64)，只需要用 6 位二进制表示。将待处理的数组每一项都除以 64，并将商数和余数分别做一元编码和二进制编码，得到如下结果：

整数	商数	余数	商数一元编码	余数二进制编码
151	2	23	110	010111
41	0	41	0	101001
16	0	16	0	010000
61	0	61	0	111101
192	3	0	1110	000000
51	0	51	0	110011
14	0	14	0	001110
65	1	1	10	000001
71	1	7	10	000111
144	2	16	110	010000
25	0	25	0	011001
35	0	35	0	100011
24	0	24	0	011000
107	1	43	10	101011
8	0	8	0	001000
12	0	12	0	001100
117	1	53	10	110101
73	1	9	10	001001
24	0	24	0	011000
96	1	32	10	100000
51	0	51	0	110011
15	0	15	0	001111
25	0	25	0	011001
107	1	43	10	101011
102	1	38	10	100110
3	0	3	0	000011

表格中每一行后两列拼起来就是该整数对应的哥伦布编码，可以看到，64 以下的整数编码后会变短。这部分代码实现如下：

function golomb_enc(arr, P) {     return arr.map(function(n) {  var q = n / P | 0;  var r = n % P;  return ((1 << (q + 1)) - 2).toString(2) + (r + P).toString(2).slice(1);     }); } var golombResult = golomb_enc(diffResult, P);

这段代码运行结果如下：

["110010111", "0101001", "0010000", "0111101", "1110000000", "0110011", "0001110", "10000001", "10000111", "110010000", "0011001", "0100011", "0011000", "10101011", "0001000", "0001100", "10110101", "10001001", "0011000", "10100000", "0110011", "0001111", "0011001", "10101011", "10100110", "0000011"]

最终结果有 197 位，25 个字节：

理论上，要实现单元素 1/64 的误判率最少只需要 6 位，26 个元素就是 156 位。GCS 的编码结果比理论值大了 26.3%，但仍优于 Bloom Filter。实际使用中，为了考虑解码通用性，一般会将 N 和 P 按照约定好的长度进行编码，追加到最终结果的开始。编码结果最后不足一字节的部分也需要补全，所以还会有一些额外开销。但是 N 和 P 越大，最终编码长度就越接近于理论值。H2O 默认使用的 P 是 8192（2^13）。

查询时，只需要将上述步骤倒过来得到 Hash 数组即可，这里不在赘述。由于 Hash 数组分布比较均匀，可以将它分为多个区间来提高查询效率。

参考：