Cassandra 架构设计

Cassandra 架构设计

概览

Apache Cassandra 是一个大规模可扩展的分布式开源 NoSQL 数据库，完美适用于跨数据中心／云端的结构化数据、半结构化数据和非结构化数据，同时 Cassandra 具有灵活伸缩、高可用、错误容忍、可调的一致性等特性。

适合的场景

• 大数据量（集群模式）
• 大量的写、统计、分析
• 多数据中心
• 数据快速增长的应用

架构

关键词

KeyWord	Explain
Gossip	点对点通信协议，用以Cassandra集群中节点间交换位置和状态信息。
Partitioner	决定如何在集群中的节点间分发数据，即在哪个节点放置数据的第一个replica。
Replica placement strategy	决定在哪些节点放置每行数据的其他replica。Cassandra在集群中的多个节点存储数据的多份拷贝(replicas)来确保可靠和容错。
Snitch	定义了复制策略用来放置replicas和路由请求所使用的拓扑信息
Virtual nodes	虚拟节点, 指定数据与物理节点的所属关系
Token Ring	令牌环

Data Centers and Racks

Rack

一个逻辑集合，有多个彼此临近 node 的组成。比如一个机架上的所有物理机器。

Data Center

有多个Rack组成的逻辑集合。建议将节点部署到多个数据中心。

Gossip and Failure Detection

Gossip 是一种 p2p 协议, 用于 failure detection, 跟踪其他节点的状态，每秒运行一次。
运用 Phi Accrual Failure Detection 实现 failure detection
计算出一个结果 level of suspicion, 表示节点失败的可能性。
具有灵活性, 同时也避免了传统 heartbeat 的不可靠。可以应对只是短暂的网络拥塞。

Gossip 介绍:
Gossip 过程是由种子节点发起，当一个种子节点有状态需要更新到网络中的其他节点时，它会随机的选择周围几个节点散播消息，收到消息的节点也会重复该过程，直至最终网络中所有的节点都收到了消息。这个过程可能需要一定的时间，由于不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议。

Gossip 的优点

• 扩展性
  网络可以允许节点的任意增加和减少，新增加的节点的状态最终会与其他节点一致。

• 容错
  网络中任何节点的宕机和重启都不会影响 Gossip 消息的传播，Gossip 协议具有天然的分布式系统容错特性。

• 去中心化
  Gossip 协议不要求任何中心节点，所有节点都可以是对等的，任何一个节点无需知道整个网络状况，只要网络是连通的，任意一个节点就可以把消息散播到全网。

• 一致性收敛
  Gossip 协议中的消息会以一传十、十传百一样的指数级速度在网络中快速传播，因此系统状态的不一致可以在很快的时间内收敛到一致。消息传播速度达到了 logN。

• 简单
  Gossip 协议的过程极其简单，实现起来几乎没有太多复杂性。

Gossip 的缺陷

分布式网络中，没有一种完美的解决方案，Gossip 协议跟其他协议一样，也有一些不可避免的缺陷，主要是两个：

• 消息的延迟
  由于 Gossip 协议中，节点只会随机向少数几个节点发送消息，消息最终是通过多个轮次的散播而到达全网的，因此使用 Gossip 协议会造成不可避免的消息延迟。不适合用在对实时性要求较高的场景下。

• 消息冗余
  Gossip 协议规定，节点会定期随机选择周围节点发送消息，而收到消息的节点也会重复该步骤，因此就不可避免的存在消息重复发送给同一节点的情况，造成了消息的冗余，同时也增加了收到消息的节点的处理压力。而且，由于是定期发送，因此，即使收到了消息的节点还会反复收到重复消息，加重了消息的冗余。

Snitches

snitch 定义了集群中每个节点相对其他节点的邻近度, 以此来确定从哪个节点读取和写入。
一般采用手动定义的模式,在 cassandra.yaml 配置为 endpoint_snitch: GossipingPropertyFileSnitch
同时在 cassandra-rackdc.properties 配置当前节点的 dc 和 rack，比如:

dc=dc1
rack=rack2

Rings and Tokens

Cassandra 表示由集群管理的数据作为一个环。环中的每个节点被分配一个或多个由token 描述的数据范围，确定在环中的位置。

token

token 是用于标识每个分区的64位整数ID，范围是: 0 - 2^127
token 是一个0~2的127次方之间的一个整数，这也意味着理论上 Cassandra 可以支持 2^127 个节点）。之所以是 2^127，是因为 MD5 HASH 固定输出 128 位的数，去掉一位符号位，剩下127位。

通过 hash算法 计算 partition key 的 hash值，得到一个127位的数，然后将这个数与各节点的 token 比较来决定存储到哪个节点上。它根据以下规则进行节点选择：

• 1.数据将存储到拥有最近的比key的hash值大的token的节点上；
• 2.若key的hash值比最大的token大，那将被存储到具有最小token的节点上。

在配置文件 cassandra.yaml 里，有一个配置是 initial_token，这里就是配置该节点的 token 值。该值留空时，Cassandra 会自动给该节点分配一个token ，依据以下规则：

• 1.若该节点已经被配置好准备加入集群，则 Cassandra 会根据集群现有的 token 来分配一个最平衡的 token 给该节点。很明显，分配一个 token 给新加入的节点，会让现有的某个节点减少一半的负载。若集群里有多个 token 都是一样平衡， 则它会选择一个可以分担目前存储了最多数据的节点的 token 。

• 2.若该节点还未准备好加入集群，则 Cassandra 会认为这个节点是引导节点，并分配一个固定值给它。所以若你分别单独配置两台节点，然后再尝试将它们集群，则会报告 token 重复。最好的方法应该是先单独配置第一台节点作为引导节点，然后后面的节点配置时应该也同时配置加入集群（后文说明），这样它们会自动获得一个平衡的 token。

配置文件里的 token 仅在系统第一次启动时被使用，然后该值被写入 system 文件，以后系统启动将不再从配置文件读取 token 。因此若你发现两台节点的 token 重复，你无法通过改变配置文件里的 token 来改变节点的 token 。正确的修改方法是删除自定义 token 文件夹里的所有文件，重新启动服务。

token 会直接影响集群里节点所承受的负载，我们应该尽量保证每个节点所负责的 token 范围是平衡的。若你发现节点的负载不平衡，你可以手动改变它们的 token 来让它们平衡。先计算出每台节点的 token （平均分配），然后使用 nodetool 工具改变它。下面给出一个java里计算token的方法，参数是节点数。

Virtual Nodes

早期 Cassandra 版本给每个节点只分配了一个 token 范围，添加删除节点,需要手动重新配置 token 范围。一方面繁琐的操作，另一方面会导致大量的数据迁移。
在1.2版本介绍了 virtual node 的概念简称 vnode ,原先的 token 范围被缩减为多个更小的 token 范围。每个节点包含多个 token 范围。默认每个节点产生256个 token 范围（通过 num_tokens 调节），也就是256个 vnode 。在2.0以后默认开启。
在性能差的节点上, 可以适当减少 num_tokens 的值。
org.apache.cassandra.dht.tokenallocator.ReplicationAwareTokenAllocator用于计算节点的token范围。

图解: 没有使用虚拟节点，Ring 环的 tokens数量 = 集群的机器数量。 比如上面一共有6个节点，所以 token 数量 = 6。
因为 副本因子 = 3，一条记录要在集群中的三个节点存在。简单地方式是计算 rowkey的hash值，落在环中的哪个 token上，第一份数据就在那个节点上, 剩余两个副本落在这个节点在 token 环上的后两个节点。
图中的 A,B,C,D,E,F 是 key 的范围，真实的值是 hash环空间，比如 0~2^32 区间分成10份，每一段是 2^32的 1/10 。
Note 1 包含 A，F，E 表示 key 范围在 A，F，E 的数据会存储到 Note 1 上，以此类推。

Rings Without Virtual Nodes

手工为集群中每个节点计算和分配一个 token。每个 token 决定了节点在环中的位置以及节点应当承担的一段连续的数据 hash 值的范围，每个节点分配了一个单独的 token 代表环中的一个位置，每个节点存储将row key 映射为 hash 值之后落在该节点应当承担的唯一的一段连续的 hash 值范围内的数据。每个节点也包含来自其他节点的 row 的副本。

Rings With Virtual Nodes

允许每个节点拥有多个较小的不连续的 hash 值范围，集群中的节点使用了虚拟节点，虚拟节点随机选择且不连续。数据的存放位置也由 row key 映射而得的hash值确定，但是是落在更小的分区范围内。

The Benefit of Using Rings with virtual nodes

• 无需为每个节点计算、分配token
• 添加移除节点后无需重新平衡集群负载
• 减少大量的大量的数据迁移
• 重建故障节点更快

Partitioners

partitioners 决定数据存放在哪个 vnode 上。它是一个 hash 函数，计算每行的 partition key 的 hash 值。
代码在 org.apache.cassandra.dht 包里,目前主要用 Murmur3Partitioner
DHT即为distributed hash table。

Replication Strategies

第一份复制存在对应 vnode 中。其他复制的存放位置由 replica strategy (或叫replica placement strategy)决定。

主要有两种策略：

• SimpleStrategy
  将副本放置在环上的连续节点处，从分区器指示的节点开始。

• NetworkTopologyStrategy
  允许为每个数据中心指定不同的复制因子。在数据中心内，它将副本分配给不同的 rack，以最大限度地提高可用性。

Consistency Levels

根据 CAP理论, 一致性(C)，可用性(A)和分区容忍性(P)不可兼得。
Cassandra 通过设置读写时最少响应节点的数量，实现了可调的一致性。
可选的一致性级别：ANY, ONE, TWO, THREE, QUORUM, ALL
其中 QUORUM, ALL 是强一致性。

强一致性公式：R + W > N (R:读复制数， W:写复制数，N:复制因子)

Queries and Coordinator Nodes

可以连接任一节点来执行读写操作
被连接的节点叫做 Coordinator Nodes ,需要处理读写一致性。比如：写到多个节点，从多个节点读取。

Memtables, SSTables, and Commit Log

Caching

Caching 有三种 cache:

• key cache
  缓存partiton keys到row index entries的映射，存在 jvm heap memory。

• row cache
  缓存常用的row, 存在 off-heap memory。

• counter cache
  提升counter性能，参见[Implementation of Counters]

Hinted Hando

一种写入高可用特性，当写入请求发给 coordinator 是，replica节点 可能因为种种原因不可用(网络、硬件等)，此时 coordinator 会临时保存写请求, 等到 replica节点 重新上线时再写入。

coordinator 会临时保存写请求, 默认保留两个小时

基本流程

基本流程: 点对点分布式系统，集群中各节点平等，数据分布于集群中各节点，各节点间每秒交换一次信息。
每个节点的 commit log 提交日志捕获写操作来确保数据持久性。
数据先被写入 MemTable (内存中的数据结构)，待 MemTable 满后数据被写入 SSTable (硬盘的数据文件)。
所有的写内容被自动在集群中 partition 分区并 replicate 复制。

库表结构: Cassandra 数据库面向行。用户可连接至集群的任意节点，通过类似 SQL 的 CQL 查询数据。
集群中，一个应用一般包含一个keyspace，一个keyspace中包含多个表。

读写请求: 客户端连接到某一节点发起读或写请求时，该节点充当客户端应用与拥有相应数据的节点间的
coordinator 协调者以根据集群配置确定环(ring)中的哪个节点应当获取这个请求。