CONAN ZONE

本文翻译自Facebook员工在LADIS大会上发布的论文.Cassandra – A Decentralized Structured Storage System
这篇论文中,两位作者详细介绍了 Cassandra的系统架构,它的设计初衷,设计应用时使用到的相关技术,以及设计/实现/使用过程中得到的经验教训.

Cassandra – 一个分散的非结构化存储系统
By Avinash Lakshman Facebook ,Prashant Malik Facebook; Translated ByJametong

概要

Cassandra 是一个分布式的存储系统,可用来管理分布在大量廉价服务器上的巨量结构化数据,并同时提供没有单点故障的高可用服务.Cassandra的设计目的是运行 在由几百个节点(可能分布在多个不同的数据中心)组成的基础设施(infrastructure)上.当节点达到这个规模时,大大小小的组件出现故障就可 能经常发生了.Cassandra在管理持久状态时面临这些故障,这种情况也驱动软件系统的可靠性(reliability)与可伸缩性 (scalability)会依赖于Cassandra的服务.虽然大部分情况,Cassandra看上去像一个数据库系统, 也与数据库系统共享大量的设计与实现手段,但是Cassandra并不支持完整的关系数据模型;相反,它提供了一个简单数据模型的客户端,支持对数据布局 与数据格式的动态控制.我们设计Cassandra的初衷是,可以运行在廉价硬件上,并能在不牺牲读效率的情况下实现高的写吞吐量.

1. 导论

Facebook维护着世界上最大的社交网络平台,利用分布在世界各地的大量数据中心的成千上万台服务器,为上亿 的用户提供服务.Facebook平台有严格的业务要求,包含性能、可靠性、效率以及高度的可伸缩性以支持平台的持续增长.在一个包含成千上万的组件的基 础设施上处理故障是我们的标准运作模式;在任何时候,随时都可能出现相当数量的服务器或网络组件故障.这样,软件系统在构建时就需要将故障当作一种常态而 不是异常来处理.为了满足上面描述的这些可靠性与可伸缩性,Facebook开发了Cassandra系统.
为了实现可伸缩性与可靠 性,Cassandra组合了多项众所周知的技术.我们设计Cassandra的最初目的是解决收件箱搜索的存储需要.在Facebook,这意味着这个 系统需要能够处理非常大的写吞吐量,每天几十亿的写请求,随着用户数的规模而增长.由于我们是通过在地理上分布的数据中心对用户进行服务的,因此支持跨越 多个数据中心的数据复制对于降低搜索延时就非常关键了.当我们在2008年6月发布收件箱搜索项目时,我们有1亿的用户,现在我们差不多有2.5亿的用 户,Cassandra一直保持了其对业务的承诺.目前,Facebook内部已经有多个服务部署了Cassandra作为其后端存储系统.
本文 的结构如下.第2节讨论相关研究,其中的部分研究对我们的设计有很大影响.第3节介绍详细的数据模型.第4节简要介绍客户端API.第5节介绍系统设计以 及Cassandra中应用到的分布式算法.第6节介绍我们如何使用Cassandra部署Facebook平台的一个应用.

2. 相关研究

对于为了性能、可用性与数据持久性对数据进行分布，文件系统与数据库社区已经进行了广泛的研究.与仅支持扁平 命名空间(namespace)的点对点(P2P)存储系统相比,分布式文件系统通常支持层次化(hierarchical)的命名空间.与 Ficus[14]与Coda[16]类似的系统都是通过牺牲一致性来复制文件以实现高可用(high availability).通常使用特别的冲突解决(conflict resolution)程序来管理更新冲突(update conflict). Farsite[2]是一个没有使用任何中心服务器的分布式文件系统. Farsite使用复制来实现高可用性与可伸缩性.Google文件系统(GFS)[9]是另一个分布式文件系统,用来存储Google内部应用的各种状 态数据.GFS设计比较简单,用一台主服务器存储所有的元数据(metadata),数据拆分成块(chunk)存储在多个块服务器(chunk server)上.不过,目前Google已经使用Chubby[3]抽象层为GFS的主服务器做了容错处理(fault tolerant).Bayou[18]是一个分布式的关系数据库系统,它支持断开操作(个人理解为网络断开以后的操作)并提供最终的数据一致性 (eventual data consistency).在这些系统中,Bayou、Coda与Ficus允许断开操作，并且在遇到类似与网络断开与停机时能够做到自动复原.这些系统 在冲突解决程序上存在差异.例如,Coda与Ficus执行系统级别的冲突解决,而Bayou允许应用级别的冲突解决.但所有这些都保证最终一致性 (eventual consistency).与这些系统类似,即使在网络段开的时候,Dynamo[6]也允许进行读写操作,并使用不同的冲突解决机制(部分客户端驱动) 来解决更新冲突.传统的基于复制的关系数据库系统重点在保证复制数据的强一致性(strong consistency).虽然强一致性为应用写程序提供了一个方便的编程模型,但是,这些系统在伸缩性与可用性方面却受到了限制.因为这些系统提供强一 致性的保证,所以在网络分开时,它们就无法进行处理.
Dynamo[6]是一个Amazon开发的存储系统,Amazon用它来存储检索用户的购 物车.Dynamo利用基于Gossip的会员算法来维护每个节点上所有其他节点的信息.可以认为Dynamo是一个只支持一跳路由请求(one-hop request routing)的结构化覆盖层(structured overlay).Dynamo使用一个向量时钟(vector lock)概要来发现更新冲突,但偏爱客户端的冲突解决机制.为了管理向量时间戳(vector timestamp),Dynamo中的写操作同时也需要执行一次读操作.在一个需要处理非常大的写吞吐量的系统中,这可能会成为瓶颈. Bigtable[4]既提供了结构化也支持数据的分布式,不过它依赖于一个分布式的文件系统来保证数据的持久化.

3. 数据模型

Cassandra中的表是一个按照主键索引的分布式多维图.它的值是一个高度结构化的对象.表中的记录键是一 个没有大小限制的字符串,虽然它通常都只有16-36个字节的长度.无论需要读写多少列,单一记录键的每个副本的每次操作都是一个原子操作.多个列可以组 合在一起形成一个称为column family的列的集合,这一点与Bigtable[4]系统非常相似.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. API

Cassandra 的API由下面三种方法组成.

• insert(table, key, rowMutation)
• get(table, key, columnName)
• delete(table, key, columnName) 列名可以是column family里面的一个特定列,或column family,或超级column family,或超级列里面的一个列

5. 系统架构
一个需要在生产环境运转的存储系统的架构是很复杂的.除了真实的数据持久化组件外,这个系统还需要包含以下特性;可 伸缩性与强大负载均衡解决方案、会员与故障检测、故障恢复、副本同步、超负荷处理、状态转移、并发与任务调度、请求编组、请求路由、系统监控与报警以及配 置管理.详细描述这里的每一个解决方案超出了本论文的范围,我们将集中介绍Cassandra使用的核心的分布式系统技术:分区、复制、会员、故障处理以 及伸缩性.处理读写请求需要所有这些模块的协同处理.通常,一个键的请求可能被路由到Cassandra集群的任何一个节点去处理.这个节点会确定这个特 定的键的副本.对于写操作来讲,系统会将请求路由到副本上,并且等待仲裁数量的副本以确认写操作完成.对于读操作来讲,基于客户端要求的一致性保证,系统 要么将请求路由到最近的副本,要么将请求路由到所有的副本并等待达到仲裁数量的响应.

5.1 分区.

增 量扩展的能力是我们设计Cassandra时考虑的一个关键特性.它要求做到在集群中的一组节点(Node)之间动态的对数据进行分 区.Cassandra使用一致性散列(consistent hash[11])技术在整个集群上对数据进行分区,但是使用一种保证顺序(order preserving)的散列函数来实现.在一致性散列中,散列函数的输出结果区间可以看作是一个封闭的圆形空间或者”环”(例如,最大的散列值回绕到最 小的散列值).为系统中的每个节点分配这个空间上的一个随机值,代表它在这个环上的位置.每个数据项都会根据它的键被指派给一个节点,通过对这个数据项的 键做散列计算,获得它在环上的位置,然后按照顺时针找到比它的位置大的第一个节点.这个节点就被认为是这个键的协调器.应用指定这个 键,Cassandra利用它来对请求做路由.这样,每个节点都会负责环上的一个区间-节点与它在环上的前一个节点(逆时针)之间的区间.一致性散列的主 要优势是增加或删除节点只会影响到它的近邻,其他的节点都不会受影响.基本的一致性散列算法还面临一些挑战.首先,在环上随机的为每个节点指定位置可能导 致数据与负载的分布不均衡.其次,基本的一致性算法会抹杀节点之间性能的异质性(差异).解决这个问题一般有两种方法:一种方法是在环上为节点指定多个位 置(Dynamo采用的方法),另一种方法是分析环上的负载信息,并移动负载较低的节点的位置以缓解负载过重的节点,引文[17]对此有详细描 述.Cassandra选择了后者,因为使用它可以简化设计与实现,并且可以让负载均衡的选择更加具有确定性.

5.2 复制

Cassandra使用复制来实现高可用性与持久性.每个数据项都会被复制到N台主机,N是通过参数”per- instance”配置的复制因子.每个键(k)都被指派给一个协调节点(上一节介绍的).由协调节点负责复制落在这个节点范围的数据项的复制.除了将本 节点范围内的数据存储到本地外,协调器需要将这些键复制到环上的其他N-1个节点.关于如何复制数据,Cassandra为客户端提供了多个选项.另 外,Cassandra还提供了多种不同的复制策略,例如”机架不可知”(rack unaware)、”机架可知”(rack aware)(同一个数据中心内)与”数据中心可知”(data-center aware).应用选择的复制策略决定了副本的数量.使用”机架可知”与”数据中心可知”复制策略时复制的算法要稍微复杂一点.Cassandra使用一 个称为Zookeeper[13]的系统在这些节点中选择一个引导者(leader).所有节点在加入集群时都需要与此引导者联系,并由引导者告知它们负 责哪个环上哪个范围的副本,引导者还需保持协调一致的努力来保持不变,以确保没有哪个节点负责环上的超过N-1个范围.关于一个节点负责的范围的元数据 (metadata)信息都会在每个节点做本地缓存,并在Zookeeper内做容错处理,这样当一个节点崩溃并返回的时候就可以知道它到底负责哪个范 围.借用Dynamo的措辞,我们认为负责一个给定范围的节点是这个范围的”优选清单”.

5.1节已经介绍了每个节点都知悉系统中的所有其 他节点,以及它们各自负责的范围.通过放宽5.2节介绍的仲裁数(quorum)的要求,即使在出现节点故障与网络分区的情况下,Cassandra也可 以保证持久性.在断电、冷却故障、网络故障或自然灾害时，数据中心也会发生故障.可以配置Cassandra使得每条记录都被复制到多个不同的数据中心. 实际上,可以这样构建一个键的偏好列表,以实现键的存储节点分布在多个数据中心.这些数据中心都是通过高速网络进行互联.即使整个数据中心出现故障,这种 跨越多个数据中心的复制架构允许我们做到不宕机.

5.3 会员

Cassandra中的集 群会员是基于Scuttlebutt[19]的,一个非常高效的反熵闲话(anti-entropy Gossip)机制. Scuttlebutt的突出的特点是它非常高效的CPU利用率以及非常高效的Gossip通道利用率.在Cassandra中,系统Gossip不止用 来管理会员信息,也用来传输其他系统相关的控制状态.

5.3.1 故障检测

故障检测是这 样一种机制,通过它一个节点在本地就可以确定系统中的任一其他节点是活着还是死了.在Cassandra中,故障检测还被用来避免在多个操作中与不可达节 点的进行通讯.Cassandra使用的是Φ Accrual故障检测器[8]的一个改进版本. Accrual故障检测器的设计思路是,故障检测模块并不是产生一个布尔值来标记一个节点是活着还是死了.相反,故障检测模块为每个被监控节点产生一个代 表其怀疑级别的数值.此值被定义为Φ.其基本的思路是用Φ的值来表示一个范围,可以动态对其进行调整以反映监控节点上的网络与负载情况.
Φ有以下 几种涵义:给定部分阈值Φ,并假定当Φ=1时我们就决定怀疑一个节点A,我们犯错误(例如,这个决定在将来可能由于心跳接收延迟而被证明是错误的)的概率 为10%.Φ=2时出错的概率大约为1%,Φ=3大约为0.1%,等等.系统中的每个节点都会维护一个滑动窗口,来表示集群中其他节点的gossip信息 的到达间隔时间.确定了这些到达间隔时间的分布后,就可以计算出Φ的值了.虽然原论文认为这个分布近似于高斯分布(Gaussian distribution),由于gossip通道的本性以及他对延时(latency)的影响,我们认为它与指数分布(Exponential Distribution)更加相似.据我们所知,我们实现的Accrual故障检测在基于Gossip的配置中还属首创. Accrual故障检测器在准确性与速度上表现都非常好, 它们也能很好的适应不同的网络环境或服务器负载环境.

5.4 引导程序

当一个节点第一次启动的时候,它会随机的选择一个令牌(token)作为它在环上的位置.为了容错的需要,映射 关系会被持久化到本地磁盘以及Zookeeper中.接着令牌信息会被传播到整个集群.我们就是通过它来知道集群中的所有节点以及它们在环上的位置的.通 过它,任何一个节点都可以将一个键(key)的请求路由到集群中的合适的节点.在引导过程中,当一个新的节点需要加入集群时,它需要读取它的配置文件,配 置文件中包含集群中的几个联络点名单.我们将这些联络点称为集群的种子(seed).种子也可以来自一个类似于Zookeeper的配置服务 (configuration service).
在Facebook的环境中,节点停机时间(由于故障或维护任务)通常都很短暂,但有时也会延 长一段时间.故障可能有多种形式,如磁盘故障、CPU损坏等.节点停机很少不表示永远离开(删除节点),因此,不该导致分区指派的重新平衡或不可达副本的 修复.类似地,手工错误可能会导致意外地启动新的Cassandra节点.为了避免出现这种效果,所有消息中都包含了每个Cassandra实例集群名 称.如果配置中的手工错误导致一个节点尝试加入一个错误的Cassandra实例,就可以根据集群名称来阻止它.由于上述原因,使用一种明确的机制来往 Cassandra实例中添加或从中删除节点或许更加合适.管理员使用命令行(command line)工具或者浏览器登陆到Cassandra的节点,提出一个会员变更(节点变更)来加入或离开集群.

5.5 集群的扩展

当有一个新节点加入系统时,它会被分配一个令牌,这样就可以缓解负载过重的节点的负载.这样导致的结果是,这 个新的节点会分担部分先前由其他节点负责的范围.Cassandra的引导算法可由系统中的任何其他节点通过命令行工具或Cassandra的网络仪表盘 (web dashboard)来启动.放弃这部分数据的节点通过内核到内核的拷贝技术将数据拷贝到新的节点.我们的运维经验显示,从单个节点传输的速率可以达到 40MB/s.我们还在努力对它进行改善,通过让多个副本来参与并行化引导传输,类似于Bittorrent技术.

5.6 本地持久化

Cassandra系统要依赖于本地文件系统做数据的持久化.这些数据是以一种易于高效检索的格式存储在磁 盘上.通常,一次写操作会涉及提交日志(Commit Log,为了数据耐用性与可恢复性)写入,以及一次内存数据结构的更新.只有在写入提交日志成功返回后,才会执行内存数据结构的写入操作.在每台主机上, 我们都单独地分配了一块磁盘存放提交日志.由于提交日志地所有写入操作都是连续的(sequential),所以我们可以最大程度的利用磁盘吞吐量.当内 存数据结构的大小(根据数据量大小与对象数量计算得出)超过一定的阈值,它就会将自身转储到磁盘.这个写操作会机器配备大量的廉价磁盘的某一个上执行.所 有到磁盘的写操作都是顺序写.随着时间的推移,磁盘上就会存在多个这样的文件,后台会有一个合并进程(merge process)将这些文件合并成一个文件.这个进程与Bigtable系统中的压缩进程(compact process)非常类似.
通常,一 个读操作在检索磁盘文件之前会先查询这个内存数据结构.检索磁盘文件是按照先新后旧的方式进行的.当发生磁盘检索时,我们可能需要查看多个磁盘文件.为了 避免查看不包含相应键(key)的文件,我们使用了布隆过滤器(bloom filter),它对文件中的键进行了汇总,它同时存在于每一个数据文件中并常驻在内存中.当需要检索某个键时,会先查阅此布隆过滤器以确认给定的文件是 否确实包含此键.column family中的一个键可以包含大量的列.当检索的列距离键较远时还需要利用一些特殊的索引.为了避免在磁盘上扫描每一列,我们维护了一份列索引来帮助我 们直接定位到磁盘上的对应块.由于指定键的列已经被序列化并写出到磁盘,我们是按照每个块(chunk)256K的范围创建索引的.块的范围大小是可配置 的,不过,我们发现256K的大小在我们的生产工作负载下运作良好.

5.7 实现细节

单 台机器上的Cassandra进程主要由以下模块组成:分区模块、集群会员管理模块、故障检测模块与存储引擎模块.所有这些模块都依赖于一个事件驱动的底 层模块,它是按照SEDA[20]架构设计的,将消息处理管道与任务管道切分成了多个阶段.所有这些模块都是完全利用Java实现.集群会员模块与故障检 测模块都建立在使用非堵塞IO的网络层上.所有的系统控制信息都依赖于基于UDP协议的消息传输,而复制与请求路由等应用相关的消息则依赖于TCP协议传 输.请求路由模块的实现使用了一个固定的状态机.当集群的任一节点收到一个读/写请求时,状态机都会在以下几种状态之间切换: (i)定位拥有这个键的数据的节点(ii)将请求路由到此节点并等待响应到达(iii)如果答复没有在配置的超时时间内到达,就将此请求置为失败并返回给 客户端(iv)根据时间戳算出最新的答复(v)为任何数据不是最新的副本的安排数据修复.出于论述起见,详细的故障情况我们就不在此讨论了.这个系统的复 制模式可以配置为同步写(synchronous write)也可以配置为异步写(asynchronous write).对于特定的需要高吞吐量的系统,我们会选择依赖于异步复制.这时,系统接收到的写操作远远超过读操作.对于使用同步的例子,在返回给用户之 前我们会等待达到仲裁的响应数量.
在任何日志文件系统中,都需要有一个机制来清理提交日志项(commit log entry), 在Cassandra中,我们使用一种滚动的提交日志,在一个旧的提交日志超过一个特定的可配置大小后,就推出一个新的提交日志.在我们的生产环境中,我 们发现128M的滚动提交日志运作良好. 每个提交日志都有一个头信息,基本上是一个大小固定的位向量,其大小通常超过一个系统可能处理的column family的个数.在我们的实现中,对于每个column family,我们都会生成一个内存数据结构以及一个数据文件.每当一个特定的column family的内存数据结构转储到磁盘,我们都会在提交日志中记录它对应的位,说明这个column family已经被成功地持久化到磁盘.这表明这部分信息已经提交了.每个提交日志都有一份对应的位向量,这些位向量的信息同时也在内存中进行维护.每当 发生提交日志滚动的时候,它的位向量,以及它之前滚动的提交日志的位向量都会被检查一下.如果确定所有的数据都已经被成功地持久化到磁盘,就删除这些提交 日志.到提交日志的写操作可以是普通模式(normal mode)也可以是快速同步模式(fast sync mode).在快速同步模式下,到提交日志的写操作会被缓冲(buffered).这表明在机器崩溃时可能会出现潜在的数据丢失.在这种模式下,内存数据 结构转储到磁盘也会被缓冲.传统的数据库通常都不会被设计用来处理特别高的写入吞吐量.Cassandra将所有的写入操作都转换成顺序写操作以最大限度 地利用磁盘的写入吞吐量.由于转储到磁盘的文件不再会被修改,从而在读取它们的时候也不需要持有任何锁.Cassandra的服务实例的读写操作实际上都 是无锁操作.所以,我们并不需要应付基于B-Tree的数据库实现中存在的并发问题.
Cassandra系统通过主键来来索引所有数据.磁盘上的 数据文件被分解成一系列的块.每个块内最多包含128个键,并通过一个块索引来区分.块索引抓取块内的键的相对偏移量以及其数据大小.当内存数据结构被转 储到磁盘时,系统会为其生成一个索引,它的偏移量会被写当作索引写到磁盘上.内存中也会维护一份这个索引以提供快速访问.一个典型的读操作总是会先检索内 存数据结构.如果找到就将数据返回给应用程序,因为内存数据结构中包含任何键的最新数据.如果没有找到,那么我们就需要对所有磁盘数据文件按照时间逆序来 执行磁盘IO.由于总是寻求最新的数据,我们就先查阅最新的文件,一旦找到数据就返回.随着时间的推移,磁盘上的数据文件数量会出现增加.我们会运行一个 非常类似于Bigtable系统的压缩进程,通过它将多个文件压缩成一个文件.基本上是对很多排序好的数据文件进行合并排序.系统总是会压缩大小彼此接近 的文件,例如,永远不会出现一个100GB的文件与另一个小于50GB的文件进行合并的情形.每隔一段时间,就会运行一个主压缩程序来将所有相关的数据文 件压缩成一个大文件.这个压缩进程是一个磁盘IO密集型的操作.需要对此做大量的优化以做到不影响后续的读请求.

6. 实践经验

在设计、实现以及维护Cassandra的过程中,我们积累了不少有益的经验,也获得了许多经验教训.一个非常 基本的经验教训是,在没有理解应用的使用效果之前不要增加任何新特性.最成问题的情况不仅仅来自节点崩溃与网络分区.我们将在此分享几个有趣的场景.

• 在 发布收件箱搜索应用之前,我们必须先为超过1亿用户的7TB的收件箱数据创建索引,接着将它们存储到我们的MySQL[1]基础结构中,然后再将它们加载 到Cassandra系统中.整个处理过程涉及到在MySQL数据文件上运行Map/Reduce[7]任务,为它们创建索引,并按照逆序索引的方式将它 们存储到Cassandra中.实际上,M/R进程是作为Cassandra的客户端运行的.我们为M/R进程开放了后端通道,使它们可以按用户汇总逆序 索引,并将序列化后的数据传输给Cassandra实例,以节省序列化/反序列化的开销.这样,Cassandra实例的瓶颈就只剩下网络带宽了.
• 大 部分应用都是只需要每个键的每个副本的原子操作.不过,还是有部分应用需要交易支持,它的主要目的是维护辅助索引.大部分有着多年RDBMS相关开发经验 的开发人员都认为这个特性很有用.我们正在研究开放此类原子操作的机制.
• 我们尝试实现了多种故障检测器,包含[15]与[5]中所描述 的故障检测器.我们得到的经验是,随着集群规模的增长,检测到故障的时间也会出现增长,超出了我们的接受限度.在一个特定的包含100个节点的实验中,检 测一个故障节点竟然耗费大约2分钟的时间.在我们的环境中,这实际上是不可接受的.利用accrual故障检测器并设置一个稍显保守的PHI(Φ)值(设 置为5),在上面的实验中检测到故障的平均时间大约为15秒.
• 不要对监控想当然.Cassandra系统与Ganglia[12]做了 很好的集成,Ganglia是一个分布式的性能监控工具.我们向Ganglia开放了各种系统级别的指标,在Cassandra部署到我们的生产环境时, 这一点帮助我们更深的理解了这个系统的行为.磁盘会无缘无故地出现故障.当磁盘出现故障时,引导算法中有多个异常分支(hook)来修复这个节点.但是, 这实际上是一个管理操作.
• 虽然Cassandra是一个完全分散地系统,我们了解到,为了使一些分布式特性的实现更加可控,支持一定数 量的协调操作还是非常必要的.我们打算对部分关键特性使用Zookeeper抽象,这些特性实际上与使用Cassandra作为存储引擎的应用关系不大.

6.1 Facebook的收件箱搜索

对于收件箱搜索,我们为每个用户维护了一份所有消息的索引,这些消息包含用户作为发送者 的消息也包含其作为接收者的消息.目前启用了两种类型的索引(a)术语搜索(b)互动搜索,根据与此用户给定互动的人的名称返回用户发送给此人以及从此人 处接收的所有消息.这个概要(schema)包含两个column family,对于查询(a),用user id作为键(key),以构成消息的单词作为超级列(super column).对于查询(b),user id仍然是键(key),接收者的id都是super column.对于这些super column中的每一个,单个消息的识别符都是列.为了实现快速检索,Cassandra为数据的智能缓存提供了特定的钩子(hook)代码.例如,当用 户点击到搜索栏时,会有一条异步消息发送给Cassandra集群,再通过用户索引在高速缓存(buffer cache)中准备好该用户的数据.这样,当实际的搜索查询请求到达时,搜索结果很可能已经在内存中了.目前,这个系统在150个节点的集群上存储了大约 50多TB的数据,这些节点分布在美国东西海岸的多个数据中心.下面展示了部分生长环境中测量出来的读性能数据.

7. 结论

我们已经建立、实现并维护的存储系统，可以提供可伸缩性、高性能与广泛的适用性.我们的经验表 明,Cassandra可以在提供低延时(low latency)的同时提高非常高的更新吞吐量(thoughput).后期的工作涉及增加压缩功能、跨越多个键的原子操作支持以及辅助索引支持.

8. 致谢

Cassandra极大地受益与Facebook公司内部许多同事的反馈.另外还要特别感谢Karthik Ranganathan,他对MySQL中的所有数据建立了索引并将这些数据迁移到Cassandra中作为我们第一份正式部署.另外还要感谢来自 EPFL的Dan Dumitriu,感谢他对我们提出的宝贵建议(关于[19]与[8]).

9. 参考文献

[1] MySQL AB. Mysql.
[2] Atul Adya, William J. Bolosky, Miguel Castro, Gerald Cermak, Ronnie Chaiken, John R. Douceur, Jon Howell, Jacob R. Lorch, Marvin Theimer, and Roger P. Wattenhofer. Farsite: Federated, available, and reliable storage for an incompletely trusted environment. In In Proceedings of the 5th Symposium on Operating Systems Design and Implementation (OSDI, pages 1-14, 2002.
[3] Mike Burrows. The chubby lock service for loosely-coupled distributed systems. In OSDI ‘06: Proceedings of the 7th symposium on Operating systems design and implementation, pages 335-350, Berkeley, CA, USA, 2006. USENIX Association.
[4] Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber. Bigtable: A distributed storage system for structured data. In In Proceedings of the 7th Conference on USENIX Symposium on Operating Systems Design and Implementation – Volume 7, pages 205-218, 2006.
[5] Abhinandan Das, Indranil Gupta, and Ashish Motivala. Swim: Scalable weakly-consistent infection-style process group membership protocol. In DSN ‘02: Proceedings of the 2002 International Conference on Dependable Systems and Networks, pages 303-312, Washington, DC, USA, 2002. IEEE Computer Society.
[6] Giuseppe de Candia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. Dynamo: amazonO? s highly available key-value store. In Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, pages 205-220. ACM, 2007.
[7] Jeffrey Dean and Sanjay Ghemawat. Mapreduce: simplified data processing on large clusters. Commun. ACM, 51(1):107-113, 2008.
[8] Xavier D?efago, P?eter Urba?n, Naohiro Hayashibara, and Takuya Katayama. The φ accrual failure detector. In RR IS-RR-2004-010, Japan Advanced Institute of Science and Technology, pages 66-78, 2004.
[9] Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. The google file system. In SOSP ‘03: Proceedings of the nineteenth ACM symposium on Operating systems principles, pages 29-43, New York, NY, USA, 2003. ACM.
[10] Jim Gray and Pat Helland. The dangers of replication and a solution. In In Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, pages 173-182, 1996.
[11] David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, and Rina Panigrahy. Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web. In In ACM Symposium on Theory of Computing, pages 654-663, 1997.
[12] Matthew L. Massie, Brent N. Chun, and David E.Culler. The ganglia distributed monitoring system: Design, implementation, and experience. Parallel Computing, 30:2004, 2004.
[13] Benjamin Reed and Flavio Junquieira. Zookeeper.
[14] Peter Reiher, John Heidemann, David Ratner, Greg Skinner, and Gerald Popek. Resolving file conflicts in the ficus file system. In USTC’94: Proceedings of the USENIX Summer 1994 Technical Conference on USENIX Summer 1994 Technical Conference, pages 12-12, Berkeley, CA, USA, 1994. USENIX Association.
[15] Robbert Van Renesse, Yaron Minsky, and Mark Hayden. A gossip-style failure detection service. In Service,Tˇ Proc. Conf. Middleware, pages 55-70, 1996.
[16] Mahadev Satyanarayanan, James J. Kistler, Puneet Kumar, Maria E. Okasaki, Ellen H. Siegel, and David C. Steere. Coda: A highly available file system for a distributed workstation environment. IEEE Trans. Comput., 39(4):447-459, 1990.
[17] Ion Stoica, Robert Morris, David Liben-nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, and Hari Balakrishnan. Chord: a scalable peer-to-peer lookup protocol for internet applications. IEEE/ACM Transactions on Networking, 11:17-32, 2003.
[18] D. B. Terry, M. M. Theimer, Karin Petersen, A. J. Demers, M. J. Spreitzer, and C. H. Hauser. Managing update conflicts in bayou, a weakly connected replicated storage system. In SOSP ‘95: Proceedings of the fifteenth ACM symposium on Operating systems principles, pages 172-182, New York, NY, USA, 1995. ACM.
[19] Robbert van Renesse, Dan Mihai Dumitriu, Valient Gough, and Chris Thomas. Efficient reconciliation and flow control for anti-entropy protocols. In Proceedings of the 2nd Large Scale Distributed Systems and Middleware Workshop (LADIS ‘08), New York, NY, USA, 2008. ACM.
[20] Matt Welsh, David Culler, and Eric Brewer. Seda: an architecture for well-conditioned, scalable internet services. In SOSP ‘01: Proceedings of the eighteenth ACM symposium on Operating systems principles, pages 230-243, New York, NY, USA, 2001. ACM.

No related posts.