Apache DataSketches 配置参数详解
系统梳理 Apache DataSketches 各 sketch 的关键配置参数，包括 HLL 的 lgK、Theta 构建器、KLL 的 k 与 m、频繁项 maxMapSize、哈希 seed 与序列化格式，并附实测精度数据。
Apache DataSketches 配置参数详解
DataSketches 的每一个 sketch 都由少量参数决定其三件事：估计精度、内存/序列化体积、以及能否互相合并。本文基于 datasketches-java 6.1.1 的实测数据，逐类说明这些参数的含义、取值与取舍。文中所有数值均来自真实运行（n = 1,000,000，JVM 堆 256MB）。
一、参数总览与精度—内存权衡
1.1 三类参数
- 精度参数：
lgK（HLL、Theta、CPC）与k（KLL）。它们决定 sketch 内部桶的数量与相对误差，是影响结果最直接的参数。 - 一致性参数：
seed（哈希种子）。参与同一次集合运算（union / intersection / aNotB）的所有 sketch 必须使用相同 seed。 - 容量参数：HLL 的目标类型（HLL_4/HLL_6/HLL_8）、频繁项的
maxMapSize。它们在精度不变的前提下改变内存占用。
1.2 通用规律（实测）
精度参数每提升一档，误差约减半，但内存/序列化体积近似翻倍。因此应「按业务可接受误差反推参数」，而不是盲目取最大值。
二、HLL 参数
2.1 lgK：精度档位
lgK 是 log2(桶数量)：HLL 使用 m = 2^lgK 个桶。理论相对标准误差约为 1.04 / sqrt(2^lgK)。构造方式：
HllSketch sk = new HllSketch(12, TgtHllType.HLL_8); // lgK=12
2.2 目标类型：HLL_4 / HLL_6 / HLL_8
目标类型只影响每个桶的存储位宽，从而影响内存，而不改变 lgK 决定的估计分辨率：
HLL_8：每桶 1 字节（8 位），精度最高、体积最大；HLL_6：每桶 6 位，兼顾；HLL_4：每桶 4 位，最省内存，但在低基数区间精度略降。
2.3 seed：哈希种子
new HllSketch(lgK, type, seed) 可指定种子，默认使用库内置种子。不同 seed 的 sketch 不能安全合并。
2.4 实测数据（n=1,000,000）
| lgK | 目标类型 | 估计值 | 相对误差 | 序列化字节（updatable） |
|---|---|---|---|---|
| 10 | HLL_4 | 985419.3 | -1.4581% | 616 |
| 10 | HLL_6 | 985419.3 | -1.4581% | 809 |
| 10 | HLL_8 | 985419.3 | -1.4581% | 1064 |
| 12 | HLL_4 | 990116.6 | -0.9883% | 2216 |
| 12 | HLL_6 | 990116.6 | -0.9883% | 3113 |
| 12 | HLL_8 | 990116.6 | -0.9883% | 4136 |
| 14 | HLL_4 | 993659.7 | -0.6340% | 8488 |
| 14 | HLL_6 | 993659.7 | -0.6340% | 12329 |
| 14 | HLL_8 | 993659.7 | -0.6340% | 16424 |
| 16 | HLL_8 | 997268.8 | -0.2731% | 65576 |
结论：同一 lgK 下三种目标类型估计值相同，仅体积递增，可按内存预算在 HLL_4/6/8 间选择；lgK 每 +1，误差约减半、体积约翻倍。
三、Theta 参数
3.1 ThetaSketchBuilder
Theta 的更新型 sketch 通过构建器创建，可配置项最多：
UpdateSketch s = UpdateSketch.builder()
.setLogNominalEntries(12) // 精度：log2(名义条目数)
.setSeed(9001L) // 哈希种子
.setP(1.0f) // 采样概率（1.0 表示不采样）
.build();
// 等价写法：setNominalEntries(4096)
setLogNominalEntries(k)/setNominalEntries(n)：n = 2^k，决定保留条目数与精度；setSeed(long)：种子，集合运算双方必须一致（详见 3.3）；setP(float)：采样率，用于按比例抽样，1.0为全量；setResizeFactor(...)：内部数组扩容因子（X1/X2/X4/X8），影响内存增长方式。
3.2 集合运算构建器
并集、交集、差集通过 SetOperation.builder() 构建，同样支持 setLogNominalEntries、setSeed、setP：
Union u = SetOperation.builder().setLogNominalEntries(12).buildUnion();
Intersection it = SetOperation.builder().setLogNominalEntries(12).buildIntersection();
AnotB aNotB = SetOperation.builder().setLogNominalEntries(12).buildANotB();
3.3 seed 一致性（实测）
同数据、不同 seed（1 与 2）的 sketch 求并集时，实测抛出异常：
SketchesArgumentException: Incompatible Seed Hashes. 93cc, c44a
即：参与同一集合运算的所有 Theta sketch 必须使用相同的 hash seed，否则无法合并。
3.4 实测数据（n=1,000,000）
| lgK | 估计值 | 相对误差 | compact 序列化字节 |
|---|---|---|---|
| 10 | 965308.4 | -3.4692% | 13632 |
| 12 | 1002714.7 | 0.2715% | 52504 |
| 14 | 1000160.0 | 0.0160% | 184648 |
| 16 | 997020.3 | -0.2980% | 651784 |
Theta 的误差随 lgK 提升而下降，但 compact 体积增长明显，需在精度与体积间权衡。
四、KLL 参数
4.1 k：精度档位
KLL 通过 k 控制精度，k 越大精度越高、体积越大：
KllFloatsSketch sk = KllFloatsSketch.newHeapInstance(200); // k=200
4.2 m：内部中间层大小
m 是 KLL 的中间层容量，由库内部管理（默认 8），通常无需用户设置；用户只需关注 k。归一化秩误差与 k 近似成反比：k 翻倍，误差约减半。
4.3 实测数据（n=1,000,000）
| k | 归一化秩误差 | P50 估计 | 序列化字节 |
|---|---|---|---|
| 100 | 0.02608 | 499952.0 | 1412 |
| 200 | 0.01329 | 501947.0 | 2536 |
| 400 | 0.00678 | 500210.0 | 4840 |
可见误差随 k 近似线性下降（k=100→200→400 时误差 0.02608→0.01329→0.00678），同时体积成比例增长。
五、频繁项（Frequent Items）参数
5.1 maxMapSize
maxMapSize 决定频繁项 sketch 内部哈希表的最大容量，直接影响可保留的候选项数量与内存：
ItemsSketch<String> fi = new ItemsSketch<>(32); // maxMapSize=32
5.2 ErrorType：误差取向
查询频繁项时需指定误差类型：
ErrorType.NO_FALSE_POSITIVES：结果不会出现假阳性（低频噪声不会被误报为频繁项），但上界较宽；ErrorType.NO_FALSE_NEGATIVES：结果不会漏掉真正频繁的项，但可能包含假阳性。
实测（maxMapSize=32，总流 100001 条）返回：
项=apple 估计频次=50001 上界=50001
项=banana 估计频次=15000 上界=15000
项=cherry 估计频次=5000 上界=5000
5.3 误差估计辅助
ItemsSketch.getAprioriError(int, long) 与实例方法 getMaximumError() 可用于评估当前配置下的误差上界。
六、CPC 参数
6.1 lgK
CPC 与 HLL 类似，用 lgK 控制精度：
CpcSketch cpc = new CpcSketch(11); // lgK=11
实测（lgK=11，n=500,000）：估计 497124.8，相对误差 -0.5750%，序列化仅 1276 字节。CPC 在同等精度下通常比 HLL 更省空间，适合基数估计场景。
七、序列化与 compact 模式
7.1 三种序列化方法
toUpdatableByteArray()：保留可继续更新的内部结构，体积较大（HLL_8 lgK=12 实测 4136 字节）；toByteArray()：通用序列化，KLL、CPC、Theta compact 结果均使用它；toCompactByteArray()：HLL 的紧凑形式，只读、体积最小。
7.2 compact 化
Theta 的更新型 sketch 调用 compact() 得到只读的 CompactSketch，其体积显著减小且可安全跨进程传输：
CompactSketch c = updateSketch.compact();
byte[] bytes = c.toByteArray();
7.3 PreambleUtil 与字节布局
每个序列化 sketch 的前若干字节是前导码（preamble），记录了序列化版本、族（Family）、lgK、标志位、桶/条目数量等元信息。库内部由 PreambleUtil 工具类读写这些字段（包级私有，属于实现细节，用户一般无需直接调用）。反序列化时正是依赖前导码识别 sketch 类型并还原参数：
HllSketch restored = HllSketch.heapify(bytes);
这就解释了为何「序列化—传输—反序列化」是无损且自描述的，也是分布式聚合（各节点本地建 sketch、汇总端合并）的基础。
八、内存占用估算与选型建议
8.1 内存占用估算
在内存模式下，HLL 约占用 2^lgK 字节量级（HLL_8）或约一半（HLL_4）；Theta 的数组规模为 2^lgK 个哈希槽（约 8 字节/槽，实测 lgK=12 的 compact 为 52504 字节）；KLL 的内存与 k 近似成正比（实测 k=200 系列化 2536 字节）。
8.2 选型建议
- 只要基数、不要集合运算：优先
HllSketch或CpcSketch，lgK=12~14适合百万级去重； - 需要交/并/差集合运算：用 Theta，注意 seed 一致；
- 需要分位数/中位数：用 KLL，
k=200是常见的精度/体积平衡点； - 需要 Top-K / 重频项：用 Frequent Items，
maxMapSize取目标频繁项数量的若干倍； - 只要低基数小内存：HLL_4 或更小的 lgK。