
2026/11/16 22:58
Apache DataSketches でケビン・J・ラングの失われた OCaml コードのリバースエンジニアリング
RSS: https://news.ycombinator.com/rss
要約▶
Japanese Translation:
安定した生産運用を 6 ヶ月間維持した後、ScopeDB はより効率的かつ正確なカージナルリティ推定のために HyperLogLog から Apache DataSketches の CpcSketch へ移行しました。後期の専門家ケヴィン J. ランによってハードコーディングされた重要な数学的ルックアップ表が利用できなくなった際、エンジニアらはソースコード内の数値の手がかりに基づいて生成器をリバースエンジニアリングする Gemini、Claude、および GPT を組み合わせたエージェンティック AI ワークフローを使用して対応しました。再構築された表(23 の Huffman 符号化、16 の置換集合、次数 19 の多項式係数、信頼区間量子位を含む)は百万回に及ぶシミュレーション試行および低確率カラムに対するビット単位での再現性検証を経て検証され、浮動小数点のキャンセル誤差を修正するとともに、有限モデルと無限モデルの補正間の不整合を解決しました。現在、建設的なユニットテストにより元のデータ値との完全な互換性が保証されています。多項式フィッティンググリッドや分母の起源など一部の理論的導出の詳細については未解明の問題として残されていますが、再構築された実装は業界全体を通じて統計的な精度と信頼性を著しく向上させました。
本文
ScopedB の approx_count_distinct
実装と Apache DataSketches Rust 移植:数値フォレンジックから導いたアーティファクトの完全再構築
approx_count_distinct概要:実装の経緯と背景
- 目標: ScopedB における近似一意カウント機能 (
) の実装を開始。approx_count_distinct- 分野の標準アプローチは HyperLogLog (HLL) であるが、当初の Rust エコシステムへの依存先としてクラウドフレアの
が選定された。cardinality-estimator
- 分野の標準アプローチは HyperLogLog (HLL) であるが、当初の Rust エコシステムへの依存先としてクラウドフレアの
- 問題点: 既存ライブラリは
コードや手動ビットパッキングに過度に依存しており、監査可能で自社管理下に置くことが困難だった。unsafe- 決定事項: 内部コピーをフォークしてメンテナンスする方針へ移行。
- 解決策: Apache DataSketches の
(空間効率が高い HllSketch)を採用。CpcSketch- Apache DataSketches は当初 Java/C++ 実装のみだったが、ScopedB(Rust)との親和性やコミュニティの関心から移植が進められた。
- 成果: 「datasketches-rust」の初期リリースと統合が完了し、本番環境で半年以上安定動作している。
Apache DataSketches Rust 開発者コミュニティと HLL の仕組み
- HLL の基本概念:
- エレメントを K つのバケットにハッシュし、各バケットは最大「リードゼロビット数」を維持する(通常 4〜6 ビット)。
- 高密度モードでは固定幅レジスタを維持する。
- CpcSketch の革新性 (Kevin J. Lang, Yahoo! Research):
- バケットごとの最大値だけでなく、古典的な FM85 コーポーンコレクタープロセスのフルな
ビット行列を保持する。K×64 - (r, c) 対: r 行で c 個のリードゼロビットを観測したら
のビットに 1 を設定する。(r, c) - 統計的効率: この全二値ヒット行列により、HLL よりも高い精度が得られる。
- バケットごとの最大値だけでなく、古典的な FM85 コーポーンコレクタープロセスのフルな
- シリアライズ戦略 (情報理論的境界):
- 低一意性:
対のスパースな(row, column)
を使用。PairTable - 中〜高一意性: スライドする 8 ビットウィンドウ、長さ制限付きハフマン符号化、列置換を組み合わせる。
- 効果: シリアライズされた CPC は、HLL と同等の精度においてストレージ使用量を 30%〜40% 削減。
- 低一意性:
- 移植の完了:
- 2025 年 1 月下旬に
を「datasketches-rust」に移植(PR-75)。CpcSketch
- 2025 年 1 月下旬に
上流実装からの移植における発見:ハードコーディングされたルックアップテーブル
- 存在する 4 つの静的テーブル:
- 静的ハフマン符号化テーブル: 23 グループ
- スライドウィンドウ用列置換: 16 グループ
- 次数 19 の多項式補正係数セット: 23 グループ
- 経験的な信頼区間分位点テーブル: 4 グループ
- 生成元の喪失:
およびcompression_data.rs
に配置されるこれら 4 つのテーブルのソースコード(estimator.rs
ファイル)が上流リポジトリに存在せず、生成元はケビン氏個人のマシン上にのみ残っていた。.ml- 悲劇: ケビン・J・ラン氏が 2019 年に他界し、そのコードも歴史から実質的に消失した。
- リバースエンジニアリングの試み:
- リー・ロドズ氏の回答によれば、論文にはハフマン符号化の詳細は記載されておらず、ケビンの最適化後(論文発表後)のコードが使われていた可能性がある。
- 突破口: コミットされたテーブルと 20 桁のヘッダーコメントを厳格な数値オラクルとして活用し、AI モデルで再生成・検証するアプローチへ転換。
離散的なコード語の盲点と 20 桁の指紋
- ハフマン符号化テーブル (23 グループ) の背景:
- 理由: スケッチごとに動的に木を構築すると数十バイトのヘッダーが不要になるため、オフラインで最適テーブルを事前計算している。
- 選択基準:
とlg_k
から適切なテーブルを選択するロジック (num_coupons
) によりテーブル ID は保持せず。determine_pseudo_phase
- コード語長の制約:
- 上流のデコーダーは 2^12 = 4096 エントリのテーブルを使用しており、12 ビットの厳格な上限があることが確認された。
- K 値(バケット数)の特定:
- ハフマン長は離散的な階段関数であり、確率の微小変化は木構造を変えることは稀。
- 判別方法: テーブル上部の
が出力する20 桁の浮動小数点コメント(例:generateHuffmanCodes.ml
)を連続的な指紋として活用。entropy: 2.1627...
- K=2^32 の確証:
- K を
から無限大までスキャンした結果、中範囲のテーブルにおいて誤差は 4 オーダ減少し、IEEE-754 ダブル精度の丸めノイズレベル (2^28
) に低下することが確認された。6.22×10⁻¹⁵
とK=2^31
は同等だが、∞
で初めて明確な極小値を示す(上流 ICON エスティメーターのコメントでも最大スロットは 2^32)。K=2^32
- K を
定常状態テーブル:“左端切断”の幻想
- 仮説: 「左端切断(left-edge truncation)」が誤差の原因であると見られた。
- B=6(充填率)で、完全飽和していない列が存在し、確率が約
となるため、観測されるエントロピー残差 (5.3×10⁻¹²
) と一致する。6.1×10⁻¹²
- B=6(充填率)で、完全飽和していない列が存在し、確率が約
- アブレーションによる否定:
- モデル切り替え:
を固定してビノミアルモデルをポアソン極限 (K=2^32
) に変更すると、エラーはK→∞
に低下。〜10⁻¹⁴ - パラメータ変化: B を増やすとエラーが半分ずつ減少する(B=6 → 3.1×10⁻¹² → 1.5×10⁻¹²)。
- モデル切り替え:
- 結論:
- 誤差の正体は左端ではなく、有限 K の補正効果。
- B を増やすとウィンドウが右へシフトし、内部の有限 K 補正項 (
) が f64 メカニカル・エプシロン未満となり、実質的にポアソン極限を模倣するだけ。2⁻ᴮ / K - 「B=6 ポアソン極限」モデルが選ばれたのは作業点と一致したが、テーブル自体は同等の有限 K ずれた間隔を許容している。
列置換:フェーズ 19/32 における丸め罠
- 目的: 56 つの「驚きビット(ウィンドウ外の列)」を確率降順でランク付けし、短いデルタ符号化を実現する。
- 計算上の問題 (
の罠):1.0 - q
という極めて小さい値がある。p0 = exp(−λ/2) ≈ 2.22×10⁻¹⁷- Rust(IEEE-754 f64)では
を計算すると、q = 1.0 - p0
が直前のフラストビット (p0
) の範囲にあり、偶数最近傍丸めにより2⁻⁵³
に丸まってしまう。1.0 - 結果:
は 0.0 となり、本来の順序が崩れる(スロット 52 が最後位に押しやられる)。1.0 - q
- 解決策:
- 指数を直接評価するロジック(例:
)を使用することでキャンセル誤差を回避。(-lambda / 2^j).exp() - これにより、B=6 のすべての置換テーブルをビット単位で再現できることが確認された。
- 指数を直接評価するロジック(例:
次数 19 の多項式と指数定数
- 二段階近似の設計:
- 低密度 (
): 三次先頭因子で事前調整された次数 19 の多項式を使用。C ≤ 5.7KN̂_poly(K, C) = C (1 + (C/K)^3 / 66.774757) Σ a_m (C/2K)^m
- 高密度: 漸近指数公式へ切り替え。
N̂_exp(K, C) = 0.7940236163830469 · K · 2^{C/K}
- 低密度 (
- フィッティング境界の分析:
- 多項式は厳密に
で停止しており、これを超えると急激に発散する。6K - 小規模スケッチ (
): 全整数lg_k ≤ 7
グリッドでの加重なし最小二乗法で係数を正確に回復可能。[1, 6K] - 大規模スケッチ (
): シングルステップの誤差が滑らかになるため、フィッティンググリッドの変更は識別不能となる(条件数がlg_k ≥ 8
と病態化)。~10^17
- 多項式は厳密に
- 指数定数
の導出:D = 0.7940236163830469- 純粋な経験値ではなく、ポアソンモデルから直接導出。
- メルリン変換と留数計算により閉形式
が得られる。D = √2 e⁻^γ - 周期的リップル(振動級数)による影響を考慮し、期間平均相対誤差がゼロになるように調整すると、この値が得られることが証明された。
百万回のモンテカルロ試行と離散的階段効果
- シミュレーションの困難:
で 10^6 回試行する場合、単一マシンでの実装は不可能(ステップ数lg_k=14
)。~1.6×10^13- 高速化: 指数スキップクーポンプロセスを採用し、O(N) → O(C) にコスト削減。
- ICON テーブルの再現性:
- ICON エスティメーターは整数カウント
にのみ依存するため、離散的な「階段ステップ」を持つ。C - 百万回の試行ではサンプル分位が整数 C ステップ上に着地するため、未丸め浮動小数点同士が最終ビットまで一致する。
- 結果: ケビンのテーブルに対して simA は 66 セル中 59 つを正確に再現(±0.5 丸め区間内)。
- ICON エスティメーターは整数カウント
- HIP テーブルの不整合:
- HIP は有限 N の影響を強く受けるため、独立した実行間で厳密な一致は期待できない。
- 統計的検査(マハラノビス T²)では、いくつかの行で軽微な不整合が検出されたが、全体的には許容範囲内。
証拠で証明可能・不可能な点:6 つの開課題
- 工学教訓: 「重言的なテスト(タートロロジー)を書くな」。単なる値の比較ではなく、定数や境界の厳密な検証を行うこと。
- 残る不確定要素 (Open Problems):
- 定常状態モデル: ポアソン極限か、ずらされたビノミアルモデルか?(f64 精度では識別不能)。
- Package-Merge のタイブレイキング: 特定条件下でのコード長生成ロジックの統一性。
- 三次分母 (
) の起源: 解析的または経験的な由来が不明。66.774757 - 多項式フィッティンググリッド: 小規模では
が確定だが、大規模では識別不能。[1, 6K] - 指数定数の選択基準: 最適化問題の明示的な解決か、あるいは経験的チューニングか。
- HIP テーブルの散乱: 軽微な集計不整合の原因(歴史的サンプリングノイズ vs 実装トリック)が特定できない。
補足:解析的導出と数学的背景
- 有限 K エントロピーエラー:
に比例してシフトし、シャノンエントロピーに線形な影響を与える (1/K
)。ΔH = α/K + O(K⁻²) - メルリン変換による主要項と周期的リップル:
- 無限列期待値の対数主要項:
log₂λ + γ/ln2 - 1/2 - 周期的リップル振幅:
(虚軸上の単純極から発生)。a ≈ 1.0904×10⁻⁶
- 無限列期待値の対数主要項:
- 期間平均相対誤差の最小化:
- 修正ベッセル関数
を用いて、定数をI0(a)
と定義。A = D / ⟨e^(ln2)P(t)⟩ - これによりビット単位での一致が保証される。
- 修正ベッセル関数
- スパイシングポイント (
) での過大評価:C=5.7K- 有限 K の影響により、ポアソン導出は一意性を若干過大評価する(最大相対バイアス
)。1/(82.6 K)
- 有限 K の影響により、ポアソン導出は一意性を若干過大評価する(最大相対バイアス
- 漸近相対標準誤差:
- ICON:
(ソースコードの定数と一致)。RSE ≈ ln2 / √K - HIP:
(定数RSE ≈ √(ln2/2) / √K
と一致)。0.5887...
- ICON: