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

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

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

阅读原文 »

2 收藏


直接登录

推荐关注