A Brief History of the UUID (KSUID)

Segment · 2017 (năm theo wiki) · 2. Tăng trưởng · Độ khó: Trung bình — bài gốc

Bối cảnh

Bài giới thiệu KSUID, thư viện Go sinh ID của Segment. Phần lớn bài là lịch sử của UUID. Bối cảnh trực tiếp: một hệ thống nội bộ dùng UUIDv4, vài tuần sau phát sinh yêu cầu sắp ID theo thời gian để lưu log lên S3 theo khoảng message ID. Với UUID ngẫu nhiên, message bị rải đều, không gom được thành nhóm, và số object S3 sẽ quá lớn.

Thay đổi chính

Lịch sử ngắn (theo bài):

• Apollo NCS (thập niên 1980): UID 64 bit = đồng hồ đơn điệu + host ID gắn vào phần cứng lúc sản xuất. Điểm phối hợp duy nhất là nhà máy.
• NCA UUID: mở lên 128 bit để các hãng khác dùng được, sau thành UUIDv1 (timestamp + host/MAC). Dùng file chung (/tmp/last_uuid) để đơn điệu giữa các process, dễ lỗi.
• MAC trong UUID là rủi ro: MAC không thật sự duy nhất và làm lộ máy (tác giả virus Melissa bị lần ra qua MAC trong UUID). Vì vậy UUIDv4 (122 bit ngẫu nhiên) phổ biến.
• Rủi ro va chạm của v4 nằm ở cài đặt, không ở toán: nguồn ngẫu nhiên kém (thiết bị di động), bug fork của OpenSSL làm một thư viện UUID PHP va chạm nhiều. Với 122 bit, phải có tới ~2^46 UUID thì xác suất va chạm mới ở mức 1/50 tỷ.
• ID có thời gian:
  • Cassandra TimeUUID: lộ host, có vấn đề khi lệch đồng hồ.
  • Twitter Snowflake: 64 bit, k-sorted, cần ZooKeeper (Twitter 2010).
  • Boundary Flake (2012): 128 bit, sắp theo thứ tự từ điển, base62, nhưng vẫn lộ host và phụ thuộc đồng hồ tiến lên.

KSUID:

• 160 bit = 32 bit timestamp (độ phân giải 1 giây, epoch riêng, dùng được >100 năm) + 128 bit ngẫu nhiên.
• Không dùng host ID, không phụ thuộc đồng hồ để đảm bảo duy nhất.
• Mã hoá độ dài cố định: 20 byte nhị phân hoặc 27 ký tự base62. Big-endian nên sắp theo thứ tự từ điển = sắp theo thời gian; không có dấu - (tránh bị search engine tách token).

Vì sao

Theo Segment: muốn sự đơn giản và an toàn của UUIDv4 (không phối hợp, không lộ máy) cộng với khả năng k-sort theo thời gian của Flake. Họ chấp nhận ID lớn hơn (160 bit) và thời gian chỉ chính xác tới giây.

Bài học cho SWE

• Có ba cách đảm bảo duy nhất: phối hợp (ticket server, ZooKeeper), định danh máy (MAC, worker ID), hoặc ngẫu nhiên đủ lớn. KSUID chọn cách thứ ba, nên không cần thành phần vận hành nào.
• Yêu cầu "sắp theo thời gian" có thể xuất hiện sau khi đã chọn ID, nên cân nhắc từ đầu.
• Biểu diễn chuỗi (độ dài cố định, thứ tự từ điển) cũng là một quyết định thiết kế.
• Đánh đổi so với Snowflake/Instagram: KSUID không vừa 64 bit, nên index lớn hơn. Twitter và Instagram đều coi 64 bit là yêu cầu cứng (Instagram 2011).

Liên quan

• Sinh ID phân tán