Trình tạo ID Snowflake - Tạo ID Phân tán Duy nhất

Bộ tạo ID Snowflake là gì?

Bộ tạo ID Snowflake tạo một số 64 bit duy nhất từ dấu thời gian, mã máy và số thứ tự. Twitter đã tạo định dạng này vào 2010 để nhiều máy chủ có thể đồng thời tạo mã nhận dạng cho từng tweet, mà không cần hỏi nhau “số này đã được sử dụng chưa?”. Công cụ này tạo một ID Snowflake từ các giá trị đã nhập và cho biết các giá trị đó lấp đầy 64 bit như thế nào.

Bộ tạo ID Snowflake hoạt động như thế nào

Bộ tạo nhận bốn đầu vào:

• Dấu thời gian: dấu thời gian Unix tính bằng mili giây. Để trống để sử dụng thời gian hiện tại.
• Mã máy: một số nguyên từ 0 đến 31 (5 bit). Đây là mã định danh của worker trong phiên bản ban đầu của Twitter.
• Mã trung tâm dữ liệu: một số nguyên từ 0 đến 31 (5 bit).
• Số thứ tự: một số nguyên từ 0 đến 4095 (12 bit), dùng để phân biệt các ID được tạo trong cùng một mili giây.

Công cụ kết hợp bốn giá trị thành một ID 64 bit. Sau đó, công cụ hiển thị kết quả dưới dạng nhị phân, được chia thành các phần dấu thời gian, trung tâm dữ liệu, máy và số thứ tự.

Dấu thời gian được đo từ một mốc bắt đầu cố định gọi là epoch Twitter: 4 tháng 11, 2010, 1:42:54,657 UTC, tức 1.288.834.974.657 mili giây sau epoch Unix. Bộ tạo này không cho phép thay đổi mốc bắt đầu đó. Mọi ID được tạo đều được đo từ cùng một ngày cố định này.

Cấu trúc ID Snowflake

ID Snowflake là một số nguyên 64 bit được chia thành bốn phần, đọc từ bit có trọng số cao nhất xuống:

Bit đầu tiên luôn là 0, vì vậy ID Snowflake luôn là một số dương. Trường dấu thời gian 41 bit và trường số thứ tự 12 bit là hai phần giúp ID Snowflake hữu ích cho việc sắp xếp: các ID được tạo sau có phần dấu thời gian lớn hơn, nên được xếp sau các ID được tạo trước.

Công thức ID Snowflake

Bộ tạo xây dựng ID bằng công thức sau:

$d = t - 1288834974657$

$I = (d << 22) \mathbin{|} (c << 17) \mathbin{|} (m << 12) \mathbin{|} s$

trong đó d là độ lệch, t là dấu thời gian đã nhập tính bằng mili giây, I là ID hoàn chỉnh, c là mã trung tâm dữ liệu, m là mã máy và s là số thứ tự.

<< là phép dịch bit sang trái. Dịch một số sang trái 22 bit tương đương với nhân số đó với 2²², tức 4.194.304. Các giá trị dịch (22, 17, 12) được xác định trực tiếp từ độ rộng của các trường: trường số thứ tự rộng 12 bit, nên mã máy nằm cao hơn 12 bit; trường máy rộng 5 bit, nên mã trung tâm dữ liệu nằm cao hơn 17 bit (12 + 5); và tương tự.

Cách tính ID Snowflake: ví dụ minh họa

Giả sử người dùng nhập:

• Dấu thời gian: 1.288.834.975.657 (chính xác 1.000 mili giây sau epoch Twitter)
• Mã trung tâm dữ liệu: 1
• Mã máy: 1
• Số thứ tự: 0

Bước 1 — Tìm độ lệch. Lấy dấu thời gian trừ epoch: 1.288.834.975.657 − 1.288.834.974.657 = 1.000.

Bước 2 — Dịch từng trường vào đúng vị trí.

• Dấu thời gian: 1.000 << 22 = 4.194.304.000
• Mã trung tâm dữ liệu: 1 << 17 = 131.072
• Mã máy: 1 << 12 = 4.096
• Số thứ tự: 0

Bước 3 — Kết hợp bằng phép OR theo bit. Vì không có trường nào sau khi dịch bị chồng lấp, cộng chúng cho kết quả giống với thực hiện phép OR:

4.194.304.000 + 131.072 + 4.096 + 0 = 4.194.439.168

Đó là ID Snowflake cho đầu vào này. Chế độ xem kết quả của công cụ chia lại cùng chuỗi nhị phân 64 bit thành khối dấu thời gian 41 bit, khối trung tâm dữ liệu 5 bit, khối máy 5 bit và khối số thứ tự 12 bit, nhờ đó cấu trúc của số vẫn được thể hiện rõ.

ID Snowflake được sử dụng ở đâu

Twitter xây dựng định dạng này để cung cấp các ID duy nhất, gần như được sắp theo thời gian, cho các tweet trên hàng nghìn máy cơ sở dữ liệu mà không cần một bộ đếm trung tâm để mọi máy chủ phải kiểm tra. Sau đó, Discord và Instagram áp dụng các thiết kế ID 64 bit tương tự cho tin nhắn và bài đăng. Ý tưởng này cũng xuất hiện trong phân mảnh cơ sở dữ liệu, ID đơn hàng của các hệ thống thương mại điện tử và nhật ký sự kiện trong các ứng dụng phân tán. Nó phù hợp với mọi môi trường trong đó nhiều máy cấp phát ID độc lập nhưng vẫn cần chúng được sắp xếp gần đúng theo thời gian.

Những hạn chế của ID Snowflake

Một bộ tạo Snowflake dùng trong thực tế thường duy trì đồng hồ riêng: tăng số thứ tự cho mỗi ID được tạo trong cùng một mili giây và chờ đến mili giây tiếp theo khi số thứ tự đạt 4.095. Công cụ này không lưu trạng thái giữa các lần tính toán. Nó tạo một ID từ bất kỳ giá trị nào được nhập, nên hữu ích để tìm hiểu định dạng nhưng khác với một dịch vụ đang vận hành thực tế.

Thiết kế này có các giới hạn cố định, bất kể dịch vụ nào triển khai nó:

• Epoch cố định: bộ tạo này chỉ chấp nhận các dấu thời gian từ 4 tháng 11, 2010 trở đi (epoch Twitter). Không thể mã hóa các ngày sớm hơn.
• Giới hạn trên của dấu thời gian: trường dấu thời gian 41 bit sẽ hết phạm vi vào khoảng tháng bảy năm 2080. Sau đó, độ lệch so với epoch không còn vừa trong 41 bit.
• Giới hạn số thứ tự: chỉ có thể cấp 4.096 ID khác nhau (0–4095) từ một máy trong cùng một mili giây trước khi các giá trị lặp lại.
• Không gian mã máy: với 5 bit cho mỗi mã máy và mã trung tâm dữ liệu, một hệ thống có 1.024 danh tính máy khác nhau (32 × 32) để phân phối mà không xảy ra xung đột.
• Sắp xếp cục bộ, không phải toàn cục: các ID chỉ được sắp xếp chính xác với nhau nếu chúng đến từ các máy có đồng hồ được đồng bộ. Độ lệch đồng hồ giữa các máy có thể phá vỡ thứ tự thời gian nghiêm ngặt.

Lịch sử của ID Snowflake

Twitter công bố định dạng ID Snowflake vào 2010 để thay thế các ID cơ sở dữ liệu tự tăng đơn giản, vốn không thể mở rộng trên nhiều máy chủ cơ sở dữ liệu độc lập. Tên gọi này bắt nguồn từ ý tưởng rằng, giống như những bông tuyết thật, không có hai ID được tạo ra giống nhau. Thiết kế này sau đó được phát hành dưới dạng mã nguồn mở và được các nền tảng lớn khác sao chép với những sửa đổi để đáp ứng cùng một nhu cầu: tạo các ID duy nhất, có thể sắp xếp, bằng nhiều máy cùng lúc.

Các câu hỏi thường gặp

ID Snowflake là gì? ID Snowflake là một số 64 bit gồm dấu thời gian, mã máy và số thứ tự, được thiết kế để nhiều máy có thể tạo các ID duy nhất mà không cần phối hợp với nhau.

Công thức ID Snowflake là gì? id = ((timestamp − epoch) << 22) | (dataCenterId << 17) | (machineId << 12) | sequence, trong đó epoch là một ngày bắt đầu cố định và << là phép dịch bit sang trái.

Có thể thay đổi epoch trong bộ tạo này không? Không. Công cụ này luôn đo dấu thời gian từ epoch Twitter cố định, 4 tháng 11, 2010. Không có trường để đặt một ngày bắt đầu khác.

Công cụ này có giải mã một ID Snowflake có sẵn không? Không. Công cụ chỉ tạo một ID mới từ dấu thời gian, mã máy, mã trung tâm dữ liệu và số thứ tự đã nhập, sau đó hiển thị phân tách bit của ID mới đó.

Một máy có thể tạo bao nhiêu ID Snowflake mỗi mili giây? Tối đa 4.096, vì trường số thứ tự rộng 12 bit (các giá trị từ 0 đến 4.095).

Bộ tạo này có thể tạo dấu thời gian hợp lệ đến năm nào? Đến khoảng tháng bảy năm 2080. Trường dấu thời gian 41 bit có thể chứa tối đa khoảng 69,7 năm tính từ epoch cố định 2010; sau đó giá trị sẽ tràn khỏi trường.

Tài liệu tham khảo

1. “Công bố Snowflake.” Twitter Engineering Blog, 2010.
2. "Snowflake ID." Wikipedia, https://en.wikipedia.org/wiki/Snowflake_ID