基于K-V模式的高可用性分布式存储技术研究

罗 常

（广东电网公司茂名供电局，广东茂名 525000）

0 引言

随着互联网的推广，越来越多的人更加依赖于网络。新型互联网技术的出现，使得人们的生活变得更加网络化。随之而来的是大数据问题，其中首当其冲的就是数据的存储问题，以及数据库实时响应问题。以2013年阿里巴巴双十一活动当天的数据为例，2013年11月11号，阿里巴巴公司旗下支付宝全天成交额高达350亿，支付宝达成的交易笔数为1.7亿笔，全天总订单数量为1.67亿个，一天内最高峰值为13 637人同时成功付款[1-2]。

透过阿里巴巴公司的数据，可以看出互联网对数据库存储以及实时性的高要求。然而根据CAP原理（一致性、可用性、分区容忍性），传统数据库没有分区容忍性，而是数据集中存储，导致了系统吞吐量和性能上无法满足现在互联网的需求，再加上为了防止单点故障，数据必然有备份与复制，在强一致性的要求下，又必将以损失性能为代价。种种迹象表明传统数据库技术已经无法满足现在互联网公司的需求[3]。

所以，在这种情况下，分布式存储技术诞生了。分布式存储技术凭借其独特的高可用性、完全分布式存储，以及实时性高等，已经成熟被应用到各家大型互联网公司，比如百度、腾讯和阿里巴巴等[4]。

1 分布式存储技术简介

传统关系数据库在很多应用场合出现了瓶颈，例如磁盘I/O瓶颈、可扩展性较差、分表分库、主从复制不易实施、无法不间断迁移等等，而NoSQL（Non relational，或者Not Only SQL，非关系型数据库）弥补了关系型数据库的不足，吸引大量开发人员参与研究。根据数据的存储模型和特点，NoSQL可以分为key-val⁃ue存储、列式存储、文档式存储、对象式存储等。其中K-V存储模式使用比较广泛，比较典型的有亚马逊的Dynamo系统。

2 Dynamo系统特点及架构

Dynamo是一个完全分布式的、无中心节点的、高可靠性、高可用性和容错能力具有良好的系统。Dynamo作为key-value模型存储平台，性能、扩展性、可用性较好，得到了广泛的应用。一般情况下，它能保证99.99%的读写访问响应时间都在300 ms内。一个Dynamo存储平台其实是由多个不同的存储机器构成的，各机器独立且角色类似。各个存储机器都存放一部分数据文件，系统会自动完成这些数据的备份，由于系统的完全分布特点，不会因为单台机器断电等故障影响到系统的对外服务。Dynamo系统特点如下：

（1）分布式存储、去中心节点；

（2）key-value模式；

（3）高容错性；

（4）复合技术解决一致性问题；

（5）高可用性和扩展性。

在设计方面，Dynamo系统遵循以下几条原则：（1）可扩展性：Dynamo每一级应保证能扩展一台存储主机，并对系统及其操作者的影响比较小；（2）对称性：dynamo应能够平等对待每个节点，保证每个节点有相同的性能；（3）去中心化：避免集中控制技术，延伸对称特性，保证有利于去中心化；（4）异质性：系统能够在异质性的基础设施运行。

3 Dynamo系统核心技术

3.1 分布式哈希（Distributed Hash Table）

为了达到去中心化的设计目的，DHT通过基于key-based路由策略来找到对应的存储节点（如图1所示）：

图1 分布式哈希图

（1）整个分布式系统组成一个环，环根据节点的数目被化分为对应的区域；

（2）每个区域用一个范围值 token表示(n-1，n]；

（3）每个节点负责一个区域。

Hash算法往往有很多，为了保证Dynamo分布式系统的高可用性，通常采用MD5作为hash算法来分配key值给环上的区域，具体步骤如图2所示。

图2 Hash算法步骤

3.2 矢量时钟（Vector clock）

使用Dynamo矢量时钟以获取同一个对象在不同时间的因果关系。矢量时钟可以看做是节点（node），计数器（counter）列表。每个版本的矢量时钟是与每个对象相关联，其对象有因果或平行分支关系。Dynamo中，当客户端更新一个对象，它必须指定哪一个版本更新。这可以通过它从早期的读出操作接收到的上下文对象中指定，该对象包含一个向量时钟信息。当系统处理一个读请求，如果Dynamo访问多个语法不太协调的分支，它会返回对应于该叶节点包含的上下文版本信息

3.3 暗示移交(Hinted handoff)

Hinted handoff是用来处理系统短暂的失效的方法，当所有主要负责的N个节点均失效的情况下，它试图将信息存放在非主要责任节点的一个特殊的位置，并记下一个hint，其包含这次写操作的真正目标节点信息。当消息服务收到一个Gossip信号得知有新的节点从失败中恢复过来时，它查看该节点有没有需要移交(handoff)的数据。通过检查它是否是那个hint提到的节点，如果是，包含hint的那个节点将向它移交(handoff)副本。

Hinted Handoff实现为一个后台线程，并用一个队列来记录所有要移交的hint信息。

Hinted handoff处理流程：从队列中取出一个待处理的hinted-handoff；进行移交工作的节点，通过上面提到的特殊的位置得hint相关信息；

基于上述hint中的目标接收信息，通过消息中心发给目标接收的节点（即恢复的节点）；

接收节点收到消息后，应用这个hint到本地。

3.4 Merkle树

Merkle Tree（MT），也叫Hash Tree，属于一种树状Hash结构。在此树中，叶节点的值是哈希值，所述非叶节点的值是它的子节点来的哈希值。Dynamo中，每个节点存储一个key值，不同节点的key值范围区间会相互重叠。在去熵操作中，考虑的关键是两个节点key值范围区的交叉点。MT的叶节点是key值相交范围区的每个key的哈希值，通过叶节点的哈希从下到上便可以构建出一个MT。Dynamo通过比对MT跟出的hash是否一致来判断是否交换子节点。

MT能够帮助Dynamo系统节省大量的时间和空间。在分布式条件下，空间被定义为对应于传输网络的数据量。从时间角度来看，MT避免了全局线性时间的比较；在网络传输上，MT查到某一层，就获取该层所需要的哈希值，大大降低了传输的数据量。

3.5 Gossip协议

Gossip是同步协议，主要用于分布式的非强一致性系统，以此来同步各节点状态。

在去中心化的集群环境里，各节点同其他节点交换实时信息是极其重要的。这些实时信息包括：

（1）节点心跳；

（2）节点状态（失效检查）；

（3）节点实时负载。

Gossip只需要少量的网络带宽中央处理器。Gossip会定期随机选择一个节点启动Gossip会话，其中每个Gossip都包含三个消息。比如，节点A启动一个Gossip到节点B：

（1）节点A→节点B，节点A发向节点B的请求信息（Gossip Request Message）；

（2）节点B→节点A，节点B发向节点A的确认信息（Gossip Ask Message）；

（3）节点A→节点B，节点A发向节点B的回应信息（Gossip Response Message）。

另外，上述消息传递系统可以检测是否出现故障的节点。

4 具体实现

Dynamo的本地持久化组件对不同的存储引擎提供了不同的操作接口，因此能够当今众多流行的数据库，比如Berkeley数据库，MySQL等。另外，它也有一个持续的后备存储内存缓冲机制。此持久性可插拔组件允许系统配置最适合的存储引擎。比如，BDB一般都可以处理kB等级的对象，MySQL能够处理MB甚至更大的对象。因此，如果对所有的对象采用统一引擎，势必造成资源的浪费，而Dynamo根据处理对象的大小分布式选择相应的本地持久性引擎。

请求的协调基于事件驱动的原理，多个类SE⁃DA结构构成了消息处理管道。使用Java NIO Channels处理所有的数据通信。执行读取和写入是协调员的基本职责，即读取一个或多个节点数据和写入一个或多个节点存储的数据。系统为每个客户的请求创建一个状态机，包含以下逻辑：

（1）标识负责一个key的节点；

（2）发送请求；

（3）等待回应；

（4）重试处理；

（5）加工包装回客户端的响应。

一般情况下每个状态机只处理单个客户端的请求。

5 总结

Dynamo经过长时间应用，它的高可用性得到了实践证明：99.95%的应用请求都成功收到无超时的响应。虽然Dynamo存在着一致性的问题，但是该问题可以利用其他技术有效地解决。其次，在Dynamo中，用户可以从自己的角度来设定三个参数值。在此之外，Dynamo还向系统的开发者们公布了系统协调一致性的逻辑上的问题。Dynamo的高可移植性使得移植应用程序到Dynamo是非常容易的，针对不同的业务需求配置相应的冲突协调机制可以大大提高系统效率。最后，Dynamo采用全成员(full membership)模式，每个节点都需要积极地与系统中的其他节点交换完整的路由表，以便知道其对等节点承载的数据，然而，这样的设计以运比较多的节点的问题是路由表存储的高成本，因此为了克服这种限制，需要通过对Dy⁃namo引入分层扩展技术。

［1］金海，袁平鹏.语义网数据管理技术及应用［M］.北京：科学出版社，2010.

［2］ Hayes B.Cloud Computing［J］.Communications of the ACM，2008，51（7）：9-11.

［3］NAMJOSHI J， GUPTE A.Service Oriented Architecture for Cloud Based Travel Reservation Software as a Service［A］.Proceedings of the 2009 IEEE International Confer⁃ence on Cloud Computing（CLOUD’09）［C］.Sep 21-25， 2009， Bangalore， India.Los Alamitos，CA，USA：IEEE Computer Society，2009：147-150.

［4］王庆波，金何乐.虚拟化与云计算［M］.北京：电子工业出版社，2009.