一致性hash算法及其在均衡负载中的应用研究_开题报告

（一）当前问题

随着网络带宽的不断增大，网络速度不断的提高，仅面向与桌面软件及面向PC服务已经不能满足当前的需求。于是乎，云计算、大数据处理、Iot相关理念孕育而生。同时伴随着一些问题也日益凸显出来，尤其是因特网中的热点(Hot spot)问题，即p2p场景下的日益增长的连接数、日益增长的数据量、日益增长的运算量。特别是云服务和大数据处理这类问题尤其突出。

（二）基于哈希算法的解决方案

为了解决这个问题在1997年由麻省理工学院提出的一种分布式哈希（DHT）实现算法——一致性哈希算法，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得分布式哈希（DHT）可以在P2P环境中真正得到应用。

一致性hash算法提出了在动态变化的Cache环境中的四个概念和原则：

平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲（节点）中去，这样可以使得所有的缓冲空间（节点）都得到充分利用。

单调性(Monotonicity)：哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲（节点）中去，而不会被映射到旧的缓冲集合中的其他缓冲区（节点）。如果是用签名取模算法，缓冲区（节点）变更会使得整个网络的映射关系更改。如果是carp，会使得1/n的映射关系更改。一致性哈希的目标，是缓冲区（节点）变更，不会改变网络的映射关系。

分散性(Spread)：分散性即同一份数据，存储到不同的缓冲区（节点），也就是说系统冗余。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。

负载(Load)：和平衡性(Balance)类似，只不过平衡性(Balance) 指的是访问均衡，而负载（Load）针对数据存储均衡。负载问题实际上是从另一个角度看待分散性问题。为了减小负载合理的使用一致性哈希算法能达到意想不到的效果。

（三）算法实现及应用场景

一致性哈希算法有多种实现算法，其中最关键的问题是如何定义数据分割策略和节点快速查询。常用的算法有CHORD以及在CHORD基础上进行优化的KAD。除此之外还有许多优秀的算法。但是其核心还是相同的，即数据分割策略和节点快速查询。

一致性哈希算法的应用场景非常广泛，目前较为流行的应用场景为非关系数据库（NoSql）以及均衡负载服务器。例如目前主流非关系数据库Cassandra和MongoDB均使用了一致性哈希算法。

而在均衡负载中，一致性哈希算法被使用的玲离尽致。一致性哈希算法可以使当摸个缓冲区（节点）发生故障时，极其容易的退出哈希环，且当修复后也能简单的加入哈希环中。这一个退出加入的动作发生时，不会影响集群中其他缓冲区（节点）。这一特性大大的减小了运维人员的工作量。

二、^范文提纲

摘要

哈希算法

简单哈希算法

简单哈希算法应用于均衡负载

简单哈希算法应用于均衡负载的问题

一致性哈希算法

一致性哈希算法的原理

均衡负载中的使用

一致性哈希算法的实现

代码实现

一致性哈希算法的优化

一致性哈希算法的优势及劣势

一致性哈希算法的优势

一致性哈希算法的劣势

一致性哈希算法的其他实现方法列举

CHORD

KAD

结论

三、参考文献

[1] Kenneth H.Rosen,徐六通,杨娟,吴斌.离散数学及其应用[M].北京：机械工业出版社. 2014.8

[2]李志敏.哈希函数设计与分析[J].北京邮电大学.2009年

[3] 马如林,蒋华,张庆霞.一种哈希表快速查找的改进方法[J].计算机工程与科学.2008,30(9)

[4]胡丽聪,徐雅静,徐惠民.基于动态反馈的一致性哈希负载均衡算法[J].计微电子学与计算机.2012,29(1)

[5]杨或剑,林波.分布式存储系统中一致性哈希算法的研究[J].电脑知识与技术.2011,07(22)

[6]姚墨涵,谢红薇.一致性哈希算法在分布式系统中的应用[J].电脑开发与应用.2012,25(7)

[7]赵飞,苏忠.一致性哈希算法在数据库集群上的拓展应用[J].成都信息工程学院学报.2015,30(1)

[8]巴子言,吴军,马严.基于虚节点的一致性哈希算法的优化[J].软件.2014,(12)

[9]王康,李东静,陈海光.分布式存储系统中改进的一致性哈希算法[J].计算机技术与发展.2016,26(7)

[10] lafikl.A Go library that implements Consistent Hashing and Consistent Hashing With Bounded Loads.[Z].GitHub. s://github.com/lafikl/consistent.2017年6月11日

[11] 左飞.算法之美[M].电子工业出版社.2016.3.1