Load balancer: thuật toán và khi nào dùng

1. Tổng quan

Khi hệ thống của bạn có nhiều instance phía sau, câu hỏi luôn là: request mới nên đi vào instance nào? Bài này giải thích các thuật toán load balancing thường gặp, cách chúng hoạt động qua code Java mô phỏng, và tiêu chí chọn thuật toán phù hợp cho từng loại workload. Đọc xong, bạn sẽ biết khi nào dùng Round Robin là đủ, khi nào cần Least Connections hay Consistent Hashing.

2. Load balancer là gì

Load balancer (LB) là thành phần đứng giữa client và một nhóm server (backend pool), có nhiệm vụ phân phối request sao cho:

Không server nào bị quá tải trong khi server khác rảnh.
Hệ thống chịu được việc một backend chết (failover).
Có thể scale ngang (thêm/bớt instance) mà client không biết.

LB có thể là phần mềm (Nginx, HAProxy, Envoy), phần cứng (F5), hoặc managed service (AWS ALB/NLB, GCP Load Balancer). Về vị trí hoạt động, LB chia thành hai loại chính:

Layer 4 (transport layer): định tuyến dựa trên IP/port, không đọc nội dung HTTP. Nhanh, ít overhead.
Layer 7 (application layer): đọc được header, path, cookie… nên định tuyến thông minh hơn (ví dụ route theo path /api/orders) nhưng tốn CPU hơn.

Lưu ý: Chọn sai layer là lỗi thiết kế phổ biến. Nếu bạn cần route theo URL path hay sticky session dựa trên cookie, Layer 4 không làm được — phải dùng Layer 7.

3. Các thuật toán load balancing phổ biến

3.1. Round Robin

Request lần lượt đi qua từng server theo thứ tự cố định, quay vòng lại từ đầu khi hết danh sách.

public class RoundRobinBalancer {

    private final List<String> servers;
    private final AtomicInteger index = new AtomicInteger(0);

    public RoundRobinBalancer(List<String> servers) {
        this.servers = servers;
    }

    public String nextServer() {
        int i = index.getAndIncrement() % servers.size();
        return servers.get(Math.abs(i));
    }
}

getAndIncrement tăng counter an toàn giữa nhiều thread, % servers.size() đưa chỉ số về trong khoảng hợp lệ. Với 3 server [A, B, C], chuỗi gọi nextServer() liên tiếp cho ra:

A, B, C, A, B, C, ...

Round Robin đơn giản, không cần biết trạng thái server. Nhược điểm: nếu các request có độ nặng khác nhau (một request xử lý 1ms, request khác 500ms), server xử lý request nặng dễ bị dồn tải hơn theo thời gian.

3.2. Weighted Round Robin

Mỗi server có một “trọng số” phản ánh năng lực xử lý (CPU, RAM). Server mạnh hơn nhận nhiều request hơn.

public class WeightedRoundRobinBalancer {

    private record WeightedServer(String name, int weight) {}

    private final List<WeightedServer> servers;
    private int currentIndex = -1;
    private int currentWeight = 0;

    public WeightedRoundRobinBalancer(Map<String, Integer> weightedServers) {
        this.servers = weightedServers.entrySet().stream()
            .map(e -> new WeightedServer(e.getKey(), e.getValue()))
            .toList();
    }

    public synchronized String nextServer() {
        int maxWeight = servers.stream().mapToInt(WeightedServer::weight).max().orElse(1);
        int gcdWeight = servers.stream().mapToInt(WeightedServer::weight)
            .reduce((a, b) -> java.math.BigInteger.valueOf(a).gcd(java.math.BigInteger.valueOf(b)).intValue())
            .orElse(1);

        while (true) {
            currentIndex = (currentIndex + 1) % servers.size();
            if (currentIndex == 0) {
                currentWeight -= gcdWeight;
                if (currentWeight <= 0) {
                    currentWeight = maxWeight;
                }
            }
            if (servers.get(currentIndex).weight() >= currentWeight) {
                return servers.get(currentIndex).name();
            }
        }
    }
}

Đây là thuật toán “smooth weighted round robin” dùng trong Nginx: server có weight cao được chọn thường xuyên hơn nhưng vẫn rải đều, không dồn liên tiếp. Với cấu hình {A: 5, B: 1, C: 1}, chuỗi chọn gần đúng là:

A, A, B, A, C, A, A

3.3. Least Connections

Chọn server đang có ít connection đang xử lý nhất. Phù hợp khi thời gian xử lý request chênh lệch lớn.

public class LeastConnectionsBalancer {

    private final Map<String, AtomicInteger> activeConnections = new ConcurrentHashMap<>();

    public LeastConnectionsBalancer(List<String> servers) {
        servers.forEach(s -> activeConnections.put(s, new AtomicInteger(0)));
    }

    public String nextServer() {
        return activeConnections.entrySet().stream()
            .min(Comparator.comparingInt(e -> e.getValue().get()))
            .map(Map.Entry::getKey)
            .orElseThrow();
    }

    public void onRequestStart(String server) {
        activeConnections.get(server).incrementAndGet();
    }

    public void onRequestEnd(String server) {
        activeConnections.get(server).decrementAndGet();
    }
}

nextServer() quét map và lấy server có số connection nhỏ nhất. onRequestStart/onRequestEnd phải được gọi đúng cặp (ví dụ trong try/finally) để số liệu không bị lệch.

Lưu ý: Least Connections cần LB theo dõi trạng thái (stateful) — tốn thêm chi phí đồng bộ nếu bạn có nhiều LB instance chạy song song. Round Robin thì stateless hoàn toàn.

3.4. Least Response Time

Biến thể của Least Connections, chọn server có (số connection × thời gian phản hồi trung bình) thấp nhất. Phức tạp hơn nhưng phản ánh tải thực tế chính xác hơn vì tính cả độ trễ xử lý.

public record ServerStats(String name, int activeConnections, double avgResponseTimeMs) {
    double score() {
        return activeConnections * avgResponseTimeMs;
    }
}

public String pickFastest(List<ServerStats> stats) {
    return stats.stream()
        .min(Comparator.comparingDouble(ServerStats::score))
        .map(ServerStats::name)
        .orElseThrow();
}

avgResponseTimeMs thường được tính bằng exponential moving average, cập nhật sau mỗi response trả về. Thuật toán này tốt cho hệ thống có mix API nhanh (cache lookup) và API chậm (báo cáo, tính toán nặng).

3.5. IP Hash / Consistent Hashing

Dùng khi cần sticky session — cùng một client luôn được route tới cùng một server (ví dụ server giữ session in-memory, hoặc cache local).

public class ConsistentHashBalancer {

    private final SortedMap<Long, String> ring = new TreeMap<>();
    private static final int VIRTUAL_NODES = 100;

    public ConsistentHashBalancer(List<String> servers) {
        for (String server : servers) {
            for (int i = 0; i < VIRTUAL_NODES; i++) {
                ring.put(hash(server + "#" + i), server);
            }
        }
    }

    public String serverFor(String clientKey) {
        long hash = hash(clientKey);
        SortedMap<Long, String> tail = ring.tailMap(hash);
        Long nodeKey = tail.isEmpty() ? ring.firstKey() : tail.firstKey();
        return ring.get(nodeKey);
    }

    private long hash(String input) {
        return input.hashCode() & 0xFFFFFFFFL;
    }
}

Mỗi server được rải thành nhiều “virtual node” trên một vòng hash (ring) để phân phối đều hơn. serverFor tìm điểm gần nhất trên vòng theo chiều kim đồng hồ ứng với key của client (thường là IP hoặc user ID). Ưu điểm lớn: khi thêm/bớt một server, chỉ một phần nhỏ key bị remap — không xáo trộn toàn bộ như hash thường (hash(key) % n).

Test nhanh để xác nhận cùng key luôn ra cùng server:

@Test
void sameClientKey_alwaysRoutesToSameServer() {
    ConsistentHashBalancer balancer =
        new ConsistentHashBalancer(List.of("server-1", "server-2", "server-3"));

    String first = balancer.serverFor("user-42");
    String second = balancer.serverFor("user-42");

    assertThat(first).isEqualTo(second);
}

3.6. Random và Power of Two Choices

Random đơn giản chọn ngẫu nhiên — hiệu quả gần Round Robin với số lượng request lớn nhưng không cần giữ state. Power of Two Choices (P2C) cải tiến: chọn ngẫu nhiên 2 server, rồi lấy server có ít connection hơn trong 2 server đó. Thuật toán này được chứng minh giảm đáng kể “tail latency” so với random thuần, mà không cần theo dõi toàn bộ cluster như Least Connections.

public String pickWithPowerOfTwo(List<String> servers, Map<String, Integer> loadMap, Random random) {
    String candidate1 = servers.get(random.nextInt(servers.size()));
    String candidate2 = servers.get(random.nextInt(servers.size()));
    return loadMap.get(candidate1) <= loadMap.get(candidate2) ? candidate1 : candidate2;
}

4. Health check và failover

Thuật toán chọn server chỉ có ý nghĩa nếu LB biết server nào đang “sống”. Health check thường có hai kiểu:

Active check: LB tự gửi request định kỳ tới endpoint như /health.
Passive check: LB đánh dấu server “down” khi liên tiếp nhận lỗi/timeout từ request thật.

Ví dụ cấu hình active health check với Nginx:

upstream backend_pool {
  server 10.0.0.1:8080 max_fails=3 fail_timeout=30s;
  server 10.0.0.2:8080 max_fails=3 fail_timeout=30s;
}

max_fails=3 nghĩa là sau 3 lần thất bại liên tiếp, server bị loại khỏi pool trong fail_timeout giây rồi được thử lại. Không có health check, LB vẫn gửi request vào server đã chết cho đến khi client timeout — trải nghiệm rất tệ.

5. Bảng so sánh: khi nào dùng thuật toán nào

Thuật toán	Khi nào phù hợp	Khi nào tránh
Round Robin	Server đồng nhất, request có độ nặng tương đương (REST API đơn giản)	Server khác cấu hình, request độ nặng khác nhau
Weighted Round Robin	Cluster có server với công suất khác nhau (migrate dần sang instance mới)	Cần phản ứng theo tải thực tế tức thời
Least Connections	Request có thời gian xử lý biến động lớn (upload file, long-polling)	Hệ thống nhiều LB instance, chi phí đồng bộ state cao
Least Response Time	Mix API nhanh/chậm, cần tối ưu latency tổng thể	Hệ thống nhỏ, không đủ dữ liệu đo response time ổn định
IP Hash / Consistent Hashing	Cần sticky session, cache locality, sharding theo client	Server thường xuyên scale lên/xuống với tốc độ cao (dù ảnh hưởng remap đã giảm, vẫn có overhead)
Random / P2C	Hệ thống rất lớn, muốn tránh overhead theo dõi state tập trung	Cần đảm bảo phân phối tuyệt đối đều trong thời gian ngắn

6. Lỗi hay gặp khi thiết kế load balancing

Dùng Round Robin cho workload không đồng nhất: một vài server nhận toàn request nặng trong khi server khác rảnh — gây lệch tải âm thầm, khó phát hiện qua monitoring tổng (CPU trung bình vẫn “bình thường”).
Sticky session bằng IP Hash khi client ở sau NAT/proxy chung: nhiều client thực tế bị gộp thành một IP, dẫn đến một server nhận tải lớn bất thường. Nên dùng cookie-based sticky session ở Layer 7 thay vì IP Hash trong trường hợp này.
Không có health check hoặc health check sai endpoint: /health trả 200 OK nhưng không kiểm tra kết nối tới database — server “sống” theo LB nhưng thực chất không xử lý được request.
Bỏ qua connection draining khi scale-in: tắt server ngay lập tức làm rớt các request đang xử lý. Cần đợi connection hiện tại hoàn tất (graceful shutdown) trước khi loại server khỏi pool.
Single point of failure ở chính LB: nếu chỉ có một LB instance, nó trở thành điểm chết của toàn hệ thống. Cần ít nhất 2 LB instance với DNS failover hoặc virtual IP (keepalived).

7. Kết luận

Load balancer không chỉ là “cái chia request cho đều” — chọn đúng thuật toán phụ thuộc vào đặc tính workload: đồng nhất hay không, cần sticky session hay không, hệ thống có đủ khả năng theo dõi state tập trung hay không. Round Robin và Weighted Round Robin phù hợp cho phần lớn trường hợp đơn giản; Least Connections và Least Response Time xử lý tốt workload biến động; Consistent Hashing giải quyết bài toán sticky session và sharding một cách bền vững khi cluster thay đổi. Quan trọng hơn thuật toán, health check và failover đúng cách mới là thứ quyết định độ tin cậy thực sự của hệ thống.