这种算法解决了普通余数Hash算法伸缩性差的问题

2019-10-07 04:04栏目:美高梅开户送58元官网
TAG:

Consistent hashing is a scheme that provides hash table functionality in a way that the addition or removal of one slot does not significantly change the mapping of keys to slots.

memcache 是一个分布式的缓存系统,但是本身没有提供集群功能,在大型应用的情况下容易成为瓶颈。但是客户端这个时候可以自由扩展,分两阶段实现。第一阶段:key 要先根据一定的算法映射到一台memcache服务器。第二阶段从服务器中取出缓存的值。但是有一个问题,比如其中一台服务器挂了,或者需要增加一台服务 的时候,这个时候第一阶段的算法就很重要了,怎样使得原来的数据尽可能的继续有效,减少扩展节点或缩减节点带来的冲击。下面列出想到一些解决方法:

一、概述

一致性哈希算法是分布式系统中常用的算法,为什么要用这个算法?比如:一个分布式存储系统,要将数据存储到具体的节点上, 在服务器数量不发生改变的情况下,如果采用普通的hash再对服务器总数量取模的方法(如key%服务器总数量),如果期间有服务器宕机了或者需要增加服务器,问题就出来了。 同一个key经过hash之后,再与服务器总数量取模的结果跟之前的结果会不一样,这就导致了之前保存数据的丢失。因此,引入了一致性Hash(Consistent Hashing)分布算法

一:hash一致性算法:

  1、我们的memcache客户端(这里我看的spymemcache的源码),使用了一致性hash算法ketama进行数据存储节点的选择。与常规的hash算法思路不同,只是对我们要存储数据的key进行hash计算,分配到不同节点存储。一致性hash算法是对我们要存储数据的服务器进行hash计算,进而确认每个key的存储位置。

算法的具体原理这里再次贴上:

优点:

 

先构造一个长度为2^32的整数环(这个环被称为一致性Hash环),根据节点名称的Hash值(其分布为[0, 2^32-1])将服务器节点放置在这个Hash环上,然后根据数据的Key值计算得到其Hash值(其分布也为[0, 2^32-1]),接着在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点,完成Key到服务器的映射查找。

当一个节点失效的时候,其他节点的数据不会受到破坏,这个节点的数据会被分流到另外一个节点。当增加一个节点时,只会对一个节点的一分部数据有影响。

 2、常规hash算法的应用以及其弊端

这种算法解决了普通余数Hash算法伸缩性差的问题,可以保证在上线、下线服务器的情况下尽量有多的请求命中原来路由到的服务器。

 

    最常规的方式莫过于hash取模的方式。比如集群中可用机器适量为N,那么key值为K的的数据请求很简单的应该路由到hash(K) mod N对应的机器。的确,这种结构是简单的,也是实用的。但是在一些高速发展的web系统中,这样的解决方案仍有些缺陷。随着系统访问压力的增长,缓存系统不得不通过增加机器节点的方式提高集群的相应速度和数据承载量。增加机器意味着按照hash取模的方式,在增加机器节点的这一时刻,大量的缓存命不中,缓存数据需要重新建立,甚至是进行整体的缓存数据迁移,瞬间会给DB带来极高的系统负载,设置导致DB服务器宕机。

图片 1image.png图片 2image.png

 

  3、设计分布式cache系统时,一致性hash算法可以帮我们解决哪些问题?

/** * 不带虚拟节点的一致性Hash算法 * @author 五月的仓颉http://www.cnblogs.com/xrq730/ * */public class ConsistentHashingWithoutVirtualNode{ /** * 待添加入Hash环的服务器列表 */ private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:111", "192.168.0.4:111"}; /** * key表示服务器的hash值,value表示服务器的名称 */ private static SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>(); /** * 程序初始化,将所有的服务器放入sortedMap中 */ static { for (int i = 0; i < servers.length; i++) { int hash = getHash(servers[i]); System.out.println("[" + servers[i] + "]加入集合中, 其Hash值为" + hash); sortedMap.put(hash, servers[i]); } System.out.println(); } /** * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法,最终效果没区别 */ private static int getHash(String str) { final int p = 16777619; int hash = 2166136261L; for (int i = 0; i < str.length hash = (hash ^ str.charAt * p; hash += hash << 13; hash ^= hash >> 7; hash += hash << 3; hash ^= hash >> 17; hash += hash << 5; // 如果算出来的值为负数则取其绝对值 if (hash < 0) hash = Math.abs; return hash; } /** * 得到应当路由到的结点 */ private static String getServer(String node) { // 得到带路由的结点的Hash值 int hash = getHash; // 得到大于该Hash值的所有Map SortedMap<Integer, String> subMap = sortedMap.tailMap; // 第一个Key就是顺时针过去离node最近的那个结点 Integer i = subMap.firstKey(); // 返回对应的服务器名称 return subMap.get; } public static void main(String[] args) { String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"}; for (int i = 0; i < nodes.length; i++) System.out.println("[" + nodes[i] + "]的hash值为" + getHash + ", 被路由到结点[" + getServer + "]"); }}

/** * 带虚拟节点的一致性Hash算法 * @author 五月的仓颉 http://www.cnblogs.com/xrq730/ */public class ConsistentHashingWithVirtualNode{ /** * 待添加入Hash环的服务器列表 */ private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:111", "192.168.0.4:111"}; /** * 真实结点列表,考虑到服务器上线、下线的场景,即添加、删除的场景会比较频繁,这里使用LinkedList会更好 */ private static List<String> realNodes = new LinkedList<String>(); /** * 虚拟节点,key表示虚拟节点的hash值,value表示虚拟节点的名称 */ private static SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>(); /** * 虚拟节点的数目,这里写死,为了演示需要,一个真实结点对应5个虚拟节点 */ private static final int VIRTUAL_NODES = 5; static { // 先把原始的服务器添加到真实结点列表中 for (int i = 0; i < servers.length; i++) realNodes.add(servers[i]); // 再添加虚拟节点,遍历LinkedList使用foreach循环效率会比较高 for (String str : realNodes) { for (int i = 0; i < VIRTUAL_NODES; i++) { String virtualNodeName = str + "&&VN" + String.valueOf; int hash = getHash(virtualNodeName); System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash); virtualNodes.put(hash, virtualNodeName); } } System.out.println(); } /** * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法,最终效果没区别 */ private static int getHash(String str) { final int p = 16777619; int hash = 2166136261L; for (int i = 0; i < str.length hash = (hash ^ str.charAt * p; hash += hash << 13; hash ^= hash >> 7; hash += hash << 3; hash ^= hash >> 17; hash += hash << 5; // 如果算出来的值为负数则取其绝对值 if (hash < 0) hash = Math.abs; return hash; } /** * 得到应当路由到的结点 */ private static String getServer(String node) { // 得到带路由的结点的Hash值 int hash = getHash; // 得到大于该Hash值的所有Map SortedMap<Integer, String> subMap = virtualNodes.tailMap; // 第一个Key就是顺时针过去离node最近的那个结点 Integer i = subMap.firstKey(); // 返回对应的虚拟节点名称,这里字符串稍微截取一下 String virtualNode = subMap.get; return virtualNode.substring(0, virtualNode.indexOf("&&")); } public static void main(String[] args) { String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"}; for (int i = 0; i < nodes.length; i++) System.out.println("[" + nodes[i] + "]的hash值为" + getHash + ", 被路由到结点[" + getServer + "]"); }}

缺点:

   分布式缓存设计核心点:在设计分布式cache系统的时候,我们需要让key的分布均衡,并且在增加cache server后,cache的迁移做到最少。

另:

 极容易造成节点间数据量的不平衡,可能一个节点上热点非常多,一个节点上热点很少。

   这里提到的一致性hash算法ketama的做法是:选择具体的机器节点不在只依赖需要缓存数据的key的hash本身了,而是机器节点本身也进行了hash运算。

用线程池起了1000个线程,每个线程hash10000次,模拟一万次数据hash,并将测试结果上传。

 

 

/** * 一致性hash代码 * * @author shiguiming * * @param <T> */public class Shared<T> { // 真实节点对应的虚拟节点数量 private int length = 100; // 虚拟节点信息 private TreeMap<Long, T> virtualNodes; // 真实节点信息 private List<T> realNodes; public Shared(List<T> realNodes) { this.realNodes = realNodes; init(); } public List<T> getReal() { return realNodes; } /** * 初始化虚拟节点 */ private void init() { virtualNodes = new TreeMap<Long, T>(); for (int i = 0; i < realNodes.size { for (int j = 0; j < length; j++) { virtualNodes.put(hash("aa" + i + j), realNodes.get; } } } /** * 获取一个结点 * * @param key * @return */ @SuppressWarnings("unchecked") public T getNode(String key) { Long hashedKey = hash; // TODO judge null Entry en = virtualNodes.ceilingEntry(hashedKey); if (en == null) { return  virtualNodes.firstEntry().getValue(); } return  en.getValue(); } /** * MurMurHash算法,是非加密HASH算法,性能很高, * 比传统的CRC32,MD5,SHA-1(这两个算法都是加密HASH算法,复杂度本身就很高,带来的性能上的损害也不可避免) * 等HASH算法要快很多,而且据说这个算法的碰撞率很低. http://murmurhash.googlepages.com/ */ private Long hash(String key) { ByteBuffer buf = ByteBuffer.wrap(key.getBytes; int seed = 0x1234ABCD; ByteOrder byteOrder = buf.order(); buf.order(ByteOrder.LITTLE_ENDIAN); long m = 0xc6a4a7935bd1e995L; int r = 47; long h = seed ^ (buf.remaining; long k; while (buf.remaining() >= 8) { k = buf.getLong(); k *= m; k ^= k >>> r; k *= m; h ^= k; h *= m; } if (buf.remaining { ByteBuffer finish = ByteBuffer.allocate.order(ByteOrder.LITTLE_ENDIAN); // for big-endian version, do this first: // finish.position(8-buf.remaining; finish.put.rewind(); h ^= finish.getLong(); h *= m; } h ^= h >>> r; h *= m; h ^= h >>> r; buf.order(byteOrder); return h; } /** * 测试内部类 * * @author shiguiming * */ static public class Node { private int name; private int count = 0; public Node() { } public Node { this.name = i; } public int getName() { return name; } public void setName { this.name = name; } public int getCount() { return count; } // 同步方法,防止并发 synchronized public void inc() { count++; } } /** * 测试方法 * * @param args * @throws InterruptedException */ public static void main(String[] args) throws InterruptedException { List<Node> ndList = new ArrayList<Node>(); int i = 0; while  { ndList.add(new Node; if  break; } final Shared<Node> sh = new Shared<Node>; ExecutorService es = Executors.newCachedThreadPool(); final CountDownLatch cdl = new CountDownLatch; // 1000个线程 for (int j = 0; j < 1000; j++) { es.execute(new Runnable() { @Override public void run() { // Random rd = new Random; for (int k = 0; k < 10000; k++) { sh.getNode(String.valueOf(Math.random; } cdl.countDown; } // 等待所有线程结束 cdl.await(); List<Node> nodeList = sh.getReal(); for (Node node : nodeList) { System.out.println("node" + node.getName() + ":" + node.getCount; } }}

 

二、一致性哈希算法情景描述(转载)

测试结果:

下面是具体介绍:(转自:)

 

图片 3image.png

consistent hashing 算法早在 1997 年就在论文 Consistent hashing and random trees 中被提出,目前在 cache 系统中应用越来越广泛;

1、 hash机器节点

一共10,000,000次 hash,基本算是较均匀投递到10个节点

1 基本场景

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

hash(object)%N

一切都运行正常,再考虑如下的两种情况;

1 一个 cache 服务器 m down 掉了(在实际应用中必须要考虑这种情况),这样所有映射到 cache m 的对象都会失效,怎么办,需要把 cache m 从 cache 中移除,这时候 cache 是 N-1 台,映射公式变成了 hash(object)%(N-1) ;

2 由于访问加重,需要添加 cache ,这时候 cache 是 N+1 台,映射公式变成了 hash(object)%(N+1) ;

1 和 2 意味着什么?这意味着突然之间几乎所有的 cache 都失效了。对于服务器而言,这是一场灾难,洪水般的访问都会直接冲向后台服务器;

再来考虑第三个问题,由于硬件能力越来越强,你可能想让后面添加的节点多做点活,显然上面的 hash 算法也做不到。

  有什么方法可以改变这个状况呢,这就是 consistent hashing...

 

使用Redis作为缓存服务器的,刚开始的时候会满足需要,随着项目的增大缓存数据的增多就会查询和插入更慢这时就要考虑Redis集群方案了

2 hash 算法和单调性

         Hash 算法的一个衡量指标是单调性( Monotonicity ),定义如下:

        单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。

容易看到,上面的简单 hash 算法 hash(object)%N 难以满足单调性要求。

首先求出机器节点的hash值(怎么算机器节点的hash?ip可以作为hash的参数吧。。当然还有其他的方法了),然后将其分布到0~2^32的一个圆环上(顺时针分布)。如下图所示:
图片 4

使用Redis分布式要保证数据都能能够平均的缓存到每一台机器,首先想到的做法是对数据进行分片,因为Redis是key-value存储的,首先想到的是Hash分片,可能的做法是对key进行哈希运算,得到一个long值对分布式的数量取模会得到一个一个对应数据库的一个映射,没有读取就可以定位到这台数据库,那么速度但然会提升了。

3 consistent hashing 算法的原理

consistent hashing 是一种 hash 算法,简单的说,在移除 / 添加一个 cache 时,它能够尽可能小的改变已存在 key 映射关系,尽可能的满足单调性的要求。

下面就来按照 5 个步骤简单讲讲 consistent hashing 算法的基本原理。

图一 

但是取模的hash算法是有问题的如果集群数量不变的话没有什么问题,一旦增加一台机器或者一台机器挂掉,导致机器数量变化,就会导致计算的出的数据库映射乱掉,不能正确存取数据了。

3.1 环形hash 空间

考虑通常的 hash 算法都是将 value 映射到一个 32 为的 key 值,也即是 0~2^32-1 次方的数值空间;我们可以将这个空间想象成一个首( 0)尾( 2^32-1 )相接的圆环,如下面图 1 所示的那样。

图片 5

图 1 环形 hash 空间

集群中有机器:A , B, C, D, E五台机器,通过一定的hash算法我们将其分布到如上图所示的环上。

因为这个问题引入我们说的一致性哈希算法,这个哈希算法具有的特征

3.2 把对象映射到hash 空间

接下来考虑 4 个对象 object1~object4 ,通过 hash 函数计算出的 hash 值 key 在环上的分布如图 2 所示。

hash(object1) = key1;

… …

hash(object4) = key4;

图片 6

图 2 4 个对象的 key 值分布

 

1.均衡性:也有人把它定义为平衡性,是指哈希的结果能够尽可能分布到所有的节点中去,这样可以有效的利用每个节点上的资源。

3.3 把cache 映射到hash 空间

Consistent hashing 的基本思想就是将对象和 cache 都映射到同一个 hash 数值空间中,并且使用相同的 hash 算法。

假设当前有 A,B 和 C 共 3 台 cache ,那么其映射结果将如图 3 所示,他们在 hash 空间中,以对应的 hash 值排列。

hash(cache A) = key A;

… …

hash(cache C) = key C;

图片 7

图 3 cache 和对象的 key 值分布

 

说到这里,顺便提一下 cache 的 hash 计算,一般的方法可以使用 cache 机器的 IP 地址或者机器名作为 hash 输入。

2、访问方式

2.单调性:对于单调性有很多翻译让我非常的不解,而我想要的是当节点数量变化时哈希的结果应尽可能的保护已分配的内容不会被重新分派到新的节点。

3.4 把对象映射到cache

现在 cache 和对象都已经通过同一个 hash 算法映射到 hash 数值空间中了,接下来要考虑的就是如何将对象映射到 cache 上面了。

在这个环形空间中,如果沿着顺时针方向从对象的 key 值出发,直到遇见一个 cache ,那么就将该对象存储在这个 cache 上,因为对 象和 cache 的 hash 值是固定的,因此这个 cache 必然是唯一和确定的。这样不就找到了对象和 cache 的映射方法了吗?!

依然继续上面的例子(参见图 3 ),那么根据上面的方法,对象 object1 将被存储到 cache A 上; object2 和 object3 对应到 cache C ; object4 对应到 cache B ;

如果有一个写入缓存的请求,其中Key值为K,计算器hash值Hash(K), Hash(K) 对应于图 – 1环中的某一个点,如果该点对应没有映射到具体的某一个机器节点,那么顺时针查找,直到第一次找到有映射机器的节点,该节点就是确定的目标节点,如果超过了2^32仍然找不到节点,则命中第一个机器节点。比如 Hash(K) 的值介于A~B之间,那么命中的机器节点应该是B节点(如上图 )。

3.分散性和负载:这两个其实是差不多的意思,就是要求一致性哈希算法对 key 哈希应尽可能的避免重复。

3.5 考察cache 的变动

前面讲过,通过 hash 然后求余的方法带来的最大问题就在于不能满足单调性,当 cache 有所变动时, cache 会失效,进而对后台服务器造成巨大的冲击,现在就来分析分析 consistent hashing 算法。

3.5.1 移除 cache

考虑假设 cache B 挂掉了,根据上面讲到的映射方法,这时受影响的将仅是那些沿 cache B 逆时针遍历直到下一个 cache ( cache C )之间的对象,也即是本来映射到 cache B 上的那些对象。

因此这里仅需要变动对象 object4 ,将其重新映射到 cache C 上即可;参见图 4 。

图片 8

图 4 Cache B 被移除后的 cache 映射

3.5.2 添加 cache

再考虑添加一台新的 cache D 的情况,假设在这个环形 hash 空间中, cache D 被映射在对象 object2 和 object3 之间。这时受影响的将仅是那些沿 cache D 逆时针遍历直到下一个 cache ( cache B )之间的对象(它们是也本来映射到 cache C 上对象的一部分),将这些对象重新映射到 cache D 上即可。

 

因此这里仅需要变动对象 object2 ,将其重新映射到 cache D 上;参见图 5 。

图片 9

图 5 添加 cache D 后的映射关系

 

版权声明:本文由美高梅开户送58元官网发布于美高梅开户送58元官网,转载请注明出处:这种算法解决了普通余数Hash算法伸缩性差的问题