Bài 47: Redlock + Tranh Luận Kleppmann vs antirez

Sau bài này bạn sẽ:

• Giải thích được điểm yếu fault-tolerance của single-instance Redis lock khi node chết hoặc failover.
• Mô tả đầy đủ thuật toán Redlock: N instance độc lập, majority quorum, tính valid time.
• Trình bày được hai luồng lập luận trong tranh luận 2016: Kleppmann (timing assumptions không an toàn) và antirez (practical đủ dùng).
• Phân biệt khi nào Redlock là lựa chọn hợp lý và khi nào nên dùng consensus system (Zookeeper, etcd) hoặc DB lock thay thế.
• Nhận biết các anti-pattern phổ biến khi áp dụng Redlock.

Các bài 42–45 xây distributed lock trên một Redis node: SET lock:resource token NX EX ttl. Cơ chế này đủ cho nhiều use case nhưng có một điểm yếu về fault tolerance:

Kịch bản 1 — Redis node chết:

T=0s   Client A acquire lock thành công. Lock lưu trong Redis node R1.
T=5s   R1 crash (hardware failure, OOM kill, reboot).
T=5s+  Lock state mất theo R1.
T=6s   Client B acquire lock thành công trên R1 mới (hoặc R1 restart rỗng).
       → A và B cùng giữ lock.

Kịch bản 2 — Master-replica với async replication:

T=0s   Client A acquire lock trên master. Replication async đến replica.
T=1s   Master crash TRƯỚC KHI replication hoàn tất.
T=2s   Replica được promote lên master (failover).
       Replica CHƯA có lock state của A (chưa kịp nhận replication).
T=3s   Client B acquire lock trên master mới thành công.
       → A và B cùng giữ lock.

Đây là hệ quả trực tiếp của async replication: Redis ưu tiên performance, replica có thể lag vài ms. Trong cửa sổ thời gian đó, failover có thể xảy ra.

Redlock đề xuất một cách tiếp cận khác: thay vì tin vào một node, yêu cầu majority của nhiều node độc lập đồng ý.

Redlock được antirez đề xuất trong Redis documentation. Ý tưởng cốt lõi:

• Dùng N Redis instance hoàn toàn độc lập — không replication, không cluster với nhau. N thường là số lẻ, ví dụ 5.
• Để acquire lock, client phải SET NX EX thành công trên majority (≥ N/2 + 1, tức ít nhất 3/5 instance).
• Toàn bộ quá trình acquire majority phải hoàn tất trước khi TTL hết.
• Thời gian lock còn hợp lệ (valid time) = TTL ban đầu − thời gian đã mất để acquire majority.
• Release: gửi DEL đến tất cả N instance, bất kể instance nào đã acquire thành công hay không.

Tại sao N phải lẻ? Để luôn có một majority rõ ràng: với N=5, majority là 3. Với N=4, majority vẫn là 3 nhưng nếu mạng bị phân vùng thành 2+2 thì cả hai phía đều không đạt majority — liveness tốt hơn N=4 khi dùng N=5.

Tại sao cần majority thay vì tất cả? Nếu yêu cầu tất cả N/N thì một node chết là đủ để lock không bao giờ acquire được — liveness kém. Majority (quorum) là điểm cân bằng giữa fault tolerance và liveness.

Thuật toán Redlock cho N=5 instance (R1…R5), TTL = 10 000 ms:

Bước 1: Lấy timestamp hiện tại.
        start_ms = current_time_ms()

Bước 2: Cố acquire lock trên từng instance tuần tự.
        Với mỗi Ri: SET lock:resource <unique_token> NX PX 10000
        Dùng timeout nhỏ cho mỗi request (vd 5–50 ms) để không bị block
        khi instance chậm hoặc không phản hồi.

Bước 3: Đếm số instance acquire thành công (acquired_count).
        Tính elapsed = current_time_ms() - start_ms.

Bước 4: Kiểm tra điều kiện lock thành công:
        - acquired_count >= 3   (majority, N/2+1)
        - elapsed < TTL          (còn thời gian hợp lệ)

        Nếu thỏa mãn:
          valid_time = TTL - elapsed  (thời gian lock còn dùng được)
          → Lock thành công, client có valid_time ms để dùng lock.

        Nếu không thỏa mãn (acquired_count < 3 hoặc elapsed >= TTL):
          → Lock thất bại → gửi DEL đến TẤT CẢ 5 instance để cleanup.

Bước 5 (Release): Khi xong hoặc khi thất bại,
        gửi DEL (có ownership check bằng Lua, như bài 43) đến tất cả N instance.

Đoạn code Python minh họa acquire Redlock (simplified, không production-ready):

import time
import uuid
import redis

# 5 Redis instance độc lập
instances = [
    redis.Redis(host="r1.internal", port=6379),
    redis.Redis(host="r2.internal", port=6379),
    redis.Redis(host="r3.internal", port=6379),
    redis.Redis(host="r4.internal", port=6379),
    redis.Redis(host="r5.internal", port=6379),
]

TTL_MS = 10_000     # 10 giây
ACQUIRE_TIMEOUT_MS = 50   # timeout mỗi instance
MAJORITY = len(instances) // 2 + 1   # 3

def acquire_redlock(resource: str) -> tuple[str | None, int]:
    """
    Trả về (token, valid_time_ms) nếu thành công, (None, 0) nếu thất bại.
    """
    token = str(uuid.uuid4())
    start_ms = int(time.monotonic() * 1000)
    acquired = []

    for r in instances:
        try:
            ok = r.set(
                f"lock:{resource}", token,
                nx=True,
                px=TTL_MS,
                # socket_timeout tương đương ACQUIRE_TIMEOUT_MS
            )
            if ok:
                acquired.append(r)
        except redis.RedisError:
            pass  # instance chết hoặc không phản hồi — bỏ qua

    elapsed_ms = int(time.monotonic() * 1000) - start_ms
    valid_time = TTL_MS - elapsed_ms

    if len(acquired) >= MAJORITY and valid_time > 0:
        return token, valid_time
    else:
        # Acquire thất bại — cleanup tất cả
        release_redlock(resource, token)
        return None, 0

RELEASE_LUA = """
if redis.call('GET', KEYS[1]) == ARGV[1] then
    return redis.call('DEL', KEYS[1])
end
return 0
"""

def release_redlock(resource: str, token: str) -> None:
    for r in instances:
        try:
            r.eval(RELEASE_LUA, 1, f"lock:{resource}", token)
        except redis.RedisError:
            pass  # Best-effort, TTL sẽ tự cleanup

Lưu ý valid_time: client phải đảm bảo hoàn thành tác vụ trong khoảng thời gian này. Nếu tác vụ cần 2 giây nhưng valid_time chỉ còn 500 ms, client không nên tiếp tục — lock gần hết hạn.

Câu hỏi thường gặp: tại sao không dùng 1 Redis với 4 replica (5 node total) thay vì 5 instance riêng biệt?

Vấn đề nằm ở async replication: khi master nhận SET lock NX thành công, lock tồn tại trên master trước, replica nhận sau (lag vài ms đến vài trăm ms). Nếu master chết ngay sau khi SET nhưng trước khi replication hoàn tất:

• Replica mới được promote không có lock state.
• Client khác có thể acquire lock trên master mới.
• Kết quả: 2 client cùng giữ lock — vi phạm mutual exclusion.

Với N instance hoàn toàn độc lập:

• Mỗi instance là một process riêng, không liên quan đến nhau.
• Để lock bị mất, phải có đồng thời majority instance chết — xác suất thấp hơn nhiều.
• Một instance chết không ảnh hưởng state của 4 instance còn lại.

Trade-off: cần vận hành N process riêng biệt, cost cao hơn, phức tạp hơn. Đây là một trong những lý do Redlock ít được dùng trong thực tế — chi phí infra cao so với lợi ích tăng thêm.

Tháng 2/2016, Martin Kleppmann đăng bài "How to do distributed locking" (martin.kleppmann.com). Lập luận chính:

Lý do 1 — Timing assumptions

Redlock tính valid_time = TTL - elapsed dựa vào đồng hồ hệ thống. Thuật toán ngầm giả định rằng đồng hồ của các node Redis và đồng hồ của client đều tiến với tốc độ tương đối đồng đều, và rằng elapsed time đo được phản ánh đúng thời gian thực tế đã trôi qua.

Kleppmann chỉ ra các tình huống phá vỡ giả định này:

• Clock jump (NTP sync): NTP có thể điều chỉnh đồng hồ hệ thống tiến hoặc lùi vài giây. Nếu đồng hồ của một Redis instance bị "nhảy" tiến 10 giây, TTL của lock đó hết trước thực tế.
• Network delay: Gói tin từ client đến instance R3 mất 500 ms trong khi đến R1 mất 1 ms. elapsed đo ở client không phản ánh thời điểm mỗi lock thực sự bắt đầu trên mỗi instance.

Lý do 2 — Process pause (GC pause)

Đây là lập luận mạnh nhất của Kleppmann. Kịch bản:

T=0ms   Client A acquire Redlock thành công. valid_time = 9 000 ms.
T=100ms Client A bắt đầu tác vụ.
T=500ms JVM GC pause bắt đầu (full GC, "stop-the-world").
        Process A bị đông cứng hoàn toàn.
T=9 500ms  Lock expire trên tất cả 5 Redis instance (đã hết TTL 10s).
T=9 600ms  Client B acquire Redlock thành công.
T=10 000ms GC pause kết thúc. Process A "wake up".
           A kiểm tra valid_time: vẫn thấy ~8 500 ms còn lại
           (tính từ lúc acquire, không tính thời gian GC).
T=10 001ms A VÀ B cùng tác vụ — 2 writer.

Process pause không chỉ xảy ra ở GC. Có thể do: SIGSTOP, virtualization overhead, CPU scheduler không cho process chạy, swap-out khi memory pressure, v.v.

Kết luận của Kleppmann

Redlock không cung cấp fencing token tăng đơn điệu (monotonically increasing). Bài 46 đã phân tích: để correctness lock thực sự an toàn, resource cần có cơ chế reject thao tác từ lock cũ dựa trên token ordering. Redlock không có cơ chế đó, nên ngay cả khi acquire thành công, không có gì ngăn được kịch bản process pause ở trên.

Kleppmann kết luận: nếu chỉ cần efficiency lock (tránh làm việc thừa, không phải correctness), single-instance Redis lock đủ dùng, không cần Redlock. Nếu cần correctness, phải dùng fencing token + consensus system.

antirez phản hồi trong bài "Is Redlock safe?" (antirez.com, 2016). Các điểm chính:

Về timing assumptions

antirez thừa nhận Redlock có timing assumptions, nhưng lập luận rằng mọi distributed system ở mức nào đó đều dựa vào timing. Consensus algorithm như Paxos hay Raft cũng có timeout để detect crash, không phải không có giả định về thời gian. Câu hỏi không phải "có timing assumption không" mà là "assumption đó có thực tế không?"

antirez cho rằng với NTP được cấu hình đúng (không cho phép step-adjustment lớn, chỉ slew), clock drift trong phạm vi Redlock handle được. Các hệ thống production với NTP chuẩn thường có drift dưới 1–2 ms/giây — nhỏ so với TTL hàng giây.

Về process pause

antirez thừa nhận GC pause là vấn đề thực, nhưng lập luận rằng:

1. Kịch bản GC pause dài hơn TTL không phải là điều kiện "normal operation" — nếu GC pause thường xuyên vượt TTL, hệ thống đó đã có vấn đề nghiêm trọng cần fix ở chỗ khác.
2. Nếu application có yêu cầu correctness nghiêm ngặt đến mức không chịu được bất kỳ window race nào dù nhỏ, thì không nên dùng bất kỳ lock TTL nào — kể cả Zookeeper session timeout cũng có window.

Về fencing token

antirez đồng ý rằng fencing token là cách tốt để đảm bảo correctness. Nhưng ông lập luận: Redlock có thể kết hợp với incrementing token. Nếu resource side cần fencing, có thể dùng Redlock để coordinate + tự cấp một token tăng dần riêng. Hơn nữa, nhiều use case thực tế không cần correctness mức đó — chỉ cần giảm xác suất double processing xuống rất thấp.

Kết luận của antirez

Redlock an toàn cho phần lớn use case thực tế ở mức efficiency lock. Với hệ thống cần correctness tuyệt đối, antirez đồng ý là nên dùng consensus system, nhưng Redlock vẫn có chỗ đứng khi cần fault tolerance cao hơn single-instance mà không cần correctness tuyệt đối.

Đọc kỹ cả hai bài, điểm thú vị là Kleppmann và antirez thực ra đồng ý về nhiều thứ. Bất đồng nằm ở phần nhỏ hơn:

Điểm bất đồng thực sự hẹp hơn tưởng: cả hai đều đồng ý rằng lock TTL không đủ cho correctness, và correctness nên dùng consensus. Câu hỏi là: Redlock có thêm giá trị thực sự cho efficiency lock hay không, khi xét đến timing assumptions và process pause?

Kleppmann nói: timing assumptions của Redlock không đáng tin, cộng với process pause là failure mode thực, nên Redlock không thêm safety đáng kể — chưa kể complexity cao hơn nhiều so với single-instance.

antirez nói: trong điều kiện thực tế (NTP chuẩn, GC pause không vượt TTL thường xuyên), Redlock an toàn hơn single-instance một cách có ý nghĩa — và đó là trade-off hợp lý cho use case cần FT.

Không có kết luận "ai đúng tuyệt đối". Quyết định phụ thuộc vào requirements cụ thể.

Nếu use case yêu cầu correctness — lock fail dẫn đến data corruption, double payment, oversell — thì cả single-instance Redis lock lẫn Redlock đều không đủ một mình. Các lựa chọn thay thế:

Zookeeper

ZooKeeper dùng ZAB (ZooKeeper Atomic Broadcast) — một consensus protocol tương tự Paxos. Để acquire lock, client tạo một sequential ephemeral znode (/locks/resource/lock-). ZK tự gán số thứ tự tăng dần (lock-0000001, lock-0000002, …). Client có số nhỏ nhất là lock holder.

• Số thứ tự znode là fencing token tự nhiên — tăng đơn điệu, đảm bảo bởi consensus.
• Ephemeral node tự xóa khi session của client mất — tương đương TTL nhưng không có timing assumption về clock.
• Không có vấn đề async replication — tất cả ghi phải được majority ZK node confirm (ZAB).

etcd

etcd dùng Raft consensus. Lock được implement qua etcd lease + key. Revision number của key tăng đơn điệu mỗi khi được tạo — đây là fencing token. Resource side có thể reject thao tác với revision number thấp hơn revision cao nhất đã thấy.

# etcd3 Python client
import etcd3

client = etcd3.client()

# Tạo lease 10 giây
lease = client.lease(ttl=10)

# Acquire lock — put key với lease
# lock_key được assign revision (etcd global monotonic counter)
lock = client.lock("resource", ttl=10)
lock.acquire()

# Revision của lock key = fencing token
# Resource side so sánh revision để reject stale write

Database lock

Với nhiều use case, DB đủ và đơn giản hơn:

• PostgreSQL advisory lock: pg_try_advisory_lock(key) — session-scoped, tự release khi connection đóng.
• SELECT FOR UPDATE: row-level lock trong transaction — an toàn, atomic với business logic cùng transaction.
• Conditional UPDATE: UPDATE table SET ... WHERE version = $expected_version — optimistic locking, không cần lock mechanism riêng.

Nếu tác vụ cần lock đã làm việc với DB (như payment, inventory), DB lock thường là lựa chọn tốt nhất — không thêm hệ thống, không thêm failure mode.

Consul

Consul session-based lock: tương tự ZK nhưng dùng Raft. Session có TTL, tự release khi agent không còn heartbeat. Ít phổ biến hơn ZK/etcd cho distributed lock trong cộng đồng backend, nhưng là lựa chọn tự nhiên nếu đã dùng Consul cho service discovery.

Không tự implement Redlock từ đầu — timing logic (đo elapsed, tính valid_time, xử lý partial failure) rất dễ sai. Dùng library đã có:

node-redlock ví dụ sử dụng:

import Redlock from "redlock";
import { createClient } from "redis";

const clients = [
  createClient({ url: "redis://r1:6379" }),
  createClient({ url: "redis://r2:6379" }),
  createClient({ url: "redis://r3:6379" }),
  createClient({ url: "redis://r4:6379" }),
  createClient({ url: "redis://r5:6379" }),
];

await Promise.all(clients.map(c => c.connect()));

const redlock = new Redlock(clients, {
  driftFactor: 0.01,   // clock drift tolerance: 1% của TTL
  retryCount: 3,
  retryDelay: 200,     // ms giữa các lần retry
  retryJitter: 50,
});

// Acquire lock 10 giây
const lock = await redlock.acquire(["lock:resource"], 10_000);

try {
  // Tác vụ cần lock
  await processOrder();
} finally {
  await lock.release();
}

driftFactor là hệ số an toàn cho clock drift: valid_time thực tế = TTL − elapsed − (TTL × driftFactor) − 2ms. node-redlock tự xử lý toàn bộ majority logic và cleanup khi acquire thất bại.

Xem xét Redlock khi

• Đây là efficiency lock (lock fail → chỉ tốn compute thừa, không phá data).
• Single Redis node chết là failure mode thực sự cần handle (vd: không có Redis replication, chạy trên bare-metal không HA).
• Chấp nhận chi phí vận hành 5 Redis instance riêng biệt.
• Đã loại trừ consensus system vì quá nặng với use case.

Không dùng Redlock khi

• Correctness critical: dùng Zookeeper/etcd (có fencing token đảm bảo bởi consensus) hoặc DB lock.
• Efficiency lock đơn giản: single-instance Redis lock đủ, Redlock là over-engineering.
• Không muốn vận hành 5 Redis instance: complexity không xứng với lợi ích.
• Môi trường có GC pause thường xuyên > TTL: timing assumption bị phá vỡ, Redlock không giúp ích.
• Đã có Redis Cluster hoặc Sentinel: Cluster/Sentinel không tương đương N instance độc lập — cần điều chỉnh thiết kế hoặc dùng option khác.

Thực tế: Redlock ít xuất hiện trong production hơn tài liệu gợi ý. Hầu hết team chọn hoặc single-instance Redis (efficiency) hoặc Zookeeper/etcd/DB (correctness), bỏ qua tầng giữa là Redlock.

• Dùng Redlock cho correctness mà không có fencing token. Redlock không cung cấp fencing token native. Chỉ vì acquire 3/5 instance không đảm bảo không có process pause sau đó. Nếu cần correctness, phải có fencing ở phía resource — Redlock một mình không đủ.
• Tự implement Redlock. Timing logic (đo elapsed với monotonic clock, tính valid_time, xử lý partial acquire, cleanup on failure) có nhiều edge case. Dùng library đã test và maintain.
• Dùng Redlock với Redis Cluster hoặc Sentinel. Redis Cluster không tương đương N instance độc lập cho Redlock. Slot sharding và async replication trong Cluster vẫn có vấn đề failover như single-master. Redlock yêu cầu instance thực sự độc lập.
• Ignore valid_time sau khi acquire. Client phải kiểm tra valid_time còn đủ để hoàn thành tác vụ trước khi bắt đầu. Acquire thành công với valid_time = 50 ms rồi chạy tác vụ 2 giây là sai logic.
• Dùng Redlock khi DB transaction đủ. Nếu tác vụ cần lock đã bao gồm DB write (payment, inventory), DB transaction với SELECT FOR UPDATE hoặc conditional update đơn giản và an toàn hơn nhiều.

1. Giải thích tại sao dùng 1 Redis master + 4 replica KHÔNG tương đương Redlock với 5 instance độc lập. Kịch bản nào master + replica vẫn có thể dẫn đến 2 client cùng giữ lock?
2. Vẽ timeline cho kịch bản GC pause khiến Redlock không đảm bảo safety: nêu rõ T bắt đầu GC, T lock expire, T client B acquire, T GC kết thúc.
3. Một team đang chạy cron job export report mỗi 5 phút, dùng Redis lock để tránh 2 instance chạy cùng lúc. Export mất khoảng 30 giây, chỉ làm tăng load DB (không ảnh hưởng data). Họ đang dùng single Redis. Có nên upgrade lên Redlock không? Giải thích.
4. Tại sao Zookeeper sequential znode và etcd revision number được gọi là fencing token "built-in"? So sánh với cách implement fencing token thủ công dùng Redis INCR (bài 46).
5. Trong đoạn code Python acquire_redlock ở bài này, tại sao dùng time.monotonic() thay vì time.time() để đo elapsed? Điều gì xảy ra nếu dùng time.time()?

Đáp án gợi ý

1. Async replication: master nhận SET NX thành công, replication chưa kịp reach replica. Nếu master crash ngay sau đó và replica được promote, replica không có lock state. Client B acquire lock trên replica-mới-thành-master thành công. Cả A (vẫn đang xử lý) và B cùng giữ lock.
2. T=0: Client A acquire Redlock (TTL=10s, valid_time=9s). T=1s: GC pause bắt đầu (full GC). T=10s: TTL hết trên tất cả instance. T=10.5s: Client B acquire Redlock thành công. T=11s: GC kết thúc — A wake up, kiểm tra valid_time = 9s - 1s elapsed = 8s (tính theo monotonic clock của A, nhưng thực tế 10s đã trôi qua). A tiếp tục tác vụ → 2 writer.
3. Không cần Redlock. Đây là efficiency lock: export chạy 2 lần chỉ tốn thêm DB load, không làm sai data. Single Redis lock đủ. Ngay cả khi Redis chết và 2 instance cùng export một lần, hậu quả chỉ là DB load tăng — acceptable. Redlock tốn 5 instance, tăng complexity mà không giải quyết vấn đề quan trọng.
4. ZK sequential znode: mỗi lock attempt tạo znode với số tự động gán bởi ZK server (ZAB consensus) — tăng đơn điệu, không thể giả mạo, đảm bảo by consensus quorum. etcd revision: global counter tăng mỗi lần có write, đảm bảo bởi Raft. Với Redis INCR thủ công: INCR là atomic nhưng Redis là single-instance — nếu Redis restart không có persistence, counter reset; nếu master-replica và master chết thì counter có thể không up-to-date. Consensus system đảm bảo monotonicity kể cả khi có node failure.
5. time.monotonic() là monotonically increasing clock không bị ảnh hưởng bởi NTP adjustment hay system clock change — chỉ tăng, không bao giờ nhảy lùi. time.time() là wall clock, có thể bị NTP điều chỉnh tiến hoặc lùi. Nếu NTP nhảy đồng hồ lùi trong quá trình acquire, elapsed tính được sẽ âm hoặc nhỏ hơn thực tế → valid_time tính sai → lock được coi là còn hợp lệ dù thực tế đã hết.

Bài tiếp theo

Bài 48 chuyển sang một vấn đề liên quan nhưng tiếp cận khác: chống double payment với idempotency key — khi distributed lock là overkill và idempotency + DB constraint là đủ.

Tham khảo

• Martin Kleppmann — How to do distributed locking (2016)
• antirez — Is Redlock safe? (2016)
• Redis Docs — Distributed Locks with Redis (Redlock)
• node-redlock — Redlock implementation cho Node.js
• ZooKeeper Recipes — Distributed Lock
• etcd — Concurrency API (lease, lock, revision)