UUID 중복 확률

요약

UUID v4는 랜덤으로 ID가 생성되어 반복 생성 시 ID가 중복될 수 있습니다. 중복 발생 확률을 구해보면 UUID v4는 초당 100만개의 ID를 100년동안 생성 할 시, 약 0.00009% 확률로 중복이 발생합니다.

UUID 중복 확률 계산

UUID v4란?

RFC 4122에 따르면 UUID는 5 버전까지 존재하며, 그중에 제일 많이 쓰는 버전은 랜덤으로 ID를 생성하는 4 버전입니다. UUID v4는 길이 128 bits로, 예약된 6 bits(4 bits는 버전, 2 bits variant)와 랜덤한 122 bits로 구성되어 있습니다. 참고로 RFC 4122에서는 variant를 1 bit 또는 3 bits로 사용하는 경우도 명시하고 있으나, 주로 사용하는것은 2 bits 길이의 variant입니다.

Birthday Problem

n명의 사람이 있을 때 생일이 같은 사람이 적어도 한쌍 있을 확률을 구하는 문제입니다. 이 문제를 쉽게 계산할 수 있는 다른 문제로 바꾼다면, 아무도 생일이 겹치지 않는 사건의 여사건 확률을 구하면 됩니다.

p(n)=1-\cfrac{_{365}P_{n}}{365^n}

3명의 사람이 있을때 생일이 같은 확률을 여사건 확률로 구하는 예입니다. 여사건 확률은 첫번째 생일을 365일 중 365일을 선택합니다. 두번째 생일을 365일 중 하루를 뺀 364일을 선택합니다. 마지막 생일을 365일 중 이틀을 뺀 363일을 선택합니다. 그리고 여사건 확률을 이용하여 생일이 겹칠 수 있는 확률을 구한다면 0.82% 확률을 구할 수 있습니다.

p(3)=1-\cfrac{365}{365}\times\cfrac{364}{365}\times\cfrac{363}{365}

UUID v4의 중복 확률 근사 계산

Birthday Problem을 이용하여, UUID v4의 중복 확률을 계산할 수 있습니다. 365일 대신에 122 bits로 표현할 수 있는 2^{122} 값을 넣고, 총 ID 생성 개수를 수식에 입력하면 중복 확률을 계산할 수 있습니다.

p(n)=1-\cfrac{_{2^{122}}P_{n}}{{2^{122}}^{n}}

하지만 2^{122}는 값이 너무나도 크기 때문에, 손으로도 PC로도 계산할 수 없습니다. 다행히도 계산하기 쉬운 근사 식이 존재하여 근사식을 이용하면 확률을 구할 수 있습니다.

p(n)=1-e^{-n^2/(2\times365)}

python을 이용하여 UUID v4의 중복 확률을 근사 계산해보겠습니다. UUID v4로 생성하는 ID는 초당 100만개의 ID를 100년동안 생성한다면 1000000\times100\times365\times24\times60\times60 개의 UUID가 생성됩니다.

from math import exp

def cal_birthday_problem_approximation(n, d):
        return 1 - exp(-n**2 / (2 * d))

print(cal_birthday_problem_approximation(1000000*100*365*24*60*60, 2**122)*100)

python 코드를 실행해보면 0.00009%의 확률로 UUID v4 중복 확률이 계산됩니다.

중복 확률이 있는 UUID 사용

대부분의 서비스에서 100만 RPS 처리면 충분히 큰 처리량이라고 볼 수 있습니다. 0.00009% 확률이 충분히 작다고 느끼신다면 UUID v4를 ID 생성에 사용할 수 있습니다. 하지만 항공이나 자율 주행 등 안전과 관련된 서비스에서는, 아무리 작은 확률도 무시 못할 것입니다. 또는 여러 서비스와 연계되는 서비스는 서비스 장애가 전파 되므로, 사용을 자제할 수 있습니다. 따라서 서비스를 고려하여 UUID v4 사용 여부를 결정하여야 합니다.