UUID 충돌 발생이 예상된다면 어떻게 대처를 해야 할까?

프로젝트를 진행하면서 UUID로 임의의 문자열을 생성하는 로직이 있었습니다.

128비트의 32글자 UUID 버전 4를 사용했습니다.

매초 10억개를 100년동안 만들더라도 단 하나의 중복이 발생할 확률이 약 50% 정도라고 알려져 있습니다.

 

따라서 따로 고려를 해본적은 없었지만 서비스가 정말 어마어마하게 커져 충돌 발생 가능성을 고려해야 한다면

어떠한 식으로 대처를 해야할 지에 대해 작성해보겠습니다.

📘 대략적인 규모 추정하기

16바이트의 UUID를 매초 10억개씩 100년동안 만들었다고 가정해본다면 기가, 테라, 페타를 넘어

약 50 엑사바이트 정도의 데이터입니다. 이는 하나의 데이터베이스에서 저장하기에는 너무나도 큰 수치입니다.

우선은 하나의 데이터베이스에 저장하는 경우를 생각해보고 추가적으로 스케일 아웃했을 경우를 고려해보겠습니다.

📕 충돌 감지하기

우선 UUID를 데이터베이스에 insert 하기 전에 이미 해당 문자열이 있는지 확인을 해야 합니다.

이를 확인하기 위해서 전체 테이블 풀스캔을 하는 것은 너무나도 큰 성능 저하가 예상됩니다.

 

따라서 우선은 인덱스를 활용해야겠다는 생각이 듭니다.

일반적인 B+Tree를 사용한다면 조회 성능이 O(logn) 정도 나오는 것을 보장할 수 있습니다.

하지만 일반적으로 인덱스는 조회 성능을 높이며 삽입/수정/삭제의 성능은 조금 포기해야 합니다.

매초 10억건은 매우 많은 insert 작업입니다. 

일반적인 B+Tree 인덱스를 이용하여 해당 문자열이 있는지 확인을 하더라도 대량의 insert 작업으로 인해서

인덱스 자료구조를 관리하는 비용이 커질 것으로 예상됩니다.

 

물론 생성하는 임의의 문자열을 UUID 버전 7과 같이 항상 정렬된 순서를 보장할 수 있다면 이에 대한 비용은 

줄어들게 할 수도 있습니다. 하지만 더 나은 대안을 생각해보겠습니다.

 

B+Tree가 아닌 해시 인덱스를 생각해보겠습니다.

B+Tree가 효과적인 인덱스 자료구조였던 이유중 하나가 범위 검색에 특화되어 있다는 점이 컸었는데

특정 임의의 문자열의 존재 여부를 판단하기에는 해시 자료구조가 조금 더 적합해 보입니다.

📗 예상되는 구조 설계

UUIDCreator 클래스를 생성하고 uuids를 해시를 이용한 Set 자료구조로 관리하도록 하겠습니다.

public class UUIDCreator {

    static Set<UUID> uuids = ConcurrentHashMap.newKeySet();

    public UUID create() {
        UUID uuid;

        do {
            uuid = UUID.randomUUID();
        } while (!uuids.add(uuid));

        return uuid;
    }
}

 

uuids에 새로 생성한 문자열이 포함되어 있다면 새롭게 생성하여 재시도하고 없다면 uuids에 추가한 후 리턴하도록 하였습니다.

이러한 방식으로 새롭게 생성한 문자열의 충돌 여부 확인을 O(1)의 시간만에 할 수 있습니다.

또한 insert 할 때도 O(1)의 성능을 보장할 수 있습니다. 

 

이제 충돌 여부 확인, 문자열 insert 모두 O(1)로 빠른 성능을 보장했지만 하나의 데이터베이스를 기준으로 하였습니다.

여러 데이터베이스에 분산되어 저장되어 있는 경우를 생각해보겠습니다.

 

이 경우에는 UUID 버전 7과 같이 시간을 기준으로 정렬을 보장할 수 있다면 그 정보를 기반으로 어떠한 데이터베이스에

저장되어 있는지를 판단하기 때문에 분산 시스템에서 적합할 수 있습니다.

하지만 완전히 충돌 발생 가능성이 0인 것은 아닌 이유는 동일 밀리초 내에서 생성된 경우는 아주 낮은 확률로

충돌이 발생할 수도 있습니다.

 

다만 이 경우에는 굳이 정렬이 아니더라도 db1-{UUID 문자열}, db2-{UUID 문자열}, db3-{UUID 문자열} 와 같은 방식으로

앞에 db에 대한 정보를 적어놓고 같은 서버 안에서만 충돌 여부를 확인한 후 앞에 db 정보를 붙인 UUID 문자열을

사용한다면 전체 서비스 내에서 충돌 없이 사용해볼 수 있을 것 같습니다.

📚 정리

1. 매초 10억건의 insert의 UUID를 생성한다면 인덱스는 B+Tree 보다는 해시가 적합할 수도 있다.

2. 해시 방식으로 인덱스를 관리하여 충돌 여부 확인, 문자열 insert를 O(1) 성능 보장

3. 스케일 아웃을 한 경우에는 UUID 버전 7이나 각 DB 마다 DB 정보를 붙여 전체 서비스에서는 충돌 방지

4. 한 번에 insert를 할 때 batch 처리를 고려