Distributed Locking Với Redis: Hiểu Thuật Toán Redlock

Một instance Redis đơn lẻ thì làm lock ngon lành cho app một process, nhưng đến lúc có nhiều service cùng giành một lock - và instance Redis đó có thể chết bất cứ lúc nào - thì SETNX kiểu ngây thơ không còn an toàn nữa. Redlock, do chính người tạo ra Redis đề xuất, là thuật toán để lấy lock phân tán qua nhiều node Redis độc lập, sao cho một node chết hay chậm cũng không âm thầm phá vỡ tính loại trừ lẫn nhau (mutual exclusion).

Đây là kiến thức nâng cao thật sự - hiểu được nó cần nắm vững mấy kiểu lỗi của hệ thống phân tán, chứ không chỉ biết mấy lệnh Redis.

Vì sao một lock Redis là chưa đủ

Một lock cơ bản trông đơn giản vầy:

SET resource:order-42 my-random-value NX PX 30000

Lệnh này chỉ set key nếu nó chưa tồn tại (NX), kèm thời hạn 30 giây (PX) để client bị crash không giữ lock mãi mãi. Vấn đề là node Redis đơn lẻ này chính là single point of failure. Nếu nó sập trước khi replicate cái write đó qua replica, mà replica lại được promote lên làm master, thì client khác có thể lấy được "cùng một" lock - vì master mới chưa từng thấy key đó.

Thuật toán Redlock

Redlock giải quyết bằng cách dùng N master Redis độc lập (implementation tham chiếu dùng 5 node), không replicate hay phối hợp gì với nhau. Client muốn lấy lock sẽ làm theo mấy bước sau:

1. Ghi lại thời gian hiện tại tính bằng mili-giây.
2. Lần lượt thử lấy lock trên cả N instance, dùng chung một key với một giá trị ngẫu nhiên, kèm timeout nhỏ cho mỗi instance để một node bị down không làm treo cả quá trình.
3. Tính thời gian đã trôi qua. Lock chỉ được xem là đã lấy được khi client lấy được lock trên đa số (N/2 + 1) instance, và tổng thời gian trôi qua nhỏ hơn thời gian hiệu lực của lock.
4. Nếu lấy được, thời gian hiệu lực thực tế bằng TTL gốc trừ đi thời gian đã trôi qua và độ lệch đồng hồ (clock drift).
5. Nếu không lấy được lock, giải phóng nó trên tất cả instance ngay lập tức, bất kể instance đó có báo thành công hay không.

Vì sao "đa số" lại quan trọng

Yêu cầu đa số (chứ không phải toàn bộ N) nghĩa là Redlock chịu được việc thiểu số node bị chết - với 5 node, tối đa 2 node có thể down hoặc mất kết nối mà lock vẫn hoạt động đúng, cùng nguyên lý chịu lỗi (fault-tolerance) đứng sau Raft với mấy hệ thống dựa trên Paxos. Nó cũng ngăn được split-brain: hai client không thể cùng lúc lấy được đa số trong 5 node, vì bất kỳ hai nhóm đa số nào của 5 node cũng phải trùng nhau ít nhất một node.

Giá trị ngẫu nhiên với chuyện giải phóng lock an toàn

Mỗi client tạo một giá trị ngẫu nhiên riêng cho lần thử lấy lock của mình (không phải placeholder qua loa). Lúc giải phóng lock phải check giá trị lưu trong Redis có còn khớp không rồi mới xóa, làm nguyên tử (atomic) bằng Lua script:

if redis.call("get", KEYS[1]) == ARGV[1] then
    return redis.call("del", KEYS[1])
else
    return 0
end

Không có bước check này, client có thể lỡ tay xóa một lock mà nó không còn sở hữu nữa - kiểu như lock của chính nó đã hết hạn, và một client khác đã lấy được lock đó trong lúc đó.

Lệch đồng hồ: Điểm yếu thật sự

Tính đúng đắn của Redlock giả định rằng đồng hồ của N node không lệch nhau quá xa so với TTL của lock. Nếu đồng hồ một node bất ngờ nhảy vọt về phía trước (NTP sync lỗi, VM bị pause rồi resume, đổi giờ thủ công), node đó có thể hết hạn lock sớm hơn hẳn so với mấy node còn lại nghĩ, tạo ra một khoảng hở mà hai client cùng tưởng mình đang giữ lock. Đây chính là cốt lõi của lời phê bình nổi tiếng từ Martin Kleppmann về Redlock: nó phụ thuộc vào hành vi đồng hồ thời gian thực theo cách rất khó đảm bảo trọn vẹn.

Fencing Token: Cách vá thực tế

Dù Redlock có làm đúng đi nữa, một client bị pause (GC pause, VM suspend, network partition) vẫn có thể tỉnh dậy sau khi lock đã hết hạn và cứ hành động như đang giữ lock - ghi vô tài nguyên chung dù client khác đã lấy được lock và làm xong việc rồi. Cách xử lý chuẩn là dùng fencing token: một số tăng dần đơn điệu, trả về mỗi lần lock được cấp.

Client A lấy được lock, nhận token 33
Client A bị pause (GC, network delay...)
Lock của Client A hết hạn
Client B lấy được lock, nhận token 34
Client B ghi vô storage, gắn token 34 vô lần ghi đó
Client A tỉnh dậy, thử ghi với token 33
Storage từ chối: 33 < 34 (đã thấy token cao hơn rồi)

Chính tài nguyên được bảo vệ - database, file store, hay API - phải là nơi thực thi việc check token này. Bản thân Redlock không thể đảm bảo điều đó; nó chỉ giảm khả năng hai client cùng tin mình đang giữ lock thôi.

Khi nào nên dùng Redlock (và khi nào không)

Redlock là lựa chọn hợp lý cho lock hiệu năng (efficiency lock) - kiểu trường hợp chạy trùng thì lãng phí nhưng không thảm họa, như ngăn cùng một cron job chạy hai lần, hoặc gộp mấy request rebuild cache bị trùng. Nó là lựa chọn rủi ro cho lock đúng đắn dữ liệu (correctness lock) - kiểu trường hợp chạy trùng làm hỏng dữ liệu, như phối hợp ghi vô sổ cái tài chính. Với mấy trường hợp đó, nên dùng hệ thống có đảm bảo consistency mạnh (dịch vụ lock dựa trên consensus như ZooKeeper hay etcd) kết hợp fencing token do chính tài nguyên thực thi, chứ không chỉ dựa vô Redis.

Mấy cái cần tránh

Dùng số node chẵn phá vỡ luôn logic quorum đa số vốn là thứ làm Redlock chịu lỗi tốt - luôn dùng số node lẻ để đa số không bị mập mờ. Đặt timeout lấy lock cho mỗi node quá cao nghĩa là chỉ một node chậm cũng đủ vượt qua TTL của lock trước khi mình kịp lấy xong lock. Và coi Redlock như một đảm bảo đúng đắn tuyệt đối, thay vì một cơ chế loại trừ lẫn nhau kiểu best-effort, chính là sai lầm dẫn tới sự cố production - kết hợp nó với fencing token bất cứ khi nào thao tác được bảo vệ thật sự quan trọng.

Redlock giảm xác suất lock bị lỗi, chứ không loại bỏ hoàn toàn. Thiết kế thao tác được bảo vệ sao cho vẫn sống sót được trong trường hợp lock lỡ có trục trặc.