[Lý Thuyết] Các thuật toán Load Balancing

root · 04/08/2015

Các thuật toán cân bằng tải

1. Round Robin

Là thuật toán luân chuẩn vòng, các máy chủ sẽ được xem ngang hàng và sắp xếp theo một vòng quay. Các truy vấn dịch vụ sẽ lần lượt được gửi tới các máy chủ theo thứ tự sắp xếp
Ví dụ:
- Cấu hình một cụm Cluster bao gồm 03 máy chủ: A, B, C.
- Yêu cầu dịch vụ thứ nhất sẽ được gửi đến máy chủ A.
- Yêu cầu dịch vụ thứ hai sẽ được gửi đến máy chủ B.
- Yêu cầu dịch vụ thứ ba sẽ được gửi đến máy chủ C.
- …
- Yêu cầu dịch vụ thứ tư sẽ lại được gửi cho máy chủ A….

Nhược điểm: khi có 2 yêu cầu liên tục từ phía người dùng sẽ có thể được gửi vào 2 server khác nhau. Điều này làm tốn thời gian tạo thêm kết nối với server thứ 2 trong khi đó server thứ nhất cũng có thể trả lời được thông tin mà người dùng đang cần. Để giải quyết điều này, round robin thường được cài đặt cùng với các phương pháp duy trì session như sử dụng cookie.

2. Thuật toán Weighted Round Robin

Tương tự như kỹ thuật Round Robin nhưng WRR còn có khả năng xử lý theo cấu hình của từng server đích. Mỗi máy chủ được đánh giá bằng một số nguyên (giá trị trọng số Weight – mặc định giá trị là 1). Một server có khả năng xử lý gấp đôi server khác sẽ được đánh số lớn hơn và nhận được số request gấp đôi từ bộ cân bằng tải
Ví dụ:
- Cấu hình một cụm Cluster bao gồm 03 máy chủ: A, B, C. với khả năng xử lý của máy A lơn hơn máy B và lớn hơn máy C. Chúng ta thiết sẽ lập trọng số weight cho các server A, B, C lần lượt là 4,3,2.
- Thứ tự điều phối luân phiên các request sẽ là AABABCABC
- Yêu cầu dịch vụ thứ nhất sẽ được gửi đến máy chủ A.
- Yêu cầu dịch vụ thứ hai sẽ được gửi đến máy chủ A.
- Yêu cầu dịch vụ thứ ba sẽ được gửi đến máy chủ B.
- Yêu cầu dịch vụ thứ tư sẽ lại được gửi cho máy chủ A….
- …

Nhược điểm:
- Sử dụng thuật toán này có thể dẫn đến việc mất cân bằng tải động nếu như tải của các request liên tục thay đổi trong một khoảng thời gian rộng
- Ví dụ các yêu cầu xem video hoặc tải các file có dung lượng lớn xen kẽ với các yêu cầu đọc thông tin,…). Như vậy nó sẽ dồn request tới 1 server có trọng số Weight cao và làm mất khả năng load balancing.
- Trong một khoảng thời gian ngắn, hoàn toàn có khả năng phần lớn các yêu cầu có tải cao sẽ được chuyển hướng đến một server.

3. Thuật toán Dynamic Round Robin (DRR)

Thuật toán DRR hoạt động gần giống với thuật toán WRR, điểm khác biệt là trọng số ở đây dựa trên sự kiểm tra server một cách liên tục, do đó trọng số liên tục thay đổi.
Đây là thuật toán động (các thuật toán ở trên là thuật toán tĩnh), việc chọn server sẽ dựa trên rất nhiều khía cạnh trong việc phân tích hiệu năng của server trên thời gia thực (ví dụ: số kết nối hiện đang có trên các server hoặc server trả lời nhanh nhất, …).
Thuật toán này thường không được cài đặt trong các bộ cân bằng tài đơn giản, nó thường được sử dụng trong các sản phẩm cân bằng tải của F5 Network.

4. Thuật toán Fastest.

Đây là thuật toán dựa trên tính toán thời gian đáp ứng của mỗi server (response time), thuật toán này sẽ chọn server nào có thời gian đáp ứng nhanh nhất. Thời gian đáp ứng được xác định bởi khoảng thời gian giữa thời điểm gửi một gói tin đến server và thời điểm nhận được gói tin trả lời.
Việc gửi và nhận này sẽ được bộ cân bằng tải đảm nhiệm, dựa trên thời gian đáp ứng, bộ cân bằng tải sẽ biết chuyển yêu cầu tiếp theo đến server nào.

Ví dụ:
- Khi truy cập vào trang youtobe.com, nếu IP của người dùng đến từ Việt Nam, yêu cầu sẽ được chuyển vào server Việt Nam xử lý. Điều này sẽ tiết kiệm khá lớn cho lượng băng thông quốc tế và cải thiện tốc độ đường truyền.
Thuật toán fastest thường được dùng khi các server ở các vị trí địa lý khác nhau. Như vậy người dùng ở gần server nào thì thời gian đáp ứng của server đó sẽ nhanh nhất, và server đó sẽ được chọn để phục vụ.

5. Thuật toán Lest Connection (LC)

Các request sẽ được chuyển vào server có ít kết nối nhất trong hệ thống. Thuật toán này được coi như thuật toán động, vì nó phải đếm số kết nối đang hoạt động của server.

Với một hệ thống có các server gần giống nhau về cấu hình, LC có khả năng hoạt động tốt ngay cả khi tải của các kết nối biến thiên trong một khoảng lớn. Do đó nếu sử dụng RC sẽ khắc phục được nhược điểm của RR.

Nhìn bên ngoài có vẻ như LC hoạt động tốt khi các server có cấu hình biến thiên khác nhau, tuy nhiên trên thực tế đều đó là không đúng.
Nhược điểm:
- Trạng thái TIMVE_WAIT của TCP thường được đặt là 2 phút, trong 2 phút đó có một server bận rộn có thể nhận hàng chục ngàn kết nối liên tục.
- Giả sử server A có khả năng xử lý gấp đôi server B, server A đang xử lý hàng ngàn những yêu cầu và giữ những yêu cầu này trong trạng thái TIME_WAIT của TCP. Trong khi đó server B cũng phải xử lý như server A nhưng vì cấu hình server B thấp hơn nên sẽ chậm hơn rất nhiều. Như vậy thuật toán LC hoạt động không tốt khi các server có cấu hình khác nhau.