大数据数据库后端【免费下载链接】prestoThe official home of the Presto distributed SQL query engine for big data项目地址https://gitcode.com/gh_mirrors/pre/presto点击查看免费下载导读KHyperLogLogKHLL是 Presto 内置的一种用于**估算大规模数据中两列关联关系reidentifiability / joinability**的紧凑型数据草图data sketch。本文以仓库内 KHyperLogLog 格式说明文档 为骨架完整讲解 KHLL 的内存结构与二进制序列化布局含各字段的字节序、含义与内存估算并结合 KHyperLogLog.java 的实现与 khyperloglog.rst 的函数说明带你掌握khyperloglog_agg、cardinality、intersection_cardinality、jaccard_index、uniqueness_distribution、reidentification_potential等 SQL 函数的使用方法以及它们在分布式聚合与序列化存储场景下的底层原理。读完本文你将能够在 Presto 中构建、合并、存储并分析两列关联关系的 KHLL 草图。KHyperLogLog 是什么KHyperLogLog 源自论文KHyperLogLog: Estimating Reidentifiability and Joinability of Large Data at ScaleChia et al., 2019。从源码注释与实现看它在 Presto 中是一种两级数据结构外层是一个k 大小的 MinHash 结构其每个条目entry以一个long类型的哈希值作为键key每个键映射到一个HyperLogLogHLL草图用于统计与该键相关联的另一列取值uii即 unique identifier input的去重基数。简单来说假设有两列x与yKHLL 用 MinHash 摘要x的取值键用每个键对应的 HLL 表示与某个x值关联的所有y值。因此一个 KHLL 草图可以回答诸如有多少个x只关联了少量y高度唯一存在再识别风险之类的问题。该类型在 Presto 中的类型名为KHyperLogLog定义见 KHyperLogLogType.java它是一个可变长度类型继承AbstractVariableWidthType底层以Slice承载序列化后的字节。其内部实现依赖 airlift 的com.facebook.airlift.stats.cardinality.HyperLogLogKHyperLogLog.java。序列化格式完整二进制布局原文档 khll.md 明确指出除非另行说明所有字段均为小端序little-endian。整体布局自上而下依次为字段类型说明format版本字节byte序列化格式版本当前实现中固定为1VERSION_BYTE见 KHyperLogLog.javaKmaxSizeintMinHash 结构中最多可容纳的条目数默认4096DEFAULT_MAX_SIZEHLL bucketsint每个 HLL 草图的桶bucket数默认256DEFAULT_HLL_BUCKETS# of entriesminhashSizeint当前 MinHash 结构中实际条目数最多为 Ktotal HLL sizeint所有序列化 HLL 草图的字节数总和HLL sizesint[]每个序列化 HLL 草图的大小字节数顺序与 keys 一致keyslong[]MinHash 结构中按升序排列的键哈希值序列HLLs字节序列与 keys 顺序一一对应的序列化 HLL 草图字节该布局与序列化实现完全吻合。查看 KHyperLogLog.java 的serialize()方法可见其写入顺序先写 1 个版本字节appendByte(VERSION_BYTE)再依次写maxSize、hllBuckets、minhash.size()、totalHllSize四个int随后写出每个 HLL 的 sizes 数组与 keys 数组最后逐个追加序列化后的 HLL 字节。反序列化newInstance(Slice)KHyperLogLog.java则按同样顺序读取并校验版本字节Unexpected version。两个值得注意的细节原文档提到currently just one format exists,0而当前仓库实现中VERSION_BYTE 1。这说明该字段的语义是格式/版本标识实际取值以当前仓库源码为准读取时会做严格校验版本不匹配即抛出异常。HLL 草图自身的序列化遵循 airlift 的 HyperLogLog 文档格式HyperLogLog.newInstance(serializedHll)/hll.serialize()本文不再展开具体可见 KHyperLogLog.java 中对HyperLogLog.newInstance的调用。内存与序列化体积估算KHLL 内部维护了两个计数器hllsTotalEstimatedInMemorySize与hllsTotalEstimatedSerializedSize在每次add、mergeWith以及溢出淘汰时通过increaseTotalHllSize/decreaseTotalHllSize保持同步KHyperLogLog.java。estimatedInMemorySize()约为对象本身 红黑树结构 minhash.size() * 8键的long 各 HLL 内存估算之和estimatedSerializedSize()约为1 4 * 4版本字节 4 个intminhash.size() * (8 4)每个键的long 每个 HLL 大小的int 各 HLL 序列化字节数之和KHyperLogLog.java。这两个估算值同时被聚合状态的内存记账所使用见下文聚合状态与内存管理。核心算法与源码级实现数据插入update 与溢出淘汰add(long value, long uii)与add(Slice value, long uii)先将value通过Murmur3Hash128哈希为 64 位键再调用私有update(long hash, long uii)KHyperLogLog.javaif (!(minhash.containsKey(hash) || isExact() || hash minhash.lastLongKey())) { return; }即只有当该哈希已存在、MinHash 尚未装满isExact()即条目数 maxSize、或新哈希小于当前最大键时才真正插入。随后computeIfAbsent为该键创建/复用 HLL 并hll.add(uii)。最后removeOverflowEntries()会循环淘汰最大的键minhash.lastLongKey()保证条目数不超过 K。这个只保留最小的 K 个哈希的策略正是 MinHash 的精髓它使得两个数据集的 MinHash 集合可以近似其集合交集而每个键内用 HLL 压缩了与该键关联的y值集合。基数估计cardinality()当isExact()为真未满 K 个条目时直接返回minhash.size()即精确基数否则按哈希密度外推估算long hashesRange minhash.lastLongKey() - Long.MIN_VALUE结合Long.divideUnsigned计算密度再外推到哈希输出范围的一半Long.MAX_VALUE并引用 Beyer 等人的论文进行偏差修正KHyperLogLog.java。合并merge 与 mergeWithmerge(KHyperLogLog a, KHyperLogLog b)有一个关键设计KHyperLogLog.java总是保留 K 值较小分辨率更高的一方作为合并基座因为若把小 K 的草图并入大 K 的草图前者的 MinHash 空间无法覆盖后者的全部 MinHash 空间会损失分辨率。mergeWith逐个键合并键相同时把两个 HLL 合并键不同则直接插入最后同样执行removeOverflowEntries()KHyperLogLog.java。交集与 Jaccard 指数exactIntersectionCardinality(a, b)仅当两个草图都处于 exact 状态时可用直接取Sets.intersection(a.minhash.keySet(), b.minhash.keySet()).size()jaccardIndex(a, b)取两集合键的并集在较小的集合大小范围内统计共同键的比例KHyperLogLog.java。在 SQL 函数层intersection_cardinality会优先走精确路径否则用jaccard * union.cardinality()估算并修正为不超过较小集合的基数KHyperLogLogFunctions.java。再识别潜力与唯一性分布reidentificationPotential(long threshold)统计基数该键关联的y值去重数不超过阈值的键所占比例即有多少x值只关联了少量y值uniquenessDistribution(long histogramSize)默认直方图大小 256DEFAULT_HISTOGRAM_SIZE对每个 HLL 的基数取min(cardinality, histogramSize)落入对应桶桶内值为相对频率1 / minhash.size()KHyperLogLog.java。Presto 中的 SQL 函数与使用方式依据官方函数文档 khyperloglog.rstKHLL 可通过khyperloglog_agg创建并可 cast 为varbinary以便存储复用。具体函数如下函数返回类型说明khyperloglog_agg(x, y)KHyperLogLog返回表示x与y两列关联关系的草图MinHash 摘要xHLL 表示与各x关联的ycardinality(khll)bigintMinHash 草图基数即x的基数估计intersection_cardinality(khll1, khll2)bigint两个草图 MinHash 结构所代表数据的集合交集基数jaccard_index(khll1, khll2)double两个草图数据的 Jaccard 指数uniqueness_distribution(khll)mapbigint,double唯一性分布直方图默认桶数为当前 MinHash 条目数uniqueness_distribution(khll, histogramSize)mapbigint,double指定桶数的唯一性直方图超过histogramSize的唯一性全部累计到最后一个桶reidentification_potential(khll, threshold)double唯一性低于threshold的x值占比再识别潜力merge(khll)KHyperLogLog多个草图聚合后的并集聚合函数merge_khll(array[khll])KHyperLogLog数组形式 KHLL 的并集SQL 使用示例-- 构建草图x 为 bigint 列y 为 bigint 列 SELECT khyperloglog_agg(x, y) AS khll FROM source_table; -- 估算 x 的基数 SELECT cardinality(khyperloglog_agg(x, y)) FROM source_table; -- 估算两组数据的 Jaccard 指数与交集基数 SELECT jaccard_index(khll_a, khll_b), intersection_cardinality(khll_a, khll_b) FROM (SELECT khyperloglog_agg(x, y) AS khll_a FROM table_a) a CROSS JOIN (SELECT khyperloglog_agg(x, y) AS khll_b FROM table_b) b; -- 评估再识别风险唯一性不超过 5 的 x 值占比 SELECT reidentification_potential(khyperloglog_agg(x, y), 5) FROM source_table; -- 草图与 varbinary 互转便于落盘存储 SELECT CAST(khyperloglog_agg(x, y) AS varbinary) AS stored FROM source_table;输入类型支持khyperloglog_agg的第一参数x与第二参数uii即y支持多种组合bigint/varchar/double均可作为xbigint/varchar可作为uii。当uii为varchar时会先经XxHash64哈希为long再写入 HLL见 KHyperLogLogAggregationFunction.java 与 KHyperLogLogWithLimitAggregationFunction.java。序列化存储与 castKHyperLogLogOperators.java 提供了KHyperLogLog - varbinary的双向 cast直接透传底层Slice。因此你可以把草图 cast 成varbinary存入外部表下次读取后再 cast 回来继续做合并与分析。聚合状态与内存管理在 Presto 聚合框架中KHLL 的中间状态由KHyperLogLogState接口描述其序列化器与工厂分别为 KHyperLogLogStateSerializer.java序列化类型即KHyperLogLog空状态写 NULL与 KHyperLogLogStateFactory.java提供单值与分组两种状态。分组状态GroupedKHyperLogLogState使用ObjectBigArrayKHyperLogLog按 group 存放草图并实时维护getEstimatedSize()对象大小 各草图内存估算 数组开销供查询引擎做内存控制工厂支持groupLimit参数当 group 数超过限制时抛出NOT_SUPPORTED异常错误信息中提示由khyperloglog-agg-group-limit配置控制用于防止分组过多导致内存爆炸KHyperLogLogStateFactory.java。KHyperLogLogWithLimitAggregationFunction是khyperloglog_agg的一个带分组上限的变体实现其getDescription()明确描述了语义MinHash structure summarizes x and the HyperLogLog sketches represent y values linked to x values。合并函数的实现merge聚合函数AggregationFunction(merge)直接以KHyperLogLog作为输入逐个mergeWith后输出序列化结果MergeKHyperLogLogAggregationFunction.javamerge_khll(array(khyperloglog))则遍历数组跳过 NULL 元素对首个非空元素依次合并空数组返回 NULLKHyperLogLogFunctions.java。使用建议与注意事项版本字节校验序列化首字节当前固定为1与 khll.md 中当前仅一种格式的描述略有出入以源码为准跨版本读取不兼容的字节流会直接抛 Unexpected versionK 与桶数的默认值K 4096、hllBuckets 256。K 决定 MinHash 的精度与内存上限桶数决定单个 HLL 的精度两者都可通过构造函数指定KHyperLogLog.java合并方向merge始终以 K 较小者为基础避免分辨率损失自建合并流程时也应遵循这一约定精确与近似未装满条目数 K时cardinality与intersection_cardinality走精确路径装满后为近似估计误差特性与 MinHash/HLL 的参数直接相关存储若需持久化草图请通过CAST(... AS varbinary)落库读取后转回KHyperLogLog再参与merge聚合。相关源码与文档索引格式说明presto-main-base/src/main/java/com/facebook/presto/type/khyperloglog/docs/khll.md本文骨架含布局图 khll_layout.png核心实现KHyperLogLog.java类型定义KHyperLogLogType.java标量函数KHyperLogLogFunctions.java聚合函数KHyperLogLogAggregationFunction.java、KHyperLogLogWithLimitAggregationFunction.java、MergeKHyperLogLogAggregationFunction.java状态与序列化KHyperLogLogState.java、KHyperLogLogStateFactory.java、KHyperLogLogStateSerializer.java官方函数文档presto-docs/src/main/sphinx/functions/khyperloglog.rst赞分享大数据数据库后端【免费下载链接】prestoThe official home of the Presto distributed SQL query engine for big data项目地址https://gitcode.com/gh_mirrors/pre/presto点击查看免费下载相关推荐Presto KHyperLogLog 函数完全指南基于 MinHash 与 HyperLogLog 的双列关联数据草图Presto KHyperLogLog 函数完全指南基于 MinHash 与 HyperLogLog 的双列关联数据草图 导读 KHyperLogLogKH大数据数据库后端Presto Set Digest 函数完全指南基于 MinHash 与 HyperLogLog 的集合相似度估算Presto Set Digest 函数完全指南基于 MinHash 与 HyperLogLog 的集合相似度估算 导读 本文深入讲解 Presto 分布式大数据数据库后端Presto HyperLogLog 函数完全指南approx_distinct 背后的数据草图与增量去重实战Presto HyperLogLog 函数完全指南approx_distinct 背后的数据草图与增量去重实战 HyperLogLog 是一种以固定内存估算海大数据数据库后端上一篇3步解密网易云NCM音乐完整指南高效实现跨平台播放自由下一篇深度技术解析Lenovo Legion Toolkit 高级性能调优与系统集成指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
