[Big-tech-interview - System Design] Thiết kế 1 Distributed ID Generator sao cho hợp lý - 4 ways

1. Khởi nguồn của rắc rối: Khi auto_increment trở nên vô dụng

Khi mới bắt đầu xây dựng một ứng dụng, mọi thứ thật đơn giản. Chúng ta chỉ cần tạo một bảng trong cơ sở dữ liệu quan hệ (như MySQL), set khóa chính là auto_increment, và ung dung nhìn các con số nhảy từ 1, 2, 3... một cách hoàn hảo.

Nhưng khi ứng dụng của bạn bùng nổ, lượng dữ liệu phình to đến mức một con server database không thể gánh nổi nữa. Bạn buộc phải áp dụng Sharding – chặt nhỏ database ra thành hàng chục, hàng trăm server khác nhau. Và lúc này, thảm họa bắt đầu.

Nếu bạn chèn một dòng mới vào Shard A, nó sinh ra ID = 1. Nếu cùng lúc đó, có request ghi vào Shard B, nó cũng sinh ra ID = 1. Hai bản ghi ở hai máy chủ khác nhau nhưng mang cùng một định danh. Khi bạn cần gom dữ liệu lại để phân tích hoặc query chéo, sự đụng độ (Collision) xảy ra khiến toàn bộ logic hệ thống sụp đổ.

Chúng ta cần một hệ thống sinh ID đáp ứng được những yêu cầu cực kỳ khắc nghiệt: phải đảm bảo tính duy nhất trên toàn cầu giữa hàng ngàn máy chủ, tốc độ phản hồi phải ở mức tính bằng micro-giây, và đặc biệt, các ID này phải tăng dần theo thời gian (Time-sortable) để hệ thống dễ dàng phân trang và sắp xếp.

2. Hành trình đi tìm giải pháp: Từ những nỗ lực đầu tiên đến Snowflake

Các kỹ sư đi trước đã thử nghiệm rất nhiều cách. Có người thử dùng Multi-master replication, bằng cách ép mỗi server nhảy ID theo một bước cố định (step = k). Ví dụ server 1 sinh số lẻ, server 2 sinh số chẵn. Nhưng cách này cực kỳ thô sơ, nó vỡ vụn ngay khi bạn cần thêm hoặc bớt server trong cụm.

Có người chuyển sang dùng UUID (chuỗi 128-bit ngẫu nhiên). Xác suất trùng UUID là cực nhỏ, hệ thống không bao giờ đụng độ. Nhưng UUID lại tạo ra một cơn ác mộng khác cho Database: chuỗi 128-bit quá dài, lưu trữ cực kỳ tốn kém và tệ hơn nữa, chúng sinh ra ngẫu nhiên nên không có tính tuần tự. Khi bạn chèn liên tục các UUID vào Index B+ Tree của cơ sở dữ liệu, nó sẽ gây ra hiện tượng phân mảnh (fragmentation) nghiêm trọng, làm sụt giảm thê thảm tốc độ ghi.

Flickr từng giải quyết bằng Ticket Server, tức là dành riêng một server duy nhất chỉ để làm bộ đếm. Tuy nhiên, nó tạo ra một Single Point of Failure (điểm chết duy nhất). Server đó sập, toàn bộ hệ thống tê liệt.

Cuối cùng, Twitter (giờ là X) đã đưa ra giải pháp giải cứu ngành công nghiệp: Thuật toán Snowflake.

Thay vì giao tiếp qua mạng hay phụ thuộc vào một database tập trung, Snowflake cho phép mỗi máy chủ ứng dụng tự tính toán và sinh ra ID ngay trên RAM của nó. Mã ID được sinh ra là một số nguyên dương 64-bit (chỉ tốn 8 bytes), cực kỳ nhỏ gọn và hoàn hảo cho hệ quản trị cơ sở dữ liệu.

Đi sâu vào 64-bit này, Twitter đã chặt nó ra làm 4 phần cực kỳ tinh tế:

• 1 bit đầu tiên luôn là 0 để biểu thị số dương.
• 41 bits tiếp theo là Timestamp (đếm theo millisecond). Vì 41 bits có thể lưu được khoảng 69 năm kể từ một mốc thời gian tùy chỉnh (Custom Epoch), và vì nó nằm ở đầu chuỗi bit, nên mọi ID sinh ra sau sẽ luôn lớn hơn ID sinh ra trước. Tính năng "sắp xếp theo thời gian" được giải quyết triệt để.
• 10 bits tiếp theo (thường chia làm 5 bit cho Datacenter và 5 bit cho Machine ID) giúp chúng ta định danh được tối đa 1024 máy chủ độc lập. Mỗi máy chủ cầm một cái "căn cước" riêng, nên chúng sinh ID độc lập mà không bao giờ sợ đụng hàng.
• 12 bits cuối cùng là một biến đếm (Sequence Number) chạy từ 0 đến 4095. Nếu trong cùng một phần ngàn giây (millisecond), một máy chủ nhận được nhiều request sinh ID, nó chỉ việc tăng biến đếm này lên. Sang millisecond tiếp theo, biến đếm lại reset về 0.

3. Câu chuyện thực chiến: Xây dựng hệ thống chat với tải 100K TPS

Hãy tưởng tượng bạn đang là kiến trúc sư trưởng cho một ứng dụng chat như Zalo hay Discord. Bạn phải xử lý lưu lượng khoảng 100.000 tin nhắn mỗi giây (100k TPS) trong các sự kiện lớn. Một yêu cầu cực kỳ tối quan trọng của ứng dụng chat là tin nhắn phải được sắp xếp đúng thứ tự thời gian hiển thị. Sai một nhịp, câu chuyện của người dùng sẽ trở nên vô nghĩa.

Với lượng dữ liệu khủng khiếp, bạn đã chia nhỏ kho chứa tin nhắn ra hàng trăm Shard Database khác nhau. Khi một người dùng bấm "Gửi", tin nhắn bay lên các Chat Server (App Server).

Thay vì để các App Server gọi sang một dịch vụ sinh ID bên ngoài (làm tăng độ trễ mạng), bạn nhúng thẳng thư viện thuật toán Snowflake vào mã nguồn của Chat Server. Mỗi Chat Server khi khởi động sẽ gọi lên một hệ thống như Zookeeper để xin cấp cho mình một Machine ID duy nhất từ 0 đến 1023.

Từ giây phút đó, khi có tin nhắn bay vào, Chat Server tự động gộp thời gian hệ thống của nó (Timestamp), Machine ID của nó, và Sequence Number hiện tại để nén thành một số BIGINT 64-bit, tạo thành message_id. Tốc độ sinh ID của mỗi máy chủ đạt mức kỷ lục: 4096 tin nhắn/ms, tương đương hơn 4 triệu tin nhắn mỗi giây. Độ trễ sinh ID gần như bằng Zero.

Tin nhắn mang theo message_id này lao thẳng xuống Database. Các mảnh Shard đón nhận độc lập. Khi client truy vấn lại lịch sử chat, họ chỉ cần ORDER BY message_id. Việc sắp xếp diễn ra siêu tốc nhờ Index BIGINT, và kết quả trả về chính xác theo dòng thời gian vì 41 bit đầu của ID chính là dấu ấn thời gian tin nhắn được tạo ra.

4. Những góc khuất và điểm nghẽn trí mạng

Mọi thiết kế vĩ đại đều có gót chân Achilles, và gót chân của Snowflake chính là sự phụ thuộc tuyệt đối vào Đồng hồ phần cứng (System Clock).

Bản chất thuật toán lấy 41 bit Timestamp từ giờ hiện tại của máy chủ. Vậy chuyện gì xảy ra nếu đồng hồ của máy chủ chạy nhanh hơn thế giới, và máy tính tự động đồng bộ lại giờ (NTP Clock Synchronization) làm cho giờ hệ thống bị tua ngược lại quá khứ vài mili-giây?

Đây là một sự cố cực kỳ thảm khốc gọi là Clock Drift hay Clock Backward. Nếu thời gian chạy lùi, máy chủ sẽ lấy một Timestamp cũ, ghép với các biến đếm cũ, và rủi ro sinh ra một ID trùng lặp hoàn toàn với ID nó vừa sinh ra trước đó là rất cao. Hơn nữa, nó làm hỏng hoàn toàn tính chất tăng dần theo thời gian của hệ thống.

Để chống lại điều này, trong thực tế, các thư viện sinh ID phải lưu lại thời gian cuối cùng mà chúng sinh ID. Nếu chúng phát hiện giờ hiện tại bé hơn giờ vừa lưu, chúng bắt buộc phải dừng hoạt động (Sleep) chờ cho thời gian trôi qua lại mốc đó, hoặc ném ra một Exception (lỗi) từ chối phục vụ để Load Balancer đẩy request sang một máy chủ khác khỏe mạnh hơn.

Một "cú lừa" khác thường gặp khi ứng dụng Snowflake là lúc đẩy cục dữ liệu về cho Frontend (Web/Javascript). Trong thế giới của Javascript, kiểu số nguyên an toàn lớn nhất (Max Safe Integer) chỉ là 53-bit. Nếu bạn trả về số 64-bit thẳng qua JSON, khi trình duyệt parse nó, những con số cuối cùng sẽ bị làm tròn sai một cách vô thức. Đã có rất nhiều hệ thống gặp lỗi truy xuất do lỗi làm tròn này. Giải pháp duy nhất là đội ngũ Backend phải nhớ luôn ép kiểu message_id sang dạng Chuỗi (String) trước khi đẩy qua API RESTful.

5. Những bước tiến kế tiếp

Nhìn ra thế giới, Twitter Snowflake đã trở thành nguồn cảm hứng bất tận. Các ông lớn khác đều tinh chỉnh nó để phù hợp với kiến trúc riêng của họ.

Sony tạo ra Sonyflake, tinh chỉnh lại số bit. Thay vì đếm bằng millisecond, Sony đếm theo block 10ms, giúp kéo dài vòng đời hệ thống lên tới 174 năm (thay vì 69 năm). Họ giảm số lượng ID sinh ra trong một block thời gian nhưng tăng lượng Machine ID lên 16 bits, cực kỳ phù hợp cho môi trường Kubernetes nơi các Pod được sinh ra và tiêu diệt liên tục với số lượng khổng lồ.

MongoDB cũng dùng tư duy tương tự để sinh ra ObjectId 96-bit của họ, tích hợp Timestamp 4-bytes ở đầu, sau đó là thông tin machine và counter. Dù to hơn 64-bit một chút nhưng nó hoàn toàn đáp ứng được nhu cầu phân tán tự nhiên của nền tảng NoSQL này.