Case study — Cassandra ring & etcd Raft

TL;DR: Cassandra và etcd đều là hệ phân tán nổi tiếng, nhưng chúng đặt cược khác nhau trên tam giác CAP. Cassandra ghép bốn thuật toán từ module này — consistent hashing phân mảnh dữ liệu lên ring, tunable quorum cho phép điều chỉnh mức nhất quán theo request, gossip lan truyền trạng thái membership, Merkle tree sửa chênh lệch giữa các replica — để đạt AP: luôn ghi được, chấp nhận eventual consistency. etcd chọn CP: Raft đảm bảo mọi đọc/ghi đều nhất quán mạnh, đổi lấy việc mất availability khi mất quorum. Bài học từ hai hệ thống: không có thiết kế "tốt hơn" — chỉ có thiết kế phù hợp với bài toán.

AP — consistent hashing + tunable quorum + gossip + Merkle tree

CP — Raft consensus cho config/service-discovery nhất quán mạnh

Phần A — Cassandra: bốn thuật toán ghép lại

1. Bài toán: dữ liệu người dùng ở quy mô Netflix

Apache Cassandra được thiết kế để lưu hàng trăm terabyte dữ liệu trải trên hàng trăm đến hàng nghìn node, không có single point of failure. Netflix dùng Cassandra để lưu viewing history, bookmark và user preferences — hệ thống phải luôn ghi được ngay cả khi một datacenter mất kết nối.

Yêu cầu:

1. Phân mảnh — 100 TB dữ liệu phải phân bố đều trên hàng trăm node.
2. Nhất quán — replica phải đồng bộ, phát hiện và sửa chênh lệch.
3. Membership — mỗi node cần biết toàn bộ cluster đang có node nào, node nào đang chết.
4. Fault tolerance — vẫn hoạt động khi một số node fail.

Cassandra giải quyết bốn yêu cầu này bằng bốn thuật toán từ module này:

2. Consistent hashing: token ring và virtual node

Cassandra dùng token ring — mỗi key được hash thành token trong không gian [0, 2^64), mỗi node sở hữu một khoảng token. Mỗi node vật lý được nhân bản thành nhiều virtual node (vnode) — mặc định 16 vnode mỗi node từ Cassandra 4.0 (bản cũ dùng 256) — để đảm bảo phân bố tải đều ngay cả khi node có phần cứng khác nhau.

-- Cassandra token assignment (đơn giản hóa)
-- Node A: owns tokens [100, 400), [700, 900)   (2 vnode)
-- Node B: owns tokens [0, 100), [400, 700)      (2 vnode)
-- Node C: owns tokens [900, 2^64) wrap [0, 0)   (1 vnode)

function getCoordinator(partitionKey):
    token <- murmur3Hash(partitionKey)    -- Cassandra dùng Murmur3
    return lookupRing(ring, token)        -- binary search, O(log(N×vnode))

Khi thêm node mới vào Cassandra cluster, chỉ vnode của node mới cần streaming data từ node kế tiếp — phần còn lại không bị ảnh hưởng. Đây chính là tính chất K/N key di chuyển của consistent hashing từ bài 01 và mini-challenge vừa xong.

Replication factor (RF): Cassandra không chỉ lưu 1 bản — mặc định RF=3, nghĩa là mỗi key được lưu trên 3 node vật lý kế tiếp nhau trên ring. Khi node chết, 2 bản replica còn lại vẫn phục vụ được.

3. Tunable quorum: CAP tradeoff theo request

Cassandra cho phép client chỉ định consistency level cho từng request — đây là ứng dụng trực tiếp của quorum R+W>N từ bài 02:

Netflix thường dùng LOCAL_QUORUM cho đọc và LOCAL_QUORUM cho ghi — đảm bảo nhất quán trong mỗi datacenter nhưng không block khi một datacenter bị cô lập.

-- Write path với QUORUM (RF=3, cần 2 replica xác nhận)
coordinator <- getCoordinator(partitionKey)
replicas    <- getReplicaNodes(ring, partitionKey, replicationFactor=3)

-- Ghi song song đến cả 3 replica
for each replica trong replicas:
    sendWriteAsync(replica, mutation)

-- Chờ đủ quorum (2/3)
waitForAcks(count=2, timeout=10ms)

-- Nếu đủ 2 ack trong timeout: success
-- Nếu không: timeout error (replica thứ 3 vẫn được ghi async sau đó)

Đây chính là cơ chế AP của Cassandra: ghi thành công khi đủ quorum, ngay cả khi một số replica lag sau. Replica lag sẽ được sửa bởi anti-entropy.

4. Gossip: membership và failure detection

Mỗi node Cassandra cần biết toàn bộ cluster — node nào đang sống, node nào đang chết, load của từng node là bao nhiêu. Với cluster 1 000 node, broadcast toàn bộ mỗi giây là không khả thi.

Cassandra dùng Gossip protocol (bài 05) — mỗi giây, mỗi node chọn ngẫu nhiên 1-3 node và trao đổi thông tin về trạng thái của mọi node mà cả hai biết. Sau O(log N) vòng, thông tin lan khắp cluster:

-- Cassandra gossip cycle (mỗi giây trên mỗi node)
peers <- selectRandom(cluster, count=3)   -- chọn 3 node ngẫu nhiên
for each peer trong peers:
    myState    <- localNodeState()        -- version, load, tokens, status
    peerGossip <- exchange(peer, myState)
    mergeState(peerGossip)                -- cập nhật bảng trạng thái local

-- Sau ~log2(1000) ≈ 10 vòng gossip: mọi node biết trạng thái mọi node khác

Gossip cũng chạy Phi Accrual Failure Detector — thay vì "timeout = dead", tính xác suất node thực sự chết dựa trên lịch sử heartbeat. Điều này tránh false positive khi network tạm thời chậm.

5. Merkle tree: anti-entropy repair

Dù có quorum, replica vẫn có thể chênh lệch theo thời gian (network partition tạm thời, node crash giữa write). Cassandra chạy anti-entropy repair định kỳ bằng Merkle tree (bài 03):

sequenceDiagram
    participant N1 as Node 1
    participant N2 as Node 2
    Note over N1,N2: Anti-entropy repair
    N1->>N1: Build Merkle tree<br/>cho token range mình sở hữu
    N2->>N2: Build Merkle tree<br/>cho cùng token range
    N1->>N2: Gửi Merkle root
    N2->>N1: So sánh root: khác nhau!
    N1->>N2: Gửi subtree trái
    N2->>N1: Subtree trái trùng khớp
    N1->>N2: Gửi subtree phải
    N2->>N1: Subtree phải khác! Gửi diff
    N1->>N1: Nhận diff, sync lại rows bị thiếu

Thay vì so sánh từng row (hàng triệu row), Merkle tree cho phép xác định đúng đoạn token range bị chênh lệch trong O(log N) so sánh hash, rồi chỉ sync dữ liệu ở đoạn đó.

Phần B — etcd: Raft cho config nhất quán mạnh

6. Bài toán: source of truth của Kubernetes

etcd là key-value store phân tán được dùng làm backing store cho Kubernetes — lưu toàn bộ trạng thái cluster: pod, deployment, service, configmap, secret. Mỗi thay đổi trong Kubernetes (thêm pod, scale deployment, cập nhật config) phải được ghi vào etcd và được mọi control plane node nhìn thấy nhất quán.

Yêu cầu khác hoàn toàn với Cassandra:

• Strong consistency bắt buộc: hai controller đọc config cùng lúc phải thấy cùng một giá trị — không thể có split-brain.
• No stale read: nếu một node write replicas=5, node khác đọc ngay sau phải thấy 5, không phải 3.
• Chấp nhận giảm availability: nếu mất quorum (mất hơn N/2 node), etcd từ chối phục vụ thay vì trả về data có thể stale.

7. Raft trong etcd: leader là single source of truth

etcd triển khai Raft (bài 06) — mọi write phải đi qua leader, được nhân bản vào log của đa số node trước khi commit:

-- etcd write path (Raft)
client gửi PUT /key value đến bất kỳ etcd node
    if node không phải leader: redirect về leader

-- Leader xử lý:
leader.log.append(entry={term, index, key, value})
-- Gửi AppendEntries đến tất cả follower song song
for each follower trong cluster:
    sendAppendEntries(follower, entry)

-- Chờ đa số xác nhận (3/5 node = quorum)
waitForAcks(count=majority)

-- Khi đủ quorum: commit entry, apply vào state machine
leader.commitIndex <- entry.index
leader.applyToStateMachine(entry)
-- Báo success cho client

Mọi read cũng đi qua leader (trong chế độ linearizable mặc định) để đảm bảo không có stale read. Đây là điểm khác với Cassandra: Cassandra có thể đọc từ bất kỳ replica nào với ONE, etcd luôn đọc từ leader.

sequenceDiagram
    participant C as Client
    participant L as Leader (etcd)
    participant F1 as Follower 1
    participant F2 as Follower 2
    C->>L: PUT /config replicas=5
    L->>L: Append to log (term=3, idx=42)
    L->>F1: AppendEntries(term=3, idx=42)
    L->>F2: AppendEntries(term=3, idx=42)
    F1->>L: ACK
    F2->>L: ACK
    Note over L: 3/3 acks = quorum đủ → commit
    L->>L: Apply to state machine
    L->>C: OK, revision=42

8. Vì sao etcd chọn CP, không AP như Cassandra

Đây là ứng dụng trực tiếp của CAP theorem:

Kubernetes không thể chịu đựng stale config: nếu scheduler đọc stale và tin rằng pod chưa được schedule trong khi thực ra đã được schedule rồi, nó sẽ schedule lại — dẫn đến duplicate pod. etcd chọn CP để loại trừ khả năng này hoàn toàn.

Cassandra vs etcd: vì sao một chọn AP, một chọn CP

graph TD
    Q0["Bài toán hệ phân tán"] --> Q1{"Stale data có\nchấp nhận được?"}
    Q1 -- "Có — vài giây lag OK" --> Q2{"Scale lớn,\ncần luôn ghi được?"}
    Q2 -- "Có" --> CASS["Cassandra AP\nConsistent hashing +\nTunable quorum +\nGossip + Merkle"]
    Q2 -- "Không" --> Q3["Cân nhắc strong DB\n(PostgreSQL, MySQL)"]
    Q1 -- "Không — must be\nstrongly consistent" --> Q4{"Cluster size\nnhỏ (3-7 node)?"}
    Q4 -- "Có" --> ETCD["etcd CP — Raft\nLinearizable reads/writes\nKubernetes, Consul"]
    Q4 -- "Không" --> Q5["Spanner, CockroachDB\n(distributed SQL + Paxos)"]

Cassandra AP phù hợp khi:

• Dữ liệu có thể được đọc lại (user preferences, activity log) — stale vài giây không gây hại.
• Scale cực lớn (hàng trăm node, petabyte) — Raft không scale tốt ở số node này.
• Cần geo-distribution với low latency writes ở mỗi datacenter.

etcd CP phù hợp khi:

• Config, locking, service discovery — bất kỳ inconsistency nào đều gây hành vi sai.
• Cluster nhỏ (thường 3-5 node) — Raft hoạt động tốt nhất ở quy mô này.
• Đổi được availability lấy correctness.

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

• Consistent hashing: token ring của Cassandra là ứng dụng trực tiếp — bài đó dạy cơ chế, case study này cho thấy cách Cassandra thêm RF và vnode vào.
• Quorum: tunable consistency level (ONE/QUORUM/ALL) của Cassandra là R+W>N ở các mức khác nhau. Bài đó chứng minh R+W>N đảm bảo overlap.
• Merkle tree: anti-entropy repair của Cassandra dùng Merkle tree để tìm đúng đoạn data bị chênh lệch mà không phải so toàn bộ.
• Gossip: Cassandra gossip protocol là ứng dụng chuẩn của epidemic broadcast — membership, failure detection, load balancing info.
• Raft: etcd là reference implementation Raft phổ biến nhất. Bài đó giải thích leader election và log replication — case study này cho thấy Kubernetes dùng nó ra sao.

Tự kiểm tra

Bài tiếp theo: Module 4 — Tổng kết & cheat sheet