基于Kademlia的负载平衡云存储算法

　　云计算已成为当前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和Davies.Meyer这三种算法运行效率较高，安全性也佳，所以成为分布式存储系统中比较受推崇的算法。文献[10]中，作者以Kademlia为路由算法，提出了一种对等结构的云存储系统MingCloud， 但只分析了系统的可用性和存储性能，未涉及负载均衡问题。文献[11]中，提出了一种完全分布式的负载平衡算法，算法在对等结构的覆盖网上，采用类似Chord的DHT算法将固定大小的文件块分配到存储节点，节点加入或离开时将前一节点的负载迁移到逻辑上的下一节点（称后继节点。当由于存储节点的升级、加入、退出或文件的添加、删除造成节点的负载不平衡时，采用如下方法：将最轻负载的节点j离线，然后作为负载最重节点i的后继节点加入，接着节点i将部分负载迁移到节点j。如负载迁移后节点i仍是负载最重的，则重复上一过程，寻找系统当前最轻载节点k，将其离线并作为i的后继节点加入。算法能改善系统的负载平衡性能，但实用性不强，因为在完全分布式且各节点负载不断变化的系统中，要让每个节点知道系统中负载最重和负载最轻的节点，需要极大的通信开销和较长的延迟时间。另外，在计算密集型应用中进行负载的迁移，也要付出很大的代价。