Timestone: Netflix's High-Throughput, Low-Latency Priority Queueing System

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

Bối cảnh

• Năm 2018, khi thiết kế Cosmos thay hệ encode media Reloaded, cần hàng đợi ưu tiên giữa ba thành phần (API Optimus, rule engine Plato, lớp serverless Stratum). Yêu cầu:
  • Một message chỉ giao cho một worker tại một thời điểm: việc encode rất tốn và fan-out ra hàng nghìn tác vụ; nếu replica trễ cho worker B lấy message mà A vừa lấy thì phí compute. Loại bỏ giải pháp eventually consistent: cần linearizable ở mức queue.
  • Việc không được song song: khi Plato đang chạy workflow cho một project, không được lấy thêm yêu cầu của cùng project (rule engine sẽ đánh giá sớm và đẩy workflow vào trạng thái sai).
  • Dequeue và đếm độ sâu theo filter metadata; tự tạo queue khi có message; message lấy được trong vòng 1 giây.
• Không có sản phẩm sẵn đáp ứng, nên tự xây.

Thay đổi chính

• Nguồn sự thật là cụm Redis bền: mọi ghi (kể cả dequeue vì đổi trạng thái) vào transaction log trước khi trả lời. Mỗi queue là một sorted set xếp theo ưu tiên; message và cấu hình queue là hash; mọi cấu trúc của một queue (kể cả index phụ trong bộ nhớ cho dequeue theo filter) nằm cùng một shard nhờ hash tag. Gần như mọi thao tác là Lua script (Redis chạy nguyên tử). Mọi API đổi trạng thái là idempotent.
• Index phụ cho quan sát: sau khi Redis trả lời, đồng thời trả cho client và phát event sang Kafka; hai job Flink cập nhật index "hiện tại" và "lịch sử" trên Elasticsearch (best-effort, thứ tự theo bộ đếm version của message).
• Mô hình: ưu tiên là số nguyên (thường là Unix timestamp ms, ưu tiên cao thì trừ bội số khoảng 10 năm), dequeue earliest-deadline-first; sáu trạng thái (invisible, pending, running, completed, canceled, errored); worker lấy kèm lease, gia hạn hoặc complete trong lease, hết lease thì message lấy lại được và mất một lần thử, hết lượt thử thì errored.
• Exclusive queue: queue gắn một khoá độc quyền (ví dụ project); mọi message phải có khoá đó; mỗi giá trị khoá tối đa một consumer tại một thời điểm. Consumer không phải tự khoá hay phối hợp.
• Quy mô (2022): 30.000 dequeue/giây (p99 45 ms), 1.200 enqueue/giây (p99 25 ms), đỉnh 5.000 enqueue/giây; 15 tỉ message từ đầu năm, bị dequeue 400 tỉ lần; thường 10 triệu message chờ. Ngoài Cosmos còn làm engine ưu tiên cho Conductor và scheduler của pipeline dữ liệu lớn.
• Đang làm: service truy vấn độ sâu riêng (CQRS); shard một queue vì queue nóng chỉ nằm trên một shard Redis và phình to khi thiếu compute; giảm index filter vốn tăng theo O(2^n) số cặp metadata.

Vì sao

• Ràng buộc "một việc một worker" và "không song song theo khoá" đặt vào hàng đợi thì mọi consumer được hưởng, thay vì mỗi consumer tự viết khoá phân tán.

Bài học cho SWE

• Với việc tốn kém, nhất quán mạnh ở hàng đợi rẻ hơn compute bị phí do giao trùng.
• Đặt mọi thứ của một đơn vị (queue) vào một shard cho phép thao tác nguyên tử, đổi lại đơn vị nóng bị giới hạn bởi một shard.

Liên quan

• Event-driven, message queue và Kafka · Hot partition và thundering herd
• Hàng đợi job khác: Airbnb 2019 · Slack 2017
• Cùng công ty: Netflix 2021