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 để đạt AP (luôn ghi được, chấp nhận eventual consistency): consistent hashing chia dữ liệu lên ring, tunable quorum cho chỉnh mức nhất quán theo từng request, gossip lan truyền trạng thái membership, Merkle tree sửa chênh lệch giữa các replica. 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. Cần luôn ghi được thì chọn kiểu Cassandra; cần không bao giờ đọc phải bản cũ thì chọn kiểu etcd.

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 ghép bốn thuật toán

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

Cassandra sinh ra để lưu dữ liệu cỡ petabyte trên nhiều node mà không có single point of failure. Trang case study của dự án nói Netflix quản lý hàng petabyte dữ liệu trên Cassandra và phải truy cập được trong vài mili giây. Bốn yêu cầu: phân mảnh (chia đều dữ liệu lên các node), nhất quán (phát hiện và sửa replica chênh lệch), membership (mỗi node biết node nào đang sống) và chịu lỗi (vẫn chạy khi một số node chết).

Hình dung Cassandra như hội chợ không ban tổ chức: gian hàng tự biết hàng xóm, giữ bản sao hàng của nhau, thỉnh thoảng đối chiếu sổ. etcd giống hội đồng có chủ tịch: mọi quyết định đi qua một người, người đó mất thì bầu lại.

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 [-2^63, 2^63) (hash Murmur3), 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), để tải chia đều, kể cả khi các node có phần cứng khác nhau.

-- Cassandra token assignment (đơn giản hóa)
-- Mỗi đoạn có dạng (prev, token]: không chồng nhau, kể cả chỗ quay về 0
-- Node A: owns (100, 400], (700, 900]    (2 vnode)
-- Node B: owns (999, 100] (quay vòng, gồm điểm 0), (400, 700]   (2 vnode)
-- Node C: owns (900, 999]                (1 vnode)
-- (số nhỏ cho dễ nhìn; token thật nằm trong [-2^63, 2^63))

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

Node nhận request từ client rồi điều phối các replica gọi là coordinator; getCoordinator ở trên chọn nó theo token. Khi thêm node mới vào Cassandra cluster, chỉ vnode của node mới cần stream dữ liệu từ node kế tiếp, phần còn lại không bị ảnh hưởng. Đó là tính chất "chỉ dời cỡ K/(N+1) key" của consistent hashing ở bài 01 và mini-challenge vừa xong.

Replication factor (RF, số bản sao): Cassandra không chỉ lưu 1 bản. Cấu hình phổ biến là 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:

Hệ thống nhiều datacenter thường dùng LOCAL_QUORUM cho cả đọc lẫn ghi: nhất quán trong từng datacenter, và không bị chặn 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=write_request_timeout)

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

Cassandra thiên về AP nhờ consistency tunable: ghi QUORUM thành công khi đủ đa số, ngay cả khi một số replica còn chậm, và replica chậm được anti-entropy sửa sau. Nhưng chính ở mức QUORUM, khi mạng chia mà không gom đủ đa số, ghi bị từ chối (hành xử như CP).

Thử ngẫmhệ thống dùng LOCAL_QUORUM cho cả đọc và ghi, ghi xong ở datacenter A. Client đọc ở datacenter B ngay sau đó có chắc thấy bản mới không, và khi nào thì thấy?

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 không khả thi.

Cassandra dùng gossip (bài 05): mỗi giây, mỗi node gossip với 1 node live ngẫu nhiên (có thể thêm 1 node unreachable và 1 seed theo xác suất) 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)   -- mô hình lý thuyết; thực tế 1 node live + tối đa 2 đích phụ
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

-- Lý tưởng: ~log4(1000) ≈ 5 vòng nếu mỗi vòng 3 peer (cỡ 10 vòng nếu chỉ 1 peer); thực tế vài vòng cuối chậm hơn

Gossip cũng chạy Phi Accrual Failure Detector: thay vì "timeout là dead", nó tính điểm nghi ngờ φ từ lịch sử heartbeat: heartbeat trễ hơn thường lệ càng nhiều thì φ càng cao, vượt ngưỡng (phi_convict_threshold, mặc định 8) mới coi là chết. Nhờ vậy khi mạng tạm thời chậm thì ít báo nhầ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):

Thứ đắt trong anti-entropy là dữ liệu truyền, không phải phép so. Mỗi replica dựng Merkle tree cho token range của mình rồi gửi cây hash đó (nhỏ hơn dữ liệu rất nhiều) cho bên điều phối; bên đó so các cây, tìm đoạn lệch ngay trên máy mình, và chỉ stream những đoạn lệch.

Thay vì so sánh từng row (hàng triệu row), Merkle tree cho phép xác định đoạn token range bị chênh lệch trong cỡ log N lần so hash, rồi chỉ đồng bộ dữ liệu ở đoạn đó (cây của Cassandra có độ sâu giới hạn, nên mỗi lá phủ cả một đoạn row).