'통계적으로 불가능한' 일이 발생할 때: UUID v4 충돌 분석

A 개발자가 최근 Hacker News에서 충격적인 사실을 공유했습니다: 그들의 데이터베이스에서 중복된 UUID v4가 발견된 것입니다. 이 시나리오는 겉보기에 불가능해 보였습니다: 데이터베이스에는 단 15,000개의 레코드만 있었고, 1년의 간격을 두고 생성된 두 레코드가 정확히 동일한 식별자 b6133fd6-70fe-4fe3-bed6-8ca8fc9386cd를 공유하고 있었습니다.

대부분의 엔지니어에게 이것은 악몽 같은 시나리오입니다. 이처럼 작은 데이터셋에서 UUID v4 충돌이 발생할 수학적 확률은 대략 $2 \times 10^{-29}$입니다. 한 댓글 작성자가 언급했듯이, 이를 설명하자면 "우주 수명 동안 발생하는 충돌 횟수가 당신의 간에 있는 원자 수보다 적습니다."

하지만 충돌은 실제로 일어났습니다. 수학적 이론과 운영 환경의 실제 사이의 이러한 불일치는 엔트로피, 의사 난수 생성기(PRNGs), 그리고 "통계적 불가능성"을 가정하는 것의 위험성에 대해 중요한 대화를 이끌어냅니다.

수학 vs. 현실

UUID v4는 122비트의 무작위성에 의존합니다. 모든 비트가 진정으로 무작위인 완벽한 세상이라면 충돌 확률은 천문학적입니다. 하지만 수학은 완벽한 엔트로피 소스를 가정합니다. 현실 세계에서 무작위성은 소프트웨어 라이브러리와 하드웨어 인터페이스가 제공하는 겉모습일 뿐이며, 이는 미묘하고 치명적인 방식으로 실패할 수 있습니다.

한 숙련된 엔지니어가 지적했듯이:

UUIDv4의 보안은 고품질 엔트로피 소스의 가정에 기반합니다. 이 가정은 하드웨어 결함, 일반적인 소프트웨어 버그, 그리고 "고품질 엔트로피"가 실제로 무엇을 의미하는지 이해하지 못하는 개발자들에 의해 무효화될 수 있습니다.

충돌이 실제로 발생하는 이유

"통계적으로 불가능한" 충돌이 발생할 때, 범인은 UUID 알고리즘 자체가 아니라 ID를 생성하는 환경인 경우가 거의 대부분입니다. 커뮤니티는 몇 가지 높은 확률의 원인을 식별했습니다:

1. "사람" 요인 (데이터 관리)

99%의 경우, 중복된 UUID는 충돌이 아니라 데이터 관리 오류입니다. 일반적인 원인은 다음과 같습니다:

• Data Migrations: 실수로 동일한 CSV를 두 번 가져오거나 데이터베이스 스냅샷을 운영 환경에 복원하는 경우.
• Retry Logic Bugs: UUID를 생성하고, 삽입을 시도하다가 실패한 후, 여전히 스코프 내에 있는 동일한 변수를 사용하여 작업을 재시도하는 코드 경로.
• Manual Injection: 사용자가 또는 개발자가 이미 알고 있는 UUID를 요청에 수동으로 삽입하는 경우.

2. 엔트로피 고갈 및 PRNG 실패

데이터가 정말로 독립적으로 생성되었다면, 문제는 **의사 난수 생성기(PRNG)**에 있습니다.

• Poor Seeding: PRNG가 동일한 시드(예: 현재 밀리초 단위의 타임스탬프)로 초기화되면, 두 개의 서로 다른 프로세스가 정확히 동일한 수의 시퀀스를 생성할 수 있습니다.
• VM State Duplication: 가상화 환경에서 PRNG이 활성화된 상태로 VM이 클론되거나 스냅샷이 찍히면, 자식 프로세스가 부모 프로세스와 정확히 동일한 엔트로피 상태를 상속받아 동일한 UUID를 생성할 수 있습니다.
• Kernel Bugs: OS 커널의 드문한 레이스 컨디션(예: 멀티 프로세서 시스템에서의 /dev/random 읽기)은 서로 다른 프로세스가 동일한 바이트를 받는 결과로 이어질 수 있습니다.

3. 결정론적 환경

일부 환경은 의도적으로 결정론적입니다. 언급된 주목할 만한 예는 Googlebot입니다. 특정 크롤러에 의해 crypto.getRandomValues()가 실행될 때 결정론적으로 작동할 수 있다는 보고가 있었으며, 이는 그들이 스크립트를 실행할 때마다 동일한