Meet Chrono, our scalable, consistent, metadata caching solution

Dropbox · 2024 · 3. Quy mô lớn · Độ khó: Khó — bài gốc

Bối cảnh

• Metadata của Dropbox nằm trên Panda, KV store giao dịch MVCC tự xây; theo đà tăng, QPS đọc sẽ vượt sức máy storage. Cache là lời giải hiển nhiên nhưng các client nội bộ đã quen read-after-write; nới đảm bảo này thì không thể kiểm và sửa code của mọi team.
• Cache thường không giữ được đảm bảo đó: ghi storage rồi ghi cache, crash ở giữa thì cache cũ; xoá cache trước khi ghi vẫn có đua (một reader đọc giá trị cũ trước khi ghi xong, nạp vào cache sau reader đọc giá trị mới).

Thay đổi chính

• Chrono chỉ trả lời một câu: "timestamp lần thử ghi gần nhất của mỗi key", không giữ giá trị (giá trị nằm ở Memcache, được phép mất hoặc cũ).
• Panda có commit timestamp đơn điệu theo key, đọc snapshot theo timestamp, GetLatest trả kèm read timestamp, và Write(..., maxPermittedCommitTimestamp) từ chối nếu commit timestamp vượt mức cho phép.
• Ghi: gọi Attempt(key, now + khoảng 5s) tới Chrono trước (phải thành công), rồi ghi Panda với maxPermittedCommitTimestamp bằng đúng giá trị đó, nên commit timestamp ≤ attempt timestamp.
• Đọc: song song hỏi Chrono LatestAttemptTimestamp và Memcache (giá trị + readTS); nếu readTS ≥ attempt timestamp thì dùng cache, ngược lại GetLatest từ Panda rồi nạp lại. Kể cả cache miss, đọc snapshot tại timestamp từ Chrono cho phép đọc linearizable từ follower, nên phần lớn đọc (key không vừa ghi) rời khỏi leader.
• An toàn không phụ thuộc đồng hồ (chỉ liveness cần đồng hồ đồng bộ lỏng); Chrono lưu bền một cận trên timestamp để giá trị trả về không lùi sau restart; bảng timestamp băm key vào slot (nhiều key chung một giá trị, chỉ làm giảm hit chứ không sai) để giới hạn bộ nhớ. Chrono và Memcache scale độc lập.
• Kiểm chứng: TLA+ ở pha thiết kế, cộng workload tự kiểm chạy liên tục ở stage và production. Một phiên bản trước có lỗi ở trình tự khởi động mà mô hình chỉ tả trạng thái ổn định không bắt; người đọc phát hiện, mô hình hoá thêm thì lộ vi phạm bất biến ngay.

Vì sao

• Giữ đảm bảo client đang dựa vào, đổi lấy độ phức tạp ở nền tảng; và mở đường cho workload đọc lớn mới (search, AI).

Bài học cho SWE

• Theo nhóm tác giả: ngữ nghĩa mạnh có giá; nếu được chọn từ đầu, đừng chiều client bằng đảm bảo mạnh mà họ không thật cần.
• Cache nhất quán = tách "biết dữ liệu đã đổi chưa" (nhỏ, chính xác) khỏi "giữ dữ liệu" (lớn, được phép sai).
• Mô hình hình thức chỉ chứng minh điều được mô hình hoá; trình tự khởi động và giả định môi trường là chỗ hay bị bỏ qua. Phần tốn thời gian nhất là vận hành hệ shard (gom request Memcache, hot spot), không phải giao thức.

Liên quan

• Cache và invalidation · Scale dọc trước khi scale ngang
• Cùng tầng metadata: Dropbox 2018
• Cache consistency ở Meta: Meta 2022