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

    千次阅读 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();
      }
    }
    展开全文
  • 当操作分布式服务器时,“一致性哈希环”是一个有用的数据结构。 该库是基于出色的实现的Consistent Hash Ring的实现。 安装 将此添加到应用程序的shard.yml : dependencies : hash_ring : github : ...
  • 一致性哈希环

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

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

    历史恩怨:

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

    设计目的:

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

    详细设计:

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

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

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

    订单结果返回:

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

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

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

    敬请期待


    展开全文
  • #inspired by 大型分布式网站设计与实践,及 ... /* 一致性哈希 * 1,哈希值应该是无符号整形,其值范围为0~2^32-1。 * 2,哈希环节点顺时针分布。 **/ $items = 1000000; #元素 $nodes =
    <?php
    
    #inspired by 大型分布式网站设计与实践,及 https://github.com/Yikun/hashes/blob/master/virtual_consist_hash.py
    
    /* 一致性哈希 
     * 1,哈希值应该是无符号整形,其值范围为0~2^32-1。
     * 2,哈希环节点顺时针分布。
     **/
    
    $items = 1000000; #元素
    $nodes = 5; #真实节点
    $vnodes = 100; #虚拟节点
    
    $ring = []; #哈希环节点数组
    $hash2node = []; #哈希值映射到哈希环的数组
    
    $nodes_stat = []; #哈希环分布统计数据
    
    function _hash($value) {
    	$k = md5(strval($value));
    	return unpack("N", $k)[1]; // bigendian unsigned long 32bit
    }
    
    /* 返回key在哈希环中插入后的位置 */
    function bisect_left($sorted_array, $key) {
    	$left = 0; 
    	$right = count($sorted_array) - 1;
    
        if ($key < $sorted_array[$left] || $key >= $sorted_array[$right]) {
        	/* 环起点位置 */
            return 0;
        } 
    
        while($right - $left > 1) {
            $middle = intval(($left + $right) / 2);
            if ($key <= $sorted_array[$middle]) {
                $right = $middle;
            } else {
                $left = $middle;
            }
        }
    
        return $right;
    }
    
    /*test bisect_left*/
    //echo bisect_left([1,3,7,9,12,15], 10) , PHP_EOL;
    
    echo "初始化哈希环",PHP_EOL;
    
    echo sprintf("节点数 %d, 虚拟节点数 %d, 总节点数 %d, 储存键数量 %d\n", $nodes, $vnodes, $nodes*$vnodes, $items);
    
    echo "初始化哈希节点统计数据",PHP_EOL;
    for ($i = 0; $i < $nodes; $i++)
    	$nodes_stat[$i] = 0;
    
    for ($i = 0; $i < $nodes; $i++) {
    	for ($j = 0; $j < $vnodes; $j++) {
    		$h = _hash(strval($i) . strval($j));
    		array_push($ring, $h);
    		$hash2node[$h] = $i;
    	}
    }
    
    echo "排序哈希环",PHP_EOL;
    sort($ring);
    
    echo "模拟键值分布",PHP_EOL;
    # 模拟分布key到哈希环中
    for ($k = 0; $k < $items; $k++) {
    	$h = _hash($k);
    	/* 找到这个键值在哈希环的节点位置 */
    	$n = bisect_left($ring, $h) % ($nodes * $vnodes);
    	//echo sprintf("element %d distributed at node %d with hash %d\n", $k, $n, $h);
    	$nodes_stat[$hash2node[$ring[$n]]]++;
    }
    
    $avg = $items/$nodes;
    $max = max($nodes_stat);
    $min = min($nodes_stat);
    
    echo "\n哈希节点统计数据\n===",PHP_EOL;
    
    echo sprintf("avg: %d\n", $avg);
    echo sprintf("max: %0.2f 最大值与平均值的差异(%0.2f%%)\n", $max, ($max-$avg)*100.0/$avg);
    echo sprintf("min: %0.2f 最小值与平均值的差异(%0.2f%%)\n", $min, ($avg-$min)*100.0/$avg);
    
    echo "节点哈希值分布情况\n===\n";
    for ($i = 0; $i < $nodes; $i++)
    	echo sprintf("node %d, numbers: %d\n", $i, $nodes_stat[$i]);


    测试结果

    初始化哈希环
    节点数 5, 虚拟节点数 100, 总节点数 500, 储存键数量 1000000
    初始化哈希节点统计数据
    排序哈希环
    模拟键值分布
    
    哈希节点统计数据
    ===
    avg: 200000
    max: 210085.00 最大值与平均值的差异(5.04%)
    min: 185845.00 最小值与平均值的差异(7.08%)
    节点哈希值分布情况
    ===
    node 0, numbers: 191739
    node 1, numbers: 185845
    node 2, numbers: 209369
    node 3, numbers: 202962
    node 4, numbers: 210085


    引用
    展开全文
  • 一致性哈希环的简单理解

    千次阅读 2014-11-02 14:20:50
    下面说说我对一致性哈希环的理解。 我找到的资料,对哈希环最多的应用,是放到了对缓存管理方面。主要思想是构建一个环,然后将多台缓存服务器分布到哈希环的不同位置,而缓存中存放的内容,是根据一致性哈希算法...
  • 一致性哈希环(转)

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

    2018-07-22 15:43:47
    一致性哈希算在一定程度上弥补了简单哈希算法的缺点。 一致性哈希算法包含以下几个概念: 1、哈希槽:用来存储哈希数据。 2、哈希环:每个哗然槽之间相互首尾相连最终针开发一个哈希环一致性哈希在存储数据时...
  • 最重要的一点忘了写了:一致性哈希算法为啥能在节点变更的时候只有少量key迁移是因为sortkeys列表其实就是一个哈希环,客户端的哈希...open-falcon中transfer会为judge和graph生成两个一致性哈希环 func initNodeRi...
  • 一致性哈希及chord

    2018-11-27 16:41:54
    一、一致性哈希 转自:一致性Hash(Consistent Hashing)原理剖析 二、chord 转自:Chord算法(原理)  
  • 一致性哈希原理

    2021-02-28 16:02:27
    一致性哈希的实现原理
  • 一致性哈希算法

    2019-11-23 00:19:21
    一致性哈希算法一、为什么使用一致性哈希算法二、一致性哈希算法三、哈希偏斜 一、为什么使用一致性哈希算法        在 Redis 分布式锁中,我们通过部署多台 Redis 的 Master ...
  • 随着memcache和redis的出现,更多人认识到了一致性哈希一致性哈希用于解决分布式缓存系统中的数据选择节点存储问题和数据选择节点读取问题以及在增删节点后减少数据缓存的消失范畴,防止雪崩的发生。 哈希槽是...
  • 首先建立一个2的32次方环,0~2的32次方-1,首尾相连,构建一个一致性哈希环; 把服务器若干个虚拟节点的哈希值,放到这个环上; 要计算的哈希值的Key值,也放到环上; 从这个Key值,顺时针查找,离它最近的虚拟节点...
  • 一致性哈希算法原理详解

    多人点赞 2021-10-17 18:31:32
    (1)一致性哈希算法将整个哈希值空间按照顺时针方向组织成一个虚拟的圆环,称为 Hash ; (2)接着将各个服务器使用 Hash 函数进行哈希,具体可以选择服务器的IP或主机名作为关键字进行哈希,从而确定每台机器在...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,133
精华内容 6,853
关键字:

一致性哈希环