精华内容
下载资源
问答
  • 一致性哈希环

    千次阅读 2015-02-05 22:17:07
    一致性哈希环

    大神的分享,我写下自己的一些理解


    首先,思考一个问题:你有一个亿级访问量的网站,每天每小时每分钟有大量的数据在传输,存读数据库非常频繁,服务器的压力很大。然后我们的解决方案是什么:缓存,memcache,redis。那么,问题来了,你有10台缓存服务器,想象一下:一条数据来了要写,写到哪台服务器上去;一个请求来了,要取一条数据,从哪台服务器取?读、取数据如何合理的选择服务器?


    常规的解决方案是:随机,随机选择服务器
    但是会带来问题,(1)数据冗余,同一份数据可能冗余存在于多台服务器上(因为每次选择读/取的服务器是完全随机的)
         (2)数据访问失败:数据存在与server1上,但是读取的时候随机到了server2上,所以就会读不到数据
    这显然是一个很严重的问题


    解决方案:
    一致性哈希环---(当然这也是一种相对的解决方案,但是基本已经可以解决实际中的场景,算法的缺陷还可以通过实际场景中的做一些弥补)
    一致性哈希环存在的问题:分配不均衡


    解决方案:
    虚拟节点(找下一个节点,为什么不用就近原则去找,因为就近的原则还是不能均衡的)

    代码实现:
    参考github:https://github.com/897798676/consistent-hash





    展开全文
  • 一致性哈希环的理论实现

    千次阅读 2018-03-11 22:48:53
    也就是一致性哈希算法的具体实现,由一位微软工程师在提交社区代码时,笔者review到的,感觉代码实现严谨简洁,并且把一致性哈希环的特点全考虑到了,是一段很不错的算法程序。本文简单对其进行分析,解释。一致性...

    前言


    最近阅读社区代码时,发现了一段富有创造性的程序算法–一致性哈希环。也就是一致性哈希算法的具体实现,由一位微软工程师在提交社区代码时,笔者review到的,感觉代码实现严谨简洁,并且把一致性哈希环的特点全考虑到了,是一段很不错的算法程序。本文简单对其进行分析,解释。一致性哈希算法这里就不多介绍了,可点击笔者之前写过的文章一致性哈希算法。一致性哈希算法在分布式系统中有很多的应用场景,主要是为了解决数据出现“热点”问题。目前这段算法是用于为待写入数据选择目标集群位置的,目标集群会有很多个,而写入的文件数据只能选择其中1个集群。

    一致性哈希环算法实现

    /**
     * Consistent hash ring to distribute items across nodes (locations). If we add
     * or remove nodes, it minimizes the item migration.
     * 一致性哈希环,分散化实体项的节点位置选择,减少因为节点的变更导致的其上所属实体项的迁移。
     */
    public class ConsistentHashRing {
      private static final String SEPERATOR = "/";
      private static final String VIRTUAL_NODE_FORMAT = "%s" + SEPERATOR + "%d";
    
      /** Hash ring 哈希环. */
      private SortedMap<String, String> ring = new TreeMap<String, String>();
      /** 虚拟节点信息 -> 节点数 映射信息 */
      /** Entry -> num virtual nodes on ring. */
      private Map<String, Integer> entryToVirtualNodes =
          new HashMap<String, Integer>();
    
      /** Synchronization 锁同步. */
      private final ReadWriteLock readWriteLock = new ReentrantReadWriteLock();
      private final Lock readLock = readWriteLock.readLock();
      private final Lock writeLock = readWriteLock.writeLock();
    
      public ConsistentHashRing(Set<String> locations) {
        for (String location : locations) {
          // 在环内添加位置信息
          addLocation(location);
        }
      }
    
      /**
       * Add entry to consistent hash ring.
       * 添加实体项到哈希环内
       * @param location Node to add to the ring.
       */
      public void addLocation(String location) {
        // 虚拟出100个节点插入
        addLocation(location, 100);
      }
    
      /**
       * Add entry to consistent hash ring.
       * 添加具体项到哈希环内
       * @param location 需要添加的节点.
       * @param numVirtualNodes 需要添加的虚拟节点数。
       */
      public void addLocation(String location, int numVirtualNodes) {
        writeLock.lock();
        try {
          // 更新虚拟节点列表信息
          entryToVirtualNodes.put(location, numVirtualNodes);
          for (int i = 0; i < numVirtualNodes; i++) {
            // 得到虚拟节点名
            String key = String.format(VIRTUAL_NODE_FORMAT, location, i);
            // 取其哈希值
            String hash = getHash(key);
            // 加入到哈希环内
            ring.put(hash, key);
          }
        } finally {
          writeLock.unlock();
        }
      }
    
      /**
       * Remove specified entry from hash ring.
       * 从哈希环内移除实体项
       * @param location Node to remove from the ring.
       */
      public void removeLocation(String location) {
        writeLock.lock();
        try {
          // 移除给定节点位置,并获取其对应的虚拟节点数
          Integer numVirtualNodes = entryToVirtualNodes.remove(location);
          for (int i = 0; i < numVirtualNodes; i++) {
            // 得到虚拟节点key,并从哈希环内移除
            String key = String.format(VIRTUAL_NODE_FORMAT, location, i);
            String hash = getHash(key);
            ring.remove(hash);
          }
        } finally {
          writeLock.unlock();
        }
      }
    
      /**
       * Return location (owner) of specified item. Owner is the next
       * entry on the hash ring (with a hash value > hash value of item).
       * 从哈希环内去得其最近的节点位置
       * @param item Item to look for.
       * @return The location of the item.
       */
      public String getLocation(String item) {
        readLock.lock();
        try {
          if (ring.isEmpty()) {
            return null;
          }
          // 计算输入路径的哈希值
          String hash = getHash(item);
          // 如果哈希环内不恰好包含此节点
          if (!ring.containsKey(hash)) {
            // 将哈希环定位到大于此key的首个位置
            SortedMap<String, String> tailMap = ring.tailMap(hash);
            // 并得到第一个大于此key的项目的key,也就是距离最近的key
            hash = tailMap.isEmpty() ? ring.firstKey() : tailMap.firstKey();
          }
          // 根据此key得到对应的虚拟节点信息
          String virtualNode = ring.get(hash);
          // 然后从虚拟节点信息中得到实际位置信息
          int index = virtualNode.lastIndexOf(SEPERATOR);
          if (index >= 0) {
            return virtualNode.substring(0, index);
          } else {
            return virtualNode;
          }
        } finally {
          readLock.unlock();
        }
      }
    
      public String getHash(String key) {
        return MD5Hash.digest(key).toString();
      }
    
      /**
       * Get the locations in the ring.
       * @return Set of locations in the ring.
       */
      public Set<String> getLocations() {
        return entryToVirtualNodes.keySet();
      }
    }
    展开全文
  • 一致性哈希环

    一致性哈希环在缓存管理方面的应用,已经说过了。详见:一致性哈希环的简单理解

    在实际开发中,我们尝试着将一致性哈希环应用到业务系统中,于是就有了这篇博文。当你看到这篇博文的时候,一个小的基于一致性哈希环的任务调度系统,已经在运行了。

    历史恩怨:

    一个交易相关的系统,伴随着业务的增长,所需要的交易时间越来越长,并且越来越不稳定,这严重的影响了系统稳定,交易安全和用户体验。

    设计目的:

    终于,有一天,一帮程序员受不了客服人员的碎碎念和产品人员的叨叨,决定对系统进行重构,重构的目的就是解决伴随着业务的增长,系统性能变缓的问题。并且提供一种可扩展的,适合集群部署的业务系统。系统必须能满足分布式部署的需要,并且能够适应将来增加分布式部署的灵活性要求。

    详细设计:

    首先,将任务异步化,由于系统客户端能对业务进行比较严格的校验,提交错误任务的几率相当小,所以,异步化真个业务流程是可行的,所以我们决定将这个业务流程异步化。即将整个流程分为订单提交,订单处理,订单返回三个阶段。

    由于任务提交部分业务简单,运算量少,所以这部分会相当快。而用户能直接看到的,也就是这部分。所以用户体验部分能很好的解决。

    对于已经提交的订单,有后台部署的处理集群,对提交的订单进行处理。该部分是性能和负载均衡的重灾区,也是哈希环的用武之地。这个留到下面进行具体说明。

    订单结果返回:

    订单处理完成后,会生成返回结果,生成的返回结果,会推送到客户端,提示用户已经处理成功(一般情况下,用户并不十分关心这部分信息)。

    这样,整个的任务处理被分为三个部分,而而用户体验到的,只是第一个订单提交部分,大大提高了系统的用户体验度。

    而对于压力比较大的订单处理部分。我们可以采用集群来处理。而集群中,任务的分配,是由基于“一致性哈希环”的任务调度系统组成。

    敬请期待


    展开全文
  • 分布式一致性哈希环

    2016-04-07 13:22:00
    大家是否有注意到前面说的话:“数组可以通过下标直接定位到相应的空间”,对就是这句,哈希表的做法其实很简单,就是把Key通过一个固定的算法函数,既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度...

    哈希表的原理与实现

    一列键值对数据,存储在一个table中,如何通过数据的关键字快速查找相应值呢?不要告诉我一个个拿出来比较key啊,呵呵。 

    大家都知道,在所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决以上的问题的。 

    具体如何做呢?大家是否有注意到前面说的话:“数组可以通过下标直接定位到相应的空间”,对就是这句,哈希表的做法其实很简单,就是把Key通过一个固定的算法函数,既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里,而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位。

    不知道说到这里,一些不了解的朋友是否大概了解了哈希表的原理,其实就是通过空间换取时间的做法。到这里,可能有的朋友就会问,哈希函数对key进行转换,取余的值一定是唯一的吗?这个当然不能保证,主要是由于hashcode会对数组长度进行取余,因此其结果由于数组长度的限制必然会出现重复,所以就会有“冲突”这一问题,至于解决冲突的办法其实有很多种,比如重复散列的方式,大概就是定位的空间已经存在value且key不同的话就重新进行哈希加一并求模数组元素个数,既 (h(k)+i) mod S , i=1,2,3…… ,直到找到空间为止。还有其他的方式大家如果有兴趣的话可以自己找找资料看看。 

    Hash表这种数据结构在java中是原生的一个集合对象,在实际中用途极广,主要有这么几个特点:

    1. 访问速度快
    2. 大小不受限制
    3. 按键进行索引,没有重复对象
    4. 用字符串(id:string)检索对象(object)

    今天整理以前写的一些算法,翻出来一个hash表的实现,就贴出来,自己也温习温习。先看看头文件,也就是数据结构的定义,相当于java中的接口的概念:

    ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    01  #include <stdio.h>
    02  
    03  #define    HASHSIZE 256
    04  
    05 //定义hash表中的节点的类型
    06 struct   nlist{
    07     struct   nlist    *next;
    08     char   *name;
    09     char   *defn;
    10  };
    11  
    12 //定义接口中的函数,也就是对外来说,这个程序可以做什么
    13  unsigned    hash(char*s);//计算一个串的hash值
    14 struct   nlist    *lookup(char*s);//查找一个value,根据key
    15 struct   nlist    *install(char*name,char*defn);//插入一个key=value的对象

    然后是具体实现:

    ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    01  #include <string.h>
    02  #include"list.h"
    03  
    04 staticstructnlist *hashtab[HASHSIZE];
    05  
    06  unsigned    hash(char*s)  //取得hash值
    07  {
    08      unsigned    hashval;
    09  
    10     for(hashval = 0; *s !='\0';s++)
    11              hashval = *s + 31 * hashval;
    12     returnhashval % HASHSIZE;
    13  }
    14  
    15 struct   nlist    *lookup(char*s)
    16  {
    17     struct   nlist    *np;
    18  
    19     for(np = hashtab[hash(s)]; np != NULL; np = np->next)
    20         if(strcmp(s,np->name) == 0)
    21             returnnp;
    22     returnNULL;
    23  }
    24  
    25 struct   nlist    *install(char*name,char*defn)
    26  {
    27     struct   nlist    *np;
    28      unsigned    hashval;
    29  
    30     if((np = lookup(name)) == NULL){
    31          np = (structnlist *)malloc(sizeof(structnlist));
    32         if(np == NULL || (np->name = strdup(name)) == NULL)
    33                 returnNULL;
    34          hashval = hash(name);
    35          np->next= hashtab[hashval];
    36          hashtab[hashval] = np;
    37      }else
    38         free((void*)np->defn);
    39     if((np->defn = strdup(defn)) == NULL)
    40             returnNULL;
    41     returnnp;
    42  }

    很简单,只有两个外部接口,

    1. install(key, value),用来插入一个新的节点
    2. lookup(key),根据一个键来进行搜索,并返回节点

    代码很简单,主要用到的hash算法跟java中的String的hashcode()方法中用到的算法一样,使用:

    ?
    1
    2
    3
    4
    5
    6
    7
    8
    1   unsigned hash(char*s)
    2   {
    3       unsigned    hashval;
    4   
    5      for(hashval = 0; *s !='\0';s++)
    6               hashval = *s + 31 * hashval;
    7      returnhashval % HASHSIZE;
    8   }

    这里的31并非随意,乃是一个经验值,选取它的目的在于减少冲突,当然,hash冲突这个问题是不能根本避免的。这里只是一个人们在测试中发现的可以相对减少hash冲突的一个数字,可能以后会发现更好的数值来。


    一致性 hash 算法

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

    基本场景

    比如你有 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 一致性 hash 算法...

    hash 算法和单调性

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

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

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

    consistent hashing 算法的原理

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

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

    1. 环形hash 空间

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

    21223634_uoCE.jpg

    2. 把对象映射到hash 空间

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

    ?
    1
    2
    3
    1   hash(object1) = key1;
    2   … …
    3   hash(object4) = key4;

    21223634_BRwY.jpg
    4 个对象的 key 值分布

    3. 把cache 映射到hash 空间

    Consistent hashing 的基本思想就是将对象和 cache 都映射到同一个 hash 数值空间中,并且使用相同的 hash 算法。假设当前有 A,B 和 C 共 3 台 cache ,那么其映射结果将如图 3 所示,他们在 hash 空间中,以对应的 hash 值排列。

    ?
    1
    2
    3
    1   hash(cache A) = key A;
    2   … …
    3   hash(cache C) = key C;

    21223634_pZzd.jpg
    cache 和对象的 key 值分布

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

    4. 把对象映射到cache

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

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

    依然继续上面的例子(上图),那么根据上面的方法:

    • 对象 object1 将被存储到 cache A 上;
    • object2和 object3 对应到 cache C ; 
    • object4 对应到 cache B。

    5. 考察cache 的变动

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

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

    因此这里仅需要变动对象 object4 ,将其重新映射到 cache C 上即可:

    21223635_l44C.jpg
    Cache B 被移除后的 cache 映射

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

    因此这里仅需要变动对象 object2 ,将其重新映射到 cache D 上:

    21223635_wUmw.jpg
    添加 cache D 后的映射关系

    虚拟节点

    考量 Hash 算法的另一个指标是平衡性 (Balance) ,定义如下:

    平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。

    hash 算法并不是保证绝对的平衡,如果 cache 较少的话,对象并不能被均匀的映射到 cache 上,比如在上面的例子中,仅部署 cache A 和 cache C 的情况下,在 4 个对象中, cache A 仅存储了 object1 ,而 cache C 则存储了 object2 、 object3 和 object4 ;分布是很不均衡的。

    为了解决这种情况, consistent hashing 引入了“虚拟节点”的概念,它可以如下定义:

    “虚拟节点”( virtual node )是实际节点在 hash 空间的复制品( replica ),一实际个节点对应了若干个“虚拟节点”,这个对应个数也成为“复制个数”,“虚拟节点”在 hash 空间中以 hash 值排列。

    仍以仅部署 cache A 和 cache C 的情况为例,在前面 中我们已经看到, cache 分布并不均匀。现在我们引入虚拟节点,并设置“复制个数”为 2 ,这就意味着一共会存在 4 个“虚拟节点”, cache A1, cache A2 代表了 cache A ; cache C1, cache C2 代表了 cache C ;假设一种比较理想的情况,参见下图 。

    21223636_3TXC.jpg
    引入“虚拟节点”后的映射关系

    此时,对象到“虚拟节点”的映射关系为:

    ?
    1
    2
    3
    4
    1   objec1->cache A2
    2   objec2->cache A1
    3   objec3->cache C1
    4   objec4->cache C2 ;

    因此对象 object1 和 object2 都被映射到了 cache A 上,而 object3 和 object4 映射到了 cache C 上;平衡性有了很大提高。引入“虚拟节点”后,映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所在 cache 时的映射关系如图 7 所示。

    21223636_Ld8u.jpg
    查询对象所在 cache

    “虚拟节点”的 hash 计算可以采用对应节点的 IP 地址加数字后缀的方式。例如假设 cache A 的 IP 地址为 202.168.14.241 。

    引入“虚拟节点”前,计算 cache A 的 hash 值:Hash("202.168.14.241");

    引入“虚拟节点”后,计算“虚拟节”点 cache A1 和 cache A2 的 hash 值:

    ?
    1
    2
    1   Hash("202.168.14.241#1"); // cache A1
    2   Hash("202.168.14.241#2"); // cache A2

    小结

    Consistent hashing 的基本原理就是这些,具体的分布性等理论分析应该是很复杂的,不过一般也用不到。


    分布式哈希算法

    我们从浅入深一步一步介绍什么是分布式哈希表。

    哈希函数

    哈希函数是一种计算方法,它可以把一个值A映射到一个特定的范围[begin, end]之内。对于一个值的集合{k1, k2, … , kN},哈希函数把他们均匀的映射到某个范围之中。这样,通过这些值就可以很快的找到与之对应的映射地址{index1, index2, … , indexN}。对于同一个值,哈希函数要能保证对这个值的运算结果总是相同的。

    21223637_ngeH.png

    哈希函数需要经过精心设计才能够达到比较好的效果,但是总是无法达到理想的效果。多个值也许会映射到同样的地址上。这样就会产生冲突,如图中的红线所示。在设计哈希函数时要尽量减少冲突的产生。

    最简单的哈希函数就是一个求余运算:  hash(A) = A % N。这样就把A这个值映射到了[0~N-1]这样一个范围之中。

    哈希表

    哈希表的核心就是哈希函数hash()。

    哈希表是一中数据结构,它把KEY 和 VALUE用某种方式对应起来。使用hash()函数把一个KEY值映射到一个index上,即hash(KEY) = index。这样就可以把一个KEY值同某个index对应起来。然后把与这个KEY值对应的VALUE存储到index所标记的存储空间中。这样,每次想要查找KEY所对应的VALUE值时,只需要做一次hash()运算就可以找到了。

    举个例子:图书馆中的书会被某人借走,这样“书名”和“人名”之间就形成了KEY与VALUE的关系。假设现在有三个记录:

    简明现代魔法 小明
    最后一天 小红
    变形记 小红

    这就是“书名”和“人名”的对应关系,它表示某人借了某本书。现在我们把这种对应关系用哈希表存储起来,它们的hash()值分别为:

    hash(简明现代魔法) = 2
    hash(最后一天) = 0
    hash(变形记) = 1

    然后我们就可以在一个表中存储“人名”了:

    0 小红
    1 小红
    2 小明

    这三个人名分别存储在0、1和2号存储空间中。当我们想要查找《简明现代魔法》这本书是被谁借走的时候,只要hash()一下这个书名,就可以找到它所对应的index,为2。然后在这个表中就可以找到对应的人名了。在这里,KEY为“书名”, VALUE为“人名”。

    当有大量的KEY VALUE对应关系的数据需要存储时,这种方法就非常有效。

    分布式哈希表

    哈希表把所有的东西都存储在一台机器上,当这台机器坏掉了之后,所存储的东西就全部消失了。分布式哈希表可以把一整张哈希表分成若干个不同的部分,分别存储在不同的机器上,这样就降低了数据全部被损坏的风险。

    分布式哈希表通常采用一致性哈希函数来对机器和数据进行统一运算。这里先不用深究一致性哈希究竟是什么,只需要知道它是对机器(通常是其IP地址)和数据(通常是其KEY值)进行统一的运算,把他们全都映射到一个地址空间中。假设有一个一致性哈希函数可以把一个值映射到32bit的地址空间中,从0一直到2^32 – 1。我们用一个圆环来表示这个地址空间。

    21223634_uoCE.jpg

    假设有N台机器,那么hash()就会把这N台机器映射到这个环的N个地方。然后我们把整个地址空间进行一下划分,使每台机器控制一个范围的地址空间。这样,当我们向这个系统中添加数据的时候,首先使用hash()函数计算一下这个数据的index,然后找出它所对应的地址在环中属于哪个地址范围,我们就可以把这个数据放到相应的机器上。这样,就把一个哈希表分布到了不同的机器上。如下图所示:

    21223634_pZzd.jpg

    这里蓝色的圆点表示机器,红色的圆点表示某个数据经过hash()计算后所得出的地址。

    在这个图中,按照逆时针方向,每个机器占据的地址范围为从本机器开始一直到下一个机器为止。用顺时针方向来看,每个机器所占据的地址范围为这台机器之前的这一段地址空间。图中的虚线表示数据会存储在哪台机器上。

    哈希表的工作原理与常用操作

    哈希表(Hash Table)的应用近两年才在NOI中出现,作为一种高效的数据结构,它正在竞赛中发挥着越来越重要的作用。 

    哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下,用空间换时间的做法是值得的。另外,编码比较容易也是它的特点之一。 

    哈希表又叫做散列表,分为“开散列” 和“闭散列”。考虑到竞赛时多数人通常避免使用动态存储结构,本文中的“哈希表”仅指“闭散列”,关于其他方面读者可参阅其他书籍。

    基础操作 

    我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数, 也叫做散列函数),使得每个元素的关键字都与一个函数值(即数组下标)相对应,于是用这个数组单元来存储这个元素。也可以简单的理解为,按照关键字为每一 个元素“分类”,然后将这个元素存储在相应“类”所对应的地方。

    但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了“冲突”,换句话说,就是把不同的元素分在了相同的“类”之中。后面我们将看到一种解决“冲突”的简便做法。 

    总的来说,“直接定址”与“解决冲突”是哈希表的两大特点。 

    函数构造:构造函数的常用方法(下面为了叙述简洁,设 h(k) 表示关键字为 k 的元素所对应的函数值): 

    • 除余法: 选择一个适当的正整数 p ,令 h(k ) = k mod p ,这里, p 如果选取的是比较大的素数,效果比较好。而且此法非常容易实现,因此是最常用的方法。 
    • 数字选择法: 如果关键字的位数比较多,超过长整型范围而无法直接运算,可以选择其中数字分布比较均匀的若干位,所组成的新的值作为关键字或者直接作为函数值。 

    冲突处理:线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 S ,则当 h(k) 已经存储了元素的时候,依次探查 (h(k)+i) mod S , i=1,2,3…… ,直到找到空的存储单元为止(或者从头到尾扫描一圈仍未发现空单元,这就是哈希表已经满了,发生了错误。当然这是可以通过扩大数组范围避免的)。 

    支持运算:哈希表支持的运算主要有:初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member)。 设插入的元素的关键字为 x ,A 为存储的数组。 初始化比较容易,例如 :

    ?
    1
    2
    3
    4
    5
    6
    7
    8
    1  constempty=maxlongint;// 用非常大的整数代表这个位置没有存储元素
    2   p=9997;// 表的大小
    3   procedure makenull;
    4   var i:integer;
    5   begin
    6  fori:=0 to p-1do
    7   A[i]:=empty;
    8   End; 

    哈希函数值的运算根据函数的不同而变化,例如除余法的一个例子:

    ?
    1
    2
    3
    4
    1   function h(x:longint):Integer;
    2   begin
    3   h:= x mod p;
    4   end;

    我们注意到,插入和查找首先都需要对这个元素定位,即如果这个元素若存在,它应该存储在什么位置,因此加入一个定位的函数 locate。

    ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    01  function locate(x:longint):integer;
    02  var orig,i:integer;
    03  begin
    04  orig:=h(x);
    05  i:=0;
    06 while(i < S)and(A[(orig+i)mod S]<>x)and(A[(orig+i)mod S]<>empty)do
    07  inc(i);
    08 //当这个循环停下来时,要么找到一个空的存储单元,要么找到这个元
    09 //素存储的单元,要么表已经满了
    10  locate:=(orig+i) mod S;
    11  end; 

    插入元素:

    ?
    1
    2
    3
    4
    5
    6
    7
    1   procedure insert(x:longint);
    2   var posi:integer;
    3   begin
    4   posi:=locate(x);//定位函数的返回值
    5  ifA[posi]=empty then A[posi]:=x
    6  elseerror;//error 即为发生了错误,当然这是可以避免的
    7   end; 

    查找元素是否已经在表中:

    ?
    1
    2
    3
    4
    5
    6
    7
    1   procedure member(x:longint):boolean;
    2   var posi:integer;
    3   begin
    4   posi:=locate(x);
    5  ifA[posi]=x then member:=true
    6  elsemember:=false;
    7   end;

    这些就是建立在哈希表上的常用基本运算。

    当数据规模接近哈希表上界或者下界的时候,哈希表完全不能够体现高效的特点,甚至还不如一般算法。但是如果规模在中央,它高效的特点可以充分体现。试验表明当元素充满哈希表的 90% 的时候,效率就已经开始明显下降。这就给了我们提示:如果确定使用哈希表,应该尽量使数组开大,但对最太大的数组进行操作也比较费时间,需要找到一个平衡点。通常使它的容量至少是题目最大需求的 120% ,效果比较好(这个仅仅是经验,没有严格证明)。

    应用举例

    什么时候适合应用哈希表呢?如果发现解决这个问题时经常要询问:“某个元素是否在已知集合中?”,也就是需要高效的数据存储和查找,则使用哈希表是最好不过的了!那么,在应用哈希表的过程中,值得注意的是什么呢? 

    哈希函数的设计很重要。一个不好的哈希函数,就是指造成很多冲突的情况,从前面的例子已经可以看出来,解决冲突会浪费掉大量时间,因此我们的目标就是尽力避免冲突。前面提到,在使用“除余法”的时候,h(k)=k mod p ,p 最好是一个大素数。这就是为了尽力避免冲突。为什么呢?假设 p=1000 ,则哈希函数分类的标准实际上就变成了按照末三位数分类,这样最多1000类,冲突会很多。一般地说,如果 p 的约数越多,那么冲突的几率就越大。 

    简单的证明:假设 p 是一个有较多约数的数,同时在数据中存在 q 满足 gcd(p,q)=d >1 ,即有 p=a*d , q=b*d, 则有 q mod p= q – p* [q div p] =q – p*[b div a] . ① 其中 [b div a ] 的取值范围是不会超过 [0,b] 的正整数。也就是说, [b div a] 的值只有 b+1 种可能,而 p 是一个预先确定的数。因此 ① 式的值就只有 b+1 种可能了。这样,虽然mod 运算之后的余数仍然在 [0,p-1] 内,但是它的取值仅限于 ① 可能取到的那些值。也就是说余数的分布变得不均匀了。容易看出, p 的约数越多,发生这种余数分布不均匀的情况就越频繁,冲突的几率越高。而素数的约数是最少的,因此我们选用大素数。记住“素数是我们的得力助手”。 

    另一方面,一味的追求低冲突率也不好。理论上,是可以设计出一个几乎完美,几乎没有冲突的函数的。然而,这样做显然不值得,因为这样的函数设计 很浪费时间而且编码一定很复杂,与其花费这么大的精力去设计函数,还不如用一个虽然冲突多一些但是编码简单的函数。因此,函数还需要易于编码,即易于实现。 

    综上所述,设计一个好的哈希函数是很关键的。而“好”的标准,就是较低的冲突率和易于实现。 

    另外,使用哈希表并不是记住了前面的基本操作就能以不变应万变的。有的时候,需要按照题目的要求对哈希表的结构作一些改进。往往一些简单的改进就可以带来巨大的方便。 

    这些只是一般原则,真正遇到试题的时候实际情况千变万化,需要具体问题具体分析才行。

    转载于:https://my.oschina.net/tantexian/blog/654116

    展开全文
  • #inspired by 大型分布式网站设计与实践,及 ... /* 一致性哈希 * 1,哈希值应该是无符号整形,其值范围为0~2^32-1。 * 2,哈希环节点顺时针分布。 **/ $items = 1000000; #元素 $nodes =
  • 一致性哈希环(转)

    2013-08-12 10:56:15
    本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及其在分布式系统中的应用。首先本文会描述一个在日常开发中经常会遇到的问题场景,借此介绍一致性哈希算法以及这个算法如何解决此问题;接...
  • 一致性哈希环的简单理解

    千次阅读 2014-11-02 14:20:50
    下面说说我对一致性哈希环的理解。 我找到的资料,对哈希环最多的应用,是放到了对缓存管理方面。主要思想是构建一个环,然后将多台缓存服务器分布到哈希环的不同位置,而缓存中存放的内容,是根据一致性哈希算法...
  • 前言一致性哈希算法在分布式系统的应用中是十分广泛的。常见的应用场景是分布式缓存。它主要解决了哈希取模算法在分布式系统...一致性哈希算法原理一致性哈希算法通过一个叫作一致性哈希环的数据结构实现。这个环的...
  • 一致性哈希算法(Consistent Hashing)最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。简单来说,一致性哈希将整个哈希...
  • 一致性哈希及chord

    2018-11-27 16:41:54
    一、一致性哈希 转自:一致性Hash(Consistent Hashing)原理剖析 二、chord 转自:Chord算法(原理)  
  • 以实际案例来说,一致性哈希就是以服务器的IP或主机名和要保存到这些服务器上的数据的键名为关键字,通过哈希函数,将这些服务器和数据顺时针映射到一个虚拟的圆环上,以达到无论是增加服务器,还是减少服务器,原来...
  • 一致性哈希

    2018-07-22 15:43:47
    一致性哈希算在一定程度上弥补了简单哈希算法的缺点。 一致性哈希算法包含以下几个概念: 1、哈希槽:用来存储哈希数据。 2、哈希环:每个哗然槽之间相互首尾相连最终针开发一个哈希环一致性哈希在存储数据时...
  • 节点(机器)的添加平衡性一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简 单哈希...
  • Loki在分布式部署的模式下,...再聊Loki之前,先来了解下一致性哈希的基本概念。一致性哈希是在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法。相较于普通的哈希算法,一致性哈希除了继承数据的离散性、...
  • 一致性哈希算法

    2020-09-23 15:09:13
    一致性哈希将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0-2^32-1(即哈希值是一个32位无符号整形),整个哈希空间如下: Memcached简介 一致性哈希算法 一致性HASH算法的JAVA实现 一致性...
  • 最重要的一点忘了写了:一致性哈希算法为啥能在节点变更的时候只有少量key迁移是因为sortkeys列表其实就是一个哈希环,客户端的哈希...open-falcon中transfer会为judge和graph生成两个一致性哈希环 func initNodeRi...
  • 一致性哈希原理应用

    千次阅读 2021-01-27 14:09:28
    一致性哈希 文章目录一致性哈希前言一、基本概念/原理二、优势1....一致性哈希算法也是使用取模的方法,只不过是对232取模,然后将232个点均匀的散列在一个圆上,这个圆环叫做哈希环。    &
  • 首先建立一个2的32次方环,0~2的32次方-1,首尾相连,构建一个一致性哈希环; 把服务器若干个虚拟节点的哈希值,放到这个环上; 要计算的哈希值的Key值,也放到环上; 从这个Key值,顺时针查找,离它最近的虚拟节点...
  • 一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简 单哈希算法带来的问题,使得...
  • 一致性哈希原理

    2019-03-18 17:46:52
    一致性哈希算法(Consistent Hashing)最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。简单来说,一致性哈希将整个...
  • 一致性哈希 先看一致性hash,常见的一个环形图如下: 在1997年,麻省理工学院的 Karger 等人提出了一致性哈希算法,为的就是解决分布式缓存的问题。 在一致性哈希算法中,整个哈希空间是一个虚拟圆环。 对于各个 ...

空空如也

空空如也

1 2 3 4 5 ... 16
收藏数 301
精华内容 120
关键字:

一致性哈希环