Cassandra 是一个在传统机器上管理大量结构化数据的分布式存储系统，提供了高可用性，并且没有单点错误。Cassandra期望运行在成百上千个结点的基础设施上（可能分布在不同的数据中心）。在这种规模下，大大小小的故障是继续不断的。Cassandra 面对这些错误管理持久状态。依靠这个服务来驱动软件系统的可靠性和可拓展性。Cassandra 不提供完整的关系式数据库，而是提供一个支持动态控制数据分布和格式的简单数据模型的客户端。Cassandra 设计在便宜的商品电脑上运行，提供高效的写操作而且不影响读操作的性能。
FB 运行着最大的社交网络平台，在高峰时期使用上万台分布在世界各地的数据中心的成千上万台服务器来服务上千万用户。这有严格操作需求在FB平台上对性能、可靠和高性能，以及为支持持续增长平台所需要的高拓展性。
为了解决上千组件组成的基础设施的错误是我们标准的操作模式。在任何时刻，一直都有少数但是有效数目的服务器和网络组件是错误的。像这样，软件系统需要构建在这种方式：把错误当成正常而不是异常。为了达到上述可靠性和可拓展性，FB开发了Cassandra。
Cassandra 使用一个综合体，被广为了解的技术来实现可拓展性和高可用性。Cassandra被设计来满足收件箱搜索问题的存储需求。收件箱搜索是一个功能，让用户搜索他们的Facebook收件箱。在Facebook这意味着这个系统需要处理一个非常高的写吞吐量：第天上百万次写操作，并随着用户数可拓展。因为用户被分布在地理各处的数据中心服务，可以跨数据中心复制数据是保持搜索延时较低的关键。收件箱搜索2008年6月被上线的，服务大概一千万用户，现在大概2亿5千的用户，到目前为止，Cassandra依旧满足承诺。Cassandra现在在FB被作为服务多个服务的存储系统的后端部署。
本文被组织如下：Section 2讨论相关工作，一些正好影响了我们设计。Section 3提供了一个更具体的数据模型。Section4展示了client API的概览。Section 5提供了支撑Cassandra工作的系统设计和分布式算法。Section6详细表述让Cassandra工作和重构来提高性能。在Section6.1，我们描述FB的一个程序使用Cassandra。最后Section7以Cassandra未来的工作结尾。
介绍了一堆相关的项目：dynamodb,gfs,Ficus,Coda,Bayou和Bigtable。就不翻译了。
一个表格在Cassandra是一个分布式的通过key来索引的多维Map。值是一个高度结构化的对象。表格的行键值是一个没有长度限制的（多为16到36字节长）字符串。不管多少列被读或者写入，在一个单行键值的每个操作是原子每个拷贝。表被组织在一起为集合叫作列族(columns families)，非常相似于Bigtable系统。Cassandra提供二类列族：简单和超级列族。超级列族可以被视为一个列族包含一个列族。
进一步，程序可以指定一个超级列或者简单列排序的顺序。系统允许列根据时间或者名字排序。列的时间排序是被像Inbox Search这样总是显示时间排序的程序大量使用。列族中任意列可以使用（惯例列族：列）访问。超级列中的任意列可以=使用（列族：超级列：列）的方式来访问。一个很好的超级列族抽象的力量的例子在Section6.1中给出。典型程序使用一个Cassandra集群，把他们作为服务的一部分来管理。尽管系统支持多表格的观念，所有的实际系统在他们的Scheme只使用一个表格。
Cassandra API由三个简单的方法构成。
insert(table, key, rowMutation)
get(table, key, columnValue)
delete(table, key, columnName)
columnName 可以指向列族中的特定列或者列族，或者一个超级列族，或者一个超级列族中的一列。
需要在一个产品级配置中运行的存储系统的架构是复杂的。另外对实际数据持久化组件，系统需要有下列特点：可拓展和负载均衡的鲁棒性解决方案，成员关系和故障检测，故障恢复，拷贝同步，过载处理，状态转移，并发和作业调度，请求管理调度，请求路由，系统检测和报警，配置管理。描述每一个解决方案超过了本文的范围，所以我们将集中在Cassandra中使用的核心分布式系统技术：分片，复制，成员，故障处理和拓展性。所有这些模块同步处理读写请求。典型的对一个键的一个读写请求被路由到Cassandra集群的任一结点。这个结点然后决定为个键服务的分片。对于写，这个系统路由请求到服务于Key的多个拷贝结点，等待拷贝结点中的负责结点(quorum)确认写操作的完成。对于读，基于被客户端一致性的保证，系统或者路由请求到最近的拷贝，或者路由请求到所有的拷贝，等待quorum的响应。
Cassandra 设计的关键特性之一就是可增加的拓展能力。这需要，将数据动态分片到集群结点集合的能力。Cassandra使用一致性哈希在集群中分片数据，但是使用保证次序的哈希函数。哈希函数输出的范围是一个圆或者一个环（最大的哈希值靠着最小的值）。每一个结点被赋予一个环中的随机值，代表它在环中的位置。根据key来标识的数据根据哈希函数来产生在环上位置来分配结点：顺时针找到第一个结点，它的位置大于数据的位置。这个结点称为该Key的协调者(coordinator)。
程序指定这个key，Cassandra 使用它来路由请求。因此，每个结点响应它与它之前结点之间的环形区域。一致性hash的主要优点是移除或者新加一个结点，只影响它紧挨的结点，其它结点不受影响。基础的一致性哈希算法有一些问题。首先，给每个结点随机分配环上的位置造成不平均的数据和负载分布。第二，基础的算法在每个节点上的性能有明显的差异。典型的这儿有二种方式来解决这个问题：一个是每个节点被赋予多个环上的几个位置（例如Dynamo），这二种是分析环上的负载信息，有一个轻负载结点在环上移动来缓解重负载结点，像参考文献【17】说。Cassandra选择后者，因为它让设计和实现非常易处理，帮助来实现负载均衡的非常决定性的选择。
Cassandra使用复制来实现高可用性和健壮性。每个数据单元被复制在N台机器上(N是配置的复制因数）。每个键值k,被分配到一个协调节点（如上文所述）。协调节点负责落入该范围的数据单元的复制。除了在本地存储每个在它负责范围的key，协调结点还复制这些key到环上的N-1个结点上。Cassandra提供给客户端一些关于数据如何复制的选项，Cassandra也提供了不同的复制策略，像：”Rack Unaware”， “Rack aware”和”datacenter aware”.拷贝根据程序选择的策略来工作。如果程序选择”Rack Unaware”复制策略，然后非协调者节点通过选择N-1个环上的后续协调者来选择。对”Rack Aware”和”Datacenter Aware”稍微更复杂。Cassandra 使用Zookeeper系统在它的结点中选择leader。所有的结点在加入集群的时候联系leader,leader告诉他们他们要复制的范围。leader上下齐心协力以保证节点不会响应超过N-1个范围。元数据（一个节点所负责的范围）被缓存在每个节点的本地以及以一个容灾的方式存储在Zookeeper中。这样一个节点宕机后被加回，仍然知道它所负责的范围。我们借用Dynamo的说法，认为节点负责一个给定范围是负责给定范围的“偏好列表”为范围的节点。
如5.1所描述，每个结点都能被系统中的其它结点所感知，以及他们负责的范围。在遇到结点故障和网络分片时，Cassandra通过像5.2描述一样通过降低 quorum 结点的要求，提供可靠性(durability)保证。因为电力中断，降温故障，网络故障和自然灾害导致数据中心发生故障。Cassandra配置为每行在多个数据中间之间复制。本质上，一个key的偏好列表是通过存储结点分布在多个数据中心来构建的。这些数据中间通过高速网络来连接。在多个数据中心复制数据的方案让我们可以不中断运行的处理整个数据中心故障。
Cassandra集群成员是基于Scuttlebutt[19]，一个非常高效的反熵(anti-entropy，不知道指的什么)基于Gossip的协议。Scuttlebutt显著的特点是它有非常高效CPU利用率和非常高效的gossip通道的利用率。尽管Cassandra系统的Gossip不是只用来成员管理，也用来传播其它系统相关的控制状态。
故障检测是一个机制：通过一个结点可以本地确定系统中任意其它结点是正常还是宕机。在Cassandra，故障检测也用来避免在大量操作中尝试与不可访问节点通信。Cassandra使用一个修改版本的Accrual Failure Detector[8] 。Accrual Failure Detection 的想法是故障检测模块不提交一个Boolean值来标记一个结点是正常还是宕机。故障检测模块提交一个表示每个监控结点可疑级别的值。这个值被定义为Φ。最基本的想法是在一个范围内表达Φ值，这个范围是动态调整的来反映被监控结点的网络和负载条件。
Φ有以下的意义：给定一些阙值Φ，假设当Φ=1时，我们决定质疑结点A，然后我们做了一个错误（例如，这决定会在将来收到一个迟到的心跳而矛盾）的可能性是大约10%。当Φ=2时，这个可能性大概是1%。当Φ=3时，则为0.1%，以此类推。系统中每个结点维护一个从集群其它结点收到Gossip消息的间隔时间的滑动窗口，这些间隔时间的分布是确定的，Φ可以被计算。尽管原始的论文建议分布近似于高斯分布，我们发现指数分布可以更好拟合，因为gossip通道的本质和它在延时的影响。据我们所知，我们在一个Gossip基础上实现的Accrual Failure Detecton是第一个这类实现。Accrual Failure Detectors 是在精度和速度上表现很好，而且对网络条件和服务器负载条件可以调整到很好。
当一个结点第一次启动，它选择一个随机的token来决定它在环上的位置。为了容灾，映射信息也会保存在本地和zookeeper中。然后，token会通过gossip协议传递到整个集群中。这就是我们知道所有的结点和它们负责环上位置的方法。这样也可以让每个节点将请求正确的路由到相应的结点上。在启动时，结点先读取一个记录了一些可访问结点(contact point)的配置文件。我们称这些最初的访问结点为集群种子（seeds of cluster)。Seeds 也可以从像zk这样的配置服务上读取。
在fb，一个结点宕机一般是短暂的，但是会持续一个区间。故障可能是硬盘故障，CPU损坏等。一个结点宕机很少会永久的不服务，因此不要重新分配partition或者修复不可访问的拷贝。相似的，人工错误可能造成启动意料外的新Cassandra结点。每个消息包含集每个Cassandra实例的群名，如果一个人工配置的错误导致一个结点尝试去连接一个错误的Cassandra实例，这个可以根据集群名来阻止。因为这些理由，使用合适明确的机制来处理机器添加和Cassandra实例之间的迁移。管理员使用命令行工具或者浏览器连接到一个Cassandra结点，提交一个成员变更来加入或者退出一个集群。
当一个新的结点添加到集群中时，它被分配一个token，可以减轻负载重结点的压力。新的节点分割一个之前其它节点负责的范围。Cassandra Bootstrap 算法通过使用命令行或者浏览器在另一个节点上操作来初始化。这个节点通过kernel-kernel copy技术把数据流传递给新的节点。操作经验显示数据从一个结点传输可以达到40mb/sec，我们通过类似于Bittorrent的技术，让多个拷贝参与到bootstrap transfer来改进速度。
Cassandra使用本地文件系统来做数据持久化。数据使用一种让查询高效的格式存储在磁盘上。典型的一个写操作包含一个为了鲁棒性和可恢复而写入commit log的操作以及一个内存数据结构的更新。内存更新只在写入日志成功后才执行。我们有一个专用的磁盘来存储commit log，因为所有的commit log是顺序的，所以我们可以最大化磁盘吞吐。当内存数据结构达到一个特定的根据数据规模和对象个数计算出的阙值，它dump到硬盘上。写操作作用在机器配置的商业磁盘上。所有的写操作是线性写到磁盘，也根据行的键值来生成一个索引来高效的查询。这些索引也持久在数据文件中。一段时间后，很多这些文件生成在磁盘上，一个合并操作在后台执行来将多个不同的文件合并为一个文件。这个过程与Bigtable系统的compaction过程相似。
一个典型的读操作首先查询内存数据结构，再查询磁盘上的文件。文件按照从最新到最旧的顺序查询。当一个磁盘文件查询发生，我们可以在多个磁盘上文件查询一个key。为了防止查询一个并不包含该key的文件，一个bloom filter也保存在每个数据文件和内存中。布隆过滤器首先被询问是否被这个文件包含。一个key在一个列族中可能有多个列。一些特殊索引需要取回这些列。为了防止扫描每个列，我们维护列的索引，让我们可以跳到正确的块。因为对于给定key的一列会被序列化并写到磁盘上。我们每256K块生成一个索引。这个限制是可以配置，但我们发现256K在我们的产品场景工作的很好。
注： 这些是标准的LSM实现，可以参考leveldb。
在一台机器上的Cassandra进程主要包含以下抽象：partitioning module、the cluster membership 和 failure detection module 以及存储引擎。这些模块都以一个事件驱动模块为基础。任务处理流水线根据SEDA架构分为几个阶段。这些模块都使用java实现。cluster membership 和 failure detection 模块都基于非阻塞的网络层。系统控制信息使用udp，其它程序相关于拷贝和路由的信息基于tcp。请求路由模块使用确定状态机来实现。请求到达集群中任意一个结点，状态机会经过如下状态：
为了描述，我们先不考虑故障情况。系统可以配置为同步写和异步写。对一些需要高吞吐量的系统，我们依赖于异步拷贝。这时写操作远远大于读操作。在同步场景，我们在回复客户端前要等待quorum结点的回应。
在任何journaled系统（journaled，也就是一个日志文件，可以恢复数据）需要有一种机制来清除commit log。在Cassandra，当前一个log超出一个配置的partition大小时，我们rolling这条log。我们从产品上发现rolling commit logs使用128MB工作的很好。每个commit log有一个固定长度的日志头（位向量）。在我们的实现中，有一个内存数据结构以及每个列族生成的一个数据文件。当内存数据结构dump到磁盘上，我们设置一位来标识其已经成功的在本地磁盘持久化。这也表明这条信息已经成功提交。这些位向量每条commit log一个,同时也被维护在内存中。Every time a commit log is rolled its bit vector and all the bit vectors of commit logs rolled prior to it are checked. 当所有的数据都持久化到磁盘后，删除所有的commit log。commit log中的写操作可以正常模式或者快同步模式。在快同步模式下，会缓存commit log的写操作。这表示有一定可能会在机器宕机时丢失数据。在这个模式下，我们也会使用缓冲的方式来dump内存数据到磁盘上。传统数据库没有设计来专门处理高吞吐的写操作。Cassandra将写操作序列化，因此最大化的提高磁盘写的吞吐量。因为Cassandra dump到磁盘的数据是不会变化的，因此并发读操作不需要持有锁。Cassandra的server对于读写都是lock-less的。因此，我们不用像那些基于B-Tree的数据库一样要去处理并发的问题。
Cassandra使用主key来构建索引。数据文件被分为一些块。每个块最多包括128个key，并使用一个block index来分隔。block index记录了key相对于block的offset以及数据大小。当一个内存结构dump到磁盘时，就会生成一个block index，他们的offset也会写到磁盘中作为索引。这个索引也被维护在内存中，为了可以快速访问。一个典型的读操作会先查询内存结构，如果内存包含最新的key，则返回给用户。否则按照时间相反的顺序查询磁盘上的数据文件。因为我们总要查询最新的数据文件，我们首先查看最近的文件，并返回是否找到。过了一段时间，会有很多的数据文件，我们像Bigtable系统一样执行一个compaction过程来合并一些文件成单个文件。本质上就是在一堆已排序文件上做合并排序。
联系客服
