How Etsy caches: hashing, Ketama, and cache smearing

Etsy · 2017 · 3. Quy mô lớn · Độ khó: Trung bình — bài gốc

Bối cảnh

Etsy dùng memcached làm look-aside cache (kết quả query DB, search, tính toán đắt) cho PHP và Java, và Varnish làm cache HTTP cho request nội bộ giữa API server (key gồm URL, query, header trong Vary như locale).
Cache lưu hàng terabyte, hàng triệu lookup/giây (2017); một máy không chịu nổi nên scale ngang thành pool.

Modulo hashing dùng hết không gian cache nhưng đổi kích thước pool là đa số key chuyển máy: từ 4 lên 5 máy chỉ 20% key còn ở chỗ cũ, hit rate tụt cho tới khi cache ấm lại.
Consistent hashing bằng Ketama (mặc định của thư viện memcached PHP): chia không gian hash thành các dải, mỗi máy giữ hàng chục đến hàng trăm dải. Từ 4 lên 5 máy, 50% key (trong ví dụ đơn giản) vẫn ở chỗ cũ; tránh đợt tải dồn khi đổi pool.
Hot key: lượt đọc theo phân phối luỹ thừa; có key được đọc nhiều và giá trị đủ lớn để làm bão hoà card mạng của máy chứa nó. Thêm máy không giúp vì chỉ dời key nóng sang máy khác. Tìm bằng mctop, memkeys, distributed tracing.
Cache smearing: với vài key nóng nhất (chọn thủ công), thêm số ngẫu nhiên trong dải nhỏ (0–8 hoặc 0–16) vào key mỗi lần đọc/ghi, biến một key thành vài key nằm trên nhiều máy. Với Varnish thì thêm một query parameter ngẫu nhiên.
Đánh đổi kích thước dải: rộng quá thì nhân bản thừa và một user có thể thấy giá trị lệch giữa các request; hẹp quá thì không trải tải (thậm chí các bản vẫn rơi vào cùng máy).

Etsy chọn nhiều máy rẻ thay vì ít máy mạnh; nên phải trải tải của key nóng ra nhiều máy thay vì mua card mạng nhanh hơn.

Cách ánh xạ key → máy quyết định chi phí của mỗi lần đổi kích thước pool.
Consistent hashing cân tải theo key, không theo lượt đọc; key nóng vẫn cần xử lý riêng.
Nhân bản key nóng là đổi không gian lấy thông lượng, kèm rủi ro đọc lệch giữa các bản.