catalogue
background
With the advent of the era of large database, many distributed applications now use clusters. Each cluster is inseparable from load balancing, that is, the load of each machine will be reduced by dividing the traffic through the load balancing algorithm.
1, Polling algorithm
Polling is to access all requests to the cluster servers in turn. Each service receives requests in turn. Regardless of the performance of each server, it can receive requests fairly.
Implementation principle
AtomicLong is used to realize atomicity, and volatile ensures visibility. As long as a thread comes in and changes the index value, other threads will find it in time. In short, threads will not reuse an index.
The getAndIncrement() method ensures that the id is continuously incremented, so it can poll the list.
static class LoadBalance {
private static volatile AtomicLong index = new AtomicLong(0);
private static Object getOne(List<? extends Object> list) {
if (index.get() >=Integer.MAX_VALUE) {
// When the integer maximum is reached, return to 0
index.set(0);
}
return list.get((int) index.getAndIncrement() % list.size());
}
}2, Random algorithm
Random algorithm is also a commonly used load balancing algorithm. It can ensure that in the case of large amount of data, the machines in the cluster can receive about the same amount of requests, that is, the probability of requests entering each machine in the cluster is equal.
Implementation principle
Use the nextInt() method to obtain a random value less than the specified integer, such as nextInt(5), then the probability of obtaining any value between 0-4 is equal, so the probability of obtaining each element in the list is also equal.
static class LoadBalance {
private static Random random = new Random(System.currentTimeMillis());
private static Object getOneByRandom(List<? extends Object> list) {
return list.get(random.nextInt(list.size()));
}
}3, Hash algorithm
Hash algorithm is a hash algorithm, which conforms to the principle of uniform distribution. Each element finds a position in the hash table through the calculated hash value, which can be evenly scattered in the hash table under a large amount of data, that is, the hash algorithm can make the requests evenly distributed to each machine in the cluster.
Implementation principle
In actual development, each request is unique and can be regarded as a unique id. the hashcode is obtained according to the id and modeled with the server list. The modulus obtained is the selected machine.
Understand each thread as a request, and then use indexAtomic to identify uniqueness.
private static AtomicLong indexAtomic = new AtomicLong(0);
@Test
public void loadBalanceHash() {
// Hash
for (int i = 0; i < SERIES_SIZE; i++) {
if (indexAtomic.get() >= Integer.MAX_VALUE) {
indexAtomic.set(0);
}
threadPool.submit(() -> {
String serverName = (String) LoadBalance.getOneByHash(serverLists, indexAtomic.getAndIncrement());
result.add(serverName);
});
}
System.out.println("================Hash algorithm================");
print(result);
}Then calculate the hashCode() of the obtained value. When the calculated value is less than 0, take the absolute value.
private static Object getOneByHash(List<? extends Object> list, Object arg) {
int value = arg.hashCode();
if (value < 0) {
value = Math.abs(value);
}
return list.get(value % list.size());
}4, Weight algorithm
The weight means the score, which can be understood as the score obtained by each machine. If the score of A machine is large, it is equivalent to receiving more requests. The nginx server can distribute the traffic to different machines and set the weight ratio. For example, it can be distributed to machines A and B, with A proportion of 2:1, Then the average number of requests received by server A is twice that received by server B.
The weight algorithm is a bit like those who can do more. It is applicable to the case that the configurations in the cluster are not equal. The servers with high configuration share more and the servers with low configuration share less.
Implementation principle
Compare the weights to the intervals with different component values. Each interval corresponds to a server. A value in the interval is randomly generated before each access. In which interval the value is in, then which server is returned.
Convert to interval:
public void loadBalanceWeight() {
// Weight: set the weight of three machines as 3:1:1
// 4. Weight algorithm: assign weight to each machine. Assuming that the assigned weight is 3 for the first machine and 1 for all other machines, then the weight is [3,4,5,6]
int[] weight = new int[serverLists.size() + 1];
weight[0] = 0;
int length;
for (int i = 1; i < weight.length; i++) {
if (i == 1) {
// Assign a weight of 3 to the first machine
weight[i] = 3;
} else {
// 1 for other machines
weight[i] = weight[i - 1] + 1;
}
}
length = weight[weight.length - 1];
final int temp = length;
for (int i = 0; i < SERIES_SIZE; i++) {
threadPool.submit(() -> {
String serverName = (String) LoadBalance.getOneByWeight(serverLists, weight, temp);
result.add(serverName);
});
}
System.out.println("================Weight algorithm================");
print(result);
}Check which interval the random value is in. If it is in [0,3), it will return to server A, if it is in [3,4), it will return to server B, and if it is between [4,5), it will return to server C.
private static Object getOneByWeight(List<? extends Object> list, int[] weight, Integer length) {
int target = random.nextInt(length);
// The calculated target value corresponds to the first position in the list.
for (int i = 0; i < weight.length; i++) {
int start = weight[i], end = weight[i + 1];
if (target >= start && target < end) {
return list.get(i);
}
}
return list.get(0);
}5, Using unit tests
package com.example.producer;
import com.example.producer.util.ThreadPoolUtil;
import org.junit.After;
import org.junit.Before;
import org.junit.Test;
import org.mockito.junit.MockitoJUnitRunner;
import java.io.*;
import java.util.*;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
public class LoadBalanceTest {
private static AtomicLong indexAtomic = new AtomicLong(0);
private static final int SERIES_SIZE = 10000;
private static final String path = "D:\\idea project\\rocketmq-project\\producer\\src\\test\\java\\com\\example\\producer\\indexFile";
private static ReadWriteLock lock = new ReentrantReadWriteLock();
List<String> serverLists = new ArrayList<>();
ExecutorService threadPool = null;
List<String> result = null;
@Before
public void initList() {
threadPool = ThreadPoolUtil.getThreadPool();
serverLists.add("serverA");
serverLists.add("serverB");
serverLists.add("serverC");
List<String> init = new ArrayList<>();
result = Collections.synchronizedList(init);
}
@After
public void clearList() {
serverLists.clear();
result.clear();
threadPool.shutdown();
}
@Test
public void loadBalancePolling() {
// polling
for (int i = 0; i < SERIES_SIZE; i++) {
threadPool.submit(() -> {
String serverName = (String) LoadBalance.getOne(serverLists);
result.add(serverName);
});
}
System.out.println("================polling algorithm ================");
print(result);
}
@Test
public void loadBalanceRandom() {
// random
for (int i = 0; i < SERIES_SIZE; i++) {
threadPool.submit(() -> {
String serverName = (String) LoadBalance.getOneByRandom(serverLists);
result.add(serverName);
});
}
System.out.println("================Random algorithm================");
print(result);
}
@Test
public void loadBalanceHash() {
// Hash
for (int i = 0; i < SERIES_SIZE; i++) {
threadPool.submit(() -> {
String serverName = (String) LoadBalance.getOneByHash(serverLists, indexAtomic.getAndIncrement());
result.add(serverName);
});
}
System.out.println("================Hash algorithm================");
print(result);
}
@Test
public void loadBalanceWeight() {
// weight
// 4. Weight algorithm: assign weight to each machine. Assuming that the assigned weight is 3 for the first machine and 1 for all other machines, then the weight is [3,4,5,6]
int[] weight = new int[serverLists.size() + 1];
weight[0] = 0;
int length;
for (int i = 1; i < weight.length; i++) {
if (i == 1) {
// Assign a weight of 3 to the first machine
weight[i] = 3;
} else {
// 1 for other machines
weight[i] = weight[i - 1] + 1;
}
}
length = weight[weight.length - 1];
final int temp = length;
for (int i = 0; i < SERIES_SIZE; i++) {
threadPool.submit(() -> {
String serverName = (String) LoadBalance.getOneByWeight(serverLists, weight, temp);
result.add(serverName);
});
}
System.out.println("================Weight algorithm================");
print(result);
}
private static void print(List<String> result) {
int countA = 0, countB = 0, countC = 0;
try {
lock.readLock().lock();
if (!result.isEmpty()) {
for (String s : result) {
if ("serverA".equalsIgnoreCase(s)) {
countA++;
} else if ("serverB".equalsIgnoreCase(s)) {
countB++;
} else {
countC++;
}
}
System.out.println("countA=" + countA + ",countB=" + countB + ",countC=" + countC);
}
} finally {
lock.readLock().unlock();
}
}
static class LoadBalance {
private static volatile AtomicInteger index = new AtomicInteger(0);
private static Random random = new Random(System.currentTimeMillis());
private static Object getOne(List<? extends Object> list) {
if (index.get() == Integer.MAX_VALUE) {
index.set(0);
}
return list.get(index.getAndIncrement() % list.size());
}
private static Object getOneByRandom(List<? extends Object> list) {
return list.get(random.nextInt(list.size()));
}
private static Object getOneByHash(List<? extends Object> list, Object arg) {
int value = arg.hashCode();
if (value < 0) {
value = Math.abs(value);
}
return list.get(value % list.size());
}
private static Object getOneByWeight(List<? extends Object> list, int[] weight, Integer length) {
int target = random.nextInt(length);
// The calculated target value corresponds to the first position in the list.
for (int i = 0; i < weight.length; i++) {
int start = weight[i], end = weight[i + 1];
if (target >= start && target < end) {
return list.get(i);
}
}
return list.get(0);
}
}
}
polling
random
Hash
weight
