Scaling Memcache at Facebook学习笔记

基本情况:

  1. the largest memcached installation in the world
  2. provides a suite of configuration, aggregation and routing services to organize memcached instances into a distributed system
  3. 使用旁路型cache-demand-filled look-aside cache
  4. 在不同的Scale需要解决的问题重点不一样:performace efficiency fault-tolerance consistency

基本操作

  1. Query Cache:先从memcache读取,然后出现miss,再从DB读取,最后写入cache
  2. Update Cache:  先update DB 然后在cache中删除。采用delete cache操作,是因为delete是幂等操作,可以防止出现并发写造成的数据不一致现象

单集群场景

  1. 一个集群内部有thousands of server, 面临的主要问题有两个:读取cache的延迟以及cache miss造成的负载
  2. 解决延迟主要的方式主要在Client端的优化,Client主要负责了序列化、压缩等操作,同时会通过Configuration System更新下游可用的Cache Server
  3. 延迟优化方案-并行化和批量请求:会根据数据之间的依赖关系构造一个DAG,根据DAG最大化可以并行请求的数据数。平均一次请求会有24个key
  4. 延迟优化方案-不同场景分别使用UDP和TCP。对于读请求使用了UDP,前端每个Client的每个线程都直接与memcache通信。Client端在读取失败时会认为是cache miss,但是在这种场景下的cache miss并不会把从DB读取的结果再写入cache,这是为了避免给整个集群的网络带来额外负担。对于更新请求使用了TCP,Client端通过一个部署在同一机器上的mcrouter与memcache交互,引入中间层可以减少Client每个线程维护大量TCP连接带来的网络、内存和CPU消耗。按照论文而言,relying on UDP can lead to a 20% reduction in latency to server requests
  5. 延迟优化方案-使用滑动窗口的流控机制来减少incast congestion。当一个Client发出了大量读请求,如果这些请求的response同时到达,将会对机架和集群交换机的带宽造成了过载压力。滑动窗口过小会造成不必要的延迟,窗口过大会造成incast congestion,导致落到后端DB的压力变大,进一步延迟会变大
  6. 负载优化方案-采用Lease机制。Lease是一个64-bit的Token,由MemCache在读请求时分配给Client,可以用来解决两个问题:stale sets 和thundering herds。stale sets是指在Query Cache和Update Cache并发执行时,可能会导致Query Cache在Cache Miss的情况下会往cache中写入老数据,通过在写入时加Lease验证+Lease会在接收到delete操作时会失效的机制可以解决这个问题。thundering herds发生在一些特殊的key写操作频繁同时很多并发读请求。当大量读请求出现cache miss时就会导致后端压力过大。Cache可以在原有的lease机制做些小改进,并不是每个读请求都分配Lease,而是每个key 10s才分配一次。那么Client在没有获取到lease时 可以稍等一段时间再重新访问cache,此时cache中已有数据。通过这样的方式,可以使得这些特殊的key的DB读请求由17K/s减少到1.3K/s。此外还有个Stale values的tricky技巧,当key接收到删除操作时,value会放到一个最近删除列表,等待过一段短时间才会真正删除(类似于延迟删除)然后部分应用可以接受读取这些待删除的不一致的脏数据。
  7. 负载优化方案-拆分成Memcache Pools。如果不同的应用共享同一个Cache集群,那么使用cache的场景、内存和负载等都会对cache命中率有消极作用。因此为了适应这种差异性,将会把一个集群的cache server拆分成不同的Pool。比如会对一些访问频率低但是cache miss代价很高的key分配large pool。
  8. 负载优化方案-Memcache Pools的多副本机制。对于并发访问key多,数据集不超出一两台cache server的容量范围但是请求数超过了单机处理能力的Pools,会将cache数据作replication。而主要的问题就在于如何报纸多副本的数据一致性。
  9. 负载优化方案-容错处理。对于小规模的cache访问失败(比如由于网络原因或者server宕机),引入了Gutter Pool机制。Gutter是一个小规模cache集群,大致占集群的1%机器。在第一次正常访问cache失败后,会继续访问Gutter,如果再次访问失败,将会把从DB读取到的数据填入到Gutter。Gutter Pool里面的数据过期时间较短,因此没有delete操作,带来的问题就是会读取短期的脏数据。而直接把key rehash到其他剩余存活机器的方法相比于Gutter Pool方式,会存在雪崩的风险。因为一些热门key被rehash会会增加当前机器的负载,可能会导致过载。而Gutter Pool一般负载较低,可以降低这种风险。

多集群场景-In a region

  1. Split web and memcached servers into multiple frontend clusters. These clusters, along with a storage cluster that contain the databases, define a region. 主要考虑的问题是如何在同一个region内部多个集群之间备份数据
  2. Regional Invalidations-在一个region内部会让storage cluster负责cache数据失效的功能。每个DB上会部署一个mcsqueal,负责从commit log里面提取出删除操作,然后发送到前端。mcsqueal并不是直接把删除操作广播到所有Cache Server,而是先转发到一些特定机器上的mcrouter,由mcrouter根据每个key转发到合适的Cache Server上,这是为了减少集群网络包的个数以及网络压力。而相比于直接由web server直接广播删除操作的方式,一来是可以更好地packet delete操作,二来是通过log的方式可以更方便的回放操作,这可以解决delete操作发送失败以及发错到其它cache Server的问题。此外还存在一个优化手段,一个web server修改数据后会往本集群的cache发送delete操作,这是为了能够给客户端提供一个read-after-write语义(即修改后需要读取新数据)以及减少脏数据在本地存活的时间。
  3. Regional Pools-如果落在前端的请求是随机转发,那么所有cache集群保存的key都基本一致,这种数据副本过多会造成内存的极大浪费。为了减少不必要的数据副本数,可以将多个前端集群共享一批cache Server的方式,这个称之为Regional Pools。数据备份是用更多的机器来换取更少的带宽使用、更少的延迟和更好的容错。而Regional Pools是希牺牲了数据备份的优势,在Regional Pools内部跨集群的通信延迟会变大,因此决定哪些key需要放到Regional Pools需要考虑这些因素:访问频率,数据大小和独立用户访问数,一般访问频率低、数据量小的数据会放到Regional Pools。
  4. Cold Cluster Warm Up-新加入的cache集群由于cache命中率较低,为了避免cache miss对后端DB压力过大,可以允许从有正常命中率的cache集群(Warm Cluster)读取数据.需要注意可能会出现读到脏数据的场景,这是因为delete操作没有及时同步到Warm Cluster,会出现从Warm Cluster读取到旧数据然后再写入到Cold Cluster。可以采取延迟删除的机制来解决,对Cold Cluster的delete操作会延迟2s后才真正删除,在此之间任何add操作都会失败。虽然2s这个时间理论上仍然存在读取到脏数据的可能,但是实际上在大多数情况下是可行的。当Cold Cluster cache命中率正常后,将会关闭填充这种填充cache机制。

多集群场景-Across Region

  1. 多个数据中心情况下会建立多个regions. 其中一个region会放置主DB,而其他region提供只读的replica,主从之间通过mysql的同步机制来同步数据。在跨集群的场景下面临的主要问题是如何解决由于主从同步延迟造成的数据不一致问题。
  2. 主从同步延迟主要是可能Server A已经往主库写入新数据了,但Server B由于cache miss由从库中读到的还是老数据,那么填入cache的就是脏数据,可以使用remote marker机制来解决cache和DB数据不一致问题。在需要更新DB数据之前,先根据key生成一个remote marker r(key)并更新cache region中,这是用来标明从库的数据是脏数据。然后再按照正常的逻辑更新DB数据。而在读取数据时如果出现cache miss,那么会先检查是否存在r(key),如果有则从主库读取数据,否则由从库读取数据。当从库同步完数据会由mcsqueal在cache region中删除r(key)。
  3. 这种remote marker机制会存在一种风险,当多个Web Server出现并发写同一个key的时候可能会导致r(key)被过早删除。按照论文中注明,这种冲突场景极少出现

单机优化

  1. 性能优化-允许内部使用的hashtable自动扩张(rehash)、由原先多线程下的全局单一的锁改进为更细粒度的锁以及每个线程一个UDP来避免竞争
  2. 内存优化-改进Slab Allocator,允许不同Slab Class互换内存。当发现要删除的item对应的Slab Class最近使用的频率超过平均的20%,将会把最近最少使用的Slab Class的内存交互给需要的Slab Class使用。整体思路类似一个全局的LRU。
  3. Transient Item Cache-某些key的过期时间会设置的较短,如果这些key已经过期但是还没达到LRU尾部时,它所占用的内存在这段时间就会浪费。因此可以把这些key单独放在一个由链表组成的环形缓冲(即相当于一个循环数组,数组的每个元素是个链表,以过期时间作为数组的下标),每隔1s,会将缓冲头部的数据给删除。
  4. 软件升级-memcache的数据是保存在System V的共享内存区域,方便机器上的软件升级。

 

ceph学习笔记--对象存储

ceph是一个支持大量小文件和随读写的分布式文件系统。笔者这两天读过ceph的论文,在这里总结一下它的设计要点。由于能力所限,加之信息来源主要是ceph的论文,部分细节脑补,对代码和实际部署并没有经验,如有纰漏烦请指教。

本文假设读者有一定分布式存储系统经验,至少了解hdfs+hbase和dynamo这两种模型,因为ceph用到的各种奇技淫巧在这些系统中都能找到影子。

Ceph分为对象存储(RADOS)和文件存储(MDS)两层。对象存储层是基础,提供可靠的K/V对存储服务。文件存储层则提供POSIX语义的目录和文件服务。本篇博文将主要介绍RADOS。


* 来自ceph作者论文

RADOS有以下特点:
– 高可用(不受限于单点或几台master)
– 轻量级master
– 支持海量小对象
– 强一致
– 并发写

数据分布(Placement)

先从数据分布说起。RADOS中的对象由对象池(pool)管理。每个池中的所有对象都有同样的副本份数,分布规则等,这些信息缓存在客户端中。用户在存取对象时需要指定池的名字。

从对象的key到最终存储数据的服务器要经过两层映射(存储节点称为OSD)。首先是经过一个哈希函数把key映射到Placement Group(简称PG)。PG类似其它系统中于虚拟分区的概念,一个PG存放多个对象,每个存储节点有上百个PG。

第二层是通过一致性哈希函数CRUSH从PGID映射到到实际存放数据的主机,对于给定PGID和副本数量,CRUSH会生成副本位置信息。其中第一个副本是主,其它为从。主副本负责接收来自客户端的写,产生日志同步给从副本。如果出现多个客户端并发写,主副本也扮演协调者决定并发写的顺序。

当少量机器发生宕机时,作为一致性哈希函数,CRUSH产生的PG副本的位置不会有很大改别。同时,缺失数据的其它副本散落在整个集群,这就保证了补齐副本数据时可以利用整个集群的网络带宽。

监控节点(Monitor)

除了存储节点外,还有一些监控节点组成小集群,负责监控存储节点的运行状态。多个监控节点通过Paxos协议达到一致和保持数据冗余。监控节点上只记录epoch序号和一些全局状态(如是存储节点否在线、地址端口等),可谓相当轻量。每当监测到存储节点发生变更时,如机器上线或下线,将epoch序号增加以区别先前的状态。所有存储节点的状态信息称为ClusterMap。

计算CRUSH时需要利用ClusterMap,因此它被缓存在客户端或者存储节点上(因为轻量),用epoch序号识别缓存的数据是否过期。系统中所有的通信都携带epoch序号,这样新产生的epoch序号就能快速扩散到整个集群。

存储节点(OSD)

存储节点真正响应用户的读写请求。假设三份副本,用户将写请求首先发送给主PG副本所在的存储节点上,称为A,而后A再将数据以日志的形式并行发送给从副本B和C。即用户写A,A同时写B和C。待B和C返回结果给A后,A才能最后告诉用户写成功。副本之间是强一致的。

当有存储节点发生宕机时,监控节点发现后更新epoch和ClusterMap,并将最新的ClusterMap推送给存储节点。宕机的发现和ClusterMap的推送都是通过gossip p2p的方式完成的。存储节点重新计算CRUSH。由于有机器宕机,有一些副本会丢失主副本,这时CRUSH重新产生的第一个副本就变成主副本。新的副本寻找旧副本要求复制数据。由地一致性哈希的特性,发生变更的PG不会很多。

考虑这样一个场景:CRUSH产生的新副本和旧副本完全没有重叠。当用户正在写一组旧副本,旧副本全然不知新副本的存在,岂不是会脑裂?解法是新副本在能服务前,一定需要找旧副本复制数据。还记得前文说到所有通信都携带epoch序号吗,这样旧副本就会意识到自己该停止服务了。

在PG上的所有写操作由””两部分组成,v在PG内递增。这样可以保证新PG上的写总是覆盖旧PG。

另一个相似的场景是读脏数据的问题:用户1读旧副本,同时用户2并发写新副本。解决之道是禁止这样的情况出现。同一PG组内的所有副本两两互发心跳维持租约,假设三副本,如果副本A一段时间未接到B或C发来的心跳,那么A就自己判断已经失去联系。新副本开始服务前,也要等足够时间使旧副本的租约失效。由于通信传播epoch号,旧副本或者发现自己的ClusterMap过期,或者被网络隔离就坐等租约失效,总是可以保证强一致。

可用性

RADOS的一个设计亮点就是采用一致性哈希、轻量级监控节点的同时又保证强一致。CAP理论说高可用和强一致两者不可兼得。这里讲的高可用,实际上是和HDFS NameNode这种重量级master相比的。一旦过半数监控节点宕机,即master不可用,所有存储节点仍然可以正常服务读写。如果此时再有一台存储节点宕机,也只会出现和它相关的PG不能服务(假设n台存储节点,3份副本,那么受影响的PG占总体的1/(n-2))。

RADOS和dynamo的区别在于在PG副本不完整的情况下,禁止客户端读写(允许读会读到脏数据),直到宕机被监控节点发现才行。由此可见,监控节点对存储节点宕机的快速感知是至关重要的。若想在万台规模下做到十秒以内感知,即使不采用p2p的方式,也需要在监控节点和存储节点之间增加一层代理。

工程难度

Ceph最初是一个实验室项目,它的作者Sage Wail在这上面发表过几篇论文。他几乎是凭藉一人之力实现了整套存储系统(包括单机存储系统、小对象存储、文件命名空间、块存储、FUSE和内核模块)。查看git历史会发现90%的代码都是这他写的。这样的项目即使放到公司,也足够几十号人忙几年。

具体而言,笔者个人以为RADOS有以下难点:
1. 监控节点需要实现Paxos才能高可用,不用说Paxos有多少坑,看HDFS这么多年才搞出来NN真正的高可用
2. 支持随机修改让副本复制变得非常复杂,需要处理边写边追的情况
3. 规模!07年的论文就在讲百PB级别的存储(笔者认为这是扯淡,07年的硬盘多大),特别是系统中使用p2p通知和存储节点自主复制,p2p的测试要比简单master-slave模型难得多(master-slave的难点在于master高可用)。想想亚马逊那次宕机事故吧

参考资料:
http://ceph.com/papers/weil-rados-pdsw07.pdf
http://ceph.com/papers/weil-thesis.pdf
http://ceph.com/papers/weil-crush-sc06.pdf
http://storageconference.org/2012/Presentations/T02.Weil.pdf