ID duy nhất ở quy mô vũ trụ

 (jasonfantl.com)
25 điểm bởi GN⁺ 2026-02-20 | 4 bình luận | Chia sẻ qua WhatsApp
  • Khảo sát cách gán ID tuyệt đối không trùng lặp cho thiết bị hoặc đối tượng, đồng thời so sánh phương pháp ngẫu nhiên (random) và xác định (deterministic)
  • Với phương pháp ngẫu nhiên, nếu dùng số bit đủ lớn thì có thể đưa xác suất va chạm về gần như 0 trên thực tế; có nhiều mức từ UUID (122 bit) đến giới hạn tính toán của toàn vũ trụ (798 bit)
  • Với phương pháp xác định, bài viết đề xuất nhiều sơ đồ như bộ đếm trung tâm, cấu trúc phân cấp ủy quyền (Dewey), cây nhị phân (Binary), token (Token), đồng thời phân tích bằng mô phỏng đặc tính tăng trưởng độ dài ID của từng cách
  • Bài viết cũng đưa ra chứng minh toán học rằng mọi sơ đồ xác định đều không thể tránh tăng trưởng tuyến tính (linear) trong trường hợp xấu nhất
  • Kết quả cho thấy cách thực tế và hiệu quả ngay cả khi mở rộng tới quy mô vũ trụ là tạo ID ngẫu nhiên, còn các phương pháp xác định thì kém hiệu quả

Sự cần thiết của ID duy nhất và cách đặt bài toán

  • Nhận dạng đối tượng là nền tảng của mọi hệ thống như sản xuất, logistics, truyền thông, bảo mật; khi mở rộng quy mô lớn, việc gán ID không trùng lặp là bài toán cốt lõi
  • Nếu loài người mở rộng tới quy mô thiên hà, vẫn cần một hệ thống ID không trùng lặp
  • Bài toán được đặt ra là: “Làm thế nào để tạo ra một ID tuyệt đối không bị trùng lặp?”

Phương pháp ngẫu nhiên (Random)

  • Cách đơn giản nhất là chọn một số ngẫu nhiên
    • Có thể tạo ở bất kỳ đâu mà không cần quản lý tập trung hay đồng bộ hóa
  • Xác suất va chạm có thể điều khiển bằng cách tăng số bit, từ đó điều chỉnh để gần như bằng 0 trên thực tế
  • UUID (122 bit) được kỳ vọng sẽ xảy ra va chạm khi tạo khoảng $2^{61}$ ID
  • Nếu xét giới hạn tính toán của toàn vũ trụ (10¹²⁰ lần) thì cần 798 bit
    • Tính theo đơn vị nguyên tử (10⁸⁰ đối tượng) là 532 bit, còn 1g nanobot (10⁵⁶ đối tượng) là 372 bit
  • Điều quan trọng là phải có độ ngẫu nhiên thực sự, khuyến nghị dùng CSPRNG hoặc nguồn số ngẫu nhiên lượng tử
    • Cần cấm các seed phổ biến hoặc ID hằng số (ví dụ: all-zero)

Phương pháp xác định (Deterministic)

  • Cách bộ đếm trung tâm là một máy chủ duy nhất cấp phát ID tuần tự
    • Do vấn đề khả năng truy cập, bài viết đề xuất cấu trúc ủy quyền giữa vệ tinh và thiết bị (Dewey)
  • Sơ đồ Dewey: ID phân cấp dạng A.B.C, được biểu diễn bằng mã hóa Elias omega
    • Tùy theo cấu trúc cây mà có thể tăng trưởng theo log hoặc tuyến tính
  • Sơ đồ Binary chia không gian ID thành cây nhị phân, trong một số trường hợp hiệu quả hơn Dewey
  • 2-Adic Valuation bảo đảm tính duy nhất bằng toán học, là một biến thể của Binary
  • Sơ đồ Token cho thấy tăng trưởng theo log trong cấu trúc chuỗi, nhưng khi bề rộng tăng thì chuyển sang tuyến tính

Chứng minh tính tất yếu của tăng trưởng tuyến tính

  • Dựa trên tiền đề rằng mọi đường gán ID đều phải duy nhất, bài viết tính số lượng đường có thể có
  • Khi số nút là n, số lượng ID cần thiết tăng lên thành $2^{n-1}$
  • Vì vậy độ dài ID tối thiểu là O(n), tức không thể tránh tăng trưởng tuyến tính trong trường hợp xấu nhất
  • Không có thuật toán nào có thể duy trì tăng trưởng theo log trong mọi trường hợp

Mô phỏng các mô hình mở rộng

  • Thử nghiệm với nhiều mô hình tăng trưởng khác nhau như Random Recursive Tree, Preferential Attachment, Fitness Model
    • Ở quy mô nhỏ (2.048 nút), Binary vượt trội, còn Dewey và Token khác nhau tùy tình huống
    • Trong mô hình Preferential, Dewey là hiệu quả nhất
    • Trong mô hình Fitness, Dewey và Binary có hiệu năng tương đương
  • Trong thí nghiệm quy mô một triệu nút, Dewey và Token vẫn duy trì tăng trưởng theo log
    • Độ dài ID có thể xấp xỉ theo dạng ≈ 6.55 × ln(n)

Mô hình mở rộng ở quy mô thiên hà và vũ trụ

  • Sự lan rộng giữa các hành tinh được mô hình hóa như một mặt sóng (front) với tốc độ cố định
    • Mỗi hành tinh tạo khoảng 10⁹ ID rồi tiếp tục lan sang hành tinh kế tiếp
  • Với bán kính thiên hà khoảng 2.121 hành tinh, khi lan khắp thiên hà thì độ dài ID vào khoảng 288.048 bit
  • Nếu tính cả lan rộng giữa các thiên hà (khoảng 7.816 bước), sẽ cần khoảng 2,2 tỷ bit (281MB)
  • Các phương pháp xác định kém hiệu quả, còn phương pháp ngẫu nhiên (798 bit trở xuống) thì vượt trội về hiệu quả

Bảo mật và các điểm cần cân nhắc thêm

  • Có thể áp dụng hệ thống xác minh dựa trên chữ ký để ngăn giả mạo ID
    • Với ID ngẫu nhiên, có thể dùng khóa công khai làm ID; với sơ đồ xác định, nút cha ký vào khóa của nút con
  • Cần có mã sửa lỗi và quản lý phiên bản
  • Với các đối tượng không thể lưu ID (ví dụ: hành tinh), có thể quản lý bằng cách ánh xạ nhiều ID
  • Cũng bàn đến việc ID có nên được duy trì khi thay thế thành phần, như trong nghịch lý con tàu Theseus
  • Các khái niệm liên quan: Decentralized Identifiers (DID), Ancestry Labeling Schemes

Kết luận

  • Các sơ đồ xác định thú vị về mặt lý thuyết nhưng ít tính thực tiễn
  • Tạo ID ngẫu nhiên là phương án thực tế và hiệu quả ngay cả ở quy mô vũ trụ
  • Việc đưa xác suất va chạm ID về “gần như bằng 0” là lựa chọn an toàn và thực tiễn nhất

Bài viết liên quan

4 bình luận

 
mammal 2026-02-20

Nhất định hãy đọc bài gốc. Bài giải thích bằng công thức và mô phỏng kèm trực quan hóa nên đọc rất thú vị.
 
princox 2026-02-20

Chắc có thể xem việc tạo dựa trên thời gian là mang tính tuyến tính nhỉ..?
Có lẽ phải xem bản gốc mới được. Câu chuyện khá thú vị đấy.
 
hmmhmmhm 2026-02-20

Nếu bị trùng thì đúng là xui ở tầm vũ trụ nhỉ...(?)
 
GN⁺ 2026-02-20
Ý kiến trên Hacker News

  • Phân tích này không hoàn toàn công bằng. Khi thiết kế UUID, người ta có xét đến tính cục bộ (locality), tức là tốc độ ánh sáng, nhưng khi tính xác suất va chạm thì lại bỏ qua điều đó. Trên thực tế, để một va chạm có ý nghĩa thì hai UUID phải có tiếp xúc nhân quả (causal contact) sau khi được tạo ra. Vì vậy, áp dụng trực tiếp nghịch lý ngày sinh (birthday paradox) là cách tiếp cận sai. Nếu tính đến tính cục bộ, kích thước UUID cần thiết có lẽ sẽ nhỏ hơn rất nhiều so với 800 bit mà bài viết nói đến. Tôi chưa làm phép tính toán học, nhưng có lẽ sẽ không quá 256 bit. Tôi thực sự thích HN vì đây là một trong số ít nơi vẫn có những thảo luận kỹ thuật khắt khe như thế này một cách nghiêm túc

    • Tôi từng đọc một giả thuyết về sự giãn nở vũ trụ khiến các thiên hà xa dần nhau và không thể trao đổi thông tin với nhau nữa. Theo giả thuyết đó, các dạng sống có tri giác sẽ phải hội tụ về nơi có mật độ khối lượng cao nhất để sinh tồn. Cuối cùng, trước khi vũ trụ chết nhiệt, có thể sẽ xảy ra một “đại hội ngộ” nơi các nền văn minh ngoài hành tinh tụ họp lại. Biết đâu đến lúc đó mới xuất hiện va chạm UUID. Tôi hình dung đám Vogon gắn UUID vào từng thẻ XML làm thống kê trở nên hỗn loạn
    • Tôi từng nhận một thùng Intel NIC mà tất cả đều có cùng một địa chỉ MAC. Tôi nhớ mình đã mất mấy ngày khổ sở mới tìm ra nguyên nhân
    • Khi bàn về những xác suất cực thấp, có lẽ cũng nên tính đến khả năng chúng ta đang hiểu sai về vũ trụ học. Có thể nón ánh sáng (light cone) không phải là giới hạn nhân quả
    • Cần tính cả thời gian lẫn tính cục bộ. Thời gian cho đến khi proton phân rã và vật chất biến mất chỉ vào khoảng 10^56 nano giây
    • Phê bình này là chính xác. Bài gốc là một thí nghiệm tư duy thú vị, nhưng đã phóng đại vấn đề vì bỏ qua tính nhân quả. Trên thực tế, va chạm UUID chỉ có ý nghĩa trong phạm vi các hệ thống có giao tiếp với nhau. Những hệ thống đó bị giới hạn bởi nón ánh sáng. 128 bit là đủ cho các hệ thống mà loài người tạo ra trong cả nghìn năm, còn 256 bit thì đã là quá mức ngay cả với toàn bộ vũ trụ

  • Khi tính số lượng đối tượng có thể được gán địa chỉ, cần xét đến việc địa chỉ của mỗi đối tượng ít nhất phải được lưu ở đâu đó một lần. Nếu để lưu một bit cần Npb hạt, thì khi số bit của địa chỉ tăng lên, số đối tượng có thể gán địa chỉ sẽ giảm xuống. Vì vậy có thể tính số lượng tối đa đối tượng có thể gán địa chỉ bằng một quan hệ dạng Nthg = Np / (Npb * f(Ntng))

  • Tôi từng phải tranh luận rằng ID ngẫu nhiên 256 bit là đủ để không cần kiểm tra va chạm. Đồng nghiệp muốn thêm logic xác minh va chạm phức tạp, nhưng tôi giải thích rằng 2^256 có quy mô tương đương số nguyên tử trong vũ trụ có thể quan sát được. Tôi thuyết phục họ rằng xác suất trung tâm dữ liệu nổ tung hàng triệu lần trước khi xảy ra va chạm còn cao hơn. Cuối cùng chúng tôi đi đến kết luận rằng chỉ 128 bit cũng đã đủ

    • Nhưng nếu trong môi trường phân tán có các chủ thể không đáng tin cậy tạo ID, thì vẫn cần xác minh vì có khả năng va chạm do ác ý. Ngược lại, nếu là một hệ thống đơn lẻ thì chỉ cần bộ đếm đơn giản, còn nếu có nhiều máy chủ thì có thể chia khoảng bằng bộ đếm phân mảnh (sharded counter)
    • Thực ra phép tính còn đơn giản hơn. Tổng lượng dữ liệu của toàn nhân loại hiện vẫn chưa tới 1 yottabyte. Theo nghịch lý ngày sinh, xác suất va chạm 50% xảy ra ở mức khoảng 2^128 mục. ID 256 bit là 32 byte, nên 2^128 * 32 byte = 10^16 yottabyte. Tức là xác suất va chạm thấp đến mức thiên văn

  • Có một cách tính cho rằng nếu gán ID cho mọi nguyên tử thì sẽ cần khoảng 532 bit. Nhưng trên thực tế, ta cũng sẽ muốn gán ID cho các nhóm nguyên tử, như vi mạch, ô tô, v.v., nên con số này có thể còn lớn hơn

    • Thực ra không phải mỗi hạt một ID, mà chỉ cần một ID cho mỗi loại hạt. Theo các định luật vật lý, các hạt đồng nhất là không thể phân biệt
    • Ngay cả khi tính đến các nhóm nguyên tử thì số bit tăng thêm có lẽ cũng không đáng kể
    • UUIDv∞ có lẽ tối thiểu khoảng 536 bit? Nếu thêm ID nhóm hay dấu thời gian thì có khi lên đến 1024 bit
    • Mỗi khi neutrino dao động thì có cần cấp ID mới không? May mà với electron thì chỉ cần một cái là đủ

  • Có một ý tưởng dùng bộ bài để biểu diễn ID. Nếu biểu diễn mỗi lá trong 52 lá bằng một ký tự Unicode thì sẽ dễ đọc, khó sửa thủ công và thuận lợi cho việc nhận diện mẫu. Nếu xáo bộ bài thật rồi dùng camera đọc vào thì còn có thể dùng làm seed ngẫu nhiên. Có một ý tưởng tương tự là DiceKeys

    • Nhưng điểm yếu lớn nhất là “xáo cho đúng cách”

  • Đây là một cách trực quan hóa và góc nhìn rất hay. Tôi đã thiết kế cơ sở dữ liệu xoay quanh các định danh ngẫu nhiên nhỏ nhất có thể. Tôi cho rằng các định danh phổ quát như thế này trên thực tế chính là “đĩa vàng” duy nhất. Trong quản lý dữ liệu khoa học hay ngành thư viện học, khái niệm này đang bị đánh giá thấp. Rất nhiều vấn đề ở các tổ chức lớn lẽ ra có thể được giải quyết bằng thiết kế định danh tốt hơn.
    Bài liên quan: Identifiers Deep Dive, Trible Structure

    • Danh tính của một thực thể cũng có thể được định nghĩa theo cách nội tại (intrinsic). Tại sao hợp đồng nhất quán (consistency contract) lại không được?

  • Tôi đang đọc đến khoảng trang 281 của cuốn The Galaxy, and the Ground Within của Becky Chambers.
    Ví dụ về một thông điệp trong sách:

    Received Message
Encryption: 0
From: GC Transit Authority --- Gora System (path: 487-45411-479-4)
To: Ooli Oht Ouloo (path: 5787-598-66)
Subject: URGENT UPDATE

    Tôi cực kỳ yêu series này. Bối cảnh một vũ trụ đa chủng loài sử dụng hệ thống địa chỉ tuyến đường được đồng thuận tập trung thật thú vị

    • Tôi đề xuất một ví dụ tương tự là A Fire Upon The Deep của Vernor Vinge. Cách dán nhãn liên lạc liên thiên hà trong đó rất thú vị
    • Đặc biệt ấn tượng với cảnh họ sợ khái niệm phô mai. Cuốn thứ hai trong series, A Closed and Common Orbit, là hay nhất

  • Gần đây tôi mới biết đến Snowflake ID. Nó được dùng ở Twitter, Discord, Instagram, Mastodon, v.v. Đây là cách giảm kích thước ID bằng cách kết hợp timestamp + ngẫu nhiên, nên tôi thấy tiếc vì bài viết không nhắc đến.
    Tham khảo: Snowflake ID trên Wikipedia, video của Tom Scott.
    Nếu thay một phần bit timestamp của Snowflake bằng bit ngẫu nhiên thì có vẻ có thể tạo 4 tỷ ID mỗi giây

    • Thực ra Snowflake có cấu trúc gần như UUID v1. Chỉ là nhỏ bằng một nửa
    • Một ý tưởng tương tự là DRUUID
    • Nhưng để toàn bộ vũ trụ đồng ý về một chiếc đồng hồ duy nhất thì gần như là bất khả thi
    • Cách này cũng tương tự BSON ID

  • Tôi tự hỏi liệu có thể tạo ID dựa trên các hiện tượng quan sát được hay không. Có thể tính duy nhất sẽ được đảm bảo nhờ những đặc tính được phân biệt bởi thời gian và khoảng cách. Ví dụ, mẫu ánh sao tại một thời điểm cụ thể chỉ có thể được một người duy nhất nhìn thấy. Nó giống với cách dùng nhiễu như đèn dung nham để làm entropy. Nếu có thể định nghĩa một hệ tọa độ cho toàn bộ vũ trụ, thì có lẽ có thể tạo ID duy nhất bằng tổ hợp thời gian cục bộ + x + y + z + salt

  • Cách dùng UUID ngẫu nhiên vượt trội hơn nhiều về mặt vòng đời. Số thiết bị có thể hoạt động đồng thời là hữu hạn, và khác với UUID dạng cây, khi thiết bị bị loại bỏ thì ID có thể được tái sử dụng. Trong thực tế, có lẽ thuật toán lai trộn giữa gốc dựa trên vị trí + các bit con ngẫu nhiên sẽ là thực dụng nhất