System|分布式|Cassandra

Cassandra思想和Dynamo差不多，还吸收了Bigtable的实现。因为是Dynamo+Bigtable，所以号称比Bigtable套娃的HBase性能高很多。

Reference: Cassandra - A Decentralized Structured Storage System

数据模型

在行方面，对行操作原子性。

在列方面，提供了simple和super两种col family，super就是嵌套的col family

查询的时候就是column family : (super column) : qualifier

和bigtable除了多了一层列之外几乎一模一样，干脆复制算了

API

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

columnName可以随便指列的任何层次

架构

一致性Hash改进

和Dynamo的虚拟节点改进采用不同策略，Cassandra会分析负载情况，并移动低负载的节点使其负载提高。为了方便移动还用了order preserving hash function，这样还能便于进行范围查询。

后来据说真香，还是用了虚拟节点

Dynamo的标答

同样是一方面处理负载均衡，一方面提供异构

备份

每个数据有N个备份，并指定key落在的节点为coordinator，不过备份机制和Dynamo做出了改变，提供了点异地容灾

• Rack unaware - 和Dynamo一样，环向下N-1
• Rack aware - 不同rack上面备份
• Datacenter aware - 不同数据中心备份

利用zookeeper选主，每个节点告诉leader自己负责的备份范围，leader协调不让某个节点负责的范围大于N-1。metadata除了本地还存在zookeeper上所以可以恢复。这个机制和Dynamo的preference list差不多，只不过放在zookeeper里多了个备份。

没有怎么看到Quorum怎么实现的，文章说by relaxing the quorum requirements as described in Section5.2，但是这节就是5.2啊。

和Dynamo一样，每个节点都具备global view。

成员

Scuttlebutt gossip 协议，交换membership以及控制状态。和Dynamo差不多

容错

Accrual Failure Detector，并不用bool告诉你节点是不是挂了，而是给出怀疑等级，这样可以适应网络条件和负载条件，更为准确。

怀疑等级为1时错误率百分之10，每提高一个级别减少十倍。节点维持滑动窗口，记录gossip路上的时间，根据gossip的延迟计算等级。

启动

选一个token(后来引入虚拟节点变成选一组)放硬盘上，然后seed节点(zookeeper配置)充当gossip桥梁。拓扑结构的改变全靠运维手动命令行。

For these reasons, it was deemed appropriate to use an explicit mechanism to initiate the addition and removal of nodes from a Cassandra instance. An administrator uses a command line tool or a browser to connect to a Cassandra node and issue a membership change to join or leave the cluster.

扩容

新节点上线时用kernel-kernel copy复制数据，怎么感觉一点都不平滑呢。估计是类似的Quorum机制。

存储

LSM tree，bloom filter也是常见的优化读手段了，基本沿用big table。

实现细节

SEDA架构实现流水线化，Staged Event Driven Architecture，SOSP 2001。把请求拆分成独立的阶段，和流水线差不多，每个阶段独立拥有自己的线程池，这样能够最大化地利用资源。顺便接着把这篇读了https://dl.acm.org/doi/pdf/10.1145/502034.502057

总结

个人感觉就是A+B论文，Dynamo+Big table，难怪只有六面，大部分细节看那两篇论文就好了，具体细节可以参考原论文。https://research.cs.cornell.edu/ladis2009/papers/lakshman-ladis2009.pdf

创新点主要有如下几个，不过发布十几年了肯定变化很多

1. order preserving hash function便于范围查找
2. 特殊的备份机制便于异地容灾
3. Accrual Failure Detector给出了更准确的衡量机制
4. SEDA架构，主流服务器都用这个
5. metadata放在zookeeper上，而不是本地或者单独的服务