`
sandaobusi
  • 浏览: 17378 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

Consistent hash算法

阅读更多

在做服务器负载均衡时候可供选择的负载均衡的算法有很多,包括:  轮循算法(Round Robin)、哈希算法(HASH)、最少连接算法(Least Connection)、响应速度算法(Response Time)、加权法(Weighted )等。其中哈希算法是最为常用的算法.

 

典型的应用场景是: 有N台服务器提供缓存服务,需要对服务器进行负载均衡,将请求平均分发到每台服务器上,

每台机器负责1/N的服务。

 

 

常用的算法是对hash结果取余数 (hash() mod N):对机器编号从0到N-1,按照自定义的hash()算法,对每个请求的hash()值按N取模,得到余数i,然后将请求分发到编号为i的机器。但这样的算法方法存在致命问题,如果某一台机器宕机,那么应该落在该机器的请求就无法得到正确的处理,这时需要将当掉的服务器从算法从去除,此时候会有(N-1)/N的服务器的缓存数据需要重新进行计算;如果新增一台机器,会有N /(N+1)的服务器的缓存数据需要进行重新计算。对于系统而言,这通常是不可接受的颠簸(因为这意味着大量缓存的失效或者数据需要转移)。那么,如何设计一个负载均衡策略,使得受到影响的请求尽可能的少呢? 

    在Memcached、Key-Value Store、Bittorrent DHT、LVS中都采用了Consistent Hashing算法,可以说Consistent Hashing 是分布式系统负载均衡的首选算法。

 

 

1、Consistent Hashing算法描述 下面以Memcached中的Consisten Hashing算法为例说明(参考memcached的分布式算法)。 由于hash算法结果一般为unsigned int型,因此对于hash函数的结果应该均匀分布在[0,2^32-1]间,如果我

们把一个圆环用2^32个点来进行均匀切割,首先按照hash(key)函数算出服务器(节点)的哈希值, 并将其分布

到0~2^32的圆上。 用同样的hash(key)函数求出需要存储数据的键的哈希值,并映射到圆上。然后从数据映射到的位置开始顺时针

查找,将数据保存到找到的第一个服务器(节点)上。


Consistent Hashing原理示意图

 

新增一个节点的时候,只有在圆环上新增节点逆时针方向的第一个节点的数据会受到影响。删除一个节点的时候,只有在圆环上原来删除节点顺时针方向的第一个节点的数据会受到影响,因此通过Consistent Hashing很好地解决了负载均衡中由于新增节点、删除节点引起的hash值颠簸问题。

 



 Consistent Hashing添加服务器示意图

 

虚拟节点(virtual nodes):之所以要引进虚拟节点是因为在服务器(节点)数较少的情况下(例如只有3台服务器),通过hash(key)算出节点的哈希值在圆环上并不是均匀分布的(稀疏的),仍然会出现各节点负载不均衡的问题。虚拟节点可以认为是实际节点的复制品(replicas),本质上与实际节点实际上是一样的(key并不相同)。引入虚拟节点后,通过将每个实际的服务器(节点)数按照一定的比例(例如200倍)扩大后并计算其hash(key)值以均匀分布到圆环上。在进行负载均衡时候,落到虚拟节点的哈希值实际就落到了实际的节点上。由于所有的实际节点是按照相同的比例复制成虚拟节点的,因此解决了节点数较少的情况下哈希值在圆环上均匀分布的问题。



虚拟节点对Consistent Hashing结果的影响

 

从上图可以看出,在节点数为10个的情况下,每个实际节点的虚拟节点数为实际节点的100-200倍的时候,结果还是很均衡的。

 

Consistent Hashing算法实现:

主类:ConsistentHash.java

 

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHash<T> {

	private final HashFunction hashFunction;
	private final int numberOfReplicas;
	private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();

	public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,
			Collection<T> nodes) {
		this.hashFunction = hashFunction;
		this.numberOfReplicas = numberOfReplicas;

		for (T node : nodes) {
			add(node);
		}
	}

	public void add(T node) {
		for (int i = 0; i < numberOfReplicas; i++) {
			circle.put(hashFunction.hash(node.toString() + i), node);
		}
	}

	public void remove(T node) {
		for (int i = 0; i < numberOfReplicas; i++) {
			circle.remove(hashFunction.hash(node.toString() + i));
		}
	}

	public T get(Object key) {
		if (circle.isEmpty()) {
			return null;
		}
		int hash = hashFunction.hash(key);
		if (!circle.containsKey(hash)) {
			SortedMap<Integer, T> tailMap = circle.tailMap(hash);
			hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
		}
		return circle.get(hash);
	}

	public static void main(String... arg) {
		List<Node> nodelist = new ArrayList<Node>();
		nodelist.add(new Node("202.117.10.1"));
		nodelist.add(new Node("202.127.120.25"));
		nodelist.add(new Node("192.168.10.125"));
		nodelist.add(new Node("127.0.0.1"));

		ConsistentHash<Node> ch = new ConsistentHash<Node>(new HashFunction(),
				3, nodelist);
		Node node = ch.get("32563");
		System.out.println(node.toString());

	}
}

 

MD5函数类:HashFunction.java

 

 

import java.io.UnsupportedEncodingException;

import com.twmacinta.util.MD5;

public class HashFunction {

	public int hash(Object obj) {
		MD5 md5 = new MD5();
		try {
			md5.Update(obj.toString(), null);
		} catch (UnsupportedEncodingException e) {
			throw new IllegalStateException("NoSuchAlgorithmException:MD5", e);
		}
		return Math.abs(md5.asHex().hashCode());
	}

}

 

模拟节点:Node.java

 

package consistentHash;

public class Node {

	public String IP;

	/**
	 * @return the iP
	 */
	public String getIP() {
		return IP;
	}

	/**
	 * @param iP
	 *            the iP to set
	 */
	public void setIP(String iP) {
		IP = iP;
	}

	public Node(String iP) {
		this.IP = iP;
	}

	@Override
	public String toString() {
		return IP;
	}

}
 

转载:http://www.yeeach.com/2009/10/02/consistent-hashing%E7%AE%97%E6%B3%95/

  • 大小: 94.2 KB
  • 大小: 98.5 KB
  • 大小: 12.8 KB
  • 大小: 43.8 KB
分享到:
评论
2 楼 xuhang1128 2013-10-30  
谢谢 讲的很清楚
1 楼 kennyhou 2012-05-19  
好东西,谢谢分享

相关推荐

    Java语言Consistent Hash算法学习笔记(代码示例)

    public ConsistentHash(int replicas, Collection&lt;T&gt; nodes) { this.replicas = replicas; for (T node : nodes) { for (int i = 0; i ; i++) { circle.put(hash(node.toString() + "-" + i), node); } } } ...

    fly-arch:分布式架构consistent-hashing(一致性hash) http

    #fly-archflylib创立的各种常见的架构技术内容列表cassandra-demo cassandra数据库的入门编程consistent-hash Java implementation of consistent-hashing基于java的一致性hash的实现一致性hash(consistent-hashing)...

    ConsistentHash:一致性hash算法的 java 和 C++ 实现

    一致性哈希(Consistent Hashing)是一种分布式哈希表(DHT, Distributed Hash Table)算法,主要用于解决在分布式系统中数据存储和检索的问题,尤其是在动态扩展集群节点时,能够尽可能地减少缓存重建,保持系统...

    ngx_http_consistent_hash-master.zip

    "ngx_http_consistent_hash-master.zip" 是一个与 Nginx Web服务器相关的压缩包文件,其中包含了一个名为 "ngx_http_consistent_hash" 的第三方模块的源代码。"master" 指示这可能是该模块的主分支或最新版本。 **...

    开源项目-benbjohnson-jmphash.zip

    《深入理解Jump Consistent Hash算法:Go语言实现详解》 在IT行业中,分布式系统和大数据处理的广泛应用使得高效、公平的哈希算法变得至关重要。其中,Jump Consistent Hash(简称JCH)算法因其简单性和良好的负载...

    ConsistentHash:一致性hash算法案例

    一致性哈希(Consistent Hashing)是一种分布式哈希表(DHT, Distributed Hash Table)的算法,主要用于解决在分布式系统中数据分片、负载均衡、缓存分发等问题。在云计算和大数据领域,一致性哈希算法有着广泛的应用,...

    Ketama一致性Hash算法(含Java代码) 1

    一致性哈希算法(Consistent Hashing)是一种在分布式系统中平衡数据分布的策略,尤其适用于缓存服务如Memcached或Redis。它的核心思想是通过哈希函数将对象映射到一个固定大小的环形空间中,然后将服务器也映射到这个...

    一致性Hash算法的原理及实现

    ### 一致性Hash算法的原理及实现 #### 一、引言 一致性Hash算法是一种用于解决分布式环境下数据存储和检索问题的重要技术。它最初由David Karger等人在1997年的论文《Consistent Hashing and Random Trees: ...

    ConsistentHash(Ketama)

    一致性哈希(Consistent Hashing)是一种分布式哈希(Distributed Hash Table,DHT)算法,主要用于解决在分布式系统中的数据存储和检索问题。在云计算、缓存系统(如Redis、Memcached)以及负载均衡等领域广泛应用...

    Python库 | jump_consistent_hash-3.1.1-cp27-cp27m-win_amd64.whl

    资源分类:Python库 所属语言:Python 资源全名:jump_consistent_hash-3.1.1-cp27-cp27m-win_amd64.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059

    Algorithm-go-jump-consistent-hash.zip

    《深入理解Go语言实现的一致性哈希算法:jump-consistent-hash》 一致性哈希算法在分布式系统中扮演着至关重要的角色,它允许数据在分布式集群中的节点间平滑迁移,确保服务的连续性和可用性。Go语言实现的一致性...

    Inside BeansDB

    BeansDB采用了独特的数据分布方式,通过手动指定的方式将数据分配到不同的节点上,而非使用Consistent Hash算法。这一决策主要是考虑到数据迁移的成本、数据位置的清晰度以及系统的扩容便利性。随着节点数量的增加,...

    一致性Hash简单实现

    - 编写`ConsistentHash`类,实现哈希环的逻辑,包括添加节点、删除节点、查找节点等方法。 - 实现查找算法,可以使用`TreeMap`的`lowerKey()`或`ceilingKey()`方法找到环上最近的虚拟节点。 4. **优化策略** - *...

    一些刷的算法题(Some algorithm questions for brushing)

    consistentHash\consistentHash.go (3227, 2021-02-07) consistentHash\consistentHash_test.go (2019, 2021-02-07) leetcode (0, 2021-02-07) leetcode\二分查找 (0, 2021-02-07) leetcode\二分查找\34- (0, 2021-...

    NGINX配置NGX-HTTP-CONSISTENT-HASH实现一致性哈希负载均衡

    1.前置条件,您已经安装NGINX 2.NGX_HTTP_CONSISTENT_HASH 是一个用于 Nginx 的模块,可以实现基于一致性哈希的负载... consistent_hash $remote_addr; server 192.168.6.65:15672; server 192.168.7.177:15672; }

    各种hash算法-hashcodeUtil

    文件名为`ConsistentHash.java`,可能是一个实现一致性哈希的类。一致性哈希的主要特点是,当添加或删除一个节点时,只有很少的数据需要重新映射到新的节点上。 4. **JDK的HashMap和HashSet**:这些集合类依赖于...

    解决分布式数据插入数据库~一致性hash算法

    为了解决这个问题,可以采用跳数法(Jump Consistent Hash)或者更高级的一致性哈希变体,如Ketama或libketama。哈希冲突则可以通过开放寻址、链地址法等方法来解决。 此外,一致性哈希算法在分布式缓存如Memcached...

    基于一致性hash算法(consistent hashing)的使用详解

    比如你有 N 个 cache 服务器(后面简称 cache ),那么如何将一个对象 object 映射到 N 个 cache 上呢,你很可能会采用类似下面的通用方法计算 object 的 hash 值,然后均匀的映射到到 N 个 cache ; hash(object)%N...

Global site tag (gtag.js) - Google Analytics