分布式存储算法(基于Kademlia的负载平衡云存储算法)

事实上，云存储的核心是通过应用软件实现从存储设备到存储服务的转变。就对，云存储系统而言，系统中有大量的存储节点，同时也有大量的存储服务需求。如何将存储服务需求合理、均衡地分配给各个存储节点，即实现负载均衡，是云存储技术的核心问题之一。解决这个问题可以大大提高云存储系统的效率，在改善用户体验的同时节省大量成本。这对对提高信息化水平具有重要意义。

本文以基于分布式哈希表(DHT)的完全分布式云存储系统为对映像，重点研究了Kademlia协议在云存储系统中的负载均衡问题，并对对算法进行了改进，使其具有更好的负载均衡性能。1相关工作

云存储系统通常是一个分布式文件系统，可以分为带中央服务器的主从结构和完全分布式的对(P2P)网络结构。前者是主流的云文件存储系统，如谷歌的GFS(谷歌文件系统[1])和Hadoop的HDFS (Hadoop分布式文件系统[2])。这种主从结构的存储技术分为两部分。主服务器(通常称为名称节点)存储和管理元数据，包括文件和块名称空间、文件和块之间的映射关系以及块服务器中每个块和副本的特定存储位置；块服务器(通常称为数据节点)存储实际的块数据。在这里，主服务器扮演中心节点的角色，根据元数据信息管理系统的存储和对处理的负载进行调整。该模式简单成熟，在实际应用中取得了成功。目前，研究文献中大量的云存储负载均衡算法都是针对对这样的系统，归纳起来，主要有静态和动态两种类型。静态负载平衡算法主要包括循环、比率和优先级。动态算法动态获取节点的存储容量，并优先将其存储在容量大的节点中。文献[3]提出了一种自适应综合动态负载均衡算法。该算法允许存储节点检测自己的负载，当负载发生跳跃变化(例如，从负载自适应到过载)时，它会将相关信息反馈给中央服务器。中央服务器根据存储节点的负载维护多个队列，存储服务优先分配给负载较轻的队列，同时在同一队列中采用轮询算法进行分配。文献[4]改进了对Hadoop中HDFS的负载均衡算法，原算法只考虑节点的空间利用率(即剩余存储容量)，而新算法还考虑了其他因素，如文件大小、文件并发访问时间、访问频率、节点处理能力、带宽等。

在具有中央服务器的主从结构中，由于中央服务器能够掌握全局信息，其负载均衡算法比对算法简单，但是随着存储节点的增加，文件和访问请求的数量增加，中央节点将成为系统的瓶颈。一旦过载或受到攻击，系统将崩溃，整体可扩展性将会很差。为了解决这个问题，像对这样具有网络结构的完全分布式云存储系统已经成为一个新的研究方向。像对这样的网络是一个覆盖网络，它是建立在现有物理网络上的虚拟层。每个节点都通过统一的路由协议进行通信，消息也在网络的逻辑连接(如对上传输

本世纪初，对等网络掀起了一股研究热潮。研究集中在对和其他具有完全分布式结构拓扑的网络。这种网络一般采用分布式哈希表技术来组织网络中的节点。分布式哈希表技术的本质是通过哈希函数将资源和存储资源的节点平均分配到同一个值空间，每个节点负责在对，的值空间中存储一小部分资源，从而实现整个分布式哈希表网络的寻址和存储。经典的分布式哈希表算法包括和弦[5]、糕点[6]、挂毯[7]、卡德姆利亚[8]等。卡德姆利亚因其高效、稳定和快速的收敛速度而被广泛应用于著名的P2P应用中，如eMule、Bitcometer、Bitsignore和Azureus。将分布式哈希表算法应用于云存储系统，可以去除中心节点，实现全分布式文件系统。常用的哈希算法包括字符串哈希算法、MD4、MD5、SHA1、戴维斯迈耶等。文献[9]对对常用的分布式哈希表算法进行了研究，发现它们都具有良好的哈希分布，能够保证数据的均匀分布。这意味着给定随机键值，该算法可以确保它们在整个哈希值空间中均匀分布。其中，MD5，SHA1和戴维斯。迈耶具有更高的效率和更好的安全性，因此它们已经成为分布式存储系统中更受尊敬的算法。在参考文献[10]中，作者提出了一种基于Kademlia作为路由算法的云存储系统，MingCloud，但只分析了系统的可用性和存储性能，并没有涉及负载均衡问题。在文献[11]中，提出了一种完全分布式的负载平衡算法。在具有对和其他结构的覆盖网络中，类似于Chord的DHT算法被用于将固定大小的文件块分配给存储节点，并且当节点加入或离开时，前一个节点的负载被转移到下一个逻辑节点(称为后继节点)。当由于存储节点的升级、加入和退出或文件的添加和删除而导致节点负载不平衡时，采用以下方法：将负载最轻的节点J 离线，然后加入作为负载最重的节点I的后继节点，然后节点I将部分负载迁移到节点J.如果在负载迁移后，节点I仍然是负载最重的节点，重复前面的过程，找到系统中负载最轻的节点K，并将其添加为节点I在离线的后继节点。该算法可以提高系统的负载均衡性能，但其实用性不强，因为在一个完全分布式的系统中，随着每个节点负载的变化，需要很大的通信开销和很长的延迟时间才能让每个节点知道系统中负载最重和负载最轻的节点。此外，计算密集型应用程序中的负载迁移也必须付出高昂的代价。