Apache Cassandra是一个开源的分布式NoSQL数据库。它提供了具有最终一致语义的分区宽列存储模型。
Cassandra的设计目标：
- 完全多主数据库副本
- 低延迟的全局可用性
- 扩展到商用硬件
- 每增加一个处理器，线性吞吐量就会增加
- 在线负载平衡和集群增长
- 分区key-oriented查询
- 灵活的schema
Apache Cassandra依赖于Amazon Dynamo分布式存储键值系统的多种技术。Dynamo系统的每个节点有三个主要组成部分：
- 在分区数据集上请求协调
- 环的成员和故障检测
- 一个本地存储引擎 Cassandra主要使用前两个集群组件，同时使用基于日志结构合并树(LSM)的存储引擎。特别地，Cassandra使用Dynamo风格：
- 使用一致哈希的数据集分区
- 使用版本化数据和可调一致性的多主（multi-master）复制
- 通过gossip协议进行分布式集群成员和故障检测
- 商用硬件的增量横向扩展
Cassandra以这种方式设计，可以满足大规模（PB级数据）关键业务存储要求。
Cassandra不仅吸收了Dynamo论文中的如何做分布式，如何做副本复制，故障容错等方面成功的经验，又吸取了Google Bigtable中的LSM单机引擎层面精华。理论扎实，工程实现靠谱，所以面世以来，不断受到人们的追捧。
Cassandra通过使用哈希函数对存储在系统中的所有数据进行分区来实现水平可伸缩性。每个分区被复制到多个物理节点，通常跨机架甚至数据中心。
Cassandra将每个节点映射到连续哈希环上的一个或多个token(令牌)，并通过将key哈希到环上然后沿一个方向“遍历”环来决定key应该放在什么位置，类似于Chord算法。一致性哈希与原始数据哈希的主要区别在于，当要哈希到的节点(桶)数量发生变化时，一致哈希只需移动一小部分key。
例如，如果我们有一个8个节点的集群，每个节点都有均匀间隔的token(令牌)，并且副本因子(RF)为3，那么要找到一个key的所属节点，我们首先对该key进行哈希以生成一个token(即key的hash)，然后沿顺时针方向“walk”（走，遍历），直到遇到三个不同的节点，这时我们找到了该key的所有副本。这个过程可以用下图表示：
每个物理节点有多个令牌
如果你许多物理节点来分散数据，则简单的单令牌一致哈希可以很好地工作。但是如果令牌间隔均匀而物理节点数量很少，此时如果新增一个节点的话就没有令牌可选，以使环保持平衡。Cassandra试图避免令牌不平衡，因为令牌范围不均衡会导致请求负载不均衡。 例如，在前面的示例中，无法在不引起不平衡的情况下添加第九个令牌。
Dynamo论文中提倡使用“虚拟节点”来解决这种不平衡问题。虚拟节点通过将令牌环中的多个令牌分配给每个物理节点来解决该问题。通过允许单个物理节点在环中占据多个位置，我们可以使小型集群看起来更大，因此即使添加单个物理节点，我们也可以使其看起来像我们添加了更多节点。
Cassandra引入了一些术语来处理这些概念：
- Token：dynamo风格的哈希环上的单个位置
- Endpoint：网络上的单个物理IP和端口
- Host ID：单个“物理”节点的唯一标识符，通常存在于一个端点并包含一个或多个令牌
- Virtual Node：哈希环上的一个令牌，由具有相同的主机ID的相同的物理节点拥有
从Tokens到Endpoints的映射形成了Token Map，Cassandra以此来会跟踪哪些环位置映射到哪些物理端点。
例如，在下图中，通过为每个节点分配两个令牌，我们可以仅使用4个物理节点来表示8个节点的集群：
说了这么多，什么意思呢？简单的回顾一下：
token代表哈希环（hash ring）上的一个位置，这这个环上，两个token之间有一个区间范围，这也是key的范围或者理解为哈希值的区间范围。从token到node的映射被称之为Token Map。
上面第一幅图中，描述的是假设你有足够的物理机，再假设副本因子是3，那么1节点对应1个token，这样就是8个节点8个token，形成了如下区间范围：
(t1,t2] -> {n2,n3,n4}
(t2,t3] -> {n3,n4,n5}
(t3,t4] -> {n4,n5,n6}
(t4,t5] -> {n5,n6,n7}
(t5,t6] -> {n6,n7,n8}
(t6,t7] -> {n7,n8,n1}
(t7,t8] -> {n8,n1,n2}
(t8,t1] -> {n1,n2,n3}假设hash("foo")落在了(t1,t2]区间，那么该key的3个副本放置的位置应该是n2,n3,n4
此时，如果我要新加一个节点n9，就没有token可选了
如果物理机不够怎么办呢？
假设物理机只有4台，但是token的范围区间是固定的，那么4个节点8个token，为了保持平衡，必须1个节点对应2个token
为了保持平衡，只能将虚拟节点均匀分布在物理节点之间，因为是按顺时针方向往前走的，数据最终还是要放到物理节点上的
于是形成了如下区间范围：
(t1,t2] -> {n1,n2,n3}
(t2,t3] -> {n2,n3,n4}
(t3,t4] -> {n3,n4,n1}
(t4,t5] -> {n4,n1,n2}
(t5,t6] -> {n1,n2,n3}
(t6,t7] -> {n2,n3,n4}
(t7,t8] -> {n3,n4,n1}
(t8,t1] -> {n4,n1,n2}每个物理节点对应两个token的好处：
- 当添加一个新节点时，它从环中的其他节点接收大约相同数量的数据，从而使数据在集群中均匀分布。
- 当删除一个节点时，它丢失的数据与环中的其他成员丢失的数据大致相同，这再次保持了数据在集群中的均匀分布。
- 如果某个节点变得不可用，查询负载(特别是支持令牌的查询负载)将均匀地分布在许多其他节点上。
坏处：
- 每个令牌在令牌环上引入最多2 * (RF - 1)的其他邻居，这意味着在令牌环的一部分失去可用性时，会出现更多的节点故障组合
- 集群范围的维护操作通常会变慢。 例如，随着每个节点令牌数量的增加，集群必须执行的离散修复操作的数量也会增加。
- 跨令牌范围的操作性能可能会受到影响。