
开发者逆向工程 Apache DataSketches 中 Kevin J. Lang 失传的 OCaml 代码
来源标题:Reverse-Engineering Kevin J. Lang's Lost OCaml Code in Apache DataSketches
一名开发者为 ScopeDB 实现 approx_count_distinct 时,在 Apache DataSketches 中发现 CPC 草图(CpcSketch)比 HLL 更省空间,但该库仅提供 Java 和 C++ 版本。他随后与其他 Rust 开发者合作推出 datasketches-rust 的初始版本,并与他人一起逆向工程了 Kevin J. Lang 编写的失传 OCaml 代码。ScopeDB 的去重计数已切换到该 Rust 实现。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
故事始于 ScopeDB 中的一个常规功能:为近似去重计数实现 approx_count_distinct。HyperLogLog(HLL)是教科书上的标准选择。早期 Rust 的 HLL 生态参差不齐,所以我先用了 Cloudflare 开源的 cardinality-estimator。但那个 crate 大量依赖 unsafe 代码和手工位打包技巧,为了让代码可审计、可控,我在 ScopeDB 内部分叉并维护了一份副本。
在评估替代方案时,我发现了 Apache DataSketches,它提供了久经考验的 HllSketch,以及空间效率更高的 CpcSketch。当时 Apache DataSketches 只提供 Java 和 C++ 实现,而 ScopeDB 是用 Rust 写的。结果,Apache DataSketches 社区对官方 Rust 移植很感兴趣。从去年年底开始,我与几位精通 sketching 算法的 Rust 开发者合作,构建并发布了 datasketches-rust 的初始版本,从 HllSketch 开始。不久之后,我把 ScopeDB 的去重计数切换到了我们自己的 datasketches-rust 实现。
任何实现过流式去重计数的人都清楚 HLL 的原理:元素被哈希到 K 个桶中,每个桶只保留目前见过的最大前导零数量(通常 4 到 6 位),而该桶中其他所有命中都不被记录。一旦 HLL 进入 dense 模式,每个桶都维护一个固定宽度的寄存器。
Yahoo! Research 的科学家 Kevin J. Lang 在 2017 年的论文《Back to the Future: an Even More Nearly Optimal Cardinality Estimation Algorithm》中提出回归基础:不再只保留每个桶的最大值,而是保留经典 FM85 优惠券收集过程完整的 K×64 位矩阵。每当第 r 行看到前导零数为 c 的哈希时,就将位 (r, c) 置为 1。保留完整的二维命中矩阵,使 CPC 能将流式 HIP 估计器与可合并的 ICON 估计器配对,从而获得比 HLL 更高的统计效率。在序列化时,它会调整布局以适配填充密度:低基数使用由 (行, 列) 对组成的稀疏 PairTable,而中高基数则结合滑动 8 位窗口、长度受限的 Huffman 编码和列置换,将 sketch 压缩到接近信息论熵极限。根据 DataSketches 文档,在相同精度下,序列化后的 CPC 比 HLL 节省 30% 到 40% 的存储空间。
一月底,我将 CpcSketch 移植到了 datasketches-rust(PR-75),并把 ScopeDB 切换到了它。它已在生产环境中平稳运行了六个多月。
然而,在从上游 C++ 和 Java 实现移植 CpcSketch 的过程中,我注意到源码中有几组硬编码的魔法查找表:
这四组静态表位于 compression_data.rs 和 estimator.rs 中。以下是简短摘录:
1 // datasketches/src/cpc/compression_data.rs 2 pub static LENGTH_LIMITED_UNARY_ENCODING_TABLE65: [u16; 65] = [ 3 // entropy: 2.0 4 // avg_length: 2.0249023437500000000; max_length = 12; num_symbols = 65 5 0x1000, 0x2001, 0x3003, 0x4007, // ... 6 ]; 7 pub static COLUMN_PERMUTATIONS_FOR_ENCODING: [[u8; 56]; 16] = [ 8 [0, 1, 2, 3, 5, 6, 7, 8, /* ... / 54, 55, 34, 14, 4], 9 // ... 10 ]; 11 pub static ENCODING_TABLES_FOR_HIGH_ENTROPY_BYTE: [[u16; 256]; 22] = [ 12 // entropy: 4.4619200780464778333 13 // avg_length: 4.5415773046232610355; max_length = 12; num_symbols = 256 14 [0x9017, 0x5009, 0x7033, 0x3002, / ... /], 15 // ... 16 ]; 17 18 // datasketches/src/cpc/estimator.rs 19 static ICON_POLYNOMIAL_COEFFICIENTS: [f64; ICON_TABLE_SIZE] = [ 20 // log K = 4 21 0.9895027971889700513, 0.3319496644645180128, 0.1242818722715769986, // ... 22 ]; 23 static ICON_LOW_SIDE_DATA: [u16; 33] = [ 24 //1, 2, 3, kappa 25 6037, 5720, 5328, // 4 1000000 26 // ... 27 ]; 28 static ICON_HIGH_SIDE_DATA: [u16; 33] = [ / ... / ]; 29 static HIP_LOW_SIDE_DATA: [u16; 33] = [ / ... / ]; 30 static HIP_HIGH_SIDE_DATA: [u16; 33] = [ / ... */ ];
每当我移植查找表时,我倾向于在单元测试中从第一性原理推导出这些值,并与静态数组逐元素比对。例如,对于 kxp_byte_lookup,我把推导直接保留在测试套件中:
1 for byte in 0u8..=255 { 2 // expected value 3 let expected = KXP_BYTE_TABLE[byte as usize]; 4 5 // computed value 6 let mut computed = 0.0; 7 for col in 0..8 { 8 let bit = (byte >> col) & 1; 9 if bit == 0 { 10 // note the inverted logic 11 computed += inv_pow2(col + 1); //note the "+1" 12 13 14 15 assert_eq!(expected, computed); 16
col) & 1; if bit == 0 { // note the inverted logic computed += inv_pow2(col + 1); //note the "+1" } } assert_eq!(expected, computed);}">
然而,对于 CompressionData 和 ICON 估计器的表,仓库中任何地方都不存在生成器源码,所以当时我无法自行推导它们。上游注释中只剩两条构建命令:
~/ocaml-4.03.0/bin/ocamlopt -o generateHuffmanCodes columnProbabilities.ml generateHuffmanCodes.ml ./generateHuffmanCodes > raw-encoding-tables.c raw-encoding-tables.c">
我搜索了每个 Apache DataSketches 仓库,都没有找到那些 .ml 文件。于是我在 datasketches-java 上开了 ISSUE-720,询问生成器源码在哪里。Lee Rhodes 回复说:
Kevin 的大部分数学模拟和建模都是用 OCaml 做的。他的代码在他的电脑上,而那台电脑已经不存在了。他的个人代码随他一起消失了……即使有人保留了他旧电脑的副本,那也可能是在大海捞针。
Kevin 于 2019 年 4 月去世,留在他个人机器上的任何代码实际上都已湮没于历史。
听到这个消息我很难过。Kevin 在 sketching 算法方面的研究构成了 Apache DataSketches 中许多核心 sketch 的基础:
(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。