Memcached是一个知名的,简单的,全内存的缓存方案。这篇文章描述了facebook是如何使用memcached来构建和扩展一个分布式的key-value存储 来为世界上最大的社交网站服务的。我们的系统每秒要处理几十亿的请求,同时存储了几万亿的数据项,可以给全世界超过10亿的用户提供丰富体验。 1 介绍近些年SNS网络大行其道,这对网站基础建设提出了巨大的挑战。每天有亿万的用户在使用这些网络服务,巨大的计算、网络和I/O资源的需求使传统的web 架构不堪重 负。SNS网站的基础架构需要满足:1、近乎实时的交流; 2、即时聚合不同来源的内容; 3、访问和更新非常热门的共享内容; 4、每秒处理几百万的用户请 求。 我们将描述我们是如何改进memcached[14]的开源版本,并且用它作为组件来构建用于世界上最大的社会化网络的分布式key-value存储的。 我们会讨论从单集群服务器扩展成地理上分布式的多集群的历程。据我们所知,这个系统是世界上已安装的规模最大的memcached系统,每秒可以处理几十 亿的请求,存储数以万亿的数据项。 本文是关于认识分布式key-value存储的灵活性和实用性的系列文章[1, 2, 5, 6, 12, 14, 34, 36]的最后一篇。本文关注于memcached,这是一个全内存哈希表的开源实现,它以较低的开销提供了对共享存储的低迟延访问。有了这些特性我们可以 构建数据密集的功能,否则是不可能的。例如,如果一个页面请求会产生数以百计的数据库请求,那么这样的功能只能停止在原型阶段,因为实现起来会太慢,代价 也太高。然而,在我们的应用里,web页面通常都会从memcached服务器获取数以千计的key-value对。 我们的目标之一,是展现部署在不同尺度(系统)上的重要主题。虽然在所有尺度上是很重要的品质,如性能,效率,容错性和一致性,我们的经验表明,在特定大小的一些素质要求比别人更多的努力来实现。举例来说,保持数据的一致性,如果复制的内容是小量的,可以更容易在小尺度的网络上实现,相比较大的网络往往只是复制必要的内容。此外,找到一个最佳的通信调度的重要性增加的数量增加服务器和网络工作成为瓶颈。 本文包括四个主要贡献:(1)我们描述了Facebook的基于memcach架构的演化。 (2)我们确定memcached的提高性能和增加内存效率的改进。 (3)我们简明扼要地讲述提高我们的经营能力我们的系统规模的机制。 (4)我们对生产工作负载赋予了特色。 2 综述以下特点大大影响了我们的设计。第一,用户阅读的内容比他们创建的要多一个数量级,这种行为(读写的特点)所产生工作负载,显然让缓存可以发挥很大的优 势。第二,我们是从多个来源读取数据的,比如MySQL数据库、HDFS设备和后台服务,这种多样性要求一个灵活的缓存策略,能够从各个独立的源中储存数 据。 MemCached提供了一组简单的操作(set、get和delete),使它在一个大规模的分布式系统中成为注目的基础组件。开源版本提供了单机内存 哈希表,在本文中,我们从这个开源版本开始,讨论我们是怎么使用这个基础组件,使它变得更有效,并用它来建一个可以处理每秒数十亿请求的分布式的键-值储 存系统。接下来,我们用“memcached”来指代它的源码或者它运行的二进制实例,用“memcache”来指代由每个实例构成的分布式系统。
图1:Memcache作为填补需求的旁路缓存系统。左半图说明了WEB服务器读取缓存时命中失败的读取路径,右半图说明其写路径。 查询缓存:我们依赖于memcache来减轻读取数据库 的负担。特别的,我们使用memcache作为填补需求的旁路缓存系统,如图1。当一个Web服务器需要数据时,首先通过一个字符串的键在 memcache中请求,如果没有找到,它会从数据库或者从后台服务中检索,再使用该键把结果存回memcache中。对于写的请求,Web服务器发送 SQL语句到数据库,接着发送删除请求到memcache,使旧的缓存数据失效。因为删除是幂等运算,所以我们使用删除缓存的方式,而不是更新缓存。
在应对MySQL数据库繁重的查询通信的众多方法中,我们选择了memcache,在有限的资源与时间限制下,这是最好的选择。此外,缓存层与持久层分离,让我们可以在工作负载发生变化时快速地调整。 通用缓存:我们同样让memcache成为一个更加通用 的键-值储存系统。比如说,工程师们使用memcache保存复杂的机器学习算法的中间结果,这些结果能被很多其它应用程序所使用。它只需要我们付出很少 的努力,就可以让新增的服务利用现有的正在使用的基础设施,而无需调整、优化、调配和维护大型的服务器群。 正如memcached没有提供服务器到服务器的协同,它仅仅是运行在单机上的一个内存哈希表。接下来我们描述我们是如何基于memcached构建一个分布式键值储存系统,以胜任在Facebook的工作负载下的操作。
图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,以便避免对可能超载的网络会服务器增添额外的负载。
图 3: 经过mcrouter以后 UDP, TCP得到的延迟 为了可靠性,客户端通过同一个web服务器上运行的mcrouter实例,在TCP协议之上运行set与delete操作。对我们需要确认状态变化(更新和删除)的操作,TCP避免了UDP实现中增加重试机制的必要。 Web服务器依赖很高程度的并行性与超量提交来获得高吞吐量。如果不采用由mcrouter合并的某种形式的连接,打开TCP连接需要的大量内存将使得在 每个web线程与memcached服务器之间打开连接变得尤其代价昂贵。通过减少高吞吐量TCP连接对网络,CPU和内存资源的需求,合并这些连接的方 式增强了服务器的效率。图3显示了生产环境中web服务器在平均的,中级的,以及百分之95的条件下,在UDP和通过经由TCP的mcrouter机制下 获得关键字的延迟。在所有情形,与这些平均值的标准差小于1%。正如数据所示,依赖UDP能有20%的延迟缩减来对请求提供服务。 ================= =======================
1 百分之95的页面抓取的是1,740项目。 Incast拥塞:memcache客户端实现流量控制机制限制incast拥塞。当一个客户端请求大量的主键时,如果所有应答同时达到,那么这些应答可 以淹没一些组件,例如:机架和集群交换机。因此客户端使用滑动窗口机制[11]来控制未处理请求的数量。当客户端收到一个应答的时候,那么下一个请求就可 以发送了。与TCP的拥塞控制类似,滑动窗口的大小随着成功的请求缓慢的增长,当一个请求没有应答的时候就缩小。这个窗口应用于所有的memcache请 求,而不关心目的地址;然而TCP窗口仅仅应用于单独的数据流。
图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不一样,不要混淆。] 过期值:当使用租约机制的时候,我们可以最小化某些特定用例下的应用等待时间。我们可以通过鉴别返回稍微过期 数据可以接受的情况进一步减少等待时间。当一个主键被删除的时候,对应的值转移到一个保存最近删除项的数据结构中,在被清楚之前将会存活很短的时间。一个 get请求可能返回一个租约,或者是一个标记为已过时的数据。应用可以使用过时的数据继续转发处理,而不需要等待从数据库读取的最新数据。经验告诉我们因 为缓存数据趋向于单调递增的数据库快照,大部分应用可以在对数据不做改变的情况下使用过时数据。
图5:高抖动键集合和低抖动键集合的每日和每周的工作集
3.2.2 memcache池 使用memcache做为通用的缓存层要求不同的工作负载分享基础设施,尽管它们具有不过的接入模式、内存占用和服务质量要求。不同应用的工作负载可以产生负干扰,这将会导致命中率下降。 为了适用这些差异,我们将集群的memcached服务器分割成独立的池。我们指定一个池(称作wildcard)为默认池,针对那些放在 wildcard中不合适的主键提供另外的池。例如,我们可能为频繁存取但是缓存不命中不耗时的主键分配一个小池。我们也可能为那些不频繁存取但是缓存不 命中异常耗时的主键分配一个大池。 图5展示了两个不同的项目集合的工作集,一个低抖动,另一个高抖动。工作集通过对每百万分之一数据项采样所有操作来近似。对于这些数据项,我们收集最小、 平均和最大数据项大小。这些数据项大小被加总,然后乘以一百万来近似工作集。每日和每周工作集的不同指出抖动的总数。具有不同抖动特征的数据项以一种不幸 的方式相互影响:那些仍然有价值的低抖动主键在那些不再被存取的高抖动主键之前被踢出。将这些不同的主键放在不同的池中将会阻止这种负干扰,同时使我们可 以通过设置高抖动池的大小来适用缓存不命中的成本。第7章提供了更深入的分析。
[译者注:工作集定义为在一个特定的时间段内一个进程所需要的内存]
图6:失效流水线 展示那些需要经过守护进程(mcsqueal)删除的主键
通过web服务器发送失效命令:通过web服务器广播失效命令到所有前端服务器更简单。很不幸,这个方法存在两个问 题。第一个,因为web服务器在批处理无效命令时没有mcsqueal有效率,所以它具有更高的包成本。第二个,当系统性的无效问题出现时,这种方法会无 能为力,比如由于配置错误造成的删除命令错误路由。过去,这经常需要动态重启整个memcache基础设施,这样一个缓慢的、破坏性的进程是我们一直想避 免的。相反,将失效命令嵌入SQL语句允许mcsqueal简单的重新执行可能已经丢掉的或者错误路由的失效命令,因为数据库提交存储有可靠的日志。 表1: 集群复制或region复制的决定性因素
[译者注:动态重启(rolling restart)是赛车比赛中的一个术语。看看F1比赛就会有个直观的概念,比赛的时候经常会出现安全车领着赛车跑两圈,当安全车离开后出现绿旗,这就是一次rolling start] 5 跨地区:一致性
将数据中心分布到广泛的地理位置具有很多优势。第一,将web服务器靠近终端用户可以极大地较少延迟。第二,地理位置多元化可以缓解自然灾害和大规模电力 故障的影响。第三,新的位置可以提供更便宜的电力和其它经济上的诱因。我们通过部署多个region来获得这些优势。每个region包含一个存储集群和 多个前端集群。我们指定一个region持有主数据库,别的region包含只读的副本;我们依赖MySQL的复制机制来保持副本数据库与主数据库的同 步。基于这样的设计,web服务器无论访问本地memcached服务器还是本地数据库副本的延迟都很低。当扩展到多region的时候,维护 memcache和持久化存储的数据一致性成了主要的技术挑战。这些挑战源于一个问题:副本数据库可能滞后于主数据库。 6 单个服务器的提升多对多的通信模式隐含着单独的服务器将会成为集群的瓶颈。这章将会讲述性能调优和memcached内存效率的提高,这有利于集群更好的扩展。提升单个服务器缓存的性能是一个活跃的研究领域[9,10,28,25]。 6.1 性能调优
我们开始使用具有固定大小哈希表的单线程memcached。第一批主要的优化是:(1)允许哈希表自动扩展来避免查找时间漂移到O(n),(2)通过一 个全局锁来保护多数据结构使得服务器多线程化,(3)赋予每个线程独立的UDP端口来减少发送副本和稍后传播中断处理开销的争用。前两个优化都贡献给了开 源社区。下述章节将会探索还没在开源版本出现的进一步优化。
[译者注:X5650好像是6核的]
使用细粒度的锁使得请求命中的峰值从每秒600K到达了1.8M提升了3倍。不命中的性能也从每秒2.7M提升到了4.5M。因为返回值需要构建和传输,而不命中对于整个多请求仅需要一个表明所有主键不命中的静态回应(END),所以命中的情况更耗时。
图7:对不同memcached版本多获取命中和不命中的性能比较
图8:对TCP和UDP单主键请求和10主键请求获取命中的性能比较
因为多主键获取在单个请求比单主键获取多打包了很多数据,所以它们使用了更少的包完成了同样的事情。图8展示了10个主键获取比单主键获取有接近4倍的性能提升。 6.2 适应性的slab分配器memcached使用一个slab分配器来管理内存。这个分配器将内存组织为slab类,每类包含预分配的均匀大小的内存块。memcached将数据 项存储到可以适应数据项元数据、键和值大小的最小可能性的slab类。slab类从64byte开始,以1.07为因子指数性增加到1MB,以4byte 对齐3。每个slab类维护一个可获得内存块的空闲列表,当它的空闲列表是空的,那么就从1MB slab中请求更多内存。一旦memcached服务器再也不能分配空闲内存,通过移除slab类中最近最少使用(LRU)的数据项来存储新的数据项。当 工作负载改变时,原有分配给每个slab类的内存可能不再足够,这样将会导致低命中率。
================= =======================
我们实现了一个适应性的分配器,这个分配器将会周期性的重新平衡slab分配来适应当前的工作负载。如果slab类正在移除数据项,而且如果下一个将要被 移除的数据项比其它slab类中的最近最少使用的数据项的最近使用时间至少近20%,那么就说明这个slab类需要更多内存。如果找到了一个这样的 slab类,那么就将存储最近最少使用数据项的slab释放,然后转移到needy类。注意,开源社区已经独立实现了一个类似的平衡跨slab类移除率的 分配器,然而我们的算法关注平衡所有类中最久数据项的时长。平衡时长比调整移除率对整台服务器单个全局最近最少使用(LRU)移除策略提供了更好的近似, 而且调整移除率深受接入模式的影响。 6.3 临时条目的缓存因为memcached支持过期时间,条目在它们过期之后仍可以驻留在内存中。 当条目被请求时或者当它们到达LRU的尾端时,Memcached会通过检查过期时间来延时剔除这些条目。 尽管在一般情况下很有效,但是这种模式允许那 些偶尔活跃一下的短期键值占据内存空间,直到它们到达LRU的尾部。
所以我们引入一种混合模式,对多数键值使用延时剔除,而对过期的短期键值则立即剔除。我们根据短期条目的过期时间把它们放入一个由链接表构成的环形缓存区 (花费几秒编入索引直到过期) – 我们称之为临时条目缓存区。每一秒钟,该缓存的头部数据格里的所有条目都会被剔除,然后头部向前移动一格。当我们给一个频繁使用的键值集合(它们对应条目 的寿命很短)设置一个短超期时间后, 该键值集合使用的memcache缓冲池的比例从6%下降到0.3%,而没有影响到命中率。 6.4 软件升级 升级、bug修复、临时诊断或性能测试都需要频繁的软件变更。一个memcached服务器能够在几小时内达到 90% 的命中率峰值。接下来,可能会耗费12小时来进行memcached服务器升级,这将要求我们谨慎管理数据库负载。我们修改了memcached,使用 System V 共享内存区来存储缓存值和主数据结构,以便在软件升级过程中数据仍能够保持可用,进而最小化损失。
图 9: 不同数量memcached服务器的访问数累积分布图 7 memcache工作负载现在我们用从生产环境中运行服务器上所获得的数据来描述memcache的负载。 7.1 web服务器上的测量
我们收集了小比例用户请求的所有memcache操作,然后讨论了扇出(fanout)、响应大小和我们工作负载的延迟特征。 延迟:我们测量从memcache请求数据的往返延迟, 这个延迟包含了请求路由和接收回复的成本、网络传输时间和反序列化和解压缩的成本。通过7天的统计,请求延迟的中位数是333微秒,位于第75百分位的是 475微秒,位于第95百分位的是1.135毫秒。空闲web服务器端到端延迟的中位数是178微秒,位于第75百分位的是219微秒,位于第95百分位 的是374微秒。在第95百分位上延迟的巨大差异是由处理数据量大的回应和等待可运行线程调度引起的,这些在3.1章已经讨论过了。
图10:读取数据大小的累积分布 7.2 池的统计
现在我们讨论四个memcache池的测量。这些池分别是wildcard(默认池),app(专门设定给特定应用的池),给存取频繁的数据的 replicated pool,给很少存取的数据的regional pool。在每个池中,我们每四分钟收集一次平均的统计,表2展示了一个月的统计周期的最大平均值。这些数据近似于那些池的峰值负载。这张表显示了对于不 同的池,get、set和delete操作的频率存在很大差异。表3展示了每个池响应大小的分布。这些不同的特征激发了我们分隔不同工作负载的欲望。 我们发现,在确定暴露过期数据的概率上,失效的及时性是一个关键因素。为了监控该生命值,我们从百万次删除操作中取样一次并记录删除命令发出的时间。随 后,我们定期地为该样本查询所有前端集群中memcache的内容,如果删除命令将一个字段设定为无效时,该字段仍然缓存,则记录一个错误。
图11:删除的管线的延时
8 相关工作一些其他的大型网站已经意识到key-value存储的应用。DeCandia 等[12]构建了高可用的key-value存储系统(Dynamo),已经亚马逊网站应用服务中大量使用。相比较,Dynamo主要着眼于优化高负荷状 况下的写操作,而我们系统的负荷主要是大量的读操作。类似的有,LinkedIn 使用Voldemort[5],由Dynamo衍生而出。其他被大量使用的key-value存储方案包括Github,digg和Blizzard使用 Redis[6];Twitter[33]和Zynga使用memcahed。Lakshmanet等[1]开发了Cassandra,一个基于模式的分 布式key-value数据库。然而我们更趋向于使用和扩展memcached,主要是由于其简单的设计。 我们的工作是扩展memecached使其在分布式数据架构下工作。Gribble等[19]构建了一个早期版本的key-value存储系统用于 Internet扩展服务。Ousterhout等[29]也构建了一个大规模内存key-value存储系统。与这些方案不同,memcache不保证 持久性。我们利用其它的系统来解决数据存储的持久性问题。 表2:各类型的平均超过7天的memcache程序池流量图
表 3: 各类型程序池关键词大小分布(k)
Ports等[31]提供了一个用于管理事任务数据库查询结果缓存的类库。我们需要的是一个更灵活的缓存措略。我们利用最近和过期读优先措略用来研究高 性能系统下缓存一致性和读操作。Ghandeharizadeh和Yap等研究也提出了一个公式,解决基于时间标记而不是确定的版本号过期集合的问题。 9 总结在这篇文章里,我们展示了使用基于memcached的技术来满足Facebook不断增长的需求. 文中讨论的很多权衡都不是很基础, 但是却是在优化线上系统性能时真实遇到的,而这个线上系统的规模还在持续部署新产品的过程中不停的扩大. 在建设、维护、扩容我们的系统时,我们学到了一下的经验。(1) 分离的缓存和持久化存储系统使我们可以对他们进行单独的度量. (2) 监视、报错、可选的特性和性能一样重要. (3) 管理有状态的组件要比管理无状态组件复杂的多. 所以将逻辑保存在无状态的客户端里会对特性的反复调用有帮助并且使系统的分裂最小化. (4) 系统要可以逐步的增加或减少新功能,即使这会导致系统的功能集临时的异构. (5) 简洁至关重要.转自:http://www.oschina.net/translate/scaling-memcache-facebook 转载请保留固定链接: https://linuxeye.com/news/1715.html |