摘要:

Memcached是一个众所周知的、简单的内存缓存解决方案。本文描述了Facebook利用memcached作为一个构建块来构建和扩展一个支持世界上最大的社交网络的分布式键值存储。我们的系统每秒处理数十亿个请求，并拥有上万亿个项目，为全世界超过10亿用户提供丰富的体验。

1.介绍
受欢迎和吸引人的社交网站带来了重大的基础设施挑战。数以亿计的人每天都在使用这些网络，并将计算、网络和I/O需求强加给传统的web架构，而传统的web架构很难满足这些需求。社交网络的基础设施需要(1)允许近实时通信，(2)实时聚合来自多个来源的内容，(3)能够访问和更新非常流行的共享内容，(4)可扩展到每秒处理数百万用户请求。

我们描述了如何改进memcached[14]的开源版本，并将其用作构建块，为世界上最大的社交网络构建一个分布式键值存储。我们将讨论从单个服务器集群扩展到多个地理分布的集群的过程。据我们所知，这个系统是世界上最大的memcached设施，每秒处理超过10亿条请求，存储上万亿项数据。

本文是认识到分布式键值存储的灵活性和实用性的一系列工作的最新成果。本文主要讨论memcached——内存散列表的一种开源实现，因为它以较低的成本提供了对共享存储池的低延迟访问。这些特性使我们能够构建大量数据的特性，否则这些特性将是不切实际的。例如，每个页面请求发出数百个数据库查询的功能可能永远不会离开原型阶段，因为它的速度太慢，成本也太高。在我们的应用中， 然而，web页面通常从memcached服务器获取数千个键值对。

我们的目标之一是提出在我们不同部署规模下出现的重要主题。虽然性能、效率、容错性和一致性等质量在所有范围内都很重要，但是我们的经验表明，在特定的范围内，某些质量比其他质量需要更多的努力来实现。例如，如果复制很少，那么在小范围内维护数据一致性会比在大范围内维护数据一致性更容易，因为大范围内通常需要复制。 此外，随着服务器数量的增加和网络成为瓶颈，找到最佳通信调度的重要性也在增加。

这篇论文主要有四个贡献:(1)我们描述了Facebook基于memcached的架构的演变。(2)对memcached进行了增强，提高了性能和内存效率。(3)突出提高系统规模化运行能力的机制。(4)我们描述了施加在我们系统上的生产工作负载。

2.综述
下列特性对我们的设计有很大的影响。首先，用户消费的内容要比他们创造的内容多一个数量级。这种行为会导致以获取数据为主的工作负载，这表明缓存可能具有显著的优势。其次，我们的读操作从各种来源获取数据，比如MySQL数据库、HDFS设施和后端服务。这种异构性需要一种灵活的缓存策略，能够存储来自不同数据源的数据。

Memcached提供了一组简单的操作(set、get和delete)，这使它成为大型分布式系统中的基本组件。我们起源于一个单机内存散列表的开源版本。在本文中，我们将讨论如何使用这个基本的构建块，使其更高效，并使用它来构建一个每秒可以处理数十亿请求的分布式键值存储。

图1:Memcache是一个满足需求的备用缓存。左半部分说明了缓存中的web服务器的读路径，右半部分说明了写路径。

我们使用“memcached”来指代源代码或正在运行的二进制文件，使用“memcache”来描述分布式系统。

查询缓存:我们依赖memcache来减轻数据库上的读负载。特别是，我们使用memcache作为一个满足需求的备用缓存，如图1所示。当web服务器需要数据时，它首先通过提供一个字符串键从memcache请求值。如果没有缓存由该键寻址的项，则web服务器从数据库或其他后端服务检索数据，并使用键-值对填充缓存。 对于写请求，web服务器向数据库发出SQL语句，然后向memcache发送删除请求，从而使任何陈旧的数据无效。我们选择删除缓存的数据而不是更新它，因为删除是幂等的。Memcache不是数据的权威来源，因此可以删除缓存的数据。

虽然有几种方法可以解决MySQL数据库上过多的读取流量，但是我们选择使用memcache。考虑到有限的工程资源和时间，这是最好的选择。此外，将缓存层与持久层分离，允许我们在工作负载更改时独立地调整每一层。

通用缓存:我们还利用memcache作为更通用的键值存储。例如，工程师使用memcache来存储来自复杂的机器学习算法的预先计算结果，然后可以用于各种其他应用程序。新服务利用现有的marcher基础设施，而不需要进行调优、优化、供应和维护大型服务器机队，几乎不需要付出什么努力。

实际上，memcached不提供服务器之间的协调;它是在一台服务器上运行的内存中的散列表。在本文的其余部分，我们将描述如何基于memcached构建一个能够在Facebook工作负载下运行的分布式键值存储。我们的系统提供了一套配置、聚合和路由服务来将memcached实例组织到一个分布式系统中。

我们组织了我们的论文，以强调出现在三种不同部署规模下的主题。当我们有一个服务器集群时，主要关心的是读取大量工作负载和广泛的扇出。由于有必要扩展到多个前端集群，我们解决了这些集群之间的数据复制问题。最后，我们描述了在我们向全世界传播集群时提供一致用户体验的机制。 操作复杂性和容错能力在任何级别上都很重要。我们提供了支持我们的设计决策的重要数据，并将读者转到Atikoglu等人的作品中，以对我们的工作量进行更详细的分析。在高层次上，图2说明了最终的体系结构，其中我们将位于同一位置的集群组织到一个区域中，并指定一个主区域，该主区域提供数据流以保持非主区域的最新状态。

在开发我们的系统时，我们优先考虑两个主要的设计目标。(1)任何更改都必须影响用户或操作问题。很少考虑范围有限的优化。(2)我们将读取瞬时失效数据的概率作为要调优的参数，类似于响应性。我们愿意公开稍微陈旧的数据，以保证后端存储服务不受过度负载的影响。

3.集群中的:延迟和负载
我们现在考虑扩展到一个集群中的数千个服务器的挑战。在这个范围内，我们的大部分工作都集中在减少获取缓存数据的延迟或由于缓存丢失而造成的负载。

3.1 减少延迟
无论数据请求的结果是缓存命中还是未命中，memcache响应的延迟都是用户请求响应时间的一个关键因素。单个用户的web请求常常会导致数百个单独的memcache get请求。例如，加载一个流行的页面平均会从memcache中获取521个不同的条目。

我们在一个集群中提供了数百个memcached服务器，以减少数据库和其他服务的负载。所有项目通过一致性散列分布[22]在memcached服务器上。因此，web服务器必须与许多memcached服务器进行常规通信以满足用户请求。因此，所有web服务器在短时间内与每个memcached服务器通信。 这种全对全的通信模式可能导致广播拥塞[30]，或使单个服务器成为许多web服务器的瓶颈。数据复制通常会缓解单服务器瓶颈，但在通常情况下会导致显著的内存效率低下。（因为冗余导致空间利用率下降）

我们主要通过关注在每个web服务器上运行的memcache客户机来减少延迟。该客户机提供一系列功能，包括序列化、压缩、请求路由、错误处理和请求批处理。客户端维护所有可用服务器的映射，并通过辅助配置系统进行更新。

并行请求和批处理:我们构造web应用程序代码，以最小化响应页面请求所需的网络往返次数。我们构造了一个有向无环图(DAG)来表示数据之间的依赖关系。web服务器使用此DAG来最大化可并发获取的项的数量。平均每个请求包含24个key。

客户机-服务器通信:Memcached服务器之间不通信。在适当的时候，我们将系统的复杂性嵌入到无状态客户机中，而不是memcached服务器中。这极大地简化了memcached，并允许我们专注于在更有限的用例中使它具有高性能。保持客户端无状态可以在软件中快速迭代，并简化我们的部署过程。客户端逻辑作为两个组件提供:一个可以嵌入到应用程序中的库，或者作为一个名为mcrouter的独立代理提供。 这个代理提供了一个memcached服务器接口，并将请求/应答路由到/来自其他服务器。

客户端使用UDP和TCP与memcached服务器通信。我们依赖UDP的get请求来减少延迟和开销。因为UDP是无连接的，所以web服务器中的每个线程都可以绕过mcrouter直接与memcached服务器通信，而无需建立和维护连接，从而减少了开销。在客户端进行UDP的丢失和错序检测并把它们视为错误，没有提供任何机制来尝试从它们中恢复。在我们的基础设施中，我们发现这个决定是可行的。在峰值负载下，memcache客户端观察到0.25%的get请求被丢弃。大约80%的下降是由于延迟或丢失的包，而其余的是由于订单交付。客户端将get错误视为缓存失败，但是web服务器在查询数据后将跳过向memcached插入条目的过程，以避免在可能超载的网络或服务器上增加额外的负载。
为了可靠性，客户端通过与web服务器运行在同一台机器上的mcrouter实例在TCP上执行设置和删除操作。对于需要确认状态更改(更新和删除)的操作，TCP减少了向UDP实现添加重试机制的需要。
Web服务器依靠高度的并行性和过度订阅来实现高吞吐量。开放TCP连接的高内存需求使得在没有通过mcrouter进行某种形式的连接合并的情况下，在每个web线程和memcached服务器之间建立开放连接的开销非常大。通过减少高吞吐量TCP连接所需的网络、CPU和内存资源，合并这些连接可以提高服务器的效率。 图3显示了生产环境中web服务器获取密钥的平均、中位数和第95个百分点的延迟UDP和通过mcrouter通过TCP。在所有情况下，这些平均值的标准偏差都小于1%。正如数据显示，依赖UDP可以让一个服务请求的延迟减少20%。

In cast congestion: Memcache客户端实现了流控制机制来限制Incast拥塞。当客户端请求大量键时，如果这些响应同时到达，则机架（memcache）和集群交换机（mcrouter）等组件将不堪重负。因此，客户端使用滑动窗口机制[11]来控制未完成请求的数量。 当客户端收到响应时，可以发送下一个请求。与TCP的拥塞控制类似，此滑动窗口的大小在请求成功时缓慢增长，在请求未得到响应时缩小。该窗口应用于所有memcache请求;而TCP窗口只适用于单个流。

图4显示了窗口大小对处于可运行状态但等待在web服务器中调度的用户请求的时间量的影响。
数据是从一个前端集群的多个机架上收集的。用户请求在每个web服务器上显示一个泊松到达过程。根据利特尔定律[26]， L =λW,排队在服务器的请求数量 (L)与请求处理所需的平均时间(W)成正比，假设输入请求速率是常数(我们的实验就是这样)。 web请求等待调度的时间是系统中web请求数量的直接指示。使用较小的窗口大小，应用程序将不得不连续地分派更多的memcache请求组，从而增加web请求的持续时间。当窗口大小变得太大时，同时发出的memcache请求的数量会导致拥塞。其结果将是memcache错误和应用程序退回到数据的持久存储，这将导致web请求的处理变慢。 在这两个极端之间存在一种平衡，可以避免不必要的延迟，并最小化阻塞。

3.2 减少负载

我们使用memcache来减少沿着更昂贵的路径(如数据库查询)获取数据的频率。当所需的数据没有被缓存时，Web服务器会退回到这些路径。下面的小节将介绍三种降低负载的技术。

3.2.1 租约 （？？）
我们引入了一种新的机制，我们称之为租赁，以解决两个问题:陈旧的集合(stale sets)和雷鸣般的兽群(thundering herds)。当web服务器在memcache中设置的值没有反映应该缓存的最新值时，就会发生过期集。当对memcache的并发更新被重新排序时，可能会发生这种情况。当一个特定的键经历了繁重的读写活动时，就会产生一群雷鸣般的声音。由于write活动会反复使最近设置的值无效，因此许多读操作都默认使用开销更大的路径。我们的租赁机制解决了这两个问题。
直观地说，memcached实例向客户端提供一个租约，以便在客户端遇到缓存丢失时将数据设置回缓存。租约是一个64位令牌，绑定到客户端最初请求的特定key。客户端在设置缓存中的值时提供租约令牌。使用租约令牌，memcached可以验证和确定是否应该存储数据，从而仲裁并发写操作。 如果memcached由于接收到该项目的删除请求而使租约令牌无效，则验证可能会失败。租约以一种类似于load-link/store-conditional操作[20]的方式来防止过时的集合。
对租约稍作修改也能减少thundering herds。每个memcached服务器都控制它返回令牌的速度。默认情况下，我们将这些服务器配置为每个密钥每10秒只返回一个令牌。在发出令牌后的10秒内请求key的值，结果会产生一个特殊通知，告诉客户端等待一小段时间。 通常，具有租约的客户机将在几毫秒内成功设置数据。因此，当等待的客户端重试请求时，数据通常出现在缓存中。
为了说明这一点，我们收集了一组key的所有缓存丢失数据，这些key特别容易受到雷鸣声的影响。如果没有租约，所有缓存丢失将导致数据库查询率达到峰值17 k / s。使用租约以后，峰值数据库查询率为1.3 k / s。由于我们根据峰值负载提供数据库，因此我们的租赁机制可以显著提高效率。

Stale values:
对于租约，我们可以在某些用例中最小化应用程序的等待时间。我们可以通过确定返回稍微过时的数据是可接受的情况来进一步减少时间。当一个键被删除时，它的值被转移到一个数据结构中，这个数据结构保存着最近删除的项，在被刷新之前，它会在这个结构中存在一段时间。 get请求可以返回标记为过期的租约令牌或数据。可以继续使用过时数据的应用程序不需要等待从数据库获取最新的值。我们的经验表明，由于缓存的值往往是数据库的单调递增快照，所以大多数应用程序都可以使用陈旧的值而不做任何更改。

3.2.2 Memcache Pools
使用memcache作为通用缓存层需要工作负载共享基础设施，尽管存在不同的访问模式、内存占用和服务质量需求。不同应用程序的工作负载可能产生负干扰，从而导致命中率下降。
为了适应这些差异，我们将集群的memcached服务器划分为不同的池。我们将一个池(名为通配符)指定为缺省值，并为其在通配符中存在问题的键提供单独的池。例如，我们可以为频繁访问的键提供一个小池，但是对于这些键，缓存丢失并不昂贵。我们还可以为不经常访问的键提供一个大的池，对于这些键，缓存丢失是非常昂贵的。

Q: 流失率怎么理解?高流失率代表什么？

图5显示了两个不同的项目集的工作集，一个是低流失率的，另一个是高流失率的。工作集的近似方法是对每一百万项中的一项的所有操作进行抽样。对于每个项目，我们收集最小、平均和最大的项目大小。这些大小相加并乘以100万，以近似于工作集。 每日和每周工作集之间的差异表明了流失量。具有不同流失率特征的物品以一种不幸的方式相互作用:在高流失率的键不再被访问之前，仍然有价值的低流失率的键被删除。将这些键放在不同的池中可以防止这种负面干扰，并允许我们根据其缓存丢失成本调整高流失池的大小。第7节提供了进一步的分析。

3.2.3 Replication Within Pools
在某些池中，我们使用复制来改进memcached服务器的延迟和效率。当(1)应用程序通常同时获取多个key，(2)整个数据集适合一个或两个memcached服务器，(3)请求速率远远高于单个服务器的管理能力时，我们选择在池中复制一类键。
在这个实例中，我们倾向于复制而不是进一步划分键空间。考虑一个memcached服务器，它拥有100个条目，并且能够每秒响应500k个请求。每个请求询问100个键。用于检索的memcached开销的差异每个请求100个键而不是1个键是很小的。为了将系统扩展到每秒处理1M个请求，假设我们添加了第二台服务器， 并在两台服务器之间平均分配键空间。 客户端现在需要分割每个请求将100个键转换为两个并行请求，得到50个键。因此，这两个服务器仍然必须每秒处理1M个请求。但是，如果我们将所有100个键复制到多个服务器，客户端对100个键的请求可以发送到任何副本。这将每个服务器的负载降低到每秒500k个请求。每个客户端根据自己的IP地址选择副本。这种方法需要将失效交付给所有副本以保持一致性。

3.3 Handling Failures
无法从memcache获取数据会导致对后端服务的过度负载，这可能会导致进一步的级联失败。我们必须在两种情况下处理故障:(1)由于网络或服务器故障而无法访问少量主机;(2)影响集群中大部分服务器的大范围停机。 如果整个集群必须脱机，我们将用户web请求转移到其他集群，从而有效地从该集群中的memcache中删除所有负载。
对于小故障，我们依赖于自动修复系统[3]。这些动作不是即时的，可能需要几分钟。这个持续时间足够长，足以导致前面提到的级联故障，因此我们引入了一种机制来进一步隔离后端服务和故障。 我们使用一组名为Gutter的小机器来接管一些故障服务器的职责。在一个集群中，Gutter约占memcached服务器的1%。
当memcached客户端没有收到对其get请求的响应时，客户端会认为服务器已经失败，并再次将请求发送到一个特殊Gutter池。如果第二个请求失败，客户机将在查询数据库之后将适当的键-值对插入到Gutter机中。 排水沟中的条目将很快过期，以避免排水沟失效。水沟以略微陈旧的数据为代价限制后端服务的负载。
请注意，这种设计不同于客户机在剩余的memcached服务器之间重新散列键的方法。这种方法存在由于键访问频率不均匀而导致级联失败的风险。 例如，一个键可以占服务器请求的20%。负责此热键的服务器也可能超载。通过将负载分流到空闲服务器，我们限制了这种风险。
通常，每个失败的请求都会导致对后备存储的攻击，可能会使其超载。通过使用排水沟存储这些结果，这些故障中的很大一部分被转换为排水沟池中的命中，从而减少了后备存储的负载。在实践中，该系统将客户端可见的故障率降低了99%，并将10%-25%的失败转换为命中。 如果memcached服务器完全失败，则在水槽池中的命中率通常在4分钟内超过35%，通常接近50%。因此，当一些memcached服务器由于故障或较小的网络事件而不可用时，水槽保护备份存储免受流量激增的影响。

4.In a Region: Replication
随着需求的增长，人们很容易购买更多的web和memcached服务器来扩展集群。然而,简单地扩展系统并不能消除所有的问题。随着越来越多的web服务器被添加进来以应对不断增加的用户流量，被高频请求的项目只会变得更受欢迎。 随着memcached服务器数量的增加，Incast拥塞也会加剧。因此，我们将web和memcached服务器分割为多个前端集群。这些集群以及包含数据库的存储集群定义一个区域。此区域架构还允许较小的故障域和可处理的网络配置。我们用数据的复制来换取更独立的故障域、可处理的网络配置和减少网络拥塞。
本节分析共享同一存储集群的多个前端集群的影响。具体来说，我们讨论了允许跨这些集群进行数据复制的后果，以及不允许这种复制的潜在内存效率。

4.1 区域内失效
虽然某个区域的存储集群保存数据的权威副本，但用户需要可以将该数据复制到前端集群中。存储集群负责使缓存的数据失效，以使前端集群与权威版本保持一致。作为一种优化，修改数据的web服务器还会向其自己的集群发送失效通知，以便为单个用户请求提供写后读语义，并减少陈旧数据在其本地缓存中出现的时间量。

修改权威状态的SQL语句被修改为包含需要在事务提交[7]时失效的memcache键。我们在每个数据库上部署失效守护进程(称为mcsqueal)。每个守护进程检查其数据库提交的SQL语句，提取任何删除操作，并将这些删除操作广播到该区域每个前端集群中的memcache部署。 图6说明了这种方法。我们认识到，大多数失效不会删除数据;实际上，只有4%的删除操作会导致缓存数据的实际失效。
降低包速率:虽然mcsqueal可以直接与memcached服务器联系，但是从后端集群发送到前端集群的包速率会高得让人无法接受。这个包速率问题是由许多数据库和许多memcached服务器跨集群边界通信造成的。 无效守护进程批量删除更少的包，并将它们发送到运行在每个前端集群中的mcrouter实例的一组专用服务器。然后，这些mcrouters从每个批处理中解压缩单独的删除操作，并将这些失效操作路由到位于前端集群内的正确的memcached服务器。批处理使每个数据包的删除数中位数提高了18倍。(通过压缩和解压缩)
通过web服务器的失效:对于web服务器来说，向所有前端集群传播失效更简单。不幸的是，这种方法有两个问题。首先，它会带来更多的包开销，因为与mcsqueal管道相比，web服务器在批处理失效方面的效率更低。 其次，当出现系统失效问题(如由于配置错误导致删除操作错误)时，它提供的资源很少。在过去，这通常需要重新启动整个memcache基础设施，这是我们希望避免的缓慢而混乱的过程。相反，在SQL语句中嵌入失效(数据库提交并存储在可靠的日志中)，允许mcsqueal简单地重播可能已经丢失或路由错误的失效。

4.2 区域池
每个集群根据发送给它的用户请求的组合独立地缓存数据。如果用户的请求被随机路由到所有可用的前端集群，那么缓存的数据在所有前端集群中大致相同。这使我们能够使集群离线进行维护，而不会降低命中率。过度复制数据可能导致内存效率低下，特别是对于大的、很少访问的项。通过让多个前端集群共享同一组memcached服务器，我们可以减少副本的数量。我们称之为区域池。
跨集群边界会导致更多的延迟。此外，与单个集群相比，我们的网络在集群边界上的平均可用带宽要少40%。复制可以用更多的memcached服务器换取更少的集群间带宽、更低的延迟和更好的容错性。 对于某些数据，放弃复制数据的优点，在每个区域只复制一个数据，这样更节省成本。在一个区域内扩展memcache的主要挑战之一是决定是否需要跨所有前端集群复制一个键，还是每个区域只复制一个键。当区域池中的服务器发生故障时，也会使用Gutter水槽。

表1总结了我们的应用程序中具有大值的两种条目。我们已经移动了一种(B)区域池，而另一个池(a)不受影响。请注意，客户端访问B类的条目要比a类的条目少一个数量级。B类的低访问速率使它成为区域池的首选，因为它不会对集群间的带宽产生负面影响。 B类还将占据每个集群通配符池的25%，因此区域化提供了显著的存储效率。但是，第A类的项目要大两倍，而且取用次数也多得多，因此没有资格列入区域审议项目。将数据迁移到区域池的决定目前是基于一组基于访问速率、数据集大小和访问特定项的惟一用户数量的人工启发方法。

4.3 冷集群热身
当我们将一个新的集群上线时，现有的集群会失败，或者执行预定的维护，缓存的命中率将非常低，从而降低了后端服务的隔离能力。一个称为冷集群预热的系统通过允许客户端进入“冷集群”(即拥有空缓存的前端集群)用于从“热集群”(即具有正常命中率的缓存的集群)而不是持久存储中检索数据。 这利用了前面提到的跨前端集群的数据复制。有了这个系统，冷集群可以在几小时内而不是几天内恢复到满负荷状态。
必须小心避免由于竞争条件造成的不一致。例如，如果冷集群中的一个客户端进行数据库更新，并且另一个客户端的后续请求在暖集群收到失效通知之前从暖集群中检索过时的值，那么该项在冷集群中就会无限期地不一致。 Memcached删除支持在指定的保留时间拒绝添加操作的非零保留时间。默认情况下，对冷集群的所有删除都被延迟两秒。当在冷集群中检测到遗漏时，客户端从热集群中重新请求键，并将其添加到冷集群中。 add失败表明数据库中有更新的数据，因此客户端将从数据库中重新获取该值。虽然理论上仍然存在删除被延迟超过两秒的可能性，但对于绝大多数情况都不是这样。冷集群预热的操作好处远远超过了罕见的缓存一致性问题的成本。一旦冷集群的命中率稳定下来，并且收益减少，我们就会关闭它。

5. 区域间： 一致性
扩大数据中心的地理位置有几个好处。首先，让web服务器更接近最终用户可以显著降低延迟。
其次，地理多样性可以减轻自然灾害或大规模停电等事件的影响。第三，新的地点可以提供更便宜的电力和其他经济激励。 我们通过部署到多个区域来获得这些优势。每个区域由一个存储集群和几个前端集群组成。我们指定一个区域存放主数据库，其他区域存放只读副本;我们依赖于MySQL的复制机制来保持副本数据库与它们的主数据库是最新的。 在此设计中，web服务器在访问本地memcached服务器或本地数据库副本时将体验到低延迟。在跨多个区域扩展时，维护memcache中的数据与持久存储之间的一致性成为主要的技术挑战。这些挑战源于一个问题:副本数据库可能落后于主数据库。
我们的系统只是一致性和性能折衷范围中的一个点。与系统的其他部分一样，一致性模型经过多年的发展已经适应了站点的规模。它能在不牺牲我们的高性能要求的情况下，混合实际建造的东西。 系统管理的大量数据意味着，任何增加网络或存储需求的微小更改都会产生与之相关的重大成本。大多数提供更严格语义的思想很少离开设计阶段，因为它们变得非常昂贵。 与许多根据现有用例定制的系统不同，memcache和Facebook是一起开发的。这使得应用程序和系统工程师能够一起工作，从而找到一个模型，该模型对于应用程序工程师来说足够容易理解，而且性能良好，并且足够简单，可以大规模可靠地工作。 我们提供了最佳效果的最终一致性，但是强调了性能和可用性。因此，这一系统在实践中对我们非常有效，我们认为我们找到了一个可以接受的折衷办法。
从主区域写: 我们之前的决定要求存储集群通过守护进程使数据无效，这在多区域体系结构中具有重要的影响。特别是，它避免了在从主区域复制数据之前出现无效声明的竞态条件。 考虑主区域中的web服务器，该服务器已经完成了对数据库的修改，并试图使过时的数据失效。在主区域内发送失效状态是安全的。但是，让web服务器使副本区域中的数据失效可能为时过早，因为更改可能还没有传播到副本数据库。 对来自复制区域的数据的后续查询将与复制流竞争，从而增加将陈旧数据设置到memcache的概率。在过去，我们在扩展到多个区域之后实现了mcsqueal。
从非主区域写入:现在考虑一个用户，当复制延迟非常大时，他从非主区域更新数据。如果用户最近的更改丢失，那么他的下一个请求可能会导致混乱。只有在复制流捕获之后，才应该允许从副本数据库中重新填充缓存。如果不这样做，后续请求可能会导致获取和缓存副本的陈旧数据。
我们使用远程标记机制来最小化读取过期数据的概率。标记的存在表明本地副本数据库中的数据可能已经过时，应该将查询重定向到主区域。 当web服务器希望更新影响某个键k的数据时，该服务器(1)在该区域设置远程标记rk，(2)对将k和rk嵌入到SQL语句中使之无效的主服务器执行写操作，(3)删除本地集群中的k。 对于后续请求k，web服务器将无法找到缓存的数据、检查rk是否存在，并根据rk的存在将其查询定向到主区域或本地区域。在这种情况下，当出现缓存丢失时，我们显式地交换额外的延迟，以降低读取陈旧数据的概率。
我们通过使用区域池来实现远程标记。请注意，此机制可能会在对同一键进行并发修改时显示过时的信息，因为一个操作可能会删除一个远程标记，该标记应该为另一个正在执行的操作保留。值得强调的是，我们为远程标记使用memcache与缓存结果有微妙的区别。 作为缓存，删除或清除键始终是一个安全的行动;它可能会增加数据库的负载，但不会影响一致性。相反，远程标记的存在有助于区分非主数据库是否保存过时的数据。在实践中，我们发现远程标记的清除和并发修改的情况都很少见。

操作上的考虑:区域间的通信是昂贵的，因为数据必须跨越很大的地理距离(例如横跨大陆联合公司)
州)。通过为删除流共享与数据库复制相同的通信通道，我们可以在低带宽连接上提高网络效率。
上述管理删除的系统在第4.1节还与副本数据库一起部署，将删除操作广播到副本区域中的memcached服务器。当下游组件变得无响应时，数据库和mcrouters缓冲删除。任何组件的失败或延迟都会导致读取陈旧数据的概率增加。 当这些下游组件再次可用时，将重新播放缓冲的删除操作。替代方法包括在检测到问题时，使集群离线或在前端集群中过度无效地处理数据。考虑到我们的工作量，这些方法带来的坏处比好处更多。

6 Single Server Improvements
all-to-all通信模式意味着单个服务器可能成为集群的瓶颈。本节描述memcached中的性能优化和内存效率提高，它们允许更好地扩展集群。提高单服务器缓存性能是一个活跃的研究领域[9,10,28,25]。
我们从使用固定大小哈希表的单线程memcached开始。第一个主要的优化是:(1)允许哈希表的自动扩展，以避免查找时间漂移到O(n)，(2)使服务器多线程使用全局锁来保护多个数据结构， 3)给每个线程自己的线程UDP端口，以减少发送响应时的争用和后面传播中断处理的开销。前两个优化由开源社区贡献。本节的其余部分将探索开放源代码版本中尚未提供的进一步优化。
我们的实验主机使用Intel Xeon CPU (X5650)运行在2.67GHz(12核和12个超级线程)，一个Intel 82574L千兆以太网控制器和12GB内存。生产服务器有额外的内存。进一步的细节已经在之前发布过[4]。 性能测试设置由15个客户机组成，这些客户机生成一个memcache流量，连接到一个带有24个线程的memcached服务器。客户端和服务器位于同一机架上，通过千兆以太网连接。这些测试度量在持续负载超过两分钟的memcached的响应延迟。

Get性能:我们首先研究将原来的多线程单锁实现替换为细粒度锁的效果。我们在发出每个键有10个的memcached请求之前，用32字节的值预先填充缓存，从而测量命中率。 图7显示了不同版本的memcached使用亚毫秒级的平均响应时间可以维持的最大请求速率。第一组栏是在细粒度锁定之前的memcached，第二组是当前的memcached，最后一组是开源版本1.4.10，它独立地实现了锁策略的一个更粗版本。
使用细粒度锁定将命中率最大值提高了三倍，从每秒60万项到每秒180万项。脱靶次数也从每秒270万次增加到每秒450万次。因为必须构造和传输返回值，所以命中的代价更大，而未命中则需要整个multiget的单个静态响应(END)，表明所有键都已丢失。
我们还研究了使用UDP而不是TCP的性能影响。图8显示了我们可以在单个get和10键multiget的平均延迟不到1毫秒的情况下维持的峰值请求率。我们发现，我们的UDP实现比我们的TCP实现在单个get和10个键的multiget上分别高出13%和8%。

因为multigets在每个请求中包含的数据比单个get更多，所以它们使用更少的包来完成相同的工作。图8显示了10个键的multiget比single gets的大约四倍的改进。

6.2 自适应Slab分配器
Memcached使用一个slab分配器来管理内存。分配器将内存组织成slab类，每个类包含预先分配的、大小一致的内存块。Memcached将项目存储在尽可能小的slab类中，这个类可以容纳项目的元数据、键和值。Slab类从64字节开始，并以1.07倍的倍数增加到1 MB，对齐到4字节边界（ 这个比例因子确保我们有64和128字节的项目，更适合于硬件高速缓存线路 ）。 每个slab类维护一个可用块的空闲列表，并在空闲列表为空时请求1MB的更多内存。一旦memcached服务器不能再分配空闲内存，则通过清除最近最少使用的项来完成新项的存储(LRU)在slab类中的项。当工作负载发生变化时，分配给每个slab类的原始内存可能不再足够，从而导致较低的命中率。
我们实现了一个自适应分配器，它定期重新平衡slab分配以匹配当前的工作负载。如果slab类当前正在清除条目，并且下一个要清除的条目的使用时间比其他slab类中最近最少使用的条目的平均使用时间至少多20%，那么它就认为slab类需要更多的内存。如果找到这样一个类，那么包含最近最少使用的项的slab将被释放并转移到需要的类。 请注意，开源社区已经独立地实现了一个类似的分配器，它平衡了slab类之间的回收率，而我们的算法侧重于平衡类之间最老的项的年龄。平衡年龄提供了一个更好的近似值为一个单一的全球最近对整个服务器使用(LRU)回收策略，而不是调整回收率，这可能会受到访问模式的严重影响。

6.3 暂态项缓存
虽然memcached支持过期时间，但条目可能在过期后仍然存在于内存中。Memcached通过检查过期时间来惰性地清除这些条目，比如在为该条目提供get请求时，或者在它们到达LRU的末尾时。虽然对于一般情况来说是有效的，但是这种方案允许短生命周期的键在看到单个活动爆发时浪费内存，直到它们到达LRU的末端。
因此，我们引入了一种混合方案，它依赖于对大多数键的延迟回收，并在短寿命键过期时主动回收短寿命键。我们将短期存在的项放入链表的循环缓冲区(以秒为单位进行索引，直到过期)—称为瞬态项缓存-根据项目的到期时间。 每一秒，缓冲区头部桶中的所有项都被清除，头部前进1。当我们向一组频繁使用的键添加一个较短的过期时间，而这些密钥的项的使用寿命很短;在不影响命中率的情况下，这个键族使用的memcache池的比例从6%降低到0.3%。

6.4 软件升级
频繁的软件更改可能需要用于升级、bug修复、临时诊断或性能测试。memcached服务器可以在几小时内达到90%的峰值点击率。因此，我们升级一组memcached服务器需要12个小时导致要小心管理数据库负载。 我们对memcached进行了修改，将其缓存的值和主要数据结构存储在System V共享内存区域中，以便在软件升级过程中数据能够保持活动状态，从而最小化中断。

7 Memcache 工作负载
现在，我们使用来自生产环境中运行的服务器的数据来描述memcache工作负载。
7.1 Web服务器上的度量
我们记录一小部分用户请求的所有memcache操作，并讨论工作负载的扇出、响应大小和延迟特性。
扇出:图9显示了web服务器在响应页面请求时可能需要联系的不同memcached服务器的分布。如图所示，56%的页面请求只与不到20个memcached服务器相连。按容量计算，用户请求倾向于请求少量的缓存数据。 然而，这种分布有一个长尾。该图还描述了一个更受欢迎的页面的分布，该页面更好地展示了all-to-all通信模式。这种类型的大多数请求将访问100多个不同的服务器;访问几百个memcached服务器并不罕见。

响应大小:图10显示了来自memcache请求的响应大小。中位数之间的差值(135字节)和平均值(954字节)意味着缓存项的大小有很大的变化。此外，在大约200字节和600字节处出现了三个不同的峰值。较大的项倾向于存储数据列表，而较小的项倾向于存储单个内容块。

延迟: 我们度量从memcache请求数据的往返延迟，其中包括路由请求和接收回复的成本、网络传输时间以及反序列化和解压缩的成本。请求延迟7天中位数333微秒而第75和第95百分位数(我和p95)分别为475μs和1.135 ms。 我们的平均端到端延时闲置的web服务器是178μs然而p75和p95分别是219μs和374μs。p95延迟之间的巨大差异源于处理大型响应和等待可运行线程被调度(如第3.1节所述)。

7.2 池统计
现在我们讨论四个memcache池的关键指标。这些池是通配符(默认池)、app(用于特定应用程序的池)、用于频繁访问的数据的复制池和用于很少访问的信息的区域池。在每个池中，我们每4分钟收集一次平均统计信息，并在表2中报告一个月收集周期内的最高平均数据。 这些数据近似于这些池所见的峰值负载。该表显示了不同池的get、set和delete速率的巨大差异。表3显示了每个池的响应大小分布。同样，不同的特性促使我们希望将这些工作负载彼此隔离。


如第3.2.3节所述，我们在池中复制数据，并利用批处理来处理高请求率。可以观察到，尽管具有最小的项大小，但复制的池具有最高的get速率(大约是次高的那个的2.7倍)和最高的字节与包的比率。这些数据与我们的设计是一致的，我们利用复制和批处理来实现更好的性能。 在app池中，更高的数据搅动自然会导致更高的miss rate。这个池往往有内容，被访问了几个小时，然后逐渐消失的流行喜欢更新的内容。从请求速率和值大小分布可以看出，区域池中的数据往往比较大，访问频率也比较低。

7.3 失效延迟
我们认识到，失效的及时性是决定暴露陈旧数据的概率的一个关键因素。为了监视这个健康状况，我们从一百万次删除中抽取一次并记录删除发出的时间。然后，我们会定期在所有前端集群中查询memcache的内容，以获取抽样的键值，并记录一个错误，如果一个条目在删除之后仍然被缓存，那么这个错误就会使它失效。

在图11中，我们使用这种监视机制报告30天内的失效延迟。我们将此数据分为两个不同的组件:(1)delete来自主区域的web服务器，并将其发送到主区域的memcached服务器;(2)delete来自一个副本区域，并将其发送到另一个副本区域。
数据显示，当删除的源和目标与主节点位于同一位置时，我们的成功率要高得多，在1秒内达到4个9，在1小时后达到5个9。然而，当删除开始并发送到主区域之外的位置时，我们的可靠性在1秒内下降到3个9，在10分钟内下降到4个9。根据我们的经验，我们发现，如果在几秒钟后就丢失了一个无效声明，那么最常见的原因是第一次尝试失败，随后的检索将解决该问题。

8 相关工作
其他几个大型网站已经认识到键值存储的效用。DeCandia等人的[12]提供了一个高可用的键值存储，它被Amazon.com上的各种应用程序服务使用。虽然他们的系统针对写大量工作负载进行了优化，但我们的目标是由读控制的工作负载。 同样的, LinkedIn使用的是Voldemort[5]，一个受Dynamo启发的系统。键值缓存解决方案的其他主要部署包括Redis6和memcached(在Twitter[33]和Zynga上)。Lakshman等人开发了Cassandra，一种基于模式的分布式键值存储。我们倾向于部署和扩展memcached，因为它的设计更简单。
我们在扩展memcache方面的工作建立在分布式数据结构中的大量工作之上。 Gribble等人提出了一个早期版本的键值存储系统，该系统可用于Internet规模的服务。Ousterhout等人的[29]也提出了一个大规模的内存键值存储系统的情况。与这两个解决方案不同，memcache不保证持久性。我们依赖于其他系统来处理持久性数据存储[19]。
Ports等人提供了一个库来管理事务数据库查询的缓存结果。我们的需求需要更灵活的缓存策略。我们对租约[18]和过期读[23]的使用，利用了之前在高性能系统中对缓存一致性和读操作的研究。 Ghandeharizadeh和Yap[15]的工作还提出了一种基于时间戳而不是显式版本号解决陈旧集问题的算法。
虽然软件路由器更容易定制和编程，但它们的性能往往不如硬件路由器。Dobrescu等人通过利用通用服务器上的多核、多内存控制器、多队列网络接口和批处理来解决这些问题。 将这些技术应用于mcrouter的实现仍然是未来的工作。Twitter还独立开发了一个类似于mcrouter[32]的memcache代理。
在Coda[35]中，Satyanarayanan等人演示了如何将因断开操作而分叉的数据集恢复到同步状态。Glendenning等人的[17]利用Paxos[24]和quorums[16]来构建Scatter，这是一个具有可线性化语义的分布式哈希表[21]，具有抗流失性。Lloyd等人研究了广域存储系统COPS中的因果一致性。
TAO[37]是另一个严重依赖缓存来处理大量低延迟查询的Facebook系统。TAO与memcache有两个基本的区别。(1) TAO实现了一个图数据模型，其中节点由固定长度的持久标识符标识
(64位整数)。 (2) TAO编码其图形模型到持久性存储的特定映射，并负责持久性。两个系统都使用许多组件，比如我们的客户机库和mcrouter。

9 结论
在本文中，我们展示了如何扩展一个基于memcached的架构来满足Facebook不断增长的需求。
所讨论的许多权衡并不是基本的，而是植根于在不断的产品开发中，在演进活动系统的同时平衡工程资源的现实。在构建、维护和改进系统的过程中，我们得到了以下教训。 (1)将缓存和持久存储系统分开，使我们能够独立地扩展它们。(2)提高监视、调试和操作效率的特性与性能同样重要。(3)管理有状态组件在操作上比管理无状态组件更复杂。因此，在无状态客户端中保持逻辑有助于迭代特性并最小化中断。 (4)系统必须支持新特性的逐步推出和回滚，即使这会导致特性集的暂时异构。（5）简单是至关重要的。