摘要
本文主张，内置透明压缩的存储硬件为数据存储管理软件（如数据库和文件系统）的创新带来了新的机遇。现代存储设备(如全闪存阵列)和一些最新的ssd(固态硬盘)可以透明地从操作系统和用户应用程序执行数据压缩。这种存储硬件实现了逻辑存储空间利用率和物理存储空间利用率的解耦。这允许数据存储管理软件故意浪费逻辑存储空间，以换取使用更简单的数据结构，从而降低实现复杂性和提高性能。根据这一主题，我们在关系数据库和键值(KV)存储的背景下进行了三个初步的案例研究。初步的实验结果很好地证明了这一研究的潜力，我们希望这一初步的研究能引起更多的兴趣来探索这一新的研究领域。
1、介绍
本文主张，内置透明压缩的存储硬件为数据管理软件(如数据库和文件系统)的创新带来了令人兴奋的机遇。商业市场已经见证了块存储设备/设备的崛起，它们执行数据压缩，对操作系统和用户应用程序完全透明。现代全闪光阵列支持块级透明压缩。内置透明压缩的ssd也在市场上崭露头角。
除了在降低存储成本方面的明显优势外，内置透明压缩的存储硬件还可以将逻辑存储空间利用率与物理存储空间利用率解耦。这为数据管理软件的创新创造了一个新的领域，可以解释如下。在传统的存储硬件上运行时，数据管理软件对物理存储空间的利用效率全权负责。因此，数据管理软件面临着存储利用效率和实现复杂性之间的严格权衡:为了提高存储空间利用率，数据管理软件需要充分利用逻辑存储空间，用用户数据完全填充每个4KB LBA(逻辑块地址)扇区，这就需要更复杂的数据结构和算法。相比之下，数据管理软件在内置透明压缩的存储硬件上运行时，可以在依赖存储硬件保持物理存储空间效率的同时，有目的地浪费逻辑存储空间，降低实现复杂度。较低的软件实现复杂度可能导致更高的速度性能和更好的系统稳定性。
之前很少有研究研究数据管理软件如何有效地利用解耦的逻辑与物理存储的利用效率。不管具体的应用程序是什么，基本的设计主题是数据管理软件明智地浪费逻辑存储以空间换取更低的实现复杂性和更高的性能。随着内置透明压缩的存储硬件出现在主流市场上，对该框架下的数据管理软件设计进行重新思考变得越来越有必要。作为这一方向的第一个努力，我们进行了三个初步的案例研究:(1)我们表明PostgreSQL(第二大最流行的开源关系数据库)可以很容易地从这个主题中受益，只需简单地调整一个参数;(2)我们证明日志结构的数据存储可以利用这个主题来减少后台垃圾收集的影响;(3)我们证明了在几乎没有内存使用的情况下，可以应用这个主题来实现基于散列的KV存储。我们希望，这些初步的案例研究将有助于吸引更多的研究兴趣和活动，这是一个很大程度上未开发的领域，这可能会带来意想不到的机会，以创新未来的数据管理软件。
2、拟设计主题
对于运行在传统存储硬件上的系统，它们的逻辑和物理存储空间利用率总是紧密耦合在一起，即LBA空间(几乎)等于存储硬件内部的物理存储空间，每个4KB的LBA扇区总是占用4KB的物理存储空间。因此，物理存储空间的利用效率完全由数据管理软件来承担。因此，数据管理软件通常采用复杂的数据结构(如b -树和日志结构的合并树)和算法，以充分利用物理存储空间。然而，这导致了高实现复杂性，高CPU/内存资源的使用，以及难以实现高速和稳定。之前关于数据管理系统的大部分研究集中在寻找存储成本和实现/性能成本之间的更好的设计折衷。
为了便于说明，图1显示了内置透明压缩的SSD的结构。数据压缩和解压缩由SSD控制器内的硬件引擎在IO路径上进行，对主机软件栈是透明的。SSD控制器内部的FTL (flash转换层)管理所有变长压缩数据块的映射/索引。通过压缩每个LBA扇区，并暴露一个比物理存储空间大得多的LBA空间，具有内置透明压缩功能的存储硬件将逻辑存储空间利用效率与物理存储空间利用效率解耦。这使得数据管理软件可以故意不充分利用逻辑存储空间，以换取使用不那么复杂的数据结构和算法。这可以降低实现复杂性，减少CPU/内存资源的使用，提高性能和稳定性。因此，我们建议从两个方面重新思考数据管理软件的设计:1. LBA空间未得到充分利用:带有内置透明压缩的存储硬件可以天生暴露比物理存储空间大得多的LBA空间。我们应该研究数据管理软件是否可以通过故意浪费丰富的LBA空间来使用更简单的数据结构和算法。2. 没有充分利用每个LBA:我们注意到，即使使用简单的压缩算法(如lz4和Snappy)，特殊的数据模式(如全零和全一向量)也可以被高度压缩。因此，我们应该研究数据管理软件是否可以通过故意浪费每个LBA的4KB存储空间来使用更简单的数据结构和算法(即，让每个4KB LBA扇区部分填充用户数据，并用全零向量填充)。
3、初步案例研究
根据上面的主题，我们进行了三个案例研究，将提出的主题应用于:(1)以最小的存储空间开销提高PostgreSQL的性能，(2)减少日志结构数据存储中GC的影响，(3)构建一个新的高效KV存储。所有的实验都是在商业ssd上进行的，这些商业ssd支持内置透明压缩，并且与前沿的普通NVMe ssd实现了相同的IOPS (IO / s)和吞吐量性能。
3.1、提升PostgreSQL性能
3.1.1、背景
PostgreSQL通过B-tree索引管理数据存储，将所有行版本存储在表空间中，实现多版本并发控制。因此，PostgreSQL不是直接就地更新行，而是首先将新的行版本存储在新的位置，然后依赖后台真空进程来回收死行版本占用的表空间。因此，在一行中更新非索引字段的性能很大程度上取决于PostgreSQL是否能够将新的行版本与旧的行版本存储在同一页中:
•如果承载旧行版本的页面已满，PostgreSQL必须将新行版本存储在另一个页面中。因此，PostgreSQL必须通过操作(拆分或创建)一个或多个额外的页面来相应地修改B-tree结构。这会导致额外的CPU使用和性能下降。
•如果存放旧行版本的页面有足够的空空间，PostgreSQL只会将新行版本添加到该页面。通过保持b树结构的完整性，这将导致非常低的CPU使用率，从而带来更高的速度性能。
上面的事实揭示了TPS(每秒事务数)性能和存储空间使用之间的基本平衡:当向页面插入新行时，如果我们没有完全填充页面并保留剩余的空空间以吸收未来的更新，我们可以提高TPS性能。然而，这同时也导致了更大的存储空间使用。PostgreSQL允许用户通过公开一个名为fillfactor的参数来配置这种权衡。它是一个介于10到100之间的百分比值，控制插入的行填充每个页面的满度。它的默认值是100，也就是说，每个页面100%被插入的行填充，因此不会为将来的更新保留任何空间。
3.1.2、基本概念及实验结果
内置透明压缩的存储硬件使得PostgreSQL在性能和存储成本之间的权衡变得更少，这为以最小的存储成本提高PostgreSQL的TPS性能提供了一个独特的机会。正如上面在第2节中指出的，像全零这样的特殊数据模式可以被高度压缩。同时，当fillfactor小于100时，PostgreSQL将每个页面中的保留空间初始化为0。因此，当在内置透明压缩的ssd上运行PostgreSQL时，每个页面中的全零段只占用非常少的物理闪存存储空间。因此，通过分离逻辑存储空间和物理存储空间的使用效率，内置透明压缩的存储硬件允许PostgreSQL在物理存储空间使用很小的增长的情况下，积极地降低填充因子以提高TPS性能。
为了进一步演示这个概念，我们在PostgreSQL(10.10版本)上使用Percona Sysbench-TPCC OLTP基准测试[3]进行了实验。我们使用了一台32核3.3GHz Xeon CPU和64个客户端线程的服务器。为了进行比较，我们在一个3.2TB NVMe SSD和一个内置透明压缩的3.2TB SSD上进行了相同的实验。通过保持fillfactor为默认值100，PostgreSQL TPS是3214和物理存储使用740 gb的NVMe SSD, PostgreSQL的TPS是3128，物理存储使用是178GB(例如，Sysbench数据集可以从740GB压缩到178GB)在内置透明压缩的SSD的情况下。通过将填充因子降低到75，在NVMe SSD的情况下，PostgreSQL的TPS提高到4265，物理存储占用率上升到905GB;在内置透明压缩的SSD的情况下，PostgreSQL的TPS提高到4330，物理存储占用率略微增加到198GB。如图2所示，结果表明，通过简单地配置填充因子参数，PostgreSQL可以明显地从逻辑与物理存储空间利用率的解耦中受益。
3.2、降低GC的影响
3.2.1、背景
日志结构设计原则已广泛应用于现代数据管理系统的实现，如面向ssd的文件系统和KV存储。由于日志结构的数据存储不执行就地更新，过时的数据将随着时间的推移而累积，导致数据存储膨胀(或空间放大)。为了限制存储空间放大，存储系统需要周期性地进行后台GC操作，以写放大为代价回收存储空间。这导致了空间放大和写放大之间的基本平衡:让Cval和Cinval表示日志结构数据存储中有效和无效数据的数量。定义γ = (Cval + Cval)/Cval为数据膨胀因子，当γ大于给定的阈值γth时，我们触发GC。当我们降低阈值γth时，运行时数据膨胀将变得不那么显著(即峰值空间放大将减少)，同时GC诱导的写放大将增加，因此GC将更明显地降低系统性能。
3.2.2、基本设计理念
根据提出的主题，我们提出了一种称为虚拟数据修剪的方法，以减少日志结构数据存储受空间放大与写入放大权衡的影响。如图3所示，基本概念是将无效数据元素的内容重置为全零，这样我们就可以依赖透明压缩而不是GC来回收无效数据占用的物理存储空间。它只会减少物理存储空间的膨胀，而不会改变逻辑存储空间的膨胀。因此，一旦我们根据物理存储空间膨胀来调度GC，我们就可以减少GC操作的频率，这可以减少GC引起的写放大，从而减少它对系统性能的影响。
我们注意到，虚拟数据修剪也会导致写放大，因为它执行读-修改-写以重置数据内容。因此，只有当它引起足够小的写放大时，我们才应该执行虚拟数据修剪。对于4KB的SSD扇区大小，我们提出以下策略来实现虚拟数据修剪:在每个4KB扇区中，让Sval表示有效数据量，并定义γ(s) = 4KB/Sval。我们只对那些γs大于阈值γth的扇区执行虚拟数据修剪。我们注意到，如果Sval为0(即4KB扇区只包含无效数据)，我们可以简单地修整整个扇区，而不是使用虚拟数据修整。因此，我们应该修改GC调度如下:让C(l) val和C(l) inval表示有效数据和无效数据所占用的逻辑存储空间，C(l) trim表示已被修剪的无效数据的数量。我们定义调整膨胀因子γt，并在γt大于阈值γth时触发GC。
3.2.3、初步实验结果
为了初步评估提出的设计方法，我们实现了一个简单的日志结构的数据存储，它由许多64MB的段组成。同时，只有一个段是打开的，以仅追加的方式接收插入/更新的数据元素。一旦打开的段达到64MB，它将被关闭，一个新的空段将被打开。在每个GC操作期间，我们在所有封闭段中搜索，并选择垃圾率最高的段进行回收。为了比较，我们研究了两种场景:(1)当前实践:按照当前日志结构数据存储设计的实践，所有的封闭段都是严格不变的，我们不应用数据修剪;(2) trim -assisted:我们将建议的虚拟数据修剪到运行时回收物理存储空间，其中所有的段不再是严格不变的。我们设置每个数据元素为2KB，表1列出了测量的写放大(WA)和物理空间放大(PSA)。结果表明，所提出的设计方法确实能够在写入放大和物理空间放大之间取得更好的平衡。
3.3、基于哈希的KV库
3.3.1、背景
要实现KV存储，核心设计决策是索引数据结构，它可以是基于树的，也可以是基于散列的。然而，与之前对基于树的KV存储的大量研究相比，之前很少有研究将重点放在基于哈希的KV存储上，尽管基于哈希的方法可以支持更高的索引访问吞吐量。内存数据存储Redis似乎是唯一一个商业上成功的基于哈希的KV存储。可以说，这主要是由于基于哈希的方法的内存成本非常高，特别是与基于日志结构的归并树的方法相比。
在传统实践中，基于哈希的KV存储必须使用内存哈希表来维护从键空间到存储空间的映射。这种通过中间哈希表的间接寻址可以保证KV对在存储空间上的紧凑布局，从而最大限度地利用存储空间。同时，哈希表的内存占用与KV对的数量成正比，导致大规模基于哈希的KV存储的内存成本过高。
3.3.2、基本设计理念
遵循利用逻辑与物理存储利用率解耦的主题，我们提出了一种无表、基于哈希的KV存储设计方法，如图4所示。其基本思想是直接将键空间散列到逻辑存储空间上，而不需要经过中间散列表。特别地，设K表示KV存储的密钥空间，L表示逻辑LBA存储空间。我们使用一个哈希函数fK→L将Ki∈K每个键哈希到一个LBA Lj∈L。通过避免使用哈希表，消除了传统实现基于哈希的KV存储所面临的内存开销障碍。此外，它减轻了CPU对哈希表的管理/搜索，从而减少了CPU的使用。如上所述，通过内存哈希表间接寻址可以确保在逻辑存储空间上紧凑地放置KV对。相反，如图4所示，所提出的方法基本上受到逻辑存储空间未充分利用的影响(即，几乎所有LBAs都有空闲空间未被占用)。一旦我们将未占用空间的内容保持为全零，带有内置压缩的存储硬件自然会保留未充分利用的物理存储。
将这种简单的设计方法转变为商业上可行的KV存储肯定是不平凡的，必须充分解决几个开放的问题和克服许多工程挑战。例如，当超过4KB的KV对被哈希到同一个LBA上时，我们应该有效地处理发生哈希溢出的情况。在这种情况下，我们应该使用一个单独的数据存储来托管这些溢出的KV对。此外，给定键空间K，我们必须使LBA空间(即|L|)足够大，以便使哈希溢出率足够低(如低于1%)。因此，随着密钥空间大小的变化，我们必须相应地调整LBA空间的大小，同时保证对运行时KV存储性能的影响最小。开发一个数学公式框架来指导运行时LBA空间的调整也是非常可取的。
3.3.3、实验初步结果
我们实现了一个初步的KV库原型，可以实现基本的GET和PUT操作，并使用嵌入式SQLite吸收溢出的KV对。KV store以异步方式处理所有PUT请求，即客户端线程将PUT请求记录到WAL (write-ahead log)中，提交到队列中，后台线程采用异步IOs的批处理方式处理该队列。正如[16]中指出的，使用异步IOs可以在低CPU使用率下非常有效地提高吞吐量。为了提高操作并行性，我们将一个表空间划分为多个部分，每个部分有自己的PUT请求队列，并与一个处理PUT请求队列的后台线程相关联。所有GET请求都是通过客户端线程同步直接ios由来处理的。为了评估，我们在这个KV库原型和RocksDB上进行了如下配置的实验:加载20亿对KV，每个key和值分别为16字节和400字节。我们保留了RocksDB的默认设置，后台线程池大小为32。对于我们的KV存储原型，我们将表空间划分为16个部分。表2列出了以7:3的GET和PUT比率运行32个客户端线程时的测量结果。结果表明，与流行的RocksDB相比，无表哈希KV存储具有非常大的潜力，可以实现显著的更高性能，同时消耗更少的CPU周期和几乎为零的内存容量。
4、相关工作
研究团体长期以来一直在研究在数据库中应用压缩的好处和权衡[6,19,28,14,23]，并研究了在文件系统级[9,8]和块设备级[20,17]上透明压缩的实现。通过实现一个内置透明压缩的SSD模拟器，Zuck et al.[32]研究了将透明压缩集成到SSD的选项，并展示了其在不牺牲TPS性能的情况下降低关系数据库存储成本的潜力。以前的大多数工作都是研究压缩的使用，仅仅是为了降低数据存储成本。相比之下，这项工作研究的是在内置透明压缩的存储硬件存在的情况下简化数据管理软件的潜力。
5、结论
该意见书首次指出，通过将逻辑存储空间利用率与物理存储空间利用率解耦，内置透明压缩的存储硬件有望创新数据存储管理软件。其核心主题是使数据存储管理软件有意地、适当地充分利用逻辑存储空间，以换取使用更简单的数据结构和算法，从而进一步降低实现复杂性和更高的性能。我们进行了三个初步的案例研究，将该设计主题应用于关系数据库和KV存储环境中，结果很好地证明了该设计的前景。
6、讨论
考虑到数据管理软件生态系统的广阔前景，随着研究社区开始探索这个提议的方向，将会有许多开放的问题和无法预见的机会。在这里，我们列出了几个悬而未决的问题，希望它们能起到催化剂的作用。
更多关系数据库的应用:这篇意见书展示了PostgreSQL如何通过简单配置一个参数就能从提出的主题中获益。目前还不清楚其他流行的关系数据库(如MySQL和Oracle)如何利用这个主题。因为他们使用不同于PostgreSQL的策略来实现MVCC，我们认为，为了获得类似的好处，可能需要适当地修改他们的源代码。
集成到日志结构数据存储:本文介绍了应用虚拟数据修剪来减少日志结构数据存储GC影响的初步结果。还需要进行更多的研究，以充分了解其中的利弊，并研究如何将所提出的技术实际地集成到真实世界的日志结构数据存储中。
无表哈希KV库的实现:本文概述了提出的无表哈希KV库的基本思想。通过消除消耗内存的哈希表，它有望成为高性能、低成本的替代品，取代现有的KV存储，如RocksDB。当然，还有许多有待解决的问题，例如，如何最有效地处理哈希溢出，如何在最小的性能影响下实现LBA空间大小调整，以及如何支持快照和事务等附加特性。
数据分析的应用:数据分析通常采用列存储，提高性能，降低存储成本。然而，在今天的列存储中大量使用压缩使得它几乎不可能有效地为事务性查询提供服务。列存储可能会利用解耦的逻辑存储空间与物理存储空间利用率来缓解这个问题，这仍然是一个完全开放的问题。
对文件系统的应用:作为任何文件系统的核心操作，存储空间分配和索引涉及到存储空间利用效率和实现复杂性(和性能)之间的权衡。这显然导致了在文件系统上下文中利用拟议主题的潜力。
用于hdd的基于ssd的缓存的应用程序:用基于ssd的缓存来补充hdd可以在适当的成本开销下提高存储系统性能。在传统的实践中，缓存必须维护一个复杂的索引数据结构，以管理HDD存储空间和基于ssd的缓存空间之间的映射。根据提出的设计主题，我们可以设想一个缓存设计解决方案，它可以避免显式使用索引，从而降低基于ssd的缓存的实现复杂性。
亮点 ：之前关于数据管理系统的大部分研究集中在寻找存储成本和实现/性能成本之间 的更好的设计折衷。但是随着内置透明压缩的存储硬件出现在主流市场上，数据管理软件的 设计变得有必要。 背景 ：内置透明压缩的存储硬件可以将逻辑存储空间利用率与物理存储空间利用率解 耦，这为数据管理软件(如数据库和文件系统)的创新带来了机遇。在传统的存储硬件上运行 时，数据管理软件对物理存储空间的利用效率全权负责。因此，数据管理软件要权衡存储的 利用效率和实现的复杂性。为了提高存储空间利用率，数据管理软件需要更复杂的数据结构 和算法去充分利用逻辑存储空间。相比之下，数据管理软件在内置透明压缩的存储硬件上运 行时，可以在依赖存储硬件保持物理存储空间效率的同时，有目的地浪费逻辑存储空间，降 低实现复杂度来获得更高的速度性能和更好的系统稳定性。 设计动机 :1. 逻辑空间未得到充分利用:带有内置透明压缩的存储硬件可以天生暴露比 物理存储空间大得多的逻辑空间。2. 没有充分利用每个逻辑块，即使使用简单的压缩算法， 特殊的数据模式(如全零和全一向量)也可以被高度压缩。 研究点 ：数据管理软件是否可以通过故意浪费丰富的逻辑空间来使用更简单的数据结构 和算法。 三个研究案例 : (1)以最小的存储空间开销提高 PostgreSQL 的性能。PostgreSQL 不直接就地更新行， 而是首先将新的行版本存储在新的位置，然后依赖后台真空进程来回收死行版本占用的表空 间。因此，如果存放旧行版本的页面有足够的空空间，PostgreSQL 只会将新行版本添加到 该页面。通过保持 b 树结构的完整性，这将导致非常低的 CPU 使用率，从而带来更高的速度 性能。本文通过修改 fillfactor 的参数进行了实验。 (2)减少日志结构数据存储中垃圾收集的影响。日志结构的数据存储不执行就地更新， 过时的数据将随着时间而累积，导致数据存储膨胀(或空间放大)。为了限制存储空间放大， 存储系统需要周期性地进行后台 GC 操作，以写放大为代价回收存储空间。本文提出虚拟数 据修剪法，以减少日志结构数据存储受空间放大与写入放大权衡的影响。将无效数据元素的 内容重置为全零，依靠透明压缩而不是 GC 来回收无效数据占用的物理存储空间。它减少了 物理存储空间的膨胀，就可以减少 GC 操作的频率，减少 GC 引起的写放大，从而减少它对系 统性能的影响。 (3)构建一个新的高效 KV 存储。传统基于哈希的方法的内存成本非常高。本文提出了一 种无表、基于哈希的 KV 存储设计方法。直接将键空间散列到逻辑存储空间上，而不需要经 过中间散列表，消除了传统实现基于哈希的 KV 存储所面临的内存开销障碍，减轻了 CPU 对 哈希表的管理/搜索，从而减少了 CPU 的使用。