一、Cassandra框架

图1 Cassandra

Cassandra是社交网络理想的数据库，适合于实时事务处理和提供交互型数据。以Amazon的完全分布式的Dynamo为基础，结合了Google BigTable基于列族（Column Family）的数据模型，P2P去中心化的存储，目前twitter和digg中都有使用。

在CAP特性上，HBase选择了CP，Cassandra更倾向于AP，而在一致性上有所减弱。

Cassandra的类Dynamo特性有以下几点：

l 对称的，P2P架构

n 无特殊节点，无单点故障

l 基于Gossip的分布式管理

l 通过分布式hash表放置数据

n 可插拔的分区

n 可插拔的拓扑发现

n 可配置的放置策略

l 可配置的，最终一致性

类BigTable特性：

l 列族数据模型

n 可配置，2级maps，Super Colum Family

l SSTable磁盘存储

n Append-only commit log

n Mentable (buffer and sort)

n 不可修改的SSTable文件

l 集成Hadoop

二、 Cassandra数据模型

Colum / Colum Family, SuperColum / SuperColum Family

Column是数据增量最底层（也就是最小）的部分。它是一个包含名称（name）、值（value）和时间戳（timestamp）的三重元组。

下面是一个用JSON格式表示的column：

{ // 这是一个Column

name: "emailAddress",

value: "arin@example.com",

timestamp: 123456789

}

需要注意的是，name和value都是二进制的（技术上指byte[]），并且可以是任意长度。

与HBase相比，除了Colum/Colum Family外，Cassandra还支持SuperColum/SuperColum Family。

SuperColum与Colum的区别就是，标准Column的value是一个“字符串”，而 SuperColumn的value是一个包含多个Column的map，另一个细微的差别是：SuperColumn没有时间戳。

{ // 这是一个SuperColumn

name: "homeAddress",

// 无限数量的Column

value: {

street: {name: "street", value: "1234 x street", timestamp: 123456789},

city: {name: "city", value: "san francisco", timestamp: 123456789},

zip: {name: "zip", value: "94107", timestamp: 123456789},

}

}

Column Family（CF）是某个特定Key的Colum集合，是一个行结构类型，每个CF物理上被存放在单独的文件中。从概念上看，CF像数据库中的Table。

SuperColum Family概念上和Column Family（CF）相似，只不过它是Super Colum的集合。

Colum排序

不同于数据库可以通过Order by定义排序规则，Cassandra取出的数据顺序是总是一定的，数据保存时已经按照定义的规则存放，所以取出来的顺序已经确定了。另外，Cassandra按照column name而不是column value来进行排序。

Cassandra可以通过Colum Family的CompareWith属性配置Colume值的排序，在SuperColum中，则是通过SuperColum Family的CompareSubcolumnsWith属性配置Colum的排序。

Cassandra提供了以下一些选：BytesType，UTF8Type，LexicalUUIDType，TimeUUIDType，AsciiType， Column name识别成为不同的类型，以此来达到灵活排序的目的。

三、分区策略

Token，Partitioner

Cassandra中，Token是用来分区数据的关键。每个节点都有一个第一无二的Token，表明该节点分配的数据范围。节点的Token形成一个Token环。例如使用一致性HASH进行分区时，键值对将根据一致性Hash值来判断数据应当属于哪个Token。

 Token Ring

分区策略的不同，Token的类型和设置原则也有所不同。 Cassandra (0.6版本)本身支持三种分区策略：

RandomPartitioner：随机分区是一种hash分区策略，使用的Token是大整数型(BigInteger)，范围为0~2^127，Cassandra采用了MD5作为hash函数，其结果是128位的整数值(其中一位是符号位，Token取绝对值为结果)。因此极端情况下，一个采用随机分区策略的Cassandra集群的节点可以达到2^127+1个节点。采用随机分区策略的集群无法支持针对Key的范围查询。

OrderPreservingPartitioner：如果要支持针对Key的范围查询，那么可以选择这种有序分区策略。该策略采用的是字符串类型的Token。每个节点的具体选择需要根据Key的情况来确定。如果没有指定InitialToken，则系统会使用一个长度为16的随机字符串作为Token，字符串包含大小写字符和数字。

CollatingOrderPreservingPartitioner：和OrderPreservingPartitioner一样是有序分区策略。只是排序的方式不一样，采用的是字节型Token，支持设置不同语言环境的排序方式，代码中默认是en_US。

分区策略和每个节点的Token(Initial Token)都可以在storage-conf.xml配置文件中设置。

bloom-filter, HASH

Bloom Filter是一种空间效率很高的随机数据结构，本质上就是利用一个位数组来表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有误差的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合，而在能容忍低错误率的场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。

原理：位数组 + K个独立hash（y）函数。将位数组中hash函数对应的值的位置设为1，查找时如果发现所有hash函数对应位都是1说明存在，很明显这个过程并不保证查找的结果是完全正确的。

在Cassandra中，每个键值对使用1Byte的位数组来实现bloom-filter。

Bloom Filter

四、副本存储

Cassandra不像HBase是基于HDFS的分布式存储，它的数据是存在每个节点的本地文件系统中。

Cassandra有三种副本配置策略：

1) SimpleStrategy （RackUnawareStrategy）：

副本不考虑机架的因素，按照Token放置在连续下几个节点。如图3所示，假如副本数为3，属于A节点的数据在B.C两个节点中也放置副本。

2) OldNetworkTopologyStrategy （RackAwareStrategy）:

考虑机架的因素，除了基本的数据外，先找一个处于不同数据中心的点放置一个副本，其余N-2个副本放置在同一数据中心的不同机架中。

3) NetworkTopologyStrategy （DatacenterShardStrategy）：

将M个副本放置到其他的数据中心，将N-M-1的副本放置在同一数据中心的不同机架中。

五、网络嗅探

网络嗅探主要用来计算不同host的相对距离，进而告诉Cassandra网络拓扑结构，以便更高效地对用户请求进行路由。主要有三种配置策略：

1) org.apache.cassandra.locator.SimpleSnitch：

将不同host逻辑上的距离（Cassandra Ring）作为他们之间的相对距离。

2) org.apache.cassandra.locator.RackInferringSnitch:

相对距离是由rack和data center决定的，分别对应ip的第3和第2个八位组。即，如果两个节点的ip的前3个八位组相同，则认为它们在同一个rack（同一个rack中不同节点，距离相同）；如果两个节点的ip的前两个八位组相同，则认为它们在同一个数据中心（同一个data center中不同节点，距离相同）。

3) org.apache.cassandra.locator.PropertyFileSnitch:

相对距离是由rack和data center决定的，且它们是在配置文件cassandra-topology.properties中设置的。

六、一致性

在一致性上，Cassandra采用了最终一致性，可以根据具体情况来选择一个最佳的折衷，来满足特定操作的需求。Cassandra可以让用户指定读/插入/删除操作的一致性级别，一致性级别有多种，如图5所示。

图5 Cassandra一致性级别

注：一致性级别是由副本数决定，而不是集群的节点数目决定。

Quorum NRW

• N: 复制的节点数量，即副本数
• R: 成功读操作的最小节点数
• W: 成功写操作的最小节点数

Quorum协议中，R 代表一次成功的读取操作中最小参与节点数量，W 代表一次成功的写操作中最小参与节点数量。R + W>N ，则会产生类似quorum 的效果。该模型中的读(写)延迟由最慢的 R(W)复制决定，为得到比较小的延迟，R和W有的时候的和比N小。

Quorum协议中，只需W + R > N，就可以保证强一致性。因为读取数据的节点和被同步写入的节点是有重叠的。在一个RDBMS的复制模型中（Master/salve)，假如N=2,那么W=2,R=1此时是一种强一致性,但是这样造成的问题就是可用性的减低，因为要想写操作成功，必须要等 2个节点的写操作都完成以后才可以。

在分布式系统中，一般都要有容错性，因此N一般大于3的，此时根据CAP理论，我们就需要在一致性和分区容错性之间做一平衡，如果要高的一致性，那么就配置N=W，R=1,这个时候可用性就会大大降低。如果想要高的可用性，那么此时就需要放松一致性的要求，此时可以配置W=1，这样使得写操作延迟最低，同时通过异步的机制更新剩余的N-W个节点。

当存储系统保证最终一致性时，存储系统的配置一般是W+R<=N，此时读取和写入操作是不重叠的，不一致性的窗口就依赖于存储系统的异步实现方式，不一致性的窗口大小也就等于从更新开始到所有的节点都异步更新完成之间的时间。

一般来说，Quorum中比较典型的NRW为（3,2,2）。

维护最终一致性

Cassandra 通过4个技术来维护数据的最终一致性，分别为逆熵（Anti-Entropy），读修复（Read Repair），提示移交（Hinted Handoff）和分布式删除。

1) 逆熵

这是一种备份之间的同步机制。节点之间定期互相检查数据对象的一致性，这里采用的检查不一致的方法是 Merkle Tree；

2) 读修复

客户端读取某个对象的时候，触发对该对象的一致性检查：

读取Key A的数据时，系统会读取Key A的所有数据副本，如果发现有不一致，则进行一致性修复。

如果读一致性要求为ONE，会立即返回离客户端最近的一份数据副本。然后会在后台执行Read Repair。这意味着第一次读取到的数据可能不是最新的数据；如果读一致性要求为QUORUM，则会在读取超过半数的一致性的副本后返回一份副本给客户端，剩余节点的一致性检查和修复则在后台执行；如果读一致性要求高(ALL)，则只有Read Repair完成后才能返回一致性的一份数据副本给客户端。可见，该机制有利于减少最终一致的时间窗口。

3) 提示移交

对写操作，如果其中一个目标节点不在线，先将该对象中继到另一个节点上，中继节点等目标节点上线再把对象给它：

Key A按照规则首要写入节点为N1，然后复制到N2。假如N1宕机，如果写入N2能满足ConsistencyLevel要求，则Key A对应的RowMutation将封装一个带hint信息的头部（包含了目标为N1的信息），然后随机写入一个节点N3，此副本不可读。同时正常复制一份数据到N2，此副本可以提供读。如果写N2不满足写一致性要求，则写会失败。 等到N1恢复后，原本应该写入N1的带hint头的信息将重新写回N1。

4) 分布式删除

单机删除非常简单，只需要把数据直接从磁盘上去掉即可，而对于分布式，则不同，分布式删除的难点在于：如果某对象的一个备份节点 A 当前不在线，而其他备份节点删除了该对象，那么等 A 再次上线时，它并不知道该数据已被删除，所以会尝试恢复其他备份节点上的这个对象，这使得删除操作无效。Cassandra 的解决方案是：本地并不立即删除一个数据对象，而是给该对象标记一个hint，定期对标记了hint的对象进行垃圾回收。在垃圾回收之前，hint一直存在，这使得其他节点可以有机会由其他几个一致性保证机制得到这个hint。Cassandra 通过将删除操作转化为一个插入操作，巧妙地解决了这个问题。

七、存储机制

Cassandra的存储机制借鉴了Bigtable的设计，采用Memtable和SSTable的方式。

CommitLog

和HBase一样，Cassandra在写数据之前，也需要先记录日志，称之为Commit Log，然后数据才会写入到Column Family对应的MemTable中，且MemTable中的数据是按照key排序好的。SSTable一旦完成写入，就不可变更，只能读取。下一次Memtable需要刷新到一个新的SSTable文件中。所以对于Cassandra来说，可以认为只有顺序写，没有随机写操作。

MenTable

MemTable是一种内存结构，当数据量达到块大小时，将批量flush到磁盘上，存储为SSTable。这种机制，相当于缓存写回机制(Write-back Cache)，优势在于将随机IO写变成顺序IO写，降低大量的写操作对于存储系统的压力。所以我们可以认为Cassandra中只有顺序写操作，没有随机写操作。

SSTable

SSTable是Read Only的，且一般情况下，一个CF会对应多个SSTable，当用户检索数据时，Cassandra使用了Bloom Filter，即通过多个hash函数将key映射到一个位图中，来快速判断这个key属于哪个SSTable。

为了减少大量SSTable带来的开销，Cassandra会定期进行compaction，简单的说，compaction就是将同一个CF的多个SSTable合并成一个SSTable。在Cassandra中，compaction主要完成的任务是：

1） 垃圾回收： cassandra并不直接删除数据，因此磁盘空间会消耗得越来越多，compaction 会把标记为删除的数据真正删除；

2） 合并SSTable：compaction 将多个 SSTable 合并为一个（合并的文件包括索引文件，数据文件，bloom filter文件），以提高读操作的效率；

3） 生成 MerkleTree：在合并的过程中会生成关于这个 CF 中数据的 MerkleTree，用于与其他存储节点对比以及修复数据。

详细存储数据结构参考 http://www.ibm.com/developerworks/cn/opensource/os-cn-cassandraxu2

附

单体、模块化

Cassandra和HBase的一个重要区别是， Cassandra在每个节点是是一个单 Java 进程，而完整的HBase 解决方案却由不同部分组成：有数据库进程本身，它可能会运行在多个模式；一个配置好的 hadoop HDFS 分布式文件系统，以及一个 Zookeeper 系统来协调不同的 HBase 进程。

同类文章：

cassandra入门

Cassandra 分布式数据库 数据结构与数据读写

Cassandra 分布式数据库 配置、启动与集群

Apache Cassandra 数据库

分布式Key-Value存储系统Cassandra入门