Springboot+Sharding-JDBC 分库分表实践四之⼀致性Hash 算法
⽂章⽬录
前⾔
前⼏篇⽂章主要介绍了Springboot+Sharding-JDBC在分库分表中的实践，那么在实际场景中，我们可能会有需求对已经分表的表节点进⾏扩容。那么在分表算法为求余的情况下，如果增加⼀个节点，会导致⼤部分已存在的数据多要进⾏迁移，⼯程量巨⼤。
那除了求余分表算法外，还有其他算法能在缩扩容场景下更好的⼯作吗？！接下来我们⼀起看下⼀致性Hash算法在分库分表中的应⽤。⼀、⼀致性Hash 是什么？
⼀致性哈希算法在1997年由⿇省理⼯学院提出，是⼀种特殊的哈希算法，⽬的是解决分布式缓存的问题。 在移除或者添加⼀个服务器时，能够尽可能⼩地改变已存在的服务请求与处理请求服务器之间的映射关系。⼀致性哈希解决了简单哈希算法在分布式哈希表(Distributed Hash Table，DHT) 中存在的动态伸缩等问题
⼀致性哈希算法将整个哈希值空间映射成⼀个虚拟的圆环，整个哈希空间的取值范围为0—-1。整个空间按顺时针⽅向组织。0—在零点中⽅向重合。接下来使⽤Hash算法对服务请求进⾏映射，将服务请求使
⽤哈希算法算出对应的hash值，然后根据hash值的位置沿圆环顺时针查，第⼀台遇到的服务器就是所对应的处理请求服务器。当增加⼀台新的服务器，受影响的数据仅仅是新添加的服务器到其环空间中前⼀台的服务器（也就是顺着逆时针⽅向遇到的第⼀台服务器）之间的数据，其他都不会受到影响。综上所述，⼀致性哈希算法对于节点的增减都只需重定位环空间中的⼀⼩部分数据，具有较好的容错性和可扩展性;
232232
那么在分表应⽤中，如下图，我们先对table1、table2、table3、table4进⾏hash计算得到key1、key2、key3、key4并映射到范围为0—-1的环中；加⼊此时我们是通过id进⾏分表操作，那么在存储时，我们先对id进⾏hash计算得出hahs值（hash(id1)），得到的值沿
圆环顺时针查遇到的第⼀个表节点，即是数据存储的真实表结点；接下来我们看下在Sharding-jdbc中的实际应⽤springboot推荐算法
⼆、使⽤步骤
1.⼀致性hash 算法
ConsistentHashAlgorithm
public class ConsistentHashAlgorithm {
//虚拟节点，key 表⽰虚拟节点的hash 值，value 表⽰虚拟节点的名称
@Getter
private SortedMap <Long , String > virtualNodes = new TreeMap <>();
//当节点的数⽬很少时，容易造成数据的分布不均，所以增加虚拟节点来平均数据分布
//虚拟节点的数⽬；虚拟节点的⽣成主要是⽤来让数据尽量均匀分布
//虚拟节点是真实节点的不同映射⽽已
//⽐如真实节点user1的hash 值为100，那么我们增加3个虚拟节点user1-1、user1-2、user1-3，分别计算出来的hash 值可能就为200，345，500；通过这种⽅式来将节点分布均匀
private static final int VIRTUAL_NODES = 3;
public ConsistentHashAlgorithm () {
}
public ConsistentHashAlgorithm (SortedMap <Long , String > virtualTableNodes , Collection <String > tableNodes ) {
if (Objects .isNull (virtualTableNodes )) {
virtualTableNodes = initNodesToHashLoop (tableNodes );
}
232
this.virtualNodes = virtualTableNodes;
}
public 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 = (i);
}else{
//第⼀个Key就是顺时针过去离node最近的那个结点
Long i = subMap.firstKey();
//返回对应的服务器
virtualNode = (i);
}
return virtualNode;
}
/**
* 使⽤FNV1_32_HASH算法计算key的Hash值
*
* @param key
* @return
*/
public long getHash(String key){
final int p =16777619;
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 = RuntimeContext().getRule();
Collection<TableRule> tableRules = TableRules();
ConsistentHashAlgorithm consistentHashAlgorithm =new ConsistentHashAlgorithm();
for(TableRule tableRule : tableRules){
String logicTable = LogicTable();
tableVirtualNodes.put(logicTable,
consistentHashAlgorithm.initNodesToHashLoop(
.stream()
.map(DataNode::getTableName)
.List()))
);
}
}catch(Exception e){
<("分表节点初始化失败 {}", e);
}
}
}
3.创建分表算法
ConsistentShardingAlgorithm
public class ConsistentShardingAlgorithm
implements PreciseShardingAlgorithm<Long>, RangeShardingAlgorithm<Long>{
/**
* 精确分⽚
* ⼀致性hash算法
*/
@Override
public String doSharding(Collection<String> availableTargetNames, PreciseShardingValue<Long> shardingValue){
//获取已经初始化的分表节点
InitTableNodesToHashLoop initTableNodesToHashLoop =
if(CollectionUtils.isEmpty(availableTargetNames)){
LogicTableName();
}
//这⾥主要为了兼容当联表查询时，如果两个表⾮关联表则
//当对副表分表时shardingValue这⾥传递进来的依然是主表的名称，
//但availableTargetNames中确是副表名称，所有这⾥要从availableTargetNames中匹配真实表
ArrayList<String> availableTargetNameList =new ArrayList<>(availableTargetNames);
String logicTableName = (0).replaceAll("[^(a-zA-Z_)]","");
SortedMap<Long, String> tableHashNode =
ConsistentHashAlgorithm consistentHashAlgorithm =new ConsistentHashAlgorithm(tableHashNode,
availableTargetNames);
TableNode(String.Value()));
}
/**
* 范围查询规则
* 可以根据实际场景进⾏修改
* 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: sharding.infrastruc.shardingAlgorithm.ConsistentShardingAlgorithm
总结
以上即是⼀致性hash算法在分表分库中的实际应⽤；虽然⼀致性hash算法能在节点伸缩的时候尽量减少数据的迁移，但是当虚拟节点数量很多时依然会造成不少数据迁移，所以前期进⾏规划时⼀定要考虑虚拟节点的倍数设置。
Demo地址：
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论