这篇文章是Recruit Lifestyle 2016年圣诞活动中的第25天的日记。

我是数据工程师集团和松软厉害的机器学习工程师tomomoto。我主要负责数据分析和机器学习，推动数据的利用，进行系统开发，并提供免费素材。

在本文中，我想稍稍介绍一下KVS的工作原理，以HBase和Cassandra为例。（与工作、圣诞节和结婚纪念日无关！）

KVS是什么意思？

最初問KVS(鍵值存儲)是什麼？如果按照名字的意思，它必須是一個KeyValueStore，那麼它就是一個從鍵取值的數據庫。但這樣就足夠了嗎？那麼從文件名(鍵)中獲取文件信息(值)的文件系統也可以被認為是KVS，但這並不合適。

通常情况下，RDB在CAP定理中指的是非CA类型的数据库，也就是AP/CP类型的键值存储系统。CAP定理简单来说，指的是很难同时满足CAP定理的三个要素，必须要牺牲其中一个要素。准确来说，它表达了这三个要素之间的权衡关系，并不一定要选择两个要素。

• CAP定理の３要素

Consistency(一貫性)
Availability(可用性)
Partition Tolerance(ネットワーク分断耐性)

KVS受到重视的开始可以追溯到2006年Google BigTable的论文和2007年Amazon DynamoDB的论文公开。Google BigTable在牺牲可用性的前提下，提供了强一致性和高负载分散性能，而Amazon DynamoDB则在牺牲一致性的前提下，实现了可扩展性和高可用性。这些论文为后来开发了一系列的开源软件如HBase（源于BigTable）和Cassandra（也有一些BigTable的影响），提供了契机。

尽管KVS存在许多不同的来源和定义，但我认为只有具备下列问题的KVS才是可接受的。

CP型のKVS:HBase

一時的なダウンタイムを許容することによって、強い一貫性と高い負荷分散性能を実現しているDataBase

AP型のKVS:Cassandra

強い一貫性を保てないことを許容するが、EventualConsistencyによってある程度の一貫性を保つ、高い可用性と高い負荷分散性能を実現しているDataBase

KVS的机制

无论是AP型还是CP型，KVS都需要在多个节点上进行数据管理以实现高负载分散性能。然而，随着节点数量的增加，某个节点发生故障的概率也会增加，从而容易导致数据丢失和可用性降低。为了解决这个问题，需要进行复制（在多个节点上管理相同的数据）。然而，在多个节点上处理相同数据时保持一致性变得更加困难。以下将以HBase作为CP型代表和Cassandra作为AP型代表来解释CP/AP型的KVS在如何平衡这种权衡关系的例子。

HBase的机制是什么？

在HBase中，数据以称为Region的块来处理，其中每个Region是通过将数据的Key分割成范围来定义的单位。假设Key的值为1-5000，并将数据分割成1000的区间，那么Key值在1001-2000范围内的数据将成为一个Region。这种分割称为Sharding（分片），在HBase中实现了自动Sharding。

RegionServer 管理一个或多个 Region。每个 RegionServer管理的 Region 信息由 Zookeeper 进行管理，Zookeeper 负责根据 Region 的重新分配进行负载均衡等操作。因此，客户端需要向 Zookeeper 获取 RegionServer 的位置信息，并直接与 RegionServer 进行数据交互。另外，为了确保数据的行级一致性，HBase 要求每个 Region 必须由一个 RegionServer 进行管理。然而，这同时增加了数据丢失的风险，并且进一步降低了可用性。

在RegionServer中，Region会作为Memostore被展开在内存中。然而，在Memostore阶段，Region尚未被复制，在仅存在内存中时，如果服务器宕机，数据将会丢失。为此，HBase将更改内容写入磁盘作为HLog。一般来说，这种机制被称为WAL（WriteAheadLog，先写日志）。

Memostore/HFile 是一种类似于日志的数据，其中包含了操作内容和目标记录等信息。因此，在写入或更新时，都会将信息追加到 Memstore 中。而在读取时，会从 Memstore 中确认目标记录的最新信息，并加载数据。如果 Memstore 中信息不足，还会参考 HFile 来获取数据。

当Memostore的大小增加时，将Memostore的数据作为HFile写入HDFS中。通常情况下，在HDFS中进行复制，因此在写入HFile时数据丢失的可能性非常低。当HFile的数量增多时，将进行合并处理，即Compaction（压缩）操作。合并处理的内容通常包括删除不再需要的日志，以满足后续处理的需求。

通过以上的机制，一些数据可能会面临较高的丢失风险，同时，为了恢复Master和RegionServer，可用性可能会下降。然而，通过增加RegionServer的数量，系统可以在实现扩展性的同时，保持行级一致性。

卡桑德拉的机制

在Cassandra中，使用一致性哈希算法（Consistent Hashing）来确定每个数据应该放置在哪个节点上。一致性哈希算法是将「数据键的哈希值」与「管理数据的节点」进行映射，将哈希值转化为数字并对一个足够大的数字取余数，然后在一个圆环上进行排列，根据位置确定负责的节点。例如，图中的DataA对应的哈希值为星号位置，有3个复制，所以负责的节点是5、6、7。通过一致性哈希算法，可以减少节点添加或删除时的数据重新分配成本。此外，它还可以实现没有主节点的情况下，每个节点自主管理其负责范围内的数据，并实现可用性的提高。

为了使用一致性哈希算法，每个节点需要知道自己以及其他节点的负责范围，以便在客户端查询时进行回答。为了宽松共享这些信息，引入了一种称为Gossip Protocol（八卦协议）的机制。Gossip Protocol是指每个节点与其他节点随机共享信息，经过一段时间后，所有节点都能保持最新信息的机制。

Cassandra的一定程度的一致性主要是由”Quorum Protocol”（仲裁協定）支持。Quorum Protocol是指要求的【複製數量】必須大於【讀取成功節點數量】和【寫入成功節點數量】之和，以確保在數據讀取成功時，總能包含最新版本的數據。此外，通過【讀取成功節點數量】和【寫入成功節點數量】，還可以優化讀取性能或變更為寫入性能為重。

加上”Quorum Protocol” ，只要能判断已读取数据版本的前后关系，就可以保证一定的一致性。判断前后关系所使用的是”Vector Clock”（向量时钟）。”Vector Clock” 是逻辑时钟的一种，是节点和计数器的集合体。为了使用常规时钟，需要始终保持所有节点时钟的同步。但是，当节点数量增多时，这变得困难，因此可以使用”Vector Clock”。然而，在Cassandra中，放弃了严格处理已读取数据版本前后关系，不使用”Vector Clock”（参考：http://www.datastax.com/dev/blog/why-cassandra-doesnt-need-vector-clocks）。

在此，一定程度的一致性被提及的原因是，如果写入几乎同时发生在不同的节点通过Vector Clock，会导致竞争并使得无法确定数据的前后关系；另外，如果写入和读取几乎同时通过不同的节点发生，根据时机不同可能会返回不同的值。

最后，我将解释在复制数为3、写入成功所需数量为2、读取成功所需数量为2的情况下，写入和读取操作的流程（需要说明的是，为了解释VectorClock，我将说明在Cassandra中未引入VectorClock的情况下如何使用）。

在进行写入操作时，首先连接到任何一个已配置的Cassandra节点，并传递写入请求的信息。连接的中介节点会递增其持有的向量时钟(Vector Clock)的计数，并为所有负责该数据的节点附加向量时钟的信息，然后发送写入请求。如果写入目标节点确定传递的向量时钟比其持有的数据向量时钟更新，则更新数据并将写入成功的消息返回给中介节点。如果负责该数据的节点无法连接，例如宕机等情况，将会在其他节点上写入专用于写入恢复操作的数据(Hint)。这样在负责该数据的节点恢复时，可以通过接收Hint来重新执行写入操作。这就是所谓的Hinted Hand Off(提醒式传递)机制。

如果代理节点返回的成功写入数量达到了设定的写入成功必要数量（Quorum Protocol），则向客户端返回写入成功。另外，如果由于超时或竞争导致无法写入的节点数量超过了写入成功必要数量，则向客户端返回失败。

在执行读取操作时，我们首先要连接到Cassandra集群中的任意一个节点，将读取请求的信息传递给该节点。连接的中间节点会将读取请求发送给所有负责存储数据的节点。被读取的节点会将其持有的数据和向量时钟等信息返回给中间节点。

如果仲介节点回到达到了设置的读取成功所需数量的Quorum Protocol，并且通过Vector Clock的比较确定了最新的数据，那么它将作为读取成功返回最新的数据。（同时，也会向保持旧数据的数据负责节点发出更新至最新数据的请求。这被称为Read Repair（读取修复）机制。）如果通过Vector Clock的比较发现存在多个竞争冲突造成的最新数据，那么它将作为读取失败返回多个最新的数据。另外，如果由于超时等原因未达到读取成功所需数量，那么将返回失败给客户端。

在负责数据的节点内部操作基本上与HBase相似，使用内存、WAL和转储文件（即HFile）来处理数据。唯一不同的是，转储文件的存储位置使用本地文件系统代替HDFS。

尽管基于以上机制，由于时间等因素可能会缺乏一致性保证，但无需特殊的Master服务器，可以实现高可用性。

总结

我簡單介紹了KVS（鍵值儲存服務）的機制，以HBase和Cassandra作為例子。希望這能幫助理解KVS的設計理念。順帶一提，我喜歡Cassandra的機制，但是在實際使用上我更喜歡HBase。

另外，在本文中介绍的机制只是核心功能的一部分，实际上还有许多其他功能。请您自行努力提升到更高的层次！

请提供相关资料。

请给出参考资料。

请提供参考资料。

• Brewers CAP Theorem on distributed systems

• Bigtable: A Distributed Storage System for Structured Data

Amazon’s Dynamo