Tiết kiệm 100TB RAM nhờ toán học và ngôn ngữ Rust

Cloudflare vận hành ở quy mô lớn đến mức ngay cả khi đã làm việc ở đây nhiều năm, tôi vẫn cảm thấy nó không thực tế. Chúng tôi có hàng nghìn máy chủ trên khắp thế giới với dung lượng RAM tính bằng petabyte và hàng triệu nhân CPU, tất cả đều được đẩy lên mức tối đa. Dù các tài nguyên đó có vẻ bao la, chúng vẫn là hữu hạn, và khi bạn cần mọi dịch vụ chạy trên mọi node, sẽ không còn chỗ cho sự lãng phí.

Ở quy mô này, những cải tiến nhỏ cũng được khuếch đại đáng kể, vì vậy ngay cả những cải tiến từng bước 1% cũng rất đáng ăn mừng. Một số tinh chỉnh mang lại hiệu quả lớn hơn nhiều: trong bài viết này, chúng ta sẽ xem xét cách những thay đổi nhỏ đối với một thuật toán đơn lẻ đã giảm đáng kể dung lượng bộ nhớ của một trong các dịch vụ dựa trên Pingora của chúng tôi. Điều đó cho phép chúng tôi thu hồi hơn 100TB RAM trên toàn cầu, bên cạnh 100TB bộ nhớ mà đội ngũ DNS đã cắt giảm được vào tháng trước.

Đừng lãng phí

Việc duy trì sự chia sẻ tài nguyên công bằng giữa các đội ngũ không hề dễ dàng, đặc biệt là trong các tổ chức lớn. Một trong những cách Cloudflare đảm bảo sự cân bằng này được duy trì là nhờ những nỗ lực không ngừng nghỉ của đội ngũ Performance tuyệt vời.

Câu chuyện này bắt đầu từ một ticket do Ivan gửi, trong đó anh phát hiện: Mức sử dụng bộ nhớ quá mức từ pingora-ketama trong Pingora Backend Router. Kết quả là dịch vụ cân bằng tải nội bộ của chúng tôi, Pingora Backend Router (vâng, PBR), đang sử dụng bộ nhớ nhiều hơn đáng kể so với dự kiến — cụ thể là trong các cấu trúc liên quan đến pingora-ketama, thư viện mã nguồn mở của chúng tôi để xử lý consistent hashing (băm nhất quán).

Để nói về cách chúng tôi giải quyết tình trạng sử dụng bộ nhớ quá mức này, chúng ta cần thảo luận về việc consistent hashing là gì, tại sao chúng tôi sử dụng nó trong PBR và tại sao nó lại tiêu tốn nhiều bộ nhớ đến vậy. Trong quá trình đó, chúng ta sẽ học một chút về Rust và cả một chút toán học.

Consistent hashing

Consistent hashing là một phương pháp được sử dụng rộng rãi để phân phối các tác vụ trên nhiều máy chủ theo cách không yêu cầu thay đổi lớn khi thêm hoặc bớt máy chủ. Nội bộ chúng tôi sử dụng nó để định tuyến các yêu cầu có thể lưu vào bộ nhớ đệm (cacheable requests) đến các máy chủ theo URL. Điều này cho phép chúng tôi chỉ giữ một bản sao của tệp được lưu trữ trên mỗi trung tâm dữ liệu và cung cấp một cách ổn định để tìm vị trí của từng tệp. Chúng tôi đã đề cập đến hệ thống này trước đây, nhưng hãy dành thời gian để tìm hiểu cách thức và lý do tại sao thuật toán này được sử dụng cũng như cách nó hoạt động.

Khái niệm chính của consistent hashing là trong khi các hàm băm (hash functions) có thể chấp nhận bất kỳ loại đầu vào nào, đầu ra của chúng bị giới hạn trong một số nguyên không dấu duy nhất (số nguyên 32, 64 hoặc 128-bit tùy thuộc vào hàm băm). Điều này cho phép chúng ta liên kết các tác vụ và máy chủ với nhau một cách nhất quán. Hầu hết các cuộc thảo luận về consistent hashing đều khiến bạn hình dung không gian đầu ra đó như một vòng tròn liên tục, quay vòng từ giá trị tối đa về 0. Cách mô tả này tạo ra một số hình ảnh trực quan đẹp mắt, nhưng nó cũng có thể làm cho khái niệm đơn giản về các dải số nguyên trở nên phức tạp hơn mức cần thiết. Đối với cuộc thảo luận của chúng ta, chúng ta sẽ biểu diễn đầu ra 32-bit của hàm băm dưới dạng một trục số.

Bây giờ, giả sử chúng ta có một tập hợp các máy chủ A, B, & C, và một tập hợp các tác vụ t-z. Chúng ta có thể ánh xạ từng cái lên trục số dựa trên giá trị băm của các giá trị đại diện cho chúng, ví dụ như địa chỉ IP cho máy chủ và khóa cache cho tác vụ.

Việc gán tác vụ cho máy chủ bây giờ chỉ đơn giản là tìm máy chủ đầu tiên nằm bên trái của mỗi tác vụ. Chúng ta có thể biểu diễn điều này một cách trực quan bằng cách tô màu vùng băm sẽ được liên kết với mỗi máy chủ. Lưu ý rằng phạm vi được bao phủ bởi máy chủ C quay vòng trở lại điểm bắt đầu, đó là lý do tại sao có ý tưởng rằng các giá trị băm tồn tại trong một vòng tròn.

Và chỉ vậy thôi. Ở mức cơ bản, consistent hashing đơn giản như vậy — nhưng không mất nhiều thời gian để thấy rằng vẫn còn chỗ để cải thiện. Lưu ý rằng phạm vi được bao phủ bởi máy chủ A trong ví dụ của chúng ta lớn hơn đáng kể so với B hoặc C. Đây là một vấn đề vì tỷ lệ các yêu cầu mà một máy chủ xử lý sẽ tỷ lệ thuận với kích thước phạm vi của nó trên trục số. Lý tưởng nhất là chúng ta muốn đảm bảo mỗi máy chủ có kích thước bằng nhau, nhưng vì các giá trị băm về cơ bản là các số ngẫu nhiên, chúng ta phải thảo luận về kích thước của các vùng dưới góc độ thống kê. 😨

Toán học và hệ quả

Đầu tiên: đừng hoảng sợ. Tôi hứa sẽ không nói dối bạn và chúng ta sẽ vẫn nằm an toàn trong phạm vi của một bài học xác suất cơ bản. Khi nói về các phân phối thống kê, có hai yếu tố lớn giúp chúng ta định lượng sự không chắc chắn theo những cách hữu ích: giá trị kỳ vọng (expected value) và độ lệch chuẩn (standard deviation). Nói một cách (quá) đơn giản, giá trị kỳ vọng cho chúng ta một điểm mà các phép đo dựa trên phân phối sẽ tập trung xung quanh, và độ lệch chuẩn cho biết hầu hết các phép đo có khả năng gần với điểm trung tâm đó như thế nào.

Đối với consistent hashing, chúng ta có thể tính toán các yếu tố này cho kích thước phân đoạn của phạm vi liên quan đến một trong N máy chủ. (Chi tiết về nguồn gốc công thức này sẽ có sau).

$$m \begin{align*} \text{Exp} &= \frac{1}{N} \\ \text{SD} &= \frac{1}{N}\sqrt{\frac{N-1}{N+1}} \end{align*} m$$

Về các con số cụ thể, giả sử chúng ta có 100 máy chủ. Các công thức trên cho kết quả:

$$m \text{Exp}=1/100 = 1\% \\ \text{SD}= \frac{1}{100}\sqrt{\frac{100-1}{100+1}} \approx 0.99\% m$$

Điều đó cho chúng ta biết rằng chúng ta có thể kỳ vọng phạm vi mà mỗi máy chủ xử lý sẽ tập trung quanh mức 0,99% tổng số và hầu hết các độ dài sẽ nằm trong khoảng 1% so với dự kiến. Điều này nghe có vẻ tốt cho đến khi chúng ta nhận ra đó là 0,99% của tổng chiều dài. Chúng ta cần chia tỷ lệ độ lệch chuẩn theo giá trị kỳ vọng để xem sai số lớn đến mức nào so với kích thước mục tiêu. Giá trị này được gọi là hệ số biến thiên (coefficient of variation).

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

Tại $m N=100, \text{CV} \approx 99\% m$ — nghĩa là một số máy chủ có khả năng sẽ phải làm việc vất vả hơn 99% so với mức cần thiết (xử lý gấp đôi số lượng yêu cầu) trong khi những máy chủ khác có thể gần như không làm gì cả! Bây giờ chúng ta đã có cách dự đoán mức độ tải đều của các máy chủ khi sử dụng consistent hashing, chúng ta có thể bắt đầu cải thiện.

Nếu chúng ta thêm các giá trị băm thì sao?

Sự đơn giản của consistent hashing là con dao hai lưỡi. Nó dễ hiểu và dễ triển khai vì mọi thứ đều được chuyển thành các giá trị băm dễ liên hệ trên cùng một trục số, nhưng bất kỳ cải tiến nào đối với hệ thống cũng sẽ cần phải liên hệ được với trục số đó. Điều đó có nghĩa là giải pháp cho bất kỳ vấn đề nào của consistent hashing chỉ có thể là nhiều giá trị băm hơn. Nó không giống như một chiếc búa vàng (một công cụ mà mọi vấn đề đều trông giống như cái đinh) mà giống như một chiếc đinh vàng vì nó biến tất cả các công cụ thành búa.

Để giải quyết vấn đề khối lượng công việc không cân bằng, chúng ta có thể thêm nhiều giá trị băm để đại diện cho mỗi máy chủ thay vì chỉ một. Chúng ta sẽ sớm đi sâu vào toán học đằng sau điều này, nhưng về mặt trực giác, trong khi mỗi phạm vi riêng lẻ có độ lệch chuẩn lớn, việc cộng dồn nhiều phạm vi lại với nhau sẽ làm cho tổng kích thước của chúng cân bằng hơn. Nếu chúng ta lấy ví dụ ba máy chủ từ các sơ đồ trên và thêm ngẫu nhiên hai giá trị băm nữa cho mỗi máy chủ, chúng ta thấy rằng nó giúp cân bằng khối lượng công việc của từng máy chủ.

Đây là một ví dụ có phần khiên cưỡng. Bản chất ngẫu nhiên của hệ thống có nghĩa là không có gì đảm bảo bạn sẽ cải thiện được bao nhiêu khi thêm 2 giá trị băm mỗi máy chủ, nhưng về mặt trực giác, việc kết hợp nhiều phân đoạn băm này lại với nhau sẽ tạo ra sự phân phối đồng đều hơn. Mỗi phân đoạn trong tổng số đều có cơ hội bù trừ cho phân đoạn khác. Có lẽ cái này quá ngắn; có lẽ cái kia quá dài. Đây về cơ bản là những gì luật số lớn cho chúng ta biết sẽ xảy ra… Vấn đề hiển nhiên là nó chỉ hoạt động với các số lớn. Trong NGINX, số lượng giá trị băm cơ sở trên mỗi máy chủ được hardcode là 160, và Pingora sử dụng cùng giá trị đó làm mặc định. Tôi sẽ tạm bỏ qua phần toán học, nhưng nếu quay lại ví dụ 100 máy chủ, nếu chúng ta sử dụng 160 điểm mỗi máy chủ thay vì chỉ một, hệ số biến thiên (có thể coi như biên độ sai số) giảm từ khoảng 99% xuống còn khoảng 8%, một sự cải thiện đáng kể.

Nếu chúng ta thêm nhiều giá trị băm hơn nữa thì sao?

Chúng ta đã thấy ở trên rằng việc tăng số lượng giá trị băm trên mỗi máy chủ theo một hằng số cho phép chúng ta cải thiện mức độ phân phối công việc đồng đều trên mỗi máy chủ, nhưng nếu chúng ta không muốn phân phối công việc đồng đều thì sao? Trong trường hợp của Cloudflare, chúng tôi có một số máy chủ có nhiều không gian lưu trữ hơn những máy chủ khác, vì vậy sẽ tốt hơn nếu số lượng yêu cầu được phân bổ cho một máy chủ tỷ lệ thuận với dung lượng đĩa của nó. Một cách để đạt được điều này là sử dụng thuật toán ketama. Tên gọi này hơi buồn cười vì thuật toán được đặt theo tên thư viện nơi nó được triển khai lần đầu, và thư viện đó được đặt tên là… chà, bạn có thể Google nó 😶‍🌫️.

Toàn bộ thuật toán tóm gọn lại là: Đối với bất kỳ hai máy chủ nào, $m S_1m$ & $mS_2m$, nếu chúng ta muốn các yêu cầu được phục vụ bởi $mS_1m$ nhiều gấp $mw\timesm$ so với những yêu cầu được phục vụ bởi $mS_2m$, thì số lượng giá trị băm liên kết với $mS_1m$ cần phải là $mH_1 = w\times H_2m$. Điều này cho phép chúng ta đặt một "trọng số" cho mỗi máy chủ, giúp điều chỉnh số lượng giá trị băm liên kết với máy chủ đó. Thật không may, đây không phải là sự thay thế cho hệ số tỷ lệ hằng số mà chúng ta đã thêm ở phần trên. Việc điều chỉnh đó cần phải có để đặt biên độ sai số tối thiểu, vốn sẽ xuất hiện ở các máy chủ có trọng số thấp nhất.

Đối với chúng tôi, vì muốn khối lượng công việc được điều chỉnh dựa trên lưu trữ, chúng tôi có thể sử dụng dung lượng đĩa làm trọng số, đó chính xác là những gì đội ngũ Pingora đã làm trong nhiều năm. Ở những nơi khác trong công ty, nơi khối lượng công việc đòi hỏi nhiều tính toán hơn, trọng số có thể dựa trên số lượng CPU hoặc GPU.

Nếu chúng ta thêm nhiều giá trị băm hơn nữa thì sao???

Vấn đề cuối cùng chúng ta cần giải quyết là cho đến nay chúng ta đang làm việc với giả định rằng bất kỳ máy chủ nào cũng có thể xử lý bất kỳ yêu cầu nào, nhưng trên thực tế thì không phải vậy. Những thứ như yêu cầu tuân thủ hoặc các tính năng lưu trữ bộ nhớ đệm được bật có nghĩa là chỉ một tập hợp con các máy chủ mới có thể xử lý một yêu cầu cụ thể. Thật không may, không giống như trước đây, chúng ta không thể giải quyết vấn đề này bằng cách thêm nhiều giá trị băm vào cùng một vòng tròn. Chúng ta phải thêm các vòng tròn hoàn toàn mới, và không chỉ vậy — mọi sự kết hợp của các tính năng có khả năng cần một vòng tròn cụ thể của riêng nó!

Sự trùng lặp dựa trên các kết hợp là một công thức kinh điển dẫn đến sự bùng nổ theo cấp số nhân. Trong trường hợp của chúng tôi, chúng tôi có một vài tính năng khác nhau dẫn đến $m2^\text{handful} = \text{dozens}m$ các vòng tròn băm nhất quán riêng biệt. Vì vậy, như bạn có thể đã đoán ra, "mức sử dụng bộ nhớ quá mức" (6GB trong một số trường hợp) mà Ivan tìm thấy là do số lượng giá trị băm khổng lồ để đáp ứng tất cả các chức năng chúng tôi cần và phải được lưu trữ trong bộ nhớ. Vậy chúng ta có thể làm gì?

Cải thiện lưu trữ

Một cải tiến lớn đến từ Zaidoon, người đã có cái nhìn sâu sắc về struct của chúng tôi để lưu trữ các giá trị băm trong PBR. Struct đó trông như thế này:

Trong bộ nhớ, nó được biểu diễn dưới dạng tám byte, trong đó bốn byte dành cho giá trị băm (điều không thể tránh khỏi) và bốn byte dành cho một chỉ mục trỏ đến máy chủ được lưu trữ trong một mảng khác. Cái nhìn sâu sắc của Zaidoon là một số nguyên 32-bit cho chỉ mục đó là lãng phí, vì PBR không có khả năng phải điều phối hơn $m2^16 \approx 65\text{k} m$ máy chủ cùng một lúc, vì vậy một số nguyên 16-bit là đủ. Vì vậy, chúng ta có thể thay thế struct ở trên bằng struct này:

Thật không may, Rust không làm cho việc đó trở nên dễ dàng. Thay đổi kích thước của chỉ mục như chúng tôi đã làm ở trên không giúp giảm dung lượng bộ nhớ. Điều này là do Rust có các quy tắc căn chỉnh (alignment rules) yêu cầu kích thước của một cấu trúc trong bộ nhớ phải là bội số của trường lớn nhất (hoặc "được căn chỉnh nhiều nhất") của nó. Trong trường hợp này, giá trị băm là lớn nhất với bốn byte, vì vậy khi lưu trữ trong bộ nhớ, một Point bắt buộc phải có kích thước $mN \times 4m$, do đó kích thước tối thiểu là tám byte.

May mắn thay, có những cách nổi tiếng để giải quyết vấn đề này. Bạn (ý tôi là tôi) có thể bị cám dỗ sử dụng #[repr(packed)], nhưng điều đó gây tranh cãi vì những lý do chính đáng. Một giải pháp an toàn hơn nhưng ít dễ đọc hơn là lưu trữ giá trị băm và chỉ mục dưới dạng mảng byte thô và truy cập chúng bằng các hàm getter. Cả hai phương pháp đều biên dịch ra cùng một kết quả.

Thay đổi đơn giản (dù hơi dài dòng) này giúp giảm lượng bộ nhớ được sử dụng cho consistent hashing tới 25%! Để làm tốt hơn thế, chúng ta sẽ cần quay lại với toán học, vì vậy mọi người hãy bám chắc vào nhé; đây là chặng cuối rồi.

Nếu chúng ta thử ít giá trị băm hơn thì sao?