Giới thiệu Meerkat: Thử nghiệm mới về thuật toán đồng thuận toàn cầu từ Cloudflare

2026-07-08

12 phút đọc

Nhiều dịch vụ nội bộ tại Cloudflare cần đọc và sửa đổi cùng một trạng thái mặt phẳng điều khiển (control-plane state) trên hơn 330 trung tâm dữ liệu toàn cầu của chúng tôi. Họ cần sự đảm bảo rằng các trình đọc khác nhau không bao giờ nhìn thấy trạng thái không nhất quán, và hệ thống vẫn khả dụng cho các thao tác ghi ngay cả khi một số trung tâm dữ liệu hoặc đường truyền gặp sự cố.

Tuy nhiên, mạng lưới của Cloudflare vận hành trên toàn bộ Internet, và Internet là một môi trường khó dự đoán. Các máy chủ và trung tâm dữ liệu có thể bị sập. Hàng đợi bị đầy. Các đường truyền và cáp quang bị cắt. Những điều kiện này gây khó khăn cho việc vận hành một hệ thống dữ liệu khả dụng toàn cầu đảm bảo tính nhất quán mạnh (ví dụ: đảm bảo tất cả các trình đọc đều đọc được tất cả các thao tác ghi trước đó) vì các điều kiện bất lợi cản trở khả năng đồng bộ hóa dữ liệu một cách đáng tin cậy giữa các bản sao (replica) của hệ thống phân tán.

Một cách để đồng bộ hóa dữ liệu an toàn bất chấp các điều kiện mạng bất lợi là thông qua thuật toán đồng thuận (consensus algorithm), cho phép một tập hợp các máy thống nhất về cùng một chuỗi giá trị, chẳng hạn như các thao tác "put" và "get" trong kho lưu trữ khóa-giá trị (key-value store), miễn là đa số các máy vẫn hoạt động và có thể giao tiếp với nhau.

Thật không may, các thuật toán đồng thuận phổ biến như Raft lại gặp khó khăn trong các mạng diện rộng (wide-area networks) như của Cloudflare vì chúng phụ thuộc vào các "leader" (nút dẫn đầu) và thời gian chờ (timeout). Leader là bản sao duy nhất được phép thực hiện các thao tác ghi, và nếu nó gặp sự cố do treo hoặc suy giảm mạng, hệ thống sẽ trở nên không khả dụng cho đến khi một bản sao khác hết thời gian chờ và một leader mới được bầu chọn. Và các giá trị timeout này rất khó cấu hình trong các mạng có độ trễ khó dự đoán.

Chúng tôi đã trải qua nhiều sự cố do các leader không khả dụng trong các hệ thống dựa trên sự đồng thuận.

Vì vậy, trong năm qua, nhóm Nghiên cứu của Cloudflare đã xây dựng một dịch vụ đồng thuận phân tán mới có tên là Meerkat, được vận hành bởi thuật toán đồng thuận QuePaxa, công bố năm 2023 bởi các nhà nghiên cứu tại EPFL. QuePaxa khác với Raft ở chỗ tất cả các bản sao đều có thể thực hiện thao tác ghi tại mọi thời điểm, và tiến trình không bao giờ bị dừng lại do timeout, điều này khiến nó rất phù hợp với mạng lưới của Cloudflare. Chúng tôi xếp chồng các ứng dụng, như kho lưu trữ khóa-giá trị giao dịch và hệ thống cho thuê (leasing system), lên trên nhật ký đồng thuận của Meerkat. Theo hiểu biết của chúng tôi, đây sẽ là lần triển khai công nghiệp đầu tiên của QuePaxa ở quy mô toàn cầu.

Meerkat là một dịch vụ đồng thuận thử nghiệm vẫn đang trong quá trình phát triển. Ban đầu, nó được thiết kế để quản lý các phần nhỏ của trạng thái mặt phẳng điều khiển (ví dụ: quyền lãnh đạo cho các cơ sở dữ liệu được sao chép) và do đó sẽ chỉ được giữ ở nội bộ trong tương lai gần. Bài viết này giới thiệu về Meerkat và đặt nền móng cho các bài đăng blog liên quan đến Meerkat sắp tới.

Những gì chúng tôi cần từ một hệ thống dữ liệu mặt phẳng điều khiển toàn cầu

Nhiều dịch vụ của Cloudflare đọc và ghi dữ liệu mặt phẳng điều khiển – dữ liệu giúp các dịch vụ đó vận hành chính xác – từ nhiều máy tính phân tán trên khắp thế giới. Một ví dụ về dữ liệu mặt phẳng điều khiển là thông tin vị trí: nơi lưu trữ các tài nguyên nhất định (như một instance của mô hình AI). Một ví dụ khác là thông tin về quyền lãnh đạo: máy nào hiện được phép thực hiện các thao tác ghi vào cơ sở dữ liệu.

Dữ liệu mặt phẳng điều khiển phải vừa nhất quán mạnh vừa có thể truy cập được bất chấp các loại lỗi cụ thể.

Trong phần này, chúng tôi mô tả chính xác các yêu cầu về tính nhất quán và khả năng chịu lỗi cho dịch vụ đồng thuận của Cloudflare. Chúng tôi sử dụng kho lưu trữ khóa-giá trị làm ví dụ thực tế cho một ứng dụng chạy trên dịch vụ đồng thuận của chúng tôi, mặc dù các ứng dụng khác (ví dụ: cho thuê/khóa phân tán) cũng có thể thực hiện được.

Tính nhất quán mạnh (Strong consistency)

Mức độ nhất quán của một hệ thống dữ liệu phân tán mô tả những loại hành vi kỳ lạ nào mà hệ thống được phép thể hiện khi nhận các thao tác đọc và ghi đồng thời. Hãy xem xét một kho lưu trữ khóa-giá trị phân tán lưu trữ một giá trị số x = 6 trên nhiều nút. Cũng hãy xem xét chuỗi các thao tác ghi sau đây. Các thao tác ghi này được gửi đến các nút khác nhau trên cơ sở nỗ lực tốt nhất (best-effort) và có thể đến theo bất kỳ thứ tự nào:

x = x + 1

x = x / 2

Mức độ nhất quán của hệ thống cho bạn biết giá trị nào của x mà một client có thể thấy khi đọc x sau các thao tác ghi này. Hãy xem xét chuỗi các thao tác sau và các thứ tự thực thi có thể xảy ra dưới các mức độ nhất quán khác nhau:

Ở mức độ nhất quán yếu, các thao tác ghi có thể bị sắp xếp lại. Trong mô hình nhất quán mạnh hơn, các thao tác ghi không thể bị sắp xếp lại, nhưng các thao tác đọc thì có thể. Ở mức độ nhất quán mạnh nhất có thể, các thao tác được sắp xếp chính xác như cách chúng xảy ra trong thời gian thực. Đặc tính này được gọi là tính tuyến tính (linearizability).

Tại Cloudflare, nhiều dịch vụ yêu cầu tính tuyến tính. Không giống như các hình thức nhất quán yếu hơn, tính tuyến tính giúp các lập trình viên không phải suy nghĩ về tất cả các hành vi kỳ lạ mà hệ thống dữ liệu có thể thể hiện. Thay vào đó, họ có thể suy luận về hệ thống phân tán giống như cách họ suy luận về bộ nhớ cục bộ trên một máy đơn luồng: tất cả các thao tác đọc sau một thao tác ghi sẽ thấy được thao tác ghi đó. Để đọc thêm tài liệu về những nguy hiểm của tính nhất quán yếu, hãy xem bài viết này của Marc Brooker.

(Nếu bạn đang thắc mắc, kho lưu trữ khóa-giá trị của Meerkat cũng cung cấp tính tuần tự hóa (serializability), điều mà chúng tôi sẽ viết trong một bài đăng tương lai.)

Khả năng chịu lỗi (Fault tolerance)

Mức độ chịu lỗi của một hệ thống mô tả những loại lỗi nào mà hệ thống có thể xử lý trước khi xảy ra thảm họa. Thảm họa thường là sự vi phạm các đặc tính mà hệ thống hướng tới, ví dụ: hai lần đọc liên tiếp mà không có thao tác ghi xen kẽ cho cùng một khóa không bao giờ thấy các giá trị khác nhau, hoặc hệ thống vẫn khả dụng cho các thao tác ghi. Các lỗi bao gồm lỗi hoặc độ trễ mạng, máy bị treo và máy khởi động lại. Một hệ thống thường sẽ xử lý rõ ràng một số lỗi nhưng không xử lý các lỗi khác (bạn không thể xử lý tất cả các lỗi, vì vũ trụ luôn có thể đi đến cái chết nhiệt). Ví dụ, một số kho lưu trữ khóa-giá trị có thể đảm bảo vẫn khả dụng cho các thao tác ghi miễn là hai phần ba số máy trong hệ thống có thể giao tiếp và không bị treo, nhưng không hứa hẹn gì nếu một máy bị xâm nhập và bắt đầu gửi các thông điệp độc hại.

Các đặc tính chịu lỗi mong muốn của chúng tôi như sau:

Thứ nhất, hệ thống dữ liệu phải vẫn khả dụng cho các thao tác ghi và đọc từ một client đặt tại bất kỳ trung tâm dữ liệu nào của chúng tôi miễn là các điều kiện sau đây đúng:

Đa số các máy trong hệ thống của chúng tôi vẫn hoạt động và có thể giao tiếp với nhau. (Về mặt hình thức, chúng tôi chịu được f lỗi trong một hệ thống gồm 2f + 1 máy).

Client có thể liên lạc với bất kỳ máy nào trong hệ thống đang được kết nối với đa số các máy đang hoạt động.

Điều này có nghĩa là một máy bị lỗi đơn lẻ, hoặc sự suy giảm mạng trên một đường truyền đơn lẻ, không ảnh hưởng đến tính khả dụng của hệ thống. Đặc tính này không được cung cấp bởi các hệ thống dựa trên Raft, như chúng ta sẽ thấy sau.

Thứ hai, hệ thống dữ liệu vẫn chính xác miễn là không có tác nhân nào trong hệ thống chủ động độc hại (và tất nhiên, không có lỗi phần mềm). Chúng tôi định nghĩa tính chính xác dựa trên sự an toàn của đồng thuận (consensus safety) ở phần sau, nhưng nói một cách đơn giản, điều này có nghĩa là không bao giờ có hai máy cập nhật nào bất đồng về thế giới (ví dụ: một máy nghĩ rằng key1=1 trong khi máy khác nghĩ rằng key1=2).

Tóm lại, hệ thống phải vẫn chính xác ngay cả khi máy bị treo, máy khởi động lại, mạng bị lỗi hoặc suy giảm, trung tâm dữ liệu bị sập, v.v. (mặc dù chúng tôi, giống như các hệ thống dựa trên Raft, không xử lý các lỗi Byzantine).

Giới thiệu về Meerkat

Meerkat là một dịch vụ đồng thuận mà trên đó chúng tôi có thể xây dựng các ứng dụng thể hiện các đặc tính trên (tính nhất quán mạnh và khả năng chịu lỗi) như kho lưu trữ khóa-giá trị (KV). Để hiểu cách Meerkat hoạt động, trước tiên chúng tôi phác thảo kiến trúc chung của Meerkat, sau đó mô tả cách lựa chọn thuật toán đồng thuận của Meerkat giúp cung cấp tính nhất quán mạnh và khả năng chịu lỗi.

Các nhà phát triển dịch vụ sử dụng Meerkat yêu cầu một cụm các bản sao Meerkat. Mỗi bản sao được kết nối với mọi bản sao khác. Mỗi bản sao tham gia vào thuật toán đồng thuận và có thể nhận cả thao tác đọc và ghi. Nhà phát triển có thể chỉ định trung tâm dữ liệu nào được phép lưu trữ các bản sao của họ, và Meerkat sẽ tự động đặt chúng.

Để tương tác với cụm của mình, client của nhà phát triển gửi một yêu cầu cụ thể cho ứng dụng đến bất kỳ bản sao nào trong cụm. Một bản sao duy nhất có thể lưu trữ nhiều loại ứng dụng, nhưng đơn giản nhất là kho lưu trữ khóa-giá trị, vì vậy loại yêu cầu cụ thể cho ứng dụng đơn giản nhất là KV get hoặc put. Bản sao phản hồi yêu cầu bằng một phản hồi cụ thể cho ứng dụng (ví dụ: các bản ghi được yêu cầu bằng get). Lưu ý rằng các thao tác đọc KV (get) được đảm bảo đọc thông tin cập nhật nhất.

Nhật ký của Meerkat

Bên dưới, bản sao dịch các yêu cầu ứng dụng (ví dụ: get và put) thành các sự kiện nhật ký. Bản sao đó phân phối từng sự kiện nhật ký đến tất cả các bản sao khác bằng cách sử dụng thuật toán đồng thuận sao cho tất cả các bản sao duy trì chính xác cùng một nhật ký sự kiện (trong thực tế, một bản sao có thể bị chậm lại, nhưng không bao giờ được ghi lại các mục khác nhau). Các sự kiện này là tùy ý — cốt lõi của Meerkat không quan tâm nội dung bên trong chúng là gì. Các ứng dụng Meerkat quan tâm đến nội dung sự kiện nhật ký. Mỗi bản sao Meerkat "lưu trữ" nhiều ứng dụng Meerkat (ví dụ: kho lưu trữ khóa-giá trị) đọc các sự kiện nhật ký và xây dựng trạng thái. (Lưu ý rằng mỗi bản sao thuộc về chính xác một cụm.)

Ví dụ, ứng dụng KV Meerkat xây dựng một kho lưu trữ khóa-giá trị trong bộ nhớ từ các sự kiện nhật ký. Vì vậy, khi một client gửi một thao tác ghi như put k1 v1, bản sao nhận được sẽ đặt thao tác ghi đó vào một sự kiện nhật ký và phân phối nó đến tất cả các bản sao. Nếu sau đó có ai đó ghi put k1 v11 vào một bản sao khác, sự kiện này cũng được phân phối đến tất cả các bản sao. Vì tất cả các bản sao đang hoạt động đều có cùng một nhật ký, các bản sao đó có thể áp dụng các thao tác trong nhật ký theo trình tự để xây dựng cùng một trạng thái chính xác. Lưu ý rằng các yêu cầu get cũng tạo ra các sự kiện nhật ký phân tán (để đảm bảo tính tuyến tính, như đã giải thích trong phần tiếp theo).

Đây là ví dụ về cách kho lưu trữ KV của một bản sao được cập nhật khi nó nhận được các sự kiện nhật ký:

Cách nhật ký của Meerkat cho phép tính nhất quán mạnh