分布式之一致性hash

mac2025-02-27  6

文章目录

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

一致性hash算法介绍

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

图片教学

原本数据结构图

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

新增节点情况

新增但无影响其他数据的情况

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

新增有影响的情况

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

删除情况

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

实现一致性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-算法.

最新回复(0)