一致性哈希算法及java实现.doc

文档介绍：一致性哈希算法及java实现应用场景在做服务器负载均衡时候可供选择的负载均衡的算法有很多,包括:轮循算法(RoundRobin)、哈希算法(HASH)、最少连接算法(LeastConnection)、响应速度算法(ResponseTime)、加权法(Weighted)等。:有N台服务器提供缓存服务,需要对服务器进行负载均衡,将请求平均分发到每台服务器上,每台机器负责1/N的服务。常用的算法是对hash结果取余数(hash()modN):对机器编号从0到N-1,按照自定义的hash()算法,对每个请求的hash()值按N取模,得到余数i,然后将请求分发到编号为i的机器。但这样的算法方法存在致命问题,如果某一台机器宕机,那么应该落在该机器的请求就无法得到正确的处理,这时需要将当掉的服务器从算法从去除,此时候会有(N-1)/N的服务器的缓存数据需要重新进行计算;如果新增一台机器,会有N/(N+1)的服务器的缓存数据需要进行重新计算。对于系统而言,这通常是不可接受的颠簸(因为这意味着大量缓存的失效或者数据需要转移)。那么,如何设计一个负载均衡策略,使得受到影响的请求尽可能的少呢?在Memcached、Key-ValueStore、BittorrentDHT、LVS中都采用了ConsistentHashing算法,可以说ConsistentHashing是分布式系统负载均衡的首选算法。基本场景比如你有N个cache服务器(后面简称cache),那么如何将一个对象object映射到N个cache上呢,你很可能会采用类似下面的通用方法计算object的hash值,然后均匀的映射到到N个cache;hash(object)%N一切都运行正常,再考虑如下的两种情况;一个cache服务器mdown掉了(在实际应用中必须要考虑这种情况),这样所有映射到cachem的对象都会失效,怎么办,需要把cachem从cache中移除,这时候cache是N-1台,映射公式变成了hash(object)%(N-1);由于访问加重,需要添加cache,这时候cache是N+1台,映射公式变成了hash(object)%(N+1);1和2意味着什么?这意味着突然之间几乎所有的cache都失效了。对于服务器而言,这是一场灾难,洪水般的访问都会直接冲向后台服务器;再来考虑第三个问题,由于硬件能力越来越强,你可能想让后面添加的节点多做点活,显然上面的hash算法也做不到。有什么方法可以改变这个状况呢,这就是consistenthashing。 hash算法和单调性Hash算法的一个衡量指标是单调性(Monotonicity),定义如下:单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。容易看到,上面的简单hash算法hash(object)%N难以满足单调性要求。consistenthashing算法的原理consistenthashing是一种hash算法,简单的说,在移除/添加一个cache时,它能够尽可能小的改变已存在key映射关系,尽可能的满足单调性的要求。下面就来按照5个步骤简单讲讲consistenth