確率的データ構造 t-digest を Go の CLI として書いた。全件ソートせずに、ストリームの 分位数（p50/p99/p99.9…） を数 KB で推定する構造。実装の hinge は 2 つ: (1) スケール関数 k(q) がセントロイドのサイズを制御し、中央は粗く・尾は鋭く保つ（だから p99.9 が中央値より精密になる）、(2) q=0/q=1 は厳密な min/max を返し、間はセントロイド平均を線形補間。加えて digest 同士はマージできる。#274-276 の確率的データ構造シリーズ（メンバーシップ/基数/頻度）に続く第 4 弾＝「分位数」。

📦 GitHub: https://github.com/sen-ltd/t-digest-cli

t-digest とは

正確な分位数を出すには全要素をソートして持つ必要があり、メモリは O(N)。t-digest は代わりに数百個の セントロイド（(平均, 重み) のペア＝近い値のクラスタ）だけを保持し、それを走査して任意の分位数に答える。50 万件でもセントロイドは ~100 個、数 KB で済む（N に依らない）。

素朴なバケツ分割の弱点は尾だ。等サイズのバケツに値をまとめると、p99.9 が中央値と同じ粗さになってしまう。t-digest はまさにこれを直す構造で、それが存在理由そのもの。

CLI はこう動く（実出力）:

$ td summary --from latencies-ms.txt --exact -c 200
count        500000
min / max    0.3 / 1655.8
centroids    122  (δ=200, 1952 bytes)
p50        20.1183        exact 20.1     (+0.09%)
p90        63.736         exact 63.7     (+0.06%)
p99        162.803        exact 161.9    (+0.56%)
p99.9      322.033        exact 312.6    (+3.02%)

50 万件のレイテンシを 2KB 弱 に要約し、p99 を誤差 0.56% で当てている。

hinge 1: 尾を鋭く保つスケール関数

セントロイドは一様には太らせない。スケール関数 k(q) が分位数 q を「k 空間」に写し、各セントロイドはそこで高々 1 単位 しか張れない。標準の k1 スケールは:

k(q)    = δ/(2π) · asin(2q − 1)
k⁻¹(k)  = (sin(2π k/δ) + 1) / 2

k は q=0 と q=1 の近くで急峻、q=0.5 で平坦。だから「1 k 単位」のセントロイドは、中央付近では広い分位数帯を覆い（精度が安い場所）、尾では極薄の帯になる（p99.9 が住む場所）。compression δ が唯一のつまみで、大きいほどセントロイドが増えて分位数が鋭くなる。

q := q0 + (cur.Weight+x.Weight)/total
if q <= qLimit {              // 1 k 単位以内 → 吸収
    cur = mergeInto(cur, x)
} else {                      // 溢れる → cur を確定し、新しいセントロイドへ
    out = append(out, cur)
    q0 += cur.Weight / total
    qLimit = kInv(k(q0) + 1)
    cur = x
}

一様分布でのテストが効果を pin する: p50 は ~1% 精度なのに、p999 は ~0.2% に抑えられる — 尾の方が精密になる、設計通りに（TestUniformQuantiles）。

hinge 2: min/max は厳密、間は補間

分位数はセントロイドを走査して半重みを累積し、隣接するセントロイド平均の間を線形補間して読む。両端だけは特別で、q=0/q=1 は別途追跡している 厳密な min/max を返し、尾はその極値と最外セントロイドの間を補間する:

func (t *TDigest) Quantile(q float64) float64 {
    if q <= 0 { return t.min }
    if q >= 1 { return t.max }
    index := q * t.total
    // ... セントロイドを走査し、平均間を補間 ...
}

TestExactExtremes が両端の厳密性を、TestMonotonic が曲線全体が単調非減少であることを確認する。

真骨頂: マージ

t-digest は合成できる。あるダイジェストのセントロイドを別のダイジェストに流し込んで再圧縮するだけだ。マージ後のダイジェストは両ストリームを見たかのように分位数に答える — だからシャード別・分単位のダイジェストを、再スキャンなしでグローバルに巻き上げられる:

func (t *TDigest) Merge(other *TDigest) { /* セントロイドを吸収して再圧縮 */ }

$ td merge -o all.tdigest a.tdigest b.tdigest
merged 2 digests → all.tdigest  count=500000  centroids=112

TestMergeApproximatesCombined が、範囲の異なる 2 ダイジェストのマージが合算ストリームのダイジェストと p10…p99 で一致することを pin する。HyperLogLog（#275）が max で、Count-Min（#276）が加算でマージできたのと同じ「合成可能性」の系譜だ。

永続化

ダイジェストは "TDG1" | δ | min | max | total | n | (mean, weight)*n というコンパクトな blob に直列化する。セントロイド 1 個あたり数バイト。手書き、コーデック無し。

tdigest/tdigest.go — ダイジェスト: k1 スケール, 圧縮, 分位数, マージ, (de)serialize（テスト 11 件）
main.go            — CLI: summary / add / quantile / merge / info, ファイル or stdin

まとめ

「p99 latency を全部覚えずに測る」ための定番が t-digest。鍵は スケール関数で尾を鋭く保つこと、min/max を厳密に持つこと、そして マージできること。確率的データ構造シリーズはこれでメンバーシップ(#274)・基数(#275)・頻度(#276)・分位数(#277) の 4 つが揃った。いずれも「全データを持たずに固定メモリで近似する」同じ思想で、t-digest ではそれが「精度を尾に寄せる」という形で現れる。

📦 GitHub: https://github.com/sen-ltd/t-digest-cli