1 介绍
我们将描述我们是如何改进memcached[14]的开源版本，并且用它作为组件来构建用于世界上最大的 会化 络的分布式key-value存储的。我们会讨论从单集群服务器扩展成地理上分布式的多集群的历程。据我们所知，这个系统是世界上已安装的规模最大的memcached系统，每秒可以处理几十亿的请求，存储数以万亿的数据项。
我们的目标之一，是展现部署在不同尺度（系统）上的重要主题。虽然在所有尺度上是很重要的品质，如性能，效率，容错性和一致性，我们的经验表明，在特定大小的一些素质要求比别人更多的努力来实现。举例来说，保持数据的一致性，如果复制的内容是小量的，可以更容易在小尺度的 络上实现，相比较大的 络往往只是复制必要的内容。此外，找到一个最佳的通信调度的重要性增加的数量增加服务器和 络工作成为瓶颈。
2综述
图2：整体架构
论文的结构主要描述了在三种不同的规模下出现的问题。当我们拥有第一个服务器集群时，频繁的读负载和广泛的输出是我们最大的担心。当有必要扩展到多个前端集群时，我们解决了集群间的数据备份问题。最后，我们描述了一种机制，这种机制让我们可以在全世界伸展集群的同时提供平滑的用户体验。不论在什么尺度上，容错性和操作复杂性总是很重要的。我们展示了重要的数据参考，这些数据指引我们做出了最终的设计决定，读者如需获得更多细节性的分析，请参看Atikoglu et al.[8]的工作。提纲挈领的解释参看图2，这是最终的架构，我们将并置集群组织起来，形成一个群体（region），指定一个主群体（master），由主群体提供数据流让非主群体保持数据同步。
在系统的发展中，我们将这两个重大的设计目标放在首位：
1. 只有已经对用户或者我们的运维产生影响的问题，才值得改变。我们极少考虑范围有限的优化。
2. 对陈旧数据的瞬态读取，其概率和响应度类似，都将作为参数来调整。我们会暴露轻度陈旧的数据以便后台存储和高强度负载绝缘。
3 集群之中： 延迟和负载
现在考虑集群中数以千计的服务器所带来的挑战。在这种规模之下，我们着眼于减少获取缓存时的负载，以及缓存不中时数据库的负载。
3.1 减少延迟
不论缓存是否命中，memcache的响应时间都是影响总响应时间的重要因素。单个的 页请求一般包含数百个memcache读请求。如一个较火的页面平均需要从memcache中获取521个不同的资源。
为了减少数据库等的负担，我们准备了缓存集群，每个集群都由数百台memcache服务器组成。资源个体经hash后存于不同的memcache服务器中。因此，web服务器必须请求多台memcache服务器，才能满足用户的请求。由此导致在很短的时间里每个web服务器都要和所有的memcache服务器沟通。这种所有对所有的连接模式会导致潮涌堵塞（incast congestion）或者某台服务器不幸成为瓶颈。实时备份可以缓解这种状况，但一般又会引起巨大的内存浪费。（译者：为何
我们减少延迟的方法主要集中在memcache客户端，每一个web服务器都会运行memcache客户端。这个客户端提供一系列功能，包括：串行化、压缩、请求路由、错误处理以及请求批处理。客户端维护着一个对所以可获得的服务器的映射，对这个映射表的更新需要通过一个辅助的配置系统。
并行请求和批处理：我们构建web应用代码，目的是最小化对于页面请求回应所必要的 络往返数。我们构建了有向无环图（DAG）用来表示数据间的依赖。web服务器使用DAG来最大化可以并发读取的项目数。平均来说，这些批量请求对于每个请求包含24个主键。
客户端-服务器通信：memcached服务器不会直接通信。如果适当，我们将系统的复杂度嵌入无状态的客户端，而不是memcached服务器。这极大地简化了memcached，使我们专注于针对更有限的用例提供高性能。保持客户端的无状态使得我们可以快速迭代开发，同时也简化了部署流程。客户端的逻辑可以提供为两种组件：可以嵌入应用的一个库，或者做为一个名为mcrouter的独立的代理程序。这个代理提供memcached服务器的借口，对不同服务器之间的请求/回复进行路由。
客户端使用UDP和TCP协议与memcached服务器通讯。我们依赖UDP来使请求的延迟和开销缩减。因为UDP是无连接的，web服务器中的每个线程都被允许直接与memcached服务器通信，通过mcrouter，不需要创建与维护连接因而减少了开销。UDP实现了检测出丢失的或失序接收（通过序列 ）的包，并在客户端将它们作为异常处理。它没有提供任何试图恢复的机制。在我们的基础架构中，我们发现这个决定很实际。在峰值负载条件下，memcache客户端观察到0.25%的请求会被丢弃。其中大约80%是由于延迟或丢失包，其余的是由于失序的交付。客户端将异常作为缓存不命中处理，但是web服务器在查询出数据以后，会跳过插入条目到memcached，以便避免对可能超载的 络会服务器增添额外的负载。
图4：web请求平均等待调度时间 图4展示了窗口大小对web服务器中处于运行态的用户请求等待调度总时间的影响。这些数据从一个前端集群的多台机架采集而来。在每个web服务器，用户请求呈现泊松到达过程。参照Little定律[26]，L=λW，假设输入请求速率是恒定的（在我们的试验中就是这样），在服务器排队的请求数量（L）正比于处理请求的平均时间（W）。web请求的等待调度时间是web请求在系统中数量的一个直接指标。当窗口比较小的时候，应用将不得不串行地分发更多组memcache请求，这将会增加web请求的持续时间。当窗口过大的时候，同时处理的memcache请求的数量将会引发incast拥塞。结果将会是memcache错误，应用退化到从持久化存储中取数据，这样将会导致对web请求的处理更缓慢。在这两个极端之间有一个平衡，处于这个平衡的时候，不必要的延迟将会避免，同时incast拥塞可以被最小化。 3.2 减少负载
我们使用memcache来减少用更耗时的方式读数据的频率，比如数据库查询。当期望的数据没有被缓存的时候，web服务器将会退化到使用更耗时方式。下述子章节将会描述三种技术，用来减少负载。
3.2.1 租约（leases）
我们引入了一个称为租约（leases）的新机制来解决两个问题：过时设置（stale sets）和惊群（thundering herds）。当web服务器更新一个在缓存中不是最新版本的值的时候，一次过时设置就发生了。当对memcache的并发更新重新排序的时候，这种情况是会发生的。当某个特定的主键被大量频繁的读写，那么一次惊群就发生了。因为写操作反复地使最近设置的值失效，那么读操作将会默认地使用更耗时的方式。我们的租约机制解决了这两个问题。
[译者注：此处的leases与Cary G. Gray的leases不一样，不要混淆。]
直观地，当这个客户端发生缓存不命中时，memcached实例给客户端一个租约，将数据设置到缓存中。租约是一个64bit的令牌，与客户端初始请求的主键绑定。当设值到缓存中时，客户端提供这个租约令牌。通过这个租约令牌，memcached可以验证和判断是否这个数据应该被存储，由此仲裁并发写操作。如果因为收到了对这个数据项的删除请求，memcached使这个租约令牌失效，那么验证操作将会失败。租约阻止过时设置的方法类似于load-link/store-conditional操作[20]。
对租约的轻微改动也可以缓和惊群这个问题。每个memcached服务器调节返回令牌的速率。默认情况，我们配置服务器对于每个主键每10秒钟返回一个令牌。当在10秒钟之内有请求，一个特殊的通知将会告诉客户端稍等一下。通常，拥有租约的客户端将会在几个毫秒的时间内成功设置数据。因此，当等待客户端重试的时候，数据经常已经在缓存中了。 为了说明这一点，我们针对容易造成惊群的主键集合收集了一个星期的缓存不命中的记录。如果没有租约机制，所有的缓存不命中都会造成数据库查询率的峰值——17K/s。使用租约机制的时候，数据库查询率的峰值是1.3K/s。因为我们依据峰值负载准备数据库，所有租约机制提供了显著的效率增益。
过期值：当使用租约机制的时候，我们可以最小化某些特定用例下的应用等待时间。我们可以通过鉴别返回稍微过期数据可以接受的情况进一步减少等待时间。当一个主键被删除的时候，对应的值转移到一个保存最近删除项的数据结构中，在被清楚之前将会存活很短的时间。一个get请求可能返回一个租约，或者是一个标记为已过时的数据。应用可以使用过时的数据继续转发处理，而不需要等待从数据库读取的最新数据。经验告诉我们因为缓存数据趋向于单调递增的数据库快照，大部分应用可以在对数据不做改变的情况下使用过时数据。
图7：对不同memcached版本多获取命中和不命中的性能比较
图 9: 不同数量memcached服务器的访问数累积分布图
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！