逆向工程 Apache DataSketches 中 Kevin J. Lang 丢失的 OCaml 代码
Reverse-Engineering Kevin J. Lang's Lost OCaml Code in Apache DataSketches

原始链接: https://www.tisonkun.io/posts/ai-repair-program/

ScopeDB 的近似去重计数从 HyperLogLog 迁移到 CPC,通过 Apache DataSketches 的 Rust 移植实现。移植 CPC 暴露了硬编码的查找表,其原始生成器已丢失。作者与 AI 模型以检入的数组和头文件注释为神谕,逆向工程了 Huffman 表、列置换、多项式系数和常量,随后在 PR-355 中添加了构造性测试。该工作将部分推导逐位验证,利用消融实验证伪看似合理的解释,并对置信度表进行蒙特卡洛检查。同时记录了局限:某些模型在浮点容差内仍无法区分,且无原始种子时无法精确复现随机表。结果是一个更可审计的 Rust 实现,加上详细的数学取证。

黑客新闻 最新 | 过去 | 评论 | 提问 | 展示 | 工作 | 提交 登录 逆向工程 Apache DataSketches 中 Kevin J. Lang 丢失的 OCaml 代码 (tisonkun.io) 5 分,由 tison,1 小时前 隐藏 | 过去 | 收藏 | 讨论 帮助 指南 | 常见问题 | 列表 | API | 安全 | 法律 | 申请 YC | 联系 搜索:
相关文章

原文

It started with a routine feature in ScopeDB: implementing approx_count_distinct for approximate distinct counting.

HyperLogLog (HLL) is the standard textbook choice. Early on, Rust’s HLL ecosystem was uneven, so I started with Cloudflare’s open-source cardinality-estimator. That crate leaned heavily on unsafe code and manual bit-packing tricks, though, so to keep things auditable and under our control, I forked and maintained an internal copy inside ScopeDB.

While evaluating alternatives, I came across Apache DataSketches, which offered a battle-tested HllSketch alongside CpcSketch, an even more space-efficient design. At the time, Apache DataSketches only shipped Java and C++ implementations, whereas ScopeDB is written in Rust.

As it turned out, the Apache DataSketches community was interested in an official Rust port. Starting late last year, I teamed up with a few other Rust developers well-versed in sketching algorithms to build and ship the initial releases of datasketches-rust, beginning with HllSketch. Soon after, I switched ScopeDB’s distinct counting over to our datasketches-rust implementation.

Apache DataSketches Rust Contributors
Apache DataSketches Rust Contributors

Anyone who has implemented streaming distinct counting knows how HLL works: elements are hashed into KK buckets, and each bucket keeps only the maximum leading-zero count seen so far (typically 4 to 6 bits), while every other hit in that bucket goes unrecorded. Once HLL enters dense mode, every bucket maintains a fixed-width register.

In his 2017 paper Back to the Future: an Even More Nearly Optimal Cardinality Estimation Algorithm, Yahoo! Research scientist Kevin J. Lang proposed going back to basics: instead of keeping only per-bucket maxima, retain the full K×64K \times 64

In late January, I ported CpcSketch to datasketches-rust (PR-75) and switched ScopeDB over to it. It has run smoothly in production for more than six months.

https://github.com/apache/datasketches-rust/pull/75
https://github.com/apache/datasketches-rust/pull/75

While porting CpcSketch from the upstream C++ and Java implementations, however, I noticed several hardcoded magic lookup tables in the source code:

  1. 23 static Huffman encoding tables
  2. 16 sliding-window column permutations
  3. 23 sets of degree-19 polynomial correction coefficients
  4. 4 empirical confidence-interval quantile tables

These four sets of static tables live in compression_data.rs and estimator.rs. Here is a short excerpt:

// datasketches/src/cpc/compression_data.rs

pub static LENGTH_LIMITED_UNARY_ENCODING_TABLE65: [u16; 65] = [

// avg_length: 2.0249023437500000000; max_length = 12; num_symbols = 65

0x1000, 0x2001, 0x3003, 0x4007, // ...

pub static COLUMN_PERMUTATIONS_FOR_ENCODING: [[u8; 56]; 16] = [

[0, 1, 2, 3, 5, 6, 7, 8, /* ... */ 54, 55, 34, 14, 4],

pub static ENCODING_TABLES_FOR_HIGH_ENTROPY_BYTE: [[u16; 256]; 22] = [

// entropy: 4.4619200780464778333

// avg_length: 4.5415773046232610355; max_length = 12; num_symbols = 256

[0x9017, 0x5009, 0x7033, 0x3002, /* ... */],

// datasketches/src/cpc/estimator.rs

static ICON_POLYNOMIAL_COEFFICIENTS: [f64; ICON_TABLE_SIZE] = [

0.9895027971889700513, 0.3319496644645180128, 0.1242818722715769986, // ...

static ICON_LOW_SIDE_DATA: [u16; 33] = [

6037, 5720, 5328, // 4 1000000

static ICON_HIGH_SIDE_DATA: [u16; 33] = [ /* ... */ ];

static HIP_LOW_SIDE_DATA: [u16; 33] = [ /* ... */ ];

static HIP_HIGH_SIDE_DATA: [u16; 33] = [ /* ... */ ];

Whenever I port lookup tables, I prefer to derive the values from first principles in unit tests and check them element by element against the static array. For kxp_byte_lookup, for example, I kept the derivation right inside the test suite:

let expected = KXP_BYTE_TABLE[byte as usize];

let bit = (byte >> col) & 1;

// note the inverted logic

computed += inv_pow2(col + 1); //note the "+1"

assert_eq!(expected, computed);

For CompressionData and the ICON estimator tables, though, no generator source existed anywhere in the repositories, so I had no way to derive them on my own back then. Only two build commands remained in an upstream comment:

~/ocaml-4.03.0/bin/ocamlopt -o generateHuffmanCodes columnProbabilities.ml generateHuffmanCodes.ml

./generateHuffmanCodes > raw-encoding-tables.c

I searched every Apache DataSketches repository and came up empty on those .ml files. So I opened ISSUE-720 on datasketches-java to ask where the generator sources lived. Lee Rhodes replied:

Kevin did most of his math simulations and modeling in OCaml. And his code was on his computer, which no longer exists. And his personal code died with him … even if they have a copy of his old computer it might be trying to find a needle in a haystack.

Kevin passed away in April 2019, and any code left on his personal machine is effectively lost to history.

I was saddened to hear that. Kevin’s research in sketching algorithms underpins many of the core sketches in Apache DataSketches:

Still, with the runtime decoders and detailed header comments sitting right there in the source files, it seemed possible to reverse-engineer the offline generators from the artifacts alone. I asked Lee whether the CPC paper explained how the tables were derived, and he answered:

You should definitely read the paper. But it won’t tell you any details on the Huffman codings. As I recall, in his paper he used a more standard compression scheme. He finished his work on the code after he had finished his paper — and in the process came up with the modified Huffman coding idea, which is quite a bit more efficient than what he discussed in the paper.

That placed the derivation well beyond what I could work out on my own in an afternoon.

Since CpcSketch worked fine in datasketches-rust as long as the lookup arrays were copied faithfully, I left the mystery aside for the time being.

Then Gemini 4 Carbon came out just as I was preparing the next release of datasketches-rust. Since the checked-in tables and 20-digit header comments already acted as a strict numerical oracle, any candidate generator could be tested immediately in code: either it reproduced every codeword, permutation entry, and floating-point diagnostic within IEEE-754 precision, or it was wrong. That made the problem well suited to an agentic workflow built around executable checks and adversarial review.

Over several iterations, I steered three models against that oracle and against one another:

  1. Initial synthesis (Gemini 4 Carbon): Starting from the static arrays and source comments, it wrote executable probes and built the first constructive test harness, reproducing the Huffman codewords and column permutations bit-for-bit and fitting the ICON polynomials to matching accuracy.
  2. Mathematical falsification (Claude Opus 5.5): Tasked with breaking those initial claims, it ran controlled ablations that disproved an early “left-edge truncation” explanation, isolated an f64 cancellation trap, mapped out where the polynomial fits stop being identifiable, and re-ran the million-trial Monte Carlo statistics.
  3. Mutation and analytical audit (GPT 6 Astra): Auditing both the tests and the derivations, it used mutation testing to expose two tautological assertions, caught several mathematical overstatements in earlier drafts, and derived a closed-form expression matching the trailing digits of the asymptotic exponential constant.

None of the models got everything right on the first try, and several plausible-looking explanations collapsed as soon as we tested perturbations in code. What survived that filter became PR-355, which checks the reconstructed generators and derivations into datasketches-rust as unit tests, following the same approach we took for kxp_byte_lookup.

https://github.com/apache/datasketches-rust/pull/355
https://github.com/apache/datasketches-rust/pull/355

The rest of this post focuses on the mathematics and numerical forensics behind those four sets of tables: how each structure works, which wrong turns looked convincing until an ablation broke them, and where the surviving artifacts cannot tell two models apart. Formal derivations sit in the appendix at the end; if you spot an error, feel free to leave a comment or open a PR on datasketches-rust.

The Blind Spot of Discrete Codewords, and a 20-Digit Fingerprint

compression_data.rs.

Why hardcode 23 static Huffman tables at all? Building trees dynamically per sketch would force the serializer to write tree headers into the compressed stream, wiping out the tens of bytes saved on small sketches. Meanwhile, the probability that column jj of the coupon matrix is set depends mainly on the fill ratio C/KC / K (collected coupons CC over row count KK). Finite-KK corrections enter only at order 1/K1 / K, a tiny difference that turns out to be the key clue below. Precomputing optimal tables offline across representative C/KC / K checkpoints lets determine_pseudo_phase select the right table solely from lg_k and num_coupons without storing a table ID.

The first 22 tables encode 8-bit sliding-window bytes (00 through 255255). Given the per-column bit probabilities q0q_0

Upstream decoders use a 212=40962^{12} = 4096

The next question is which occupancy model columnProbabilities.ml actually used for column jj:

  1. Finite-KK binomial model: each item hits column jj with single-trial probability pj=1/(K⋅2j)p_j = 1 / (K \cdot 2^j)
  2. Infinite-KK Poisson limit: letting K→∞K \to \infty

Comparing integer codewords alone immediately runs into a blind spot: across the six midrange tables (array indices 16..21), sweeping KK from 2162^{16}

What actually acts as a continuous fingerprint to pin down KK are the two 20-digit floating-point comments that generateHuffmanCodes.ml printed above each table. Here is table 16 (the first midrange byte table):

// entropy: 2.1627885076675394949

// avg_length: 2.2704182849800043087; max_length = 12; num_symbols = 256

Shannon entropy H=−∑P(b)log⁡2P(b)H = -\sum P(b) \log_2 P(b)

Candidate Parameter KKMax Entropy Error max⁡∣ΔH∣\max \lvert \Delta H \rvertMax Avg Code Length Error
K=228K = 2^{28}7.38×10−107.38 \times 10^{-10}7.25×10−107.25 \times 10^{-10}
K=230K = 2^{30}1.48×10−101.48 \times 10^{-10}1.45×10−101.45 \times 10^{-10}
K=231K = 2^{31}4.92×10−114.92 \times 10^{-11}4.84×10−114.84 \times 10^{-11}
K=232K = 2^{32}6.22×10−156.22 \times 10^{-15}6.22×10−156.22 \times 10^{-15}
K=233K = 2^{33}2.46×10−112.46 \times 10^{-11}2.42×10−112.42 \times 10^{-11}
K=234K = 2^{34}3.69×10−113.69 \times 10^{-11}3.63×10−113.63 \times 10^{-11}
K→∞K \to \infty4.92×10−114.92 \times 10^{-11}4.84×10−114.84 \times 10^{-11}

At K=232K = 2^{32}

Look at the clean symmetry in that table: K=231K = 2^{31}

Steady-State Tables: The “Left-Edge Truncation” Mirage

estimator.rs. Rather than running Newton’s method across all 128 columns at query time, Kevin designed a two-piece approximation:

  • For C≤5.7KC \le 5.7K
  • Beyond that splice point, switch to an asymptotic exponential formula
N^poly(K,C)=C(1+(C/K)366.774757)∑m=019am(K)(C2K)m\hat{N}_{\text{poly}}(K, C) = C \left(1 + \frac{(C/K)^3}{66.774757}\right) \sum_{m=0}^{19} a_m(K) \left(\frac{C}{2K}\right)^m