Cassandra 一个去中心化的结构化存储

概要

cassandra是一个分布式存储系统已管理大量的结构化数据分布在许多商用服务器上，同时允许在单点故障的情况下提供高可用。Cassandra的目标是运行在上百台节点的基础设施之上（可能分割到不同的数据中心）。在这个尺度下，大的和小的组件故障连续不断。Cassandra在面对这些故障管理持久状态的方式驱动了一来该软件服务的软件系统的可靠性和伸缩性。在很多封面Cassandra类似一个数据库，并与之贡献很多实现策略Cassandra不知此完全的关系模型；作为替代他提供给客户端一个简单的数据模型以支持对数据布局和格式的动态控制。Cassandra的系统被设计为运行在廉价的通用硬件。在处理高吞吐量的同时不影响读取的效率。

1 介绍

Facebook运行最大的社交网络平台，服务于上亿的用户在峰值时段使用上万台服务器其遍布整个世界。这是一个严格的操作要求facebook的平台的性能，可靠性，有效性有严格的要求，并且支持持续的增长，平台需要高可缩放性。处理包括上千个组件的故障是我们标准运作模式。总会有小的但是明显的服务和网络组件在给定的事件故障。因此，软件系统需要结构化的管理者将失败视为日常而不是意外。为了应对上述的可用性和可缩放需求facebook开发了Cassandra。

Cassandra总和使用了知名的技术一达到可缩放和可用性。Cassandra被设计为实现Inbox serch 问题。Inbox是一项功能允许用户搜索他们的facebook收件箱。在facebook中这意味着系统需要处理非常高的写入量，每天上百万的写入，并且随着用户数量的扩大。由于用户从地理分布的数据中心获得服务，允许副本数据穿过数据中心是保证低延迟的关键。Inbox 查询在2008年6月启动服务于大约1亿用户如今我们有超过2.5亿的用户，并且Cassandra还在保持增长。Cassandra现在被部署在后端存储系统为facebook的多个服务服务。

2 相关工作

分布式数据的可靠性可用性和持久性在文件系统和数据库已经有了广泛的研究。对于只支持平面空间的p2p存储，分布式文件系统特别支持了分级的命名空间。文件系统类似Ficus和Coda 以牺牲一致性为代价来获得高可用性。更新冲突通常使用专门 打冲突解决程序进行管理。Farsite是一个分布式文件系统他不使用任何中心化服务。Farsite使用复制达到了高可用和可缩放。GFS是另一个文件系统以托管谷歌内部的应用状态。GFS使用了简单的单个主设计以托管整个元数据，其数据被切分为chunk并且存储在chunk服务上。然而，GFSmaster使用Chubby的抽象处理容错。Bayou是一个分布式关系型数据库允许不连贯的操作并且提供数据的最终一致性。在这些系统中，Coda和Ficus 允许断开操作并对网络分区和中断问题具有弹性。这些系统在解决冲突上的过程有所不同。例如coda和Ficus执行文件级别的冲突决议，Bayou允许应用级别的解决。然而，他们都保证最终一致性，Dynamo允许读取和写入操作连续，即便是在网络分区的情况下别去使用不同的由客户端驱动的冲突解决机制来解决冲突。传统的复制的关系数据聚焦于保证副本数据的强一致性。虽然强一致性提供了应用写入方便的模型，这写系统限制了可缩放性和可用性。这些系统没有处理网络分区的能力，因为他通常提供强一致性保证。

向量时钟（Vector Clock）是一种用于解决分布式系统中并发更新冲突的问题的机制。它通过记录每个节点（或副本）在某个数据项上的修改历史，来追踪这些数据项的状态变化，以便在多个副本并行修改时能够检测到哪些修改是冲突的。

在分布式系统中，通常会有多个节点（或副本）处理同一数据项的不同副本。为了确保数据一致性，需要一种机制来判断这些副本是否有冲突，尤其是在它们的更新是并行进行的情况下。向量时钟就提供了一种解决方法。

1. 每个节点有一个时钟：系统中的每个节点维护一个向量，记录该节点对数据项的修改历史。向量中的每个元素对应一个节点的时钟，通常是一个整数，表示该节点的修改次数。例如，系统中有三个节点 A、B 和 C，那么每个节点会维护一个三维向量 [A, B, C]，每个维度的值代表该节点对数据项的修改次数。
2. 每次修改都会更新时钟：当某个节点修改数据时，它会增加自己的时钟值，同时将这个更新传播到其他节点。例如，假设节点 A 修改了数据，它的向量时钟会变成 [1, 0, 0]（假设初始时钟为 [0, 0, 0]），表示节点 A 对数据进行了第一次修改。
3. 向量时钟的传播：当节点 A 将数据更新发送给节点 B 和节点 C 时，它会把自己的向量时钟一并发送过去。接收到更新的节点会更新自己的时钟，确保自己的向量时钟包含其他节点的历史修改。

4. 检测冲突：向量时钟的核心在于它能帮助系统识别冲突。例如：

   • 如果两个节点同时修改了同一数据项，但修改的顺序无法确定，或者修改的内容互相冲突，则这两个版本会被标记为冲突。
   • 如果两个节点的向量时钟不相等，并且没有完全包含对方的历史时钟，那么这两个修改就是并行的，意味着可能会发生冲突，需要进一步处理。

向量时钟的核心方案是通过维护每个节点的历史修改来检测分布式系统中是否存在更新或者冲突。

Dynamo是一个存储系统他被亚马逊用来存储和检索用户购物车。Dynamo的基于成员的算法帮助每个节点维护其他节点的信息。Dynamo可以定义为一个结构化的覆盖网络，最多有一跳路由请求。Dynamo使用矢量时钟的方案检测冲突，但是更偏好于客户端测解决冲突。Dynamo的写操作也需要执行读取操作来管理矢量时间戳。在系统处理非常高的写吞吐量的环境中，这可能是非常有用的。Bigtable提供了结构和数据分布，但是他的持久性依赖于分布式文件系统。

3 数据模式

Cassandra中的表是由键缩阴丹分布式多维映射。值是一个高度结构化的对象。行键（row key）在表中是一个字符串但是允许16-36的字节长度。每个操作对每个副本都是原子的，无论读取或写入多少列。列被分组到一起加入一个叫做列族的集合，这与bigtable非常类似。Cassandra暴露了俩种列组，简单和超级列族。超级列族可以被抽象为列族的列族。

此外，应用可以指定列的顺序使用超级列族或者是普通列族。系统 允许列变得有序通过时间或者名字。类似iInbox 查询这样的应用利用了列的时间排序，结果总是按顺时间排序的顺序显示。在一个列族（column family）内的任何列都可以通过以下方式访问：column_family : column，任何类型为超级的列都可以通过column_family:super_column:column进行访问。一个关于超级列抽象能力的非常航的例子在6.1。应用程序通常使用专用的Cassandra集群，并将其作为服务的一部分进行管理。虽然系统提供了多个表的概念，但是所有的部署模式只有一个表。

4 API

Cassandra API包含了如下的三个简单方法。

• insert(table, key, rowMutation)
• get(table, key, columnName)
• delete(table, key, columnName)

columnName用来指定的列，列族， 超级列族或者超级列中的列。

5 系统架构

需要在生产环境中运行的系统架构是很复杂的。除了实际的数据存储组件之外，系统须有如下的特性；可缩放和健壮的环境一应对负载均衡成员和故障检，失败回复，复制同步，过载处理，状态转换，实时工作调度，请求编组，请求路由，系统监控和警报与配置管理。描述解决方案的每个细节超出了这个论文的范围，所以我们关注于cassandra使用的核心系统分局技术，分区，复制，成员，故障和缩放。所有的这些模块同步处理负载请求。通常，对于key的读写请求被路由到cassandra的任何节点。节点之后确定特定key的复制。对于写入，系统路由请求到副本并且等待副本的法定数量来确认写操作的完成。对于读取，基于通过客户端对一致性保证的需要，系统要么路由到最近的副本要么路由请求到所有副本并且等待法定人数的响应。

5.1 分区

cassandra的一个设计的关键特性是增量扩展的能力。这需要在集群中的节点集（即存储主机）上动态划分数据。cassandra使用一致性哈希分区数据跨越集群，但是使用了一个保持顺序的哈希函数。在一致性哈希中，哈希函数的数范围被视为一个固定圆形空间形成的环（即最大的哈希值到最小的哈希值）。每个节点在信息系统中被分配一个随机值，代表它在环上位置。由key标识的每个数据项通过哈希分给每一个节点，数据项的键以获得其在环上的位置，然后顺时钟遍历找到位置大于该数据项的第一个节点。这个节点被视为此键的协调器。应用程序指定此键，并且cassandra使用它路由请求。因此，每个节点负责环中该区域，并且处理环上的节点。一致性哈希的一个主要优点是，一个节点的离开或者到达只影响它的近邻，其他节点仍然不受影响。首先随机的位置指派到圆上的每个节点导致数据和载荷分布不均。通常解决这个方法由俩个问题：一个方法是将节点分配到圆中的多个位置（类似Dynamo），第二是分析圆上的负载信息并且稍微调整环上节点的移动减轻过载节点。cassandra选择了后者因为他的视线非常容易处理并且有助于做出关于负载均衡非常确定的选择。

5.2 复制

不同的策略就是为了就近复制。在复制速度和可靠性做取舍。复制的越远，越不容易一起崩溃。

cassandra使用复制以保证高可用性和持久性。每个数据项被复制到n个节点其中n是复制因子被每个实例配置。每个键k被分配到对应节点（在之前的章节描述的）。协调器负责其数据范围内的数据项。除了本地存储范围内的每个键之外，协调器在环中的N-1个节点复制这些键。Cassandra为客户端提供了各种复制数据的选项。Cassandra提供了多种复制策略比如Rack Unaware和Rack Aware（在数据中心中）以及Datacenter Aware（在数据中心）。副本的选择基于应用的复制策略。如果中心应用选择了Rack Unaware复制策略，那么非协调器的副本将通过选择协调器后续的N-1个节点来确定。Cassandra系统选举leader使用了一个叫做Zookeeper的系统。所有加入集群的节点与leader联系，告诉它们复制的范围是什么，并且leader会协调维护不变性，没有节点负责超过n-1个范围。关于节点范围的元数据在本地缓存在每个节点上并且在Zookeeper中保证容错性。通过这种方式崩溃和恢复的节点知道它的范围。我们借用了Dynamo的说法，将负责给定范围的节点称为该范围的偏好列表（preference list）。

如5.1章的例子一样，每个节点都知道系统中的其他节点和他们负责 的范围。Cassandra通过5.2章中描述的仲裁要求，在节点故障和网络分区存在的情况下保证持久性。数据中心的故障 是由于断点，散热失效，网络故障和自然灾害。Cassandra被配置为在数据中心复制每个行。本质上，构造了键的首选项列表，因此存储节点扩展跨越多个数据中心。这些数据中心使用告诉网络进行连接。跨越多个数据中心的复制方案允许我们处理整个数据中心的故障无论是否停电。

5.3 成员

Cassandra的客户端成员是基于Scuttlebutt的，一个非常有效的基于Gossip的逆熵机制。Scuttlebutt的一个突出的特性是非常有效的CPU利用率以及非常有效的利用了gossip通道。在Cassandra系统内部，gossip不仅用于成员，还用于传播系统的相关控制状态。

5.3.1 失败探测

Accrual Failure Detector 是一种用于分布式系统中的故障检测机制，旨在通过累积的信息来逐渐确定某个节点是否发生故障。与传统的故障检测机制（如心跳或超时检测）不同，Accrual Failure Detector 提供了一个更为渐进的失败判定过程，使得系统能够在不同情况下适应不同的故障检测需求。

每个节点都会定期发送心跳消息，以便其他节点检测它的存活状态。接收节点根据这些消息来计算发送节点失效的概率。

通过累积收到的心跳信息，节点估算出发送节点失败的可能性，这个概率随着时间的推移逐渐增加，直到某个阈值被触发，从而确定节点已经失败。

系统会设定一个阈值（通常是一个概率值），当某个节点的失败概率超过这个阈值时，系统就会认为该节点发生了故障。

这个阈值通常是动态调整的，根据实际的网络状况和节点的健康状态来修改。

失败探测是一个机制，如果有任何系统中的节点上线或者下线，节点可以本地进行确定。在Cassandra中失败探测也被用来避免在各种操作中与不可达的节点通信。Cassandra使用修改版本的$\Phi$累计故障检测器。累计故障检测器的思想是故障探测模块，不会我发出一个布尔值来表示节点是up还是down。相反。故障检测模块发出一个值，表示每个监视节点怀疑的级别。这个值的定义如同$\Phi$。其基本的思想是动态调整的尺度上表示$\Phi$的值，以反映被监视节点的网络负载和条件。

$\Phi$遵循以下机制，给定一些阈值$\Phi$，并且假设我们在$\Phi$的时候怀疑节点，然后是我们犯错的可能性（即，这个决定会在未来被延迟的心跳推翻）约为10%。当$\Phi$=2概率是1%,$\Phi$=3概率是0.1.以此类推。系统中的每个节点都维护一个滑动窗口，显示来自集群中其他节点的gossip信息的间隔到达时间。这些到达间隔的时间是确定的，并且由$\Phi$计算出来。虽然原论文认为分布式近似高斯的，我们发现指数分布是一个更好的近似。因为gossip通道的性质和对延迟的影响。据我们所知，我们的是使用gossip实现累计故障检测同类中的第一个。累计故障检测对于准确性和速度都非常好，他能很好的适应网络环境和服务负载条件。

5.4 启动

在一个节点启动的第一时间，他选择一个随机token已定位环上的位置，为了容错，映射被持久化到本地磁盘和Zookeeper中。token信息之后会被gossip环绕到集群。这就是我们如何知道所有节点在圆上的位置。这允许所有节点为key进行请求路由到合适的集群中的节中。在启动案例中，当一个节点需要加入集群他读取配置文件，其中包含了了几个接触点的列表。我们叫这个初始化点为集群的种子。种子也来自配置服务比如Zookeeper。

在facebook环境节点停机时（由于异常和维修任务）通常是短暂的，但是也可能遗留较长时间。故障可以是多种形式，比如磁盘故障，CPU损坏等我。节点停机很少意味着永久离开，因此不会导致分区作业重平衡或者修复无法访问的副本。类似的手动的错误可能会导致无意中启动新的Cassandra节点。每条信息都是这样包括每个Cassandra实例的节点名。因为这个原因，它被认为是合适的：使用显示的机制初始化Cassandra实例中的节点添加和删除。管理者使用命令行工具或者浏览器连接到Cassandra节点并且发送成员修改已加入或者离开集群。

5.5 缩放集群

当新的节点添加到系统中，他被分配一个token，这样就可以减轻负载过重的节点。这导致了新节点拆分其他节点之前负责的范围。操作员使用命令行或者Cassandra web仪表盘，Cassandra启动算法从系统中的任何其他的节点上初始化。放弃数据的节点使用核-核复制技术将数据传输到新节点。运行经验表明，数据可以在40MB/s的速度在单个节点传输。我们正在努力改进这一点，通过多个副本参与启动传输，从而并行化工作，类似于Bittorrent。

5.6 本地持久化

Cassandra系统信任本地文件系统以进行持久化。数据在磁盘上的表示使用使用有效的数据检索方式。写操作包括写入提交日志用于持久性和可恢复性并且更新内存的数据结构。写入到内存的数据结构只有在成功的写入提交日志之后才会执行。我们在每个机器上有专用的磁盘用于提交日志因此所有写入提交日志是连续的，因此我们最大化磁盘的吞吐量。当内存中的数据结构超过特定的阈值（基于数据大小和对象数量计算的），它将自己存储到磁盘。这个写操作是在机器所配备的许多商品磁盘上上的一个进行的。所有写操作都是顺序写入磁盘的，并且还生成一个索引，一遍根据row key高效的进行查找。这些索引页随着文件数据一起被持久化。随着时间推移，许多这样的文件可能存在于磁盘上，并且归并程序在背景中运行以核对文件的不同合并到一个树中 。这个过程非常类似bigtable系统中的压缩过程。

一个典型的读取操作在查看磁盘文件之前，首先查询内存中的数据结构。这些文件是按照从新到旧的顺序来进行查看的。当进行磁盘查找时，我们可以查找多个磁盘上文件的一个key。为了防止查找到不包含键的文件，一个bloom过滤器，总结文件中的键，他存储在每个数据文件中也存储在内存中。首先要查看bloom过滤器，以检查正在查找的键是否存在于给定的文件中。列族中的键可能有多列。需要一些特殊的索引来检查离键较远的列。为了防止扫描磁盘上的每一列，我们维护索引，使我们能能跳转到磁盘上正确的快进行检索。当给定键被序列化并且写到磁盘时，我们在256K区块的边界生成索引。这个参数是可配置的，但是256K对于我们生产环境工作的很好。

5.7 实现细节

SEDA（Staged event-driven architecture）事件驱动架构是一种为高并发和高可扩展性系统设计的架构模型

1. 阶段（Stage）： 每个阶段是一个独立的处理单元，通常有自己的线程池、任务队列和资源管理机制。一个阶段只负责执行特定的功能，比如接受请求、解析请求、处理数据、返回响应等。这样可以避免系统出现“瓶颈”或者某个阶段过载的问题。
2. 事件驱动： 各个阶段通过事件传递任务，即每个阶段完成任务后，会生成一个事件，并将其放入下一个阶段的队列中，从而实现任务的分布式处理。通过事件驱动机制，SEDA能够在负载较大时有效缓解系统压力，并通过异步非阻塞方式提升性能。
3. 资源管理： 每个阶段的线程池和任务队列可以动态调整，系统可以根据负载自动调节阶段资源，避免因单个阶段过载影响整体系统性能。这样，SEDA可以灵活地应对负载的变化。
4. 流控： 通过对每个阶段的任务队列进行监控，SEDA可以动态调整资源分配和处理速度。当一个阶段的负载过高时，可以通过减少进入该阶段的任务数量来缓解压力，从而保证系统的平稳运行。

Cassandra的进程在单个机器上主要由以下的抽象构成：分区模块，集群成员和失败探测模块以及存储引擎模块。每个模块都依赖于事件驱动的基层，其中消息处理管道和任务管道沿着SEDA架构的路线分成多个阶段。这些模块都是使用java从头开始实现的。集群成员和故障检测模块，构建在网络层的上方，它使用nio。系统控制消息基于UDP的消息传递，而用于复制和请求路由相关的应用信息依赖于TCP。请求和路由模块使用特定的状态机进行实现。当读写请求到到达集群中的任何节点，集群中的状态机通过以下几种变化 1 定义拥有key数据的节点 2 路由请求到节点并且等待响应等待的到来 3 如果响应没有在配置的超时内到达，请求返回失败并返回到客户端 4 根据时间戳找出最近的响应 5 如果没有找到最新的数据片，则安排对数据的修复。为了说明我们不讨论失败的场景。系统可以配置执行同步或者异步操作。对于确定需要高吞吐量的系统，我们依赖于异步的复制。在这里进入系统的写操作远远大于进入系统的读操作。在同步案例中，在返回给客户端之前，我们等待响应的法定人数 。

在任何日志系统中，需要存在一种清楚日志条目的机制。在Cassandra中我们使用滚动提交日志其中当旧的日志提交超过特定的可配置大小时，就会生成一个新的提交日志。我们发现在生产环境中滚动提交日志大小设置在128MB能工作的非常好。每个提交日志都有一个header，他基本上是一个位向量，通常比系统处理的列组数量要多。在我们的实现中，我们有一个内存中的数据结构和一个按列族生成的数据文件。每次将特定内存中数据结构存储到磁盘时，我们都会提交日志中设置它的位，表示该列组已经成功持久化到磁盘。这表示信息片已经提交了。这些位向量是每个提交日志，也保存在内存中，每次滚动提交日志的所有向量。如果认为所有数据都成功持久化到磁盘啧删除这些提交日志。写入提交日志的操作可以是正常模式也可以是快速同步模式。在快速同步模式中对提交日志写操作将被缓冲。在这种模式下，我们还以缓冲的方式将内存中的数据结构转储到磁盘。传统的数据库不是为处理特别高的写入吞吐而设计的。传统的数据库不是为了高吞吐量而设计的。由于转储到磁盘的文件永远不会发生变化，因此在读取它们时不需要加锁。因此，我们不需要处理或处理存在于基于B-Tree的数据库实现中的并发问题。

Cassandra系统基于主键索引索引所有的数据。磁盘上的数据文件被分解成一系列的块。每个块包含了最多128个key，通过块索引进行切分。块索引捕获到块中的相关key的偏移和数据的大小。当将内存中的数据结构转储到磁盘时，将生成一个块索引，并将其偏移量作为索引写入磁盘。这个索引维在内存中以进行快速访问。一个典型的读取操作总是第一步查阅在内存中的数据。如果发现数据就返回给应用，因为内存中包含任何键的新数据。如果没有找到，那么我们执行相反的事件顺序对磁盘上的所有数据进行io。因为我们总是找寻最新的数据，如果我们找到了 数据就返回。数据文件的数量将会随着时间增长。我们执行压缩过程，非常类似Bigtable系统，他合并多个文件为一个；本质是对已经排序的文件进行归并排序。系统总是对相似的大小的文件进行压缩。也就是说永远不会出现一个100GB的文件被压缩为小于50gb的文件。定期的运行一个主要的亚索过程我，将所有的相关的数据文件压缩成一个大文件。这个压缩过程是一个磁盘密集型操作。可以进行很多优化不影响即将到来的读请求。

6 实践

7 结论

我们已经构建和运行了一个强大的系统，他提供可缩放，高性能，广泛的应用能力。我们可以通过经验证明可以提供低延迟的同时支持非常高的更新吞吐量。未来的工作包括增加压缩， 支持跨键原子性的支持和二级索引。