如何实现基于无表散列的键值存储？
存储中的透明压缩：创新基础设施软件的催化剂 V
第五部分：如何实现基于无表散列的键值存储？
要实现键值(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的内存使用量要小得多。
图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”.
【存储中的透明压缩：创新基础设施软件的催化剂】系列完结撒花~
作者：张彤
简介：张彤教授在西安交通大学获得电子工程学士学位/硕士学位，在明尼苏达大学获得电子工程博士学位。目前是伦斯勒理工学院（RPI）的教授。研究领域包括数据库、文件系统、固态和磁数据存储设备和系统、数字信号处理和通信、纠错编码、VLSI架构和计算机架构。张彤教授在著名的USENIX/IEEE/ACM会议和期刊上发表了150多篇技术论文，引用h指数为36，在他的众多研究成果中，他为建立闪存信号处理研究领域，以及在商业数据存储和通信系统中实际实现低密度奇偶校验 (LDPC) 编解码器做出了开创性贡献。曾获得过两项最佳论文奖，并拥有超过20项的美国专利申请。
张教授是ScaleFlux的联合创始人兼首席科学家，负责开发计算存储产品的关键技术和算法，探索其在数据库等主流应用领域的优化使用。
关于ScaleFlux:
ScaleFlux是大规模部署计算存储的领导者。计算存储将是下一代数据中心的重要基石，使其能够为计算和存储I/O密集型应用提供更高性能、更低成本、更好扩展性的运行平台。ScaleFlux 成立于2014年，是一家快速发展的独角兽企业，并得到 SK、Micron、Kioxia和Xilinx等公司的战略支持。
