Cassandra And PNUTS--Two classic distributed system翁纯佳（浙江工业大学计算机科学与技术系，杭州，310023）Cassandra And PNUTS–两个经典的分布式系统WengChunJia(Zhejiang university of technology Computer science and technology department ,HangZhou,310023)AbstractCassandra is a distributed storage system for managing very large amounts of structured data spread out across many commodity servers, while providing highly available service with no single point of failure. Cassandra aims to run on top of an infrastructure of hundreds of nodes (possibly spread across different data centers). At this scale, small and large components fail continuously. The way Cassandra manages the persistent state in the face of these failures drives the reliability and scalability of the software systems relying on this service.We describe PNUTS, a massively parallel and geographically distributed database system for Yahoo!’s web applications. PNUTS provides data storage organized as hashed or ordered tables, low latency for large numbers of concurrent requests including updates and queries, and novel per-record consistency guarantees. It is a hosted, centrally managed, and geographically distributed service, and utilizes automated load-balancing and fail over to reduce operational complexity.Key words：Cassandra；distribute;storage system；PNUTS；automated load-balancing；fail over 摘要：Cassandra是一个分布式的存储系统,可用来管理分布在大量廉价服务器上的巨量结构化数据,并同时提供没有单点故障的高可用服务.Cassandra的设计目的是运行在由几百个节点(可能分布在多个不同的数据中心)组成的基础设施上.当节点达到这个规模时,大大小小的组件出现故障就可能经常发生了.Cassandra在管理持久状态时面临这些故障,这种情况也驱动软件系统的可靠性与可伸缩性会依赖于Cassandra的服务.PNUTS是一个Yahoo的网站应用的数据库系统，它并发量极大和分布在多个地域。

PNUTS在存储方面按哈希或有序表组织数据，大量并发地查询或更新响应时延很低，同时很有创意地为单条记录提供一致性保证。

它是一个自建的、集中管理并分布在多个地域的服务，通过负载均衡和故障自动切换来降低运营的复杂度。

关键词: Cassandra；分布式；存储系统；PNUTS；负载均衡；故障自动切换一．Cassandra1. 导论Facebook维护着世界上最大的社交网络平台,利用分布在世界各地的大量数据中心的成千上万台服务器,为上亿的用户提供服务.Facebook 平台有严格的业务要求,包含性能、可靠性、效率以及高度的可伸缩性以支持平台的持续增长.在一个包含成千上万的组件的基础设施上处理故障是我们的标准运作模式;在任何时候,随时都可能出现相当数量的服务器或网络组件故障.这样,软件系统在构建时就需要将故障当作一种常态而不是异常来处理.为了满足上面描述的这些可靠性与可伸缩性,Facebook开发了Cassandra系统.为了实现可伸缩性与可靠性,Cassandra组合了多项众所周知的技术.设计Cassandra的最初目的是解决收件箱搜索的存储需要.在 Facebook,这意味着这个系统需要能够处理非常大的写吞吐量,每天几十亿的写请求,随着用户数的规模而增长.由于我们是通过在地理上分布的数据中心对用户进行服务的,因此支持跨越多个数据中心的数据复制对于降低搜索延时就非常关键了.当Facebook在2008年6月发布收件箱搜索项目时,有1亿的用户, 现在差不多有2.5亿的用户,Cassandra一直保持了其对业务的承诺.目前,Facebook 内部已经有多个服务部署了Cassandra作为其后端存储系统.2. 相关研究对于为了性能、可用性与数据持久性对数据进行分布，文件系统与数据库社区已经进行了广泛的研究.与仅支持扁平命名空间的点对点(P2P)存储系统相比,分布式文件系统通常支持层次化的命名空间.与Ficus 与Coda类似的系统都是通过牺牲一致性来复制文件以实现高可用.通常使用特别的冲突解决程序来管理更新冲突.Farsite是一个没有使用任何中心服务器的分布式文件系统. Farsite使用复制来实现高可用性与可伸缩性.Google文件系统(GFS)是另一个分布式文件系统,用来存储Google内部应用的各种状态数据.GFS 设计比较简单,用一台主服务器存储所有的元数据,数据拆分成块存储在多个块服务器上.不过,目前Google 已经使用Chubby抽象层为GFS的主服务器做了容错处理.Bayou是一个分布式的关系数据库系统,它支持断开操作(个人理解为网络断开以后的操作)并提供最终的数据一致性.在这些系统中,Bayou、Coda与Ficus 允许断开操作，并且在遇到类似与网络断开与停机时能够做到自动复原.这些系统在冲突解决程序上存在差异.例如,Coda与Ficus执行系统级别的冲突解决,而Bayou允许应用级别的冲突解决.但所有这些都保证最终一致性.与这些系统类似,即使在网络段开的时候,Dynamo[6]也允许进行读写操作,并使用不同的冲突解决机制(部分客户端驱动) 来解决更新冲突.传统的基于复制的关系数据库系统重点在保证复制数据的强一致性.虽然强一致性为应用写程序提供了一个方便的编程模型,但是,这些系统在伸缩性与可用性方面却受到了限制.因为这些系统提供强一致性的保证,所以在网络分开时,它们就无法进行处理.Dynamo[6]是一个Amazon开发的存储系统,Amazon用它来存储检索用户的购物车.Dynamo利用基于Gossip的会员算法来维护每个节点上所有其他节点的信息.可以认为Dynamo是一个只支持一跳路由请求的结构化覆盖层.Dynamo使用一个向量时钟概要来发现更新冲突,但偏爱客户端的冲突解决机制.为了管理向量时间戳,Dynamo中的写操作同时也需要执行一次读操作.在一个需要处理非常大的写吞吐量的系统中,这可能会成为瓶颈. Bigtable[4]既提供了结构化也支持数据的分布式,不过它依赖于一个分布式的文件系统来保证数据的持久化.3. 数据模型Cassandra中的表是一个按照主键索引的分布式多维图.它的值是一个高度结构化的对象.表中的记录键是一个没有大小限制的字符串,虽然它通常都只有16-36个字节的长度.无论需要读写多少列,单一记录键的每个副本的每次操作都是一个原子操作.多个列可以组合在一起形成一个称为column family的列的集合,这一点与Bigtable系统非常相似.Cassandra提供两种类型的column family,简单的column family与超级的column family.可以将超级column family想象成column family里面嵌入column family.进一步,应用还可以指定超级column family或者简单column family里面的列的排序顺序.系统允许按时间或者名称对列进行排序.按照时间对列进行排序可以被类似于收件箱搜索这样的应用使用,因为它们的结果始终需要按照时间顺序进行展示.column family中的每个列都需要通过规范column family : column来进行访问,每个超级column family中的列都通过规范column family : super column : column来进行访问.小节6.1给出了一个展示超级column family抽象能力的非常好的例子.通常,应用都会使用一个独占的Cassandra集群,并将它们当作服务的一部分进行管理.虽然,Cassandra系统支持多表的概念,在部署时每个概要中都只能有一个表.4. 系统架构一个需要在生产环境运转的存储系统的架构是很复杂的.除了真实的数据持久化组件外,这个系统还需要包含以下特性;可伸缩性与强大负载均衡解决方案、会员与故障检测、故障恢复、副本同步、超负荷处理、状态转移、并发与任务调度、请求编组、请求路由、系统监控与报警以及配置管理.详细描述这里的每一个解决方案超出了本论文的范围,我们将集中介绍Cassandra使用的核心的分布式系统技术:分区、复制、会员、故障处理以及伸缩性.处理读写请求需要所有这些模块的协同处理.通常,一个键的请求可能被路由到Cassandra集群的任何一个节点去处理.这个节点会确定这个特定的键的副本.对于写操作来讲,系统会将请求路由到副本上,并且等待仲裁数量的副本以确认写操作完成.对于读操作来讲,基于客户端要求的一致性保证,系统要么将请求路由到最近的副本,要么将请求路由到所有的副本并等待达到仲裁数量的响应.4.1 分区.增量扩展的能力是我们设计Cassandra时考虑的一个关键特性.它要求做到在集群中的一组节点之间动态的对数据进行分区.Cassandra使用一致性散列(consistent hash)技术在整个集群上对数据进行分区,但是使用一种保证顺序的散列函数来实现.在一致性散列中,散列函数的输出结果区间可以看作是一个封闭的圆形空间或者”环”(例如,最大的散列值回绕到最小的散列值).为系统中的每个节点分配这个空间上的一个随机值,代表它在这个环上的位置.每个数据项都会根据它的键被指派给一个节点,通过对这个数据项的键做散列计算,获得它在环上的位置,然后按照顺时针找到比它的位置大的第一个节点.这个节点就被认为是这个键的协调器.应用指定这个键,Cassandra利用它来对请求做路由.这样,每个节点都会负责环上的一个区间-节点与它在环上的前一个节点(逆时针)之间的区间.一致性散列的主要优势是增加或删除节点只会影响到它的近邻,其他的节点都不会受影响.基本的一致性散列算法还面临一些挑战.首先,在环上随机的为每个节点指定位置可能导致数据与负载的分布不均衡.其次,基本的一致性算法会抹杀节点之间性能的异质性(差异).解决这个问题一般有两种方法:一种方法是在环上为节点指定多个位置(Dynamo采用的方法),另一种方法是分析环上的负载信息,并移动负载较低的节点的位置以缓解负载过重的节点,引文对此有详细描述.Cassandra选择了后者,因为使用它可以简化设计与实现,并且可以让负载均衡的选择更加具有确定性.4.2 复制Cassandra使用复制来实现高可用性与持久性.每个数据项都会被复制到N台主机,N是通过参数”per-instance”配置的复制因子. 每个键(k)都被指派给一个协调节点(上一节介绍的).由协调节点负责复制落在这个节点范围的数据项的复制.除了将本节点范围内的数据存储到本地外,协调器需要将这些键复制到环上的其他N-1个节点.关于如何复制数据,Cassandra为客户端提供了多个选项.另外,Cassandra还提供了多种不同的复制策略,例如”机架不可知”、”机架可知”(同一个数据中心内)与”数据中心可知”.应用选择的复制策略决定了副本的数量.使用”机架可知”与”数据中心可知”复制策略时复制的算法要稍微复杂一点.Cassandra使用一个称为Zookeeper[13]的系统在这些节点中选择一个引导者.所有节点在加入集群时都需要与此引导者联系,并由引导者告知它们负责哪个环上哪个范围的副本,引导者还需保持协调一致的努力来保持不变,以确保没有哪个节点负责环上的超过N-1个范围.关于一个节点负责的范围的元数据信息都会在每个节点做本地缓存,并在Zookeeper内做容错处理,这样当一个节点崩溃并返回的时候就可以知道它到底负责哪个范围.借用Dynamo的措辞,我们认为负责一个给定范围的节点是这个范围的”优选清单”.4.3 会员Cassandra中的集群会员是基于Scuttlebutt[19]的,一个非常高效的反熵闲话机制. Scuttlebutt的突出的特点是它非常高效的CPU利用率以及非常高效的Gossip通道利用率.在Cassandra中,系统Gossip 不止用来管理会员信息,也用来传输其他系统相关的控制状态.4.4 引导程序当一个节点第一次启动的时候,它会随机的选择一个令牌作为它在环上的位置.为了容错的需要,映射关系会被持久化到本地磁盘以及 Zookeeper中.接着令牌信息会被传播到整个集群.我们就是通过它来知道集群中的所有节点以及它们在环上的位置的.通过它,任何一个节点都可以将一个键的请求路由到集群中的合适的节点.在引导过程中,当一个新的节点需要加入集群时,它需要读取它的配置文件,配置文件中包含集群中的几个联络点名单.我们将这些联络点称为集群的种子.种子也可以来自一个类似于Zookeeper的配置服务.4.5 集群的扩展当有一个新节点加入系统时,它会被分配一个令牌,这样就可以缓解负载过重的节点的负载.这样导致的结果是,这个新的节点会分担部分先前由其他节点负责的范围.Cassandra的引导算法可由系统中的任何其他节点通过命令行工具或Cassandra的网络仪表盘来启动.放弃这部分数据的节点通过内核到内核的拷贝技术将数据拷贝到新的节点.我们的运维经验显示,从单个节点传输的速率可以达到 40MB/s.我们还在努力对它进行改善,通过让多个副本来参与并行化引导传输,类似于Bittorrent技术.二．PNUTS1.简介我们把PNUTS打造成一个超级规模、托管的数据库系统，来支持Yahoo!的网站应用。