全文翻译
摘要
本文对流行的Memcached系统提出了一组从架构和工作负载出发的算法和工程改进，从而极大地提高了其内存效率和吞吐量。这些技术—乐观布谷鸟散列、一种基于时钟的近似lRU的回收算法，以及乐观锁定的全面实现——使最终系统在小键值对上减少30%的内存使用，并在网络上每秒提供多达3倍的查询。我们在一个称为MemC3-Memcached的系统中实现了这些修改，该系统具有时钟和并发布谷鸟散列，但我们相信它们也更普遍地适用于当今许多读密集型、高并发的网络存储和缓存系统。
1.介绍
近年来，对数据的低延迟访问已成为许多互联网服务的关键。这一要求导致许多系统设计人员从主存中提供所有或大部分特定的数据集——使用主存[19,26,21,25]或作为缓存，以转移热的或特别敏感的延迟[10]项。
评估这些系统的两个重要指标是性能(吞吐量，以每秒处理的查询来衡量)和内存效率(以存储项目所需的开销来衡量)。内存消耗很重要，因为它直接影响系统可以存储的项目数量，以及这样做的硬件成本。
本文证明了对算法和数据结构设计的仔细关注可以显著提高内存中数据存储的吞吐量和内存效率。我们展示了传统的方法经常不能利用目标系统的架构和预期的工作负载。作为一个案例研究，我们将重点关注Memcached[19]，一个流行的内存缓存层，并展示我们的技术工具箱是如何将Memcached的性能提高3倍，并将内存使用量减少30%的。
标准Memcached的核心是使用典型的哈希表设计，使用基于链表的链接来处理冲突。它的缓存替换算法是严格的LRU，也是基于链表的。这种设计依赖于锁来确保多个线程之间的一致性，导致多核cpu[11]的可伸缩性较差。
本文提出了MemC3(带有时钟和并发布谷鸟哈希的Memcached)，这是一种对Memcached内部结构的重新设计。这种重新设计是根据并利用了一些观察结果。首先，体系结构特性可以隐藏内存访问延迟并提供性能改进。特别地，我们的新哈希表设计利用了CPU缓存的局部性来最小化完成任何给定操作所需的内存取次数;它利用指令级和内存级的并行性来加速无法避免的读取操作。
其次，MemC3的设计也利用了工作负载特性。许多Memcached工作负载主要是读，很少写。这个观察结果意味着我们可以将Memcached的排他的全局锁定替换为针对常见情况的乐观锁定方案。此外，许多重要的Memcached工作负载以非常小的对象为目标，因此每个对象的开销对内存效率有显著影响。例如，Memcached严格的LRU缓存替换需要大量的元数据——通常比对象本身占用的空间更多;在MemC3中，我们使用一个紧凑的基于时钟的近似。
本文的具体贡献包括:
- 一种叫做乐观布谷鸟哈希的新哈希方案。传统的布谷鸟哈希[23]算法虽然具有较高的空间效率，但对并行操作并不友好。乐观布谷鸟哈希(1)实现了较高的内存效率(例如95%的表占用率);(2)允许多个reader和一个writer同时访问哈希表;(3)保持哈希表操作对缓存友好(第3节)。
- 紧凑的基于时钟的回收算法，每个缓存条目只需要1比特的额外空间，并支持并发缓存操作(第4节)
- 乐观锁定，在确保一致性的同时消除线程间同步。乐观布谷鸟哈希表操作(查找/插入)和LRU缓存回收操作都使用了这种锁定方案，以实现对共享数据结构的高性能访问(第4节)。
最后，我们在Memcached-1.4.13的基础上实现并评估MemC3，这是一个网络的、内存中的键值缓存。表1比较了MemC3和基本的Memcached。MemC3使用更少的内存和计算提供了更高的吞吐量，我们将在本文的其余部分演示这一点。
2.背景
2.1 Memcached Overview
Memcached实现了一个简单而轻量级的键-值接口，所有的键-值元组都存储在DRAM中，并从DRAM中提供服务。客户端使用以下命令通过网络与Memcached服务器通信:
• SET/ADD/REPLACE(key, value): add a (key, value) object to the cache;
• GET(key): retrieve the value associated with a key; • DELETE(key): delete a key.
在内部，Memcached使用哈希表对键值项建立索引。这些条目也在一个按最近访问时间排序的链表中。当缓存已满时，最近最少使用(LRU)的条目将被删除，并被新插入的条目所替换。
Hash Table:为了快速查找键，每个键-值项的位置都存储在一个散列表中。哈希冲突是通过链接解决的:如果多个键映射到同一个哈希表桶，它们就形成一个链表。链接可以有效地插入或删除单个键。然而，查找可能需要扫描整个链。
Memory Allocation:naive的内存分配(例如，malloc/free)可能导致严重的内存碎片。为了解决这个问题，Memcached使用基于板的内存分配。内存被划分为1 MB的页面，每个页面又被进一步划分为固定长度的块。Key-value对象存储在适当大小的块中。块的大小，即每个页面的块的数量，取决于特定的slab类。例如，默认情况下slab类1的块大小是72字节，该类的每个页面有14563个块;而slab类43的块大小是1 MB，因此只有1个块横跨整个页面。为了插入一个新键，Memcached查找chunk大小最适合这个key-value对象的slab类。如果有一个空闲块可用，则将其分配给该项;如果搜索失败，Memcached将执行缓存回收。
Cache policy ：在Memcached中，每个slab类在一个LRU队列中维护自己的对象(参见图1)。每次访问一个对象都会导致该对象移动到队列的头部。因此，当Memcached需要从缓存中取出对象时，它可以在尾部找到最近最少使用的对象。队列被实现为一个双链表，因此每个对象都有两个指针。
Threading:Memcached最初是单线程的。它使用libevent实现异步网络I/O回调[24]。后来的版本支持多线程，但是使用全局锁来保护核心数据结构。因此，索引查找/更新和缓存回收/更新等操作都是序列化的。之前的工作表明，这种锁定阻止了当前Memcached在多核cpu[11]上的扩展。
Performance Enhancement：以前的解决方案[4,20,13]将内存中的数据分片到不同的核。分片消除了线程间同步以允许更高的并发性，但在不平衡的工作负载下，它也可能在不同核之间呈现不平衡的负载，或者浪费(昂贵的)内存容量。除了简单的分片，我们还将探索如何将性能扩展到共享和访问相同内存空间的多个线程;然后可以应用分片来进一步扩展系统。
2.2 Real-world Workloads: Small and Read-only Requests Dominate
我们的工作是由Facebook[3]最近发布的几个键-值工作负载特征决定的。首先，对小对象的查询占主导地位。大多数键小于32字节，大多数值不超过几百字节。特别是，有一种常见的请求类型几乎独占地使用16或21字节键和2字节值。
存储这样小的键值对象的结果是高内存开销。Memcached总是为每个键值对象分配一个56字节的报头(在64位服务器上)，而不管其大小。头文件包括两个用于LRU链表的指针和一个用于形成哈希表的链接指针。对于小的键值对象，这个空间开销不能平摊。因此，我们为索引和缓存寻找更有效的内存数据结构。
其次，查询的读取量很大。一般来说，对于Facebook中的Memcached工作负载，报告的GET/SET比率为30:1。那些可以根据需要增加缓存大小的重要应用程序会显示出更高的GET比例(例如，99.8%是GET，或者GET/SET=500:1)。注意，这个比率还取决于GET命中率，因为每次GET miss之后通常都会有一个SET来更新应用程序的缓存。
虽然大多数查询都是get，但该操作没有得到优化，并且在查询路径上广泛使用了锁。例如，每个GET操作都必须获得(1)一个锁来排他访问这个特定的密钥，(2)一个全局锁来排他访问哈希表;(3)读取相应的key-value对象后，必须再次获取全局锁来更新LRU链表。我们的目标是删除GET路径上的所有互斥对象，以提高Memcached的并发性。
3 Optimistic Concurrent Cuckoo Hashing
在这一节中，我们提出了一种紧凑的、并发的和缓存感知的散列方案，称为乐观并发布谷鸟散列。与Memcached原来基于链的哈希表相比，我们的设计采用了布谷鸟哈希[23]——一种实用的、先进的哈希方案，具有较高的内存效率和O(1)的预期插入时间和检索时间，从而提高了内存效率。然而，基本的布谷鸟哈希不支持并发读/写访问;对于每次插入或查找，它还需要多个内存引用。为了克服这些限制，我们提出了一组新的技术来改善基本的布谷鸟散列在并发性，内存效率和缓存友好:
布谷鸟散列的乐观版本，支持多读/单写并发访问，同时保留其空间优势;一种使用每个键的简短摘要来改进哈希表操作的缓存位置的技术;优化布谷鸟哈希插入，提高了吞吐量
正如我们在第5节中所展示的，结合这些技术创建了一个在实践中很有吸引力的哈希方案:它的哈希表达到了90%以上的占用率(相比之下，线性探测的占用率为50%，或者需要链接所需的额外指针)[?]。每次查找平均只需要两次并行的cacheline读取，然后(最多)一次内存引用。相比之下，天真的布谷鸟散列需要两个并行的cacheline读取，如果每个桶有N个键，则需要(最多)2N个并行的内存引用;而链接需要(最多)N个依赖内存引用来扫描一个包含N个键的桶。哈希表支持多个读取器和一个写入器，大大提高了读密集型工作负载的速度，同时保持了写密集型工作负载的同等性能。
哈希表为所有键值对象提供查找、插入和删除操作。在查找时，哈希表返回一个指向相关键值对象的指针，如果找不到该键，则返回“不存在”。当插入成功时，哈希表返回true，如果哈希表已满则返回false。Delete只是从哈希表中删除键的条目。我们关注查找，插入。删除非常类似于查找。
在详细介绍我们的技术之前，我们首先简要描述一下如何执行布谷鸟散列。布谷鸟哈希的基本思想是使用两个哈希函数而不是一个，从而为每个键提供两个可能的驻留位置。布谷鸟散列可以动态地重新定位现有的键，并在插入过程中改进表，为新键腾出空间。
在详细介绍我们的技术之前，我们首先简要描述一下如何执行布谷鸟散列。布谷鸟哈希的基本思想是使用两个哈希函数而不是一个，从而为每个键提供两个可能的驻留位置。布谷鸟散列可以动态地重新定位现有的键，并在插入过程中改进表，为新键腾出空间。
如图2所示，我们的散列表由一个桶数组组成，每个桶有4个槽每个插槽包含一个指向key-value对象的指针和一个称为标签的键的简短摘要。为了支持可变长度的键，完整键和值不存储在哈希表中，而是与表外的相关元数据一起存储，并由指针引用。空指针表示此槽位未被使用。
每个键映射到两个随机桶，因此查找检查每个槽中的所有8个候选键。为了插入一个新的键x到表中，如果两个桶中的任何一个有一个空槽，那么它就被插入到那个桶中;如果两个桶都没有空间，Insert会从一个候选桶中随机选择key y，并将y重定位到它自己的备用位置。替换y也可能需要踢出另一个已经存在的键z，所以这个过程可能会重复，直到找到一个空闲的槽，或者直到达到最大的置换次数(例如，在我们的实现中，500次)。如果没有发现空闲的槽位，则认为哈希表已满，无法插入，并安排一个扩展过程。虽然它可以执行一个置换序列，但是布谷鸟哈希的预期插入时间是O(1)[23]。
为了支持可变长度的键并保持索引紧凑，实际的键不存储在哈希表中，必须通过跟随指针检索。我们提出了一种缓存感知技术，通过使用标记——键的短散列(在我们的实现中是一个字节)，以最小的内存引用来执行布谷鸟散列。这种技术的灵感来自我们在之前的工作[17]中提出的“部分键布谷鸟哈希”，但消除了前面方法在最大表大小方面的限制。
Cache-friendly Lookup
最初的Memcached查找不是缓存友好的。它需要多个依赖指针解引用来遍历一个链表:基本的布谷鸟散列也不是缓存友好的:在每个查找上检查两个桶最多需要8个(并行的)指针解引用。此外，在Insert上替换每个键也需要一个指针解引用来计算交换的备用位置，每个Insert可能执行几个置换操作。 我们的哈希表在一般情况下不需要指针指针引用。我们计算一个1字节的标签作为每个插入键的摘要，并将标签作为其指针存储在同一个桶中。查找首先比较标记，然后只有标记匹配时才检索完整键。这个过程如下所示(T代表标签)
由于两个不同的键具有相同的标记，可能会出现错误的检索，因此将进一步验证所获取的完整键，以确保它确实是正确的。用哈希法处理一个字节的标签，标签冲突的几率只有1/28 = 0.39%。在检查了所有8个候选槽之后，负查找平均产生8 × 0.39% = 0.03个指针deref- reference。因为每个存储桶都适合于一个CPU cacheline(通常是64字节)，所以每次查找平均只进行2次平行的cacheline大小的读取，以检查两个存储桶，如果查找失败，则执行0.03个指针解引用，如果查找成功，则执行1.03个指针解引用。
Cache-friendly Insert :
3.2 Concurrent Cuckoo Hashing
For clarity of presentation, we first define a cuckoo path as the sequence of displaced keys in an Insert operation. In Figure 3 “a ⇒ b ⇒ c” is one cuckoo path to make one bucket available to insert key x. There are two major obstacles to making the sequential cuckoo hashing algorithm concurrent:
- 死锁风险(写入者/写入者):当沿着布谷鸟路径移动键时，插入可能修改一组桶，直到一个键落在一个可用的桶中。在交换键之前，我们不知道有多少个键和哪些键桶将被修改，因为每个被替换的键都依赖于之前被删除的键。因此，使插入原子化并避免死锁的标准技术(例如提前获取所有必要的锁)显然不适用。
当一个键被踢出它原来的存储区时，在它被插入到它的替代位置之前，这个键从两个存储区时都是不可访问的，并且暂时不可用。如果Insert不是原子的，读取器可能会在键不可用的时间内完成查找并返回错误。例如，在图3中，在第4个bucket用a替换了b之后，但是在b重定位到第1个bucket之前，b没有出现在表中的任何一个bucket上。一个读者在这个时候查找b可能会返回负的结果。
我们所知道的[12]是之前提出的唯一一种并行布谷鸟散列方案，它将插入插入到一个原子位移序列中，而不是锁定整个布谷鸟路径。它在每个存储桶上增加额外的空间，作为一个溢出缓冲区，以便临时从其他存储桶交换主机密钥，从而避免踢出现有的密钥。因此，它的空间开销(通常每个桶多两个槽作为缓冲区)比基本的布谷鸟散列要高得多。
相反，我们的方案保持了较高的内存效率，并允许多个阅读器并发访问哈希表。为了避免写入器/写入器死锁，它一次只允许一个写入器，这是一个折衷，因为我们的目标工作负载读很多。为了消除误选，我们的设计改变了基本布谷鸟哈希插入的顺序:
将发现有效的cuckoo路径与该路径的执行分开。我们首先搜索一个布谷鸟路径，但在这个搜索阶段不移动键。沿着布谷鸟路径向后移动键。已知一个有效的布谷鸟路径后，我们首先将布谷鸟路径上的最后一个键移动到空闲槽，然后将倒数第二个键移动到前一个键留下的空槽，以此类推。因此，每次交换只影响一个键，它总是可以成功地移动到新的位置，而不会被踢出。
直觉上，最初的插入总是将一个选中的键移动到另一个桶，并踢出另一个现有的键，除非在那个桶中找到一个空槽。因此，在插入完成之前总是有一个受害者键“floating”，导致错误遗漏。相反，我们的方案首先发现一条到空槽的布谷鸟路径，然后沿着这条路径将这个空槽传播到要插入的键。为了说明图3中的方案，我们首先在不编辑任何桶的情况下，为键x找到一条有效的布谷鸟路径“a宗b宗c”。路径已知后，c被交换到第3个桶的空槽中，然后将b重新定位到第1个桶中c的原始槽中，以此类推。最后，a的原槽可用，x可以直接插入到该槽中。
3.2.1 Optimization: Optimistic Locks for Lookup
锁分段 许多锁定方案都可以使用我们提出的并发布谷鸟散列，只要它们确保在插入过程中，布谷鸟路径上的所有位移相对于查找而言都是原子的。最直接的方案是在每次位移和查找之前锁定两个相关桶。虽然很简单，但这种模式需要对每个查找锁定两次，并且要谨慎地顺序，以避免死锁。
对于常见情况的优化，我们的方法利用了一个写入器来同步插入和查找，且开销很低。它不是锁定存储桶，而是为每个键分配一个版本计数器，在插入时替换这个键时更新它的版本，并在查找期间查找版本变化，以检测任何并发置换。
维护每个键版本的最简单方法是将其存储在每个键-值对象中。然而，这种方法为每个键添加一个计数器，可能有数亿个键。更重要的是,这种方法会导致竞态条件:检查或更新的版本给定的关键,我们必须首先查找在哈希表中查找键-值对象(外部存储的哈希表),这最初的查找不受任何保护锁,因此不是线程安全的。
相反，我们创建了一个计数器数组(图2)。为了保持这个数组较小，每个计数器通过哈希在多个键之间共享(例如，第i个计数器由哈希值为i的所有键共享)。我们的实现总共保留了8192个计数器(或32 KB)。这允许计数器适合缓存，但允许大量并发访问。它还将“错误重试”(由于修改了不相关的键而重新读取键)的几率保持在大约0.01%。所有的计数器都被初始化为0，并且只有原子内存操作才能读取/更新，以确保所有线程之间的一致性。
在替换一个键之前，Insert进程首先将相关的计数器加1，指示其他查找正在对这个键进行更新;当键被移动到它的新位置后，计数器再次增加1以表示完成。因此，键版本在每次位移后增加2。 在查找进程读取给定键的两个桶之前，它首先快照存储在其计数器中的版本:如果这个版本是奇数，必须有一个并发插入操作同一个键(或者另一个共享同一个计数器的键)，它应该等待并重试;否则，它将进入两个桶。在读取完两个桶之后，它再次对计数器进行快照，并将其新版本与旧版本进行比较。如果两个版本不同，写入器必须修改了这个键，应该重试查找。附录中的正确性证明涵盖了一些特殊情况。
我们修改后的插入过程首先寻找一个有效的布谷鸟路径，然后沿着路径交换键。由于搜索和执行阶段的分离，我们应用以下优化来加快路径发现，并增加找到空槽的机会。 我们的插入过程不是沿着一条布谷鸟路径寻找空槽，而是并行地跟踪多条路径。在每一步，多个受害者键被“踢出”，每个键扩展自己的布谷鸟路径。当一条路径到达一个可用的存储桶时，搜索阶段就结束了。 如果有多个搜索路径，insert可能会更早地找到一个空槽，从而提高吞吐量。此外，它提高了哈希表在超过执行的最大位移数之前存储新键的机会，从而增加了加载因子。更多布谷鸟路径的影响将在第5节进行评估。
4 Concurrent Cache Management
缓存管理和回收是MemC3的第二个重要组成部分。当服务小的键值对象时，这也成为Memcached空间开销的主要来源，每个键需要18个字节(即两个指针和一个2字节的引用计数器)，以确保键可以按照严格的LRU顺序安全地被驱逐。字符串LRU缓存管理也是一个同步瓶颈，因为所有对缓存的更新都必须在Memcached中序列化。
缓存管理和回收是MemC3的第二个重要组成部分。当服务小的键值对象时，这也成为Memcached空间开销的主要来源，每个键需要18个字节(即两个指针和一个2字节的引用计数器)，以确保键可以按照严格的LRU顺序安全地被驱逐。字符串LRU缓存管理也是一个同步瓶颈，因为所有对缓存的更新都必须在Memcached中序列化。
本节介绍我们如何通过基于时钟替换算法[6]实现一个近似的LRU缓存来提高缓存管理空间的效率(每个密钥1比特)和并发(没有同步来更新LRU)。时钟是一种众所周知的算法;我们的贡献在于将时钟替换与我们的cuckoo算法中的乐观的条带锁集成在一起，从而减少锁定和空间开销。
由于我们的目标工作负载主要是小对象，完美交换近似LRU所节省的空间允许缓存存储更多的条目，这反过来提高了命中率。正如我们将在第5节中展示的那样，我们的缓存管理实现了Memcached中默认缓存的3到10倍的查询吞吐量，同时也提高了命中率。
CLOCK Replacement:缓存必须实现替换策略的两个功能: 在缓存中查询一个键后，更新以跟踪最近的数据;和Evict来选择要清除的键，当将键插入到完整的缓存中时。
Memcached将每个键值条目保存在自己的slab类中一个基于双链表的LRU队列中。在每次缓存查询之后，Update将访问的条目移动到自己队列的头部;为了在缓存已满时释放空间，Evict用新的键-值对替换队列尾部的条目。这确保了每个队列中严格的LRU驱逐，但不幸的是，对于双向链表，它还需要每个键有两个指针，更重要的是，对一个链表的所有更新都是序列化的。每个读访问都需要进行一次更新，因此队列不允许并发，即使对于只读工作负载也是如此。
Memcached将每个键值条目保存在自己的slab类中一个基于双链表的LRU队列中。在每次缓存查询之后，Update将访问的条目移动到自己队列的头部;为了在缓存已满时释放空间，Evict用新的键-值对替换队列尾部的条目。这确保了每个队列中严格的LRU驱逐，但不幸的是，对于双向链表，它还需要每个键有两个指针，更重要的是，对一个链表的所有更新都是序列化的。每个读访问都需要进行一次更新，因此队列不允许并发，即使对于只读工作负载也是如此。
CLOCK通过改进并发性和空间效率近似于LRU。对于每个slab类，我们维护一个循环缓冲区和一个虚拟手;缓冲区中的每个位代表一个不同的key-value对象的近延:1表示“最近使用”，0表示“最近使用”。每次更新只是将每次键访问的recency位设置为1;每个驱逐检查当前指针指向的钻头。如果当前位为0，则Evict选择相应的key- value对象;否则，我们将该位重置为0，并在循环缓冲区中推进指针，直到我们看到0位。
驱逐进程必须与读取线程协调以确保驱逐是安全的。否则，一个键-值条目可能会在删除后被一个新的(键，值)对覆盖，但是仍然访问被删除的键的条目的线程可能会读取脏数据。为此，原始的Memcached为每个条目添加了一个2字节的引用计数器，以避免这种罕见的情况。读取每个条目的计数器，驱逐进程就知道有多少其他线程正在并发地访问这个条目，从而避免驱逐那些繁忙的条目。 我们的缓存将缓存回收与布谷鸟散列的乐观锁定方案集成在一起。当Evict se-通过时钟选择一个受害者键x时，它首先增加键x的版本计数器来通知其他正在读取x的线程进行重试;然后，它从哈希表中删除x，使以后的读者无法访问x，包括那些重试;最后，它再次增加键x的版本计数器，以完成对x的更改。注意，Evict和哈希表插入都是序列化的(使用锁)，所以当更新计数器时，它们不会相互影响。 使用如上所述的Evict，我们的缓存通过版本检查确保了一致的获取。在访问哈希表之前，每个人都首先获取键的版本快照;如果哈希表返回一个有效的指针，则跟随该指针并读取相关的值。然后，GET将最新的键版本与快照进行比较。如果版本不同，则GET可能观察到中间状态不一致，必须重试。GET和SET的伪代码见算法1。
