分布式之一致性hash

旧城等待， 2023-06-12 08:38 4阅读 0赞

### 文章目录 ###

*  一致性hash算法介绍
 *  图片教学
 *   *  原本数据结构图
     *  新增节点情况
     *  删除情况
 *  实现一致性hash算法
 *   *  分析代码
     *  github
 *  参考博客

# 一致性hash算法介绍 #

负载均衡算法：一般使用储存的数据%机器台数，但是一旦新增机器或者减少机器，就会影响所有原本导向的节点。
    	比如：目前储存数据：6，有4台机器，它会是6%4=2，会保存在2号机器。但是一旦新增一台机器，6%5=1，
    变成储存在一号机器。原本所有的数据都不见了，这是个很大的问题。
    
    	一致性hash算法：就是即使机器经常变动，对原本数据的影响以及搬迁不大。使用就近节点储存数据的原则，
    怎么理解呢？它是一个闭环的结构，当你数据落在节点则保存在节点上。如果数据不落在节点上，则按统一的一个方向，
    就近储存数据。

# 图片教学 #

## 原本数据结构图 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODMzNjY1OA_size_16_color_FFFFFF_t_70]

原本hash闭环图，Data数据就近赋值，比如:Data1，其实是不落在节点上的，就近原则落在Node1上。

## 新增节点情况 ##

**新增但无影响其他数据的情况**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODMzNjY1OA_size_16_color_FFFFFF_t_70 1]

新增Node4节点，看到对原本数据是没有影响的。

**新增有影响的情况**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODMzNjY1OA_size_16_color_FFFFFF_t_70 2]

为了方便演示，把节点和数据移动了一下！
    	可以看到，新增Node4节点，但是原本的Data1就近原则落在Node4节点上。（原本Data1已经不存在了，
    按照一致性hash算法的话,它会在Node4去查这个Data1的数据，为空。这个时候重新put进去到Node4）

## 删除情况 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODMzNjY1OA_size_16_color_FFFFFF_t_70 3]

这个删除情况当然是会影响原本数据的，用胸肌想一下就知道了。

# 实现一致性hash算法 #

这个是参考下面博客滴~

## 分析代码 ##

**变量**

/** 按照 键 排序*/
    TreeMap<Integer, Node> nodes = new TreeMap<>();

使用TreeMap来获取最近的节点

**put方法**

void put(Obj obj) {
      int objHashcode = obj.hashCode();
      Node node = nodes.get(objHashcode);
      if (node != null) {
        node.putObj(obj);
        return;
      }
    
      // 找到比给定 key 大的集合
      SortedMap<Integer, Node> tailMap = nodes.tailMap(objHashcode);
      // 找到最小的节点
      int nodeHashcode = tailMap.isEmpty() ? nodes.firstKey() : tailMap.firstKey();
      nodes.get(nodeHashcode).putObj(obj);
    
    }

根据nodes.tailMap方法找到比这个数据大的节点，如果有则说明数据落在最大节点Map里面的最小的节点上。  
如果没有比它大的节点map，由于是闭环！！！把数据赋值给第一个最小节点。

**get方法**

Obj get(Obj obj) {
      Node node = nodes.get(obj.hashCode());
      if (node != null) {
        return node.getObj(obj);
      }
    
      // 找到比给定 key 大的集合
      SortedMap<Integer, Node> tailMap = nodes.tailMap(obj.hashCode());
      // 找到最小的节点
      int nodeHashcode = tailMap.isEmpty() ? nodes.firstKey() : tailMap.firstKey();
      return nodes.get(nodeHashcode).getObj(obj);
    }

如果落在节点上。直接获取节点上的数据。如果不在节点上，就近找到节点获取数据。

## github ##

[一致性hash实现][hash].

# 参考博客 #

[自己实现一个一致性-Hash-算法][-Hash-].

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODMzNjY1OA_size_16_color_FFFFFF_t_70]: /images/20230531/7fe40f98deb04323a616a64277dc1de0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODMzNjY1OA_size_16_color_FFFFFF_t_70 1]: /images/20230531/d0470b0d65a5412893198c7051204314.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODMzNjY1OA_size_16_color_FFFFFF_t_70 2]: /images/20230531/4c55584bfa7d429f9e4c7a0940c37396.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODMzNjY1OA_size_16_color_FFFFFF_t_70 3]: /images/20230531/ff2e8b3557db4da2b0bfa6c874be4f63.png
[hash]: https://github.com/dajitui/UniqueHash
[-Hash-]: https://thinkinjava.cn/2018/03/31/2018/2018-03-31-%E8%87%AA%E5%B7%B1%E5%AE%9E%E7%8E%B0%E4%B8%80%E4%B8%AA%E4%B8%80%E8%87%B4%E6%80%A7-Hash-%E7%AE%97%E6%B3%95/