对照实验系统论文阅读笔记(二)

这一次我们阅读和翻译关于分层实验平台的来自Google的论文Overlapping experiment infrastructure: more, better, faster experimentation (没有找到特别官方的链接,学术搜索能搜到)。

 

Google也大量需要在线的对照实验来做决策,几乎所有的微小的改变,都需要通过实验决定。相比众多的实验,流量的数量已经成为了瓶颈。为了更高效、更准确地做更多的实验,这篇文章设计了分层实验平台。同一份流量可以同时做多个实验。

 

更多、更好、更快

 

实验平台不仅能同时运行多个实验,也要具有灵活性:不同的实验可以使用不同的配置、不同的流量大小。不正确的实验不应当被允许运行,正确但影响很差的实验应当被迅速发现并中止。实验的设置和进行应当容易并迅速,即使不是工程师也可以做(不需要写代码)。实验指标应当实时可用,这样实验就可以被迅速评估。简单的重复实验应当很容易做,最理想情况下,实验平台可以用做灰度发布(gradually ramping up)。

 

发展到这一步,不仅需要工程上的架构设计,也需要相应的工具和对使用流程的控制。

 

背景

 

这里说的分层实验平台只用在Web互联网服务上,不包括Google Apps、Chrome等(我们可以想象一下,实际上,非Web服务也可以做对照实验,但是如果要做重叠的实验则有一定的困难)。

 

与之前在(一)中提到的对照实验系统一样,做对照实验完全由参数来控制。使用参数使得实验容易创建,因为他们可以是易读的文字,不是代码。同样,数据文件比程序文件更容易快速部署。

 

在最初,Google使用了一种可以称作“单层实验平台”的架构。一个流量只能做一个实验。首先分配基于Cookie划分流量的实验,然后再划分基于随机分配流量的实验。这种架构不足以支持足够多的实验。

 

分层架构

 

layer

 

我们将参数划分为若干个子集,每个子集之内的参数是可能互相影响的,也就是说不能同时做实验的;子集之间的参数则是不会互相影响的(正交的)。这种划分可以来自于检查,也可以来自于过往实验的结果。用每一个子集对应一个抽象的“层”的概念。同时,把对流量的每一个划分抽取对应一个抽象的“领域”(domain)的概念。一个领域里可以有多层,一个层里也可以有多个领域。如图。而这个图也可以看做最宏观上Google Web的层和领域的划分。

 

虽然看起来有点复杂,但这个划分有很多好处。一个非重叠实验领域,可以方便地做影响非常大的实验(可能实验的参数跨遍各层,只能在这个领域做);它允许在两个领域中对相同的参数做不同的划分;我们也可以比较容易地把一个参数从一层中移到另一层中(如果发现这样更有利于流量的利用)。

 

注意到图(c)中增加了发布层Lanuch Layer。Lanuch Layer是一种特殊的层,它们必须运行着100%的流量(它们所在的领域称default domain,不能与其他domain纵向切分),同一个参数最多出现在一个Launch层中,同时最多出现在一个普通层中。Launch中参数的取值,可以被下面普通实验层中进行的实验的参数取值所覆盖。

 

发布层的典型应用是,每一个待发布的参数版本,新建一个发布层,而当它稳定后,删掉这个发布层。由于发布层在default domain中,因此它可以用来最终验证实验间的相互影响。

流量的划分不仅有基于cookie、random的,也会根据实验的要求有更灵活的其他方式,比如userid,query-string等。而不同的划分方式可能会在领域与层之间造成饥饿和有偏的问

题,为此,需要给每个领域和层指定流量划分方式,对已经被上层抽取造成的有偏的流量要加以标识,排除掉它们以避免有偏。

 

分层实验框架的工程架构基本就是如此,而这篇论文的后半部分还用了很大的篇幅讨论前面说到的”工具和使用流程控制”,我们在下一篇阅读笔记中讨论。

 

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高可用)。想想亚马逊那次宕机事故吧

参考资料:

Click to access weil-rados-pdsw07.pdf

Click to access weil-thesis.pdf

Click to access weil-crush-sc06.pdf

Click to access T02.Weil.pdf