Load Balancing khó hay dễ
load balancer
3
White

huydx viết ngày 02/05/2018

Hôm nay tôi có xem một clip khá thú vị nói về Load Balancing

Clip thuộc hội thảo ScaleConf, được phát biểu bởi Tyler McMullen, CTO của Fastly (một startup làm về CDN).
Trong bài phát biểu thì Tyler có đề cập đến nhiều algorithm cũng như kiến thức về Load Balancing mà tôi thấy rất thú vị.

Load Balancing là gì?

Đúng như nghĩa tiếng Anh dịch thẳng tuồn tuột, Load Balancing có nghĩa là "cân bằng tải". Một kịch bản thường được thấy nhất chính là việc bạn có một web service, được phục vụ bởi N servers cho M requests đến từ người dùng. Load Balancing chính là việc làm thế nào để chia M requests đó cho N servers một cách "hợp lý" nhất.

Việc chia tải đó thông thường sẽ được thực hiện thông qua một server nằm giữa, mà người ta hay gọi là proxy. Một số proxy middleware hay được biết đến, có thể kể đến Nginx, HAProxy (phần mềm) hay là F5 BigIP (phần cứng).

(hình vẽ được lấy từ http://vmgate.com/)

Gần đây có xu hướng mới là thay vì cần một proxy server (vì thực tế proxy server có thể là Single Point of Failure), một số framework có hỗ trợ việc client side load balancing, tức là việc chia tải sẽ được thực hiện ở phía client (có thể là một service khác trong microservice, hay thậm chí là web browser).

Tuy nhiên việc được đặt ở đâu không quan trọng, cái quan trọng hơn là việc "thế nào" (How)

Tại sao thuật toán Load Balancing quan trọng

Trong bài talk, thì Tyler có đề cập đến một sự thật khá hiển nhiên, nhưng lại rất thú vị

Most of your users requests will experience long tail latency
The probability of all N resource requests in a page avoiding the 99th percentile is (0.99^N)

Giải thích kĩ phần này một chút, latency của một web service trong thực tế sẽ được mô tả thông qua một phân phối xác xuất chuẩn theo hàm log. (Log-Normal Distribution). Có thể bạn không nhớ nhiều lắm về xác xuất (tôi cũng vậy), nhưng về ý tưởng thì trong latency của N request , sẽ có N1 request (N1 ~ N) kết thúc với latency "vừa đủ", tuy nhiên N2 (=N-N1) requests còn lại sẽ kết thúc với latency "rất chậm".

Nói một cách khác, phân phối latency trong thực tế sẽ có dạng "long tail", giống như dưới đây

(hình được lấy từ stackexchange):

Với quan sát rằng latency là Long Tail, như vậy có nghĩa 99th percentile latency của webserver của bạn là rất tốt, thì 1% còn lại sẽ tồi ở mức không thể chấp nhận được. (Note: bạn nào chưa biết percentile là gì thì có thể xem link https://www.quora.com/What-is-p99-latency )

Theo định nghĩa về percentile thì xác xuất để 1 request rơi vào 99th percentile "tốt" sẽ là 99%.
Vậy xác suất để N request rơi vào vùng "tốt" này sẽ là 99% ^ N.
Vậy nếu N là 69 requests thì xác suất rơi vào vùng tốt chỉ ~ 50%, vậy tức là còn 50% sẽ có khả năng rơi vào vùng "rất tồi".

Điều này có nghĩa là, hãy giả sử bạn là amazon, để gọi ra trang home page của amazon, bạn phải gọi tầm 500 API khác nhau (tính cả static request). vậy xác xuất rơi vào vùng tốt của bạn chỉ là ... 0.6%. Hay nói một cách khác, nếu 99th percentile của amazon là 10s, thì khả năng một khách hàng phải chịu latency 10s khi họ vào thăm amazon.com sẽ là ... 99.4%.

Vậy việc giải thích dài dòng về latency cũng như long tail ở trên liên quan quái gì đến Load Balancing? Thực ra nó chỉ nhằm để cho một kết luân duy nhất: Một thuật toán Load Balancing tốt phải giúp GIẢM NTH PERCENTILE LATENCY (N có thể là 99, hay 99.9999, tuỳ vào tiêu chuẩn của service của bạn. N càng lớn, số lượng user phải chịu đựng high latency càng thấp). Vậy làm sao để giảm Nth Percentile Latency thông qua Load Balacing?

Liệu có tồn tại một thuật toán Load Balancing hoàn hảo?

Như tôi vừa nói ở trên, một thuật toán oad balancing tốt phải nhằm giảm latency. Vậy khi nào thì latency sẽ bị tăng? Hãy tưởng tượng rằng bạn có 1 node (web server) bị quá tải vì một lý do nào đó (bad hardware, spike..) khiến nó xử lý request cực chậm. Như vậy có thể dễ dàng thấy rằng, càng nhiều công việc được đưa cho node đó bao nhiêu, Nth Percentile Latency sẽ càng tăng lên.

Hãy đi từ một thuật toán đơn giản nhất cho LB: Random.
Thuật toán này có thể mô tả dễ dàng bằng đoạn code dưới đây:

public Endpoint select() {
    List<endpoint> endpoints = endpointGroup.endpoints(); 
    return endpoints.get(new Random().nextInt(endpoints.length));
}

Random LB không có gì là tồi. Nó đơn giản, không có edge case, có cùng tính chất thậm chí ngay cả khi bạn có nhiều tầng LB (multi-tier). Tuy nhiên có một điểm tồi chính là việc, nếu coi hàm random của bạn đủ tốt để nó phân tán đều (uniform distributed) vào từng node, thì nếu có một node rơi vào trạng thái xử lý chậm, thì nó vẫn phải xử lý số lượng request ngang bằng với các node khoẻ mạnh, và điều đó hiển nhiên sẽ làm tăng Nth Percentile Latency.

Trong thực tế thì thay vì random, người ta hay sử dụng thuật toán Round robin hơn. Round robin đơn thuần lần lượt chọn các node kế tiếp nhau, và quay vòng lại khi hết lựa chọn.

private final AtomicInteger sequence = new AtomicInteger(); 

public Endpoint select() {
    List<endpoint> endpoints = endpointGroup.endpoints(); 
    int currentSequence = sequence.getAndIncrement(); 
    return endpoints.get(Math.abs(currentSequence % endpoints.size())); 
} 

Tuy nhiên về bản chất thì Round Robin cũng có các điểm cộng và trừ tương tự như Random, vậy nên RR vẫn chưa phải là lựa chọn tốt nhất cho chúng ta. Round Robin trong thực tế có thể cải thiện bằng cách gắn thêm "trọng lượng" (weight) cho từng node, khiến cho chúng ta có thể qui định được là một node có thể chịu được nhiều tải hơn các node khác bằng cách gắn cho nó weight cao hơn.

Thuật toán Weighted Round Robin có thể được mô tả thông qua đoạn code dưới đây:

private final AtomicInteger sequence = new AtomicInteger();

public Endpoint select() { 
    int currentSequence = sequence.getAndIncrement(); 
    return endpointsAndWeights.selectEndpoint(currentSequence); 
} 

Endpoint selectEndpoint(int currentSequence) { 
    int[] weights = endpoints.stream()
                             .mapToInt(Endpoint::weight) 
                             .toArray(); 
    int mod = currentSequence % totalWeight;
    for (int i = 0; i  0) { 
                return endpoints.get(j); 
            } 
            if (weights[j] > 0) { 
                weights[j]--; 
                mod--; 
            } 
        } 
    } 
    return endpoints.get(Math.abs(currentSequence % endpoints.size()));
} 

Weighted Round Robin, mặc dù giải quyết được bài toán khi có một node yếu hơn các node khác, bằng cách phân cho nó weight thấp hơn. Tuy nhiên điểm bất lợi của thuật toán này lại là không thực hiện được tại real time. Thông thường weight sẽ được quyết định trước, và nếu muốn thay đổi weight thì cần phải restart lại LB server, và cần sự can thiệp của con người vào việc quyết định weight. Nói một cách khác, Weighted Round Robin sẽ không giải quyết được trường hợp khi mà một node bị spike bất ngờ (do logic, do network failure/spike, do disk failure/spike...), mà trong thực tế trường hợp này sẽ rất dễ xảy ra.

Cả 2 thuật toán Random lẫn RoundRobin đều thuộc về dạng "tĩnh" (static) khi mà việc phân bổ tải không thể thay đổi tuỳ theo trạng thái của nodes. Vậy có một cách nào thông minh hơn không nhỉ.

Có một thuật toán nổi tiếng mà có thể thay đổi theo trạng thái node gọi là JSQ (Join Shortest Queue). Ý tưởng của JSQ rất đơn giản

Under JSQ, an incoming request is routed to the server with the least number of unfinished requests.

Hay có nghĩa là

Request sẽ được phân cho node mà có số lượng request chưa hoàn thành ít nhất

Paper phân tích về JSQ dưới góc nhìn của xác suất thông kê bạn có thể tham khảo tại: http://www.cs.cmu.edu/~harchol/Papers/peva07.pdf . Để cài đặt JSQ thì LB server cần một cách để lưu trạng thái về việc: bao nhiêu request mà từng node (backend server), vẫn chưa hoàn thành (book-keeping mechanism). Ý tưởng của JSQ có thể được hiểu thông qua đoạn code mô tả dưới đây (đoạn code dưới không quan tâm đến concurrency cũng như performance)

private final Map<Endpoint, Integer> queueLengthBookKeeping;

public Endpoint select() { 
    // find shortest queue
    int min = Integer.MAX_VALUE;
    Endpoint select = null;
    for (Entry<Endpoint, Integer> entry : queueLengthBookKeeping) {
        Integer val = entry.getValue();
        if (val < min) {
            min = val;
            select = entry.getKey();
        }
    }
    return select;
}

//Serving function
try {
    Integer old = queueLengthBookKeeping.get(endpoint);
    queueLengthBookKeeping.put(endpoint, old+1);
    request(req, endpoint);
} catch (Exception ex) {
    Integer old = queueLengthBookKeeping.get(endpoint);
    queueLengthBookKeeping.put(endpoint, old-1);
}l

Bạn có thể thấy là cài đặt của JSQ nhìn qua thì thấy là rất đơn giản. Tuy nhiên để đạt được hiệu năng tốt thì có rất nhiều điểm cần cải thiện. Có một cách để thay vì phải lưu book-keeping bên trong memory và tăng/giảm mỗi khi request đến, thì chúng ta có thể đồng bộ (sync) giữa Load Balancer và các node tại mỗi N giây hay N phút. Tuy nhiên cách thức đồng bộ thế nào cho hợp lý cũng không phải đơn giản. Tuy nhiên việc đồng bộ khiến JSQ gặp một vấn đề nữa gọi là "herd effect", khi mà dữ liệu đồng bộ có thể đã cũ, khiến cho request có thể được phân bổ đến nhầm node. Mặc dù gặp nhiều khó khăn nhưng JSQ cũng đã và đang được sử dụng trong thực tế khá nhiều tại Cisco Local Director, IBM Network Dispatcher, Microsoft Sharepoint hay là F5 Labs BIG/IP (trong đó BIG/IP là một trong những Hardware Load Balancer với hiệu năng tốt nhất thế giới).

Một hướng phát triển nữa của Load Balancing Algorithm là dựa vào việc các node sẽ thông báo đến cho Load Balancer về trạng thái hiện tại. Một thuật toán khá nổi tiếng đi theo hướng này là JIQ (Job Idle Queue) được phát triển bởi Microsoft. Bạn có thể tham khảo paper tại đây. Ý tưởng thuật toán này là

We propose a class of algorithms called Join-Idle-Queue (JIQ) for large-scale load balancing with distributed dispatchers. The central idea is to decouple discovery of lightly loaded servers from job assignment. The basic version involves idle processors informing dispatchers at the time of their idleness, without interfering with job arrivals. This removes the load balancing work from the critical path of request processing.

JIQ giả định môi trường là phân tán (nhiều Load Balancer cùng thực hiện việc phân tải), do đó ngoài việc tìm ra một cách thức tốt nhất để node có thể thông báo cho LB là "tao đang rỗi nè", thì JIQ cũng phải giải quyết bài toán là "thông báo cho ai". Bởi nếu thông báo cho toàn bộ LB thì sẽ dẫn đến node đang rỗi rãi sẽ bị bom một lượng request mà nó không giải quyết nổi. Làm thế nào đẻ JIQ giải quyết vấn đề đó thì ... bạn đọc paper nha

Kết luận

Kết luận là ... Load Balancing rất khó. Cũng như title của bài talk của Tyller : Load Balancing is Impossible.
Một vài điểm khiến nó khó mà chúng ta có thể rút ra là:

  • Môi trường phân tán (Multi Layer Load Balancing)
  • Lượng request lớn (High Load)
  • Trạng thái luôn luôn thay đổi (Dynamic State)

Vì vậy nếu bạn muốn có một thuật toán Load Balancing hoàn hảo, thì có thể khẳng định là nó vẫn chưa tồn tại. Hy vọng qua bài viết bạn hiểu được một việc đơn giản như là Load Balancing khi đặt trong thực tế sẽ khó đến thế nào.

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

huydx

116 bài viết.
960 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
153 14
Introduction (Link) là một cuộc thi ở Nhật, và cũng chỉ có riêng ở Nhật. Đây là một cuộc thi khá đặc trưng bởi sự thú vị của cách thi của nó, những...
huydx viết gần 2 năm trước
153 14
White
126 15
Happy programmer là gì nhỉ, chắc ai đọc xong title của bài post này cũng không hiểu ý mình định nói đến là gì :D. Đầu tiên với cá nhân mình thì hap...
huydx viết hơn 3 năm trước
126 15
White
98 10
(Ảnh) Mở đầu Chắc nhiều bạn đã nghe đến khái niệm oauth. Về cơ bản thì oauth là một phương thức chứng thực, mà nhờ đó một web service hay một ap...
huydx viết 3 năm trước
98 10
Bài viết liên quan
White
30 13
Vẫn theo khung sườn đã định trước từ phần 1, trong phần này tôi sẽ giới thiệu cách cấu hình nginx để thực hiện vai trò của một load balancer. Trư...
manhdung viết 3 năm trước
30 13
White
53 9
Bài viết này xin đề cập tới Nginx Load balancing 1. Thế nào Load Balancing Load Balancing hay còn gọi là Cân bằng tải ?? một kỹ thuật thường đư...
Cùi Bắp viết gần 2 năm trước
53 9
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
116 bài viết.
960 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!