第 5 周作业:一致性 Hash 算法

发布于: 2020 年 07 月 07 日
  1. 简单hash负载匀衡算法

1.1 算法原理:简单Hash负载均衡算法时最先出现。主要是对客户端请求Key散列值对服务段机器数取模,模树对应服务器数量,取模结果就是接收该请求的服务器机器。

1.2 缺点。服务器数量发生变化时,按照上面所述的负载匀衡计算方法,对应缓存的key会失效,缓存数据需要重新计算。

  1. 简单一致性HASH算法。

2.1 算法原理:构造一个Hash环,这个Hash环,最大是2的32次方−1,因为hashCode是int型。服务端机器散列分部到HASH环上,客户端请求也散列到HASH环上,按照顺时针或逆时针原则,找到对应的服务器。

2.2 问题点。

  • 服务端机器散列到Hash环上,可能会有分布不均的问题,导致业务请求不能均衡地负载。

  • 如果集群中有一台机器宕机,会导致该机器上的请求分配到临近的下一个机器上,那么该机器有可能导致负载过高而引起系统雪崩。

  • 如果集群中增加一台机器,并不能够均衡原有所有机器的服务压力,只会分担临近机器的压力,所以不能做到新增服务想要达到的目的。

  1. 一致性Hash算法。

一致性Hash算法是在简单一致性Hash算法的基础上,通过引入虚拟节点 的方法,将服务机器更加散列到Hash环上,这种做法并不能够完全均衡地散列服务器,只能够做到相对的均衡。另外一致性Hash算法并不是能够完全解决系统雪崩的问题,而且虚拟节点的数量也不宜过多,否则也会影响到服务的性能。

public interface Cache {
String get(String key);
void set(String key, String value);
}
public class CacheImpl implements Cache{
private ConsistentHashRing ring = new ConsistentHashRing();
public CacheImpl(List<String>servers, int virtualNumPerNode) {
ring.addServers(servers, virtualNumPerNode);
}
@Override
public String get(String key) {
Cache serverKey = ring.getServer(key);
return serverKey.get(key);
}
@Override
public void set(String key, String val) {
Cache serverKey = ring.getServer(key);
serverKey.set(key, val);
}
@Override
public String toString() {
return ring.toString();
}
}
public class CacheServer implements Cache {
//MOCK缓存,存储KV
private Map<String, String> caches = new HashMap<>();
private String serverName;
public CacheServer(String serverName){
this.serverName = serverName;
}
public String getServerName(){
return this.serverName;
}
public Map<String, String> getCaches(){
return caches;
}
@Override
public String get(String key) {
return caches.get(key);
}
@Override
public void set(String key, String value) {
caches.put(key, value);
}
}
public class ConsistentHashRing {
TreeMap<Integer, Cache> map = new TreeMap<>();
List<Cache> servers = new ArrayList<>();
/**
* 往环中加入服务器
*/
public void addServers(List<String> servers, int virtualNum){
if(CollectionUtils.isNotEmpty(servers)){
for(String server : servers){
//先放置服务器
Cache cacheServer = new CacheServer(server);
map.put(getHashCode(server), cacheServer);
//加入虚拟节点
for(int i=0; i<virtualNum; i++){
map.put(getHashCode(server +"?NODE"+i), cacheServer);
}
this.servers.add(cacheServer);
}
}
}
public int getHashCode(String key) {
final int p = 16777619;
int ret = (int) 2166136261L;
for (int i = 0; i < key.length(); i++) {
ret = (ret ^ key.charAt(i)) * p;
}
ret += ret << 13;
ret ^= ret >> 7;
ret += ret << 3;
ret ^= ret >> 17;
ret += ret << 5;
return ret < 0 ? -ret : ret;
}
/**
* 根据缓存key,查找环上的对应服务器
*
*/
public Cache getServer(String cacheKey) {
if(MapUtils.isEmpty(map) || StringUtils.isBlank(cacheKey)){
System.out.println("paras error");
return null;
}
int hash = getHashCode(cacheKey);
Map.Entry<Integer, Cache> server = map.ceilingEntry(hash);
if (server == null)
return map.firstEntry().getValue();
return server.getValue();
}
@Override
public String toString() {
int totalNum = 0;
for (Cache cache : servers) {
CacheServer cacheServer = (CacheServer) cache;
totalNum += cacheServer.getCaches().size();
}
int avg = totalNum / servers.size();
StringBuilder sb = new StringBuilder();
sb.append("总缓存个数:").append(totalNum)
.append(" 服务器台数:").append(servers.size())
.append(" 每服务器虚拟节点数:").append(map.size()/servers.size() - 1)
.append(" 平均值:").append(avg)
.append("\r\n");
// 标准差公式: (每个样本 - 平均值)的平方 / (服务器数 - 1),结果再取平方根
long diff = 0;
for (Cache cache : servers) {
CacheServer cacheServer = (CacheServer) cache;
int size = cacheServer.getCaches().size();
sb.append("Server-Name:")
.append(cacheServer.getServerName())
.append(" Cache-num: ")
.append(size)
.append("\r\n");
long tmp = size - avg;
diff += (tmp * tmp);
}
diff /= (servers.size() - 1);
sb.append("标准差为: ").append(Math.sqrt(diff)).append("\r\n");
return sb.toString();
}
}
public class Main {
static List<String> servers = Arrays.asList(
"10.0.0.1",
"10.0.0.2",
"10.0.0.3",
"10.0.0.4",
"10.0.0.5",
"10.0.0.6",
"10.0.0.7",
"10.0.0.8",
"10.0.0.9",
"10.0.0.10");
static int maxCacheNum = 1000000;
public static void main(String[] args) {
testCache(0);
testCache(1);
testCache(10);
testCache(100);
testCache(150);
testCache(180);
testCache(200);
testCache(250);
testCache(300);
testCache(400);
testCache(600);
}
static void testCache(int virtualNum) {
Cache cache = new CacheImpl(servers, virtualNum);
fillCache(cache, maxCacheNum);
System.out.println(cache);
}
static void fillCache(Cache cache, int cacheNum) {
for (int i = 0; i < cacheNum; i++) {
String key = "key" + i;
String val = "val" + key;
cache.set(key, val);
}
}
}

总缓存个数:1000000 服务器台数:10 每服务器虚拟节点数:0 平均值:100000
Server-Name:10.0.0.1 Cache-num: 126281
Server-Name:10.0.0.2 Cache-num: 6669
Server-Name:10.0.0.3 Cache-num: 154480
Server-Name:10.0.0.4 Cache-num: 138847
Server-Name:10.0.0.5 Cache-num: 11541
Server-Name:10.0.0.6 Cache-num: 357376
Server-Name:10.0.0.7 Cache-num: 91493
Server-Name:10.0.0.8 Cache-num: 13296
Server-Name:10.0.0.9 Cache-num: 82488
Server-Name:10.0.0.10 Cache-num: 17529
标准差为: 106793.68220545632
总缓存个数:1000000 服务器台数:10 每服务器虚拟节点数:1 平均值:100000
Server-Name:10.0.0.1 Cache-num: 138804
Server-Name:10.0.0.2 Cache-num: 22060
Server-Name:10.0.0.3 Cache-num: 174995
Server-Name:10.0.0.4 Cache-num: 113543
Server-Name:10.0.0.5 Cache-num: 46784
Server-Name:10.0.0.6 Cache-num: 198967
Server-Name:10.0.0.7 Cache-num: 116060
Server-Name:10.0.0.8 Cache-num: 19315
Server-Name:10.0.0.9 Cache-num: 82488
Server-Name:10.0.0.10 Cache-num: 86984
标准差为: 60789.75229428065
总缓存个数:1000000 服务器台数:10 每服务器虚拟节点数:10 平均值:100000
Server-Name:10.0.0.1 Cache-num: 104938
Server-Name:10.0.0.2 Cache-num: 79140
Server-Name:10.0.0.3 Cache-num: 72727
Server-Name:10.0.0.4 Cache-num: 112781
Server-Name:10.0.0.5 Cache-num: 140551
Server-Name:10.0.0.6 Cache-num: 101554
Server-Name:10.0.0.7 Cache-num: 79670
Server-Name:10.0.0.8 Cache-num: 85200
Server-Name:10.0.0.9 Cache-num: 130580
Server-Name:10.0.0.10 Cache-num: 92859
标准差为: 22686.196552088673
总缓存个数:1000000 服务器台数:10 每服务器虚拟节点数:100 平均值:100000
Server-Name:10.0.0.1 Cache-num: 103966
Server-Name:10.0.0.2 Cache-num: 98325
Server-Name:10.0.0.3 Cache-num: 107182
Server-Name:10.0.0.4 Cache-num: 90553
Server-Name:10.0.0.5 Cache-num: 104485
Server-Name:10.0.0.6 Cache-num: 103057
Server-Name:10.0.0.7 Cache-num: 103351
Server-Name:10.0.0.8 Cache-num: 87699
Server-Name:10.0.0.9 Cache-num: 95855
Server-Name:10.0.0.10 Cache-num: 105527
标准差为: 6659.118560290093
总缓存个数:1000000 服务器台数:10 每服务器虚拟节点数:150 平均值:100000
Server-Name:10.0.0.1 Cache-num: 97799
Server-Name:10.0.0.2 Cache-num: 103811
Server-Name:10.0.0.3 Cache-num: 111376
Server-Name:10.0.0.4 Cache-num: 97195
Server-Name:10.0.0.5 Cache-num: 95083
Server-Name:10.0.0.6 Cache-num: 99680
Server-Name:10.0.0.7 Cache-num: 98785
Server-Name:10.0.0.8 Cache-num: 91618
Server-Name:10.0.0.9 Cache-num: 103900
Server-Name:10.0.0.10 Cache-num: 100753
标准差为: 5461.379221405523
总缓存个数:1000000 服务器台数:10 每服务器虚拟节点数:180 平均值:100000
Server-Name:10.0.0.1 Cache-num: 95347
Server-Name:10.0.0.2 Cache-num: 101224
Server-Name:10.0.0.3 Cache-num: 104367
Server-Name:10.0.0.4 Cache-num: 99721
Server-Name:10.0.0.5 Cache-num: 103001
Server-Name:10.0.0.6 Cache-num: 95309
Server-Name:10.0.0.7 Cache-num: 106419
Server-Name:10.0.0.8 Cache-num: 96007
Server-Name:10.0.0.9 Cache-num: 100253
Server-Name:10.0.0.10 Cache-num: 98352
标准差为: 3847.598341823117
总缓存个数:1000000 服务器台数:10 每服务器虚拟节点数:200 平均值:100000
Server-Name:10.0.0.1 Cache-num: 94915
Server-Name:10.0.0.2 Cache-num: 104407
Server-Name:10.0.0.3 Cache-num: 103055
Server-Name:10.0.0.4 Cache-num: 101686
Server-Name:10.0.0.5 Cache-num: 98822
Server-Name:10.0.0.6 Cache-num: 94714
Server-Name:10.0.0.7 Cache-num: 103939
Server-Name:10.0.0.8 Cache-num: 102839
Server-Name:10.0.0.9 Cache-num: 98001
Server-Name:10.0.0.10 Cache-num: 97622
标准差为: 3651.643465619282
总缓存个数:1000000 服务器台数:10 每服务器虚拟节点数:250 平均值:100000
Server-Name:10.0.0.1 Cache-num: 92358
Server-Name:10.0.0.2 Cache-num: 105479
Server-Name:10.0.0.3 Cache-num: 108135
Server-Name:10.0.0.4 Cache-num: 96552
Server-Name:10.0.0.5 Cache-num: 99564
Server-Name:10.0.0.6 Cache-num: 93253
Server-Name:10.0.0.7 Cache-num: 107010
Server-Name:10.0.0.8 Cache-num: 100038
Server-Name:10.0.0.9 Cache-num: 97353
Server-Name:10.0.0.10 Cache-num: 100258
标准差为: 5461.108495534583
总缓存个数:1000000 服务器台数:10 每服务器虚拟节点数:300 平均值:100000
Server-Name:10.0.0.1 Cache-num: 98877
Server-Name:10.0.0.2 Cache-num: 104614
Server-Name:10.0.0.3 Cache-num: 109080
Server-Name:10.0.0.4 Cache-num: 97134
Server-Name:10.0.0.5 Cache-num: 92452
Server-Name:10.0.0.6 Cache-num: 96634
Server-Name:10.0.0.7 Cache-num: 104742
Server-Name:10.0.0.8 Cache-num: 99452
Server-Name:10.0.0.9 Cache-num: 95405
Server-Name:10.0.0.10 Cache-num: 101610
标准差为: 5033.286202869851
总缓存个数:1000000 服务器台数:10 每服务器虚拟节点数:400 平均值:100000
Server-Name:10.0.0.1 Cache-num: 100840
Server-Name:10.0.0.2 Cache-num: 102895
Server-Name:10.0.0.3 Cache-num: 104440
Server-Name:10.0.0.4 Cache-num: 104144
Server-Name:10.0.0.5 Cache-num: 95783
Server-Name:10.0.0.6 Cache-num: 90076
Server-Name:10.0.0.7 Cache-num: 104480
Server-Name:10.0.0.8 Cache-num: 101943
Server-Name:10.0.0.9 Cache-num: 96030
Server-Name:10.0.0.10 Cache-num: 99369
标准差为: 4740.446919858929
总缓存个数:1000000 服务器台数:10 每服务器虚拟节点数:600 平均值:100000
Server-Name:10.0.0.1 Cache-num: 103417
Server-Name:10.0.0.2 Cache-num: 102469
Server-Name:10.0.0.3 Cache-num: 100347
Server-Name:10.0.0.4 Cache-num: 95392
Server-Name:10.0.0.5 Cache-num: 101912
Server-Name:10.0.0.6 Cache-num: 90973
Server-Name:10.0.0.7 Cache-num: 104451
Server-Name:10.0.0.8 Cache-num: 101727
Server-Name:10.0.0.9 Cache-num: 100812
Server-Name:10.0.0.10 Cache-num: 98500
标准差为: 4082.0972550883694

实验数据:

  1. 虚拟节点位于1-150时 标准方差逐步缩小。

  2. 虚拟节点个数 180时 标准方差 3847

虚拟节点个数 200时 标准方差 3651

  1. 虚拟节点个数250-600时 标准方差 又逐步变大。

结论:

虚拟节点 180-200 数量较好。

参考:

https://xie.infoq.cn/article/8651e7b5ef05177005b474dfc

https://xie.infoq.cn/article/0c660a8f26689cb4ac94e8b17

用户头像

姜 某某

关注

还未添加个人签名 2019.05.09 加入

还未添加个人简介

评论

发布
暂无评论
第 5 周作业:一致性 Hash 算法