基于Kademlia的负载平衡云存储网络的建设

　0引言
　　云计算已成为当前IT行业的热门话题。作为支撑云计算的关键技术，云存储技术也越来越受到关注。云存储具有低成本、高可用性、高扩展性、高可靠性及存储细节对用户透明等特点。
　　云存储的核心实际上是通过应用软件来实现存储设备向存储服务的转变。
　　对于云存储系统来说，系统中拥有大量的存储节点，同时又有大量存储服务的要求，如何将存储服务要求合理、均匀地分配到各个存储节点，即实现负载的均衡，是云存储技术的核心问题之一。解决好这个问题，能极大地提高云存储系统的效率，在提高用户体验的同时节省大量的成本，对提高信息化水平具有重要的意义。
　　本文以基于分布式哈希表（Distributed Hash Table， DHT的完全分布式云存储系统为研究对象，重点研究将Kademlia协议应用到云存储系统的负载均衡问题，并对算法进行了改进，使其具有更好的负载均衡性能。   []
　　1相关工作
　　云存储系统通常是一种分布式文件系统，具体可分为具备中心服务器的主从式结构和完全分布式的对等（Peer to Peer， P2P网络结构。前者是目前主流的云文件存储系统，如Google的GFS（Google File System[1]、Hadoop的HDFS（Hadoop Distributed File System [2]等。这种主从结构的存储技术，其存储分为两部分，主服务器（一般称name node存储和管理元数据，包括文件和块的名空间、文件到块之间的映射关系及每一个块及副本在块服务器中的具体存储位置；块服务器（一般称data node则存储实际的块数据。这里主服务器起着中心节点的作用，它根据元数据信息管理系统的存储，并对处理的负载进行调整。这种模式实现简单，也比较成熟，在实际应用上也取得了成功。
　　目前研究文献中的云存储负载均衡算法大量针对此类系统。归纳一下，主要有静态和动态两类。静态的负载均衡算法主要有轮询（Round Robin、按比率（Ratio和按优先级（Priority几种；动态算法则通过动态获取节点的存储能力，并优先存储于能力强的节点。文献[3]中提出了一种自适应的综合动态负载均衡算法。算法让存储节点检测自身负载，当负载有一个跳跃变化（如从适载到过载时，就向中心服务器反馈相关信息。中心服务器根据存储节点的负载轻重维持多个队列，存储服务优先分配给轻载队列，而在同一队列中则采用轮询算法进行分配。文献[4]则对Hadoop的HDFS的负载均衡算法进行了改进，原算法只考虑了节点的空间使用率（即剩余存储能力，而新算法还考虑了其他因素，如文件大小、文件并发访问时间、访问频度、节点处理能力、带宽等。
　　在具有中心服务器的主从式结构中，由于中心服务器能掌握全局信息，所以其负载均衡算法相对比较简单。但随着存储节点、文件数量及访问请求的增加，中心节点会成为系统的瓶颈，一旦过载或遭受攻击会导致系统的崩溃，整个扩展性较差。
　　为解决这个问题，完全分布式的对等网络结构的云存储系统成为新的研究方向。对等网络是一种覆盖网络，是建立在已有物理网络上的一个虚拟层，各节点通过统一的路由协议进行通信，消息也在对等网络的逻辑连接上传递。
　　本世纪初，对等网络曾有过一波研究热潮。研究重点在全分布式结构化拓扑的对等网络。这种网络一般采用DHT技术来组织网络中的节点。DHT技术的实质是将资源和存储资源的节点通过散列函数均匀分布到同一个取值空间，每一个节点负责对应取值空间中的一小部分资源的存储，从而来实现整个DHT网络的寻址和存储。经典的DHT算法有chord[5]、Pastry[6]、Tapestry[7]、Kademlia[8]等，其中Kademlia因为效率和稳定性高、收敛速度快等原因，被广泛应用于eMule、Bitcomet、Bitspirit和Azureus等著名P2P应用软件中。
　　将DHT算法应用于云存储系统，能去除中心节点，实现全分布式的文件系统。常用的哈希算法有字符串哈希算法、MD4、MD5、SHA1、Davies Meyer等。文献[9]对常用的DHT算法进行了研究，发现它们都具有良好的散列分布性，能够保证数据的均匀分布。这就意味着，给定随机的键值，算法能保证将其均匀地散布于整个哈希值空间。其中，MD5、SHA1和这三种算法运行效率较高，安全性也佳，所以成为分布式存储系统中比较受推崇的算法。文献[10]中，作者以Kademlia为路由算法，提出了一种对等结构的云存储系统MingCloud， 但只分析了系统的可用性和存储性能，未涉及负载均衡问题。文献[11]中，提出了一种完全分布式的负载平衡算法，算法在对等结构的覆盖网上，采用类似Chord的DHT算法将固定大小的文件块分配到存储节点，节点加入或离开时将前一节点的负载迁移到逻辑上的下一节点（称后继节点。当由于存储节点的升级、加入、退出或文件的添加、删除造成节点的负载不平衡时，采用如下方法：将最轻负载的节点j离线，然后作为负载最重节点i的后继节点加入，接着节点i将部分负载迁移到节点j。如负载迁移后节点i仍是负载最重的，则重复上一过程，寻找系统当前最轻载节点k，将其离线并作为i的后继节点加入。算法能改善系统的负载平衡性能，但实用性不强，因为在完全分布式且各节点负载不断变化的系统中，要让每个节点知道系统中负载最重和负载最轻的节点，需要极大的通信开销和较长的延迟时间。另外，在计算密集型应用中进行负载的迁移，也要付出很大的代价。
　　目前基于DHT的全分布式实验性云存储系统也已出现，如自由软件GlusterFS（Gluster File System， 官网：http
　　//。GlusterFS不需要元数据，而是使用DaviesMeyer散列算法来进行数据定位，即只要根据路径和文件名就可以定位其存放的服务器。这样使得数据访问完全并行化，从而实现真正的线性性能扩展，同时也提高了系统的性能、可靠性和稳定性。但GlusterFS没有能很好地解决负载均衡问题，新增节点需要通过系统中老节点的链接才能被访问到，老节点负载较重。
　　使用DHT算法的目的就是通过散列函数将键值均匀地分布到某个取值空间中。如果应用于云存储系统，其隐含的前提是云中每个存储节点是同构的，即存储节点具有相同的存储能力和处理能力，这样能使存储内容均匀地分布于各存储节点，总体上使得系统的负载保持均衡，这时造成负载不平衡的主要原因仅限于存 储节点的升级、加入、退出或文件的删除。文献[11]等多数针对基于DHT技术的云存储系统中负载平衡的研究，就是基于节点同构这个前提的。但存储节点的同构只能是一种假设，实际的云存储系统中，节点往往是异构的，且节点间存储能力可能差异很大，如将存储内容在这些节点中均匀分布，会造成严重的负载不均衡，这对将DHT技术应用到云存储系统提出了挑战。如何较好地解决这个问题是此类系统走向实用的关键。
　　2Kadmalia算法及负载平衡性能
　　为研究基于DHT的全分布式文件系统的负载均衡问题，本研究选择使用最广泛的Kademlia（下简称KAD算法作为研究对象。之所以选用它，是因为相对其他DHT算法，KAD的效率和稳定性高，收敛速度快。
　　2.1KAD算法
　　KAD先采用DHT散列算法（典型地使用SHA1算法得到资源和各节点的散列值（通常为160位，并将资源存储到与它们的散列值相同的目的节点或与目的节点逻辑距离最接近的节点中。与其他DHT算法不同的是，在KAD网络中，两个节点之间的逻辑距离由这两个节点对应散列值（以下称节点标志的异或（X0R决定，即：D（a， b = pid_a ⊕ pid_b；这里D代表逻辑距离，pid_a和pid_b分别为节点标志，⊕为异或算符。
　　KAD采用“k桶”来记录网络中节点的路由信息。如果散列值为160位，则节点维护了160个k桶，第i（0≤i<160个k桶存放k条与自身距离为2i ～ 2i+1间已知其他节点的信息。KAD通过节点间的消息传递进行信息交互，主要通过4个远程过程调用（Remote Procedure Call， RPC来完成节点间的通信：PING、STORE、FIND_NODE和FIND_VALUE。
　　1PING
　　探测一个节点是否在线；
　　2STORE
　　指示一个节点存储一个〈key，value〉对；
　　3FIND_NODE
　　递归查询与指定目标逻辑距离最接近的k个节点的信息；
　　4FIND_VALUE
　　根据键值查找到一个存放对应资源的节点。
　　这些操作中最基础的是FIND_NODE操作。
　　FIND_NODE返回k个ID值最接近目标ID的元组。查询过程如下：
　　1起始查询节点从自己的k桶中选择ALPHA个最接近目标ID值的节点并行发送FIND_NODE消息，其中ALPHA为同时进行查询的并发数，一般取3。   []
　　2收到FIND_NODE的节点，返回该节点所知的k个最接近目标节点的列表给查询节点。
　　3 查询节点整理收到的节点列表，选择ALPHA个新的未曾发送过的节点发送FIND_NODE。
　　4直到所有返回的节点列表中未发现比现有节点更接近目标的节点或最近节点集的所有节点都已经被查询。
　　查询节点维持了一张包含k个已知逻辑上最近的邻居表，利用FIND_NODE查询得到的新知识不断更新这张邻居表，并向邻居表中未查询过的节点发送FIND_NODE查询，如此循环，直至没有新节点能加入表且表中所有节点均已被查询。
　　STORE则利用FIND_NODE找到k个最接近目标键值的节点，选择其中m个距离最近的节点发存储命令。
　　KAD算法有效地解决了P2P系统中的资源定位问题，其结构化的拓扑和独特的异或算法提高了节点的查询效率，并且能确保当节点存在于KAD网络时就一定能够被发现。该算法在实际使用中体现出良好的性能。
　　2.2KAD算法的负载平衡性能
　　KAD网络本质上是在分布式网络的基础上构建一个覆盖网，并在网中均匀地分布要存储的信息。如果节点是同构的，即每个节点的存储能力、处理能力和带宽均相同，理论上KAD算法的负载平衡性能会较好。但是，如果网络中节点是异构的，使用KAD算法的负载均衡性能又会怎样？对此，本文进行了相应的仿真实验。
　　2.2.1仿真环境
　　本文采用peersim仿真工具[12]。该仿真器用Java编写，可从peersim官网（http
　　//中下载并获得KAD协议模块，但该模块目前只完成了主要的FIND_NODE调用的功能。本文在此基础上实现了FIND_VALUE和STORE模块，并添加了统计和输出各项指标的仿真代码。
　　仿真使用peersim的事件驱动模型，存储节点数设为500个，文件块大小设置为64MB（与GFS系统一致，仿真时间设为3000h，散列位数设为32，k桶中的k值设为20，并发查询数设为3，存储的副本数也设为3。假设网络可靠，传送的消息均未丢失，每一个观察周期（100000s有节点增加或失效的概率均为0.25，系统中按轻载和重载两种情况定期产生文件存储要求。
　本文分别针对节点同构和节点异构两种场合的KAD系统进行仿真实验。同构节点的场合假设每个节点均有500M的存储容量；异构节点的场合假设节点的存储容量有3种
　　1000MB、500MB和100MB，3种节点数量大致相同。给节点存储容量设定比实际偏小的值是为了更早地观察到节点过载现象。每种结构类型又设定轻载和重载两种情况，重载时文件保存操作的频率增加到轻载时的3倍。为考察系统的负载平衡性能，本文采用直观的随时间变化的过载节点百分比（即存储容量耗尽的过载节点占总节点数的百分比及文件保存的成功率（文件保存操作的成功次数与总的保存操作次数之比为衡量指标，这里假定文件保存不成功的原因主要是由于节点的存储能力不足，也可能是节点失效（离开。由于设定了系统的副本数为3，所以文件能成功保存至少一份的概率要远高于上述成功率数据。
　　2.2.2轻载时同构节点与异构节点KAD负载平衡性能的比较轻载时两场合KAD负载平衡性能比较
　　图1表明轻载情况下KAD在异构节点场合的过载节点百分比要明显高于同构节点场合。
　　图片
　　2.3分析与结论
　　通过仿真结果可以看到，不论是轻载还是重载，在系统为异构节点的场合，过载节点的百分比明显高于同构节点的场合，而文件保存的成功率则明显要低。由于实际的云存储系统中存储节点通常是异构的，所以如果直接将KAD算法应用于云存储系统，其负载平衡性能无法达到理想的状况。
　　3改进的KAD算法及负载平衡性能
　　3.1改进的KAD算法
　　为了弥补KAD算法的不足，考虑对KAD算法进行改进。改进的目标主要针对异构节点场合下的负载平衡性能的改善，要在保留KAD算法原有优良性能的基础上，使其负载均衡性能有较大提高。
　　基本思想是在存储资源时，既采用哈希算法均匀分配，又考虑节点的存储能力，优先将资源存储到负 载最小、存储能力最强的节点中，以达到节点的负载平衡。
　　新算法的主要改进是在存储环节。假设文件已经分好块（这是为了提高存储效率，每块的长度固定（block_size变量设定，默认64MB，则文件存储过程如下：
　　1根据文件路径、文件名及块号计算要存储文件块的标识（FileBlockId。
　　采用哈希算法（典型的如SHA1算法，得到一个散列值（默认160位，可设定，该散列值对应要存储文件块的标识FileBlockId，同时也作为目标节点标识（destNode。
　　程序前
　　.2改进的KAD算法的负载平衡性能
　　为了检验新算法的负载平衡性能，在peersim上编写仿真代码并进行了仿真实验。仿真的参数设置与前面一致。 本文比较了异构节点场合下KAD算法与改进的KAD算法在轻载和重载两种情况下的负载平衡性能。
　　3.2.1异构节点场合轻载时KAD与改进的KAD负载平衡性能的比较异构场合轻载时两算法负载平衡性能比较
　　图5表明轻载情况下异构节点场合改进的KAD相比KAD的过载节点百分比明显要低。
　　3.3性能分析
　　从仿真结果看，不管是轻载还是重载，改进的KAD算法在负载平衡性能上比原KAD算法有非常明显的提升。特别是在轻载的情况下，改进算法的文件保存成功率在相当长的时间内保持为100%，较原算法平均提升27.2%。重载情况下则平均提升35.1%。改进后系统中的过载节点百分比则有显著下降，平均下降7.0%（轻载和33.7%（重载。
　　分析性能提升的原因，KAD算法先用FIND_NODE得到k（仿真中k=20个离目的节点逻辑距离最近的节点，再从中选取m个（m为副本数，m≤k，仿真中m=3节点发送存储命令STORE。这m个节点的选取只考虑离目的节点逻辑距离的远近，而不考虑节点本身的存储能力，这样对异构节点的系统，必定会造成负载的不均衡。而改进的KAD算法得到k个与目的节点距离最近的节点后，从中选取m个剩余存储空间最大的节点发送存储命令，这样就能在很大程度上改善系统的负载平衡性能。轻载时文件保存成功率为100%，可理解为系统总能在满足KAD算法要求的k个候选节点中挑出m个能满足存储要求的节点来存储。
　　3.4算法开销
　　为了获得节点的剩余存储空间的大小，新算法需要增加一些通信开销。在用FIND_NODE得到最接近目标节点的k个节点后，选择存储目标的节点s需向这k个节点发送存储空间查询请求STORAGE_SPACE_REQ消息，被查询节点回应STORAGE_SPACE_REP消息给s，消息包含被查询节点的ID和当前剩余存储容量，节点s再从中选择存储能力最强的m个节点发送STORE命令。这些额外的通信开销主要包括发送STORAGE_SPACE_REQ消息和节点回应STORAGE_SPACE_REP消息，每个存储过程增加2k条信息（不考虑网络层的路由消息，即额外的通信开销为O（k。而KAD系统中存储过程（含路由查找的通信开销，文献[8]中认为是O（k，但这仅仅是理想情况下，平均应为O（lb N[1]，极端情况甚至可以到O（N （这时节点搜索整个网络才得到与目标距离最近的k个节点，其中N为网络中节点数。由于k一般远远小于N（默认k取20，节点数N则可以成千上万，所以新协议增加的通信开销是可以接受的，这也可以从仿真实验中得到验证。
　　图9是500个异构节点、轻载情况下系统中的消息总数随时间的变化，从中也可看出新协议增加的通信开销是有限的。
　　图片
　　图9异构节点场合两种算法下系统中的消息数的变化
　　与文献[11]中的负载平衡算法（下称Y算法相比，改进的KAD算法未涉及节点内部的负载迁移。单凭Y算法需要查找网络中负载最重的节点和负载最轻的节点，复杂度就达到O（N，远超改进的KAD算法（O（k。两者性能比较则因条件限制尚未在仿真上实现。
　4结语
　　针对当前主流的云存储系统采用主从式结构带来的可扩展性差的问题，本文尝试将KAD算法应用于分布式文件系统，并考察其负载均衡性能。实验显示，系统在节点异构环境下的负载均衡性能要明显差于节点同构环境。为改善节点异构环境下的性能，本文对KAD算法进行了改进，在满足KAD算法要求的存储节点中，优先将负载分配给存储能力强的节点。仿真结果证明，算法在增加有限开销的情况下，大大提高了系统的负载均衡性能。
　　参考文献
　　[1]
　　GHEMAWAT S， GOBIOFF H， LEUNG ST. The Google file system [C]// Proceedings of the 19th ACM Symposium on Operating Systems Principles. New York
　　ACM， 2003
　　29-43.
　　[2]
　　Hadoop community. Hadoop disributed file system [EB/OL]. [20140711]. http
　　//.
　　[3]
　　ZHANG C， YIN J. Dynamic load balancing algorithm of distributed file system [J]. Journal of Chinese Computer Systems， 2011，32（7
　　1424-1426.（张聪萍，尹建伟.分布式文件系统的动态负载均衡算法[J].小型微型计算机系统，2011，32（7   []
　　1424-1426.
　　[4]
　　LIU K， NIU W. An improved data balancing algorithm for Hadoop [J]. Journal of Hennan Polytechnic University
　　Natural Science， 2013，32（3
　　332-336.（刘琨，钮文良.一种改进的Hadoop数据负载均衡算法[J].河南理工大学学报
　　自然科学版，2013，32（3
　　332-336.
　　[5]
　　STOICA I， MORRIS R， KARGER D， et al. Chord
　　a scalable peertopeer lookup service for Internet applications [C]// Proceedings of the International Conference of the Special Interest Group on Data Communication. New York