Sinh ID phân tán

Bài toán

Khi chỉ có một database, AUTO_INCREMENT là đủ. Khi dữ liệu nằm trên nhiều máy, ID không còn duy nhất toàn hệ thống. Đây thường là thứ đầu tiên vỡ khi phân tán dữ liệu. Yêu cầu hay gặp: duy nhất, sắp được theo thời gian, vừa 64 bit, không thêm điểm hỏng.

Diễn tiến theo thời gian

• 2010 · Twitter: chuyển sang Cassandra và MySQL shard thì mất auto-increment. Yêu cầu của họ:

  • hàng chục nghìn ID/giây, không phối hợp;
  • k-sorted (lệch dưới ~1 giây);
  • 64 bit, vì đổi số bit của tweet ID từng rất khổ khi có hơn 100.000 codebase phụ thuộc.

  Họ loại ticket server (không đảm bảo thứ tự), UUID (128 bit), ZooKeeper sequential (chậm, giảm availability). Snowflake = timestamp + worker number (lấy từ ZooKeeper lúc khởi động) + sequence. Twitter 2010

• 2011 · Instagram: cùng bài toán, cân nhắc cả ba phương án trên. Snowflake gần nhất với nhu cầu nhưng phải thêm service + ZooKeeper. Họ đưa ý tưởng vào trong Postgres: 41 bit thời gian + 13 bit shard logic + 10 bit sequence, sinh bằng PL/pgSQL. Instagram 2011

• 2011 · Pinterest: ID 64 bit = shard 16 bit + type 10 bit + local auto-increment 36 bit + 2 bit dự trữ: ID tự chỉ chỗ dữ liệu, không cần dịch vụ sinh ID. Pinterest 2015

• 2012 · Pinterest: ID 64 bit = shard ID 16 bit + type 10 bit + local ID (auto increment của MySQL), không dùng bảng tra như Twitter vì mỗi query MySQL trên AWS khoảng 3 ms; đổi lại dữ liệu gắn vào shard mãi mãi. Pinterest 2013

• 2014 · Twilio: mẹo tạm khi tách shard mà hai master cùng nhận ghi: auto_increment_offset/increment cho shard0 sinh số lẻ, shard1 sinh số chẵn, rồi bỏ khi đã tách xong. Twilio 2014

• 2015 · Wix: dùng MySQL như kho key/value, active-active ở 3 DC; bỏ serial key (gây lock, khó active-active), dùng GUID do client sinh (varchar(50)). Wix 2015

• 2017 · Discord: mọi ID là Snowflake. Nhờ sắp được theo thời gian, message_id làm luôn clustering key trong Cassandra (thay cho created_at, vốn có thể trùng). Discord 2017

• ~2017 · Segment: UUIDv4 không sắp được nên không gom log theo khoảng ID trên S3. KSUID = 32 bit timestamp (theo giây) + 128 bit ngẫu nhiên, 160 bit, base62 27 ký tự, sắp theo thứ tự từ điển = sắp theo thời gian. Không host ID, không phối hợp. Bài cũng tóm lược lịch sử: Apollo UID 64 bit → UUIDv1 (MAC, làm lộ máy) → v4 ngẫu nhiên; Flake (128 bit). Segment 2017

• 2022→2023 · Buildkite: từ hai định danh (số nguyên làm khoá chính, UUID cho bên ngoài) sang UUID có thời gian: thử bản "v4 có timestamp" (đặt nhãn v7 làm hỏng hệ thống của vài khách hàng vốn kiểm version), WAL của primary giảm 50%; rồi UUIDv7 làm khoá chính cho mọi bảng mới vì sắp shard DB theo organization, số nguyên tăng dần cần phối hợp giữa DB. Đã cân nhắc ShardingID của Instagram, khoá phức hợp của Shopify. Buildkite 2023

• 2024 · Figma: mặt trái. Khoá shard là auto-increment hoặc ID tiền tố timestamp kiểu Snowflake; chia theo khoảng thì dữ liệu mới dồn vào một shard. Họ hash khoá trước khi route. Sau khi shard ngang, họ vẫn phải giải lại bài toán sinh ID duy nhất toàn cục cho khoá chính (ghi trong danh sách việc còn lại). Figma 2024

• 2026 · Uber: bỏ từ điển toàn cục ánh xạ UUID → số thứ tự 32-bit (điểm hỏng chung, buộc các job chạy tuần tự vì cấp số trùng) bằng cách hash UUID thẳng ra 64-bit (xxHash64), rủi ro va chạm không đáng kể; các backfill chạy song song. Uber 2026

Các lựa chọn và đánh đổi

Quy tắc rút ra

1. Đặt timestamp ở bit cao để ID tự sắp theo thời gian.
2. Chọn 64 bit từ đầu. Đổi kích thước ID sau này cực đắt (Twitter).
3. Gói thông tin định tuyến (shard) vào ID để biết bản ghi nằm đâu (Instagram).
4. Đội nhỏ nên ưu tiên cách không thêm service (Instagram).
5. ID theo thời gian tốt cho sắp xếp nhưng xấu cho chia theo khoảng. Nếu dùng làm khoá shard thì phải hash (Figma). Xem Hot partition và thundering herd.
6. Có ba cách đảm bảo duy nhất: phối hợp (ticket server, ZooKeeper), định danh máy (worker/MAC), hoặc ngẫu nhiên đủ lớn (UUIDv4, KSUID). Cách thứ ba không cần thành phần vận hành nào, nhưng phải chấp nhận ID lớn hơn 64 bit (Segment).

Câu hỏi mở

• KSUID (Segment 2017) đã trả lời một phần: timestamp + ngẫu nhiên, 160 bit. UUIDv7 đã có nguồn: Buildkite 2023 chuyển khoá chính sang UUIDv7, WAL giảm 50% khi bỏ UUID ngẫu nhiên, và gặp bẫy tương thích (hệ của khách kiểm version) (Buildkite 2023). ULID vẫn chưa có nguồn production.
• Figma sẽ sinh ID toàn cục bằng cách nào sau khi shard? Chờ bài tiếp của Figma.