Paimon Lookup 哈希文件和Sort文件选择

Paimon构建lookup结构见：Paimon lookup核心过程：分级查找、二分和缓存创建（LookupFile）_paimon 分级存储-CSDN博客

Hash查找和Sort查找是一个Lookup File内部的事情（它指向一个远程的SST 和 一个本地的File）。

见：

Paimon Lookup: LSM Tree Sort Block-CSDN博客

Paimon哈希lookup文件构建解析-CSDN博客

Paimon 中 HashLookupStoreWriter 的实现并非一个简单的内存哈希表，而是考虑了外存（磁盘）和分页，这使得它与 Sort 实现的优劣对比更加微妙和有趣。

核心设计思想

• Hash Lookup Store：其设计目标是实现理论上 O(1) 的随机查找。它通过哈希函数将 Key 直接映射到文件中的一个位置（slot），从而快速定位。为了避免将整个哈希表加载到内存，它使用了 MappedByteBuffer，这是一种内存映射文件技术，让操作系统来负责将文件页面（Page）在磁盘和内存之间换入换出。
• Sort Lookup Store：其设计目标是实现 O(log n) 的随机查找。它将所有的 Key-Value 对按 Key 排序后顺序存储。查找时，利用二分搜索算法在排好序的 Key 文件中快速定位。

---

详细优劣对比分析

对比维度	Hash Lookup Store (基于 HashLookupStoreWriter.java)	Sort Lookup Store (通用实现)
​​查找性能​​	理论最优，但有不确定性。理想情况下为 O(1)。但如果哈希冲突严重（代码中 collisions++ 会记录），性能会退化，需要进行线性探测（probe++），最坏情况退化为 O(n)。	非常稳定。严格的 O(log n) 性能，不受数据分布影响，性能表现非常可预测。
​​构建/写入性能​​	较慢且复杂。从代码 close() 和 buildIndex() 方法可以看出，构建过程分为两步： 1. 将所有 KV 写入临时文件。 2. 读取临时文件，计算每个 Key 的哈希值，并将其放入最终的、预先分配好大小的哈希槽（slot）中。	较快且高效。构建过程直接写入远程有序的SST，只需要转换格式。
​​内存使用​​	可能更高且有空间浪费。它需要预先分配一个大小为 slots * slotSize 的哈希表空间（indexAccessFile.setLength(...)）。 slots 的数量由 keyCount / loadFactor 决定。 如果 loadFactor 设置得较低（例如默认0.75），就会有至少25%的预留空槽，造成空间浪费。 虽然 MappedByteBuffer 使得它不直接占用等同大小的堆内存，但它会占用进程的虚拟内存地址空间，并可能给操作系统的页面缓存带来压力。	可控且高效。构建时，内存使用由外部排序的缓冲区大小决定，是可控的。 最终生成的索引文件没有空洞，只存储有效数据，内存占用和磁盘占用都非常紧凑。
​​磁盘空间​​	占用较大。原因同上，由于 loadFactor 的存在，索引文件本身就比实际需要的要大，以预留空间减少哈希冲突。	占用紧凑。索引文件和数据文件都只包含有效数据，没有内部空洞和预留空间，磁盘利用率高。
​​对数据特征的敏感度​​	非常敏感： 1. 对 Key 长度敏感：从 put 方法中的 getIndexStream(keyLength) 可以看出，此实现为每一种不同长度的 Key 都创建了独立的索引和数据文件。如果你的 Key 长度变化多端，会产生大量小文件，性能会受影响。 2. 对 Key 分布敏感：如果哈希函数设计不佳或 Key 本身分布不好，会导致大量哈希冲突，严重影响性能。	不敏感，非常鲁棒。无论 Key 的长度如何变化，无论 Key 的值如何分布，排序结构都能稳定地工作，性能表现一致。

总结与 Paimon 的选择

综合以上分析，我们可以得出结论：

• Sort Lookup Store (默认选项)：是更通用、更稳健、资源效率更高的选择。它的性能稳定可预测，构建速度快，对内存和磁盘的利用率都非常高，并且能很好地处理各种数据类型和分布。这解释了为什么 Paimon 会选择 sort 作为 lookup.local-file-type 的默认值。它在绝大多数场景下都是一个不会出错的、表现良好的选择。

CoreOptions.java有这样的默认配置

    public static final ConfigOption<LookupLocalFileType> LOOKUP_LOCAL_FILE_TYPE =key("lookup.local-file-type").enumType(LookupLocalFileType.class).defaultValue(LookupLocalFileType.SORT).withDescription("The local file type for lookup.");

• Hash Lookup Store (特定场景优化选项)：是一个更极致、但适用场景更窄的选择。

  • 优点：在 Key 长度固定、哈希函数表现良好、且哈希冲突率低的情况下，它可以提供比 O(log n) 更快的 O(1) 查找性能。
  • 缺点：构建过程更慢，资源（内存/磁盘）占用更高，且对数据特征（尤其是 Key 的长度）非常敏感。

因此，只有当 确信 业务场景符合以下所有条件时，才值得考虑手动将 lookup.local-file-type 切换到 hash：

1. 对查找延迟有极致的要求，O(log n) 已经无法满足。
2. 主键的长度是固定的或变化范围极小。
3. 愿意牺牲更多的构建时间和磁盘/内存资源来换取这部分查找性能的提升。