14. 분산 고유 ID 생성: Snowflake·UUID·ULID와 시계 역행 문제

난이도: 중상

1. 요구 속성과 상충

• 전역 유일성: 충돌이 사실상 없어야 한다(중복 ID는 데이터 손상).
• 시간 순 정렬(k-sortable): ID만 봐도 대략 생성 순서를 알 수 있으면 인덱스 삽입 지역성·시계열 조회·키셋 페이징에 유리.
• 크기: 64비트(정수)면 인덱스·저장·전송이 싸다. 128비트(UUID)는 두 배.
• 처리량: 노드별로 조정 없이 초당 수십만 개 생성 가능해야.
• 조정 비용: 매 ID마다 중앙(DB/락)을 거치면 병목·SPOF·지연. 무(無)조정이 이상적.
• 추측 불가능성: 순차 ID는 열거·스크래핑·정보 노출 위험.

핵심 상충: 시간 정렬(지역성↑) vs 추측 불가능(보안↑, 랜덤성↑), 무조정(처리량↑) vs 짧은 길이/순차성, 중앙 조정(짧고 순차) vs 가용성/확장성. 모두를 만족하는 단일 답은 없고 용도별로 고른다.

2. 방식 비교

• DB auto-increment/시퀀스: DB가 유일성·순차성을 보장. 짧고(8B) 정렬됨. 그러나 중앙 DB에 의존(SPOF·병목), 멀티 샤드/멀티 리전에서 통일이 어렵다(오프셋·스텝으로 회피하지만 운영 복잡). 미리 ID를 알 수 없어 배치 삽입에 왕복이 필요.
• UUIDv4(랜덤 128비트): 무조정·무충돌(확률적으로 0에 수렴)·어디서나 생성. 단 정렬 안 됨(완전 랜덤) → 인덱스 단편화, 16바이트로 큼, 사람이 읽기 불편. 보안상 추측은 어렵다(장점).
• Snowflake류(64비트): 보통 [부호1][타임스탬프~41b][머신 ID~10b][시퀀스~12b]. 타임스탬프 접두라 시간 정렬, 머신 ID로 노드 간 충돌 회피, 시퀀스로 같은 ms 내 다건 처리. 무조정·고처리량·64비트로 균형이 좋다. 단점은 머신 ID 할당 체계가 필요하고 시계 역행에 취약(4번).
• ULID / UUIDv7: 앞쪽에 밀리초 타임스탬프, 뒤쪽 랜덤. 시간 정렬 + 무조정 + 충돌 회피를 동시에. UUIDv7은 표준 UUID(128비트)라 호환성이 좋고, ULID는 Base32 26자로 사람이 다루기 쉽다. 머신 ID 조정이 없어 Snowflake보다 운영이 단순(대신 128비트, 랜덤 부분 덕에 같은 ms 내 엄밀한 단조성은 옵션).
• 티켓/세그먼트 서버: 중앙이 번호 구간(예: 1000개)을 노드에 묶음으로 발급하고, 노드는 그 안에서 로컬로 소진. 매 ID마다 중앙을 안 거쳐 처리량↑·DB 부하↓, 짧은 정수 유지. 구간 경계에서만 조정. 노드 장애 시 미사용 구간은 버려진다(구멍). (Flickr 티켓, 메이투안 Leaf-segment.)

3. 인덱스 지역성

B-트리 기본 키 인덱스는 키 순서로 정렬 저장된다. UUIDv4처럼 랜덤한 키는 삽입 위치가 매번 트리 전역에 흩어져, ① 거의 모든 삽입이 다른 페이지를 건드리고(랜덤 I/O·캐시 미스), ② 페이지 분할(split)이 잦아 단편화·쓰기 증폭이 커진다. 특히 InnoDB처럼 클러스터드 인덱스(데이터가 PK 순)면 데이터 자체가 흩어진다.

시간 정렬 ID(Snowflake/ULID/UUIDv7) 는 새 키가 항상 인덱스의 오른쪽 끝 부근에 추가되어, 삽입이 같은 핫 페이지에 모이고 페이지 분할이 줄어 쓰기·캐시 효율이 좋다. 또 "최근 것"이 키 범위의 끝에 모이므로 범위 조회/시계열 스캔과, WHERE id > @last ORDER BY id LIMIT n 식의 키셋 페이지네이션이 자연스럽다(생성 시간 순 = ID 순). 즉 정렬 가능한 ID는 앞 문제에서 본 키셋 페이징의 안정 키로 그대로 쓰인다. (반대 주의: 항상 끝에 몰리면 그 페이지가 쓰기 핫스팟이 될 수 있어, 극단적 쓰기 부하에선 샤드/해시 접두로 분산하기도 한다 — 지역성과 핫스팟 분산의 또 다른 상충.)

4. Snowflake 시계 역행

Snowflake는 타임스탬프가 단조 증가한다고 가정한다. NTP 보정·VM 마이그레이션·수동 변경으로 시계가 과거로 점프하면, 이미 발급한 ID보다 작은(과거) 타임스탬프로 ID를 만들게 되어 ① 정렬성이 깨지고 ② 같은 (타임스탬프, 머신, 시퀀스) 조합이 재현되어 중복 ID가 날 수 있다. 방어:

• 마지막 타임스탬프 추적: 노드가 마지막 발급 타임스탬프를 기억하고, 현재 시계가 그보다 작으면(역행) 차이가 작으면 그 시각까지 대기(spin/sleep), 크면 발급을 거부/에러로 보호.
• 시퀀스 확장으로 짧은 역행 흡수: 같은/이전 ms면 시퀀스를 이어 써 단조성을 유지하다, 고갈되면 다음 ms를 기다린다.
• 단조 시계 사용: 가능하면 벽시계 대신 단조 클록 기반으로 보정, NTP는 점프 대신 slew(서서히 보정) 설정.
• 머신 ID 유일성 보장: ZooKeeper/etcd·설정으로 머신 ID 중복을 막아, 시계가 정상일 때의 충돌을 원천 차단.

5. 게임에서의 선택

• 아이템 UID / 거래·주문 ID: 영속·인덱스 키이고 시계열 조회가 많으므로 Snowflake/UUIDv7/ULID(정렬 가능, 무조정)가 적합. 거래/결제처럼 외부 노출되는 ID는 추측 가능성도 고려.
• 로그 상관관계(correlation) ID: 서비스 간 추적용. 충돌만 없으면 되고 정렬은 덜 중요 → UUIDv4/ULID. 분산 추적 표준(Trace ID)을 따르는 게 보통.
• 매치 ID / 인스턴스 ID: 수명이 짧고 디렉터리 키로 쓰임 → Snowflake/ULID로 시간 정렬해두면 운영 조회가 편하다.
• 보안 주의: 순차/추측 가능한 ID는 "다음 ID로 남의 거래/우편/프로필 접근(IDOR)", 발급량 추정(경쟁사 분석), 열거 스크래핑에 노출된다. 외부에 노출되는 식별자는 랜덤 성분이 큰 ID(UUIDv4/ULID 랜덤부)나 별도의 불투명 토큰을 쓰고, 권한 검사를 ID 추측 불가에 의존하지 말 것(서버 권위로 소유권을 항상 확인).

요약: 내부 영속 키는 시간 정렬 가능한 무조정 ID(Snowflake/ULID/UUIDv7) 가 인덱스 지역성·키셋 페이징·운영성에서 유리하고, 외부 노출 식별자는 추측 불가능성을 우선한다. Snowflake를 쓸 땐 시계 역행 방어를 반드시 구현한다.