UUID가 겹치면 어떻게 하지? (중복을 최소화 해보자!)

이번 토이 프로젝트를 진행하며 세션 키를 직접 생성하게 되었다!!

그런데 문득 이런 생각이 들었다.🤔

우선은 유니크 하면 떠오르는 UUID로 생성하면 될 것 같긴한데..

왜 이렇게 'UUID도 중복으로 생성될 수도 있다는 확률이 존재한다는 것' 자체가 마음에 들지않지?? 😠

물론.

마음의 위안을 얻기위해 이곳저곳 자료를 찾아보고 계산한 결과,

UUID는 1초에 100만 건씩 100년동안 생성을 해야 0.00009% 확률로 중복이 될 수 있다고는 한다.

만약 1초에 1건씩이면 10억년을 생성해야 1번이 중복이 될 수 있다고 한다. (~~그 전에 외계인이 침략을 하..~~)

"그런데 벼락을 2번을 맞고, 복권에도 당첨된 사람도 있다고 하지 않나??"

https://www.joongang.co.kr/article/18302627#home

그럼 만약 내가 저런 확률로 중복이 된다면??🥺

내 서버에선 어떠 유저는 다른 유저의 정보를 가지게 되는건가..? (물론 세션스토리지에 넣을 때 중복인지 검증하면 되긴하겠지만,,)

그래서 나는 UUID만 사용하는 것보다 최대한 더 중복 확률을 더 줄여 보고 싶은 마음에 다른 삽질(방법)을 생각해보았다.

💭 내가 생각하는 세션 키 생성 조건

세션은 최대 24시간까지 유지가 된다고 가정. (기본 시간은 훨씬 더 짧게 설정 하겠지만)
초당 10,000회의 세션 키가 생성된다고 가정.
세션 키 길이는 32 Byte. (UUID의 경우 하이픈 제외할 시 32Byte.)

🛫 자! 이제 어떻게 더 중복을 줄일 수 있을까?

여기선 비교를 위해 우선은 똑같이 UUID의 16진수를 사용하여 비교해 보려고 한다.

🧮 먼저 UUID만 사용했을 경우 하루에 중복될 수 있는 확률을 구한다.

import java.util.UUID;

public String createSessionId() {
    return UUID.randomUUID().toString();
}

우선 모든 경우의 수이다.

16^32 = 340,282,366,920,938,463,463,374,607,431,768,211,456 경우의 수

하루동안 생성 될 수 있는 세션의 수이다.

10,000(초당 생성 수) * 60(초) * 60(분) * 24(시간) = 864,000,000 건

아래는 UUID가 중복되지 않을 확률을 구하는 공식이다. 왼쪽은 실제 공식이며 이렇게나 큰 숫자를 계산하는것은 불가능하기 때문에,

스털링의 공식으로 근사화 한 오른쪽 공식으로 확률을 구해보도록 하였다.

혹여나 직접 계산을 해보고 싶으신 분들을 위해 알려드리자면,

n은 모든 경우의 수이며,
r은 생성한 갯수이다.

(다만, 복잡하고 값이 너무 크기 때문에 직접 계산은 안하시는것을 추천드린다.. 꽤나 힘들다..🥹)

이를 공식에 의해 직접 계산을 해본다면...

일반 계산기로는 안돼서 엄청 큰 숫자도 계산이 되는 계산기를 찾아봤습니다.

📈 초당 1만건 생성 시 UUID가 하루동안 중복될 수 있는 확률이다.

0.0000000000000000000011% (소수점 23자리에서 반올림)

⌚ 이번에는 위와같이 밀리세컨드를 세션키에 포함하였을 때 하루에 중복이 발생할 확률을 구한다.

본인이 중복을 덜 발생시키기 위해 구현해 본 것이다. 👀

현재 밀리세컨드 시간을 세션키에 포함시키는 방법

8byte (하루 밀리세컨드 초 8자리 숫자) + 24byte (나머지 UUID로 랜덤 생성하기)
하루는 밀리세컨드 초로 86,400,000 이므로 8자리로 표현할 수 있다.
- 00시가 지나 초가 적을 경우 0으로 대체하여 8자리를 유지한다.
- System.currentTimeMillis() 는 표준 UTC 시간을 사용하므로 한국은 +09:00을 해주어야 하지만,
- 순차 생성을 위한 값으로 꼭 한국 시간과 일치해야 할 필요는 없기에 그대로 사용했다.

import java.util.UUID;

private static final long MILLISECOND_BY_DAY = 86_400_000L;

public String createSessionId() {
    // UTC 표준 현재 시간을 하루로 나눈 나머지를 구한다.
    long todayMillisecond = System.currentTimeMillis() % MILLISECOND_BY_DAY;
    
    // 밀리세컨드 초가 8자리보다 적을 경우 0으로 대체하여 8자리를 유지한다.
    String millisecond = String.format("%08d", todayMillisecond);
    
    UUID uuid = UUID.randomUUID();
    String substring = uuid.toString().substring(8);
    
    return millisecond + substring;
}

위 createSessionId()를 여러번 실행한 결과 값이다.

42120209-cdb2-4e75-bcdb-3ea7b6fb0673
42139071-6d91-45c4-98bd-6c5029cb9556
42144408-ee75-40d9-843f-da93492daa58

이제 해당 방법의 모든 경우의 수이다.

16^24 = 79,228,162,514,264,337,593,543,950,336 경우의 수

(하루동안) 동일한 밀리세컨드에 생성 될 수 있는 세션의 수이다.

10,000(초당 생성 수) / 1,000(밀리세컨드) = 약 10 건

📉 밀리세컨드 + UUID가 하루동안 중복될 수 있는 확률이다.

0.00000000000000000000000000057% (소수점 30자리에서 반올림)
다른 밀리세컨드는 무조건 세션 키 값이 다르기 때문에 같은 밀리세컨드에서만 비교하면 된다.
세션키는 최대 24시간이 지나면 폐기 되기 때문에 하루가 지나도 중복 생성 되지 않는다.

🥁 비교 결과

하루동안 발생할 수 있는 중복확률은

UUID만 사용하였을 경우

0.0000000000000000000011 %

밀리세컨드를 UUID의 앞 8자리를 대체하였을 경우

0.00000000000000000000000000057 %

한눈에 봐도 확실히 중복 될 확률이 훨씬 줄어든 것을 확인할 수 있으며

밀리세컨드를 포함 시키는 것이 약 200만 배의 중복확률 발생 차이를 줄일 수 있었다.

이는 정확히 동일한 밀리세컨드의 요청이 아닌이상 애초에 중복이 발생 할 수 가 없는 구조이고,

같은 밀리세컨드에 생성이 되었더라도 이미 앞서서 비교한 것도 이미 상당히 큰 규모인 1초당 10,000명의 사용자가 로그인 한 기준임에도

중복이 발생했는지 비교 대상이 겨우 10건 남 짓이다. (실제로는 편차가 많겠지만)

그럼 또 여기서 궁금한 것이 생긴다. 🤔

그렇다면 과연 이 방법은 얼마나 정말 엄청나게 많은 사용자가 동시에 로그인을 해야 중복이 발생할 확률이 기하 급수적으로 늘어날까?

이를 알아보기위해 또 한번 삽질을 해보았다.

1초당 세션 키 생성

5,000 명일 경우
- UUID : 0.00000000000000000000027% (소수점 24자리에서 반올림)
- 밀리세컨드 : 0.00000000000000000000000000013% (소수점 30자리에서 반올림)
10,000 명일 경우
- UUID : 0.0000000000000000000011% (소수점 23자리에서 반올림)
- 밀리세컨드 : 0.00000000000000000000000000057% (소수점 30자리에서 반올림)
100,000 명 일 경우
- UUID : 0.00000000000000000011% ( 소수점 21자리에서 반올림)
- 밀리세컨드 : 0.000000000000000000000000062% (소수점 28자리에서 반올림)
...
100,000,000 명 일 경우
- UUID : 0.00000000000011% (소수점 15자리에서 반올림)
- 밀리세컨드 : 0.000000000000000000063% (소수점 22자리에서 반올림)

계산해본 결과 나의 생각과는 다르게 상당히 예상 밖이였다.

1초당 생성되는 세션 키가 더더욱 많이 늘어나더라도 초당 10만명 이상부터는 실제 중복 확률이 늘어나는 비율이 일정하게 증가하였다.

나는 아무래도 UUID로 랜덤 생성하는 공간 범위 차이가 24제곱과 32제곱은 꽤나 큰 차이가 나므로,

동일 밀리세컨드 시간에 전달되는 사용자 요청이 늘어남에 따라 후자의 방법에선 중복 확률이 현저히 올라 갈 것이라고 생각을 하였었는데.

실제로는 UUID만 사용하는것과 동일하게 약 10만명 이후부터는 균일하게 증가하는 것으로 계산이 되었다.

따라서,

현재 시간을 포함시켜 순서대로 생성하는 것이 더 중복확률을 줄일 수 있다고 판단을 하게 되었다.

그렇다면 UUID 대신 만들꺼라면 꼭 16진수이어야 할까? 🤔

자, 그렇다면 이번에는!

어차피 중복을 최소화 하기 위한 것이라면 굳이 16진수를 사용하지 않아도 되지 않을까?

라는 생각을 하게 되었는데, 그이유는 UUID는 기본적으로 16진수(0-9, a-f)를 통해 고유 ID를 생성해 내고 있다.

이는 4bit로 나타낼 수도 있고,
이미 프로그래밍 언어나 라이브러리를 사용할 때도 더 널리 사용되고 있어 보편적이므로 사용한다고 한다.

하지만 1btye는 8bit 이니까 4bit가 더 남는거잖아??

단순히 생각만 해보아도 알 수 있듯 단순히 더 높은 진수를 사용할 경우 무지막지하게 중복될 확률을 더 줄일 수 있다.

따라서 UUID 대신 직접 랜덤 문자열을 생성하는 로직도 구현을 해보았다.

여기에선 0-9, a-z, A-Z 까지 총 62개의 문자를 사용하려던 중 개발의 용이성을 위해

023456789abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNOPQRSTUVWXYZ

위와 같이 헷갈릴 수 있는 숫자 1과 소문자 l(엘), 대문자 I(아이)는 제외하도록 하여 59개의 문자(진수)를 사용하였다.

다음은 이전의 밀리세컨드 로직을 UUID 대신 59진수로 개선한 코드이다.

import java.util.UUID;
import java.util.Random;
import java.security.SecureRandom;

private final ThreadLocalRandom random = ThreadLocalRandom.current();
private static final long MILLISECOND_BY_DAY = 86_400_000L;
private static final String SESSION_RANDOM_STRING = 
	"023456789abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNOPQRSTUVWXYZ";

public String createSessionId() {
    SecureRandom random = new SecureRandom();
    StringBuffer buffer = new StringBuffer();
    buffer.append(String.format("%08d", System.currentTimeMillis() % MILLISECOND_BY_DAY));
    for (int i = 0; i < 24; i++) {
        buffer.append(SESSION_RANDOM_STRING.charAt(random.nextInt(SESSION_RANDOM_STRING.length())));
    }
    return buffer.toString();
}

아래는 여러번 createSessionId()를 실행 시키고 반환 받은 결과이다.

40878273FATyjGVzF3oZ0ZtKMoTRfmzq
40881585xbM293qAZtfPGAVRTfKKYTBP
40888916RSbqhqNbLXyuJmMrC28ev4YO
40893415CFwDWRqaAS93vwNgkjHHngfE

정상적으로 랜덤한 값을 잘 생성 하는 것을 확인 할 수 있다.😄

🚀 혹시나 궁금하신 분들이 계실까봐 초당 10,000명이 호출하였을때 중복이 발생할 확률을 비교한 값이다.

UUID v4 :
- 0.0000000000000000000011%
- (소수점 23자리에서 반올림)
밀리세컨드 + UUID v4 :
- 0.00000000000000000000000000057%
- (소수점 30자리에서 반올림)
- (UUID v4 에 비해 약 200만 배 감소)
밀리세컨드 + 59진수 :
- 0.000000000000000000000000000000000016 %
- (소수점 37자리에서 반올림)
- (UUID v4 에 비해 약 68조7500억 배 감소)

❓ 근데 SecureRandom?? 그냥 Random을 사용하면 안될까?

컴퓨터는 기본적으로 난수를 생성할 수 없다고 한다.
그럼에도 난수를 생성하기 위해선 다양한 알고리즘과 Seed가 필요하다.
이는 즉, 동일한 Seed를 입력하게되면 동일한 랜덤값이 생성될 수 있다.
때문에 이를 극복하기 위해선 SecureRandom을 사용하여 동일한 Seed에서도 다른 값을 생성할 수 있어야 한다.

	Random	SecureRandom
크기	48 bits	128 bits
시드 생성	시스템 시계를 시드로 사용하거나 시드를 생성 함.	OS에서 임의의 데이터를 가져 옴.
결과 예측	예측하기 위해선 2^48 번의 시도가 필요 함. 오늘날의 고급 CPU를 사용하면 실제 시간내에 예측 가능.	예측하기 위해선 2^128번의 시도가 필요 함. 오늘날의 고급 CPU로도 수년 정도 소요.
함수 생성	비교적 간단한 알고리즘인 Linear Congruential Generator(LCG) 사용.	비교적 더 강력한 암호학적 해시 함수 SHA1을 사용하여 의사 난수를 생성하는 SHA1PRNG 알고리즘
보안 목적	사용하면 안 됨.	사용하기 위해 설계 됨.

참고자료 : https://www.geeksforgeeks.org/random-vs-secure-random-numbers-java/

🍀 마무리 하며.

이번 실험 자체가 예를 들어 1초에 만 건의 요청을 받는다하여도 정확히 동일한 밀리세컨드에 만 건이 올 수도 있는 등 실제 상황에서는 다른 결과가 발생할 것이라고 생각을 한다.

하지만 그럼에도 결론을 내보자면 UUID만을 사용할때보다 현재 밀리세컨드를 포함하여 생성하는 것이

중복이 발생하지 않을 확률을 약 200만배나 더 낮출 수 있다는 결론을 내릴 수 있게 되었다.🫢

다만 현재 시간의 밀리세컨드를 일부 세션 키에 포함 시키는 것이라,

그냥 UUID만을 사용하여 생성하는 것에 비하면 더 보안적으로는 좋지 않는 방향이라고 볼 수 있다.

하지만 아직 나머지 24byte는 UUID를 사용하여 랜덤으로 생성하기 때문에 이것을 뚫어내는 것도 쉽게는 하지 못할 것이라고 생각이 든다.

또한 보안적으로 더 강화를 시키고 싶다면 16진수가 아닌 위와 같은 상황처럼 59 또는 64진수 내외에서 자유롭게 선택하여 더 높이는 방법도 생각을 해두면 좋을 것 같다.

📭 여담으로..

이러한 현재 시간을 토대로 생성하는 방법은 놀랍게도 이미 UUID v1에 있다고 한다.😲 (개발하며 알았다..)

하지만 UUID v1는 MAC 주소까지 사용해서 생성하기 때문에 MAC 주소를 유추할 수 있어 안전하지 않다고 하여,

지금은 잘 사용하지 않고 대부분 UUID v4을 가장 많이 사용한다고 한다.

그리고 기술을 사용할 때는 현재에만 그치지 않고 그 역사를 들여다 보면 좋다고 예전에 멘토님께서 해주신 말씀이 기억나는데, 이번이 딱 그런 기회였던 것 같았다.

그래도 직접 구현을 해보며 정확하진 않지만 대략적으로 v1과 v4의 중복이 얼마나 차이가 나는지를 몸소 체험할 수 있어 절대 손해를 보았다고 생각을 하진 않아도 될 것 같다.

📚 참고자료

'JAVA' 카테고리의 다른 글

Redisson Lock을 사용해서 동시성 문제를 해결해보자! (1)	2025.01.19
JAVA 람다(Lambda)를 사용할 때 장단점 (0)	2024.08.13
전역 변수, 지역 변수, 클래스 변수 차이를 이해하자! (1)	2024.04.23

beatmejy

UUID가 겹치면 어떻게 하지? (중복을 최소화 해보자!)

이번 토이 프로젝트를 진행하며 세션 키를 직접 생성하게 되었다!!

물론.

"그런데 벼락을 2번을 맞고, 복권에도 당첨된 사람도 있다고 하지 않나??"

💭 내가 생각하는 세션 키 생성 조건

🛫 자! 이제 어떻게 더 중복을 줄일 수 있을까?

🧮 먼저 UUID만 사용했을 경우 하루에 중복될 수 있는 확률을 구한다.

📈 초당 1만건 생성 시 UUID가 하루동안 중복될 수 있는 확률이다.

⌚ 이번에는 위와같이 밀리세컨드를 세션키에 포함하였을 때 하루에 중복이 발생할 확률을 구한다.

본인이 중복을 덜 발생시키기 위해 구현해 본 것이다. 👀

📉 밀리세컨드 + UUID가 하루동안 중복될 수 있는 확률이다.

🥁 비교 결과

하루동안 발생할 수 있는 중복확률은

그럼 또 여기서 궁금한 것이 생긴다. 🤔

1초당 세션 키 생성

따라서,

그렇다면 UUID 대신 만들꺼라면 꼭 16진수이어야 할까? 🤔

아래는 여러번 createSessionId()를 실행 시키고 반환 받은 결과이다.

❓ 근데 SecureRandom?? 그냥 Random을 사용하면 안될까?

🍀 마무리 하며.

📭 여담으로..

📚 참고자료

'JAVA' 카테고리의 다른 글

티스토리툴바

UUID가 겹치면 어떻게 하지? (중복을 최소화 해보자!)

이번 토이 프로젝트를 진행하며 세션 키를 직접 생성하게 되었다!!

물론.

"그런데 벼락을 2번을 맞고, 복권에도 당첨된 사람도 있다고 하지 않나??"

💭 내가 생각하는 세션 키 생성 조건

🛫 자! 이제 어떻게 더 중복을 줄일 수 있을까?

🧮 먼저 UUID만 사용했을 경우 하루에 중복될 수 있는 확률을 구한다.

📈 초당 1만건 생성 시 UUID가 하루동안 중복될 수 있는 확률이다.

⌚ 이번에는 위와같이 밀리세컨드를 세션키에 포함하였을 때 하루에 중복이 발생할 확률을 구한다.

본인이 중복을 덜 발생시키기 위해 구현해 본 것이다. 👀

📉 밀리세컨드 + UUID가 하루동안 중복될 수 있는 확률이다.

🥁 비교 결과

하루동안 발생할 수 있는 중복확률은

그럼 또 여기서 궁금한 것이 생긴다. 🤔

1초당 세션 키 생성

따라서,

그렇다면 UUID 대신 만들꺼라면 꼭 16진수이어야 할까? 🤔

아래는 여러번 createSessionId()를 실행 시키고 반환 받은 결과이다.

❓ 근데 SecureRandom?? 그냥 Random을 사용하면 안될까?

🍀 마무리 하며.

📭 여담으로..

📚 참고자료

'JAVA' 카테고리의 다른 글

'JAVA' Related Articles

티스토리툴바