You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@shenyu.apache.org by xi...@apache.org on 2021/10/11 02:58:26 UTC
[incubator-shenyu-website] branch main updated: add
SourceCode-Analysis-LoadBalance-SPI file (#312)
This is an automated email from the ASF dual-hosted git repository.
xiaoyu pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/incubator-shenyu-website.git
The following commit(s) were added to refs/heads/main by this push:
new d244298 add SourceCode-Analysis-LoadBalance-SPI file (#312)
d244298 is described below
commit d2442981e834cedc06b2a8219155fe095874b38e
Author: JenniferYin <43...@users.noreply.github.com>
AuthorDate: Mon Oct 11 10:58:20 2021 +0800
add SourceCode-Analysis-LoadBalance-SPI file (#312)
---
blog/SourceCode-Analysis-LoadBalance-SPI.md | 419 +++++++++++++++++++++
.../SourceCode-Analysis-LoadBalance-SPI.md | 419 +++++++++++++++++++++
.../loadbalance-class-diagram.png | Bin 0 -> 146770 bytes
.../methodWeightMap.png | Bin 0 -> 13038 bytes
.../weighted-roundrobin-demo.png | Bin 0 -> 86681 bytes
5 files changed, 838 insertions(+)
diff --git a/blog/SourceCode-Analysis-LoadBalance-SPI.md b/blog/SourceCode-Analysis-LoadBalance-SPI.md
new file mode 100644
index 0000000..e404b69
--- /dev/null
+++ b/blog/SourceCode-Analysis-LoadBalance-SPI.md
@@ -0,0 +1,419 @@
+---
+slug: code-analysis-loadbalance-spi
+title: LoadBalance SPI Source Code Analysis
+author: Huihui Yin
+author_title: Apache ShenYu Contributor
+author_url: https://github.com/changanjennifer/
+tags: [load balance,SPI,Apache ShenYu]
+---
+
+Gateway applications need to support a variety of load balancing strategies, including `random`,`Hashing`, `RoundRobin` and so on. In `Apache Shenyu` gateway, it not only realizes such traditional algorithms, but also makes smoother traffic processing for the entry of server nodes through detailed processing such as traffic `warm-up,` so as to obtain better overall stability. In this article, let's walk through how `Apache Shenyu` is designed and implemented this part of the function.
+
+> This article based on `shenyu-2.4.0` version of the source code analysis.
+
+[TOC]
+
+## LoadBalance `SPI`
+
+The implementation of `LoadBalance` is in ***shenyu-plugin-divide*** module. It has based on its `SPI` creation mechanism. The core interface code is shown as follows. This interface well explains the concept: load balancing is to select the most appropriate node from a series of server nodes. Routing, traffic processing and load balancing is the basic function of `LoadBalance` `SPI`.
+
+```java
+@SPI
+public interface LoadBalance {
+
+ /**
+ * @param upstreamList upstream list
+ * @param ip ip
+ * @return divide upstream
+ */
+ DivideUpstream select(List<DivideUpstream> upstreamList, String ip);
+}
+```
+
+Where `upstreamList` represents the server nodes list available for routing. `DivideUpstream` is the data structure of server node, the important elements including `protocol`, `upstreamUrl` , `weight`, `timestamp`, `warmup`.
+
+```java
+public class DivideUpstream implements Serializable {
+ private String upstreamHost;
+ /**
+ * this is http protocol.
+ */
+ private String protocol;
+ private String upstreamUrl;
+ private int weight;
+ /**
+ * false close/ true open.
+ */
+ @Builder.Default
+ private boolean status = true;
+ private long timestamp;
+ private int warmup;
+}
+
+```
+
+## Design of LoadBalance module
+
+The class diagram of `LoadBalance` module`is`shown as follows.
+
+
+
+We can draw the outline of `LoadBalance` module from the class diagram:
+
+1. The abstract class `AbstractLoadBalance` implements the SPI `LoadBalance` interface，and supplies the template methods for selection related, such as select(), selector()，and gives the calculation of weight.
+
+2. Three implementation classes which inherit `AbstractLoadBalance` to realize their own logic:
+
+ - `RandomLoadBalance` - Weight Random
+ - `HashLoadBalance` - Consistent Hashing
+ - `RoundRobinLoadBalance` -Weight Round Robin per-packet
+
+3. The utility class `LoadBalanceUtil` provides public static method to be called.
+
+ The implementation classes and algorithms are configurable. According to its specification, by adding profile in `SHENYU_DIERECTORY` directory, the data in profile should be *key*=*value-class* format, where the *value-class* will be load by the `Apache Shenyu SPI` class loader, and *key* value should be an `name` defined in `LoadBalanceEnum.`
+
+```properties
+random=org.apache.shenyu.plugin.divide.balance.spi.RandomLoadBalance
+roundRobin=org.apache.shenyu.plugin.divide.balance.spi.RoundRobinLoadBalance
+hash=org.apache.shenyu.plugin.divide.balance.spi.HashLoadBalance
+```
+
+`The code of LoadBalanceEnum` is as follows：
+
+```java
+public enum LoadBalanceEnum {
+ /**
+ * Hash load balance enum.
+ */
+ HASH(1, "hash", true),
+
+ /**
+ * Random load balance enum.
+ */
+ RANDOM(2, "random", true),
+
+ /**
+ * Round robin load balance enum.
+ */
+ ROUND_ROBIN(3, "roundRobin", true);
+
+ private final int code;
+ private final String name;
+ private final boolean support;
+}
+```
+
+## AbstractLoadBalance
+
+This abstract class implements the `LoadBalance` interface and define the abstract method `doSelect()` to be processed by the implementation classes. In the template method `select()`, It will do validation first then call the `doSelect()` method.
+
+```java
+ /**
+ * Do select divide upstream.
+ *
+ * @param upstreamList the upstream list
+ * @param ip the ip
+ * @return the divide upstream
+ */
+ protected abstract DivideUpstream doSelect(List<DivideUpstream> upstreamList, String ip);
+
+ @Override
+ public DivideUpstream select(final List<DivideUpstream> upstreamList, final String ip) {
+ if (CollectionUtils.isEmpty(upstreamList)) {
+ return null;
+ }
+ if (upstreamList.size() == 1) {
+ return upstreamList.get(0);
+ }
+ return doSelect(upstreamList, ip);
+ }
+```
+
+When the `timestamp` of server node is not null, and the interval between current time and `timestamp` is within the traffic warm-up time, the formula for weight calculation is.
+$$ {1-1}
+ww = min(1,uptime/(warmup/weight))
+$$
+It can be seen from the formula that the final weight(`ww`) is proportional to the original-`weight` value. The closer the time interval is to the `warmup` time, the greater the final `ww`. That is, the longer the waiting time of the request, the higher the final `weight`. When there is no `timestamp` or other conditions, the `ww` is equal to the `weight` value of `DivideUpstream` object.
+
+The central of thinking about *warm-up*is to avoid bad performance when adding new server and the new `JVMs` starting up.
+
+Let's see how the load balancing with `Random`, `Hashing` and `RoundRobin` strategy is implemented.
+
+## RandomLoadBalance
+
+The `RandomLoadBalance` can handle two situations:
+
+1. Each node without weight, or every node has the same weight, randomly choose one.
+2. Server Nodes with different weight, choose one randomly by weight.
+
+Following is the `random()` method of `RandomLoadBalance`. When traversing server node list, if the randomly generated value is less than the weight of node, then the current node will be chosen. If after one round traversing, there's is no server node match, then it will return the first item of the list. The `getWeight(DivideUpstream upstream)` is defined in `AbstractLoadBalance` class.
+
+```java
+ private DivideUpstream random(final int totalWeight, final List<DivideUpstream> upstreamList) {
+ // If the weights are not the same and the weights are greater than 0, then random by the total number of weights
+ int offset = RANDOM.nextInt(totalWeight);
+ // Determine which segment the random value falls on
+ for (DivideUpstream divideUpstream : upstreamList) {
+ offset -= getWeight(divideUpstream);
+ if (offset < 0) {
+ return divideUpstream;
+ }
+ }
+ return upstreamList.get(0);
+ }
+```
+
+## HashLoadBalance
+
+In `HashLoadBalance`, it takes the advantages of [consistent hashing](https://en.wikipedia.org/wiki/Consistent_hashing) , that maps both the input traffic and the servers to a unit circle, or name as *hash ring*. For the requested`ip` address, with its hash value to find the node closest in clockwise order as the node to be routed. Let's see how consistent hashing is implemented in `HashLoadBalance`.
+
+As to the hash algorithms, `HashLoadBalance` uses `MD5` hash, which has the advantage of mixing the input in an unpredictable but deterministic way. The output is a 32-bit integer. the code is shown as follows:
+
+```java
+private static long hash(final String key) {
+ // md5 byte
+ MessageDigest md5;
+ try {
+ md5 = MessageDigest.getInstance("MD5");
+ } catch (NoSuchAlgorithmException e) {
+ throw new ShenyuException("MD5 not supported", e);
+ }
+ md5.reset();
+ byte[] keyBytes;
+ keyBytes = key.getBytes(StandardCharsets.UTF_8);
+ md5.update(keyBytes);
+ byte[] digest = md5.digest();
+ // hash code, Truncate to 32-bits
+ long hashCode = (long) (digest[3] & 0xFF) << 24
+ | ((long) (digest[2] & 0xFF) << 16)
+ | ((long) (digest[1] & 0xFF) << 8)
+ | (digest[0] & 0xFF);
+ return hashCode & 0xffffffffL;
+}
+```
+
+Importantly, how to generate the hash ring and avoid skewness? Let's the`doSelect()` method in`HashLoadBalance` as follows:
+
+```java
+ private static final int VIRTUAL_NODE_NUM = 5;
+
+ @Override
+ public DivideUpstream doSelect(final List<DivideUpstream> upstreamList, final String ip) {
+ final ConcurrentSkipListMap<Long, DivideUpstream> treeMap = new ConcurrentSkipListMap<>();
+ for (DivideUpstream address : upstreamList) {
+ for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
+ long addressHash = hash("SOUL-" + address.getUpstreamUrl() + "-HASH-" + i);
+ treeMap.put(addressHash, address);
+ }
+ }
+ long hash = hash(String.valueOf(ip));
+ SortedMap<Long, DivideUpstream> lastRing = treeMap.tailMap(hash);
+ if (!lastRing.isEmpty()) {
+ return lastRing.get(lastRing.firstKey());
+ }
+ return treeMap.firstEntry().getValue();
+ }
+```
+
+In this method, duplicated labels are used which are called "virtual nodes" (i.e. 5 virtual nodes point to a single "real" server). It will make the distribution in hash ring more evenly, and reduce the occurrence of data skewness.
+
+In order to rescue the data sorted in the hash ring, and can be accessed quickly, we use [ConcurrentSkipListMap](https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentSkipListMap.html) of Java to store the server node lists ( with virtual nodes) and its hash value as key. This class a member of [Java Collections Framework](https://docs.oracle.com/javase/8/docs/technotes/guides/collections/index.html), providing expected average *log(n)* time cost for retrieve and acce [...]
+
+Furthermore, the method tailMap(K fromKey) of `ConcurrentSkipListMap` can return a view of portion of the map whose keys are greater or equal to the `fromKey`, and not need to navigate the whole map.
+
+In the above code section, after the hash ring is generated, it uses `tailMap(K fromKey)` of `ConcurrentSkipListMap` to find the subset that the elements greater, or equal to the hash value of the requested `ip`, its first element is just the node to be routed. With the suitable data structure, the code looks particularly clear and concise.
+
+Consistent hashing resolved the poor scalability of the traditional hashing by modular operation.
+
+## RoundRobinLoadBalance
+
+The original Round-robin selection is to select server nodes one by one from the candidate list. Whenever some nodes has crash ( ex, cannot be connected after 1 minute), it will be removed from the candidate list, and do not attend the next round, until the server node is recovered and it will be add to the candidate list again. In `RoundRobinLoadBalance`,the weight Round Robin per-packet schema is implemented.
+
+In order to work in concurrent system, it provides an inner static class `WeigthRoundRobin` to store and calculate the rolling selections of each server node. Following is the main section of this class( removed remark )
+
+```java
+protected static class WeightedRoundRobin {
+
+ private int weight;
+ private final AtomicLong current = new AtomicLong(0);
+
+ private long lastUpdate;
+
+ void setWeight(final int weight) {
+ this.weight = weight;
+ current.set(0);
+ }
+ long increaseCurrent() {
+ return current.addAndGet(weight);
+ }
+
+ void sel(final int total) {
+ current.addAndGet(-1 * total);
+ }
+ void setLastUpdate(final long lastUpdate) {
+ this.lastUpdate = lastUpdate;
+ }
+}
+```
+
+Please focus on the these method:
+
+- `setWeight(final int weight)` : set the current value by *weight*
+
+- `increaseCurrent()`: Increment the `current` value by `weight`, and `current` set to 0.
+
+- `sel(final int total)`: decrement the `current` value by *total*
+
+ Let's see how the weight factor being used in this round-robin selection?
+
+ First it defines a two-level `ConcurrentMap` type variable named as `methodWeightMap` , to cache the server node lists and the rolling selection data about each server node.
+
+```java
+private final ConcurrentMap<String, ConcurrentMap<String, WeightedRoundRobin>> methodWeightMap = new ConcurrentHashMap<>(16);
+```
+
+In this map, the key of first level is set to `upstreamUrl` of first element in server node list. The type of second object is `ConcurrentMap<String, WeightedRoundRobin>,` the key of this inner Map is the value `upstreamUrl`variable of each server node in this server list, the value object is `WeightedRoundRobin`, used to trace the rolling selection data about each server node. As to the implementation class for the Map object, we use `ConcurrentHashMap` of [JUC](https://docs.oracle.c [...]
+
+In the second level of the map, the embedded static class - `WeighedRoundRobin` of each node is thread-safe, implementing the weighted `RoundRobin` per bucket. The following is the code of the `doselect()` method of this class.
+
+```java
+@Override
+public DivideUpstream doSelect(final List<DivideUpstream> upstreamList, final String ip) {
+ String key = upstreamList.get(0).getUpstreamUrl();
+ ConcurrentMap<String, WeightedRoundRobin> map = methodWeightMap.get(key);
+ if (map == null) {
+ methodWeightMap.putIfAbsent(key, new ConcurrentHashMap<>(16));
+ map = methodWeightMap.get(key);
+ }
+ int totalWeight = 0;
+ long maxCurrent = Long.MIN_VALUE;
+ long now = System.currentTimeMillis();
+ DivideUpstream selectedInvoker = null;
+ WeightedRoundRobin selectedWRR = null;
+ for (DivideUpstream upstream : upstreamList) {
+ String rKey = upstream.getUpstreamUrl();
+ WeightedRoundRobin weightedRoundRobin = map.get(rKey);
+ int weight = getWeight(upstream);
+ if (weightedRoundRobin == null) {
+ weightedRoundRobin = new WeightedRoundRobin();
+ weightedRoundRobin.setWeight(weight);
+ map.putIfAbsent(rKey, weightedRoundRobin);
+ }
+ if (weight != weightedRoundRobin.getWeight()) {
+ //weight changed
+ weightedRoundRobin.setWeight(weight);
+ }
+ long cur = weightedRoundRobin.increaseCurrent();
+ weightedRoundRobin.setLastUpdate(now);
+ if (cur > maxCurrent) {
+ maxCurrent = cur;
+ selectedInvoker = upstream;
+ selectedWRR = weightedRoundRobin;
+ }
+ totalWeight += weight;
+ }
+ ...... //erase the section which handles the time-out upstreams.
+ if (selectedInvoker != null) {
+ selectedWRR.sel(totalWeight);
+ return selectedInvoker;
+ }
+ // should not happen here
+ return upstreamList.get(0);
+}
+```
+
+For example we assume `upstreamUrl` values of three server nodes is: LIST = [upstream-20, upstream-50, upstream-30]. After a round of execution, the data in newly created `methodWeightMap` is as follows:
+
+
+
+For the above example LIST, assumes the `weight` array is [20,50,30]. the following figure shows the value change and polling selection process of the `current` array in `WeighedRoundRobin` object.
+
+
+
+In each round, it will choose the server node with max `current` value.
+
+- Round1:
+ - Traverse the server node list, initialize the `weightedRoundRobin` instance of each server node or update the `weight` value of server nodes object `DivideUpstream`
+ - say, in this case, after traverse, the `current` array of the node list changes to [20, 50,30]，so according to rule, the node Stream-50 would be chosen, and then the static object `WeightedRoundRobin` of Stream-50 executes `sel(-total)` , the `current` array is now [20,-50, 30].
+- Round 2: after traverse, the `current` array should be [40,0,60], so the Stream-30 node would be chosen， `current` array is now [40,0,-40].
+- Round 3: after traverse, `current` array changes to [60,50,-10], Stream-20 would be chosen，and `current` array is now [-40,50,-10].
+
+When there is any inconsistence or some server crashed, for example, the lists size does not match with the elements in map, it would copy and modify the element with lock mechanism, and remove the timeout server node, the data in Map updated. Following is the fault tolerance code segment.
+
+```Java
+ if (!updateLock.get() && upstreamList.size() != map.size() && updateLock.compareAndSet(false, true)) {
+ try {
+ // copy -> modify -> update reference
+ ConcurrentMap<String, WeightedRoundRobin> newMap = new ConcurrentHashMap<>(map);
+ newMap.entrySet().removeIf(item -> now - item.getValue().getLastUpdate() > recyclePeriod);
+ methodWeightMap.put(key, newMap);
+ } finally {
+ updateLock.set(false);
+ }
+ }
+
+ if (selectedInvoker != null) {
+ selectedWRR.sel(totalWeight);
+ return selectedInvoker;
+ }
+ // should not happen here
+ return upstreamList.get(0);
+```
+
+## LoadBalanceUtils
+
+In this class, a static method calling `LoadBalance` is provided, where`ExtensionLoader` is the entry point of `Apache Shenyu SPI`. That is to say, `LoadBalance` module is configurable and extensible. The `algorithm` variable in this static method is the `name` enumeration type defined in `LoadBalanceEnum`.
+
+```java
+ /**
+ * Selector divide upstream.
+ *
+ * @param upstreamList the upstream list
+ * @param algorithm the loadBalance algorithm
+ * @param ip the ip
+ * @return the divide upstream
+ */
+ public static DivideUpstream selector(final List<DivideUpstream> upstreamList, final String algorithm, final String ip) {
+ LoadBalance loadBalance = ExtensionLoader.getExtensionLoader(LoadBalance.class).getJoin(algorithm);
+ return loadBalance.select(upstreamList, ip);
+ }
+```
+
+## Using of LoadBalance module
+
+In the above section, we describe the `LoadBalance` `SPI` and three implementation classes. Let's take a look at how the `LoadBalance` to be used in `Apache Shenyu`. [DividePlugin](http://shenyu.apache.org/docs/plugin-center/http-handle/divide-plugin) is a `plugin` in `Apache Shenyu` responsible for routing `http` request. when enable to use this `plugin`, it will transfer traffic according to selection data and rule data, and deliver to next plugin downstream.
+
+```java
+@SneakyThrows
+@Override
+protected Mono<Void> doExecute(final ServerWebExchange exchange, final ShenyuPluginChain chain, final SelectorData selector, final RuleData rule) {
+ ......
+}
+```
+
+The type of second parameter of `doExecute()` is `ShenyuPluginChain`, which represents the execution chain of `plugins`. For details, see the mechanism of [Apache Shenyu Plugins](http://shenyu.apache.org/docs/design/flow-control). The third one is `SelectorData` type, and the fourth is `RuleData` type working as the rule data.
+
+In `doExecute()` of `DividePlugin`, first verify the size of `header`, content length, etc, then preparing for load balancing.
+
+Following is a code fragment using`LoadBalance` in the `doExecute()` method:
+
+```java
+ // find the routing server node list
+ List<DivideUpstream> upstreamList = UpstreamCacheManager.getInstance().findUpstreamListBySelectorId(selector.getId());
+ ...
+ // the requested ip
+ String ip = Objects.requireNonNull(exchange.getRequest().getRemoteAddress()).getAddress().getHostAddress();
+
+ //calling the Utility class and invoke the LoadBalance processing.
+ DivideUpstream divideUpstream = LoadBalanceUtils.selector(upstreamList, ruleHandle.getLoadBalance(), ip);
+```
+
+ In the above code, the output of`ruleHandle.getLoadBalance()` is the `name` variable defined in `LoadBalanceEnum`, that is `random`, `hash`, `roundRobin`, etc. It is very convenient to use `LoadBalance` by `LoadBalanceUtils`. When adding more `LoadBalance` implementing classes, the interface in `plugin` module will not be affect at all.
+
+## Summary
+
+After reading through the code of `LoadBalance` module, from the design perspective, it is concluded that this module has the following characteristics:
+
+1. Extensibility: Interface oriented design and implemented on `Apache Shenyu SPI` mechanism, it can be easily extended to other dynamic load balancing algorithms (for example, least connection, fastest mode, etc), and supports cluster processing.
+2. Scalability： Every load balancing implementation, weighted Random, consistency Hashing and weighted `RoundRobin` can well support increase or decrease cluster overall capacity.
+3. More detailed design such as *warm-up* can bring better performance and obtain better overall stability.
diff --git a/i18n/zh/docusaurus-plugin-content-blog/SourceCode-Analysis-LoadBalance-SPI.md b/i18n/zh/docusaurus-plugin-content-blog/SourceCode-Analysis-LoadBalance-SPI.md
new file mode 100644
index 0000000..da0fe94
--- /dev/null
+++ b/i18n/zh/docusaurus-plugin-content-blog/SourceCode-Analysis-LoadBalance-SPI.md
@@ -0,0 +1,419 @@
+---
+slug: code-analysis-loadbalance-spi
+title: LoadBalance SPI 代码分析
+author: Huihui Yin
+author_title: Apache ShenYu Contributor
+author_url: https://github.com/changanjennifer/
+tags: [load balance,SPI,Apache ShenYu]
+---
+
+ 网关应用需要支持多种负载均衡的方案，包括随机选择、Hash、轮询等方式。`Apache Shenyu`网关中不仅实现了传统网关的这些均衡策略，还通过流量预热(warmup)等细节处理，对服务器节点的加入，做了更平滑的流量处理，获得了更好的整体稳定性。让我们来看看Shenyu是是如何设计和实现这部分功能的。
+
+> 本文基于`shenyu-2.4.0`版本进行源码分析.
+
+[TOC]
+
+## LoadBalance `SPI`
+
+`LoadBalance` SPI 定义在***shenyu-plugin-divide***模组中，以下是这个核心接口的代码，这个接口很好的诠释了这样一个理念：负载均衡是在一系列服务器节点中选出最合适的节点，也就是选择策略。做流量转发、路由和负载均衡是`LoadBalance SPI`的基本功能
+
+```java
+@SPI
+public interface LoadBalance {
+
+ /**
+ * @param upstreamList upstream list
+ * @param ip ip
+ * @return divide upstream
+ */
+ DivideUpstream select(List<DivideUpstream> upstreamList, String ip);
+}
+```
+
+接口中，upstreamList是可选路由的一组服务器节点，`DivideUpstream` 是服务器节点的数据结构，它包括的重要元素有：协议、upstreamUrl 、权重、时间戳，warmup等。
+
+```java
+public class DivideUpstream implements Serializable {
+ private String upstreamHost;
+ /**
+ * this is http protocol.
+ */
+ private String protocol;
+ private String upstreamUrl;
+ private int weight;
+ /**
+ * false close/ true open.
+ */
+ @Builder.Default
+ private boolean status = true;
+ private long timestamp;
+ private int warmup;
+}
+
+```
+
+## Design of LoadBalance module
+
+图1是`LoadBalance`模组的类图：
+
+
+
+从类图上可以看出`LoadBalance`的设计概要：
+
+1. 抽象类`AbstractLoadBalance`继承自`LoadBalance` SPI接口，并提供选择的模板方法，及权重计算。
+
+2. 三个实做类继承`AbstractLoadBalance`， 实现各自的逻辑处理。
+
+ - `RandomLoadBalance` -加权随机选择 Weight Random
+ - `HashLoadBalance` - 一致性Hash
+ - `RoundRobinLoadBalance` -加权轮询（Weight Round Robin per-packet)
+
+3. 由Util类`LoadBalanceUtil` 实现对外的静态调用方法。
+
+ 另外根据`Apache Sheny SPI`规范，在`SHENYU_DIERECTORY`中的添加profile，配置`LoadBalance`的实现类，配置key=class形式，左边的operator要和`LoadBalanceEnum`中的定义一致。
+
+```properties
+random=org.apache.shenyu.plugin.divide.balance.spi.RandomLoadBalance
+roundRobin=org.apache.shenyu.plugin.divide.balance.spi.RoundRobinLoadBalance
+hash=org.apache.shenyu.plugin.divide.balance.spi.HashLoadBalance
+```
+
+`LoadBalanceEnum`的定义如下：
+
+```java
+public enum LoadBalanceEnum {
+ /**
+ * Hash load balance enum.
+ */
+ HASH(1, "hash", true),
+
+ /**
+ * Random load balance enum.
+ */
+ RANDOM(2, "random", true),
+
+ /**
+ * Round robin load balance enum.
+ */
+ ROUND_ROBIN(3, "roundRobin", true);
+
+ private final int code;
+ private final String name;
+ private final boolean support;
+}
+```
+
+## AbstractLoadBalance
+
+这个抽象类实做了`LoadBalance`接口, 定义了抽象方法`doSelect()`留给实作类处理，在模板方法`select()` 中先进行校验，之后调用由实作类实现的`doSelect()`方法。
+
+```java
+ /**
+ * Do select divide upstream.
+ *
+ * @param upstreamList the upstream list
+ * @param ip the ip
+ * @return the divide upstream
+ */
+ protected abstract DivideUpstream doSelect(List<DivideUpstream> upstreamList, String ip);
+
+ @Override
+ public DivideUpstream select(final List<DivideUpstream> upstreamList, final String ip) {
+ if (CollectionUtils.isEmpty(upstreamList)) {
+ return null;
+ }
+ if (upstreamList.size() == 1) {
+ return upstreamList.get(0);
+ }
+ return doSelect(upstreamList, ip);
+ }
+```
+
+权重的处理方法`getWeight()`的逻辑是：当有时间戳，并且当前时间与时间戳间隔在流量预热warmup时间内，权重计算的公式为：
+$$ {1-1}
+ww = min(1,uptime/(warmup/weight))
+$$
+从公式可以看出，最终的权值，与设置的weigth成正比，时间间隔越接近warmup时间，权重就越大。也就是说等待的时间越长，被分派的权重越高。没有时间戳时等其他情况下，返回`DivideUpstream`设置的`weight`值。
+
+考虑流量预热(warmup)的核心思想是避免在添加新服务器和启动新JVM时网关性能不佳。
+
+下面我们看一下三个实做类的实现。
+
+## RandomLoadBalance
+
+这里随机`LoadBalance` 可以处理两种情况：
+
+1. 没有权重：所有服务器都没有设定权重，或者权重都一样， 会随机选择一个。
+2. 有权重：服务器设定有不同的权重，会根据权重，进行随机选择。
+
+下面是有权重时的随机选择代码`random()`： 遍历服务器列表，当产生的随机值小于某个服务器权重时，这个服务器被选中。 若遍历后没有满足条件，就返回服务器列表的第一个。这里`getWeight(DivideUpstream upstream)` 方法是在`AbstractLoadBalance` 中定义的，按公式计算权重。
+
+```java
+ private DivideUpstream random(final int totalWeight, final List<DivideUpstream> upstreamList) {
+ // If the weights are not the same and the weights are greater than 0, then random by the total number of weights
+ int offset = RANDOM.nextInt(totalWeight);
+ // Determine which segment the random value falls on
+ for (DivideUpstream divideUpstream : upstreamList) {
+ offset -= getWeight(divideUpstream);
+ if (offset < 0) {
+ return divideUpstream;
+ }
+ }
+ return upstreamList.get(0);
+ }
+```
+
+因此，当采用`RandomLoadBalance`时，是按权重随机分派服务器的。
+
+## HashLoadBalance
+
+`Apache Shenyu`的`HashLoadBalance` 中采用了一致性hash算法，使用有序hash环，将key与服务器节点的hash映射缓存起来。对于请求的ip地址，计算出其`hash`值， 在hash环上顺时针查找距离这个key的hash值最近的节点，将其作为要路由的节点。一致性hash解决了传统取余hash算法的可伸缩性差的问题。
+
+`HashLoadBalance`中的采用的是加密的单向MD5散列函数，这个hash函数会hash后产生不可预期但确定性的()的结果，输出为32-bit的长整数。`hash`代码如下：
+
+```java
+private static long hash(final String key) {
+ // md5 byte
+ MessageDigest md5;
+ try {
+ md5 = MessageDigest.getInstance("MD5");
+ } catch (NoSuchAlgorithmException e) {
+ throw new ShenyuException("MD5 not supported", e);
+ }
+ md5.reset();
+ byte[] keyBytes;
+ keyBytes = key.getBytes(StandardCharsets.UTF_8);
+ md5.update(keyBytes);
+ byte[] digest = md5.digest();
+ // hash code, Truncate to 32-bits
+ long hashCode = (long) (digest[3] & 0xFF) << 24
+ | ((long) (digest[2] & 0xFF) << 16)
+ | ((long) (digest[1] & 0xFF) << 8)
+ | (digest[0] & 0xFF);
+ return hashCode & 0xffffffffL;
+}
+```
+
+再看一下`HashLoadBalance`的选择函数`doSelect()`的实现：
+
+```java
+ private static final int VIRTUAL_NODE_NUM = 5;
+
+ @Override
+ public DivideUpstream doSelect(final List<DivideUpstream> upstreamList, final String ip) {
+ final ConcurrentSkipListMap<Long, DivideUpstream> treeMap = new ConcurrentSkipListMap<>();
+ for (DivideUpstream address : upstreamList) {
+ for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
+ long addressHash = hash("SOUL-" + address.getUpstreamUrl() + "-HASH-" + i);
+ treeMap.put(addressHash, address);
+ }
+ }
+ long hash = hash(String.valueOf(ip));
+ SortedMap<Long, DivideUpstream> lastRing = treeMap.tailMap(hash);
+ if (!lastRing.isEmpty()) {
+ return lastRing.get(lastRing.firstKey());
+ }
+ return treeMap.firstEntry().getValue();
+ }
+```
+
+这个方法中，生成带虚拟服务器节点的hash环， 一个实际节点会生成5个虚拟节点，因此整个hash环的均匀性大大增加，降低数据倾斜的发生。
+
+为了实现hash环的有序性及顺时针查找功能，代码中使用Java 的[ConcurrentSkipListMap](https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentSkipListMap.html) 来存储带虚拟节点的服务器节点及其hash值， 它既能保证线程安全，又能保证数据的有序性，支持高并发。 另外，`ConcurrentSkipListMap`提供了一个`tailMap(K fromKey)`方法，可从`map`中查找比`fromKey`大的值的集合，但并不需要遍历整个数据结构。
+
+上述代码中，生成hash环之后，就是调用`ConcurrentSkipListMap`的`tailMap()`方法，找到大于等于请求的ip的hash值的子集，这个子集的第一个就是要路由的服务器节点。采用了合适的数据结构，这里的代码看上去是不是特别的简洁流畅？
+
+## RoundRobinLoadBalance
+
+Round-robin轮询方法的原始定义是顺序循环将请求依次循环地连接到每个服务器。当某个服务器发生故障（例如：一分钟连接不上的服务器)，从候选队列中取出，不参与下一次的轮询，直到其恢复正常。在 `RoundRobinLoadBalance`中实现的是组内加权轮询（`Weight Round Robin per-packet`)方法：
+
+为了计算和存储每个服务器节点的轮询次数，在这个类中定义了一个静态内部类`WeigthRoundRobin`，我们先看一下它的主要代码（去掉了注释）：
+
+```java
+protected static class WeightedRoundRobin {
+
+ private int weight;
+ private final AtomicLong current = new AtomicLong(0);
+
+ private long lastUpdate;
+
+ void setWeight(final int weight) {
+ this.weight = weight;
+ current.set(0);
+ }
+ long increaseCurrent() {
+ return current.addAndGet(weight);
+ }
+
+ void sel(final int total) {
+ current.addAndGet(-1 * total);
+ }
+ void setLastUpdate(final long lastUpdate) {
+ this.lastUpdate = lastUpdate;
+ }
+}
+```
+
+请重点关注这几个方法：
+
+- `setWeight(final int weight)` ，为对象设定权重，并将current重置为0.
+
+- `increaseCurrent()` : 对`AtomicLong`类型的对象`current`，累加其权重值。
+
+- `sel(final int total)`: `current`减去传入的 `total`值。
+
+下面我们看一下带权重的轮询过程是如何实现的。
+首先定义了一个`ConcurrentMap`类型对象`methodWeightMap` 两层对象来存储服务器列表与其各个明细节点的轮询资料。
+
+```java
+private final ConcurrentMap<String, ConcurrentMap<String, WeightedRoundRobin>> methodWeightMap = new ConcurrentHashMap<>(16);
+```
+
+这个map对象第一层的key为当前服务器列表的第一个节点的`upstreamUrl`, 第二个对象`ConcurrentMap<String, WeightedRoundRobin>`存储了组内各个服务器节点的轮询情况，内层Map的key为组内每个服务器的`upstreamUrl`。`Map`对象使用`JUC`的`ConcurrentHashMap`，不仅存取高效，而且线程安全，支持高并发。
+
+内层map的每个节点对应的`WeighedRoundRobin`作为静态内部类能确保线程安全，并实现组内的加权轮询选择功能。下面是这个类的`doSelect()`方法的代码。
+
+```java
+@Override
+public DivideUpstream doSelect(final List<DivideUpstream> upstreamList, final String ip) {
+ String key = upstreamList.get(0).getUpstreamUrl();
+ ConcurrentMap<String, WeightedRoundRobin> map = methodWeightMap.get(key);
+ if (map == null) {
+ methodWeightMap.putIfAbsent(key, new ConcurrentHashMap<>(16));
+ map = methodWeightMap.get(key);
+ }
+ int totalWeight = 0;
+ long maxCurrent = Long.MIN_VALUE;
+ long now = System.currentTimeMillis();
+ DivideUpstream selectedInvoker = null;
+ WeightedRoundRobin selectedWRR = null;
+ for (DivideUpstream upstream : upstreamList) {
+ String rKey = upstream.getUpstreamUrl();
+ WeightedRoundRobin weightedRoundRobin = map.get(rKey);
+ int weight = getWeight(upstream);
+ if (weightedRoundRobin == null) {
+ weightedRoundRobin = new WeightedRoundRobin();
+ weightedRoundRobin.setWeight(weight);
+ map.putIfAbsent(rKey, weightedRoundRobin);
+ }
+ if (weight != weightedRoundRobin.getWeight()) {
+ //weight changed
+ weightedRoundRobin.setWeight(weight);
+ }
+ long cur = weightedRoundRobin.increaseCurrent();
+ weightedRoundRobin.setLastUpdate(now);
+ if (cur > maxCurrent) {
+ maxCurrent = cur;
+ selectedInvoker = upstream;
+ selectedWRR = weightedRoundRobin;
+ }
+ totalWeight += weight;
+ }
+ ...... //erase the section which handles the time-out upstreams.
+ if (selectedInvoker != null) {
+ selectedWRR.sel(totalWeight);
+ return selectedInvoker;
+ }
+ // should not happen here
+ return upstreamList.get(0);
+}
+```
+
+举例，若服务器组`upstreamUrl` 分别为： LIST = [upstream-20, upstream-50, upstream-30]时，经过一轮执行后，建立的`methodWeightMap` 资料如下：
+
+
+
+假设上述的LIST中，各个服务器节点的权重数组为: [20,50,30], 下图是内部类current 值变化和轮询选择过程：
+
+
+
+每一轮，选择值current最大的服务器节点：
+
+- Round1:
+ - 对当前服务器LIST做遍历，当服务器节点的weightedRoundRobin 为null时，current被置为各自的权重； 不为null时，累加各自的权重。
+ - 即：遍历后current 分别为 [20, 50,30] ， 会选择Stream-50, Stream-50对应的WeightRoundRobin静态类做 sel(-total)处理，current 更新为[20,-50, 30].
+- Round 2 遍历后的current是[40,0,60], 会选择Stream-30， current分别更新为[40,0,-40].
+- Round 3 遍历后的current是[60,50,-10], 会选择Stream-20，current分别更新为[-40,50,-10].
+
+中间进行了容错处理， 当服务器的个数与map个数不一样，就对methodWeightMap 加锁做处理。 用先copy 后modify的方式， 把超时的服务器remove掉，即移除掉发生故障的服务器，并更新Map资料。如下是异常时的处理代码：
+
+```Java
+ if (!updateLock.get() && upstreamList.size() != map.size() && updateLock.compareAndSet(false, true)) {
+ try {
+ // copy -> modify -> update reference
+ ConcurrentMap<String, WeightedRoundRobin> newMap = new ConcurrentHashMap<>(map);
+ newMap.entrySet().removeIf(item -> now - item.getValue().getLastUpdate() > recyclePeriod);
+ methodWeightMap.put(key, newMap);
+ } finally {
+ updateLock.set(false);
+ }
+ }
+
+ if (selectedInvoker != null) {
+ selectedWRR.sel(totalWeight);
+ return selectedInvoker;
+ }
+ // should not happen here
+ return upstreamList.get(0);
+```
+
+## LoadBalanceUtils
+
+在这个类中，提供了调用`LoadBalance`的静态方法, 其中`ExtensionLoader` 是`Apache Shenyu`的`SPI`执行入口。也就是说，LoadBalance模组是可配置、可扩展的。这个静态方法中的`algorithm`变量是`LoadBalanceEnum`中定义`name`枚举类型。
+
+```java
+ /**
+ * Selector divide upstream.
+ *
+ * @param upstreamList the upstream list
+ * @param algorithm the loadBalance algorithm
+ * @param ip the ip
+ * @return the divide upstream
+ */
+ public static DivideUpstream selector(final List<DivideUpstream> upstreamList, final String algorithm, final String ip) {
+ LoadBalance loadBalance = ExtensionLoader.getExtensionLoader(LoadBalance.class).getJoin(algorithm);
+ return loadBalance.select(upstreamList, ip);
+ }
+```
+
+## Using of LoadBalance module
+
+上面说明了`LoadBalance` SPI接口及三个实作类。下面看一下`LoadBalance`在`Apache Shenyu`中是如何被调用的。`DividePlugin`是路由选择插件，所有的Http请求都由该插件进行负载均衡处理。当请求头rpcType = http, 且开启该插件时，它将根据请求参数匹配规则，最终交由下游插件进行响应式代理调用。
+
+在`DividePlugin`的`doExecute`方法中，先对要转发的请求的Header大小、content长度等做校验，
+
+```java
+@SneakyThrows
+@Override
+protected Mono<Void> doExecute(final ServerWebExchange exchange, final ShenyuPluginChain chain, final SelectorData selector, final RuleData rule) {
+ ......
+}
+```
+
+接口方法的第二个参数是`ShenyuPluginChain` 类型，代表`plugin`的调用链，具体可参见`Apache Sheyu` 的`plugin`的调用机制。第三个`SelectorData`类型的参数是选择器， 第四个是`RuldData`类型，代表规则。分别请查看对应的代码。
+
+ 下面给出了`doExecute`()方法中，有关`LoadBalance`调用的代码片段：
+
+```java
+ //取到要路由的服务器节点列表。
+ List<DivideUpstream> upstreamList = UpstreamCacheManager.getInstance().findUpstreamListBySelectorId(selector.getId());
+ ...
+ //取到请求的ip
+ String ip = Objects.requireNonNull(exchange.getRequest().getRemoteAddress()).getAddress().getHostAddress();
+
+ //调用Util方法，执行LoadBalance处理
+ DivideUpstream divideUpstream = LoadBalanceUtils.selector(upstreamList, ruleHandle.getLoadBalance(), ip);
+```
+
+ 这里`UpstreamCacheManager` 是缓存的要路由的服务器节点 ， `ruleHandle.getLoadBalance()`取到的是`LoadBalanceEnum`定义的枚举name, 如`random, hash, roundRobin`等.
+
+ 经过封装，调用负载均衡功能非常的方便。 未来增加新的`LoadBalance`类，这些调用的`Plugin`代码完全不需要变更。
+
+## Summary
+
+经过上面的代码解读，从设计角度总结`LoadBalance` 模组具有如下的特点：
+
+1. 可扩展性：面向接口的设计，及基于Apache Shenyu SPI的实现，使得系统具有良好的可扩展性。可以方便的扩展为其他的动态的负载均衡算法，如最少连接方式(least connection)、最快模式( fastest)。并支持集群处理，具有良好的可扩展性。
+2. 可伸缩性： 采用的一致性hash `LoadBalance`、权重随机和权重轮询，都可以无缝支持集群扩容或缩容。
+
+3. 流量预热等更细致的设计，能带来整体上更为平滑的负载均衡。
diff --git a/static/img/activities/code-analysis-loadbalance-spi/loadbalance-class-diagram.png b/static/img/activities/code-analysis-loadbalance-spi/loadbalance-class-diagram.png
new file mode 100644
index 0000000..c6a9daa
Binary files /dev/null and b/static/img/activities/code-analysis-loadbalance-spi/loadbalance-class-diagram.png differ
diff --git a/static/img/activities/code-analysis-loadbalance-spi/methodWeightMap.png b/static/img/activities/code-analysis-loadbalance-spi/methodWeightMap.png
new file mode 100644
index 0000000..15d7b76
Binary files /dev/null and b/static/img/activities/code-analysis-loadbalance-spi/methodWeightMap.png differ
diff --git a/static/img/activities/code-analysis-loadbalance-spi/weighted-roundrobin-demo.png b/static/img/activities/code-analysis-loadbalance-spi/weighted-roundrobin-demo.png
new file mode 100644
index 0000000..15bd794
Binary files /dev/null and b/static/img/activities/code-analysis-loadbalance-spi/weighted-roundrobin-demo.png differ