Introduction to Load Balancing and Its Algorithms

This article provides a comprehensive overview of load balancing, a critical component for high‑concurrency and high‑availability systems. It begins by describing the challenges faced by large‑scale websites—massive user traffic, high concurrency, and massive data—and explains two scaling approaches: vertical scaling (adding CPU, memory, disk to a single machine) and horizontal scaling (adding stateless application servers to a cluster).

Load balancing is defined as the process of distributing network traffic across multiple servers to improve overall response speed and availability. Its main functions include handling high concurrency, providing scalability, ensuring high availability, and offering security features such as black‑/white‑listing and DDoS protection.

The article classifies load balancing from several dimensions:

By carrier: hardware load balancers (e.g., F5, A10) and software load balancers (e.g., Nginx, HAProxy, LVS).

By network layer: DNS, HTTP redirect, reverse proxy, IP (layer‑3), and data‑link layer.

By algorithm: random, weighted random, round‑robin, weighted round‑robin, least active, weighted least active, source‑IP hash, and consistent hash.

Each classification is described with its advantages and disadvantages, accompanied by diagrams (omitted here) and practical usage scenarios.

Key load‑balancing algorithms are detailed as follows:

Random Algorithm

Requests are assigned to a randomly selected node. Suitable when all servers have identical hardware.

public interface LoadBalance<N extends Node> {
    N select(List<N> nodes, String ip);
}

public abstract class BaseLoadBalance<N extends Node> implements LoadBalance<N> {
    @Override
    public N select(List<N> nodes, String ip) {
        if (CollectionUtil.isEmpty(nodes)) {
            return null;
        }
        if (nodes.size() == 1) {
            return nodes.get(0);
        }
        return doSelect(nodes, ip);
    }
    protected abstract N doSelect(List<N> nodes, String ip);
}

public class RandomLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
    private final Random random = new Random();
    @Override
    protected N doSelect(List<N> nodes, String ip) {
        int index = random.nextInt(nodes.size());
        return nodes.get(index);
    }
}

Weighted Random Algorithm

Extends random selection by assigning weights to nodes; the probability of selection is proportional to the weight.

public class WeightRandomLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
    private final Random random = ThreadLocalRandom.current();
    @Override
    protected N doSelect(List<N> nodes, String ip) {
        int length = nodes.size();
        AtomicInteger totalWeight = new AtomicInteger(0);
        for (N node : nodes) {
            Integer weight = node.getWeight();
            totalWeight.getAndAdd(weight);
        }
        if (totalWeight.get() > 0) {
            int offset = random.nextInt(totalWeight.get());
            for (N node : nodes) {
                offset -= node.getWeight();
                if (offset < 0) {
                    return node;
                }
            }
        }
        return nodes.get(random.nextInt(length));
    }
}

Round‑Robin Algorithm

Requests are distributed sequentially across nodes.

public class RoundRobinLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
    private final AtomicInteger position = new AtomicInteger(0);
    @Override
    protected N doSelect(List<N> nodes, String ip) {
        int length = nodes.size();
        position.compareAndSet(length, 0);
        N node = nodes.get(position.get());
        position.getAndIncrement();
        return node;
    }
}

Weighted Round‑Robin Algorithm

Combines round‑robin with node weights, allowing higher‑capacity servers to receive more requests.

public class WeightRoundRobinLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
    private final AtomicInteger position = new AtomicInteger(0);
    private static final int RECYCLE_PERIOD = 60000;
    private final ConcurrentMap<Integer, WeightedRoundRobin> weightMap = new ConcurrentHashMap<>();
    private final AtomicBoolean updateLock = new AtomicBoolean();
    @Override
    protected N doSelect(List<N> nodes, String ip) {
        int totalWeight = 0;
        long maxCurrent = Long.MIN_VALUE;
        long now = System.currentTimeMillis();
        N selectedNode = null;
        WeightedRoundRobin selectedWRR = null;
        for (N node : nodes) {
            int hashCode = node.hashCode();
            WeightedRoundRobin wrr = weightMap.get(hashCode);
            int weight = node.getWeight();
            if (weight < 0) weight = 0;
            if (wrr == null) {
                wrr = new WeightedRoundRobin();
                wrr.setWeight(weight);
                weightMap.putIfAbsent(hashCode, wrr);
                wrr = weightMap.get(hashCode);
            }
            if (weight != wrr.getWeight()) {
                wrr.setWeight(weight);
            }
            long current = wrr.increaseCurrent();
            wrr.setLastUpdate(now);
            if (current > maxCurrent) {
                maxCurrent = current;
                selectedNode = node;
                selectedWRR = wrr;
            }
            totalWeight += weight;
        }
        if (!updateLock.get() && nodes.size() != weightMap.size()) {
            if (updateLock.compareAndSet(false, true)) {
                try {
                    weightMap.entrySet().removeIf(item -> now - item.getValue().getLastUpdate() > RECYCLE_PERIOD);
                } finally {
                    updateLock.set(false);
                }
            }
        }
        if (selectedNode != null) {
            selectedWRR.decreaseCurrent(totalWeight);
            return selectedNode;
        }
        return nodes.get(0);
    }
    private static final class WeightedRoundRobin {
        private int weight;
        private final AtomicLong current = new AtomicLong(0);
        private long lastUpdate;
        public long increaseCurrent() { return current.addAndGet(weight); }
        public long decreaseCurrent(int total) { return current.addAndGet(-1L * total); }
        public int getWeight() { return weight; }
        public void setWeight(int weight) { this.weight = weight; current.set(0); }
        public void setLastUpdate(long lastUpdate) { this.lastUpdate = lastUpdate; }
        public long getLastUpdate() { return lastUpdate; }
    }
}

Least Active Algorithm

Selects the node with the smallest number of active (in‑flight) requests.

public class LeastActiveLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
    private final Random random = new Random();
    @Override
    protected N doSelect(List<N> nodes, String ip) {
        int length = nodes.size();
        int leastActive = -1;
        int leastCount = 0;
        int[] leastIndexs = new int[length];
        int totalWeight = 0;
        int firstWeight = 0;
        boolean sameWeight = true;
        for (int i = 0; i < length; i++) {
            N node = nodes.get(i);
            if (leastActive == -1 || node.getActive() < leastActive) {
                leastActive = node.getActive();
                leastCount = 1;
                leastIndexs[0] = i;
                totalWeight = node.getWeight();
                firstWeight = node.getWeight();
                sameWeight = true;
            } else if (node.getActive() == leastActive) {
                leastIndexs[leastCount++] = i;
                totalWeight += node.getWeight();
                if (sameWeight && i > 0 && node.getWeight() != firstWeight) {
                    sameWeight = false;
                }
            }
        }
        if (leastCount == 1) {
            return nodes.get(leastIndexs[0]);
        }
        if (!sameWeight && totalWeight > 0) {
            int offsetWeight = random.nextInt(totalWeight);
            for (int i = 0; i < leastCount; i++) {
                int idx = leastIndexs[i];
                offsetWeight -= nodes.get(idx).getWeight();
                if (offsetWeight <= 0) {
                    return nodes.get(idx);
                }
            }
        }
        return nodes.get(leastIndexs[random.nextInt(leastCount)]);
    }
}

Source‑IP Hash Algorithm

Hashes the client IP to consistently map a request to the same server (sticky session).

public class IpHashLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
    @Override
    protected N doSelect(List<N> nodes, String ip) {
        if (StrUtil.isBlank(ip)) {
            ip = "127.0.0.1";
        }
        int length = nodes.size();
        int index = hash(ip) % length;
        return nodes.get(index);
    }
    public int hash(String text) {
        return HashUtil.fnvHash(text);
    }
}

Consistent Hash Algorithm

Maps keys onto a hash ring; adding or removing a node only affects its immediate neighbors, providing stability for distributed caches and storage.

public class ConsistentHashLoadBalance<N extends Node> extends BaseLoadBalance<N> implements LoadBalance<N> {
    private final ConcurrentMap<String, ConsistentHashSelector<?>> selectors = new ConcurrentHashMap<>();
    @Override
    protected N doSelect(List<N> nodes, String ip) {
        Integer replicaNum = nodes.size() * 4;
        int identityHashCode = System.identityHashCode(nodes);
        ConsistentHashSelector<N> selector = (ConsistentHashSelector<N>) selectors.get(ip);
        if (selector == null || selector.identityHashCode != identityHashCode) {
            selectors.put(ip, new ConsistentHashSelector<>(nodes, identityHashCode, replicaNum));
            selector = (ConsistentHashSelector<N>) selectors.get(ip);
        }
        return selector.select(ip);
    }
    private static final class ConsistentHashSelector<N extends Node> {
        private final TreeMap<Long, N> virtualNodes;
        private final int identityHashCode;
        ConsistentHashSelector(List<N> nodes, int identityHashCode, Integer replicaNum) {
            this.virtualNodes = new TreeMap<>();
            this.identityHashCode = identityHashCode;
            if (replicaNum == null) replicaNum = 100;
            for (N node : nodes) {
                for (int i = 0; i < replicaNum / 4; i++) {
                    byte[] digest = md5(node.getUrl());
                    for (int j = 0; j < 4; j++) {
                        long m = hash(digest, j);
                        virtualNodes.put(m, node);
                    }
                }
            }
        }
        public N select(String key) {
            byte[] digest = md5(key);
            return selectForKey(hash(digest, 0));
        }
        private N selectForKey(long hash) {
            Map.Entry<Long, N> entry = virtualNodes.ceilingEntry(hash);
            if (entry == null) entry = virtualNodes.firstEntry();
            return entry.getValue();
        }
    }
    public static long hash(byte[] digest, int number) {
        return (((long) (digest[3 + number * 4] & 0xFF) << 24)
                | ((long) (digest[2 + number * 4] & 0xFF) << 16)
                | ((long) (digest[1 + number * 4] & 0xFF) << 8)
                | (digest[number * 4] & 0xFF)) & 0xFFFFFFFFL;
    }
    public static byte[] md5(String value) {
        MessageDigest md5;
        try {
            md5 = MessageDigest.getInstance("MD5");
        } catch (NoSuchAlgorithmException e) {
            throw new IllegalStateException(e.getMessage(), e);
        }
        md5.reset();
        byte[] bytes = value.getBytes(StandardCharsets.UTF_8);
        md5.update(bytes);
        return md5.digest();
    }
}

The article concludes with a list of reference materials, including videos, books, and online articles that discuss load‑balancing concepts and implementations.