Cloudflare tiết kiệm thêm 100TB RAM nhờ toán học và Rust

Cloudflare vừa công bố một tối ưu hóa ấn tượng: giảm hơn 100TB RAM tiêu thụ trên toàn hệ thống nhờ cải tiến thuật toán băm nhất quán (consistent hashing) trong thư viện pingora-ketama. Thành tựu này có được nhờ kết hợp phân tích toán học xác suất với những thay đổi tinh tế trong cách lưu trữ dữ liệu bằng ngôn ngữ Rust.

Bài toán: Khi cân bằng tải ngốn quá nhiều bộ nhớ

Cloudflare vận hành hàng nghìn máy chủ trên toàn thế giới với hàng petabyte RAM và hàng triệu lõi CPU. Ở quy mô đó, ngay cả những cải thiện 1% cũng có ý nghĩa lớn. Câu chuyện bắt đầu từ một ticket do kỹ sư Ivan phát hiện: dịch vụ Pingora Backend Router (PBR) — hệ thống cân bằng tải nội bộ của Cloudflare — đang sử dụng bộ nhớ vượt xa mức mong đợi, đặc biệt ở các cấu trúc liên quan đến pingora-ketama.

Mức tiêu thụ bộ nhớ "quá đáng" này có thời điểm lên tới 6GB ở một số trường hợp. Để hiểu nguyên nhân, cần nắm rõ cách hoạt động của thuật toán băm nhất quán.

Băm nhất quán hoạt động như thế nào?

Băm nhất quán (consistent hashing) là phương pháp phân phối tác vụ lên nhiều máy chủ sao cho khi thêm hoặc bớt máy chủ, số lượng tác vụ phải di chuyển là tối thiểu. Cloudflare dùng nó để định tuyến các yêu cầu có thể lưu cache (cacheable request) tới máy chủ dựa trên URL, đảm bảo mỗi tệp chỉ được lưu một bản trong mỗi trung tâm dữ liệu.

Ý tưởng cốt lõi: hàm băm nhận đầu vào tùy ý nhưng trả về một số nguyên không dấu (32, 64 hoặc 128-bit). Ta hình dung không gian đầu ra này như một trục số. Mỗi máy chủ được đặt trên trục số dựa trên hash của địa chỉ IP, mỗi tác vụ được đặt dựa trên hash của cache key. Việc gán tác vụ cho máy chủ chỉ đơn giản là tìm máy chủ đầu tiên nằm bên trái của tác vụ đó trên trục số.

Minh họa băm nhất quán trên trục số

Vấn đề nằm ở chỗ: vì hash về bản chất là số ngẫu nhiên, kích thước vùng phụ trách của mỗi máy chủ sẽ chênh lệch nhau. Một máy chủ có thể phải xử lý gấp đôi lượng yêu cầu so với máy khác, hoặc gần như không làm gì cả.

Toán học đứng sau vấn đề

Với N máy chủ, giá trị kỳ vọng (expected value) và độ lệch chuẩn (standard deviation) của tỷ lệ vùng phụ trách là:

$$\text{Exp} = \frac{1}{N}, \quad \text{SD} = \frac{1}{N}\sqrt{\frac{N-1}{N+1}}$$

Hệ số biến thiên (coefficient of variation) — thước đo mức sai lệch so với mục tiêu — được tính bằng:

$$\text{CV} = \frac{\text{SD}}{\text{Exp}} = \sqrt{\frac{N-1}{N+1}}$$

Với N = 100, CV xấp xỉ 99%, nghĩa là một số máy chủ có thể phải làm việc nặng gấp đôi so với mức lý tưởng.

Giải pháp quen thuộc là thêm nhiều hash cho mỗi máy chủ. NGINX mặc định dùng 160 hash mỗi máy chủ, và Pingora cũng vậy. Với 100 máy chủ, CV giảm từ khoảng 99% xuống còn khoảng 8%.

Cloudflare còn dùng thuật toán ketama để gán trọng số cho máy chủ dựa trên dung lượng ổ đĩa, giúp máy chủ có nhiều dung lượng nhận nhiều yêu cầu hơn. Nhưng khi phải xử lý nhiều tổ hợp tính năng khác nhau (yêu cầu tuân thủ, tính năng cache khác nhau), số lượng vòng băm riêng biệt tăng theo cấp số nhân — lên tới hàng chục vòng. Đây chính là nguyên nhân gây ngốn RAM.

Cải tiến lưu trữ: Từ 8 byte xuống 6 byte

Một bước đột phá đến từ kỹ sư Zaidoon, người nhận ra rằng cấu trúc lưu hash hiện tại đang lãng phí bộ nhớ:

struct Point {
    hash: u32,
    index: u32,
}

Cấu trúc này chiếm 8 byte — 4 byte cho hash (không thể tránh) và 4 byte cho chỉ mục máy chủ. Vì PBR khó có thể cần điều phối quá 65.000 máy chủ cùng lúc, chỉ mục 32-bit là thừa thãi. Chỉ cần 16-bit là đủ.

Tuy nhiên, Rust có quy tắc căn chỉnh bộ nhớ (alignment) khiến việc giảm kích thước trường không tự động giảm kích thước struct. Giải pháp an toàn là lưu hash và index dưới dạng mảng byte thô với các phương thức truy cập:

struct Point([u8; 6]);

impl Point {
    fn hash(&self) -> u32 {
        u32::from_ne_bytes(self.0[0..4].try_into().unwrap())
    }
    fn index(&self) -> u16 {
        u16::from_ne_bytes(self.0[4..6].try_into().unwrap())
    }
}

Thay đổi tưởng chừng đơn giản này giúp giảm 25% bộ nhớ dùng cho băm nhất quán.

Minh họa cải tiến lưu trữ

Giảm số lượng hash: Khi "nhiều hơn" không còn tốt

Cloudflare đã tự mình suy ra công thức chính xác cho độ lệch chuẩn với k hash mỗi máy chủ:

$$\text{CV}_k = \sqrt{\frac{N-1}{N \cdot k + 1}}$$

Khi vẽ đồ thị CV theo k, họ nhận ra mỗi bước giảm sai số đòi hỏi tăng gần như một bậc độ lớn số hash. Với trọng số m_w = 625, số hash mỗi máy chủ lên tới 100.000. Nhưng 90.000 hash cuối cùng chỉ mang lại mức giảm sai số vỏn vẹn 0,7%.

Tệ hơn nữa, với hash 32-bit, xác suất va chạm (collision) tăng nhanh chóng theo nghịch lý ngày sinh nhật (birthday paradox). Ở các trung tâm dữ liệu có 2048 máy chủ, sai số thực tế bắt đầu tăng khi số hash vượt ngưỡng 10.000 đến 100.000 mỗi máy chủ.

Đồ thị sai số và va chạm hash

Kết luận: Cloudflare có thể giảm 90% số hash sinh ra cho mỗi máy chủ mà không gây sai số đáng kể. Đây là tin cực tốt cho kế hoạch thu hồi RAM.

Di chuyển an toàn, không đánh sập máy chủ gốc

Thay đổi vòng băm đồng nghĩa với việc một số yêu cầu có thể lưu cache sẽ được định tuyến tới máy chủ khác. Nếu chuyển đổi toàn bộ mạng cùng lúc, gần như toàn bộ nội dung cache sẽ bị vô hiệu hóa, biến một tối ưu bộ nhớ thành thảm họa lưu lượng truy cập về máy chủ gốc.

Vì vậy, PBR đã chạy đồng thời cả hai vòng băm trong một thời gian: vòng ketama cũ và vòng mới nhỏ hơn. Mỗi yêu cầu dùng khung di chuyển (migration framework) chuẩn để quyết định vòng nào chọn backend, đảm bảo quyết định ổn định theo từng hash yêu cầu và có đường lùi (rollback) rõ ràng.

Quá trình triển khai được thực hiện theo lớp: bắt đầu từ các vị trí nhỏ để kiểm chứng, mở rộng dần ra các nhóm trung tâm dữ liệu lớn hơn, rồi mới tới phần còn lại của thế giới. Cách này giúp kiểm soát hai chiều độc lập: lượng lưu lượng dùng vòng mới và phạm vi địa lý được phép thay đổi.

Trong suốt quá trình, nhóm kỹ sư theo dõi dấu vết chọn backend, bộ đếm phiên bản vòng, lỗi kết nối PBR, bộ nhớ tiến trình, thời gian khởi động, hành vi cache và lưu lượng gốc. Khi đạt 100%, đường dẫn vòng cũ tạm thời được gỡ bỏ.

Biểu đồ so sánh mức sử dụng bộ nhớ PBR

Kết quả: mức sử dụng bộ nhớ giảm 100TB — một con số đáng kinh ngạc đối với một thay đổi thuật toán.

Bài học cho các kỹ sư Việt Nam

Tất cả cải tiến trên đã có sẵn trong crate pingora-ketama dưới dạng một cargo feature (hiện chưa được quảng bá). Vòng băm v2 có định dạng lưu trữ gọn hơn, phương pháp sắp xếp nhanh hơn và khả năng điều chỉnh số hash cơ sở mỗi nút.

Câu chuyện này mang lại bài học quý giá cho các đội ngũ kỹ thuật tại Việt Nam:

• Đừng bỏ qua những quyết định "hiển nhiên": Cấu trúc dữ liệu tưởng chừng hợp lý vẫn có thể ẩn chứa lãng phí khổng lồ.
• Toán học là công cụ đắc lực: Hiểu rõ phân phối xác suất giúp đưa ra quyết định tối ưu dựa trên dữ liệu thay vì phỏng đoán.
• Tối ưu hóa cần đi kèm an toàn: Di chuyển theo lớp, chạy song song phiên bản cũ và mới, luôn có đường lùi.
• Quy tắc căn chỉnh bộ nhớ trong Rust đáng để tìm hiểu sâu nếu bạn làm việc với hệ thống hiệu năng cao.

"Bạn có thể không giải quyết được mọi vấn đề bằng Rust, nhưng toán học thì phổ quát." — Kevin Guthrie & Mariia Iurchenko, Cloudflare

Ở quy mô của Cloudflare, một thay đổi nhỏ trong thuật toán có thể tiết kiệm hàng trăm terabyte RAM. Với các hệ thống Việt Nam đang mở rộng quy mô, việc đào sâu vào những chi tiết tưởng chừng nhỏ nhặt như vậy hoàn toàn có thể mang lại lợi ích tương tự.