本文總結了負載均衡常見的4中算法，我們可以發現nginx?或者spring cloud?中的ribbon都使用到了這樣的算法思想，我們可以根據自己的業務場景選擇合適算法。
?前言
一般來說，我們在設計系統的時候，為了系統的高擴展性，會盡可能的創建無狀態的系統，這樣我們就可以采用集群的方式部署，最終很方便的根據需要動態增減服務器數量。但是，要使系統具有更好的可擴展性，除了無狀態設計之外，還要考慮采用什么負載均衡算法，本文就帶領大家認識以下常見的4種負載均衡算法。
什么是負載均衡
負載均衡是指多臺服務器以對稱的方式組成一個服務器集群。每臺服務器的地位相當（但不同的服務器可能性能不同），可以獨立提供服務，無需其他服務器的輔助。為了保證系統的可擴展性，需要有一種算法能夠將系統負載平均分配給集群中的每臺服務器。這種算法稱為負載均衡算法。負責執行負載均衡算法并平均分配請求的服務器稱為負載均衡器。
隨機算法
隨機算法非常簡單，該算法的核心是通過隨機函數隨機獲取一個服務器進行訪問。假設我們現在有四臺服務器，192.168.1.1~ 192.168.1.4, 該算法用java實現大致如下：
public class RandomTest {
private static final List<String> servers = Arrays.asList("192.168.1.1", "192.168.1.2", "192.168.1.3", "192.168.1.4");
public static String getServer() {
Random random = new Random();
int index = random.nextInt(servers.size());
return servers.get(index);
}
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
String server = getServer();
System.out.println("select server: "+server);
}
}
}當樣本較小時，算法可能分布不均勻，但根據概率論，樣本越大，負載會越均勻，而負載均衡算法本來就是為應對高并發場景而設計的。該算法的另一個缺點是所有機器都有相同的訪問概率, 如果服務器性能不同，負載將不平衡。
輪詢算法
Round-Robin輪詢算法是另一種經典的負載均衡算法。請求以循環的方式分發到集群中的所有服務器。同理，對于上述四臺服務器，假設客戶端向集群發送10個請求，則請求分布將如下圖所示：
在十個請求中，第一、第五和第九個請求將分配給192.168.1.1?，第二、第六和第十個請求將分配給192.168.1.2?，依此類推。我們可以看到round-robin算法可以在集群中均勻的分配請求。但是，該算法具有與隨機算法相同的缺點，如果服務器性能不同，負載將不平衡，因此需要加權輪詢算法。
加權輪詢算法
Weighted Round-Robin?加權輪詢算法是在round-robin算法的基礎上根據服務器的性能分配權重。服務器能支持的請求越多，權重就越高，分配的請求也就越多。對于同樣的10個請求，使用加權輪詢算法的請求分布會如下圖所示：
可以看到192.168.1.4權重最大，分配的請求數最多。看一下使用Java簡單實現的以下加權循環算法。
public class RoundRobinTest {
public class Node{
private String ip;
private Integer weight;
private Integer currentWeight;
public Node(String ip,Integer weight) {
this.ip = ip;
this.weight = weight;
this.currentWeight = weight;
}
public String getIp() {
return ip;
}
public void setIp(String ip) {
this.ip = ip;
}
public Integer getWeight() {
return weight;
}
public void setWeight(Integer weight) {
this.weight = weight;
}
public Integer getCurrentWeight() {
return currentWeight;
}
public void setCurrentWeight(Integer currentWeight) {
this.currentWeight = currentWeight;
}
}
List<Node> servers = Arrays.asList(
new Node("192.168.1.1",1),
new Node("192.168.1.2",2),
new Node("192.168.1.3",3),
new Node("192.168.1.4",4));
private Integer totalWeight;
public RoundRobinTest() {
this.totalWeight = servers.stream()
.mapToInt(Node::getWeight)
.reduce((a,b)->a+b).getAsInt();
}
public String getServer() {
Node node = servers.stream().max(Comparator.comparingInt(Node::getCurrentWeight)).get();
node.setCurrentWeight(node.getCurrentWeight()-totalWeight);
servers.forEach(server->server.setCurrentWeight(server.getCurrentWeight()+server.getWeight()));
return node.getIp();
}
public static void main(String[] args) {
RoundRobinTest roundRobinTest = new RoundRobinTest();
for (int i = 0; i < 10; i++) {
String server = roundRobinTest.getServer();
System.out.println("select server: "+server);
}
}該算法的核心是的動態計算currentWeight?。每個服務器被選中后，currentWeight需要減去所有服務器的權重之和，這樣可以避免權重高的服務器一直被選中。權重高的服務器有更多的分配請求，請求可以平均分配給所有服務器。
哈希算法
哈希算法，顧名思義，就是利用哈希表根據 計算出請求的路由hashcode%N。這里hashcode代表哈希值，N代表服務器數量。該算法的優點是實現起來非常簡單。具體實現如下：
rivate static final List<String> servers = Arrays.asList("192.168.1.1", "192.168.1.2", "192.168.1.3", "192.168.1.4");
public static String getServer(String key) {
int hash = key.hashCode();
int index = hash%servers.size();
return servers.get(index);
}
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
String server = getServer(String.valueOf(i));
System.out.println("select server: "+server);
}
}哈希算法在很多緩存分布式存儲系統中很常見，比如Memorycached和Redis，但是一般不會用到上面的哈希算法，而是優化后的一致性哈希算法。
總結
本文總結了負載均衡常見的4中算法，我們可以發現nginx?或者spring cloud?中的ribbon都使用到了這樣的算法思想，我們可以根據自己的業務場景選擇合適算法。
