▲

우주적 규모의 고유 ID

 (jasonfantl.com)
2P by GN⁺ 4시간전 | ★ favorite | 댓글 1개
  • 기기나 객체에 절대적으로 중복되지 않는 ID를 부여하는 방법을 탐구하며, 무작위(random) 방식과 결정적(deterministic) 방식을 비교
  • 무작위 방식은 충분히 큰 비트 수를 사용하면 충돌 확률을 사실상 0으로 만들 수 있으며, UUID(122비트) 부터 우주 전체 연산 한계(798비트) 까지 다양한 수준 제시
  • 결정적 방식에서는 중앙 카운터, 위임형 계층 구조(Dewey) , 이진 트리(Binary) , 토큰(Token) 등 여러 스킴을 제안하고, 각 방식의 ID 길이 성장 특성을 시뮬레이션으로 분석
  • 모든 결정적 스킴은 최악의 경우 선형(linear) 성장을 피할 수 없다는 수학적 증명 제시
  • 결과적으로 우주적 확장에서도 실용적이고 효율적인 방법은 무작위 ID 생성이며, 결정적 방식은 비효율적임을 확인

고유 ID의 필요성과 문제 설정

  • 객체 식별은 제조, 물류, 통신, 보안 등 모든 시스템의 기반이며, 대규모 확장 시 중복 없는 ID 부여가 핵심 과제
  • 인류가 은하 규모로 확장할 경우에도 중복 없는 ID 체계가 필요함
  • 문제는 “어떻게 하면 절대 중복되지 않는 ID를 만들 수 있는가”로 설정됨

무작위(Random) 방식

  • 가장 단순한 방법은 임의의 수를 선택하는 것
    • 중앙 관리나 동기화 없이 어디서나 생성 가능
  • 충돌 확률은 비트 수를 늘려 제어 가능, 사실상 0에 가깝게 조정 가능
  • UUID(122비트) 는 약 $2^{61}$개의 ID를 생성할 때 충돌이 예상됨
  • 우주 전체 연산 한계(10¹²⁰회) 를 고려하면 798비트가 필요
    • 원자 단위(10⁸⁰개) 기준은 532비트, 1g 나노봇(10⁵⁶개)은 372비트
  • 진정한 무작위성 확보가 중요하며, CSPRNG나 양자 난수원 사용 권장
    • 흔한 시드나 상수 ID(예: all-zero)는 금지 필요

결정적(Deterministic) 방식

  • 중앙 카운터 방식은 단일 서버가 순차적으로 ID를 발급
    • 접근성 문제로 위성·기기 간 위임 구조(Dewey) 제안
  • Dewey 스킴: A.B.C 형태의 계층적 ID, Elias omega 코딩으로 표현
    • 트리 구조에 따라 로그형 또는 선형 성장
  • Binary 스킴은 ID 공간을 이진 트리로 분할, 일부 경우 Dewey보다 효율적
  • 2-Adic Valuation은 수학적 고유성 보장, Binary의 변형 형태
  • Token 스킴은 체인 구조에서 로그형 성장을 보이지만, 폭이 넓어지면 선형으로 전환

선형 성장의 불가피성 증명

  • 모든 ID 부여 경로가 고유해야 함을 전제로, 가능한 경로 수를 계산
  • 노드 수가 n일 때 필요한 ID 수는 $2^{n-1}$로 증가
  • 따라서 ID 길이는 최소 O(n) , 즉 최악의 경우 선형 성장 불가피
  • 어떤 알고리듬도 모든 경우에서 로그형 성장을 유지할 수 없음

확장 모델 시뮬레이션

  • Random Recursive Tree, Preferential Attachment, Fitness Model 등 다양한 성장 모델로 실험
    • 소규모(2,048노드)에서는 Binary가 우수, Dewey·Token은 상황별 차이
    • Preferential 모델에서는 Dewey가 가장 효율적
    • Fitness 모델에서는 Dewey와 Binary가 유사 성능
  • 백만 노드 규모 실험에서도 Dewey·Token은 로그형 성장 유지
    • ID 길이 ≈ 6.55 × ln(n) 형태로 근사 가능

은하 및 우주 규모 확장 모델

  • 행성 간 확산은 일정 속도의 파동(front) 형태로 모델링
    • 각 행성은 약 10⁹개의 ID를 생성 후 다음 행성으로 확산
  • 은하 반경 약 2,121행성, 전체 확산 시 ID 길이 약 288,048비트
  • 은하 간 확산(약 7,816단계)까지 고려 시 약 22억 비트(281MB) 필요
  • 결정적 방식은 비효율적이며, 무작위 방식(798비트 이하) 이 압도적으로 효율적

보안 및 추가 고려사항

  • ID 위조 방지를 위해 서명 기반 검증 체계 적용 가능
    • 무작위 ID는 공개키를 ID로 사용, 결정적 스킴은 부모가 자식 키에 서명
  • 오류 정정 코드와 버전 관리 필요
  • ID 저장 불가 객체(예: 행성)는 여러 ID를 매핑해 관리
  • Theseus의 배 문제처럼 구성 요소 교체 시 ID 지속 여부 논의
  • 관련 개념: Decentralized Identifiers(DID) , Ancestry Labeling Schemes

결론

  • 결정적 스킴은 이론적으로 흥미롭지만 실용성 낮음
  • 무작위 ID 생성이 우주적 규모에서도 현실적이며 효율적
  • ID 충돌 확률을 “사실상 0”으로 만드는 것이 가장 안전하고 실용적인 선택임
▲
GN⁺ 4시간전  [-]
Hacker News 의견들

  • 이 분석은 완전히 공정하지 않음. UUID 설계 시 지역성(locality) , 즉 빛의 속도를 고려하면서도 충돌 확률 계산에서는 그걸 무시함. 실제로 충돌이 의미 있으려면 두 UUID가 생성 후 인과적 접촉(causal contact) 을 해야 함. 따라서 단순한 생일 역설(birthday paradox)을 적용하는 건 잘못된 접근임. 지역성을 고려하면 필요한 UUID 크기는 기사에서 말한 800비트보다 훨씬 작을 것 같음. 수학적 계산은 안 해봤지만 256비트 이상일 것 같지는 않음. HN은 이런 깐깐한 기술적 논의가 진지하게 오가는 몇 안 되는 곳이라 정말 좋아함

    • 예전에 은하들이 멀어지며 서로 정보 교환이 불가능해지는 우주 팽창 가설을 읽은 적이 있음. 그 가설에 따르면 지적 생명체들은 생존을 위해 질량 밀도가 가장 높은 곳으로 수렴하게 됨. 결국 우주의 열적 죽음 전에 외계 문명들이 한자리에 모이는 ‘대회합’이 일어날 수도 있음. 그때쯤이면 UUID 충돌이 생길지도 모름. Vogon들이 XML 태그마다 UUID를 붙이는 바람에 통계가 엉망이 되는 상상을 해봄
    • 예전에 Intel NIC를 한 상자 받았는데 전부 같은 MAC 주소였던 적이 있음. 원인을 찾느라 며칠 고생했던 기억이 있음
    • 극도로 낮은 확률을 논할 때는, 혹시 우리가 우주론을 잘못 이해하고 있을 가능성까지 고려해야 함. 빛의 원뿔(light cone)이 인과적 한계가 아닐 수도 있음
    • 시간과 지역성 둘 다 고려해야 함. 양성자가 붕괴하고 물질이 사라질 때까지의 시간은 약 10^56 나노초에 불과함
    • 이 비판이 정확함. 원문은 재미있는 사고 실험이지만 인과성을 무시해 문제를 과대평가함. 실제로 UUID 충돌은 서로 통신하는 시스템 내에서만 의미가 있음. 그런 시스템은 빛의 원뿔로 제한됨. 128비트면 인류가 천 년 동안 만들 시스템에도 충분하고, 256비트는 우주 전체에도 과함

  • 주소 지정 가능한 객체 수를 계산할 때는, 각 객체의 주소가 최소 한 번은 어딘가에 저장되어야 한다는 점을 고려해야 함. 한 비트를 저장하는 데 Npb 입자가 필요하다면, 주소 비트 수가 늘어날수록 주소 지정 가능한 객체 수는 줄어듦. 따라서 Nthg = Np / (Npb * f(Ntng)) 형태의 관계식으로 최대 주소 가능 개수를 구할 수 있음

  • 예전에 256비트 랜덤 ID면 충돌 검사를 안 해도 충분하다고 주장해야 했던 적이 있음. 동료들은 복잡한 충돌 검증 로직을 추가하자고 했지만, 2^256은 관측 가능한 우주의 원자 수와 비슷한 규모라 설명했음. 충돌이 일어나기 전에 데이터센터가 수백만 번은 폭발할 확률이 더 높다고 설득함. 결국 128비트만으로도 충분하다는 결론에 도달했음

    • 하지만 분산 환경에서 신뢰할 수 없는 주체들이 ID를 생성한다면 악의적 충돌 가능성이 있으므로 검증이 필요함. 반면 단일 시스템이라면 단순 카운터로 충분하고, 여러 서버가 있다면 샤딩된 카운터로 구간을 나누면 됨
    • 사실 계산은 더 간단함. 전 인류의 데이터 총량은 아직 1요타바이트도 안 됨. 생일 역설에 따르면 50% 충돌 확률은 2^128개 수준에서 발생함. 256비트 ID는 32바이트이므로, 2^128 * 32바이트 = 10^16 요타바이트가 필요함. 즉, 충돌 확률은 천문학적으로 낮음

  • 모든 원자에 ID를 부여한다고 가정하면 약 532비트가 필요하다는 계산이 있음. 하지만 실제로는 원자 그룹(예: 마이크로칩, 자동차 등)에도 ID를 부여하고 싶을 것이므로 더 커질 수 있음

    • 사실 입자마다가 아니라 입자 종류별로 하나의 ID만 있으면 됨. 물리 법칙상 동일 입자는 구별 불가능하기 때문임
    • 원자 그룹을 고려해도 추가되는 비트 수는 거의 없을 것임
    • UUIDv∞는 최소 536비트쯤 될까? 그룹 ID나 타임스탬프까지 넣으면 1024비트쯤 될지도 모름
    • 중성미자가 진동할 때마다 ID를 새로 부여해야 할까? 다행히 전자에는 하나만 있으면 됨

  • 카드 덱으로 ID를 표현하는 아이디어가 있음. 52장의 카드 각각을 유니코드 문자로 표현하면 읽기 쉽고, 수동 편집이 어렵고, 패턴 인식에도 유리함. 실제 카드 덱을 섞어 카메라로 읽어들이면 랜덤 시드로도 활용 가능함. 비슷한 아이디어로 DiceKeys도 있음

    • 하지만 “제대로 섞는 것”이 가장 큰 약점임

  • 멋진 시각화와 통찰임. 나는 가능한 한 작은 랜덤 식별자를 중심으로 데이터베이스를 설계했음. 이런 보편적 식별자가 사실상 유일한 ‘황금 디스크’라고 생각함. 과학 데이터 관리나 도서관학 분야에서는 이런 개념이 과소평가되고 있음. 많은 대규모 조직 문제들이 더 나은 식별자 설계로 해결될 수 있었음.
    관련 글: Identifiers Deep Dive, Trible Structure

    • 엔터티의 정체성은 내재적(intrinsic) 으로 정의할 수도 있음. 왜 일관성 계약(consistency contract) 은 안 되는가?

  • Becky Chambers의 『The Galaxy, and the Ground Within』 281페이지쯤 읽는 중임.
    책 속 메시지 예시:

    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

    이 시리즈 정말 사랑함. 다종족 우주가 중앙 합의된 경로 주소 체계를 쓰는 설정이 흥미로움

    • 비슷한 예시로 Vernor Vinge의 『A Fire Upon The Deep』을 추천함. 은하 간 통신 라벨링 방식이 흥미로움
    • 특히 치즈 개념을 두려워하는 장면이 인상 깊었음. 시리즈 중 두 번째 책 『A Closed and Common Orbit』이 최고였음

  • 최근 Snowflake ID를 알게 되었음. Twitter, Discord, Instagram, Mastodon 등에서 사용함. 타임스탬프 + 랜덤 조합으로 ID 크기를 줄이는 방식인데, 기사에서는 다루지 않아 아쉬움.
    Snowflake ID 위키, Tom Scott 영상 참고.
    Snowflake 타임스탬프의 일부 비트를 랜덤으로 바꾸면 초당 40억 개 ID를 만들 수 있을 듯함

    • 사실 Snowflake는 UUID v1과 거의 같은 구조임. 단지 절반 크기일 뿐
    • 비슷한 아이디어로 DRUUID도 있음
    • 하지만 우주 전체가 하나의 시계에 동의하는 건 불가능에 가까움
    • 이 방식은 BSON ID와도 유사함

  • 관측 가능한 현상을 기반으로 ID를 만들 수 있을까 궁금함. 시간과 거리로 구분되는 특성 덕분에 유일성이 보장될지도 모름. 예를 들어 특정 시점의 별빛 패턴은 단 한 사람만 볼 수 있음. 용암 램프처럼 노이즈를 엔트로피로 쓰는 방식과 비슷함. 만약 우주 전체의 좌표계를 정의할 수 있다면, 지역 시간 + x + y + z + salt 조합으로 유일한 ID를 만들 수 있을 것 같음

  • 랜덤 UUID 방식이 수명 측면에서 훨씬 우수함. 동시에 작동 가능한 장치 수는 한정되어 있고, 트리 기반 UUID와 달리 장치가 폐기되면 ID를 재활용할 수 있음. 현실적으로는 위치 기반 루트 + 랜덤 하위 비트를 섞은 혼합 알고리즘이 가장 실용적일 것 같음

답변달기