❗ 本文最后更新于 3279 天前,文中所描述的信息可能已发生改变,请谨慎使用。
在我之前的《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。我们画出图表看一下:
上图中蓝线是 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 unary_encoding(q).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 个字节:
11001011 10101001 00100000 11110111
10000000 01100110 00111010 00000110
00011111 00100000 01100101 00011001
10001010 10110001 00000011 00101101
01100010 01001100 01010000 00110011
00011110 01100110 10101110 10011000
00011
理论上,要实现单元素 1/64 的误判率最少只需要 6 位,26 个元素就是 156 位。GCS 的编码结果比理论值大了 26.3%,但仍优于 Bloom Filter。实际使用中,为了考虑解码通用性,一般会将 N 和 P 按照约定好的长度进行编码,追加到最终结果的开始。编码结果最后不足一字节的部分也需要补全,所以还会有一些额外开销。但是 N 和 P 越大,最终编码长度就越接近于理论值。H2O 默认使用的 P 是 8192(213)。
查询时,只需要将上述步骤倒过来得到 Hash 数组即可,这里不再赘述。由于 Hash 数组分布比较均匀,可以将它分为多个区间来提高查询效率。
参考:
本文链接:https://imququ.com/post/golomb-coded-sets.html,参与评论 »
--EOF--
发表于 2015-11-16 08:54:53,并被添加「H2O」标签。查看本文 Markdown 版本 »
Comments
Waline 评论加载中...