要实现键值(KV)存储，一个核心设计决策是选择基于树的还是基于散列的索引数据结构。在传统的实践中，基于散列的键值存储必须使用内存中的散列表来维护从键空间到存储空间的映射。因此，基于散列的键值存储的内存使用量与键空间的大小(即键值对的总数)成线性关系。相比之下，基于树的索引数据结构，如B+树和LSM树，通过把绝大多数索引保留在存储设备上，实现了更低的内存资源消耗。因此，尽管基于散列的索引可以支持更高的访问吞吐量和更低的访问延迟，它仅被键值对总数相对较少的内存数据存储(例如，Redis)使用。大规模、可持久化的键值存储几乎总是建立在基于树的索引数据结构之上。
本篇博客介绍了，通过存储设备内的透明压缩技术，在非常小的内存资源开销下，实现大规模基于散列的键值存储首次成为可能。为了从根本上克服基于散列的键值存储的内存开销障碍，唯一的选择是不使用散列表，而是将键空间直接散列到逻辑存储空间上。然而，键值对将不能再紧密地放置在逻辑存储空间上，导致大量的逻辑存储空间未充分利用(例如，几乎所有的4KB LBA block都有一些空间未被使用)。因此，当在传统的存储设备上运行时，这种无散列表键值存储将会承受非常高的存储成本，因此实际上不可行。相比之下，正如在前面几篇博客中所指出的，内置透明压缩的存储设备支持几乎可变大小的block I/O，这自然包含了每个4KB LBA block中利用率不足的逻辑存储空间。因此，当在内置透明压缩的存储硬件上运行时，基于无表散列的键值存储可以在不牺牲存储成本的情况下消除内存开销障碍。这首次使基于散列的方法在实现大容量键值存储方面成为基于树实现的可行替代方案。
图1说明了传统的基于散列的键值存储（左侧）和基于无表散列的键值存储（右侧）。设K表示键值存储的键空间，L表示逻辑LBA存储空间。我们使用一个散列函数 fK→L来把每个键 ki∈K直接映射到一个 li∈L上，不通过散列表中转。通过避免散列表的使用，它消除了传统的基于散列的键值存储所面临的内存成本障碍。此外，CPU无需管理/搜索散列表，从而降低了CPU计算开销。
为了演示，我们实现了一个名为KallaxDB的无表散列键值存储，并将其与RocksDB和WiredTiger进行了比较。我们在一台具有24核2.6GHz Intel CPU、64GB DDR4 DRAM和一个内置透明压缩的3.2TB CSD2000的服务器上运行了所有的实验。我们使用以下五个YCSB基准测试：YCSB A（50%读取，50%更新）、YCSB B（95%读取，5%更新）、YCSB C（100%读取）、YCSB D（95%读取，5%插入）和YCSB F（50%读取，50%读修改写）。我们把大小约400GB、包含4千亿个键值对的数据集加载到三个键值存储中，下表显示了逻辑/物理存储空间的使用情况和索引的内存使用情况。结果清楚地表明，虽然KallaxDB占用了更大的逻辑存储空间，但其物理存储成本与其他键值存储的物理存储成本非常接近。与此同时，与其他键值存储相比，KallaxDB的内存使用量要小得多。
| 逻辑空间 | 物理空间 | 索引内存使用 | |
| RocksDB | 419GB | 209GB | 4.4GB |
| WiredTiger | 573GB | 276GB | 11.4GB |
| KallaxDB | 805GB | 218GB | 1.2GB |
图2显示了平均操作吞吐量（即ops/s）、平均读延迟、99%读延迟和CPU效率的测量结果。我们用“每键值存储操作的CPU Cycle数”来量化CPU效率。图2中的结果表明，基于无表散列的键值存储在所有性能和CPU使用指标上始终优于RocksDB和WiredTiger。例如，在工作负载YCSB F下，KallaxDB的性能分别比RocksDB和WiredTiger高出2.6倍和5.8倍。与RocksDB和WiredTiger相比，KallaxDB在所有5个YCSB工作负载中都实现了1.4倍~2.7倍的平均读取延迟的性能提升。平均而言，KallaxDB的CPU效率比RocksDB高2.3倍~3.2倍，比WiredTiger高2.8倍~4.7倍。详情请参阅2021年我们在the International Workshop on Data Management on New Hardware发表的论文“KallaxDB: A Table-less Hash-based Key-Value Store on Storage Hardware with Built-in Transparent Compression”.
