Cassandra 是一个开源的、分布式的、无中心的、弹性可扩展的、高可用的、容错的、一致性可调的、面向行的数据库，它基于 Amazon Dynamo 的分布式设计和 Google Bigtable 的数据模型，由 Facebook 创建，在一些最流行的网站中得到应用。

Cassandra 可以方便管理分布在很多商业服务器节点上的非常大量的结构化数据，同时提供无单点失效的高可用服务。Cassandra目标是在几百个基础节点上运行（可能分布在不同的数据中心）。在这个规模上，大大小小的组件经常失效。Cassandra对这些失败持久状态的管理方式促使软件系统的可靠性和扩展性依赖这一服务。虽然在许多方面Cassandra类似于一个数据库，并且共享很多设计和相关实现策略，但Cassandra并不支持完整的关系数据模型；相反，它为客户提供了一个支持动态控制数据布局并且格式简单数据模型。Cassandra系统设计目标是：运行在廉价商业硬件上，高写入吞吐量处理，同时又不用以牺牲读取效率为代价。

Facebook 是世界上最大的社交网络平台，高峰时期有数以万计分布在世界各地的服务器为数百万用户提供服务。Facebook 平台在性能、可靠性、效率以及支持持续增长平台所需的高扩展性等方面对操作有着严格的要求。我们的标准操作模式是在由几千个组件组成的基础设施上进行故障处理；任何时候都总有一些小型但非常重要的服务器或网络组件会发生故障。因此，软件系统需要建立处理故障（在这种情况下故障是一种常态而非异常）的机制。为了满足上述可靠性和可扩展性的需要，Facebook 研发了 Cassandra。

相关研究

分布式数据的性能、可用性和耐受性在文件系统和数据库方面已经得到了广泛的研究。同仅支持命名空间的 P2P 存储系统相比，分布式文件系统通常都支持层级结构命名空间。像 Ficus 和 Coda 之类的系统以牺牲一致性为代价来获取高可用性。更新冲突通常使用专门的冲突解决流程来进行管理。Farsite 是一个分布式文件系统，没有使用中央服务器，通过复制来达到高可用性和扩展性。Google 文件系统（GFS）是另一个分布式文件系统，用来管理 Google 内部应用的托管状态。GFS 使用了一种简单的设计，以一个主服务器来存储所有的元数据，其余数据被分成块存储到各个块服务器上。然而 GFS 主服务器现在使用了 Chubby 抽象来进行容错处理。Bayou 是一个分布式关系数据库系统，允许断开连接下的操作并且提供最终数据一致性。在这些系统中 Bayou, Coda 和 Ficus 允许断开连接下的操作并且可以弹性处理网络中断、停电之类的问题。这些系统的冲突解决流程各有差别。例如，Coda 和 Ficus 平台提供系统级别冲突解决方案，Bayou 提供应用级别的解决方案。所有的这些都是为了保证数据的最终一致性。同这些文件系统一样，Dynamo 即使当网络断开的时候也允许读写操作的继续，并且通过不同冲突解决机制(某些是由客户端驱动的)来解决更新冲突。传统复制关系数据库的系统专注于保证复制数据强一致性的问题。虽然强一致性为应用开发者提供了一个方便的编程模型，但是这些系统在扩展性和可用性上却被限制了。这些系统不能够处理网络中断的问题，因为他们通常都提供了强一致性的保证。

Dynamo 是一个 Amazon 的存储系统，用来存储和检索用户的购物车。Dynamo 的 Gossip 基于成员算法来帮助每个节点保持其他的每个几点的信息。

Dynamo可以定义为在大多数单跳请求路由的结构化覆盖。Dynamo 使用向量时钟计划用来检测新的冲突，但偏向于一个客户端解决冲突的机制。在 Dynamo 中的一个写操作同样需要读操作进行向量时间戳的管理。这在系统需要处理高吞吐量的环境中非常受限。Bigtable 提供了结构和数据的分布式，但是依赖于一个分布式文件系统用来做持久化。

Hbase 是一种基于分布式系统的关系型数据库，而 Cassandra 是一个高性能、可靠和可扩展的列存储数据库。它们的主要区别在于数据结构和查询处理方式的不同。HBase 上的查询需要通过网络进行分布式的并行计算，而 Cassandra 则使用本地节点之间的消息传递来完成查询任务。

系统架构

Cassandra 依赖于Dynamo 分布式存储键值系统的一些技术。Dynamo系统中的每个节点都有三个主要组成部分：

• 在分区的数据集上请求协调
• 环状成员和故障检测
• 本地持久化存储引擎

对分区数据集的请求协调是指在 Dynamo 系统中，每个节点都负责处理一部分数据，而这些数据是通过哈希函数进行分区的。当客户端发出请求时，Dynamo 会根据请求中的键值来确定哪个节点负责处理该请求，并将请求转发给相应的节点进行处理。这样，Dynamo 系统就能够通过多个节点协同工作来处理大量的客户端请求，从而实现高吞吐量和低延迟。

Cassandra主要使用前两个集群组件，同时使用基于日志结构合并树(LSM)的存储引擎。特别地，Cassandra 基于 Dynamo 改进了：

• 使用一致哈希的数据集分区
• 使用版本化数据和可调一致性的多主（multi-master）复制
• 通过 gossip 协议进行分布式集群成员和故障检测
• 商用硬件的增量横向扩展

Cassandra 以这种方式设计，可以满足大规模（PB级数据）关键业务存储要求。

Cassandra 不仅吸收了 Dynamo 论文中的如何做分布式，如何做副本复制，故障容错等方面成功的经验，又吸取了 Google Bigtable 中的 LSM 单机引擎层面精华。

本地持久化

Cassandra 的数据持久化需要依赖本地文件系统。数据用一种高效读取格式存放在硬盘上。出于耐受性和可恢复性考虑，通常写操作将会涉及到提交日志写入并且更新到一个内存数据结构中。写入内存数据结构仅仅在写入提交日志成功后才会进行。我们每台机器上都有个专门磁盘用来提交日志，因为所有写入提交日志是连续的，所以可以最大限度的利用磁盘吞吐量。当内存数据结构大小（根据数据大小和数量计算得出）超过一定阈值，它将转储到磁盘上。这个写操作是在每台机器配备的许多廉价磁盘中的一个上进行的。所有写入操作写入到磁盘都是有序的，并且生成了一个基于行键可进行快速检索的索引。这些索引通常是数据文件在一起持久化的。随着时间的推移，在磁盘上可能会存在很多这样的文件，后台会有一个合并进程将这些文件合并成一个文件。这个进程和 Bigtable 系统中的压缩进程非常相似。

一个典型的读取操作在读取磁盘上文件之前首先将查询内存数据结构。文件是以文件的新旧来进行排序的。当进行磁盘检索时，我们可能需要检索磁盘上的多个文件的关键字。为了避免查找到不包含关键字的文件，我们用布隆过滤器来汇总文件中的关键字，它同样也存储在每个数据文件中并常驻内存。（检索时）首先将咨询布隆过滤器来检查搜索的关键字是否在给定的文件中。一个列簇中的关键字可能会包含很多列。所以当检索的列距离键较远时还需要利用一些特殊的索引。为了防止搜索时搜索磁盘上的每一列，我们维护列索引来帮组我们直接跳到磁盘上所取列的正确块上。由于指定键的列已经被序列化并写入到磁盘，所以我们按照每块 256K 的范围来生成索引。边界的大小是可以配置的，但是我们发现在实际产品负载环境下中，256K 大小工作良好。

数据分区

一致性哈希数据分区

Cassandra 通过使用哈希函数对存储在系统中的所有数据进行分区，实现了横向可扩展性。每个分区都被复制到多个物理节点上，通常跨越故障域，如机架甚至数据中心。由于每个副本都可以独立地接受它所拥有的每个密钥的突变，每个密钥都必须是版本的。在最初的 Dynamo 论文中，确定性的版本和矢量时钟被用来协调对一个键的并发更新，与此不同的是，Cassandra 使用了一个更简单的最后写入获胜的模型，每个突变都有时间戳（包括删除），然后数据的最新版本是 “获胜 “值。从形式上讲，Cassandra 为每条 CQL 行使用一个 Last-Write-Wins Element-Set 无冲突复制数据类型，或 Conflict-free replicated data type，以解决复制集上冲突的突变。

Cassandra 一个重要的设计特性就是持续扩展的能力。这要求动态将数据分区到集群中各个节点（即存储主机）的能力。Cassandra 整个集群上的数据分区用的是一致性哈希，但是使用了保序哈希函数来达到这一点。在一致性哈希算法中，一个散列函数输出范围被当作一个固定的圆形空间或‘环’来对待（即最大散列值之后为最小散列值）。系统中的每一个节点被赋予一个在这一空间内表示其圆环的位置的随机值。每一个数据项通过键来标识，通过散列数据项的键来确定环上的位置，然后分配到圆环上第一个离大于该条目位置最近的节点。这个节点被视为此键的坐标。应用对此键进行特化处理并且 Cassandra 使用它来进行请求路由。因此，每个节点只需对圆环上它与前任节点之间的区域负责。一致性哈希最主要的优点是离开或到达一个节点只会影响期直接毗邻节点，而其他节点不受影响。基础的一致性散列算法面临一些挑战。首先，每个节点圆环上随机位置的分配导致数据和负载分布的不均匀。第二，基础算法无视节点性能的不均匀性。通常解决这个问题有两个方法：一个是将一个节点分配给环中多个位置（就像 Dynamo 的做法），第二种就是对环上的负载信息进行分析，优先路由负载小的节点以减轻负载较重的节点负担。Cassandra 采用后一种方法，因为它能够使得设计和实现易于处理，并且有助于负载均衡做出确定的选择。

在朴素数据哈希中，通常通过将键的哈希模数除以桶数来将键分配给桶。例如，如果您想使用朴素哈希将数据分发到 100 个节点，则可能将每个节点分配到 0 到 100 之间的一个桶，将输入键模数除以 100，并将数据存储在关联的桶中。然而，在这种朴素方案中，添加一个节点可能会使几乎所有映射失效。

Cassandra 则将每个节点映射到连续哈希环上的一个或多个令牌，并通过将键散列到环上然后“沿着”环向一个方向行走来定义所有权，类似于 Chord 算法。一致性哈希与朴素数据哈希的主要区别在于，当要散列到的节点（桶）数量发生变化时，一致性哈希只需移动少量键。

例如，如果我们有一个具有均匀分布的令牌的8节点集群， 和复制因子 （RF） 为 3，然后查找键我们首先对该键进行哈希处理以生成令牌（这只是哈希的 key），然后我们以顺时针的方式“走”环，直到我们遇到三个不同的节点，此时我们已经找到了所有 该密钥的副本。此 8 节点群集示例具有 gRF=3 可以可视化如下：

物理节点与多个令牌

在 Cassandra 中，每个物理节点可以拥有多个令牌，这些令牌在哈希环上占据多个位置。这种方法称为“虚拟节点”，它通过为每个物理节点分配多个令牌来解决不平衡问题。通过允许单个物理节点在环中占据多个位置，我们可以使小集群看起来更大，因此即使添加单个物理节点，我们也可以使其看起来像添加了更多节点，从而在添加甚至单个节点时从更多环邻居那里获取更多较小的数据块。

Cassandra 引入了一些术语来处理这些概念：

• 主机 ID：单个“物理”节点的唯一标识符，通常位于一个 gEndpoint 处并包含一个或多个 gTokens。
• 虚拟节点（或 vnode）：由同一物理节点拥有的哈希环上的 gToken，具有相同的 gHost ID。

令牌到端点的映射产生了令牌映射，在其中 Cassandra 跟踪哪些环位置映射到哪些物理端点。例如，在下图中，我们可以通过为每个节点分配两个令牌来表示仅使用 4 个物理节点的 8 个节点集群:

每个令牌最多引入2 x（rf -1）令牌环上的其他邻居，这意味着节点故障的组合有更多的组合，我们在某些令牌环中失去了可用性。您拥有的令牌越多，停电的可能性就越高。

整个群集维护操作通常会放慢速度。例如，随着每个节点的令牌数量的增加，群集必须增加的离散维修操作数量。

跨越令牌范围的操作的性能可能会受到影响。

请注意，在Cassandra 2.x中，唯一可用的令牌分配算法是选择随机令牌，这意味着要保持平衡每个节点的默认令牌数必须很高，在256处。共同增加了无法获得的风险。这就是为什么在3.x +中添加了新的确定性令牌分配器，该分配器巧妙地选择令牌，以使环具有最佳平衡，同时需要每个物理节点的令牌数量要少得多。

每个物理节点的多个令牌提供了以下好处：

• 当添加新节点时，它从环中其他节点接受大约相等数量的数据，从而在整个集群中实现数据均匀分布。
• 当一个节点被撤销时，它将数据大致均匀地丢失给环中其他成员，再次保持整个集群中数据的均匀分布。
• 如果一个节点不可用，则查询负载（特别是令牌感知查询负载）会均匀地分布到许多其他节点上。

多主复制

Cassandra 将每个数据分区复制到集群中的许多节点，以保持高可用性和持久性。当发生变化时，协调器对分区键进行散列以确定数据所属的令牌范围，然后根据 Replication Strategy 将突变复制到该数据的副本。

所有复制策略都有复制因子（ RF ）的概念，它向Cassandra指示分区应该存在多少个副本。例如，使用 RF=3 keyspace，数据将被写入三个不同的副本。副本总是被选择为使得它们是不同的物理节点，这通过在需要时跳过虚拟节点来实现。复制策略还可以选择跳过存在于相同故障域（诸如机架或数据中心）中的节点，使得 Cassandra 集群可以容忍整个机架甚至节点的数据中心的故障。

Cassandra支持可插拔复制策略，该策略确定哪些物理节点充当给定令牌范围的副本。数据的每个键空间都有自己的复制策略。所有生产部署都应使用 NetworkTopologyStrategy ，而 SimpleStrategy 复制策略仅适用于测试尚不了解群集数据中心布局的群集。

NetworkTopologyStrategy 需要为群集中的每个数据中心指定复制因子。即使您的群集只使用单个数据中心，建议使用 NetworkTopologyStrategy 而不是 SimpleStrategy ，以便在需要时更容易将新的物理或虚拟数据中心添加到群集。

还有其它非常方便的复制策略。

数据版本

Cassandra 使用变化时间戳版本控制来保证数据的最终一致性。具体而言，进入系统的所有变化都是利用从客户端时钟提供的时间戳来进行的，或者在没有客户端提供的时间戳的情况下利用从协调器节点的时钟提供的时间戳来进行的。更新根据上次写入成功的冲突解决规则解决。Cassandra 的正确性取决于这些时钟，因此请确保运行正确的时间同步进程，如 NTP。

Cassandra 将单独的突变时间戳应用于 CQL 分区中的每一行的每一列。行通过主键保证是唯一的，并且行中的每一列根据最后写入成功冲突解决方案来解决并发变异。这意味着对分区内不同主键的更新实际上可以在没有冲突的情况下解决！此外，CQL 集合类型（如映射和集合）使用相同的无冲突机制，这意味着映射和集合的并发更新也可以保证解决。

复制副本同步

由于Cassandra中的副本可以独立地接受变化，因此某些副本可能具有比其他副本更新的数据。Cassandra有许多尽力而为的技术来驱动副本的收敛，包括读取路径中的 Replica read repair <read-repair> 和写入路径中的 Hinted handoff <hints> 。

然而，这些技术只是尽力而为，为了保证最终的一致性，Cassandra实现了 anti-entropy repair <repair> ，其中副本在其数据集上计算分层哈希树，称为Merkle树，然后可以在副本之间进行比较，以识别不匹配的数据。像最初的Dynamo论文一样，Cassandra支持完全修复，其中副本散列其整个数据集，创建Merkle树，将它们发送给彼此并同步任何不匹配的范围。

与原始的 Dynamo 论文不同，Cassandra 还实现了子范围修复和增量修复。子范围修复允许 Cassandra 通过创建仅跨越部分数据范围的大量树来提高哈希树的能力（可能降低到单个分区级别）。增量修复允许 Cassandra 只修复自上次修复以来发生更改的分区。

可调整的一致性

Cassandra 通过一致性级别支持一致性和可用性之间的每操作权衡。Cassandra 的一致性级别是Dynamo的 R + W > N 一致性机制的一个版本，其中操作员可以将必须参与读取（ R ）和写入（ W ）的节点数量配置为大于复制因子（ N ）。在 Cassandra 中，您可以从通用一致性级别菜单中选择，这允许操作员在不知道复制因子的情况下选择 R 和 W 行为。通常，当读取一致性级别包含足够的节点以保证与写入一致性级别的仲裁交集时，写入将对后续读取可见。

还允许很多不同的一致性级别。

故障检测

Cassandra 通过使用 Gossip 来实现分布式集群成员身份和故障检测。Gossip 是一种用于在分布式系统中传播节点信息的算法。在 Cassandra 中，每个节点都会定期与其他节点通信，以交换关于集群中其他节点的信息。这些信息包括节点的状态（如是否在线）、令牌分配情况以及其他元数据。

当一个节点与其他节点通信时，它会将自己所知道的关于集群中所有节点的信息发送给对方。接收到信息的节点会将其与自己所知道的信息进行比较，并更新自己的信息。这样，每个节点都能够通过与其他节点通信来获取关于集群中所有节点的最新信息。

如果一个节点在一段时间内未能与其他节点通信，则该节点会被标记为不可用，并且集群中的其他节点会停止将请求转发给该节点。这样，Cassandra 就能够快速检测到故障并将请求重新路由到可用的副本上，从而保证了系统的高可用性。

Gossip 是形成环成员资格的基础，但故障检测器最终决定节点是 UP 还是 DOWN 。Cassandra 中 的每个节点都运行 Phi Accrual Failure Detector 的一个变体，其中每个节点都在不断地独立决定其对等节点是否可用。该决定主要基于接收到的心跳状态。例如，如果一个节点在一定时间内没有看到来自节点的心跳增加，故障检测器就会“定罪”该节点，此时 Cassandra 将停止向其路由读取（写入通常会写入提示）。如果/当节点再次开始心跳时，Cassandra 将尝试联系并连接，如果它可以打开通信通道，它将标记该节点为可用。

商业上的扩展不重要，就不写了。

总结

Cassandra 的数据模型与传统的关系型数据库（RDBMS）有很大的不同，它没有固定的表结构，也没有预定义的约束和索引。Cassandra 的数据模型更加灵活和动态，可以根据业务需求随时添加或删除列，也可以支持复杂的数据类型，如列表、集合、映射等。但是，这种灵活性也带来了一些缺点，例如不支持联合查询、聚合、事务等等。在使用 Cassandra 时，需要根据应用场景进行合理的数据建模，并尽量避免产生大量稀疏或重复的数据。

Cassandra 是一种最终一致性（eventual consistency）的数据库，这意味着在某些情况下，不同节点上可能会存在不同版本的数据副本，并且需要一段时间才能达到一致状态。Cassandra 使用时间戳来解决数据冲突，并且允许用户在读写操作时指定不同级别的一致性要求。例如：

• 读操作可以指定 ONE、QUORUM、ALL 等级别，表示至少需要从一个、过半数或所有节点读取到最新版本的数据才返回结果。
• 写操作可以指定 ANY、ONE、QUORUM、ALL 等级别，表示至少需要向一个、过半数或所有节点写入成功才返回结果。

Cassandra 的最终一致性机制与强一致性（strong consistency）的数据库有很大的差异，它可以提供更高的可用性和可扩展性，并且适合处理海量并发请求。但是，这种机制也带来了一些缺点像是不能保证实时读取到最新版本的数据，在某些场景下可能会导致业务逻辑出错，等等。

本文正在参加「金石计划」