Time Based UUID의 새로운 표준(IETF version 6,7,8)

TL;DR

IETF가 2022년 12월에 발행한 new time based uuid format - UUIDv7 Field and Bit Layout

Overview

네트워크 상에는 데이터베이스, 시스템 인스턴스, 블루투스 등 수많은 개체들이 존재합니다. 우리는 이 개체들을 식별하기 위해서 각각의 고유한 이름을 지어주고 싶습니다. 하지만 이를 중앙 제어 시스템으로 처리하게 되면 저장 및 검색 용량이 선형적으로 증가합니다. 이를 해결하기 위해서는 컴퓨터가 스스로 이름을 지으면서도 고유성을 충족할 수 있는 방법이 필요했습니다.

Apollo라는 기업에서 만든 NCS(Network Computing System, 네트워크 컴퓨팅 시스템)는 엔티티의 고유한 기본 ID 역할을 하는 UID(Universal IDentifier)를 도입하였습니다. UID는 단조로운 시계와 하드웨어에 영구적으로 내장된 고유 호스트 ID를 결합한 64비트의 문자열이었습니다.

Apollo는 NCS 원칙을 NCA(Network Computing Architecture, 네트워크 컴퓨팅 아키텍처)로 표준화할 때 기존 UID 설계로는 충분하지 않다고 생각했습니다. 각각의 호스트의 비트크기가 벤더사마다 달랐기 때문입니다. 따라서 UID 설계를 기반으로 공간을 128비트로 확장한 UUID(Universally Unique IDentifier)가 탄생했습니다. 비트 크기를 확장해서 더 넓은 범위의 공급업체를 수용할 수 있었습니다. 이 개념은 NCA 표준을 뛰어넘어서도 인기를 유지하며 ISO, IETF, ITU 등에 의해 표준화 되었습니다.

UUID는 이후 RFC-4122에 공식 표준화된 문서로 정의가 되었습니다. 하지만 이 표준은 꽤나 오래전인 2005년에 정의가 되었으며 최신 애플리케이션 및 데이터베이스의 활용에 여러 문제점이 있음을 발견했습니다. 다양한 기업에서 문제를 해결하기 위한 방법들을 고안했고 이들의 노력을 반영하여 2022년 12월 IETF(Internet Engineering Task Force, 국제 인터넷 표준화 기구)를 통해 새로운 버전의 UUID의 표준 초안이 등장하였습니다.

이 글에서는 기존의 UUID의 구성 요소와 각 버전별 활용, 문제점을 확인하고 새로운 UUID Version에 대한 소개와 함께 java 환경에서 사용할 수 있는 예제 코드를 첨부하였습니다.

RFC-4122 UUID

UUID는 RFC-4122에 공식으로 표준화된 문서로 정의가 되어있습니다. 길이는 128 bit이며 고유성을 보장합니다. 이 UUID는 구성 방식에 따른 다양한 버전이 존재합니다.

RFC-4122에 명세된 UUID 특징

• 길이는 128bit이며 16진수로 표현된다.
• UUID는 고유해야 한다.
• UUID를 생성하는데 등록 기관이 필요하지 않다.(중앙 집중화가 필요하지 않다)

UUID 구성요소

UUID version 1을 기반으로 구성요소를 소개하겠습니다. 다른 버전에서는 사용하지 않는 필드가 있을 수 있습니다.

https://www.uuidtools.com/uuid-versions-explained#version-1

시간 관련 필드 (time_low(32bit), time_mid(16bit), time_hi_and_version(16bit(앞에 4bit는 version))

시간 관련 필드는 생성 시점의 타임스탬프의 값을 나눠서 표현합니다. ‘time_hi_and_version’ 필드는 UUID의 버전도 포함합니다. 시관 관련 필드는 version1에서 사용이 되며 version 2는 필드의 일부를 POSIX UID/GID(사용자, 그룹 식별자) 정보로 대체됩니다. version 3~5에서는 해시값 혹은 난수로 사용합니다.

• 버전 (version): UUID의 ‘time_hi_and_version’ 필드 내에는 버전 번호가 포함되어 있습니다. 이 버전 번호는 UUID가 어떻게 생성되었는지에 대한 정보를 제공합니다 (예: 버전 1은 시간 기반, 버전 4는 무작위)

클록 시퀀스 (clock_seq_hi_and_reserved(16bit, 앞의 2bit는 variant(variant마다 bit 범위는 2~4)))

클록 시퀀스 필드는 UUID 생성 시의 클록 시퀀스 값을 포함합니다. 클록 시퀀스는 동일한 타임스탬프에 여러 UUID가 생성될 때 충돌을 방지하는 데 사용됩니다. 정확한 사용 방법은 구현에 따라 다릅니다. version 3~5에서는 해시값 혹은 난수로 사용됩니다.

• variant: UUID에는 ‘clock_seq_hi_and_reserved’ 필드 내에 variant 정보가 포함되어 있습니다. 이는 UUID의 포맷을 결정하며, 다양한 UUID 스펙이 공존할 수 있도록 합니다.

노드 (Node, 48bit)

이 필드는 보통 MAC 주소를 사용하여 UUID를 생성한 노드(컴퓨터나 서버 등)를 식별합니다. 이는 UUID가 네트워크상에서 고유하도록 보장하는 데 도움을 줍니다.

• MAC 주소: version 1, 2에서 사용되며 실제 MAC 주소나 대체된 유사 MAC 주소를 사용합니다. version 1에서는 나머지 값을 타임스탬프를 사용하기 때문에 고유하게 유지하기 위한 중요한 값입니다. version 3~5에서는 사용되지 않습니다.

UUID Version

앞서 소개한 UUID 버전은 RFC-4122에서 명시한 내용으로 5개의 버전이 존재합니다. 각 버전은 time_hi_and_version 필드에서 앞에 4비트를 이용하여 명시합니다.

The version number is in the most significant 4 bits of the time
stamp (bits 4 through 7 of the time_hi_and_version field).

The following table lists the currently-defined versions for this
UUID variant.

Msb0  Msb1  Msb2  Msb3   Version  Description

0     0     0     1        1     The time-based version
                                 specified in this document.

0     0     1     0        2     DCE Security version, with
                                 embedded POSIX UIDs.

0     0     1     1        3     The name-based version
                                 specified in this document
                                 that uses MD5 hashing.

0     1     0     0        4     The randomly or pseudo-
                                 randomly generated version
                                 specified in this document.

0     1     0     1        5     The name-based version
                                 specified in this document
                                 that uses SHA-1 hashing.

Msb0, Msb1, Msb2, Msb3는 버전으로 명시할 4bit의 값이며 0 혹은 1의 값을 갖습니다.

UUID Version 1

현재 시간과 UUID를 생성하는 컴퓨터 또는 ‘노드’의 MAC 주소 기반

1582년 10월 15일부터 나노초 단위로 표시되는 타임스탬프와 생성하는 컴퓨터의 MAC 주소를 이용해 만듭니다. 하지만 나노초단위로 시간을 측정할 수 없는 컴퓨터가 많기 때문에 일부값을 난수로 사용할 수 있습니다. 타임스탬프로 값을 만들기 때문에 time based로 정렬된 UUID 값을 가질 수 있습니다.

문제점

1. 타임스탬프에 사용되는 100나노초와 그레고리력 시대는 일반적이지 않으며 표준 숫자 형식으로 정확하게 표현하기 어렵다.
2. 시간 순서를 정렬하기 위해서 자체적으로 검사/파싱이 필요하다.
3. MAC 주소를 사용하면 개인 정보 보호 및 네트워크 보안 문제가 발생한다. 시스템을 특정하고 공격 대상으로 삼을 수 있다. 또한 VM 및 컨테이너의 등장으로 MAC 주소의 고유성은 더이상 보장되지 않는다.

UUID Version 2

RFC 4122에서 “DCE 보안” UUID라고 합니다. DCE에서 version 2 명세 게시합니다. 이 UUID는 형식에 몇 가지 문제가 있기 때문에 널리 사용되지는 않습니다.

version 2에서는 생성자의 MAC 주소, 타임스탬프, 로컬 컴퓨터 혹은 그룹의 ID가 포함됩니다. DCE는 POSIX UID/GID의 보안정보를 포함합니다.

문제점

1. 특수한 목적에 맞춰 설계되었기 때문에 일반적인 환경에서는 사용되지 않는다.

UUID Version 3, 5

• version3: 이름과 네임스페이스의 MD5 해시를 기반으로 합니다.
• version5: 이름과 네임스페이스의 SHA-1 해시를 기반으로 합니다. (SHA-1은 해시값이 길기 때문이 잘라서 사용합니다)

네임스페이스와 고유한 이름을 기반으로 생성됩니다. 시간 또는 임의적 요소가 없으므로 동일한 입력으로 매번 똑같은 출력을 만드는 멱등(idempotent)하다는 특징을 갖고 있습니다. 즉, 입력 값을 알면 출력값을 예상할 수 있습니다.

UUID는 4개의 RFC-4122에 사전 정의된 네임스페이스를 사용합니다.

DNS - 6ba7b810-9dad-11d1-80b4-00c04fd430c8
URL - 6ba7b811-9dad-11d1-80b4-00c04fd430c8
OID - 6ba7b812-9dad-11d1-80b4-00c04fd430c8
X.500 DN - 6ba7b814-9dad-11d1-80b4-00c04fd430c8

name은 정의 uuid를 만들 때 사용자가 직접 입력해야 합니다.

문제점

1. version 3에서 사용되는 MD5의 해시 알고리점은 충돌 공격(collision attacks)에 취약합니다. 두 개의 서로 다른 입력이 MD5 해시 값을 생성할 수 있다. version5의 SHA-1 알고리즘은 MD5보다 안전하지만 이론적으로 충돌 공격에 취약하다.
2. version 3,5 모두 멱등한 특성이 있기 때문에 입력 값을 알게 되면 UUID를 예측할 수 있다. 즉 결정적 방식(deterministic)을 사용하고 있다.
3. 해싱 알고리즘을 사용하므로 계산 비용이 발생한다.
4. 시간 순서가 지정되지 않는다.

UUID Version 4

UUID는 모든 필드가 무작위로 생성됩니다. 2^122개가 넘는 고유한 v4 UUID가 있습니다. 이것이 가장 일반적인 UUID 버전입니다.

단순하게 랜덤 값을 사용하기 때문에 고유성을 가질 수 있고 이론상으로는 충돌 가능성이 있지만 확률이 극단적으로 많기 때문에 일반적으로 사용합니다. 또한 version 3,5 와 다르게 해싱하는 과정이 없어 성능상 우수합니다.

문제점

1. 시간 순서가 지정되지 않는다.

UUID Version 4 구현과 문제점

java.util.UUID 클래스의 메소드를 통해 UUID를 다시 확인하겠습니다. 자바 1.5 버전 이후부터 제공하는 UUID는 RFC-4122 표준을 준수하며 version 1,2,3,4의 uuid을 제공합니다.

UUID를 생성하기 가장 쉬운 방법은 randomUUID() 메서드를 사용하면 됩니다. 이 메서드는 version4를 기반으로 생성됩니다.

import java.util.UUID;

UUID uuidVersion4 = UUID.randomUUID();

이 코드를 분석하면 다음과 같습니다.

SecureRandom ng = Holder.numberGenerator;

• SecureRandom 는 암호학적으로 강력한 난수 생성기(cryptographically strong random number generator, FIPS 140–2, RFC-408 요구사항 적용)입니다.

byte[] randomBytes = new byte[16];

• RFC-4122 UUID의 요구사항인 128 비트(16 byte)를 충족합니다.

ng.nextBytes(randomBytes);

• 이 바이트 배열을 SecureRandom 를 통해 난수로 채웁니다.

randomBytes[6]  &= 0x0f;  /* clear version        */
randomBytes[6]  |= 0x40;  /* set to version 4     */

• UUID 버전을 4로 설정합니다. 0x40은 이진수로 변환했을 때, ‘0100 0000’ 이므로 6비트입니다.

randomBytes[8]  &= 0x3f;  /* clear variant        */
randomBytes[8]  |= 0x80;  /* set to IETF variant  */

• UUID의 variant 를 IETF 표준에 맞게 설정합니다. 이 중 앞의 2비트 ‘10’만이 variant를 사용하는데 설정이 되기 때문에(버전마다 상이) 2비트를 사용합니다.

코드를 보면 전체 version(6비트)과 variant(2비트)를 명시한 8비트를 제외한 122비트가 UUID는 암호학적으로 안전한 난수를 사용하게 됩니다. 따라서 UUID Version4는 2^122의 조합을 가집니다. 이로써 충돌 가능성이 무척이나 낮기 때문에 안전하게 값을 생성할 수 있음을 확인할 수 있습니다.

이 함수를 통해 UUID를 12,800,000개를 만드는데 걸리는 시간을 측정하면 다음과 같습니다. 생성하는 예제 코드는 Baeldung 블로그 링크를 통해 확인할 수 있습니다.

12800000 UUIDs generated, 0 collisions in 4622ms

추가적으로 UUID에서 확인할 수 있는 timestamp 및 node 등의 정보는 version 1에서만 제공하는 것을 확인할 수 있습니다.

UUID Version 4의 문제점

UUID Version 4는 앞서 봤듯이 모든 문자가 랜덤으로 생성되기 때문에 정렬에 취약합니다. 데이터베이스 측면에서 봤을 때, UUID를 고유한 key 값으로 설정했을 때 여러 문제가 발생합니다.

첫 번째로 128 비트라는 공간적인 문제입니다. RDB에서 사용하는 auto increment PK의 경우 주로 64비트의 bigint로 사용하곤 하는데, UUID는 이의 2배인 128비트를 사용하게 됩니다. 두번째로는 이러한 무작위성의 이유로 인덱스 추가 연산을 할 때 인덱스가 중간에 삽입되기 때문에 재조정이 필요합니다. 가령 auto increment는 이미 정렬된 인덱스에 마지막 값을 추가하기 때문에 append의 개념과 유사하게 마지막 노드에 추가됩니다. 하지만 UUID는 그 때 그때 적절한 위치를 중간에 삽입해야 하기 때문에 RDB 인덱스 b+트리 구조상 균형을 맞추기 위한 트리연산 유발이 잦게 됩니다. 또한 논리적인 정렬(생성시간에 따른 정렬 등)의 사용도 불가능합니다.

아래 그림은 MySQL에서 100,000개의 insert 쿼리를 통해 UUID version4과 sequential UUID version4의 성능을 비교한 결과입니다. 성능의 현저한 차이를 확인할 수 있습니다.

https://blog.programster.org/mysql-performance-when-using-uuid-for-primary-key

이러한 이유로 우리는 UUID Version 4를 식별키로 사용하기에 망설여집니다. 이 문제를 해결하기 위해 토스는 타임스탬프 기반의 tuid를 오픈소스로 공개하기도 하였고 segmentio 라는 기업에서 sortable UUID인 ksuid를 출시하기도 했습니다. 이외에도 time-sequential한 UUID에 대한 고안은 다양하게 있습니다.

그리고 2022년 12월 IETF는 draft 형식으로 UUID version 6,7,8을 제안했습니다.

Time Based New UUID Format Version 6,7,8

이 제안은 IETF draft 형식으로 작성되었습니다. 2022년 12월에 작성된 문서로 2005년에 제정된 RFC-4122에 문제점을 개선하기 위해 등장한 양식입니다.

해당 표준은 최신 애플리케이션 및 데이터베이스에 친화적인 UUID의 다양한 용례를 기반으로 만들어졌습니다. 이 문서에서는 기존 UUID 1~5 버전의 문제점을 다음과 같이 명시했습니다.

1. UUIDv4와 같이 시간 순서가 지정되지 않은 UUID 버전은 데이터베이스 인덱스 위치가 좋지 않습니다. 연속해서 생성된 새 값은 인덱스에서 서로 가깝지 않으므로 임의의 위치에서 삽입을 수행해야 함을 의미합니다. 이에 사용되는 일반 구조(B-트리 및 변형)에 대한 부정적인 성능 효과는 극적일 수 있습니다.
2. UUIDv1 타임스탬프에 사용되는 100나노초, 그레고리력 시대는 일반적이지 않으며 [ IEEE754 ] 와 같은 표준 숫자 형식을 사용하여 정확하게 표현하기 어렵습니다.
3. 시간 순서에 따라 정렬하려면 자체 검사/파싱이 필요합니다. 간단한 바이트별 비교를 수행할 수 있는 것과는 대조적입니다.
4. 버전 1 UUID의 노드 필드에 MAC 주소를 사용하면 개인 정보 보호 및 네트워크 보안 문제가 발생합니다. 노출된 MAC 주소는 시스템을 찾고 해당 시스템에 대한 다양한 기타 정보(최소 제조업체, 잠재적으로 기타 세부 정보)를 공개하는 공격 표면으로 사용될 수 있습니다. 또한 가상 머신 및 컨테이너의 출현으로 MAC 주소 고유성은 더 이상 보장되지 않습니다.
5. [ RFC4122 ] 에 지정된 구현 세부 사항 중 상당수는 모든 애플리케이션에 대해 지정할 수 없거나 상호 운용 가능한 구현을 생성하는 데 필요하지 않은 절충안을 포함합니다.
6. [ RFC4122 ]는 UUID 생성 요구사항과 단순히 UUID를 저장하는 애플리케이션을 구분하지 않으며 이는 종종 다릅니다.

이를 해결하기 위해 앞서 말한 다양한 방식의 UUID 사례를 명시하였고 이에 표준을 제정하기 위해 문서가 작성되었습니다.

분석된 UUID 구현 사례

이 문서는 총 ID 길이, 비트 레이아웃, 어휘 형식/인코딩, 타임스탬프 유형, 타임스탬프 형식, 타임스탬프 정확도, 노드 형식/구성 요소, 충돌 처리 및 다중 타임스탬프 틱 생성 순서의 추세에 대해 다음 16가지 서로 다른 구현을 분석을 기반으로 합니다.

1. [ULID] by A. Feerasta
2. [LexicalUUID] by Twitter
3. [Snowflake] by Twitter
4. [Flake] by Boundary
5. [ShardingID] by Instagram
6. [KSUID] by Segment
7. [Elasticflake] by P. Pearcy
8. [FlakeID] by T. Pawlak
9. [Sonyflake] by Sony
10. [orderedUuid] by IT. Cabrera
11. [COMBGUID] by R. Tallent
12. [SID] by A. Chilton
13. [pushID] by Google
14. [XID] by O. Poitrey
15. [ObjectID] by MongoDB
16. [CUID] by E. Elliott

New UUID Version

이를 통해 제시한 새로운 버전의 UUID 형식은 다음과 같습니다.

Msb0 Msb1 Msb2 Msb3 Version Description
 0    1    1    0     6     Reordered Gregorian time-based UUID specified in this document.
 0    1    1    1     7     Unix Epoch time-based UUID specified in this document.
 1    0    0    0     8     Reserved for custom UUID formats specified in this document

UUID 버전 6(UUIDv6)

• 불투명한 바이트 시퀀스로 정렬할 수 있도록 UUID 버전 1을 재정렬 기존 UUIDv1 구현을 고려하면 구현이 쉬움

UUID 버전 7(UUIDv7)

• 널리 구현되고 잘 알려진 Unix Epoch 타임스탬프 소스에서 가져온 완전히 새로운 시간 기반 UUID 비트 레이아웃

UUID 버전 8(UUIDv8)

• 이전 버전과의 호환성을 유지하는 것 외에 명시적인 요구 사항이 없는 자유 형식 UUID 형식

최대 UUID

• [ RFC4122 ] 섹션 4.1.7 의 반대인 특수 UUID

IETF는 version 1에 호환되는 버전으로 version 6을 제시하였고 가능한 version 7를 사용하도록 권장하고 있습니다. version 7은 version 1 또는 6에 비해 엔트로피 특성이 향상되었습니다. 엔트로피(entropy)는 동일한 시간에 요청된 UUID를 서로 다른 값으로 만들어 고유성을 보장하기 위한 기능입니다.

IETF UUID Version 7

new format의 UUID version은 다음과 같은 특성을 가지고 있습니다. 아직 용례가 부족하므로 자세한 내용은 문서에서 직접 확인하기를 권장드립니다.

• 타임스탬프의 세분성
• 단조성과 카운터
• 분산 UUID 생성
• 충돌 저항
• 글로벌 및 지역적 고유성
• 추측 불가능성
• 정렬
• 불투명
• DBMS 고려사항
• IANA 고려사항
• 보안 고려사항

위의 특성을 고려하여 만들어진 UUID Version 7의 구조는 아래와 같습니다.

https://datatracker.ietf.org/doc/html/draft-peabody-dispatch-new-uuid-format#timestamp_granularity

unix_ts_ms(48bit)

• Unix epoch 타임스탬프의 48비트 빅엔디안(big-endian)의 양의 정수값입니다.
• 빅엔디안 포맷은 가장 중요한 바이트(Most Significant Byte, MSB)가 메모리의 낮은 주소에 위치합니다. 따라서 더 낮은 주소에 있는 바이트부터 비교하기만 해도 자연스럽게 순서대로 정렬할 수 있습니다. 바이트를 순선대로 비교함으로서 더 작은 타임스탬프를 식별할 수 있습니다.

version(4bit)

• UUID Version 7은 0111 로 표현됩니다.

rand_a(12bit)

• 고유성을 위한 난수 데이터입니다.

variant(2bit)

• 기존 RFC-4122 variant 와 동일합니다.

rand_b(62bit)

• 고유성을 위한 난수 데이터입니다.

즉, 48bit로 timestamp를 표현하고 4bit version, 2bit variant, 74bit rand_a, rand_b 난수를 표현한 구조입니다.

UUID Version 7 구현 라이브러리와 성능

IETF가 제정한 New UUID Format을 구현한 java의라이브러리도 등장했습니다. Baeldung에서 이를 소개하는 글은 time-based UUID인 UUID version 1, 6, 7를 라이브러리를 통해 UUID 생성 방법과 성능을 비교하였습니다.

UUID를 48bit의 timestamp와 74bit의 난수를 결합해서 생성함과 동시에 같은 timestamp의 경우 고유성을 획득하기 위한 로직을 구현하기 위해 thread-safe하게 UUID를 생성하는 방법을 사용해야 합니다.

uuid-creator

implementation 'com.github.f4b6a3:uuid-creator:5.3.5'

UUID uuidVersion1 = UuidCreator.getTimeBased();
UUID uuidVersion6 = UuidCreator.getTimeOrdered();
UUID uuidVersion7 = UuidCreator.getTimeOrderedEpoch();

구현로직은 아래와 같습니다.

@Override
public synchronized UUID create() {

• synchronized 키워드를 사용해서 thread-safe하게 구현했습니다.

if ((time > lastTime - CLOCK_DRIFT_TOLERANCE) && (time <= lastTime)) {
   this.lastUuid = increment(this.lastUuid);
} else {
...

• 현재 시간이 마지막 시간과 동일하거나, 시스템 시계의 작은 조정이나 윤초 후에 이전 시간보다 약간 뒤로 이동한 경우를 확인합니다. 이 경우, 마지막 UUID를 증가시킵니다.

...
else {
 if (this.random instanceof ByteRandom) {
  final byte[] bytes = this.random.nextBytes(10);
  final long long1 = ByteUtil.toNumber(bytes, 0, 2);
  final long long2 = ByteUtil.toNumber(bytes, 2, 10);
  this.lastUuid = make(time, long1, long2);
 } else {
  final long long1 = this.random.nextLong();
  final long long2 = this.random.nextLong();
  this.lastUuid = make(time, long1, long2);
 }
}

• 새로운 UUID를 생성하고 lastUuid에 값을 저장합니다.

이 메서드의 성능을 계산하면 아래와 같이 나옵니다.

12800000 UUIDs generated, 0 collisions in 2595ms

java-uuid-generator(JUG)

implementation 'com.fasterxml.uuid:java-uuid-generator:4.3.0'

UUID uuidVersion1 = Generators.defaultTimeBasedGenerator().generate();
UUID uuidVersion6 = Generators.timeBasedReorderedGenerator().generate();
UUID uuidVersion7 = Generators.timeBasedEpochGenerator().generate();

구현로직은 아래와 같습니다.

private final Lock lock = new ReentrantLock();
...
public UUID construct(long rawTimestamp) {
   lock.lock();
...

• ReentrantLock를 사용해서 thread-safe하게 구현합니다.

if (rawTimestamp == _lastTimestamp) {
    boolean c = true;
    for (int i = ENTROPY_BYTE_LENGTH - 1; i >= 0; i--) {
        if (c) {
            byte temp = _lastEntropy[i];
            temp = (byte) (temp + 0x01);
            c = _lastEntropy[i] == (byte) 0xff && c;
            _lastEntropy[i] = temp;
        }
    }
    if (c) {
        throw new IllegalStateException("overflow on same millisecond");
    }
} else {
 ...

• 타임스탬프가 마지막으로 사용된 타임스탬프와 동일한지 검사합니다. 만약 동일하다면, 동일한 타임스탬프에 대해 다른 UUID를 생성하기 위한 추가 로직을 실행합니다.

else {
    _lastTimestamp = rawTimestamp;
    _random.nextBytes(_lastEntropy);
}
return UUIDUtil.constructUUID(UUIDType.TIME_BASED_EPOCH, (rawTimestamp << 16) | _toShort(_lastEntropy, 0), _toLong(_lastEntropy, 2));ㅓㅁ

• 현재 시간이 마지막으로 생성된 UUID의 시간과 다를 경우, 새로운 타임스탬프를 설정하고 엔트로피 배열에 새로운 난수 값을 채워 넣어 새로운 UUID를 생성할 준비를 합니다. 이 방식은 각 UUID가 시간에 따라 고유하게 생성될 수 있도록 보장합니다.

이 메서드의 성능을 계산하면 아래와 같이 나옵니다. 다른 UUID 생성 로직보다는 성능이 좋지 않지만 큰 차이가 발생하지는 않습니다.

12800000 UUIDs generated, 0 collisions in 15795ms

UUID version 7의 충돌 가능성

UUID version 7의 충돌 가능성은 version 4와 다르게 계산하기가 복잡합니다. version 4는 난수 122비트를 사용하므로 단순 계산으로 2^122의 가능성을 유추할 수 있습니다. UUID version 7은 난수 74비트를 사용하지만 2^74의 가능성으로 밀리초마다 독립적이라는 특성이 있습니다.

이 둘의 충돌 가능성을 비교한 글의 내용을 요약하면 다음과 같습니다.

분석의 가정

• UUID 버전 4는 122비트를 무작위로 사용하며, 버전 7은 74비트를 무작위로 사용한다고 가정합니다.
• 특정 시간(𝑇 밀리초) 동안 𝑔개의 UUID를 생성한다고 할 때, 버전 4와 버전 7의 충돌 확률을 계산합니다.

주요 결과

• 주어진 𝑔 값에 대해, 𝑇가 어느 정도 커지면 버전 7이 버전 4보다 충돌 가능성이 낮아지는 “컷오프 포인트”를 찾습니다.
• 작은 𝑡 값에 대해서는 버전 4가 유리하며, 큰 𝑡 값에 대해서는 버전 7이 유리합니다. 이는 버전 7의 각 밀리초 독립성이 큰 역할을 합니다.

구체적인 수치

• 예를 들어, 밀리초당 최소 2개의 UUID를 생성한다면, 버전 7이 버전 4보다 낫다는 결론에 도달하는 데 약 4,459.7년(140737488355329ms)이 걸립니다. 밀리초당 천 개를 이상으로 생성할 경우, 이 컷오프 포인트는 약 8,916.59년(281193501733946ms)으로 증가합니다. 이후 g의 개수가 늘어나도 큰 차이가 없습니다.

결론

• 해시 충돌을 피하는 것이 주요 목표라면 대부분의 경우 버전 4를 선택하는 것이 좋습니다. 그러나 버전 7은 데이터베이스 인덱스의 지역성을 개선하는 등 다른 이점을 제공할 수 있습니다.
• 버전 4와 버전 7 간에는 각각의 장단점이 있으며, 특정 애플리케이션에 적합한 UUID 알고리즘을 선택할 때 이러한 요소들을 고려해야 합니다.

Conclusion

UUID의 표준인 RFC-4122는 2005년에 발행된 꽤나 오래된 표준이었습니다. 최신 애플리케이션과 데이터베이스 활용을 위해 여러 기업에서 Sortable UUID를 고안하였고 IETF는 RFC-4122에 기반한 2022년 12월 새로운 형식의 UUID 초안을 게재했습니다.

IETF는 16개의 기업의(혹은 그 이상)UUID 기술을 분석하여 표준을 제시하였고 정렬 성능이 우수한 Time Based UUID(대표적으로 version 7)을 만들었습니다. IETF의 초안은 통상 몇개월에서 몇년까지 커뮤니티 간의 합의를 통해 RFC에 발행됩니다. 하지만 IETF 초안만으로도 업계에서는 사실상 표준으로 사용하는 경우가 많습니다.

물론 새로운 UUID가 은탄환이 되지는 않습니다. 상황에 따라 기존에 사용하던 UUID version 4가 필요할 수 있습니다. UUID의 본질적 특성을 이해하고 이를 구현한 라이브러리의 원리를 이해하여 상황에 따라 적절한 선택을 해야합니다.

Reference

Twilio Segment Blog

UUID Versions Explained | UUIDTools.com

https://www.baeldung.com/java-generating-time-based-uuids

New UUID Formats

https://datatracker.ietf.org/doc/html/draft-peabody-dispatch-new-uuid-format

RFC 4122: A Universally Unique IDentifier (UUID) URN Namespace

UUID Version 7 Implementation and Conundrums