如何实现基于无表散列的键值存储?
要实现键值(KV)存储,一个核心设计决策是选择基于树的还是基于散列的索引数据结构。在传统的实践中,基于散列的键值存储必须使用内存中的散列表来维护从键空间到存储空间的映射。因此,基于散列的键值存储的内存使用量与键空间的大小(即键值对的总数)成线性关系。相比之下,基于树的索引数据结构,如B+树和LSM树,通过把绝大多数索引保留在存储设备上,实现了更低的内存资源消耗。因此,尽管基于散列的索引可以支持更高的访问吞吐量和更低的访问延迟,…
要实现键值(KV)存储,一个核心设计决策是选择基于树的还是基于散列的索引数据结构。在传统的实践中,基于散列的键值存储必须使用内存中的散列表来维护从键空间到存储空间的映射。因此,基于散列的键值存储的内存使用量与键空间的大小(即键值对的总数)成线性关系。相比之下,基于树的索引数据结构,如B+树和LSM树,通过把绝大多数索引保留在存储设备上,实现了更低的内存资源消耗。因此,尽管基于散列的索引可以支持更高的访问吞吐量和更低的访问延迟,…
作为使用最广泛的索引数据结构,B+ Tree支持当今几乎所有的关系数据库管理系统 (RDBMS,例如 MySQL、PostgreSQL、MariaDB、Oracle、SQL Server 和 DB2)。最近,LSM-Tree作为 B+ Tree 的竞争者吸引了一部分的注意力,主要是因为 LSM-Tree 的两个被广泛引用的优点:更低的存储成本和更小的写放大。这里的写放大定义为B+Tree或LSM-Tree写入存储设备的数据总量与写入B+Tree或LSM-Tree的用户数据量的比值
数据库和文件系统几乎普遍使用预写日志 (WAL) 来确保原子性操作和数据持久性。它的基本概念非常简单:在应用到数据文件之前,数据修改会被保存到一个专用的日志区域。在一般情况中,数据修改首先在内存WAL缓冲区中作为日志记录累积,然后刷新到存储WAL文件中。为了最大限度地提高数据持久性,系统会在每次事务提交时执行memory-to-storage flush(使用fsync或fdatasync等命令)。
作为应用最广泛的关系型数据库,PostgreSQL应用B+ tree索引去管理其数据存储(默认B+ tree page大小为8KB),通过存储表空间中的所有row version实现MVCC(多版本并发控制)。因此,PostgreSQL总是没有直接在一个B+ tree page中更新一行,而是首先将新的行版本存储在一个新的位置,并依赖于后台真空过程来回dead row version所占用的表空间。
存储中的透明压缩是开启计算存储驱动器 (CSD) 商业化之旅的最佳选择,主要有两个原因:(1) 零采用障碍:存储内透明压缩不需要对现有存储 I /O 软件堆栈进行任何更改(例如,文件系统、块层和驱动程序)和 I/O 接口协议(例如,NVMe 和 SATA)。 这确保了在其无缝集成和部署到现有基础设施中,无需用户应用程序去更改任一代码