文章序言1、什么是连贯的Hash？ 二、步骤1 .一致性混列算法ConsistentHashAlgorithm 2.初始化表节点，混列环InitTableNodesToHashLoop 3.分表算法ConsistentShardingAlgorithm 4
前言几篇文章主要介绍了Springboot Sharding-JDBC在存储库分区表中的实践，但在实际场景中，可能需要扩展已经表化的表节点。 那么，在分表算法过多的情况下，如果增加一个节点，现有的大部分数据就会被转移，工程量就会变得庞大。
那除了求剩余表的算法以外，其他算法在缩小扩展场景中能做得更好吗？ 接下来，我们来看看一致性哈希算法在分类表中的应用。
一、一致性Hash是什么？ 一致性哈希算法由麻省理工学院于1997年提出，是一种用于解决分布式缓存问题的特殊哈希算法。 删除或添加服务时，可以尽可能小地修改现有服务请求与处理请求服务之间的映射关系。 一致性散列解决了简单散列算法存在于分布式散列表(分布式散列表，DHT )中的动态伸缩等问题
一致性散列算法将整个散列空间映射到虚拟圆环，整个散列空间的取值范围为0— 2 32 2^{32} 232-1。 整个空间按顺时针方向组织。 0— 2 32 2^{32} 232与零点的中方向重叠。 然后，使用散列算法映射服务请求，使用散列算法计算相应的散列值，并根据散列值的位置沿环顺时针搜索服务请求。 第一个遇到的服务器是对应的处理请求服务器。 添加新服务器时，受影响的数据只有新添加的服务器和环空间中的上一台服务器(即第一台逆时针遇到的服务器)之间的数据，其他数据不受影响。 综上所述，一致性散列算法对于节点的增减只需要重新配置环空间中的一部分数据，具有良好的容错性和可扩展性；
那么，在分表应用中，如下图所示，首先对table1、table2、table3、table4进行混列计算，得到key1、key2、key3、key4，范围为0—2 32 ^ { 32 } 此时，我们用id进行分表操作。 那么，保存时，首先对id进行散列计算，求出散列值(hash(id1 ) )，得到的值沿着环顺时针找到第一个遇到的表节点，即数据保存的真正的表节点。 接下来，让我们看一下Sharding-jdbc中的实际使用
二、步骤1 .使用一致的混列算法consistenthashalgorithmpublicclassconsistenthashalgorithm//虚拟节点。 key是虚拟节点的散列值，value是虚拟节点的名称@表示@getterprivate的//节点的数量少时，数据的分布容易变得不均匀，所以增加虚拟节点来平均化数据的分布//虚拟节点的数量； 虚拟节点的生成主要是为了尽可能均匀地分布数据//虚拟节点是实节点的不同映射。 //例如，如果实际节点user1的散列值为100，则增加3个虚拟节点user1-1、user1-2、user1-3，分别计算的散列值也可以为200、345、500； 由此，使节点均匀分布privatestaticfinalintvirtual _ nodes=3； publicconsistenthashalgorithm ({ } publicconsistenthashalgorithm (sortedmaplong，String virtualTableNodes， collectionstringtablenodes (if (objects.is null ) virtualtablenodes ) ) virtualtablenodes=initnodestohashloop ) table } }公共
SortedMap<Long, String> initNodesToHashLoop(Collection<String> tableNodes) { SortedMap<Long, String> virtualTableNodes = new TreeMap<>(); for (String node : tableNodes) { for (int i = 0; i < VIRTUAL_NODES; i++) { String s = String.valueOf(i); String virtualNodeName = node + "-VN" + s; long hash = getHash(virtualNodeName); virtualTableNodes.put(hash, virtualNodeName); } } return virtualTableNodes; } /** * 通过计算key的hash * 计算映射的表节点 * * @param key * @return */ public String getTableNode(String key) { String virtualNode = getVirtualTableNode(key); //虚拟节点名称截取后获取真实节点 if (StringUtils.isNotBlank(virtualNode)) { return virtualNode.substring(0, virtualNode.indexOf("-")); } return null; } /** * 获取虚拟节点 * @param key * @return */ public String getVirtualTableNode(String key) { long hash = getHash(key); // 得到大于该Hash值的所有Map SortedMap<Long, String> subMap = virtualNodes.tailMap(hash); String virtualNode; if (subMap.isEmpty()) { //如果没有比该key的hash值大的，则从第一个node开始 Long i = virtualNodes.firstKey(); //返回对应的服务器 virtualNode = virtualNodes.get(i); } else { //第一个Key就是顺时针过去离node最近的那个结点 Long i = subMap.firstKey(); //返回对应的服务器 virtualNode = subMap.get(i); } return virtualNode; } /** * 使用FNV1_32_HASH算法计算key的Hash值 * * @param key * @return */ public long getHash(String key) { final int p = 16777619; int hash = (int) 2166136261L; for (int i = 0; i < key.length(); i++) hash = (hash ^ key.charAt(i)) * p; hash += hash << 13; hash ^= hash >> 7; hash += hash << 3; hash ^= hash >> 17; hash += hash << 5; // 如果算出来的值为负数则取其绝对值 if (hash < 0) hash = Math.abs(hash); return hash; }} 2.初始化表结点，并映射到hash环该步骤会在应用启动时初始化分表的表结点，提前进行hash计算
InitTableNodesToHashLoop public class InitTableNodesToHashLoop { @Resource private ShardingDataSource shardingDataSource; @Getter private HashMap<String, SortedMap<Long, String>> tableVirtualNodes = new HashMap<>(); @PostConstruct public void init() { try { ShardingRule rule = shardingDataSource.getRuntimeContext().getRule(); Collection<TableRule> tableRules = rule.getTableRules(); ConsistentHashAlgorithm consistentHashAlgorithm = new ConsistentHashAlgorithm(); for (TableRule tableRule : tableRules) { String logicTable = tableRule.getLogicTable(); tableVirtualNodes.put(logicTable, consistentHashAlgorithm.initNodesToHashLoop( tableRule.getActualDataNodes() .stream() .map(DataNode::getTableName) .collect(Collectors.toList())) ); } } catch (Exception e) { log.error("分表节点初始化失败 {}", e); } }} 3.创建分表算法 ConsistentShardingAlgorithm public class ConsistentShardingAlgorithm implements PreciseShardingAlgorithm<Long>, RangeShardingAlgorithm<Long> { /** * 精确分片 * 一致性hash算法 */ @Override public String doSharding(Collection<String> availableTargetNames, PreciseShardingValue<Long> shardingValue) {//获取已经初始化的分表节点 InitTableNodesToHashLoop initTableNodesToHashLoop = SpringContextUtils.getBean(InitTableNodesToHashLoop.class); if (CollectionUtils.isEmpty(availableTargetNames)) { return shardingValue.getLogicTableName(); } //这里主要为了兼容当联表查询时，如果两个表非关联表则 //当对副表分表时shardingValue这里传递进来的依然是主表的名称， //但availableTargetNames中确是副表名称，所有这里要从availableTargetNames中匹配真实表 ArrayList<String> availableTargetNameList = new ArrayList<>(availableTargetNames); String logicTableName = availableTargetNameList.get(0).replaceAll("[^(a-zA-Z_)]", ""); SortedMap<Long, String> tableHashNode = initTableNodesToHashLoop.getTableVirtualNodes().get(logicTableName); ConsistentHashAlgorithm consistentHashAlgorithm = new ConsistentHashAlgorithm(tableHashNode, availableTargetNames); return consistentHashAlgorithm.getTableNode(String.valueOf(shardingValue.getValue())); } /** * 范围查询规则 * 可以根据实际场景进行修改 * Sharding. * * @param availableTargetNames available data sources or tables's names * @param shardingValue sharding value * @return sharding results for data sources or tables's names */ @Override public Collection<String> doSharding(Collection<String> availableTargetNames, RangeShardingValue<Long> shardingValue) { return availableTargetNames; }} 4.更改配置 tables: t_user: #t_user表 key-generator-column-name: id #主键 actual-data-nodes: ds0.t_user${0..39} #数据节点,均匀分布 table-strategy: #分表策略使用一致性hash算法 standard: sharding-column: id precise-algorithm-class-name: com.none.sharding.infrastruc.shardingAlgorithm.ConsistentShardingAlgorithm 总结以上即是一致性hash算法在分表分库中的实际应用；虽然一致性hash算法能在节点伸缩的时候尽量减少数据的迁移，但是当虚拟节点数量很多时依然会造成不少数据迁移，所以前期进行规划时一定要考虑虚拟节点的倍数设置。
Demo地址：Github