Abstract

Cassandra 是一个分布式存储系统，用来管理一大堆结构化的数据，在许多服务器上。

高科用，没有单点错。

用于在上百个节点的基础设施上运行。可能分数据中心。

这个规模下，大小错误频发。Cassandra 在许多方面重组了数据库并且借鉴了许多实现和策略，但是并没有支持完整的关系数据模型。但是它提供了一个简单的数据模型来支持动态控制数据布局和格式。Cassandra 被设计用于廉价的家用（商用）硬件，在保持高写吞吐量时并未牺牲读取的效率。

Intro

Facebook 作为世界上最大的社交网络平台，用户和内容的增长速度非常快。急需高性能、可靠、高效、可扩展的平台。并且软件系统需要将服务器的 failure 作为一种常态而不是意外来处理（容错）。因此开发了 Cassandra。

Cass 融合了很多有名的技术来提高可扩展性和可用性。最初是为了满足 Inbox Search 服务的存储需求而开发的。在 Facebook 中，这项特性允许用户搜索他们的 Facebook Inbox。这意味着需要处理非常高的写吞吐，大约十亿每天的写操作，并且随着用户数量的增加还会增长。用户从地理上分布的数据中心请求数据，因此降低搜索延迟的核心是跨数据中心的数据复制。从2008年的1亿用户到2010年的2.5亿，Cassandra展现出了它的潜力，现在成为了Facebook许多产品服务的存储服务后端。

2 相关工作，影响了设计的

3 数据模型

4 客户端 api

5 系统设计和分布式算法

6 开发中的经验，优化

7 future work

DATA MODEL

表：分布式的多维 map，由 key 来 索引。

value 是一个高度结构化的数据对象

表的行key是一个没有大小限制的字符串，一般16-36bytes。

在每个副本中，对一行的操作是原子化的，无论修改了多少列。

列可以分组到一起放到集合中，叫做“列族”。

Cass 内置了两种 column families，Simple 和 Super column families。应用程序可以在其中指定列的排序依据为时间或名称，用来适应服务的需要。

API

insert(table, key, rowMutation)

get(table, key, columnName)

delete(table, key, columnName)

columnName 可以是列族中的列，可以是列族，可以是 Super cf，或 SCF 中的列。

SYSTEM ARCHITECTURE

分片 Partitioning

因为需要很高的扩展性，为了动态地将数据分布到节点上，使用一致性hash。一致性hash是基于一个数环来实现的。所有的hash值都对同一个上限去取模，系统中的每一个节点也将被分配一个随机值，并放到数环当中。每一个数据对象通过其key 的hash找到其在环中的位置，顺着环向下走的第一个数据节点即是该对象存放的节点。因此，每一个数据节点都只需要负责其前一个数据节点到它自身之间的hash值即可。

一致性hash 的好处就是节点的增减只会影响它的直接邻居，其他节点都不受影响。不过这样的设计也有一些问题。第一是为节点分配随机值，可能导致数据和负载分配的不均匀。另外这样的算法考虑不到节点之间的性能差距。一般来说有两个方法能够解决这一问题：一是让一个节点在环上存在多个位置，二是分析环中的负载信息，让轻负载节点在环中移动，以缓解负载重的节点压力。Cassandra 采取了第二种。

复制 Replication

Cassandra 使用了复制技术以实现高可用和持久化。每个数据对象都有 N 个副本。

每一个对象的key k都会在hash环中被分配给一个协调者节点。它管理着数据的复制。除了在本地存储一份外，协调者节点还会将它复制到环中的 N-1 个节点。Cassandra 为客户端提供了数据复制方法的多种选择。“Rack Unaware”, “Rack Aware”(within datacenter) and “Datacenter Aware”. 备份的选择是基于应用选择的策略。如果选择 RU，那么复制到协调者的 N-1 个后继节点上；对于RA和DA策略会稍微复杂一点。Cass 会在节点之间选举一个 leader（Zookeeper）。所有的节点在加入集群的时候，都会与 leader 通讯来获取它们的备份范围。并且 leader 会保证不会有节点负责超过 N-1 个范围。所有的节点所负责的范围的 metadata 会在每一个节点中以 Zookeeper 的容错机制进行本地缓存，以便从错误中恢复的节点也能找回自己负责的部分。此外，对于每一个被负责的范围，都有一个负责节点的“优先列表”。

每一个节点都有关于其他所有节点的知识。Cassandra 通过放松多竖排的要求，为可能出现的节点故障和网络分区问题提供了持久的保证。有时可能一整个数据中心会因为不可抗力失效。Cassandra 保证每一个数据行都会有跨数据中心的副本。在上文中的“优先列表”即是为了保证其中的节点是分布在多个数据中心的。这些数据中心之间有高速网络连接。跨中心的复制允许我们既能处理数据中心的错误，又能够避免服务中断。

Membership。这是什么？成员资格

通过 Gossip 来维护整个集群的成员状态。Gossip 大概是每一个成员每个 T 秒进行一次 heartbeat，选择其他的 member 发送它的优先列表，然后将自己的列表和收到的列表合并起来。

错误检测。Cassandra 采用了一个 $\Phi$ Accrual Failure Detector (SRDS 2004) 的修改版本。错误检测常见的模式就是采用心跳，如果心跳超时则认为对端失败。在实际使用中，由于网络延迟的抖动会导致误判。系统使用如下方法提高基于心跳探测方式的准确率：

1、假设心跳消息符合某一概率模型。例如定期发送的心跳消息在有网络延迟的情况下，接受到消息的 interval 符合正态分布。

2、利用接受到的历史数据（滑动窗口），对概率模型参数进行极大似然估计。

3、利用估计得出的参数代入模型，计算在当前时刻接收到心跳消息的概率。

得到概率后，并不直接得出对端是否存活的判断，而向上层应用返回这一概率，由应用自行解释。

在 Cassandra 中，认为指数分布是较好的近似。

Bootstrapping 初次启动

当一个节点初次启动的时候，它会随机选择一个 token来产生节点在环上的位置。为了容错，映射会被持久化到磁盘本地以及 Zookeeper 中。然后 token 的信息会通过 Gossip 在集群当中传播。这就使得每一个节点都能够将请求路由到正确的节点上。在 bootstrap 程序中，如果节点想要加入一个集群，会先读取一个包含了几个通讯点的配置文件，我们把最初的这几个通讯点叫做集群的“种子”。种子也可以通过 Zookeeper 这样的服务来确定。

Scaling the Cluster 集群扩容

当一个新节点加入到系统当中时，它会按照优先缓和负载较重的节点的目的来分配 token，这会导致新的节点将原来节点的负责范围划走一半。Cassandra 的 bootstrap 算法是通过操作员通过系统中其他的节点的命令行或者是 Cassandra 的 web 管理面板来启动的。原节点通过 kernel-kernel 的复制技术将数据流转移到新的节点上。

Local Persistence 本地持久性 （落盘？）

Cassandra 是依赖于本地文件系统来完成数据持久化的。数据在磁盘上是以可自我恢复的形式存储的。一般的数据写入操作都包含了对 commit log 的写入来保证持久性和可恢复性，以及对内存中数据结构的更新。对内存数据结构的写入仅在 commit log 写入成功后进行。每台机器上都有一块专门的硬盘用于 commit log 的存储，以最大化磁盘的吞吐量。当磁盘中数据结构的规模达到一定的上限，它就会将自己写入到磁盘当中。所有的磁盘写入都是顺序的，并且写入时会产生一个索引以实现基于行 key 的高效查询。这些索引也会随着数据文件一同被持久化。长期运行中，可能会产生许多的索引文件，因此在后台运行了一个合并进程来合并文件。这一过程与 Bigtable 系统中的压缩非常类似。

一个正常的读操作首先查询内存中的数据结构，然后才会查询磁盘中的文件。文件查询的顺序是从新到旧。当一个磁盘查询发生的时候，我们可能会在磁盘中的很多个文件中查找同一个 key。为了减少不必要的查询，每一个文件都又一个 bloom filter。它聚合了文件中存在的所有 key 值，存放在数据文件当中，且在内存中也有一份。这个过滤器会在查询到来时首先判断被查询的 key 在给定的文件中是否存在。

实际体验

深刻的一课：如果没有理解一个新特性产生的影响，就不要添加它。

许多麻烦的场景其实不是因节点失效或网络分区问题而产生的。