분산 ID 생성의 진화는 중앙 집중식 데이터베이스 시퀀스에서 시작되어 마이크로서비스 아키텍처의 병목 현상이 되었고, Twitter의 Snowflake와 UUID 변형으로 발전했습니다. 초기 접근법은 NTP 동기화 시계에 크게 의존했지만, 이는 윤초, 시계 드리프트 및 네트워크 파티션 중에 취약함을 드러냈습니다. 사건 소싱 및 전 세계적으로 일관된 로깅에 대한 현대적인 요구는 협조 오버헤드 없이 인과 관계를 존중하는 엄격히 단조로운 시퀀스를 요구했습니다.
전통적인 접근 방식은 가용성과 순서 간의 시계가 skew되는 딜레마에 직면해 있습니다. 순수 물리적 타임스탬프는 밀접한 동기화가 필요하여 CAP 정리에 따라 파티션 내성을 위반하고, Lamport 타임스탬프나 벡터 시계와 같은 순수 논리적 시계는 시간적 지역성과 데이터베이스 압축 효율성을 희생합니다. 데이터베이스 색인 효율성을 위해 k-소트 가능성이 요구될 경우 도전이 더욱 커집니다. 이 굴곡 시간 순서는 엄격한 단조성과 공존해야 하며, 장애 복구 시 뒤로 밀려나는 일이 없어야 합니다. 또한 해저 케이블이 끊길 때 지역적 고립으로 인해 ID 충돌이나 가용성 손실이 발생해서는 안 됩니다.
물리적 시간(밀리초 구성 요소)과 논리적 카운터가 결합된 Hybrid Logical Clock (HLC) 아키텍처를 구현하고, 노드 ID 파티셔닝을 보강합니다. 각 지역 클러스터는 시작 시점이나 멤버십 변경 시 etcd나 ZooKeeper와 같은 합의 서비스에서 10-16 비트의 노드 ID를 받습니다. 각 노드 내에서 HLC는 물리적 시간이 진행되지 않았을 때 논리적 구성 요소를 증가시켜 시계 조정에도 불구하고 단조성을 보장합니다.
ID 구조는: 에폭 밀리초(41 비트) + 논리적 카운터(12 비트) + 노드 ID(10 비트)로 결합됩니다. 파티션 중에는 노드가 로컬 논리 카운터 공간에서 계속 할당합니다. 파티션이 복구되면 HLC의 max-plus-one 병합 규칙이 중앙 집중식 조정 없이 인과 관계 보존을 보장합니다.
한 글로벌 암호화폐 거래소는 AWS us-east-1, eu-west-1, 및 ap-southeast-1에서 트랜잭션 ID 생성을 요구했습니다. 이 시스템은 규제 감사 추적을 위해 엄격한 시간 순서를 유지하면서 초당 800만 개의 주문을 처리해야 했습니다. 해저 케이블 유지 보수 중 네트워크 파티션이 발생하면서 이전 시스템에서 UUIDv4 충돌 위험이 발생해 데이터베이스 고유 제약 조건을 위반하고 거래 중단이 발생했습니다.
해결책 1: 중앙 집중식 PostgreSQL 시퀀스와 캐싱
PostgreSQL 시퀀스를 애플리케이션 수준에서 배치 할당(한 번에 10,000 ID 가져오기)하여 데이터베이스 왕복을 줄였습니다. 그러나 아시아-태평양 네트워크 파티션 동안 캐싱 노드는 90초 이내에 할당된 범위를 소진하여 UUID 생성으로 fallback하여 감사 추적 순서를 파괴했습니다. 단일 RDS 인스턴스는 또한 교차 지역 쓰기에서 140ms 지연을 발생시켜 50ms 이하의 생성 요구를 위반했습니다.
해결책 2: Snowflake에서 영감을 받은 Twitter 알고리즘
ZooKeeper-관리 노드 ID와 함께 Snowflake를 구현한 결과, 노드당 초당 22,000 ID와 우수한 정렬성을 가진 압축된 64비트 ID를 달성했습니다. 그러나 유럽 노드에서 NTP 데몬이 윤초 희석을 경험하는 동안 미국 노드는 즉각적인 스텝을 사용하여 시스템은 중복 밀리초 타임스탬프를 생성했습니다. 이로 인해 효과적인 데이터베이스 제약 조건 확인이 필요해 처리량이 40% 저하되었습니다.
해결책 3: CRDT 수렴의 하이브리드 논리 시계
CockroachDB의 HLC 패턴을 채택하여 각 지역 리더는 지역별로 파티셔닝된 노드 ID 공간을 허용하는 로컬 논리 카운터를 유지하여 노드당 초당 4096 ID를 생성합니다. 싱가포르 케이블 절단 동안 고립된 노드는 계속해서 논리 카운터를 사용하여 ID를 생성했고, 재연결 시 HLC 비교 함수가 중복 없이 인과 관계를 보장했습니다. 이 접근 방법은 정확성 보장을 위한 128비트 ID 폭을 포기하고 파티션 동안 가용성을 유지했습니다.
선택된 해결책 및 결과
해결책 3가 파티션 내성 및 단조성 보장으로 인해 선택되었습니다. 이 시스템은 남중국해 케이블 유지 보수 중 4시간 파티션을 겪으며 중복 없이 도쿄 지역에서 초당 1200만 개의 ID를 처리했습니다. 통합 후, HLC의 happens-before 추적 덕분에 ID 재작성 없이 완료되었으며, UUID에 비해 15% 저장 비용이 감소했습니다. 이는 사전 순서가 RocksDB 압축을 줄이는 데 기여했습니다.
대부분의 지원자는 NTP가 항상 시간을 앞으로 이동한다고 가정합니다. 실제로는 공격적인 시계 skew 수정이 수백 밀리초만큼 시간을 뒤로 설정할 수 있습니다. 이 해결책은 지속적인 단조 시계를 유지하는 것을 요구합니다(예: CockroachDB의 "합성" 시간): OS가 마지막으로 할당된 ID의 물리적 구성 요소보다 작은 타임스탬프를 보고할 때 시스템은 물리적 퇴행을 무시하고 오로지 논리적 카운터만 계속 증가시킵니다.
또한 노드가 최대 드리프트 신뢰 구간을 전파하는 시계 경계 전파를 구현하여 로컬 불확실성이 10ms를 초과하는 경우 생성 요청을 거부합니다. 이 메커니즘은 ID를 발행하기 전에 비동기화된 노드를 감지합니다. 이는 외부 일관성을 위반하는 "되감기" 이상 현상을 방지합니다.
지원자는 종종 10비트 노드 ID가 1,024개의 고유 생성기만 허용한다고 간과합니다. Kubernetes 환경에서 frequent pod 재시작이 발생하면 단순한 ID 할당이 수 주 내에 네임스페이스를 소진합니다. 이 해결책은 epoch 기반 재활용을 구현합니다: 노드 ID는 etcd에서 TTL (Time-To-Live)로 리스되며, 재활용된 ID는 최대 시계 skew(일반적으로 24시간)를 초과하는 "톰스톤" 격리 기간에 들어갑니다.
재배포 중에 시스템은 해당 노드 ID가 발행한 마지막 ID의 HLC를 확인합니다. 현재 전 세계 시간이 그 타임스탬프보다 초과하면 ID를 재할당할 수 있습니다. 이를 위해 퇴역 노드 메타데이터를 추적하는 묘지 서비스가 필요합니다.
K-소트 가능 ID(예: Snowflake)는 LSM-tree 또는 B-tree 구조의 "핫 엔드"에 쓰기를 집중시켜 최신 SSTable 또는 가장 오른쪽 리프 페이지를 압도합니다. 지원자들은 종종 k-소트 가능성이 읽기 지역성을 향상시키는 동안 Cassandra나 TiKV에서 쓰기 증폭을 생성한다는 사실을 간과합니다. 이 완화 방법은 셔드 접두사를 통해 엔트로피 코딩을 도입합니다: ID 앞에 노드 ID 또는 클라이언트 세션의 4비트 해시를 추가하여 다수의 RocksDB memtable에 쓰기를 분산시키며 대략적인 시간 순서를 보존합니다.
CockroachDB의 경우 ID 열 위에 해시-셔드 인덱스를 사용합니다. 대안적으로, 최근 ID를 Redis 스트림에 버퍼링한 후 차가운 저장소에 배치 삽입함으로써 쓰기 데킹을 적용합니다. 이는 수집과 압축 주기를 분리합니다.