Merkle tree — phát hiện khác biệt hiệu quả

TL;DR: Merkle tree là cây nhị phân trong đó lá lưu hash của từng block dữ liệu, và mỗi node trong lưu hash của hai node con. Root là một hash đại diện cho toàn bộ tập dữ liệu. Để so sánh hai replica: nếu root giống nhau thì dữ liệu giống hệt nhau, không cần so thêm. Nếu root khác, đi xuống theo nhánh có hash khác cho đến lá, tìm đúng block nào khác biệt trong O(log n) thay vì so toàn bộ O(n). Kỹ thuật này là nền tảng của anti-entropy repair (định kỳ so các bản sao rồi vá chỗ lệch) trong Cassandra/Dynamo, commit tree trong Git, và block verification trong Bitcoin.

Cluster Cassandra của bạn có hai node, mỗi node giữ cùng 10 triệu key (hai bản sao). Mạng bị gián đoạn 30 giây; trong thời gian đó một số write vào node A chưa đến node B. Làm thế nào node B biết chính xác key nào bị thiếu mà không phải nhận cả 10 triệu key để so? Merkle tree trả lời câu hỏi này.

1. Vấn đề: so sánh hai tập dữ liệu lớn

Tình huống anti-entropy repair (định kỳ so các bản sao rồi vá chỗ lệch): node A và node B đều lưu N=10.000.000 key-value. Sau một khoảng downtime, chúng có thể lệch nhau một số key. Cần tìm ra đúng những key nào khác nhau để sync.

Giải pháp ngây thơ (O(n)): node A gửi toàn bộ 10 triệu key cho node B so sánh. Mỗi key 100 byte → 1 GB qua mạng chỉ để tìm ra có khi chỉ 100 key lệch.

Git và Bitcoin gặp cùng bài toán ở quy mô khác: so một khối dữ liệu lớn mà không đọc lại từ đầu đến cuối.

2. Cấu trúc Merkle tree

Hình dung mỗi đoạn dữ liệu có một "dấu vân tay" ngắn (hash). Gộp dấu vân tay của hai đoạn kề nhau thành một dấu mới, cứ gộp lên mãi cho tới một dấu duy nhất ở đỉnh. Đó là Merkle tree (Ralph Merkle, 1987), xây từ dưới lên:

1. Lá (leaf): mỗi lá lưu hash(data_block_i): hash của một đơn vị dữ liệu.
2. Node trong (internal node): hash(left_child || right_child): hash của chuỗi nối hai con.
3. Root: hash duy nhất đại diện cho toàn bộ tập dữ liệu.

Cái tiết kiệm không nằm ở phép so lẻ mà ở nhánh bị cắt: D1 và D2 không bị đọc một byte nào, vì một phép so ở H12 đã loại cả nửa cây. Với bốn lá thì chưa thấy gì; với một triệu bản ghi, chính cơ chế này biến một triệu phép so thành hai mươi.

Tính chất then chốt: bất kỳ thay đổi nào ở lá đều lan ngược lên root qua chuỗi hash. Nếu root giống nhau thì gần như chắc chắn toàn bộ cây giống nhau: với hash 256-bit, muốn tìm một cặp dữ liệu khác nhau mà cùng hash phải thử cỡ 2^128 lần.

Thử ngẫmhai cây Merkle bốn lá chỉ khác ở D3. Khi so từ root xuống, những cặp hash nào được so và nhánh nào bị cắt?