facebook缓存论文

# facebook缓存论文

https://research.facebook.com/publications/scaling-memcache-at-facebook/

Memcached是一个众所周知的简单的内存缓存方案。这篇论文介绍了Facebook如何利用memcached来构建和扩展一个分布式的key-value存储来支撑世界上最大的社交网络。我们的系统每秒处理数十亿的请求，并且内部支撑了数十万项目的运转，向全球十亿用户提供良好的服务体验。

# 1 Introduction

一个流行并有趣的社交网站对计算机领域的基础设施提出了巨大的挑战。每天都有数亿人在使用网络，但是现在传统的web架构难以满足这样的计算能力、网络、IO。

一个社交网络的基础设施需要满足下面这几个特征：

近乎实时的通讯
动态聚合多个数据源
能够访问并更新非常流行的分享内容
可以弹性处理用户每秒发起的数以百万计的请求

我们描述了如何改进开源的memcached[14]并且使用memcched构建了世界上最大的社交网络的key-value存储。我们将会讨论如何从一个单个服务器集群扩展到多地域集群的过程。据我们所知，我们构建了世界上最大的memcched，处理了每秒数十亿请求，并且存储了万亿级别的数据对象。

这篇论文是一系列中最新的一篇充分意识到key-value存储对的灵活性和实用性[1, 2, 5, 6, 12, 14, 34, 36].

这篇论文使用memcched作为内存hash table的开源实现，选取的原因是它具有低成本的优势提供对共享存储池的访问。这些特新能够让我们去构建数据密集型的功能。例如，一个特性需要每个页面的包含数百个对数据库的请求，这种情况业务背景下使用数据库可能永远在原型阶段，因为数据库太慢了，成本太高了。在我们的应用中，web页面将会从memcched中获取上千个键值对。

我们的目标之一是介绍不同规模下的部署展现出的问题。尽管性能、效率、容错和一致性在所有的业务规模下都很重要，但是我们的经验告诉我们在特定过的一些规模下，有些特点需要比其他特点付出更加多的努力。例如，在小规模的系统中通过同步复制去维护数据一致性要比在大型系统中容易的多。于此同时，随着服务器数量的增加，不同服务之间寻找最佳的网络道路变的更加重要，网络也随之变为影响的瓶颈。

本文主要的贡献如下：

描述了Facebook的memcched的架构演进过程
对memcched进行了改进，提高了性能和内存效率
重点介绍了提高我们操作大规模系统的能力
描述了运行在我们整个系统中的产品负载情况

# 2 Overview

以下这些特点影响了我们对系统的设计。

首先，用户消费的内容比产出的内容多了一个数量级。这就导致获取数据是系统首要考虑的事情，缓存将会显著的提高查询的性能。

其次，我们将会从各个数据源中读取数据，例如MySQL、HDFS和后端服务。不同服务之间的差异，需要一种灵活的缓存策略，能够存储来自不同数据源的数据。

Mmcached提供了一组简单的操作（set、get、delete）这就使得memcched成为大规模分布式系统中最具吸引力的组件。我们开始使用的开源版本提供了一个简单的内存Hash 表。在这篇论文中，我们将会讨论如何使用memcched构建更有效的，能抗住每秒数百万的请求的分布式键值对存储。

文章中，我们使用memcached来标识源代码或者正在运行的二进制文件，而memcache来描述分布式缓存系统。

# 2.1 查询缓存

我们依赖memcache来减轻数据库的负载。通常情况下，我们把memcache作为一个旁路缓存区使用，如图1所示。

当web服务器读取数据的时候，首先向memcache进行请求。如果请求的数据没有被缓存，则web服务会想数据库或者其他的后端服务进行检索，然后让缓存填充回memcache中。

对于写请求而言，web服务器向数据库发送SQL请求，然后向memcache发送删除请求，使缓存中的过期key失效。

我们选择删除缓存数据而不是更新，是因为删除是一个幂等操作。Memcache不是作为权威的数据来源，因此允许去删除缓存的数据。

虽然有几种方法可以解决MySql数据库上大量的读流量，但我们依然选择使用memcache。考虑到有限的工程资源和时间，这是一个最好的选择。此外，将缓存层与持久层分离，那我们在工作负载发生变化时独立调整每一层的结构（比如MySQL换成PGSQL）。

# 2.2 通用缓存

我们还利用memcache作为更通用的键值存储。例如，工程师使用memcache预先去存储复杂的机器学习算法计算好的结果，可以用于其他各种应用。对于新服务来说，利用现有的memcache并不需要调优、优化、供应和维护大型服务器，非常易于使用。

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

我们的论文结构介绍了在三种不同部署规模下出现的情况。当我们有一个服务器集群时，包含大量读取操作负载和广泛的扇出是主要关注的问题。当需要扩展到多个集群的时候，我们解决了这些数据在集群之间的复制问题。最后，我们将描述在将集群分布到世界各地时提供一致用户体验的机制，无论是什么样的服务器规模，操作复杂性和容错性都非常的重要。我们展示了支持我们设计决策的数据，并建议读者参考atikoglu等人[8]的工作，以获得更详细的工作负载分析。

图2 演示了这个最终的体系结构，我们将共存的集群组织到一个区域中，并指定一个提供数据流的主区域，以同步的方式，保持从区域的最新。

在发展我们系统时优先考虑两个设计目标：

任何更改都必须影响用户面临的问题或操作问题。很少考虑范围有限的优化。
将读取瞬时过期数据的概率作为一个主要调优的参数，类似于响应性。我们愿意暴露一些陈旧的数据，以使后端存储服务免受过度负载的影响。

# 3 In a Cluster: Latency and Load

我们现在面临着在一个集群中，扩展到上千台服务器。在这种规模下，我们的工作主要集中在减少获取缓存数据的延迟或由于缓存Miss而造成的负载。

# 3.1 Reducing Latency

无论是命中还是没有命中缓存，memcache的响应是影响用户响应时间的至关重要的因素。当个用户的请求，往往回去读取数百个人在memcache的信息。例如在加载热门页面的时候，平均会从memcache中获取512个条目。

我们在一个集群中提供了数百个memcache节点，以减轻数据库和其他服务的负载。这些个缓存条目是通过一致性Hash的方式分布在上。因此，web服务器必须经常与许多memcached服务器通信，以满足用户的请求，所有的web服务器都可以在很短的时间内与每个memcached服务器通信。这种all-to-all的通讯方式，会存在单个cache服务成为众多web服务的瓶颈。数据复制通常可以缓解单服务器瓶颈，但通常会导致严重的内存效率低下。

我们将减少延迟的重心放在每个服务器的memcache client之上。这些客户端包含了一系列的功能，比如：序列化、压缩、请求路由、错误处理和批量请求。客户端中使用map结构维护了所有的可用cache服务，这是通过额外一套配置进行自动更新的。

并行请求和批处理: 我们构建web的服务尽可能的减少在渲染一个页面所需要的网络请求次数。构造了一个有向无环图（DAG）去表示数据之间的依赖，web服务可以利用DAG提高从cache中获取数据的最大条目，每个批量请求平均包含24个密钥。

客户端和服务端之间的通讯: Memcached服务之间并不互相通讯，通常情况下，我们将系统的复杂性嵌入到无状态客户机中，而不是memcached服务器中。这种操作方式极大的简化了memcached,并且可以让我们在有限的用户案例中实现高性能的系统。而且保持客户端无状态可以在软件中快速迭代，并简化我们的部署过程。客户端提供了两种形式的处理逻辑：直接将库嵌入到客户端中，或者直接使用mcrouter代理。该代理提供一个memcached服务器接口，提供请求/应答路由/来自其他服务器的功能。

客户端采用TCP或者UDP的协议去连接memcached服务， UDP会被用于get请求，以为减少延迟和网络开销。

由于UDP是无连接的web服务中的每一个线程都可以直接与memcached进行连接，绕过mcrouter，不需要建立和维护连接从而减少的开销。UDP实现了检测丢失或接收的数据包的顺序(使用序列号)，并在客户端将其作为错误处理。（注：因为UDP是无连接的，不具有TCP的严谨传输机制，所以需要再代码层面额外控制数据包的完整性），且没提供任何错误恢复机制。在我们的具体实践过程中，这个没有提供错误恢复机制的觉得是实用的。在高负载下memcache的客户端观察到只有0.25%的请求会被丢弃，其中大约有80%的请求是由于延迟或者丢包导致的，剩余20%则是由于客户端未按照顺序进行投递。客户端将Get错误视为缓存丢失，但web服务器在查询数据后将跳过向memcached插入条目，以避免在可能过载的网络或服务器上增加额外的负载。

web服务和cache服务在同一个机器上，为了可靠性客户端会采用TCP协议进行set和delete操作。相比与UDP的实现，TCP协议提供的重试机制来可靠的进行需要状态更改的操作（更新和删除）。

web服务依赖于高并发和超额认购（注：例如运行的线程>系统的线程）来实现高吞吐量。在建立连接的时候如果不通过mcrouter进行连接，而是采用各个web 服务开启线程与memcached进行连接，那么将创建大量的TCP的连接，这个操作成本非常高。合并这些连接，将会减少网络传输、CPU、和内存消耗，将会提升web服务效率。

图3展示了在UDP协议下和在TCP协议下，平均、中位数和95%的情况下，获取Key的延迟。

在所有情况下，这些平均值的标准差都小于1%。数据显示，依赖于udp可以减少20%的延迟来服务请求。

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

图4显示了窗口大小对处于可运行状态但等待在web服务器内部调度的用户请求的时间影响。这些个数据是从机架上收集的。用户请求到达服务器请求的特征符合柏松分布,根据利特尔定律 L = λW, 即：在服务器中的请求队列与每个请求的处理时间呈正比，假设输入请求的速率是恒定的（至少在实验中是这样）。web请求等待调度的时间直接指示了系统中web请求的数量。随着滑动串口的减小，web服务将不得不连续调度更多的memcache请求，导致增加web请求的持续时间；如果滑动窗口设置的足够大，对memcache的并发请求可能将阻塞网络。最后将会导致memcache发生错误并且应用程序会退回到进行数据库查询，这将导致web请求的处理变慢。这需要在极端情况下不必要的网络延迟和最小化的网络拥塞进行一个平衡。

# 3.2 Reducing Load

我们使用memcache去减少从数据库获取数据的频率。只有在所需要的数据没有被缓存的时候，才会去请求这些个耗时服务。接下来的章节将会详细介绍减少负载的技术。

# 3.2.1 Lease

我们提供了一种Lease机制来解决缓存中的旧数据和缓存击穿的情况。当query操作和update操作并发执行的时候，将会导致缓存中有旧的数据。而缓存击穿是指在一个key在大量读的情况下，进行了写入操作然后删除了缓存，导致数据在缓存中没有存在流量则会直接打到DB上，导致后端的压力过大。我们的Lease机制将会解决这两个问题。

直观地说，memcached实例向客户端提供一个Lease机制以便在客户端遇到缓存Miss时将数据设置回缓存。Lease是一个64位的Token，绑定到客户端请求的key上面，客户端向cache中设置值的时候需要提供这个Token令牌，通过这个Token，cache服务可以去校验客户端的这个写操作，从而避免并发写入。如果memcached已经接收到对该项的删除请求，则再进来的删除请求则会失败。

Token机制的存在也减轻了缓存击穿，每个memcached服务器都会调整返回令牌的速率，默认情况下，我们将这些服务器配置为每个密钥每10秒只返回一次Token。在发出Token后的10秒内请求键的值会导致一个特殊的通知，告诉客户机等待一小段时间。拥有租约的客户机将在几毫秒内成功设置数据。因此，当等待的客户机重试请求时，数据通常出现在缓存.中。

在没有Lease的情况下，所有缓存丢失导致数据库查询速率的峰值为17 k/s。有了Lease，数据库查询速率的峰值为1.3 k/s。所以Lease机制能够显著提升系统性能。

**过期的值：**通过Lease机制能够在一些情况下显著的减少客户端的响应时间。当Key被删除的时候，它的值被转移到保存最近删除的项的数据结构中，在被刷新之前，它会在数据结构中存在很短的一段时间。get请求可以返回一个Token或被标记为过期的数据。应用可以继续使用这个过期的值，而不用必须从数据库那拿到最新的值。我们的经验表明，由于缓存的值往往是数据库的一个单调增加的快照，所以大多数应用程序可以使用陈旧的值而不做任何更改。

# 3.2.2 Memcache Pools

使用memcache作为通用缓存层需要应用共享基础设施，尽管这些应用服务之间有不同的访问模式、内存占用和服务质量要求，所以在不同应用程序之间可能产生负面干扰，导致命中率降低。

为了适应这些差异，我们将集群的memcached服务器划分到单独的池中。我们指定一个池(命名为wildcard)作为默认值，并为在wildcard中驻留有问题的key提供单独的池。例如，我们可以为频繁访问但缓存丢失代价不高的key提供一个小池。我们也可以为不经常访问的key键提供一个大的池，对于这些键，缓存丢失的代价非常高。

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

# 3.2.3 Replication Within Pools

在一些Pool中，使用复制手段来提高memcached服务器的延迟和效率。

在此实例中，我们倾向于复制，而不是进一步划分键空间。

假设一个memcached服务器拥有100个条目，每秒能够响应500k个请求。每个请求需要100个密钥。每个请求检索100个键而不是1个键的memcached开销差异很小。

为了将系统扩展到处理1m个请求/秒，假设我们添加第二个服务器并在两者之间平均分配密钥空间。

客户现在需要将100个密钥请求分成两个并行请求(~ 50个密钥)。

因此，两台服务器仍然必须每秒处理1m个请求。但是，如果我们将所有100个密钥复制到多个服务器，客户机对100个密钥的请求就可以发送到任何副本。这将每个服务器的负载减少到每秒500k请求。每个客户机根据自己的I p地址选择副本。这种方法需要向所有副本交付失效，以保持一致性。

# 3.2.4 Handling Failures

无法从memcache中获取数据会给后端服务带来过多的负载，从而可能导致进一步的级联故障，类比redis雪崩。

需要从两个层面来处理失败:

由于网络或服务器故障，少数主机无法访问
影响集群中大部分服务器的大范围停机

如果整个集群出现了不得不停机的问题，我们需要将用户web请求转移到其他集群，从而有效地从该集群的memcache中移除所有负载。

对于小型故障，我们依赖于自动修复系统。这些修复行为不是即时的，可能需要几分钟。这个持续时间足够长，足以导致前面提到的级联故障，因此我们引入一种机制来进一步隔离后端服务与故障。我们专门用一组名为gutter的机器来接管一些故障服务器的职责。Gutter大约占集群中memcached服务器的1%。

当memcached客户端没有收到对其get请求的响应时，该客户端假定服务器失败，并再次向一个特殊的槽池发出请求。

如果第二个请求没有成功，客户端将在查询数据库后将适当的键值对插入到gutter机器中。缓存中的条目快速过期，以避免缓存失效。Gutter限制了后端服务的负载，代价是数据稍有陈旧。

注意，这种设计不同于客户机在其余memcached服务器之间重新哈希键的方法。由于密钥访问频率不一致，这种方法存在级联故障的风险。例如，一个密钥可以占服务器请求的20%。负责此热键的服务器也可能超载。通过将负载分流到空闲服务器，我们可以限制这种风险。

通常，每个失败的请求都会导致对后备存储的一次命中，从而可能使后备存储过载。通过使用gutter来存储这些结果，这些失败中的很大一部分将在gutter池中转换为命中，从而减少了对后备存储的负载。在实践中，该系统将客户端可见的失败率降低了99%，并将每天10%-25%的失败转换为命中。如果一个memcached服务器完全失败，槽池中的命中率通常在4分钟内超过35%，经常接近50%。因此，当一些memcached服务器由于故障或轻微网络事故而不可用时，gutter可以保护备份存储免受流量激增的影响。

# 4 In a Region: Replication

随着需求的增加，可以掏钱来购买更多的web和memcached服务器来扩展集群（能掏钱的就不要麻烦程序猿了）。然而，简单地扩展系统并不能消除所有的问题。

为了应对不断增加的用户流量，越来越多的web服务器被添加到集群中，这就会对我们的项目提出更高质量的要求。随着memcached服务器数量的增加，网络拥塞也会恶化。因此，我们将web和memcached服务器拆分为多个前端集群，这些集群会按照区域进行一个划分。这种区域体系结构还允许较小的故障和易于处理的网络配置，我们用数据复制来换取更加可控的故障、可处理的网络配置和网络拥塞的减少。

本节分析多个前端集群共用同一个存储集群时的影响。具体来说，我们将讨论允许跨这些集群进行数据复制的后果，以及禁止这种复制的潜在内存效率。

# 4.1 Regional Invalidations

虽然区域中的存储集群拥有数据的权威副本，但用户需求可能会将数据复制到前端集群中。存储集群负责使缓存数据失效，以保持前端集群与权威版本一致。作为一种优化，修改数据的web服务器也会向自己的集群发送失效信息，为单个用户请求提供先读后写的语义，并减少本地缓存中出现过期数据的时间。

修改状态的sql语句被修改为包含一旦事务提交就需要失效的memcache键。我们在每个数据库上部署失效守护进程(名为mcsqueal)。每个守护进程检查其数据库提交的sql语句，提取任何删除，并将这些删除广播到该区域的每个前端集群中的memcache。图6演示了这种方法。

我们认识到大多数失效并不删除数据; 实际上，只有4%的删除会导致缓存数据的实际失效。

Reducing packet rates: 虽然McSqueal可以直接连接memcached服务器，但从后端集群发送到前端集群的数据包的最终速率将会非常高，流量非常大。这个数据包发送速率问题是多个数据库和多个memcached服务器跨集群边界进行通信的结果。Invalidation守护进程将批量删除到更少的包中，并将它们发送到在每个前端集群中运行mcrouters实例的一组专用服务器。这些mcrouters然后从每个批处理中解包单个删除，并将这些无效路由到前端集群中与之共存的正确memcached服务器。批处理的结果是每个包删除的中位数提高了18倍。

Invalidation via web servers: 对于web服务器来说，向所有前端集群广播缓存失效更简单。不幸的是，这种方法存在两个问题。首先，它引起了更多的网络开销，因为web服务器在批处理无效方面不如mcsqueal管道有效率。其次，当出现系统失效问题(如配置错误导致的删除路由错误)时，它提供的资源很少。在过去，这通常需要滚动重新启动整个memcache基础设施，这是一个我们希望避免的缓慢且具有破坏性的过程。相反，在sql语句(数据库提交并存储在可靠的日志中)中嵌入无效，允许mcsqueal简单地重放可能丢失或路由错误的无效。

# 4.2 Regional Pools

每个集群根据发送给它的用户请求的情况独立地缓存数据。如果用户的请求被随机路由到所有可用的前端集群，那么所有前端集群的缓存数据将大致相同。这允许我们将集群离线进行维护，而不会降低命中率。过度复制数据会导致内存效率低下，特别是对于很少访问的大型项目。我们可以通过让多个前端集群共享同一组memcached服务器来减少副本的数量。我们称之为区域池。

跨越集群边界会引起更多的延迟。此外，我们的网络在集群边界上的平均可用带宽比在单个集群内少40%。复制用更多的memcached服务器来换取更少的集群间带宽、更低的延迟和更好的容错。对于某些数据，放弃复制数据的优势，而在每个区域拥有一个副本会更节省成本。在区域内扩展memcache的主要挑战之一是决定一个键是需要跨所有前端集群复制，还是每个区域只有一个副本。当区域池中的服务器出现故障时，也使用Gutter。

表1总结了应用程序中具有较大值的两种项。我们已经将一种(b)移动到区域池中，而保持另一种(a)不变。注意，客户端访问类别b中的项目比类别a中的项目少一个数量级。类别b的低访问速率使其成为区域池的主要候选对象，因为它不会对集群间带宽产生不利影响。类别b还将占据每个集群通配符池的25%，因此区域化提供了显著的存储效率。但是，a类项目的数量是b项目的两倍，查阅次数也比a类项目频繁得多，因此不符合区域审议的资格。将数据迁移到区域池的决定目前基于一组基于访问率、数据集大小和访问特定项目的唯一用户数量的手动启发式。

# 4.3 Cold Cluster Warmup

当我们将一个新的集群上线时，现有的集群出现故障或执行预定维护时，缓存的命中率将非常低，从而降低了与后端服务隔离的能力。一个称为冷集群预热的系统通过允许“冷集群”(即具有空缓存的前端集群)中的客户端从“热集群”(即具有正常命中率的缓存的集群)而不是从持久存储中检索数据来缓解这一问题。这利用了前面提到的跨前端集群的数据复制。有了这个系统，冷集群可以在几个小时内恢复到满负荷运行，而不是几天。

必须注意避免由于竞争条件而引起的不一致。例如，如果冷集群中的一个客户机执行数据库更新，而来自另一个客户机的后续请求在热集群接收到无效值之前从热集群检索过期值，那么该项在冷集群中将无限期地不一致。Memcached删除支持非零延迟时间，拒绝指定延迟时间内的添加操作。默认情况下，所有对冷集群的删除都会延迟两秒发出。当在冷集群中检测到缺失时，客户机从热集群中重新请求密钥并将其添加到冷集群中。添加失败表明数据库上有新的数据可用，因此客户机将从数据库中重新获取值。虽然理论上仍然存在删除延迟超过两秒的可能性，但对于绝大多数情况来说，这并不正确。冷集群预热的操作好处远远超过缓存一致性问题的代价。一旦冷集群的命中率稳定下来，好处减少，我们就会关闭它。

# 5 Across Regions: Consistency

数据中心更广泛的地理位置有几个优点。首先，让web服务器离用户更近可以显著减少延迟。其次，地理多样性可以减轻自然灾害或大规模停电等事件的影响。再者，新的地点可以提供更便宜的电力和其他经济激励。通过部署到多个地区，我们获得了这些优势。每个区域由一个存储集群和多个前端集群组成。我们指定一个区域保存主数据库，其他区域包含只读副本。我们依靠我的sql的复制机制来保持复制数据库与它们的主数据库保持同步。在这种设计中，当访问本地memcached服务器或本地数据库副本时，web服务器体验到较低的延迟。当访问跨多个区域时，保持memcache中数据和持久存储之间的一致性成为主要的技术挑战。这些挑战源于一个问题: 复制数据库可能落后于主数据库。

我们的系统只代表了一致性和性能权衡的广泛范围中的一个点。一致性模型和系统的其他部分一样，经过多年的演变，以适应站点的规模。它混合了可以实际构建的东西，而不牺牲我们的高性能要求。系统管理的大量数据意味着任何增加网络或存储需求的微小更改都会带来不小的成本。大多数提供更严格语义的想法很少离开设计阶段，因为它们变得非常昂贵。与许多根据现有用例量身定制的系统不同，memcache和facebook是一起开发一起成长的。这允许应用程序和系统工程师一起工作，以找到一个模型，该模型对应用程序工程师来说足够容易理解，但性能和简单程度足以使其在大规模可靠地工作。我们提供最佳的一致性，但强调性能和可用性。因此，这个系统在实践中非常适合我们，我们认为我们找到了一个可以接受的折衷方案。

Writes from a master region: 我们先前的决定要求存储集群通过额外的进程使数据失效，这在多区域体系结构中产生了重要的影响。特别是，它避免了在从主区域复制数据之前出现失效的竞态条件。假设主区域中的web服务器已经完成了对数据库的修改，并试图使过时的数据失效，在主区域内发送key过期请求是安全的。然而，让web服务器在复制区域中使数据失效这种方案不够成熟的，因为更改可能还没有传播到复制数据库。对来自复制区域的数据的后续查询将与后面复制进来流进行竞争，从而增加将过时数据设置到memcache中的可能性。从历史上看，我们是在扩展到多个区域后实现mcsqueal的。

**Writes from a non-master region:**现在考虑当复制延迟过大时从非主区域更新数据的用户。如果用户最近的更改丢失，那么用户的下一个请求可能会导致混乱。应该只允许在复制流赶上后从副本的数据库重新填充缓存。如果不这样做，后续的请求可能会导致副本的陈旧数据被提取和缓存。

我们采用了一种远程标记机制来降低读取陈旧数据的可能性。该标记的存在表明本地副本数据库中的数据可能已经过时，应该将查询重定向到主区域。当web服务器希望更新影响一个键k的数据时，该服务器(1)在区域中设置一个远程标记rk，(2)在s q l语句中执行对嵌入k和rk的主节点的写操作，并(3)在本地集群中删除k。在对k的后续请求中，web服务器将无法找到缓存的数据，检查r k是否存在，并根据r k的存在将其查询指向主区域或本地区域。在这种情况下，当缓存丢失时，我们显式地用额外的延迟来交换读取过时数据的概率的降低。

我们通过使用区域池实现远程标记。注意，在对同一个键进行并发修改时，这种机制可能会显示陈旧的信息，因为一个操作可能会删除一个本该为另一个正在进行的操作保留的远程标记。值得强调的是，我们对远程标记使用memcache与缓存结果有微妙的区别。作为缓存，删除或删除键总是一个安全的操作;它可能会增加数据库的负载，但不会影响一致性。相反，远程标记的存在有助于区分非主数据库是否保存陈旧的数据。在实践中，我们发现清除远程标记和并发修改的情况都是罕见的。

Operational considerations: 区域间的通信是昂贵的，因为数据必须跨越很大的地理距离(例如跨越美国大陆)。通过为删除流共享与数据库复制相同的通信通道，我们在较低带宽连接上获得了网络效率。

前面提到的4.1节中用于管理删除的系统还与副本数据库一起部署，以便将删除广播到副本区域中的memcached服务器。当下游组件失去响应时，数据库和McRouters缓冲区将被删除。任何组件的故障或延迟都会增加读取陈旧数据的可能性。一旦这些下游组件再次可用，将重放缓冲删除。替代方案包括使集群离线或在检测到问题时使前端集群中的数据过度失效。考虑到我们的工作负载，这些方法带来的破坏大于好处。

# 6 Single Server Improvements

all-to-all通信模式意味着单个服务器可能成为集群的瓶颈。本节描述memcached中的性能优化和内存效率提高，它们允许更好地在集群内伸缩。

提高单服务器缓存性能是一个活跃的研究领域[9,10,28,25]。

# 6.1 Performance Optimizations

我们从使用固定大小哈希表的单线程memcached开始。

第一个主要的优化是:

允许哈希表的自动扩展，以避免查找时间漂移到o(n)
使用全局锁使服务器多线程化，以保护多个数据结构
为每个线程提供自己的udp端口，以减少在发送应答时的争用，并在以后扩展中断处理开销。

前两个优化被回馈给了开源社区。本节的其余部分将探讨开放源码版本中尚未提供的进一步优化。

我们用的实验主机如下：

CPU X5650、12核、12超线程、2.67GHZ
千兆网卡 Intel 82574L
内存 12GB

性能测试设置由15个客户机组成，向具有24个线程的单个memcached服务器生成memcache流量。客户端和服务器位于同一个机架上，通过千兆以太网连接。这些测试来测量memcached响应在持续负载的两分钟内的延迟。

Get Performance: 我们首先研究用细粒度锁替换原来的多线程单锁实现的效果。我们通过在发出每个请求10个键的memcached请求之前，用32字节的值预先填充缓存来测量点击率。图7显示了不同版本memcached在亚毫秒级的平均响应时间下可以维持的最大请求率。

第一组条是细粒度锁定之前的memcached，第二组条是当前的memcached，最后一组条是开放源码版本1.4.10，它独立实现了锁定策略的粗粒度版本。

使用细粒度锁定可以将每秒60万个条目的峰值获取率提高到1.8M。缓存失效的性能也从每秒2.7M增加到4.5M。命中的代价更大，因为返回值必须构造并传输，而未命中则需要对整个multiget进行单个静态响应(end)，以指示所有键都未命中。

我们还研究了使用udp代替tcp的性能影响。图8显示了对于10个键的单个获取和多个获取，我们可以在平均延迟小于1毫秒的情况下维持的峰值请求率。

我们发现，我们的udp实现比单次获取的tcp实现高出13%，10键多次获取高出8%。

因为多重获取在每个请求中装入的数据多于单一获取，所以它们使用更少的包来完成相同的工作。图8显示了10键多重获取比单个获取大约提高了4倍。

# 6.2 Adaptive Slab Allocator

Memcached使用slab分配器来管理内存。分配器将内存组织成slab类，每个slab类都包含预分配的、大小一致的内存块。Memcached将项目存储在尽可能小的slab类中，以适应项目的元数据、键和值。Slab类从64字节开始，并以指数形式增长1.07倍，直到1 mb，对齐于4字节。每个slab类维护可用块的空闲列表，并在其空闲列表为空时请求1mb内存空间。一旦memcached服务器不能再分配空闲内存，将使用LRU算法去淘汰一些slab空间。当工作负载发生变化时，分配给每个slab类的原始内存可能不够，从而导致较低的命中率。

我们实现了一个自适应分配器，它定期进行重新分配，以匹配当前工作负载。当它认为slab类需要更多的内存，会根据下一个要驱逐的项目最近使用的时间至少比其他slab类中最近最少使用的项目的平均值多20%这个规则，进行删除。如果找到这样的类，那么保存最近最少使用的slab将被释放并转移到需要的类。请注意，开源社区已经独立实现了一个类似的分配器，它平衡各个slab类之间的驱逐率，而我们的算法专注于平衡各个类之间最古老的项目的年龄。平衡年龄为整个服务器提供了一个更好的近似于单个LRU驱逐策略的方法，而不是调整可能严重受访问模式影响的驱逐率。

# 6.3 The Transient Item Cache

虽然memcached支持过期时间，但缓存条目在过期后仍可以很好地保存在内存中。Memcached在为该条目提供get请求时，或者当它们到达LRU的末尾时，通过检查过期时间来后置删除这些条目。虽然这种方案对于一般情况下是有效的，但是这种方案会浪费一定的内存空间，直到它们到达LRU的末端。

因此，我们引入了一种混合方案，它依赖于大多数Key的惰性删除，并在Key过期时主动删除。我们根据Key的过期时间将短期Key放入链表的循环缓冲区中(以秒为索引直到过期)——称为瞬时项缓存。每一秒钟，位于缓冲区头部的桶中的所有Key都被删除，头部前进1。（类似redis的删除方法，也有点像时间轮）当我们为大量使用的Key集合添加一个短的过期时间，而这些Key的有效寿命却很短;该Key集合使用的memcache池的比例从6%降低到0.3%，而不影响命中率。

# 6.4 Software Upgrades

升级、bug修复、临时诊断或性能测试可能需要对软件进行频繁的更改。memcached服务器可以在几小时内达到其峰值命中率的90%。因此，升级一组memcached服务器可能需要花费12个小时以上的时间，因为需要仔细管理由此产生的数据库负载。我们修改了memcached，将其缓存值和主要数据结构存储在系统的共享内存区域中，以便数据可以在软件升级期间保持存活，从而最大限度地减少中断。

# 7 Memcache Workload

现在，我们使用来自生产中运行的服务器的数据来描述memcache工作负载。

# 7.1 Measurements at the Web Server

我们将记录一小部分用户请求的所有memcache操作，并讨论工作负载的扇出、响应大小和延迟特征。

扇出: 图9显示了web服务器在响应页面请求时可能需要联系的不同memcached服务器。

如图所示，56%的页面请求访问了不到20个memcached服务器。就数量而言，用户请求倾向于请求少量的缓存数据。然而，这种分布有一个长尾效应。该图还描述了一个更流行的页面的分布，该页面更好地展示了all-to-all通信模式。这种类型的大多数请求将访问超过100个不同的服务器;访问几百个memcached服务器并不罕见。

图10显示了来自memcache请求的响应大小。

响应大小: 中位数(135bytes)和平均值(954bytes)之间的差异意味着缓存项的大小有很大的差异。此外，在大约200bytes和600bytes处似乎有三个不同的峰值。较大的项倾向于存储数据列表，而较小的项倾向于存储单个内容片段。

延迟: 我们测量从memcache请求数据的往返延迟，其中包括路由请求和接收应答的成本、网络传输时间以及反序列化和解压缩的成本。在7天内，中位请求延迟是333μs，而第75百分位和第95百分位(p75和p95)分别是475μs和1.135ms。空闲web服务器端到端延迟的中值为178μs，而p75和p95分别为219μs和374μs。p95延迟之间的巨大差异来自于处理大型响应和等待可运行线程被调度(如3.1节所述)。同样，不同的特性促使我们希望将这些工作负载彼此隔离。

# 7.2 Pool Statistics

现在我们讨论四个memcache pool的关键指标。这些池是通配符(默认池)、app(专用于特定应用程序的池)、用于频繁访问的数据的复制池和用于很少访问的信息的区域池。在每个池中，我们每4分钟收集一次平均统计数据，并在表2中报告一个月收集周期的最高平均值。该数据接近这些池所看到的峰值负载。该表显示了不同池的获取、设置和删除速率的巨大差异。表3显示了每个池的响应大小的分布。

如3.2.3节所述，我们在池中复制数据，并利用批处理处理高请求率。注意，尽管复制池的条目大小最小，但它的获取速率最高(约为次高池的2.7倍)，字节与包的比率也最高。这些数据与我们的设计一致，我们利用复制和批处理来实现更好的性能。在应用池中，更高的数据流失率自然也就更高。这个资源池往往包含访问几个小时的内容，然后就会逐渐消失，取而代之的是更新的内容。从请求率和值大小分布可以看出，区域池中的数据往往较大且访问频率较低。

# 7.3 Invalidation Latency

我们认识到，失效的及时性是决定暴露陈旧数据概率的一个关键因素。要监视此运行状况，我们将从100万个删除中选取一个进行采样，并记录发出删除的时间。随后，我们将按一定的间隔在所有前端集群中查询memcache的内容，以获取采样的键，并记录一个错误，即如果删除了应该使其失效的项，但仍保留缓存项。

在图11中，我们使用这种监视机制来报告30天内的失效延迟。

我们将这些数据分成两个不同的部分:

删除来自主区域的web服务器，并被指定为主区域的memcached服务器
删除来自一个复制区域，并打算删除到另一个复制区域。

数据显示，当删除源和目标与主服务器位于同一位置时，我们的成功率会高得多，在1秒内达到4个9秒的可靠性，1小时后达到5个9秒的可靠性。然而，当删除开始并到达主区域以外的位置时，我们的可靠性在一秒钟内下降到3个9，在10分钟内下降到4个9。根据我们的经验，我们发现，如果只在几秒钟后就丢失了失效，最常见的原因是第一次尝试失败了，随后的重试将解决问题。

其他一些大型网站已经认识到键值存储的效用。De candia等人[12]提出了一种高可用的键值存储，它被amazon.com上的各种应用程序服务使用。虽然他们的系统是针对写工作负载进行优化的，但我们的目标是以读为主的工作负载。类似地，linked in使用voldemort[5]，一个受dynamo启发的系统。键值缓存解决方案的其他主要部署包括github、digg和blizzard上的redis[6]，以及twitter[33]和zynga上的memcached。Lakshman等人开发了cassandra，这是一个基于模式的分布式键值存储。我们更喜欢部署和扩展memcached，因为它的设计更简单。

# 9 Conclusion

在本文中，我们展示了如何扩展基于memcached的架构来满足facebook日益增长的需求。讨论的许多权衡不是基本的，而是根植于平衡工程资源的现实，同时在持续的产品开发下发展一个活的系统。

在构建、维护和发展我们的系统的过程中，我们吸取了以下教训：

分离缓存和持久存储系统允许我们独立地扩展它们
提高监视、调试和操作效率的特性与性能同样重要
管理有状态组件在操作上比无状态组件更复杂。因此，将逻辑保存在无状态客户机中有助于迭代特性并将中断最小化
系统必须支持新特性的逐步推出和回滚，即使这会导致特性集的临时异构。
简单性是至关重要的！！

# Acknowledgements

我们要感谢xxxxxxx的贡献。

感谢xxxxxx。

最后，我们要感谢facebook的工程师们，感谢他们的建议、错误报告和支持，正是他们成就了memcache的今天。

# References

ApacheCassandra.http://cassandra.apache.org/.
Couchbase.http://www.couchbase.com/.
MakingFacebookSelf-Healing.https://www.facebook.com/note.php?note_id=10150275248698920.
OpenComputeProject.http://www.opencompute.org.
ProjectVoldemort.http://project-voldemort.com/.
Redis.http://redis.io/.
ScalingOut.https://www.facebook.com/note.php?note_id=23844338919.
ATIKOGLU,B.,XU,Y.,FRACHTENBERG,E.,JIANG,S.,ANDPALECZNY,M.Workloadanalysisofalarge-scalekey-valuestore.ACMSIGMETRICSPerformanceEvaluationReview40,1(June2012),53–64.
BEREZECKI,M.,FRACHTENBERG,E.,PALECZNY,M.,ANDSTEELE,K.Powerandperformanceevaluationofmemcachedonthetilepro64architecture.SustainableComputing:Informat-icsandSystems2,2(June2012),81–90.
BOYD-WICKIZER,S.,CLEMENTS,A.T.,MAO,Y.,PESTEREV,A.,KAASHOEK,M.F.,MORRIS,R.,ANDZELDOVICH,N.Ananalysisoflinuxscalabilitytomanycores.InProceedingsofthe9thUSENIXSymposiumonOperatingSystemsDesign&Implementation(2010),pp.1–8.
CERF,V.G.,ANDKAHN,R.E.Aprotocolforpacketnetworkintercommunication.ACMSIGCOMMCompututerCommuni-cationReview35,2(Apr.2005),71–82.
DECANDIA,G.,HASTORUN,D.,JAMPANI,M.,KAKULAP-ATI,G.,LAKSHMAN,A.,PILCHIN,A.,SIVASUBRAMANIAN,S.,VOSSHALL,P.,ANDVOGELS,W.Dynamo:amazon’shighlyavailablekey-valuestore.ACMSIGOPSOperatingSys-temsReview41,6(Dec.2007),205–220.
FALL,K.,IANNACCONE,G.,MANESH,M.,RATNASAMY,S.,ARGYRAKI,K.,DOBRESCU,M.,ANDEGI,N.Routebricks:enablinggeneralpurposenetworkinfrastructure.ACMSIGOPSOperatingSystemsReview45,1(Feb.2011),112–125.
FITZPATRICK,B.Distributedcachingwithmemcached.LinuxJournal2004,124(Aug.2004),5.
GHANDEHARIZADEH,S.,ANDYAP,J.Gumball:aracecon-ditionpreventiontechniqueforcacheaugmentedsqldatabasemanagementsystems.InProceedingsofthe2ndACMSIGMODWorkshoponDatabasesandSocialNetworks(2012),pp.1–6.
GIFFORD,D.K.Weightedvotingforreplicateddata.InPro-ceedingsofthe7thACMSymposiumonOperatingSystemsPrin-ciples(1979),pp.150–162.
GLENDENNING,L.,BESCHASTNIKH,I.,KRISHNAMURTHY,A.,ANDANDERSON,T.ScalableconsistencyinScatter.InProceedingsofthe23rdACMSymposiumonOperatingSystemsPrinciples(2011),pp.15–28.
GRAY,C.,ANDCHERITON,D.Leases:Anefficientfault-tolerantmechanismfordistributedfilecacheconsistency.ACM
SIGOPSOperatingSystemsReview23,5(Nov.1989),202–210.
GRIBBLE,S.D.,BREWER,E.A.,HELLERSTEIN,J.M.,ANDCULLER,D.Scalable,distributeddatastructuresforinternet
serviceconstruction.InProceedingsofthe4thUSENIXSym-posiumonOperatingSystemsDesign&Implementation(2000),pp.319–332.
HEINRICH,J.MIPSR4000MicroprocessorUser’sManual.MIPStechnologies,1994.
HERLIHY,M.P.,ANDWING,J.M.Linearizability:acorrect-nessconditionforconcurrentobjects.ACMTransactionsonProgrammingLanguagesandSystems12,3(July1990),463–492.
KARGER,D.,LEHMAN,E.,LEIGHTON,T.,PANIGRAHY,R.,LEVINE,M.,ANDLEWIN,D.ConsistentHashingandRandomtrees:DistributedCachingProtocolsforRelievingHotSpotsontheWorldWideWeb.InProceedingsofthe29thannualACMSymposiumonTheoryofComputing(1997),pp.654–663.
KEETON,K.,MORREY,III,C.B.,SOULES,C.A.,ANDVEITCH,A.Lazybase:freshnessvs.performanceininformationmanagement.ACMSIGOPSOperatingSystemsReview44,1(Dec.2010),15–19.LAMPORT,L.Thepart-timeparliament.ACMTransactionsonComputerSystems16,2(May1998),133–169.
LIM,H.,FAN,B.,ANDERSEN,D.G.,ANDKAMINSKY,M.Silt:amemory-efficient,high-performancekey-valuestore.InProceedingsofthe23rdACMSymposiumonOperatingSystemsPrinciples(2011),pp.1–13.
LITTLE,J.,ANDGRAVES,S.Little’slaw.BuildingIntuition(2008),81–100.
LLOYD,W.,FREEDMAN,M.,KAMINSKY,M.,ANDANDER-SEN,D.Don’tsettleforeventual:scalablecausalconsistencyforwideareastoragewithCOPS.InProceedingsofthe23rdACMSymposiumonOperatingSystemsPrinciples(2011),pp.401–416.
METREVELI,Z.,ZELDOVICH,N.,ANDKAASHOEK,M.Cphash:Acache-partitionedhashtable.InProceedingsofthe17thACMSIGPLANsymposiumonPrinciplesandPracticeofParallelProgramming(2012),pp.319–320.
OUSTERHOUT,J.,AGRAWAL,P.,ERICKSON,D.,KOZYRAKIS,C.,LEVERICH,J.,MAZI`ERES,D.,MI-TRA,S.,NARAYANAN,A.,ONGARO,D.,PARULKAR,G.,
ROSENBLUM,M.,RUMBLE,S.M.,STRATMANN,E.,ANDSTUTSMAN,R.Thecaseforramcloud.CommunicationsoftheACM54,7(July2011),121–130.
PHANISHAYEE,A.,KREVAT,E.,VASUDEVAN,V.,ANDER-SEN,D.G.,GANGER,G.R.,GIBSON,G.A.,ANDSE-SHAN,S.Measurementandanalysisoftcpthroughputcol-
lapseincluster-basedstoragesystems.InProceedingsofthe6thUSENIXConferenceonFileandStorageTechnologies(2008),pp.12:1–12:14.
PORTS,D.R.K.,CLEMENTS,A.T.,ZHANG,I.,MADDEN,S.,ANDLISKOV,B.Transactionalconsistencyandautomaticmanagementinanapplicationdatacache.InProceedingsofthe9thUSENIXSymposiumonOperatingSystemsDesign&Implementation(2010),pp.1–15.
RAJASHEKHAR,M.Twemproxy:Afast,light-weightproxyformemcached.https://dev.twitter.com/blog/twemproxy.
RAJASHEKHAR,M.,ANDYUE,Y.Cachingwithtwem-cache.http://engineering.twitter.com/2012/07/caching-with-twemcache.html.
RATNASAMY,S.,FRANCIS,P.,HANDLEY,M.,KARP,R.,ANDSHENKER,S.Ascalablecontent-addressablenetwork.ACMSIGCOMMComputerCommunicationReview31,4(Oct.2001),161–172.
SATYANARAYANAN,M.,KISTLER,J.,KUMAR,P.,OKASAKI,M.,SIEGEL,E.,ANDSTEERE,D.Coda:Ahighlyavailablefilesystemforadistributedworkstationenvironment.IEEETrans-actionsonComputers39,4(Apr.1990),447–459.