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 trong Cassandra/Dynamo, commit tree trong Git, và block verification trong Bitcoin.

Cassandra cluster của bạn có hai node mỗi node giữ 10 triệu key (replica). 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. Sau khi mạng phục hồi, làm thế nào node B biết chính xác key nào bị thiếu mà không cần gửi toàn bộ 10 triệu key qua mạng để so sánh? 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

Kịch bản anti-entropy repair: 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 qua mạng cho node B so sánh. Với mỗi key 100 byte → 1 GB dữ liệu mạng chỉ để phát hiện có thể chỉ 100 key khác biệt. Không khả thi trong production.

Vấn đề tương tự: Git phải phát hiện commit nào trong local repository không có trên remote trước khi push — với lịch sử hàng nghìn commit. Bitcoin node mới join network cần verify toàn bộ blockchain (hàng trăm nghìn block) một cách hiệu quả. Mọi bài toán này cần cùng một kỹ thuật.

2. Cấu trúc Merkle tree

Merkle tree (Ralph Merkle, 1987) được 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.

Trong sơ đồ trên: D3 bị sửa đổi. H3 thay đổi → H34 thay đổi → Root thay đổi. H12, H1, H2, H4 vẫn giống hệt → không cần kiểm tra nhánh trái.

Tính chất then chốt: bất kỳ thay đổi nào ở lá đều "bubble up" lên root qua chuỗi hash. Nếu root giống nhau, với xác suất cực cao (birthday paradox với hash 256-bit: 1/2^128) toàn bộ cây giống nhau.

Thử ngẫmcây Merkle bốn lá trong sơ đồ trên chỉ D3 đổi — chỉ 2 hash (H3, H34) tính lại. Với cây tương tự nhưng một triệu lá, tính lại toàn bộ có còn rẻ như vậy không?

3. Pseudocode — xây cây và so sánh

-- Xây Merkle tree từ danh sách data block
function buildMerkle(blocks):
    if blocks rỗng: return null
    -- Bước 1: xây tầng lá
    nodes <- []
    for each block in blocks:
        nodes.append(LeafNode(hash = hash(block), data = block))
    -- Bước 2: xây lên từng tầng
    while nodes.length > 1:
        -- Đệm node lẻ Ở MỖI TẦNG (duplicate node cuối) -- không chỉ tầng lá:
        -- tầng trung gian cũng có thể lẻ nếu số block ban đầu không phải lũy thừa 2
        if nodes.length mod 2 = 1:
            nodes.append(nodes.last)
        nextLevel <- []
        for i <- 0 to nodes.length-1 step 2:
            left <- nodes[i]
            right <- nodes[i+1]
            parent <- InternalNode(
                hash = hash(left.hash || right.hash),
                left = left,
                right = right
            )
            nextLevel.append(parent)
        nodes <- nextLevel
    return nodes[0]    -- root
// Time: O(n)  Space: O(n) cho toàn bộ cây

-- So sánh hai Merkle tree, trả về danh sách lá khác nhau
-- lo, hi: khoảng chỉ số lá mà cây con hiện tại bao phủ [lo, hi]
function diff(nodeA, nodeB, lo, hi, result):
    if nodeA.hash = nodeB.hash:
        return                             -- nhánh này giống hệt, bỏ qua
    if nodeA là lá:
        result.append(lo)                  -- tìm được lá khác biệt
        return
    -- đệ quy xuống nhánh có hash khác
    mid <- (lo + hi) / 2
    diff(nodeA.left,  nodeB.left,  lo,      mid, result)
    diff(nodeA.right, nodeB.right, mid + 1, hi,  result)
// Time: O(k log n) với k lá khác biệt  Space: O(log n) stack đệ quy

Hàm diff chỉ đi sâu vào nhánh khi hash khác nhau. Với k lá khác biệt, mỗi lá cần O(log n) bước để tìm xuống từ root → tổng O(k log n). Khi k rất nhỏ so với n (anti-entropy sau downtime ngắn), tiết kiệm rất lớn so với O(n).

3.1 Ví dụ so sánh

Hai replica mỗi replica 8 block. Node B thiếu 2 block (block 3 và block 7).

Với n=8 ví dụ nhỏ này trông không ấn tượng, nhưng với n=10.000.000 và k=100 block khác biệt: O(100 × log₂(10.000.000)) ≈ 2.400 hash so sánh thay vì 10.000.000 — giảm hơn 4.000 lần.

4. Anti-entropy trong Cassandra

Cassandra gọi quá trình này là anti-entropy repair. Mỗi node xây Merkle tree cho từng token range (phần ring nó phụ trách). Khi chạy nodetool repair:

1. Node A và node B trao đổi Merkle tree root (chỉ 1 hash, vài byte).
2. Nếu giống → không cần làm gì thêm.
3. Nếu khác → trao đổi từng tầng cây (tổng O(k log n) hash) để xác định đúng key range nào lệch.
4. Chỉ sync data của key range lệch đó.

Cách tiếp cận này giúp Cassandra repair nhanh sau network partition mà không cần truyền toàn bộ dữ liệu.

Thử ngẫmcallout vừa nói git diff dùng cùng cơ chế Merkle tree, không so từng byte file. Sửa 1 dòng trong file nằm sâu 5 cấp thư mục, bao nhiêu tree object Git phải tính lại hash?

5. Pitfall

Pitfall 1 — Hash node trong bằng hash(left_hash + right_hash), không phải hash(data_left + data_right)

-- SAI: hash lại toàn bộ data của subtree — mất ý nghĩa incremental
InternalNode.hash <- hash(left_data || right_data)

-- ĐÚNG: hash của hash — chỉ cần 64 byte (2 hash 32-byte) thay vì toàn bộ data
InternalNode.hash <- hash(left.hash || right.hash)

Hash của hash cho phép tính incremental: khi một lá thay đổi, chỉ cần tính lại O(log n) hash trên đường từ lá lên root, không phải hash lại toàn bộ subtree. Đây là điểm mấu chốt làm Merkle tree hiệu quả.

Pitfall 2 — Không xử lý số lá lẻ → cây không cân bằng

-- SAI: để số lá lẻ, node cuối không có cặp → null pointer hoặc cây không đầy đủ
for i <- 0 to nodes.length-1 step 2:
    left <- nodes[i]
    right <- nodes[i+1]   -- nếu i+1 vượt biên → crash

-- ĐÚNG: pad node lẻ về chẵn ở mỗi tầng (không cần tổng số lá là lũy thừa của 2)
if nodes.length mod 2 = 1:
    nodes.append(nodes.last)    -- duplicate lá cuối

Bitcoin dùng cách pad này (duplicate transaction cuối nếu số lẻ). Cách khác: hash lá đơn với chính nó. Quan trọng là chọn nhất quán một convention — hai node phải dùng cùng convention khi so sánh tree, nếu không root luôn khác dù data giống.

Pitfall 3 — Dùng Merkle tree cho dữ liệu thay đổi liên tục mà không rebuild định kỳ

-- CẢNH BÁO: Merkle tree không tự update khi data thay đổi
-- Phải rebuild (O(n)) hoặc maintain cây với update (O(log n)/update)
-- Cassandra chỉ chạy repair theo lịch, không real-time

Cassandra không duy trì Merkle tree real-time — quá tốn kém với write throughput cao. Thay vào đó, repair chạy theo lịch (thường hàng tuần). Trong khoảng thời gian giữa các lần repair, replica có thể diverge nhỏ — đây là acceptable trong mô hình AP eventual consistency.

6. Liên hệ các bài khác

• Crypto hash: Merkle tree dựa hoàn toàn vào tính chất của hash function — collision resistance đảm bảo "root giống = data giống" với xác suất cực cao. SHA-256 dùng trong Bitcoin Merkle tree; MurmurHash3 dùng trong Cassandra anti-entropy (không cần crypto-strength, chỉ cần phân phối đều và nhanh).
• Merkle proof: bài đó đào sâu vào Merkle proof — chứng minh rằng một block cụ thể thuộc tập dữ liệu mà chỉ cần O(log n) hash (không cần cả cây). Đây là cơ chế SPV trong Bitcoin light client và Ethereum state proof.
• Consistent hashing: quyết định key nào vào node nào. Merkle tree quyết định cách hai node kiểm tra xem họ có đồng thuận không. Cả hai cùng nhau tạo ra cơ chế anti-entropy của Cassandra.
• Case study Cassandra & etcd: xem cách Cassandra triển khai nodetool repair dùng Merkle tree trong thực tế, bao gồm streaming protocol và repair scheduling.

📚 Deep Dive

Tóm tắt

• Merkle tree: lá = hash(data), node trong = hash(con_trái + con_phải), root = đại diện toàn bộ tập dữ liệu.
• So sánh hai replica: nếu root giống → giống hệt; nếu khác → đệ quy xuống nhánh có hash khác → tìm lá khác biệt trong O(k log n) với k lá khác.
• Anti-entropy: nodes trao đổi root (vài byte), chỉ drill down khi cần — tránh truyền toàn bộ O(n) data qua mạng.
• Hash của hash (không phải hash lại data) là điểm mấu chốt cho hiệu quả incremental update.
• Xử lý số lá lẻ và dùng nhất quán một convention là điều kiện để hai node build cùng tree.
• Dùng trong: Cassandra anti-entropy repair, Git object model, Bitcoin block verification, IPFS content addressing.

Tự kiểm tra

Bài tiếp theo: Vector clock — thứ tự nhân quả sự kiện