ULID란 무엇일까?

개요

보통 UUID를 통해 식별자의 고유값을 보장해 주거나 twitter의 snowflake를 활용하곤 합니다.

또한 ULID라는 개념도 알게 되었는데, ULID란 무엇일까요?

 

ULID의 등장배경

UUID를 사용하게 되면 정렬 없이 무작위의 값을 생성해 냅니다.

그러면 어떤 식별자가 먼저 만들어진 건지? 알 수 없습니다.

이를 해결하기 위해 ULID가 등장하게 됩니다.

 

ULID란?

https://zendesk.engineering/how-probable-are-collisions-with-ulids-monotonic-option-d604d3ed2de

Universally Unique Lexicographically Sortable Identifier의 약자로 대소문자를 구별하지 않는 시간을 나타내는 26글자와 16글자의 임의의 값으로 구성되어 있습니다.

 

한국어로 번역해 보면 Lexicographically(사전적으로) Sortable(정렬가능한) Universally Unique Identifier(범용 고유 식별자)입니다.

사전적이라는 뜻은 보통 ascii 코드의 숫자를 기준으로 문자열의 크기를 비교할 수 있는 것을 떠올리면 될 것 같습니다.

 

ULID의 Monotonicity

고유 식별자에서 최대관심사는 충돌가능성이 얼마나 낮은가입니다.

ULID는 최대 millisecond까지 감지하고, 동일한 millisecond가 감지되면 최하위 비트 위치에서 1비트를 증가하는 방법인 Monotonicity를 제공하곤 합니다.

 

이때 Randomness에서 80bit를 제공하기 때문에 2^80이라는 무작위성이 제공되고, 매우 큰 수로 판단됩니다.

하지만 무작정 큰 수라고 해서 신뢰할 수 없으며, Monotonicity 옵션을 활용할 경우 초기에 생성된 난수를 1비트씩만 증가시키기 때문에 난수가 전혀 생성되지 않습니다.

 

01EX8Y7M8MDVX3M3EQG69EEMJW
01EX8Y7M8MDVX3M3EQG69EEMJX
01EX8Y7M8MDVX3M3EQG69EEMJY
01EX8Y7M8MDVX3M3EQG69EEMJZ
01EX8Y7M8MDVX3M3EQG69EEMK0
01EX8Y7M8MDVX3M3EQG69EEMK1
01EX8Y7M8MDVX3M3EQG69EEMK2
01EX8Y7M8MDVX3M3EQG69EEMK3
01EX8Y7M8N1G30CYF2PJR23J2J < millisecond changed
01EX8Y7M8N1G30CYF2PJR23J2K
01EX8Y7M8N1G30CYF2PJR23J2M
01EX8Y7M8N1G30CYF2PJR23J2N
01EX8Y7M8N1G30CYF2PJR23J2P
01EX8Y7M8N1G30CYF2PJR23J2Q
01EX8Y7M8N1G30CYF2PJR23J2R
01EX8Y7M8N1G30CYF2PJR23J2S
         ^ look          ^ look

|---------|--------------|
    time      random

millisecond가 변경되면 time 쪽의 bit가 변경되고, millisecond가 같은 경우에는 초기에 생성된 난수를 1비트씩 증가시키는 Monotonicity 옵션의 예시입니다.

 

그래서 충돌 가능성은?

Monotonicity 옵션을 활용하는 경우 오히려 무작위 ULID를 사용하는 것보다 충돌 가능성이 적습니다.

또한 밀리 초당 1,000개의 이벤트를 처리한다고 가정해 보았을 때 향후 100년 동안 충돌할 확률이 0.000126%에 불과합니다.

 

 

 

참고자료

https://zendesk.engineering/how-probable-are-collisions-with-ulids-monotonic-option-d604d3ed2de

https://github.com/f4b6a3/ulid-creator#monotonic-ulid