Series duthaho đi phỏng vấn: bài toán Unique ID

Mọi người ghé qua thì ủng hộ mình 1 tym + subscrible trên https://duthaho.substack.com/p/toi-i-phong-van-bai-toan-unique-id để mình có thêm động lực ra bài mới nhé!

Bắt đầu buổi phỏng vấn

(Anh Minh bắt đầu cuộc gọi, mỉm cười thân thiện)

Anh Minh: Chào duthaho, anh là Minh. Cảm ơn em đã dành thời gian tham gia buổi phỏng vấn hôm nay. Em nghe rõ anh nói chứ?

duthaho: Dạ em chào anh Minh, em nghe rất rõ ạ. Em cũng cảm ơn anh đã tạo điều kiện cho em có buổi trao đổi này.

Anh Minh: Ok tốt rồi. Hôm nay chúng ta sẽ có một bài toán về thiết kế hệ thống. Anh muốn tìm hiểu về cách em tư duy, phân tích vấn đề và đưa ra các lựa chọn kiến trúc. Em cứ thoải mái trao đổi, vẽ vời trên whiteboard nhé. Đây là cuộc thảo luận hai chiều thôi.

duthaho: Dạ vâng ạ.

Anh Minh: Được rồi, bài toán của chúng ta như sau: "Hãy thiết kế một dịch vụ có khả năng tạo ra các ID duy nhất (unique ID) cho một hệ thống quy mô lớn, ví dụ như YouTube hoặc một sàn thương mại điện tử. Yêu cầu là ID phải ngắn gọn và hệ thống phải đáp ứng được lưu lượng truy cập rất cao."

Em đã hiểu rõ đề bài chưa?

Giai đoạn 1: Làm rõ yêu cầu

duthaho: Dạ em đã hiểu đề bài. Trước khi đi vào giải pháp, em xin phép hỏi một vài câu để làm rõ hơn các yêu cầu của hệ thống ạ.

Anh Minh: Rất tốt, em hỏi đi.

duthaho:

1. Về chức năng: ID này sẽ được dùng ở đâu ạ? Ví dụ như trong URL hay chỉ trong nội bộ hệ thống? Điều này sẽ ảnh hưởng đến định dạng của ID, ví dụ nó có cần phải "URL-safe" không?

2. Về phi chức năng:

   • Thông lượng (Throughput): Khi anh nói "lưu lượng rất cao", con số cụ thể chúng ta hướng đến là khoảng bao nhiêu ID mỗi giây ạ? Ví dụ 10,000 hay 100,000 ID/giây?

   • Độ trễ (Latency): Thời gian phản hồi để tạo một ID có yêu cầu khắt khe không ạ? Ví dụ dưới 10ms hay 50ms?

   • Tính duy nhất: Yêu cầu là duy nhất 100% hay chỉ cần xác suất trùng lặp cực kỳ thấp là được ạ?

   • Thứ tự: ID được tạo ra có cần phải sắp xếp được theo thời gian không ạ?

Anh Minh: (Gật đầu, tỏ vẻ hài lòng) Những câu hỏi rất xác đáng. Giả sử các yêu cầu cụ thể như sau nhé:

• ID cần phải ngắn và an toàn cho URL (URL-safe).

• Thông lượng mục tiêu là 50,000 ID/giây ở mức đỉnh điểm.

• Độ trễ phải dưới 10ms.

• Yêu cầu duy nhất 100%.

• Việc sắp xếp được theo thời gian là một lợi thế lớn, nhưng không bắt buộc.

Giai đoạn 2: Thảo luận các hướng tiếp cận

duthaho: Dạ em cảm ơn anh. Với các yêu cầu này, em nghĩ đến một vài hướng tiếp cận với các sự đánh đổi khác nhau.

Đầu tiên là phương án đơn giản nhất: dùng Auto-Increment của Database.

• Ưu điểm: Rất dễ triển khai, đảm bảo duy nhất và tuần tự.

• Nhược điểm: Đây sẽ là một nút cổ chai (bottleneck) cực lớn và là điểm lỗi duy nhất (Single Point of Failure). Nó không thể đáp ứng được 50,000 request/giây. Do đó, em xin phép loại phương án này.

Anh Minh: Anh đồng ý. Vậy còn phương án nào khác không?

duthaho: Dạ có ạ. Một phương án phân tán hoàn toàn là dùng UUID.

• Ưu điểm: Không cần một dịch vụ tập trung, các máy chủ tự sinh ID nên khả năng mở rộng là vô hạn, không có điểm lỗi duy nhất.

• Nhược điểm: UUID quá dài (36 ký tự), không đáp ứng yêu cầu "ID ngắn gọn". Hơn nữa, UUID phiên bản 4 phổ biến thì hoàn toàn ngẫu nhiên, không sắp xếp được theo thời gian, gây ảnh hưởng xấu đến hiệu năng index của database.

Anh Minh: Ok. Vậy có vẻ UUID cũng chưa phù hợp.

duthaho: Dạ đúng ạ. Để cân bằng các yếu tố, em đề xuất xây dựng một dịch vụ tạo ID tập trung (Centralized Service). Có hai hướng triển khai phổ biến cho dịch vụ này:

1. Dùng Redis INCR: Ta có thể dùng lệnh INCR nguyên tử của Redis để tạo ra một chuỗi số tuần tự. Sau đó mã hóa số này sang Base62 để có ID ngắn và URL-safe.

2. Dùng thuật toán kiểu Twitter Snowflake: Xây dựng một dịch vụ sinh ra số 64-bit duy nhất, sau đó cũng mã hóa sang Base62.

Anh Minh: Rất hay. Em có thể phân tích sâu hơn về ưu và nhược điểm của việc dùng Redis và Snowflake không?

duthaho: Dạ được ạ.

• Với Redis INCR:

  • Ưu điểm: Rất nhanh (in-memory), thông lượng cao trên một node, triển khai đơn giản hơn Snowflake.

  • Nhược điểm: Vẫn có nguy cơ là điểm lỗi duy nhất. Mặc dù có thể dùng Redis Sentinel/Cluster để tăng tính sẵn sàng, nhưng vẫn có độ trễ khi failover. Quan trọng nhất, khả năng mở rộng bị giới hạn bởi năng lực của một node Redis duy nhất, vì lệnh INCR trên một key không thể phân tán ra nhiều node.

• Với Snowflake:

  • Ưu điểm: Được thiết kế để mở rộng theo chiều ngang và có tính sẵn sàng cao ngay từ đầu. ID sinh ra có thể sắp xếp theo thời gian, đây là lợi thế rất lớn cho việc truy vấn và phân tích dữ liệu. Tổng thông lượng của hệ thống rất lớn.

  • Nhược điểm: Phức tạp hơn trong việc triển khai và vận hành, đòi hỏi các thành phần phụ trợ như Zookeeper để quản lý machine ID và NTP để đồng bộ thời gian.

Với yêu cầu về thông lượng lớn và tính sẵn sàng cao, em nghĩ phương án Snowflake là phù hợp nhất cho bài toán này trong dài hạn.

Giai đoạn 3: Đi sâu vào giải pháp

Anh Minh: Anh đồng ý với lựa chọn của em. Em có thể mô tả cấu trúc của một ID theo kiểu Snowflake và kiến trúc tổng quan của dịch vụ này không?

duthaho: Dạ. ID 64-bit của Snowflake được cấu thành từ 3 phần chính ạ:

1. Timestamp (41 bits): Số mili giây tính từ một mốc thời gian (epoch), cho phép hệ thống hoạt động trong ~69 năm.

2. Machine ID (10 bits): Mã định danh cho máy chủ tạo ID, cho phép có tối đa 1024 máy chủ trong cụm.

3. Sequence Number (12 bits): Số thứ tự cho các ID được tạo ra trong cùng 1 mili giây trên cùng 1 máy chủ, cho phép tạo tối đa 4096 ID/ms/máy.

Về kiến trúc tổng quan, hệ thống sẽ bao gồm:

• Một cụm các ID Generator Server: Chạy logic tạo ID Snowflake.

• Một Load Balancer: Đứng trước để phân phối request.

• Một dịch vụ Coordination (như Zookeeper/Etcd): Để đảm bảo mỗi Generator Server khi khởi động sẽ được cấp một Machine ID duy nhất.

Anh Minh: Em đã đề cập đến 2 vấn đề vận hành khá khó của Snowflake. Một là quản lý Machine ID, hai là đồng bộ thời gian. Em sẽ giải quyết chúng như thế nào?

duthaho: Dạ, với Machine ID, em sẽ dùng Zookeeper. Mỗi server khi khởi động sẽ kết nối tới Zookeeper và đăng ký một "ephemeral node" để nhận một Machine ID duy nhất từ một pool đã định sẵn. Vì là ephemeral node, nếu server bị mất kết nối, Zookeeper sẽ tự động thu hồi Machine ID đó để cấp phát lại.

Còn với đồng bộ thời gian, tất cả các server trong hệ thống bắt buộc phải được cài đặt và cấu hình dịch vụ NTP (Network Time Protocol) để đảm bảo đồng hồ hệ thống luôn được đồng bộ chính xác.

Anh Minh: Rất rõ ràng. Giờ là một câu hỏi mở rộng. Giả sử hệ thống phát triển, và chúng ta cần nhiều hơn 1024 máy chủ tạo ID. Em sẽ làm gì?

duthaho: Dạ đây là một bài toán đánh đổi kinh điển. Vì không gian 64-bit là cố định, để tăng số bits cho Machine ID (ví dụ lên 11 bits để có 2048 máy), em buộc phải lấy 1 bit từ nơi khác.

• Lựa chọn 1: Lấy 1 bit từ Sequence Number. Machine ID sẽ là 11 bits, Sequence còn 11 bits.

  • Đánh đổi: Thông lượng trên mỗi máy giảm còn 2048 ID/ms. Tuy nhiên, tổng thông lượng hệ thống vẫn tăng. Lựa chọn này thường an toàn hơn.

• Lựa chọn 2: Lấy 1 bit từ Timestamp. Machine ID là 11 bits, Timestamp còn 40 bits.

  • Đánh đổi: Tuổi thọ của hệ thống giảm một nửa, còn khoảng 34.5 năm. Đây là rủi ro lớn trong dài hạn.

Vì vậy, em sẽ chọn phương án 1, hy sinh một chút thông lượng trên từng node để đổi lấy khả năng mở rộng hệ thống và giữ được tuổi thọ lâu dài.

Giai đoạn 4: Kết thúc

Anh Minh: Cảm ơn duthaho. Phần trình bày của em rất có cấu trúc, mạch lạc và cho thấy sự hiểu biết sâu về các trade-off trong thiết kế hệ thống. Anh không còn câu hỏi nào thêm. Em có câu hỏi nào cho anh không?

duthaho: Dạ hiện tại thì em chưa có câu hỏi nào ạ. Em cảm ơn anh Minh đã dành thời gian ạ.

Anh Minh: Ok, cảm ơn em. Bộ phận tuyển dụng sẽ liên hệ với em về kết quả trong vài ngày tới nhé. Chào em.

duthaho: Dạ, em chào anh.