Cassandra 内部原理和底层实现
Centralized database
单机处理能力不够:
- 计算能力
- 存储量
Distributed database
Partitioning
几种策略:
- Range Partition: 根据范围进行分片，比如
North:1~1000，East:1000~2000 - List Partition: 和 Range Partition 相似，不过是定义几个包含不同 id 的分区列表
North:[3, 5, 6, 9, 17]，East:[1, 2, 10, 11, 19, 20] - Hash Partition: 根据 key 的 Hash 结果进行分片
Consistent Hashing 可以减少增减节点时的数据迁移量。采取哈希环的方式，每个 node 都维护哈希环的信息表，每个 node 都是对等的
在 Cassandra 中任意节点都可以处理客户端的请求。若发现客户端请求的数据不是本节点负责，则会查看维护的哈希环信息表，接着向那个节点请求数据然后返回给客户端
这里稍微一提，Redis 的集群实现是将整个数据库划分为 16384 个 slot，数据库中的每个键都属于某一个 slot。集群中的每个节点负责处理这 16384 个 slot 中的一部分，并且所有节点间都会互相通知自己所负责处理的 slot。也就是说对于一个 key，任意节点都能够判断出它实际存储在哪个节点中。当客户端请求某个节点，而此节点发现数据不在自身范围内的时候则会向客户端发送 MOVED，引导客户端向正确的节点发送请求。这点和 Cassandra 是不同的
Gossip Protocol
用于
- Membership
- Failure Detection
如何避免重复传播 图的标记
避免 Overhead:
- Fan Number 传播局部范围
- Time To Live(TTL) 控制传播次数
当有新节点加入时，会向某个节点索要数据，这时会获取哈希环信息。那个节点也会更新自己的哈希环信息，然后经过节点间不断通信，所有节点都会得到更新
Load Balance
1) Hash 是否均匀 2) 新节点加入会影响平衡 3) 节点处理能力不同 4) 存在热点数据
解决方案:
- virtual nodes(Amzon)
- move nodes(Cassandra) 后来又使用 virtual nodes
参考 How data is distributed across a cluster (using virtual nodes)
CAP 理论
- 一致
- 可用
- 分区容忍
在分布式系统中，由于网络等原因一定会产生分区。所以 P 是必须的，只能在 C 和 A 中进行选择
Replication
避免所有的 replicas 在一个物理节点中
Consistency
Cassandra 提供 tunable consistency，具体三个参数
- N: number of replicas
- W: consistency level of write operations
- R: consitency level of read operations
1) N 3, W 1, R 1 的情况
N 为 3，存放在 DB4 中的数据会复制 3 份(沿表寻找)。如下图中的 DB4, DB1, DB2
这是如果 client 想要写入 Value 为 2 的数据，会向三个节点都发送请求。但是由于 W 被设置为 1，只要有一个写入成功即可向 client 返回写入成功。读取向三个 replica 中的任何一个读取。所以存在读取旧数据的可能性
2) N 3, W 3, R 1
向所有的 replica node 写入，一定能够读取最新数据
3) N 3, W 1, R 3
也同样会读取到最新的数据，根据 timestamp 决定谁为最新数据
定理：若满足 W + R > N 则一定会读取到最新的数据
How to achieve eventual consistency
Read Repair
当 R 小于 N 时，有一定概率(用户设置)会向所有 replica 发送读请求。若数据不一致，则强制 replica 进行同步。缺点是如果一条数据很久不被读取，则不会发生同步
Hinted Handoff
N 3 W 2 R 2 下，会像所有 replica 发送写请求，但是只要成功两个即可。这是 client 直接请求的节点会存放一份数据，不断尝试向未写入成功的 replica node 写入。容易发生雪崩
Anti-Entropy Repair
定期进行数据同步
- To routinely maintain node health.
- To recover a node after a failure while bringing it back into the cluster.
- To update data on a node containing data that is not read frequently, and therefore does not get read repair
- To update dat aon a node that has been down
- To recover missing data or corrupted SSTables
How to detect inconsistency
Merkle Trees，写频繁时会不断进行 hash，造成 overhead