Cassandra系列文章的第三篇。
在第一篇文章中提到过，Cassandra的每个节点都存储从key到node的路由信息，而且这个路由表是整个集群共同维护、修改的而非某个master修改的。如果有一个master来维护，那么想怎么分就怎么分，每个节点读取这个配置即可。但如果没有这个中心节点，相当于每个节点自己维护自己的路由配置，那么一定要保证根据一个特定的集群状态，所有节点计算出来的结果是完全一样的。并且不仅要计算自己应该存什么，还应该计算别人应该存什么，因为客户端连任何一个节点都能请求任何数据。换句话说，每个节点根据一个特定的集群状态计算出的某个节点的sharding信息应该是完全一样的。
为了达成这个目标，首先集群中的每个节点获得的集群状态应该是一致的，其次根据这个一致的状态应该用同样的逻辑来进行计算。输入和计算逻辑一样，才能保证输出一样。并且如果集群的状态发生变化时，比如有机器挂掉、新增了新机器等，为了数据的一致性，应该尽量保证路由信息不变，如果路由信息不得不改版，应该做到尽量安全切换，防止数据丢失。同时因为Cassandra是CAP中的AP系统，路由信息切换不能以暂时无法访问失去可用性为代价。
对第一个目标，获得一致的集群状态，Cassandra使用gossip协议维持其一致性。Gossip协议是一种无中心节点的分布式系统中常用的通信协议，akka等系统也用。简单来说就是每个节点周期性地随机找一个节点互相同步彼此的信息，P2P通信，很像人类社会的“gossip”因而得名。从概率上讲，集群中的状态最终是一定会收敛的，也就是说gossip协议维护的状态是最终一致性的。因为每个周期每个节点只选择1个其他节点进行通信，从概率上来说同步信息的负担不会因为集群节点数的增多而增大，不像有中心节点的系统中中心节点的负载会因为节点数变多而变高，但是集群信息收敛需要的时间也会变长。不过因为是最终一致性，实际上对性能的要求显得没那么高，因而跨机房高延迟的状态并不会导致什么太大的问题，而通常有中心节点的系统中对中心节点的响应时间有一定要求，跨机房的话性能会受到一定的影响。
分布式系统一个常见的问题是“分裂”，有中心节点的系统怕选出两个master，无中心节点的系统怕拆成两个集群。Cassandra为了防止集群被拆成两半，主要通过两个手段。第一个手段是gossip协议需要在起始阶段人工指定“种子节点”来获取初步的信息，并且一般来说需要每个节点填相同的若干个种子节点以保证在初期肯定能连到同一个集群中，此外每个gossip周期随机选其他节点同步消息时，如果随机到的不是种子节点则额外选随机一个种子节点再进行同步。这样既可以保证每个节点都能连到同一个集群中，也可以保证每个已存在的节点可以第一时间知道有新的节点加入（因为种子节点是最先知道新节点加入的）。此外gossip同步时拿到的集群节点列表是只增不减的，除非用户手动删除否则哪怕访问不到也只是标记成“无响应”，不会踢出。先保证初期能连到同一个集群中，再保证后来不会有节点退出这个集群，从而防止P2P的集群分裂。
Gossip基于消息传递，实际上整个Cassandra都是基于消息传递，或者说其实所有分布式系统也都是如此。只是不同的系统、不同的模块对消息的处理方式不同。对上层来说有同步阻塞的，有异步回调的，还可能是单向的发完就不收了。Cassandra的StorageService类中将收到的消息按照各种类型注册对应的Verb类来处理对应的消息。具体的代码细节暂时不想讲了。总的来说对gossip消息的处理就是在消息中封装自己知道的集群中每个节点的当前状态的version给对方，对方与本地信息判断，如果更新旧更新本地，如果比本地旧就把更新的信息给对方。这样两边的消息就都同步了。这里的信息有十几种，每种信息的修改都占用一个独立的自增version，这样同步数据算diff的时候根据version的差异可以传输尽量少的内容。
Gossip只维护集群节点状态信息，不负责维护其他信息。
第二个目标，根据一致的状态需要计算出一致的路由表。其实单纯只是想得出一致的路由表很容易，因为输入都一样了，代码只要写的一样输出一定是一样的……但是分配路由信息时还是要有一些原则，最基本的原则就是数据要平均分配。如果只能根据集群信息没有额外的信息的话，实际上想平均分配也只能是哈希分片。HBase根据每个region数据的大小来自动分配，过大就拆成俩。这个在无中心节点的Cassandra上实现就很难，因为一个数据是存在多个节点上的，这几个节点也不见得都有全部数据，不同节点无法计算出有一个统一、一致的拆分的临界点和时机。
数据库的哈希分片，总体上有三种。第一种是哈希值模节点数，简单方便但是一旦节点数变了就天下大乱，需要迁移特别多的数据。第二种是哈希值模一个略大的数，比如几千、几万，把数据分在这些个slot中，然后每个节点负责若干个slot。但是哪些节点维护哪些slot又是个新问题，无中心节点的redis cluster采用这种方案后，只能依赖一个外部的ruby脚本来让用户手动分配slot到节点的映射关系，确实能用，但不够美观。而第三种就是Cassandra采用的一致性哈希。
一致性哈希（consistent hashing）是分布式哈希表（distributed hash table）的一种，两者的区别很多人并没有分清，很多人把DHT等同于一致性哈希是错误的。分布式哈希表是一类技术，用来在分布式网络中存储信息。实际上对普通人来说，DHT这个词肯定要比一致性哈希、Gossip等技术更有名，因为BitTorrent和eMule等P2P下载协议使用DHT来获得更多的peer。原始的P2P下载虽然是无中心节点的，但是需要一个中心服务器来获取拥有某个文件的人的ip信息。后来BT的客户端开发者使用Kademlia算法发展出了DHT网络，eMule基于eDonkey网络也用Kademlia算法实现了自己的DHT，取前三个字母叫KAD网络。这两个技术都使每个客户端自身也存储一部分数据，这样形成一个巨大的网络，存储整个BT/ed2k网络中公开的文件索引信息不依赖之前的中心服务器。
Kademlia算法的细节可以看维基百科等资料。核心来说就是每个节点计算一个尽量唯一的id，而这个id和别的id取异或的结果就是两个节点的“距离”。虽然公网中每个节点的ip+port能唯一确定一个节点（内网用户没人权），但是因为ip+port直接二进制取异或的话距离近的全是同一个子网的容易导致要挂全挂什么的，所以会hash到更高的维度比如KAD的id是160bit的，这样距离就和物理上的距离完全无关了。对160bit的id系统来说，每个节点存储160个桶，第X个桶存所有id的前X-1位与自身id一样而第X位不一样的节点的信息。也就是说第一个桶的节点距离与自己非常大，而最后一个桶只能存那个与自己距离为1的节点。每个桶存储的节点数都有上限，这样在节省空间的同时这个节点存储的主要都是与自己距离近的点。当需要读写数据的时候，用其key算出来的哈希值（当然也会和id是同样的位数）去对应的桶找距离最近的节点，向那个节点要数据，那个节点也在自己本地的桶中找与这个哈希值更近的节点，直到某个节点找不到更近的、自己就是最近的，就存着这个数据。这种查找的方式是局部最优，也因此并不能保证数据只存了一份或者一定能读到数据，但BT/eMule只用来尽量多的找到拥有这个文件的节点，多一个是一个，因此问题不大。
Kademlia算法解决的是节点数非常多、不能把网络中的每个节点都存起来的情况。而对Cassandra来说，节点数足够小可以让每个节点都存储其他节点的信息，因此使用一致性哈希来存储数据。一致性哈希是DHT的另一种算法，把哈希值的取值空间首尾连接变成一个环，每个哈希值在环上都能找到对应的位置，数据的哈希值对应位置顺时针找下一个节点对应的哈希值的位置，就是该存放这条数据的节点（如果数据存N份就是接下来的N个节点）。这种算法的优势是如果环上增减了节点，只需要迁移环上位置上下两侧对应的数据，其他的数据不用动。总体来说哈希值是足够均匀的（Cassandra用MurMurHash来计算哈希值，速度快效果好），那么想保证数据分配在每个节点上是均匀的，就需要让每个节点的id在环上均匀分布。当节点数不够多的时候想靠随机id分布得均匀避免人工干预是不现实的，所以早期几乎都是人工指定id的。Cassandra从1.2开始支持虚拟节点vnode——每个Cassandra实例在环上注册多个节点（默认256个）。这样环上的总节点数就非常多，每个节点在一致性哈希环上负责256个区间，这样一方面每个区间的长度平均来看都更均匀，另一方面平均一下每个实例的总区间长度也足够均匀。并且可以不同实例配置不同的vnode个数来使不同硬件配置的实例分配的数据量、qps按比例有多有少。此外vnode意味着增加或者减少一个实例的时候，导数据会从几乎所有节点导，而不是只从相邻节点导，在数据总量不变的情况下，从更多的节点导可以减少导数据的时间，也可以均衡负载。
虽然vnode个数越多分配越均匀，但过多的vnode也不是好事，一方面会导致查找效率变低，另一方面在增减节点导数据的时候要导更多个区间的数据，而每个区间的数据导过来都会生成一个SSTable文件，过多的区间意味着初期节点SSTable数过多，会增加节点的负载。另外Cassandra支持多机房多个一致性哈希的环，每个机房一个，也可以针对每个机房设置数据存储不同的份数，从而实现非常自由的跨机房功能。如系列文章的第一篇所说，Cassandra是时间戳谁大谁赢的“NTP一致性”，跨机房的时间戳误差由用户自行承担，如果不在乎这个误差，那么非常好用。似乎美帝Cassandra很火也很大程度是因为美帝多机房的公司非常多。客户端在读写的时候可以配置是本地机房节点读写若干份还是全局若干份还是每个机房各若干份，不同级别的性能和一致性不同，自行根据需求选择。并且因为跨机房的带宽较低，Cassandra并不是直接连另外一个机房的若干个节点，而是只发一个请求到那个机房的一个节点，让那个节点转发请求，从而降低所需的带宽。
因为一致性哈希是一个确定的状态，需要确保在环上是能读到数据的。因此如果有节点新加进来，不能直接把他加到一致性哈希的环上，因为还没有数据，而之前存这个数据的节点现在不再负责存储对应的数据，相当于直接把数据弄丢了。所以需要这个节点先加入gossip网络然后根据自己选择的vnode来从对应的节点中导数据。Cassandra使用一种中间状态来定义正在导数据的节点——joining，而导数据的过程根据触发条件的不同，称作bootstrap或者rebuild。默认Cassandra会在一个空白节点启动的时候自动执行bootstrap，但是如果某个节点是一个新机房的第一个节点，环上只有自己的话直接bootstrap就把所有数据都搞过来了，肯定扛不住也没必要因为还会加新节点。因此关掉bootstrap后启动，一次性在新机房加入多个节点，然后人工逐个执行rebuild操作并指定从哪个机房导数据。
以上是Cassandra为了解决从key到node的路由信息所采用的方案。但这还没完。
因为为了确保可用性，通常读写时W和R都会小于N，因此通常N是3然后WR都设为quorum也就是2。不考虑时间戳误差的问题的话基本上是可以确保总是能读到最新的数据的。但是可能很多数据实际上只写了两份，第三份失败了。虽然平时读起来没啥问题，对client来说是感知不到的，无论选哪两个节点读，都还是能读到数据。如果这个时候想新增一个节点，而这个节点在导数据的时候选择从没有数据的那个节点导（为了加快速度减少初期的磁盘冗余Cassandra只会从N个节点中的一个来导某个区间的数据），那么导完数据在status从joining变成up后，可能会出三种问题：
第一个问题是，假如新上来的节点在环上取代的那个节点恰好是本来有数据的节点，那么接下来这个数据对应的三个节点里只有一个节点有这个数据，这个时候依然quorum的读就有1/3的概率读不到数据了不符合预期，而且数据冗余只有1份也很容易彻底丢失。第二个问题是，导数据的时候新写的数据还是写在原来的那三个节点，假设依然是有一个节点没写成，那么导完数据节点变成up后，还是有可能只有一个节点有数据。第三个问题是，因为gossip的集群信息维护是最终一致性的，一个节点从joining变成up并不是马上就让所有人知道的，一旦有些client知道有些client不知道，那么读写的节点就只有两个是一样的第三个是错开的，假如写的client又是只写成两份，与他错开的client可能就只能读到一份了。
这三个问题总体上都是因为quorum的写并不能保证所有节点都写成功，而降低冗余度无论对数据安全性还是一致性都没好处。因此Cassandra提供两种方式来修复冗余度。第一种是在读取的时候进行read repair操作，强制从所有节点读数据，一旦发现数据不一致就将N个数据合并作为真正的最新数据，把最新数据与每个节点当前数据diff的部分重新写回去（算这个diff的部分曾经有bug，我第一次给Cassandra提交代码就是改这个bug）。显然这个操作比单纯的读R份复杂而耗时，而且这么搞相当于ALL而非quorum没有可用性，因此不能每次都执行read repair。Cassandra支持在table级别配置触发read repair的概率，默认是0.1，可以0关闭也可以1强制开启，并且可以是只repair本地机房也可以repair所有机房。第二种是后台的repair操作，一次repair一个表在当前节点的所有数据。Repair时使用merkle tree减少数据传输，大概的意思就是分段算哈希，每几段连续hash可以组成更高层面的hash，最终变成一个hash，从下到上形成一个树，如果整个range的hash和对应节点一样就说明数据没差，如果hash不一样就分别看前半段和后半段的hash是否一样，这样二分下去就可以定位到真正不一致的区间，只需要传少量的数据。
Repair可以保证数据冗余度但是前面那三个问题实际上只解决了第一个问题（所以在新增节点之前最好把所有表都repair一遍才够安全，repair很慢的，所以Cassandra的运维成本并没有想象的那么低……）。对第二个问题和第三个问题为了避免不得不开read repair，Cassandra有个特殊的处理，如果发现当前写入的数据想写W份而目前正有一个节点在导数据而未来这个数据也会放在这个新节点上，那么就把这个新节点也当做写入的目标，并且必须额外再多写成功一份才算全局成功，也就是从四个节点里写成三个才可以。这样就不用开read repair了。
综上，看上去很美好的W+R>N，一方面是忽略了时间戳的误差，另一方面需要额外的运维工作确保他总是能读到最新的数据。除此之外在删除数据的时候还有tombstone的坑，这个以后专门一篇文章来写。
发表回复