분산 시스템에서 유일 ID 생성

 

GitHub - LeeJaeYun7/concertTicket

 

 

현재 진행하고 있는 프로젝트인 '콘서트 예약 서비스' 프로젝트에서는 멤버를 생성할 때, UUID를 활용하고 있었습니다.

이 글에서는 '분산 환경'을 고려해 UUID를 트위터 스노우플레이크(snowflake) 접근법으로 개선한 내용에 대해 다루겠습니다

 

 

1) UUID란?

- UUID(Universally Unique Identifier)는 컴퓨터 시스템에서 정보를 유일하게 식별하기 위한

  128비트(16바이트) 길이의 숫자입니다. UUID는 매우 낮은 확률로 충돌이 발생하며,

   중복 UUID가 하나 발생할 확률은 초당 10억 개의 UUID를 100년 동안 생성할 경우에

   비로소 50%에 달할 정도로 극히 낮습니다.

 

-  Java에서는 UUID.randomUUID() 메서드를 통해 쉽게 UUID를 생성할 수 있습니다.

    이를 활용하면 시스템 내에서 유일한 식별자를 손쉽게 생성할 수 있어,

    분산 시스템이나 다중 서버 환경에서 유용하게 사용됩니다.

UUID uuid = UUID.randomUUID()

 

 

2) UUID의 단점

- UUID는 유일성을 보장하고 생성이 간편한 장점이 있지만, 몇 가지 단점도 존재합니다.

 

- 첫 번째 단점은 UUID가 랜덤한 16바이트 문자열로 구성되어 있다는 점입니다.

  이는 인덱스가 적용된 관계형 데이터베이스(RDB)에 저장될 때, 검색 시 O(N)의 시간 복잡도가 발생할 수 있습니다.

  이유는 RDB의 인덱스가 항상 정렬된 상태를 유지해야 하는데, 랜덤한 UUID는 정렬을 방해하기 때문입니다.

  이로 인해 트래픽이 많은 환경에서는 데이터베이스에 부담을 줄 수 있습니다.

 

- 두 번째 단점은 UUID가 상대적으로 큰 크기(16바이트)를 차지한다는 점입니다.

  이는 저장 공간을 더 많이 소모하고, 데이터 처리 성능에 영향을 줄 수 있습니다.

 

3) 트위터 스노우플레이크(Snowflake) 접근법으로 개선

트위터 스노우 플레이크(snowflake) 예시

- 트위터의 스노우플레이크(Snowflake) 방식은 분산 시스템에서 고유한 식별자(ID)를

  효율적으로 생성하기 위한 방법으로, 여러 개의 요소를 결합하여 유일한 값을 생성합니다.

  이 방식은 UUID의 단점을 해결하고 성능을 개선할 수 있는 특징을 가지고 있습니다.

 

- 스노우플레이크 방식에서 생성된 키는 다음과 같은 구성 요소로 이루어집니다:

1. 타임스탬프
   • 키의 가장 중요한 부분은 타임스탬프입니다. 생성 시각을 기준으로 유니크한 값을 생성하므로, 타임스탬프가 키의 접두어(prefix)로 사용됩니다.
   • 이렇게 하면 RDB에 순차적으로 값을 저장할 수 있어, 인덱스 성능이 개선되며, O(1)의 시간복잡도를 유지할 수 있습니다. 이로 인해 데이터베이스 성능에 부하를 주지 않고 효율적인 검색이 가능합니다.
2. 서버 ID
   • 타임스탬프가 1ms 단위로 동일한 값이 생성될 수 있으므로, 구분을 위해 서버 ID가 포함됩니다.
     서버 ID는 각각의 서버를 구별하기 위한 고유한 값입니다.
3. 일련번호 (Sequence Number)
   • 서버 ID와 타임스탬프가 동일한 경우, 중복을 피하기 위해 일련번호가 추가됩니다.
     일련번호는 같은 밀리초 내에서 생성되는 여러 개의 ID를 구분하는 역할을 합니다.
   • 일련번호는 일반적으로 Auto-increment 방식으로 생성되거나,
     UUID와 같은 랜덤값을 활용할 수도 있습니다.

장점

• 순차적 저장: 타임스탬프 기반의 순차적인 생성 방식으로, RDB의 인덱스 성능을 최적화할 수 있습니다.
• 효율적인 성능: O(1)의 시간 복잡도를 보장하며, 대규모 트래픽 환경에서도 데이터베이스에 부담을 줄여줍니다.

- 최종적으로 생성된 key는 다음과 같습니다. 

package com.example.concert.utils;

import com.example.concert.common.CustomException;
import com.example.concert.common.ErrorCode;
import com.example.concert.common.Loggable;

import java.net.InetAddress;
import java.net.UnknownHostException;
import java.util.UUID;

import static java.lang.Math.abs;

public class SnowFlakeGenerator {

    public static String createSnowFlake() {
        try {
            String timestamp = String.valueOf(System.currentTimeMillis()); --- (1) 
            String hostAddress = InetAddress.getLocalHost().getHostAddress(); --- (2) 
            String randomUUID = String.valueOf(abs(UUID.randomUUID().getMostSignificantBits())); --- (3)

            return timestamp + '-' + hostAddress + '-' + randomUUID; --- (4)
        } catch (UnknownHostException e) {
            throw new CustomException(ErrorCode.HOST_NOT_FOUND, Loggable.ALWAYS);
        }
    }
}

 

(1) 타임스탬프 생성
- System.currentTimeMillis()를 사용하여 현재 시간을 밀리초 단위로 타임스탬프를 생성합니다.

(2) 서버 인스턴스 식별자 생성
- InetAddress.getLocalHost().getHostAddress()를 통해 현재 서버의 IP 주소를 얻어 서버 인스턴스를 식별합니다.

(3) 랜덤 UUID 생성
- UUID.randomUUID()를 사용해 랜덤 UUID를 생성하고, 그 중 앞의 8바이트만 추출합니다.

(4) 최종 키 생성
- (1), (2), (3)에서 생성된 값을 결합하여 최종적으로 고유한 키를 생성합니다.

 

 

 

4) Postman 요청 결과

 

 

 

참고

- 가상 면접 사례로 배우는 대규모 시스템 설계 기초, 7장 분산 시스템을 위한 유일 ID 생성기 설계