Faster：一个高效就地更新的并发键值存储_c# faster

目录

摘 要

1. 引言

2. 系统概述

3. Faster 的哈希索引

4. 内存中的键值存储

5. Faster 处理更多的数据

6. Faster 实现就地更新

7. 评估

8. 相关工作

9. 结论

---

Faster：A Concurrent Key-Value Store with In-Place Updates 论文的翻译及一些笔记

摘 要

过去的十年，在云环境中的数据密集型（data-intensive）应用程序和服务增长迅速。数据在各种边缘资源（如设备、浏览器和服务器）上创建，并由云应用程序进行处理以获得数据的内在含义或做出决策。应用程序和服务要么处理收集到的数据，要么进行实时监控和处理数据。这些应用程序通常是更新密集型的，涉及大量超出内存容量的状态。然而，它们在其访问模式中展示出明显的时间局部性。本文介绍 Faster，一种为点读，盲更新和 read-modify-write 操作设计的键值存储。Faster 将高度缓存优化的并发哈希索引与混合日志（Hybrid log）相结合：一种跨越内存和磁盘的并发日志结构的记录存储（a concurrent log-structured record store that spans main memory and storage），同时支持内存中热点数据的就地更新。实验表明，与目前广泛部署的系统相比，Faster 提高了数个数量级的吞吐量（单台机器上每秒高达 160M 的操作），并且当工作负载适应内存时，超过了纯内存数据结构系统的性能。

1. 引言

1.1 挑战及现有的解决方案

状态管理是这类应用程序和服务要面临的一个重要问题。它展示了几个独特的特征：

Large State（状态数量大）：某些应用程序访问的状态量可能非常大，远远超过内存的容量。例如，有针对性的搜索广告提供商可以为数十亿用户维护每位用户、每条广告和点击率的统计数据。此外，在二级存储器上保留不常访问的状态通常开销更少，即使它适应内存。

Update Intensity（更新操作多）：虽然 read 和 insert 操作很常见，但有些应用程序的更新流量很大。例如，每秒从传感器和设备接收数百万个 CPU 读数的监控应用程序可能需要为每个读数更新每个设备的集合。

Locality（局部性）：即使数十亿个状态对象在任何给定的时间点上可能是活动的，但只有一小部分是 "热" 的，并且伴随很强的时间局部性被频繁地访问或更新。例如，一个跟踪每个用户统计数据（平均一周）的搜索引擎可能有 10 亿用户，但在给定的时刻只有 100 万用户在积极地获取信息。此外，热集合可能会随着时间推移而改变；在我们的例子中，当用户开始和停止浏览会话时会产生该现象。

Point Operations（点操作）：假设状态由大量插入、更新和查询的独立对象组成，那么针对（基于 hash 的）点操作进行调优的系统通常就足够了。如果范围查询不常见，可以使用简单的变通方法，如索引键范围的直方图。

Analytics Readiness（分析准备）：状态更新应随时可供后续的离线分析使用；用于例如计算平均广告点击率随时间的变化。

许多系统采用的解决方案是在多台机器上划分状态，并使用纯内存数据结构，如英特尔 TBB Hash Map，这些结构针对并发性进行了优化，并支持就地更新——在当前内存位置修改数据，而不在其他位置创建新副本——以实现高性能。但是，整体解决方案花费很昂贵，并且经常未充分利用每台机器上的资源。例如，搜索引擎的广告服务平台可能将其状态划分到数百台机器的主存储器中，导致每台机器的请求率低和计算资源利用率低。此外，纯内存数据结构使故障恢复变得复杂。

键值存储是受欢迎的状态管理方案。有的键值存储旨在处理大于内存的数据，并通过将数据存储在二级存储上来支持故障恢复。过去已经提出了许多这样的键值存储。但是，这些系统通常针对 blind updates、reads 和 range scans 进行优化，而不是针对点操作（point operations）和read-modify-writes（例如，针对更新聚合）进行优化。因此，这些系统不能扩展到每秒超过几百万次的更新，即使热集合完全适应内存。Redis 和 Memcached 等缓存系统针对 point operations 进行了优化，但速度较慢，并且依赖数据库或 KV 存储等外部系统进行存储和/或故障恢复。并发性、在内存中的就地更新和处理大于内存的数据的能力的结合在我们的目标应用程序中很重要；但是现有系统不能同时满足这些特征。我们将在第 8 节详细讨论相关工作。

1.2 介绍 Faster

本文描述了一种新的并发键值存储，称为 Faster，旨在为涉及更新密集型状态管理的应用程序提供服务。Faster 的接口（2.2节和附录E）除了 read 之外，还支持在实践中的两种状态更新：blind updates，即盲目地用新值替换旧值 和 read-modify-writes（RMWs），即值是基于当前值和输入（可选）自动更新的。特别地，RMW 更新使我们能够支持部分更新（例如，更新一个 value 中的单个字段）以及可合并的聚合（mergeable aggregates）（例如，求和、计数）。作为点操作存储，Faster 实现了每秒 1 亿次操作的内存吞吐量。在支持大于内存的数据的同时保持如此高的性能需要仔细的设计和构建框架。我们做出以下贡献：第2节。对于一个可扩展的线程模型，我们将标准的基于 epoch 的同步增强到一个通用框架中，该框架通过触发 action 来促进全局变化到所有线程的惰性传播。该框架提供了 Faster 的线程，在 epoch 保护的安全下，可以无限制地访问内存。在整篇文章中，我们强调了这种概括有助于简化我们的可扩展并行设计的例子。

第3、4节。我们提出了一个并行的无锁的、可调整大小的高速缓存 hash 索引的设计。当与标准内存记录分配器结合时，它充当内存键值存储，我们发现它比目前流行的纯内存数据结构具有更好的性能和可伸缩性。

第5、6节。日志结构是一种众所周知的技术，用于处理大于内存的数据并支持简单的故障恢复。它基于 read-copy-update 策略，其中对记录的更新是在日志的新副本上进行的。我们发现这样的设计可能会限制 Faster 的吞吐量和可扩展性。如前所述，就地更新对性能至关重要。在这方面，我们提出了混合日志（HybridLog）：一种新的混合日志，它无缝地将就地更新与传统的附加日志相结合。混合日志组织允许 Faster 对 "热" 记录执行就地更新，并对较冷的记录使用读拷贝更新（RCU）。此外，它通过对驻留在内存中的内容进行整理（shaping）来充当高效的缓存，而无需任何记录或每一页的统计信息。这样做同时要求我们解决新的技术挑战。6.5 节概述了出现故障时 Faster 的一致性保证。

第7节。我们使用 YCSB 基准进行了详细测评，结果表明应用混合日志技术的 Faster 拥有 "高达几个数量级" 的更好的性能表现和接近线性的可扩展性。此外，与目前最先进、开销更大的缓存技术相比，我们使用仿真来更好地理解混合日志的缓存行为。

Faster 遵循快速处理普通例子的设计理念。通过谨慎地（1）使用缓存并发无锁哈希索引提供对记录的快速点访问（point-access）；（2）选择何时以及如何执行昂贵或不常见的操作（如调整索引大小、检查点和从内存中逐出数据）;（3）允许线程在大多数情况下执行就地更新，速度超过了纯内存系统对内存工作负载的吞吐量，同时支持大于内存的数据并适应不断变化的热点集合。

作为使用动态代码生成的高级语言组件，Faster 模糊了传统 KV 存储和流系统中使用的仅更新 "状态存储" 之间的界限（例如，Spark State Store 和 Flink）。此外，混合日志是面向记录的，近似按时间排序的，可以输入到基于扫描的日志分析系统中（参见附录F）。

在本文中，借助于 Faster 和 HybridLog 的帮助，主要展示的结果是有可能实现所有这些：高更新速率、通过限制内存占用而实现的低成本、对大于内存的数据的支持，以及当工作集适应内存时超过纯内存数据结构的性能。

2. 系统概述

Faster 是一个并发的无锁（latch-free）的键值存储，旨在实现跨线程的高性能和可扩展性。在我们的设计中，我们广泛使用了无锁原子操作，如 compare-and-swap，fetch-and-add 和 fetch-and-increment（参见附录A），并大量利用了扩展的基于 epoch 的同步框架（ 2.3节 ）帮助我们支持就地更新。

2.1 Faster 的架构

图1 显示了 Faster 的整体架构。它由保存键值记录指针的哈希索引（hash index）和分配并管理单个记录的记录分配器（record allocator）组成。index（ 第3节 ）提供非常高效的基于哈希的哈希桶访问。哈希桶是缓存行大小的哈希桶条目数组。每个条目包括一些元数据和一个由记录分配器提供的地址（逻辑的或物理的）。记录分配器存储和管理单个记录。Faster 未在索引级别解决的哈希冲突，而是通过将记录组织为链表来进行处理。每个记录都由记录头、键和值组成。键和值可以是固定或可变的。记录头包含一些元数据和指向链表中前一条记录的指针。请注意，与许多传统设计不同，键不是 Faster 哈希索引的一部分，这有两点好处：

 （1）它减少了 hash 索引的内存占用，允许我们将它完全保留在内存中。

（2）它将用户数据和索引元数据分开，这允许我们将 hash 索引与不同的记录分配器混合和匹配。

对 Faster 哈希索引的总结：

(1) 它是连续的一个数组，每个单元等于 cache-line 的大小。

(2) 维护了指向数据项的指针（数据项通过链表链接）和元数据，但索引项不维护键（减少索引的内存轨迹、索引和数据项分离/解耦）。

我们在本文中描述了三个分配器（图1中的表格总结了它们的功能）：内存分配器（第4节）实现无锁访问和记录的就地更新；追加日志结构分配器（第5节）提供无闩锁访问，可以处理大于内存的数据，但不需要就地更新；最后是一个新的混合日志（Hybrid-Log）分配器（ 第6节 ），它将无锁并发访问与就地更新以及处理大于内存的数据的能力相结合。

2.2 用户接口

Faster 支持读取、高级用户定义的更新和删除。我们使用动态代码生成将编译期间作为用户定义的委托提供的更新逻辑集成到存储中，从而产生一个高效的存储，并对高级更新提供本机支持。我们在附录 E 中介绍了代码生成。生成运行时的 Faster 接口由以下操作组成：

Read：读取一个键对应的值。

Upsert：用新的值盲目地（存在值）替换键对应的值。如果键不存在，则插入一个键值对。

RMW：使用用户在编译时提供的更新逻辑，基于现有值和输入（可选）更新键值。我们称之为 read-modify-write（RMW）操作。用户还提供更新的初始值，当键不在存储中时使用。此外，用户可以在编译时指示 RMW 操作是 mergeable，也称为 CRDT（Conflict-Free Replicated Data Type，无冲突的复制数据类型）。这种数据类型可以计算出部分值，这些部分值随后可以被合并，从而获得最终的值。例如，基于求和的更新可以计算出部分和，然后将部分和相加得到最终的值。

Delete：从存储中删除一个键。

此外，由于本文介绍的几个原因，一些操作可能会在 Faster 中挂起。在这种情况下，Faster返回 PENDING 状态；线程定期发出 CompletePending 请求，以处理与该线程相关的未完成挂起操作。

2.3 Epoch Protection 框架

Faster 基于一个旨在实现可伸缩性 key 的设计原则：避免公共快速访问路径（common fast access path）中线程之间昂贵的协调。Faster 的线程一般是独立运行的，大多数时间没有同步操作。与此同时，它们需要就共享系统状态上同步的通用机制（common mechanism）达成一致。为了实现这些目标，我们将多线程 epoch protection 的思想扩展到一个框架中，该框架支持对任意全局操作的惰性同步（lazy synchronization）。虽然像 Silo、Masstree 和 Bw-Tree 这样的系统已经将 epoch 用于特定的目的，但我们将其扩展到一个通用框架，可以作为 Faster 和其他并行系统的构建模块。我们接下来描述 epoch protection，并描述它作为一个框架在 2.4 节中的使用。

Epoch Basics。系统维护一个共享的原子计数器 E，称为当前 epoch，可以由任何线程递增。每个线程 T 都有一个本地版本的 E，用 ET 表示。线程定期刷新它们的本地 epoch 值。所有线程本地的 epoch 值 ET 存储在一个共享的 epoch table 中，每个线程有一个高速缓存行。如果所有线程都具有比 c 更高的 ET，即任意线程的 ET > c，则称 epoch c 是安全的。请注意，如果 epochc 是安全的，则小于 c 的所有 epoch 也是安全的。我们还维护了一个全局计数器 ES，它跟踪当前最大的安全 epoch。ES 通过扫描 epoch 表中所有的条目得到，并在线程刷新其 epoch 时更新。系统保持以下不变式：任意线程 : ES < ET ≤ E。 

Trigger Actions。当一个 epoch 变的安全时，我们使用触发器操作来增强基础的 epoch 框架，从而提高执行任意全局操作的能力。当增加当前 epoch 时，比如说从 c 到 c +1，线程可以另外关联一个 action，该 action 将由系统在 epoch c 是安全时触发。这可以使用 drain-list 来实现，这是一个 (epoch,action) 对列表，其中 action 是在 epoch 安全后必须调用的回调代码片段。该表是使用一个小数组来实现的，每当 ES 更新时，该数组都会扫描准备触发的操作。我们在数组上使用原子的 compare-and-swap 来确保一个 action 只执行一次。为了增强可伸缩性，我们只在当前 epoch 发生变化时才重新计算 ES 并扫描排出列表。

2.4 使用 Epoch 框架

我们使用以下四个可由任何线程调用的操作来展示 epoch protection 框架：

Acquire：为 T 保留一个条目并设置 ET 为 E。

Refresh：将 ET 更新为 E，将 ES 更新为当前最大安全 epoch，并触发 drain-list 中的任何就绪 action。

BumpEpoch（Action）：将计数器 E 从当前值 c 增加到 c + 1，并将 (c,Action) 添加到 drain-list。

Release：将 ET 从 epoch 表中删除。

带有触发 action 的 epoch 可以用来简化并行系统中的惰性同步。考虑一个典型的例子，当一个共享变量的状态更新为 active 时，一个函数 active-now 必须被调用。线程自动将状态更新为 active 状态，并以 active-now 作为触发 action 来触发 epoch。并非所有线程都会立即观察到这种状态的变化。然而，当它们刷新它们的 epoch 时，它们都保证观察到这一变化（使用内存栅栏的顺序内存一致性）。因此，只有在所有线程都看到 active 状态并因此是安全的之后，才会调用 active-now。

我们在 Faster 中使用 epoch 框架来协调系统操作，如内存安全垃圾回收（ 第4节 ）、索引大小调整（附录 B）、循环缓冲区维护和页面刷新（ 第5节 ）、共享日志页面边界维护（ 6.2节 ）和检查点（ 6.5节 ），同时为读取和更新等用户操作提供更快的线程对共享内存位置的无限制无锁访问。

2.5 Faster 线程的生命周期

作为本文中的官方示例，我们使用 Faster 来实现计数存储，其中一组 Faster 用户线程使用传入的附加值，令原本的值递增（即 RWMs 操作）。线程调用 Acquire 向 epoch 机制注册 ET。接下来，它发布一系列用户操作，以及定期调用 Refresh（例如，每 256 个操作）以更新 ET 和 ES，并扫描 drain-list 以触发 CompletePending（例如，每 64K 个操作）来处理先前未完成的操作。最后，线程调用 Release 来取消 Faster 的注册，即结束生命周期。

3. Faster 的哈希索引

Faster 的一个关键部分是哈希索引，这是一个并发、无锁、可扩展且可调整大小的哈希索引。如第 2 节所述，索引与返回逻辑或物理内存指针的记录分配器一起工作。为了便于说明，我们假设一台 64 位机器有 64 字节的高速缓存行。在更大的架构上，我们希望有更大的原子操作，允许我们的设计扩展。第 4、5 和 6 节，我们将该索引与不同的分配器配对，以创建具有不断增长功能的键值存储。

3.1 索引组织

Faster 索引是一个连续数组，存储在内存中。它共有 2k 个哈希桶，每个桶的大小等于一个cache-line，并具有与 cache-line 相同的对其方式（图2），操作的时候直接读取整个桶（以 64 位机器为例，一个索引项大小为 64 字节）。因此，64 字节的桶由 7 个 8 字节的哈希桶条目（hash bucket entries，即索引项）和一个 8 字节的条目（用作溢出桶指针）组成。每个溢出桶也都具有 cache-line 大小和对齐方式，并使用内存分配器按需分配。

 8 字节条目的选择至关重要，因为它允许我们使用 64 位原子的 compare-and-swap 操作对条目进行无锁操作。在 64 位机器上，物理地址通常不到 64 位；例如，英特尔机器使用 48 位指针。因此，我们可以利用额外的位来进行索引操作（Faster 至少需要一位）。在本文的其余部分，我们使用 48 位指针，但是请注意，我们可以支持长达 63 位的指针。

每个索引项由三部分组成：Tag（15位）、Tentative bit（暂定位，1位）和地址（48位）（源码与论文有差异，源码中 Tag 占 14 位）。值为 0 的项表示空槽（An entry with value 0 (zero) indicates an empty slot）。在具有 2k 个哈希桶的索引中，Tag 用于将索引的有效哈希分辨率从 k 位提高到 k + 15 位，通过减少哈希冲突提高性能。哈希值为 h 的键的哈希桶首先使用 h 的前 k 位来标识，称为 h 的偏移量。h 的后 15 位称为 h 的标签。标签仅用于提高哈希分辨率，并且可以更小，或者根据地址的大小完全移除。Tentative bit 是插入所必需的，用于保证插入等 CAS 操作的安全性，稍后将会介绍。

3.2 索引操作

Faster 索引基于不变式（invariant），即每个 (offset,tag) 都有一个唯一的索引项，该索引项指向一个记录集合，这些记录的键的哈希值和 (offset,tag) 匹配。确保这种不变式，同时支持索引项的并发无锁读取、插入和删除是一项挑战。

查找和删除一个索引项。定位对应于一个键的索引项很简单：我们使用 k 个哈希位来识别哈希桶，扫描桶以找到匹配标签的索引项。从索引中删除一个索引项也很容易：我们使用 compare-and-swap 用 0 替换匹配的索引项（如果有的话）。

插入一个索引项。考虑这样一种情况，在桶中存在空的索引项，必须插入一个新的索引项。一种简单的方法是寻找一个空的索引项，并使用 compare-and-swap 插入标签。然而，两个线程可能同时在桶的两个不同的空索引项中插入相同的标签，该情况破坏了我们的不变式。作为一种变通方法，考虑一种解决方案，其中每个线程从左到右扫描桶，并确定性地选择第一个空索引项作为目标。它们将使用 compare-and-swap 来竞争插入，但只有一个会成功。这种方法甚至违反了存在删除时的不变式，如图 3a 所示。线程 T1 从左到右扫描桶，并选择空索引项 5 来插入 tag g5。另一个线程 T2 从同一个桶中索引项 3 的位置删除 tag g3，然后尝试插入一个带有相同 tag g5 的键。从左到右扫描将导致线程 T2 为该标签选择第一个空索引项 3。可以看出，独立选择空索引项并直接插入的算法都存在这个问题：就在线程 T1 执行 compare-and-swap 之前，它可能会被换出，数据库状态可能会任意更改，包括另一个具有相同标记的索引项。

虽然给桶加锁是一个可行的（但很重要的）解决方案，但 Faster 使用了一种无锁的两阶段插入算法，该算法利用了 tentative bit。一个线程找到一个空索引项，并插入带有暂定位集（tentative bit set）的记录。设置了暂定位的索引项被视为对并发读取和更新不可见。然后，我们重新扫描桶（注意，它已经存在于我们的缓存中），以检查是否存在索引项具有相同的 tag 且 tentative bit 为 1 的情况；如果存在，我们回滚并重试。否则，我们重置 tentative bit 以完成插入。因为每个线程都遵循这个两阶段方法，所以我们保证能够保持索引不变。为了了解原因，图 3b 显示了两个线程的操作顺序：不存在可能导致重复的 non-tentative 标签的交错。

3.3 调整索引大小和 checkpoint 索引

对于键的数量随时间变化很大的应用程序，我们支持动态调整 Index 的大小。我们利用 epoch保护和阶段状态机（epoch protection and a state machine of phases）以很低的开销执行大小调整（参见附录B）。有趣的是，无锁操作的使用总是将索引保持在一致的状态，即使存在并发操作。这允许我们在不获取读锁的情况下执行索引的异步模糊检查点（asynchronous fuzzy checkpoint），从而大大简化了恢复（参见 6.5 节）。

4. 内存中的键值存储

我们现在使用第三节介绍的 Faster 哈希索引构建一个完整的内存键值存储，以及一个简单的内存分配器，如 jemalloc。具有相同（offset,tag）值的记录被组织为反向单链表。索引项指向一个 list 中的尾部（该 list 是最近的记录，其实就是头插法构建的链表），而尾部又指向前一条记录，依此类推（见图1）。每条记录的大小可以是固定的，也可以是可变的，由记录头、键和值组成。记录头如图 2 所示。除了前面的指针之外，我们还使用了一些位（invalid and tombstone，即无效位和逻辑删除位）来跟踪日志结构的分配器所必需的信息（参见第 5、6 节）。这些位作为地址字的一部分存储，但如果需要，也可以单独存储。 

使用 In-Memory Allocator 的操作

在 Faster 中，用户线程在基于 epoch protection 框架的安全性下读取和修改记录值，记录级别（record-level，记录保存键值对）的并发由用户的读取或更新逻辑处理。例如，可以对计数器使用 fetch-and-add，使用记录级别锁，或者利用应用程序级别的分区进行无锁更新。接下来描述存储的操作。

Reads。我们根据哈希值找到索引项，如第 3.2 节所述，然后遍历链表以找到匹配的键值对。

Updates 和 Inserts。Upsert 和 RMW 都是从查找键的索引项开始的。如果索引项不存在，我们使用 3.2 节中描述的两阶段算法将 tag 和新记录的地址一起插入哈希桶的一个空的索引项中。如果条目存在，我们将扫描链表以找到一个与键相匹配的记录。如果存在这样的记录，我们就地执行操作。只要线程不刷新其 epoch，它就可以保证访问记录的内存位置。此属性允许线程就地更新值，而不用担心内存安全。如果这样的记录不存在，我们使用 compare-and-swap 将新记录拼接到 list 的尾部。在我们的计数存储示例中，我们增加了现有键的计数器值，使用 fetch-and-add 或普通的就地递增（如果键被分区）。插入新键的初始值设置为 0。

Deletes。我们通过在记录头或索引项（对于第一条记录）上使用 compare-and-swap 将记录从链表中分离出来，从而达到删除记录的目的。当从单链表中删除记录时，条目被设置为 0，以便将来插入。删除的记录不能立即返回内存分配器，因为在同一位置有并发更新。我们使用我们的 epoch protection 框架来解决这个问题：每个线程维护一个本地线程（以避免并发瓶颈）（epoch,address）空闲列表。当 epoch 变得安全时，我们可以安全地将它们返回给内存分配器。

5. Faster 处理更多的数据

通过构建一个日志结构的记录分配器，我们将内存中的 Faster 从第 4 节转换为一个成熟的键值存储，它可以处理比内存大的数据。日志结构是一个研究得很好的领域，我们的方法是对现有技术（如 LSM-tree）的直接修改，增加了 epoch protection 以降低同步开销。由于这种系统只支持追加，所以性能不好；我们将在第 7.4.1 节展示它实现了每秒不超过 2000 万次操作的吞吐量，并且不随线程数量而扩展。然而，这种设计作为一种构建模块非常有用，有助于解释我们在第 6 节中的主要贡献，我们将使用一种新型的混合日志分配器来获得可伸缩的性能。

5.1 逻辑地址空间

我们首先定义一个跨越内存和二级存储器的全局逻辑地址空间。记录分配器分配并返回与该地址空间中的位置相对应的 48 位逻辑地址。与我们的纯内存版本不同，Faster 的哈希索引存储的是记录的逻辑地址，而不是其物理地址。逻辑地址空间使用尾部偏移量（tail offset）来维护，该偏移量指向日志尾部的下一个空闲地址。一个额外的偏移量，称为头偏移量（head offset），跟踪内存中可用的最低逻辑地址。头部偏移与尾部偏移保持大致恒定的距离，代表日志可用的内存。为了最小化开销，我们只在尾部偏移跨越页面边界时更新它。

当前 head 和日志的 tail 之间的连续地址空间存在于有界限的内存循环缓冲区中，如图 4 所示。循环缓冲区是固定大小的页帧的线性数组，每个页帧大小为 2F 字节，每个页帧被分配为与底层存储设备扇区对齐，以便允许无缓冲的读取和写入，而无需额外的内存拷贝。一个大于 head 地址的逻辑地址 L 存在于内存的偏移量等于 L 的后 F 位，在页帧中位置等于圆形数组中L >> F。

新记录分配总是发生在 tail。我们将 tail 偏移用两个值保存——页码和偏移量。为了提高效率，线程使用 fetch-and-add 来分配内存偏移量；如果偏移量对应于不适合当前页面的分配，它将增加页码并重置偏移量。看到新偏移量大于页面大小的其他线程等待该偏移量变得有效，然后重试。

对头、尾偏移量的总结：

(1) 尾偏移量（tail offset）：它指向日志尾的下一个空闲地址，地址用 2 个字段描述：页编号、偏移量。分配器对偏移量执行 CAS 分配，若该页满，则递增页编号并重置偏移量；其他线程看到这个情况后会等待偏移量合法，然后重试。

(2) 头偏移量（head offset）：它指向内存中最低的可用逻辑地址。它和尾偏移量保持大致相等的滞后，等于日志在内存中可用的大小，头偏移量只会在尾偏移量跨越页边界时才会更新。

5.2 循环缓冲维护

我们需要以一种无锁的方式来管理日志记录的落盘，因为线程在 epoch 边界之间执行无限制的内存访问。为了实现这一点，我们需要维护两个状态数组：一个刷新状态（flush-status）数组跟踪当前页面是否已刷新到二级存储，一个关闭状态（closed-status）数组确定页帧是否可以被回收以供重用。因为我们总是将记录附加到日志中，所以一旦创建了记录，它就是不可变的。当日志尾部进入一个新的 p+1 页时，我们用一个刷新触发 action 来触发 epoch，该 action 发出一个异步 I/O 请求，将 p 页刷新到二级存储（调用 BumpEpoch(Action)，其中 action 为"发起异步请求，将页 p 刷盘"）。只有当 epoch 变得安全时，才会调用此操作——因为线程会在操作边界刷新 epoch，所以我们可以保证所有线程都会完成对页面中地址的写入，并且刷新是安全的。当异步刷新操作完成时，页面的刷新状态被设置为刷新（即设置 flush-status 为 flushed）。

随着日志 tail 的增长，可能需要从内存中换出一个现存的页框（当日志尾不断增加时，我们需要将环形缓冲区的 head 移除，以便于日志尾重用），但是我们首先需要确保没有线程正在访问该页面。传统的数据库在每次访问之前都使用一个锁来锁定缓冲池中的页面，这样在使用时就不会被逐出。然而，为了获得高性能，我们利用 epoch 来管理换出。回想一下，head offset 决定了内存中是否有记录。为了从内存中清除页面，我们增加了 head offset，并用一个触发 action 来冲击当前 epoch，设置旧页帧的关闭状态数组（当日志头往前时，先将 head offset 递增，然后调用 BumpEpoch(Action)，其中 action 为"设置该页的 closed-status 为 closed"）。当这个 epoch 是安全的，我们知道所有线程将会看到更新的 head offset，因此不会访问这些内存地址。请注意，在更新 head offset 之前，我们必须确保被换出的页面已经完成刷盘，以便需要这些记录的线程可以从存储中检索到它。

5.3 追加日志分配器的操作

Upsert 只需在日志尾部添加一条新记录，并像以前一样使用 compare-and-swap 来更新哈希索引。如果操作失败，我们只需将日志记录标记为无效（使用了 header 的标识位），然后重试该操作。删除操作的逻辑是插入删除记录（再次使用了 header 的标识位），并要求发起日志垃圾回收（参见附录三）。

Read 和 RMW 操作类似于第 4 节中描述的内存中的操作。但是，更新总是附加到日志的尾部，并链接到前一条记录（然后使用 compare-and-swap 更新索引项，若失败，则同上）。此外，逻辑地址的处理方式也不同。对于检索到的逻辑地址，我们首先检查该地址是否大于当前头偏移量。如果大于，则直接从内存中读取。如果没有，我们会向磁盘发出一个异步读取记录的请求。作为一个记录日志，我们只检索记录，而不是整个逻辑页面。在我们的计数存储示例中，每个计数器增量都会导致将新的计数器追加到日志的尾部（如果需要，从磁盘中读取旧的值），然后进行 compare-and-swap 来更新索引项。

每个用户操作都与一个 context（上下文）相关联，该 context 使得 I/O 完成时的操作进一步继续。每个 Faster 线程都有一个本地线程挂起队列，其中包含该线程发出的所有已完成异步请求的 context。线程会定期调用一个 CompletePending 函数使这些 context 出队并处理后续部分。请注意，后续部分可能需要发出进一步的 I/O 操作，例如，针对记录链表中的前一个逻辑地址。

6. Faster 实现就地更新

上一节中介绍的追加日志分配器设计，除了处理大于内存的数据之外，由于其仅追加的特性，还支持更新的无锁访问路径。但这是有代价的：每次更新都涉及到尾部偏移量的原子增量，以创建新记录，并原子地替换哈希索引中的逻辑地址。此外，仅附加（append-only）日志增长很快，尤其是在更新密集型工作负载的情况下，这很快会使磁盘 I/O 成为瓶颈。

另一方面，就地更新在这种工作负载中有几个优点：

（1）频繁访问的记录可能在更高级别的缓存中可用（局部性强）；

（2）不同哈希桶的键的访问路径不冲突；

（3）更新较大值的部分是有效的，因为它避免了复制整个记录或维护需要压缩附加的昂贵的增量链（expensive delta chains）；

（4）大多数更新不需要修改 Faster 的哈希索引。

6.1 引入 HybridLog

混合日志（HybridLog）是一种新颖的数据结构，它结合了就地更新（在内存中）和日志结构组织（在磁盘上），同时提供了对记录的无锁并发访问。混合日志跨越内存和二级存储，其中内存中的数据充当热点数据的缓存，并适应不断变化的热点数据，提高了局部性。

在混合日志中，逻辑地址空间被分成 3 个连续的区域：（1）稳定区域（2）只读区域和（3）可变区域，如图 5 所示。稳定区域部分在磁盘上。内存中的部分由只读区域和可变区域组成。可变区域中的记录可以就地修改，而只读区域中的记录不能。为了更新当前只读区域中的记录，我们遵循 Read-Copy-Update（RCU）策略：在可变区域中创建新的副本，然后进行更新。对这种记录的进一步更新就地执行，只要它停留在可变区域中。

 我们在第 5 节的追加日志分配器上实现了 HybridLog，使用了一个额外的标记称为只读偏移量（read-only offset），它对应于驻留在内存循环缓冲区中的逻辑地址。在 head offset 和 read-only offset 之间的区域为只读区域，在 read-only offset 之后的区域为可变区域。如果一个记录的逻辑地址大于read-only offset，它将被就地更新。如果地址在 read-only offset 和 head offset 之间，我们在日志尾部创建一个更新的副本，并更新哈希索引以指向新的位置；如果地址小于 head-offset，意味着它不在内存中，因此发出一个异步 I/O 请求从磁盘中检索记录。一旦获得，在尾部创建新的更新副本，然后更新哈希索引。表 1 总结了这一更新方案。

read-only offset 与 tail offset 保持恒定的滞后，并且仅在与 head-offset 类似的跨域页面边界处更新。由于逻辑地址小于 read-only offset 的页都不会并发更新，因此将它们刷新到磁盘是安全的。随着 tail offset 的增加，read-only offset 也随之移动，使页面随时可以刷新。一旦它们被安全地存储到磁盘上，就可以使用 head offset 和关闭状态数组（像第 5 节）将它们从循环缓冲区中逐出。因此，read-only offset 充当准备刷新到磁盘的页面的轻量指示器。请注意，混合日志中的 read-only offset 允许对可变区域中的记录进行无锁访问，而在传统设计中，记录（或页面）必须在更新之前固定在缓冲池中，以防止在将它们刷新到磁盘时进行并发更新。

read-only offset 和 tail offset 之间的滞后决定了将内存缓冲区容量划分为快速的就地可更新（fast in-place updatable）和不可变的只读（immutable read-only）区域。除了帮助将页面安全地刷新到磁盘中，read-only 区域还充当一个二级缓存。在第 6.4 节中，我们讨论了缓存行为和混合日志区域大小对 Faster 性能的影响。

6.2 Lost-Update异常

read-only offset 被自动更新和读取。但是，线程仍然可能基于偏移量的旧值来决定更新方案，从而导致不正确的执行。考虑图 6 所示的场景，来自我们的计数存储示例。线程 T1 和 T3 从 Faster 哈希索引中获得相同的逻辑地址。T1 决定进行就地更新，因为 L 大于当前只读偏移 R1。同时，由于 tail offset 的移动，线程 T2 更新了从 R1 到 R2 的 read-only offset。现在，线程 T3 将 L 与 R2 进行比较，并决定在 L' 创建一个新记录，更新值为 5。但是，线程 T1 在 L 时将该值更新为5，以后的所有访问都将使用 L' 时的值，因此我们丢失了 T1 的更新。（下表应为 L > R1）

（1）键值对 (k, v) 位于只读偏移量 R1 后，偏移量记为 L。

（2）线程 T1 和线程 T3 同时获取了 L。

（3）线程 T1 比较 L > R1，准备执行 in-place 更新。

（4）线程 T2 执行了其他更新操作，将尾偏移量往后递增，并将只读偏移量递增到 R2。

（5）线程 T3 比较 L< R3，执行 RCU，拷贝并追加了 (k, v + 1)。

（6）线程 T1 开始执行就地更新，将 L 上的 (k, v) -> (k, v + 1)，但实际上应为 (k, v + 2)，即更新丢失。

发生上述异常是因为线程 T2 更新了 read-only offset，而 T1 基于当前值执行操作（T2的修改对其他线程不可见）。我们可以通过在 T1 操作的整个过程中获取 read-only offset 上的读锁来防止这种情况的发生。然而，这样的锁方案是昂贵的，并且不必要地延迟了 read-only offset 的移动，而 read-only offset 的移动对于维护循环缓冲区是不可或缺的。另一方面，即使 read-only offset 发生了偏移，也会出现异常，因为一个线程（T1）基于旧值做出更新决定，而另一个线程（T2）基于新的偏移量值做出更新决定。

我们使用另一个称为安全只读偏移量的标记来消除这种不正确的执行。该标记跟踪所有线程看到的 read-only offset。它是基于以下不变式设计的：安全的 read-only offset 是任何活跃的 Faster 线程看到的最小的 read-only offset。我们使用如下的 epoch 触发操作机制来维护它：每当 read-only offset 被更新时，我们将当前 epoch 与一个触发操作结合起来，该触发操作将安全的 read-only offset 更新为新值。这种基于 epoch 的安全的 read-only offset 更新满足不变式，因为所有跨越当前 epoch 的线程都必须看到 read-only offset 的新值。

使用附加标记，安全的 read-only offset，HybridLog 被分成 4 个区域。我们将安全的 read-only offset 和 read-only offset 之间的区域称为模糊区域（fuzzy region），因为一些线程可能会在 read-only offset 之后看到它，而另一些线程可能会在之前看到它。只有当线程刷新它们的 epoch 时，它们才能保证获得安全的 read-only offset 和 read-only offset 的最新值。因此，每个线程可能都有这些标记的线程本地视图，如图 7 所示。

注意：蓝色框框是每个线程所看到的 Fuzzy region，蓝框上面是每个线程自身视角的安全read-only offset，蓝框下面是每个线程自身视角的 read-only offset。全局的安全 read-only offset，取的是每个线程视角中最小值的 read-only offset。

线程 T4 具有最高的 read-only offset，因为它最近刷新了其 epoch，而线程 T3 是过时的值，因为它最近没有刷新。但是，请注意，任何线程的安全的 read-only offset 是最小 read-only offset，这是由我们的 epoch protection 框架确保的。当记录的逻辑地址小于安全 read-only 时，线程可能会尝试并发地创建一个新记录（因为在只读区域），由于对 Faster 哈希索引的原子 CAS 操作，所以只有一个记录会成功。

上述过程通过触发 epoch action 让该偏移量对所有线程可见：

1. 它追踪所有线程可见的 read-only offset，取其中最小的。
2. 使用 epoch 保护框架进行更新：

当只读偏移量更新时，调用 BumpEpoch(Action) 注册回调，更新安全只读偏移量到新的值。

其他线程若跨越了上面调用时的 epoch，则会触发安全只读偏移量的刷新，那么安全只读偏移量就可见了。

1. 当键值对地址小于"安全只读偏移量"，则需要执行 RCU 更新。

6.3 模糊区域（Fuzzy Region）

有趣的是，当一条记录落入模糊区域时，不同类型的更新会得到不同的处理。在这里，我们将更新类型分为三种，即 Blind Update、RMW 和 CRDT 更新。表 2 总结了每种更新类型的更新方案。

注意：对于 Mutable Region 部分而言，更新操作都是 in-place 的。而对于 Invalid 部分而言，操作都是在尾部创建一个新纪录。

Blind Update。此更新不读取键的旧值。即使一个线程正在就地更新先前的位置，另一个线程也可以在尾部用新值创建一个新记录。由于更新是并发发布的，应用程序的语义必须允许所有可能的顺序。此外，如果记录在内存中不可用，我们可以避免从磁盘中进行昂贵的检索，因为我们不需要旧值。（不需要读旧值，因此只要小于只读偏移量，就直接 RCU 追加新纪录到尾部）

RMW。这种更新首先读取记录，然后根据当前值更新记录。因为我们不能完全确定没有其他线程正在同时更新一个值，所以我们不能精确地在尾部创建一个新的副本来避免前面讨论的丢失更新异常。因此，我们通过将 context 放在待处理的队列中来延迟更新，类似于存储上的记录的处理方式。

RMW 不能直接执行 RCU，因为可能会丢失更新（6.2），因此：

1. 若小于 head offset：发起异步磁盘I/O请求，读取旧值，然后进行下一步。
2. 若小于安全 read-only offset：将更新操作随着上下文放入队列中，延迟执行，执行的是下一步。
3. 若小于只 read-only offset：在尾部创建新的记录。

CRDTs。CRDT 更新涉及若干可合并的 RMWs，但是在 blind updates 和 RMWs 之间存在一个有趣的中间地带（CRDT updates are RMWs, but present an interesting middle-ground between blind updates and RMWs）。回想一下，CRDTs 可以作为独立的部分值进行计算，这些值随后可以合并以获得最终值。我们的官方实例（计数存储）是一个 CRDT，因为多个部分的计数可以相加以获得总计数值。通过 CRDT 更新，我们可以处理类似于 blind update 的模糊区域。当一条记录位于模糊区域（或磁盘上）时，我们只需在尾部创建并链接一条新的增量记录，并对初始（空）值进行更新。读取必须协调所有增量记录以获得最终的收敛值。我们可以想象这样一个方案：周期性地折叠 delta，以保持 delta 链长度的界限。由于更新可合并，所以直接创建一个 delta 记录到尾部，并将其和之前的值用链表链起来即可，读取时扫描链表即可得到结果。

6.4 HybridLog 分析

日志的缓存行为和整理。键值存储的内存部分就像一个缓存，所以性能很大程度上取决于它的效率。在数据库中的缓冲池管理和操作系统中的虚拟内存管理的背景下，已经提出了几种高速缓存协议，例如 First-In First-Out（FIFO）、CLOCK、Least Recently Used（LRU）和 LRU 的扩展版本 LRU-K 协议。所有这些（除了 FIFO）都需要细粒度的每页（或每条记录）统计数据才能高效工作。有趣的是，由于访问模式，Faster 在每个记录粒度上实现了良好的缓存行为，而没有任何这样的开销。Faster 这种混合的 in-place 和复制更新方案（hybrid in-place and copy update scheme）是有效的缓存，非常类似于 Second-Chance FIFO 协议。我们使用 7.5 节中的模拟来比较这些协议。

简而言之：Fasterkv 的 Hybrid Log 缓冲实际上是一个新的缓冲替换协议，它非常类似于Second-Chance FIFO协议。而它和其他传统协议相比，做到了更细粒度的控制（键值对级别），且并没有过大的开销。

Faster 根据访问模式对日志进行整理，有助于将热门数据保存在内存中。在我们的计数存储实例中考虑一个写操作较大的工作负载（附录 D 解决了其他类型的工作负载）。当从磁盘检索一条记录进行更新时，将在尾部创建计数已更新的新记录。在进入混合日志的只读区域之前，该记录将保留在内存中，并可用于就地更新。如果某个键是热的，那么在将其从内存中逐出并生成新的可变记录之前，很可能会有后续的请求。这是键在内存中保持缓存的第二次机会（处于 read-only 区域的数据依然可以相应读请求，所以这种混合日志结构相对于直接刷新到磁盘的解决方案而言，给在内存中的数据提供了两次机会）。否则，它将被逐出到磁盘，为内存中更热的键腾出空间。

调整 Hybrid Log 区域的大小。Hybrid Log 分配器中可变和只读区域的大小很重要。一个极端（lag = 0）是仅追加存储，而另一个极端（lag = buffersize）是数据适应内存时的内存存储。只读区域的大小决定了提供给记录在内存中保持缓存的第二次机会的程度。较小的只读（即较大的 Mutable 区域）区域由于就地更新而产生更好的内存性能。但是，热记录可能会被逐出到磁盘，原因很简单，因为在很短的时间内无法访问该键。另一方面，更大的只读区域会导致昂贵的仅附加更新，导致日志增长更快。此外，它导致只读和可变区域中记录的复制，有效地减小了内存中的缓存大小。我们观察到，在实践中，可变和只读区域的缓冲区大小按 9:1 划分会产生良好的性能。我们在第 7.4.2 节中评估了 HybridLog 区域大小对性能的影响。

简而言之：更小的 Read-only Region 或更大的 Mutable Region 会提高更新性能（因为更容易 in-place 更新），但热点数据更容易被刷盘（假如一段时间内没访问）。而更大的 Read-only Region 或更小的 Mutable Region 表现出的更新性能相对较差，日志会更快地增长（因为更容易 RCU），但由于 RCU，减少了内存中缓存的大小。

6.5 Faster 的恢复和一致性

如果出现故障，HybridLog 未刷新的尾部将丢失。但是，Faster 可以恢复到与单调性属性一致的数据库状态：对于线程（按顺序）发出的任何两个更新请求 r1 和 r2，恢复后的状态包括：(1) none; (2) 只有 r1; 或者 (3) r1 和 r2。也就是说，恢复后的状态不能只包含 r2 而不包含 r1。我们可以使用 Write-Ahead-Log （WAL）来实现这个属性，它可以记录由于请求而产生的所有修改，类似于传统数据库和现代的键值存储（如 RocksDB）。应用程序可以定期获得内存中 Faster 的模糊检查点（Fuzzy Checkpoint），然后可以与 WAL 结合使用，恢复到一致的状态。使用 WAL 从一个模糊检查点覆盖是一个研究得很好的问题，因此我们在本文中不涉及它。

消除 WAL。有一个单独的 WAL 可能会给更新密集的工作负载带来瓶颈，所以我们为Faster 设计了一个不需要 WAL 的恢复方案。我们在下面简要概述我们的解决方案，但是将恢复的详细处理留给未来的工作。其基本理念是，我们可以将 HybridLog 视为我们的 WAL，并延迟提交，以便在有限的时间窗口内实现原地更新。

检查点更快。虽然技术上我们可以从 HybridLog 中重建整个哈希索引，但检查点索引可以更快的恢复。对 Faster 索引的所有操作都是使用原子 compare-and-swap 指令执行的。因此，检查点线程可以异步读取索引，而无需获取任何读锁。但是，由于哈希索引是并发更新的，这样的检查点是模糊的，并且可能与 HybridLog 上的位置不一致。但是，我们可以使用 HybridLog 从这个模糊检查点恢复哈希索引的一致版本，如下所述。

我们记录 HybridLog 的尾部偏移量在开始（t1）和完成（t2）之后的模糊检查点。在此间隔期间对哈希索引的所有更新仅对应于日志上 t1 和 t2 之间的记录，因为就地更新不会修改索引。然而，其中一些更新可能是模糊检查点的一部分，而另一些可能不是。在恢复过程中，我们按顺序扫描 HybridLog 上 t1 和 t2 之间的记录，并在必要时更新恢复的模糊索引。得到的索引是直到 t2 都对应于 HybridLog 的一致的哈希索引，因为在完成模糊检查点（并记录尾偏移量 t2）之后对哈希索引项的所有更新只对应于 t2 之后的日志记录。

最后，通过将 HybridLog 的 read-only offset 移动到 t2，在相应的磁盘刷新完成后，我们得到一个对应于日志位置 t2 的检查点。请注意，我们的检查点算法可以在后台执行，而无需停止数据库。每一个这样的检查点在 Faster 都是增量的，因为我们只 offload 自上一个检查点以来修改过的数据。增量检查点通常需要一个单独的类似位图的数据结构来标识需要刷新的数据，而 Faster 通过不同的数据组织方式来实现这一点。

讨论。由于就地更新，使用上述技术恢复后的状态可能违反单调性：更新 r1 可以修改位置l1 ≥ t2，而稍后的更新 r2 可能修改位置 l2 < t2。我们在 t2 之前的检查点，包括 l2 但不包括 l1，违反了单调性。有趣的是，我们可以通过使用 epoch 和触发器来恢复单调性，以便线程可以协作切换到数据库的新版本，如 HybridLog 上的一个位置所标识的那样——细节留待未来工作。

7. 评估

我们用四种方式进行评估。首先，当数据集适合内存时，我们将 Faster 的整体吞吐量和多线程可扩展性与主流的键值存储进行比较。接下来，我们通过改变内存预算，对大于内存的数据进行实验。第三，我们执行微基准测试来说明 Faster 和 HybridLog 的具体设计选择。最后，我们使用模拟来评估 Faster 的缓存行为。

7.1 实施、设置、工作负载

实施。我们在 C# 中实现了一个可用于任何应用程序的嵌入式组件，并使用代码生成来内联用户函数以提高性能。线程发出 30 秒的操作序列，我们测量在此期间完成的操作数量。我们将 Faster 指向固态硬盘上的一个文件来存储日志。我们假设一个基于过期的垃圾回收方案（附录C），并且在结果中不包括这个成本。与检查点和恢复相关的成本也不包括在内。除非另有说明，我们将可就地更新区域的大小定为内存的90%。默认情况下，我们使用 # keys 哈希桶条目来调整 Faster 索引的大小。虽然 Faster 可以与内存分配器配对，但本文中的所有实验都使用混合日志，因此代表了 Faster 键值存储的完整版本，它可以处理比内存更大的数据。

设置。实验在两台相同的机器上进行，一台运行 Windows Server 2018，另一台运行 Ubuntu Linux（针对其他系统，因为它们针对 Linux 进行了优化）。两台都是戴尔 PowerEdge R730 机器，配备 2.60GHz 英特尔至强处理器 E5-2690 v4 处理器。它们有 2 个插槽，每个插槽有 14 个内核（28个超线程）。它们有 256GB 的内存和一个 3.2TB 的融合 NVMe 固态硬盘用于日志。我们尽可能将线程固定在硬件内核上。双插槽实验跨插槽分割线程，随着线程数量的增加，渐变更加平滑。我们将输入数据集预加载到内存中，并运行每个测试 30 秒，除了 RocksDB，这将在下面描述。

工作量。我们使用雅虎云服务基准的 YCSB-A 工作负载的扩展版本，有 2.5 亿个不同的 8字节键，8 字节和 100 字节的值大小。对于工作负载中的读取和盲更新部分，工作负载被描述为 R:BU。此外，除了基准支持的盲更新之外，我们还添加了 RMW 更新。在实验中，这样的更新被表示为 0:100 RMW（在本文中我们只完成了 100% 的 RMW 更新实验）。RMW 更新从用户提供的带有 8 个条目的输入数组中增加一个数值，来模拟一个按键运行的 "求和" 操作。

除了提供的 uniform 和 zipfian（θ = 0.99）分布之外，我们在一些实验中添加了一个新的热集分布，它对一组冷热键进行建模，项目从冷到热移动，在热状态下停留一段时间，然后变冷。例如，这种分布为搜索引擎的用户建模。

基线系统。我们将 Faster 与两类系统进行比较：纯内存系统和大于内存的系统。在纯内存类别中，我们针对高性能纯内存范围索引 Masstree 和高度优化的纯内存哈希索引英特尔 TBB 并发哈希映射进行评估。在能够处理大数据的系统类别中，我们针对 RocksDB 和 Redis 这两家主流的键值存储进行评估。请注意，我们将比较添加到使用范围索引的存储中，主要是因为这种系统被广泛部署，即使是针对点操作的工作负载，并且众所周知，它对内存（Masstree）和大于内存（RocksDB）进行了高度优化。我们配置了 RocksDB，禁用了预写日志记录和校验和，参数如 RocksDB Wiki 所建议。我们使用直接输入/输出进行读写，每次测试运行 10 分钟。在 MassTree 中，我们使用默认配置，将软件线程固定在内核上。借助英特尔 TBB，我们将值在线存储在哈希映射中。Redis 在 7.2.4 节中单独评估。

7.2 与现有系统的比较

7.2.1 单线程性能。

对于单个线程，我们使用 YCSB（8字节有效负载）和 100% 的 RMW工作负载，以及不同百分比的 Read 与 Upsert（数据集拟合在内存中）。uniform 和 zipf 的结果分别如图 8a 和图 8b 所示。我们注意到，Faster 能够实现非常高的单线程吞吐量，这使得它非常适合嵌入的环境。此外，Faster 处理的数据比内存大，它的性能也优于纯内存系统。

7.2.2 所有线程性能。

我们使用所有 56 个线程（在两个插槽上），并与之前具有相同工作负载的系统进行比较。图 8c 和图 8d 分别示出了 uniform 和 zipf 的结果。Faster 能够实现最高 115M ops/s的 uniform 吞吐量，以及165M ops/s的 zipfian 工作负载吞吐量。有趣的是，英特尔 TBB 哈希在 uniform 方面做得很好，但在 zipf 分布方面面临一些争议，无法扩展。如预期的那样，其他系统的性能要低得多。

我们还运行了改变索引中标签大小的实验，以检查它对吞吐量的影响。简而言之，对于所有线程上的 YCSB 50:50 uniform 工作负载，我们发现即使标签只有 1 位（或 4位），性能也下降了不到 14%（或 5%），这验证了 Faster 可以稳健地处理更大的地址大小。

7.2.3 可扩展性。

我们使用 zipf 分布来绘制性能，线程数量不断增加，使用一个 CPU 和两个 CPU。我们首先评估 100% RMW YCSB 的工作负载，图 9a 中有 8 个字节的有效负载。我们在一个 CPU 和两个 CPU 上都可以很好地看到快速缩放。Masstree（纯内存范围索引）也可以很好地扩展，但绝对性能要低得多。Intel TBB 哈希映射在一个 CPU 内可以很好地扩展，但在两个 CPU 上运行时，在 20 个左右的核上就会出现问题，可能是因为与 zipf 工作负载发生锁定争用。接下来，我们在图 9b 中评估具有 100 字节有效载荷的 0:100 盲更新工作负载。在这种情况下，性能是线性的，直到两个 CPU 上的 48 个线程，但在这一点之后趋于稳定，因为更大的 100 字节有效负载导致系统达到最大的 cross-socket 可用带宽。

7.2.4

与 Redis 的比较。Redis 是内存中的键值存储（或缓存），它与 Faster 有三个不同之处：

1. Redis 不是并发的，用户需要承担对数据和操作进行哈希分区的开销。
2. 虽然 Redis 提供了可选的可恢复性，但它希望所有数据都适合内存，并使用 fork 为数据库创建快照。
3. Redis 是为通过网络访问而设计的，因此设计时考虑到了这个瓶颈。因此，它的性能预计会低于嵌入式系统，如 Faster。

我们通过在单个线程上运行 redis-benchmark 来研究最后一点，并使用以下参数：-D8-C10-P $ { PIPERAL }-t set，get -r 1000000 -n 20000000。这些值是 8 字节，我们使用 10 个客户端线程，连接到本地主机（以避免网络开销），并运行 20M 的 Get 和 Set 操作，这些操作访问 0 到 1M 范围内的随机记录。我们将 pipeline 深度从 1 改变到 200。在这个简化的场景中，我们看到了大约 1.1M sets/s 和1.4M gets/s。对于 250M 的 key 空间（类似于我们的 YCSB 工作负载），我们看到大约 700K sets/s 和 900K gets/s。这些速度明显低于单线程的 Faster。

7.3 大于内存的实验

我们使用 100 字节的有效负载运行 YCSB，核心数据集大小为 27GB，并将一个槽上的线程数量设置为 14（7个核心）。Faster 的内存预算包括用于哈希索引的 2GB 空间，在本实验中，哈希索引的大小为 #key/8 个哈希桶。

首先，我们使用 50:50 的 zipf 工作负载，并在 图10 中绘制吞吐量与 RocksDB 的关系。正如预期的那样，由于固态硬盘随机读取的增加，Faster 在内存有限的情况下会变慢，可是一旦整个数据集适应内存，它就会很快达到内存性能水平。我们认为，随着内存的减少，性能的急剧下降可以通过在 Faster 的环境中优化 I/O 路径来改善；我们计划在今后的工作中解决这个问题。

接下来，在 0:100 的盲更新工作负载下，如预期的那样，如果内存足够，Faster 的性能会稍低。随着内存预算的下降，更多的数据溢出到存储中，但吞吐量的下降幅度没有读取的大，因为对固态硬盘的大容量顺序日志写入（没有随机读取）效率更高。我们看到，对于这两种工作负载，RocksDB 每秒最多可实现 500,000 次操作。

最后，我们使用 0:100 的工作负载，80% 的 read-only 区域和 uniform 分布。由于就地更新较少，这会增加系统的写吞吐量。我们发现 Faster 的速度可以达到 1.74 GB/s 的顺序日志写入带宽，接近固态硬盘的理论最大 2GB/s。

7.4 Faster 的详细评估

7.4.1 比较的是 append-only。我们使用 Faster 的 append-only 日志分配器运行 YCSB-A 50:50 （50% 读取和 50% 盲更新）。我们的循环内存缓冲区有 215 页，每页 4MB。图11 显示了均匀分布和 zipf 分布的性能。我们看到，虽然性能随着混合日志线性扩展，但在日志中创建新条目和尾部争用会导致 append-only 日志明显变慢。在混合日志的情况下，zipf 的性能比 uniform 好得多，因为键不对称会导致更好的 TLB 和缓存行为。另一方面，仅使用 append，由于更新冲突，更多失败的 compare-and-swap 操作抵消了 zipf 分发的性能优势。

7.4.2 IPU（in-place-update，IPU）域的大小。我们使用具有 100% RMW 工作负载的 YCSB-A，并改变 IPU 域因子，该因子被定义为数据集在日志的就地更新区域中的分数。图12a 显示了当我们增加 IPU 区域因子时实现的总吞吐量（在 56 个线程上）和日志增长的速率（在副轴上）。随着键的 uniform 分布，我们看到吞吐量随着 IPU 区域的增加而增加，因为我们有更多的机会执行就地更新。此外，日志增长更慢，这是非常可取的。请注意，我们显示了 8 字节键和值的日志增长率，每条记录总共 24 个字节，但是对于更大的有效负载，增长率会成倍增加。最后，zipfian 键分布的图表明，由于键的集中，吞吐量在更低的 IPU 区域因子比均匀的更高，这是混合日志的整理效果。由于同样的原因，日志增长率也下降得更快（随着 IPU 区域大小的增加）。

7.4.3 模糊区域。我们在所有 56 个线程上执行 100% RMW 工作负载（uniform），并将数据库的 IPU 区域大小从 0.25 更改为 1.0，这将导致日志增长更快，进而导致ReadOnlyAddress 移动地更快，最终导致更多更新在模糊区域中挂起。图12b 展示出了随着 IPU 区域大小的增加模糊更新的百分比。线程每 256 次操作刷新一次它们的 epoch。即使使用 uniform 的键分配和 56 个线程，该百分比也不会超过 3%，并且仅在不到 70% 的内存用于就地更新的人工场景中，该百分比才高于 0.5%。

接下来，我们通过将 IPU 区域因子固定为 0.8 来保持日志增长率不变，并改变线程数量。正如预期的那样，图13 显示模糊操作的百分比随着线程数量的增加而增加，但是即使所有 56 个线程都保持在 1% 以下。

7.5 缓存行为的模拟

我们进行了一个模拟研究来比较众所周知的缓存协议（6.4 节）和 HybridLog 的缓存行为。我们维护一个恒定大小的键缓冲区作为缓存，并且每当被访问的键不在缓冲区中时，使用每个缓存协议来驱逐一个键。对于 HLOG，我们有一个只读标记，它与 tail 之间有一个恒定的延迟；当一个键在只读区域时，我们将它复制到 tail，就像在 Faster 中一样。我们改变缓存大小，观察 3 种访问模式的缓存命中率：uniform、zipfian（θ = 0.99）和 Hot-set 分布。热集分布包括一个移动热集（总大小的 1/5）以 90% 的概率均匀访问，其余的冷集以 10% 的概率均匀访问。我们的结果显示在图14、图15和图16中。HLOG 和其他协议一样执行 uniform 分布。在 zipfian 和 Hot-set 分布的情况下，由于内存中键的复制，HLOG 的缓存未命中率高于 LRU-1、LRU-2 和时钟协议。HLOG 协议导致热键的两个副本，一个在只读区域，一个在可变区域，从而减少了有效的缓存大小。然而，HLOG 比简单的 FIFO 更好，因为它为键提供了第二次留在缓存中的机会。总的来说，与其他协议（除了 FIFO）不同，HLOG 的缓存行为可以胜任其他优化算法，而不需要维护大量统计数据，同时仍然提供无锁的快速访问路径。

8. 相关工作

Faster 为并发系统设计、数据结构、键值存储、文件系统和数据库提供了丰富的研究空间。下面我们来总结一下当前的技术水平。

内存设计和结构（In-Memory Designs and Structures）。过去已经提出了许多并行设计模式，例如 hazard pointers 和 the repeat offender problem。基于 epoch 的设计已经被许多系统用来缓解特定的瓶颈。然而，我们用触发 action 来增强 epoch protection，并将其设计为一个通用框架来实现惰性同步。在论文的几个实例中，Faster 将其用作构建模块（参见第 2.4 节）。就地更新在纯内存数据结构中很普遍。提出 read-copy-update 是为了让 read 不受并发 write 的影响。现代存储中的快速顺序写入导致了日志结构的流行，这种结构将 RCU 应用于仅附加日志上的数据。日志结构最初应用于文件系统，但后来用于键值存储。Faster 的 HybridLog 结合了这些技术，实现了两者的最佳效果：热数据的高性能和存储的快速顺序日志记录。

哈希键值存储（Hash Key-Value Stores）。诸如 Redis、Memcached 之类的内存缓存和存储，以及改进的版本，诸如 MemC3 和 MICA 被用来加速 Web 部署和减轻数据库负载，但是它们本身并不处理大于内存的数据（Redis 支持用于恢复的预写日志）。像 RAMCloud 和 FaRM 这样的分布式系统专注于扩展键值存储，例如，通过使用分区、远程内存或 RDMA，而不是利用冷数据的存储。所有这些系统报告的单节点性能低于我们的目标。相比之下，Faster 是一个单节点并发高级语言组件，它使用基于日志的混合（hybrid log-based）数据组织来利用存储。流状态存储，如 Spark State Store 和 Storm Trident State Store，使用简单的分区内存哈希表，定期同步检查。它们不支持并发访问，并且展示的吞吐量很低。谷歌 Cloud Dataflow 在内存中存储最近的状态，并定期将数据下放到 BigTable，由于去耦，导致潜在的高开销。

范围键值存储（Range Key-Value Stores）。像 Masstree 这样的系统是纯内存的范围索引，因此针对不同的应用。像 Cassandra、RocksDB 和 BwTree 这样的键值存储系统，可以处理比内存更大的状态。然而，它们不太适合我们的目标应用程序，它们的键排序页面格式是为读取和范围查询而优化的，但代价是更大的复杂性。此外，对于更新密集型工作负载来说，它们使用 read-copy-update 的成本很高。RocksDB 在其内存组件（0 级）中支持就地更新，但无法利用它来获得可接受的内存工作负载性能。RocksDB 的吞吐量通常低于 1M ops/sec，其 "merge" 操作对于 RMW 工作负载来说成本很高。相比之下，Faster 的目标是以极高的性能实现点操作和更新密集型工作负载。

数据库（Databases）。内存数据库针对更一般的数据处理需求进行了优化，而不是针对 Faster的目标进行优化。它们无法处理溢出到二级存储的数据。ERMIA 是一个快速的内存优化数据库，在其设计中使用了无锁结构、epoch 保护和日志结构等技术。然而，它是仅追加的，并且针对的是完全可序列化的事务，而不是原子点操作的事务，导致我们的目标应用程序的预期性能较低。传统数据库使用缓冲池处理大数据。Faster 避免了缓冲池和页面锁存，但使用日志中的粗粒度区域来实现高性能，同时适应不断变化的工作集。H-Store 划分了工作负载并避免了并发性，但这种策略会产生 shuffle 开销、负载不平衡和偏斜问题。Deuteronomy 和 SQL Server Hekaton 分别使用哈希来索引恢复日志和内存数据库，但基于 RCU。