Skip to content

Commit d153ca7

Browse files
dunwudunwu
committed
update codes and docs
1 parent 9710d6f commit d153ca7

15 files changed

Lines changed: 594 additions & 307 deletions

‎assets/Java性能调优.xmind‎

478 KB
Binary file not shown.

‎codes/java-distributed/java-load-balance/pom.xml‎

Lines changed: 12 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,8 @@
1-
<?xml version="1.0"?>
2-
<project xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
3-
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"
4-
xmlns="http://maven.apache.org/POM/4.0.0">
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<project xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://maven.apache.org/POM/4.0.0"
3+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
54
<modelVersion>4.0.0</modelVersion>
65

7-
<parent>
8-
<groupId>io.github.dunwu</groupId>
9-
<artifactId>dunwu-parent</artifactId>
10-
<version>0.5.1</version>
11-
</parent>
12-
136
<groupId>io.github.dunwu.javatech</groupId>
147
<artifactId>java-distributed-load-balance</artifactId>
158
<version>1.0.0</version>
@@ -25,13 +18,19 @@
2518

2619
<dependencies>
2720
<dependency>
28-
<groupId>io.github.dunwu</groupId>
29-
<artifactId>dunwu-tool-core</artifactId>
30-
<version>0.5.7</version>
21+
<groupId>cn.hutool</groupId>
22+
<artifactId>hutool-all</artifactId>
23+
<version>5.4.1</version>
24+
</dependency>
25+
<dependency>
26+
<groupId>org.projectlombok</groupId>
27+
<artifactId>lombok</artifactId>
28+
<version>1.18.12</version>
3129
</dependency>
3230
<dependency>
3331
<groupId>junit</groupId>
3432
<artifactId>junit</artifactId>
33+
<version>4.13</version>
3534
<scope>test</scope>
3635
</dependency>
3736
</dependencies>

‎codes/java-distributed/java-load-balance/src/main/java/io/github/dunwu/javatech/BaseLoadBalance.java‎

Lines changed: 12 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -2,8 +2,6 @@
22

33
import cn.hutool.core.collection.CollectionUtil;
44

5-
import java.util.Collection;
6-
import java.util.LinkedList;
75
import java.util.List;
86

97
/**
@@ -12,37 +10,28 @@
1210
*/
1311
public abstract class BaseLoadBalance<N extends Node> implements LoadBalance<N> {
1412

15-
protected List<N> nodes = new LinkedList<>();
16-
17-
@Override
18-
public void buildNodes(final Collection<N> collection) {
19-
this.nodes = new LinkedList<>(collection);
20-
}
21-
22-
@Override
23-
public void addNode(N node) {
24-
this.nodes.add(node);
25-
}
26-
27-
@Override
28-
public void removeNode(N node) {
29-
this.nodes.remove(node);
30-
}
31-
3213
@Override
33-
public N select() {
14+
public N select(List<N> nodes, String ip) {
15+
// nodes 列表为空，返回 null
3416
if (CollectionUtil.isEmpty(nodes)) {
3517
return null;
3618
}
3719

38-
// 如果 nodes 列表中仅有一个 node，直接返回即可，无需进行负载均衡
20+
// 如果 nodes 列表中仅有一个 node，直接返回即可
3921
if (nodes.size() == 1) {
4022
return nodes.get(0);
4123
}
4224

43-
return doSelect();
25+
return doSelect(nodes, ip);
4426
}
4527

46-
protected abstract N doSelect();
28+
/**
29+
* 负载均衡算法抽象方法，各个算法需要自行实现
30+
*
31+
* @param nodes 节点列表
32+
* @param ip 请求方 IP
33+
* @return <N> 被选中的节点
34+
*/
35+
protected abstract N doSelect(List<N> nodes, String ip);
4736

4837
}

‎codes/java-distributed/java-load-balance/src/main/java/io/github/dunwu/javatech/ConsistentHashLoadBalance.java‎

Lines changed: 88 additions & 45 deletions
Original file line numberDiff line numberDiff line change
@@ -1,65 +1,108 @@
11
package io.github.dunwu.javatech;
22

3-
import io.github.dunwu.javatech.support.HashStrategy;
4-
import io.github.dunwu.javatech.support.MurmurHashStrategy;
3+
import java.nio.charset.StandardCharsets;
4+
import java.security.MessageDigest;
5+
import java.security.NoSuchAlgorithmException;
6+
import java.util.List;
7+
import java.util.Map;
8+
import java.util.TreeMap;
9+
import java.util.concurrent.ConcurrentHashMap;
10+
import java.util.concurrent.ConcurrentMap;
511

6-
import java.util.*;
12+
public class ConsistentHashLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
713

8-
public class ConsistentHashLoadBalance<V extends Node> implements LoadBalance<V> {
14+
private final ConcurrentMap<String, ConsistentHashSelector<?>> selectors = new ConcurrentHashMap<>();
915

10-
private HashStrategy hashStrategy = new MurmurHashStrategy();
11-
12-
private final static int VIRTUAL_NODE_SIZE = 1000;
16+
@SuppressWarnings("unchecked")
17+
@Override
18+
protected N doSelect(List<N> nodes, String ip) {
19+
// 获取 nodes 原始的 hashcode
20+
int identityHashCode = System.identityHashCode(nodes);
21+
ConsistentHashSelector<N> selector = (ConsistentHashSelector<N>) selectors.get(ip);
22+
if (selector == null || selector.identityHashCode != identityHashCode) {
23+
selectors.put(ip, new ConsistentHashSelector<>(nodes, identityHashCode, 1000));
24+
selector = (ConsistentHashSelector<N>) selectors.get(ip);
25+
}
26+
return selector.select(ip);
27+
}
1328

14-
private final static String VIRTUAL_NODE_SUFFIX = "&&";
29+
/**
30+
* @param <N>
31+
*/
32+
private static final class ConsistentHashSelector<N extends Node> {
1533

16-
private Set<V> nodes = new LinkedHashSet<>();
34+
/**
35+
* 使用 TreeMap 存储 Node 虚拟节点
36+
*/
37+
private final TreeMap<Long, N> virtualNodes;
1738

18-
private TreeMap<Integer, V> hashRing = new TreeMap<>();
39+
private final int identityHashCode;
1940

20-
@Override
21-
public void buildNodes(final Collection<V> collection) {
22-
this.nodes = new LinkedHashSet<>(collection);
23-
this.hashRing = buildConsistentHashRing(this.nodes);
24-
}
41+
ConsistentHashSelector(List<N> nodes, int identityHashCode, Integer replicaNum) {
42+
this.virtualNodes = new TreeMap<>();
43+
this.identityHashCode = identityHashCode;
44+
// 获取虚拟节点数，默认为 100
45+
if (replicaNum == null) {
46+
replicaNum = 100;
47+
}
48+
for (N node : nodes) {
49+
for (int i = 0; i < replicaNum / 4; i++) {
50+
// 对 url 进行 md5 运算，得到一个长度为16的字节数组
51+
byte[] digest = md5(node.getUrl());
52+
// 对 digest 部分字节进行 4 次 hash 运算，得到四个不同的 long 型正整数
53+
for (int j = 0; j < 4; j++) {
54+
// h = 0 时，取 digest 中下标为 0 ~ 3 的4个字节进行位运算
55+
// h = 1 时，取 digest 中下标为 4 ~ 7 的4个字节进行位运算
56+
// h = 2, h = 3 时过程同上
57+
long m = hash(digest, j);
58+
// 将 hash 到 node 的映射关系存储到 virtualNodes 中，
59+
// virtualNodes 需要提供高效的查询操作，因此选用 TreeMap 作为存储结构
60+
virtualNodes.put(m, node);
61+
}
62+
}
63+
}
64+
}
2565

26-
@Override
27-
public void addNode(V node) {
28-
this.nodes.add(node);
29-
this.hashRing = buildConsistentHashRing(this.nodes);
30-
}
66+
public N select(String key) {
67+
byte[] digest = md5(key);
68+
return selectForKey(hash(digest, 0));
69+
}
3170

32-
@Override
33-
public void removeNode(V node) {
34-
this.nodes.removeIf(v -> v.equals(node));
35-
this.hashRing = buildConsistentHashRing(this.nodes);
36-
}
71+
private N selectForKey(long hash) {
72+
Map.Entry<Long, N> entry = virtualNodes.ceilingEntry(hash);
73+
if (entry == null) {
74+
entry = virtualNodes.firstEntry();
75+
}
76+
return entry.getValue();
77+
}
3778

38-
@Override
39-
public V select() {
40-
return next(UUID.randomUUID().toString());
4179
}
4280

43-
public V next(String key) {
44-
int hashCode = hashStrategy.hashCode(key);
45-
// 向右找到第一个 key
46-
Map.Entry<Integer, V> entry = hashRing.ceilingEntry(hashCode);
47-
if (entry == null) {
48-
// 想象成一个环，超过尾部则取第一个 key
49-
entry = hashRing.firstEntry();
50-
}
51-
return entry.getValue();
81+
/**
82+
* 计算 hash 值
83+
*/
84+
public static long hash(byte[] digest, int number) {
85+
return (((long) (digest[3 + number * 4] & 0xFF) << 24)
86+
| ((long) (digest[2 + number * 4] & 0xFF) << 16)
87+
| ((long) (digest[1 + number * 4] & 0xFF) << 8)
88+
| (digest[number * 4] & 0xFF))
89+
& 0xFFFFFFFFL;
5290
}
5391

54-
private TreeMap<Integer, V> buildConsistentHashRing(Set<V> nodes) {
55-
TreeMap<Integer, V> hashRing = new TreeMap<>();
56-
for (V node : nodes) {
57-
for (int i = 0; i < VIRTUAL_NODE_SIZE; i++) {
58-
// 新增虚拟节点的方式如果有影响，也可以抽象出一个由物理节点扩展虚拟节点的类
59-
hashRing.put(hashStrategy.hashCode(node + VIRTUAL_NODE_SUFFIX + i), node);
60-
}
92+
/**
93+
* 计算 MD5 值
94+
*/
95+
public static byte[] md5(String value) {
96+
MessageDigest md5;
97+
try {
98+
md5 = MessageDigest.getInstance("MD5");
99+
} catch (NoSuchAlgorithmException e) {
100+
throw new IllegalStateException(e.getMessage(), e);
61101
}
62-
return hashRing;
102+
md5.reset();
103+
byte[] bytes = value.getBytes(StandardCharsets.UTF_8);
104+
md5.update(bytes);
105+
return md5.digest();
63106
}
64107

65108
}

‎codes/java-distributed/java-load-balance/src/main/java/io/github/dunwu/javatech/IpHashLoadBalance.java‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package io.github.dunwu.javatech;
2+
3+
import cn.hutool.core.util.HashUtil;
4+
import cn.hutool.core.util.StrUtil;
5+
6+
import java.util.List;
7+
8+
/**
9+
* @author peng.zhang
10+
* @date 2021/1/19
11+
*/
12+
public class IpHashLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
13+
14+
@Override
15+
protected N doSelect(List<N> nodes, String ip) {
16+
if (StrUtil.isBlank(ip)) {
17+
ip = "127.0.0.1";
18+
}
19+
20+
int length = nodes.size();
21+
int index = hash(ip) % length;
22+
return nodes.get(index);
23+
}
24+
25+
public int hash(String text) {
26+
return HashUtil.fnvHash(text);
27+
}
28+
29+
}

‎codes/java-distributed/java-load-balance/src/main/java/io/github/dunwu/javatech/LeastActiveLoadBalance.java‎

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
package io.github.dunwu.javatech;
2+
3+
import java.util.List;
4+
import java.util.Random;
5+
6+
/**
7+
* @author peng.zhang
8+
* @date 2021/1/18
9+
*/
10+
public class LeastActiveLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
11+
12+
private final Random random = new Random();
13+
14+
@Override
15+
protected N doSelect(List<N> nodes, String ip) {
16+
int length = nodes.size();
17+
// 最小的活跃数
18+
int leastActive = -1;
19+
// 具有相同“最小活跃数”的服务者提供者（以下用 Node 代称）数量
20+
int leastCount = 0;
21+
// leastIndexs 用于记录具有相同“最小活跃数”的 Node 在 nodes 列表中的下标信息
22+
int[] leastIndexs = new int[length];
23+
int totalWeight = 0;
24+
// 第一个最小活跃数的 Node 权重值，用于与其他具有相同最小活跃数的 Node 的权重进行对比，
25+
// 以检测是否“所有具有相同最小活跃数的 Node 的权重”均相等
26+
int firstWeight = 0;
27+
boolean sameWeight = true;
28+
29+
// 遍历 nodes 列表
30+
for (int i = 0; i < length; i++) {
31+
N node = nodes.get(i);
32+
// 发现更小的活跃数，重新开始
33+
if (leastActive == -1 || node.getActive() < leastActive) {
34+
// 使用当前活跃数更新最小活跃数 leastActive
35+
leastActive = node.getActive();
36+
// 更新 leastCount 为 1
37+
leastCount = 1;
38+
// 记录当前下标值到 leastIndexs 中
39+
leastIndexs[0] = i;
40+
totalWeight = node.getWeight();
41+
firstWeight = node.getWeight();
42+
sameWeight = true;
43+
44+
// 当前 Node 的活跃数 node.getActive() 与最小活跃数 leastActive 相同
45+
} else if (node.getActive() == leastActive) {
46+
// 在 leastIndexs 中记录下当前 Node 在 nodes 集合中的下标
47+
leastIndexs[leastCount++] = i;
48+
// 累加权重
49+
totalWeight += node.getWeight();
50+
// 检测当前 Node 的权重与 firstWeight 是否相等，
51+
// 不相等则将 sameWeight 置为 false
52+
if (sameWeight && i > 0
53+
&& node.getWeight() != firstWeight) {
54+
sameWeight = false;
55+
}
56+
}
57+
}
58+
59+
// 当只有一个 Node 具有最小活跃数，此时直接返回该 Node 即可
60+
if (leastCount == 1) {
61+
return nodes.get(leastIndexs[0]);
62+
}
63+
64+
// 有多个 Node 具有相同的最小活跃数，但它们之间的权重不同
65+
if (!sameWeight && totalWeight > 0) {
66+
// 随机生成一个 [0, totalWeight) 之间的数字
67+
int offsetWeight = random.nextInt(totalWeight);
68+
// 循环让随机数减去具有最小活跃数的 Node 的权重值，
69+
// 当 offset 小于等于0时，返回相应的 Node
70+
for (int i = 0; i < leastCount; i++) {
71+
int leastIndex = leastIndexs[i];
72+
// 获取权重值，并让随机数减去权重值
73+
offsetWeight -= nodes.get(leastIndex).getWeight();
74+
if (offsetWeight <= 0) {
75+
return nodes.get(leastIndex);
76+
}
77+
}
78+
}
79+
// 如果权重相同或权重为0时，随机返回一个 Node
80+
return nodes.get(leastIndexs[random.nextInt(leastCount)]);
81+
}
82+
83+
}

‎codes/java-distributed/java-load-balance/src/main/java/io/github/dunwu/javatech/LoadBalance.java‎

Lines changed: 2 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
package io.github.dunwu.javatech;
22

3-
import java.util.Collection;
3+
import java.util.List;
44

55
/**
66
* 负载均衡策略接口
@@ -10,12 +10,6 @@
1010
*/
1111
public interface LoadBalance<N extends Node> {
1212

13-
void buildNodes(Collection<N> collection);
14-
15-
void addNode(N node);
16-
17-
void removeNode(N node);
18-
19-
N select();
13+
N select(List<N> nodes, String ip);
2014

2115
}

0 commit comments

Comments
 (0)