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。我们画出图表看一下:

hash-data-sorted

上图中蓝线是 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 数组分布比较均匀,可以将它分为多个区间来提高查询效率。

参考:

本文链接:参与评论 »

--EOF--

提醒:本文最后更新于 385 天前,文中所描述的信息可能已发生改变,请谨慎使用。

Comments