Hãy tưởng tượng bạn vận hành một cơ sở dữ liệu phân tán với ba bản sao (replica) trên ba máy chủ khác nhau, mỗi bản sao chứa một tỷ bản ghi. Một nút bị mất kết nối vài giờ do lỗi mạng và giờ cần đồng bộ lại. Cách ngây thơ nhất là so từng bản ghi một, tức đọc và truyền một tỷ dòng dữ liệu qua mạng để tìm ra vài nghìn dòng bị lệch. Với băng thông thực tế, việc này có thể mất hàng giờ và làm nghẽn cả cụm. Đây là bài toán mà các hệ thống như Cassandra, Riak hay Amazon Dynamo giải bằng cơ chế anti-entropy: định kỳ so sánh các bản sao để phát hiện và sửa sai lệch mà không phải truyền toàn bộ dữ liệu.

Xây dựng cây hash

Merkle tree giải quyết bài toán này bằng cấu trúc cây nhị phân của các mã băm. Ở tầng lá, mỗi nút chứa mã băm của một bản ghi hoặc một nhóm nhỏ bản ghi trong một khoảng khóa nhất định. Lên một tầng, mỗi nút cha là mã băm được tạo từ hai nút con bên dưới. Quá trình lặp lại cho đến khi chỉ còn một nút duy nhất ở đỉnh: root hash. Với một tỷ bản ghi, nếu bạn chia thành 32.000 lá, giống cách Cassandra làm với cây có độ sâu 15, mỗi lá đại diện cho khoảng 31.000 bản ghi liền kề theo khóa. Toàn bộ cây chỉ tốn vài megabyte để lưu, dù dữ liệu gốc nặng hàng trăm gigabyte.

So sánh root hash

Khi hai bản sao cần đồng bộ, mỗi nút tự tính cây Merkle của phần dữ liệu mình giữ rồi gửi cho nhau, hoặc gửi cho một nút điều phối. Bước so sánh đầu tiên cực kỳ đơn giản: chỉ so hai root hash. Nếu hai giá trị này giống hệt nhau, điều đó chứng minh, với xác suất va chạm hash gần như bằng không, rằng toàn bộ tỷ bản ghi ở hai bên hoàn toàn khớp nhau, không cần truyền một byte dữ liệu thực nào. Đây là điểm hiệu quả nhất của kỹ thuật này: một phép so sánh 32 byte với SHA-256 thay cho việc quét cả một tỷ dòng.

Duyệt cây con để khoanh vùng sai lệch

Nếu root hash khác nhau, ta biết dữ liệu có sai lệch nhưng chưa xác định được vị trí. Lúc này thuật toán đi xuống một tầng, so sánh hash của hai nút con trái và phải. Nhánh nào có hash khớp nhau thì bỏ qua toàn bộ, vì mọi bản ghi bên dưới nhánh đó chắc chắn giống nhau. Nhánh nào lệch thì tiếp tục đệ quy xuống tầng kế tiếp, so hai nút con của nó. Cứ như vậy, mỗi tầng loại bỏ được một nửa không gian khóa cần nghi ngờ, cho đến khi chạm tới lá, tại đó ta biết chính xác khoảng khóa nào chứa bản ghi lệch. Chỉ dữ liệu trong khoảng khóa đó mới cần truyền qua mạng để đồng bộ lại, có thể chỉ vài nghìn bản ghi thay vì cả tỷ.

Chi phí xây dựng và bảo trì cây

Merkle tree không miễn phí. Tính lại toàn bộ cây đòi hỏi quét hết dữ liệu để tính mã băm cho từng lá, tốn CPU và I/O đáng kể, nên Cassandra không lưu cây này lâu dài mà chỉ tính lại mỗi lần chạy repair. Riak thì ngược lại, giữ cây trên đĩa và cập nhật dần khi có bản ghi mới, đánh đổi bộ nhớ và độ phức tạp để tránh phải quét lại toàn bộ dữ liệu mỗi lần. Chọn độ sâu cây cũng là một sự cân bằng: cây sâu hơn, nhiều lá hơn, khoanh vùng sai lệch chính xác hơn nhưng tốn nhiều bộ nhớ và thời gian tính hash hơn, còn cây nông hơn thì rẻ nhưng mỗi lần phát hiện lệch phải truyền một khoảng khóa lớn hơn. Trong công nghệ phân tán, đây là bài toán kinh điển: hy sinh một chút chi phí tính toán cục bộ để tiết kiệm tài nguyên mạng, thứ luôn đắt đỏ và chậm hơn CPU rất nhiều lần khi hệ thống trải rộng qua nhiều trung tâm dữ liệu.

Kỹ thuật này không chỉ nằm trong sách giáo khoa. Các cơ sở dữ liệu NoSQL hiện đại như Cassandra, Riak và cả kiến trúc gốc Dynamo của Amazon đều dựa vào Merkle tree để giữ hàng trăm nút đồng bộ mà không biến mạng nội bộ thành nút thắt cổ chai. Ý tưởng cốt lõi, biến bài toán so sánh có chi phí tăng theo quy mô dữ liệu thành chuỗi phép so sánh mã băm tăng theo logarit, cũng xuất hiện trong Git, blockchain và nhiều hệ thống cần xác minh tính toàn vẹn của dữ liệu lớn mà không phải tải lại từ đầu.