Va chạm ULID là gì
ULID gồm 128 bit, viết thành 26 ký tự Crockford Base32. 48 bit đầu là timestamp Unix theo mili giây. 80 bit còn lại là phần ngẫu nhiên. Hai ULID chỉ bằng nhau khi cả hai phần trùng, nên va chạm chỉ có thể xảy ra trong cùng một mili giây.
Vì vậy tổng số ID trong nhiều tháng thường không phải là con số đáng sợ. Bài toán ngày sinh không chạy trên tổng cả đời hệ thống. Nó chạy trên các ID rơi vào cùng một mili giây, rồi xác suất nhỏ đó được lặp lại cho từng mili giây trong khoảng thời gian bạn chọn.
Công thức trang này dùng
Trong một mili giây, n hậu tố ngẫu nhiên 80 bit được rút từ không gian d = 2^80 giá trị. Xác suất có ít nhất một hậu tố lặp là chặn ngày sinh. Khi n chưa quá lớn, nó xấp xỉ n(n-1) / 2^81, vì 2 x 2^80 = 2^81. 2^80 bằng 1.208.925.819.614.629.174.706.176.
Máy tính này dùng dạng gần đó: n^2 / 2^81 cho mỗi mili giây, cao hơn một chút so với n(n-1) / 2^81. n là số ID của cả cụm trong một mili giây: tốc độ mỗi node quy về số ID trên mili giây, nhân với số node. M là số mili giây của khoảng thời gian. Một năm được tính 365,25 ngày và một tháng 30,4375 ngày, đúng như form trên trang. Xác suất có ít nhất một va chạm trong cả cửa sổ là khoảng 1 - exp(-M x n^2 / 2^81). Khi số mũ nhỏ hơn 10^-6, trang in thẳng số mũ đó, vì lúc ấy 1 - exp(-x) không khác x ở mức có thể thấy.
Mô hình giả định tốc độ được trải đều, và mỗi node rút hậu tố độc lập. Một đợt dồn nhiều ID vào vài mili giây rủi ro hơn cùng một tốc độ trung bình, vì xác suất tăng theo bình phương của n.
Ví dụ tính tay
Một mili giây, 1.000 ID. Lấy số cặp chặt hơn: 1.000 x 999 / 2^81 = 4,13 x 10^-19. Phải cỡ một nghìn tỷ ID trong đúng mili giây đó thì xác suất mới trở thành chuyện bình thường. 2^40 vào khoảng 1,1 x 10^12.
Đúng số mặc định của form: 100 ID mỗi giây trên mỗi node, 10 node, trong 5 năm. Đó là 1 ID mỗi mili giây trên cả cụm (100 / 1.000 x 10). M bằng 157.788.000.000 mili giây. Tổng số ID cũng là 157.788.000.000. Xác suất gộp khoảng 6,53 x 10^-14, cỡ 1 trên 15 nghìn tỷ. Trung bình một ID mỗi mili giây thì hầu hết mili giây không có cặp nào, nên dạng n^2 hơi ước lượng cao trong trường hợp này.
Mức tốc độ mà máy tính mới hiện số dễ đọc: 50.000 ID trong mọi mili giây, suốt một ngày. M bằng 86.400.000. Số mũ khoảng 8,93 x 10^-8, cỡ 1 trên 11,2 triệu. Đó là 50 triệu ID mỗi giây. Đây là nhịp của cả cụm máy, không phải một tiến trình.
Khi nào nên dùng
- Bạn định dùng ULID làm khóa chính và cần một con số cho đúng lưu lượng dự kiến, thay vì một câu chung về 80 bit.
- Bạn muốn thấy đầu vào đáng quan tâm là số ID trên mỗi mili giây, không phải số dòng của bảng.
- Bạn đang so mô hình này với Snowflake, nơi va chạm là lỗi phối hợp worker, hoặc với UUID v4, nơi bài toán ngày sinh gom cả lịch sử vào một thùng.
Lỗi hay gặp
- Đừng nhét tổng số ID cả đời vào một công thức ngày sinh. Cách đó giả định mọi ID được tạo trong một mili giây và phóng đại rủi ro rất nhiều.
- ULID đơn điệu (monotonic) là mô hình khác. Thư viện tăng dần phần ngẫu nhiên trong một tiến trình sẽ không tự va chạm cho đến khi bộ đếm 80 bit quay vòng, điều không xảy ra trong thực tế. Rủi ro chỉ còn giữa các tiến trình không phối hợp với nhau.
- Đồng hồ chạy lùi có thể dùng lại một mili giây. Nếu phần ngẫu nhiên cũng bị đặt lại, giả định mỗi lần là một lần rút mới không còn đúng.
- Trang không đọc cơ sở dữ liệu. Cùng một bộ số vào thì cùng một ước lượng.
- Số node chỉ có ý nghĩa khi các node đó rút từ cùng không gian 80 bit trong cùng mili giây. Bộ đếm monotonic cục bộ từng tiến trình không thuộc mô hình này.
Mô hình va chạm khác nhau chỗ nào
| Định dạng | Trùng có thể xảy ra khi nào | Nên đo cái gì |
|---|---|---|
| ULID (hậu tố ngẫu nhiên) | Cùng mili giây và cùng 80 bit ngẫu nhiên | Số ID mỗi mili giây, rồi lặp trên cả cửa sổ |
| UUID v4 | Bất kỳ lúc nào trong cả lịch sử | Tổng số ID so với 122 bit ngẫu nhiên (khoảng n^2 / 2^123) |
| Snowflake | Cùng mili giây, cùng datacenter, cùng worker, cùng sequence | Trùng worker và tràn sequence, không phải chặn ngày sinh ngẫu nhiên |
| CUID2 (bản chính thức, dài 24) | Bất kỳ lúc nào, không chia theo thời gian | Độ dài. Một chữ cái cộng 23 ký tự base36 vào khoảng 124 bit |
Câu hỏi
Vì sao ULID chỉ va chạm trong một mili giây?
48 bit đầu là timestamp. Mili giây khác thì tiền tố khác, nên các hậu tố 80 bit không bị so sánh xuyên thời gian. Hai ID chỉ bằng nhau khi cả tiền tố và hậu tố trùng.
2^81 trong công thức là gì?
Hậu tố ngẫu nhiên có d = 2^80 giá trị. Số hạng dẫn của chặn ngày sinh là n(n-1) / (2d). 2d chính là 2^81. Máy tính dùng n^2 / 2^81, cùng ý đó và thiên về phía an toàn hơn một chút.
Xác suất 10^-14 đã đủ an toàn chưa?
Với mã định danh thì có. Nó thấp hơn nhiều so với mức đáng kể cho một khóa cơ sở dữ liệu. Con số cần nhìn là bao nhiêu ID dùng chung một mili giây. Trung bình gần 1 thì chưa phải vùng va chạm. Hàng chục nghìn ID mỗi mili giây, kéo dài, mới làm số mũ hiện ra, và nó vẫn nhỏ.
ULID monotonic có đổi kết quả không?
Có. Bộ tạo monotonic dùng phần ngẫu nhiên như một bộ đếm trong một tiến trình, nên tiến trình đó không lặp giá trị trong cùng mili giây. Trang này mô hình các lần rút ngẫu nhiên độc lập. Hãy dùng nó cho thiết kế đó, không dùng cho bộ đếm riêng từng tiến trình.
Trang có biết bảng của tôi đã trùng chưa?
Không. Đây là xác suất tính từ tốc độ, số node và thời gian bạn nhập. Trang không nối tới cơ sở dữ liệu, và dữ liệu bạn nhập không được tải lên.