Design Unique ID Generation For Distributed System

유일 ID를 위해 관계형 데이터베이스의 auto_increment 베이스를 기본 키를 사용하는 방법도 존재한다. 하지만 이 방법은 트래픽이 매우 높으면 값 생성 부하가 생길 수 있고, 분산 시스템 환경에서 사용하기 적절하지 않다.

• 데이터베이스 한 대인 경우: 유일한 데이터베이스 서버에 장애가 발생하면 단일 지점 장애가 발생하여 ID 할당 자체가 중단될 수 있다.

• 데이터베이스 여러 대인 경우: 각 데이터베이스에서 생성된 ID가 겹치지 않도록 보장하기 위해 지연이 발생할 수 있다.

분산 환경에서 유일 ID 생성 시스템을 설계할 때 다음의 요구사항에 맞춰 설계해 볼 수 있다.

• 유일성

• 숫자로만 구성

• 64비트로 표현 가능

• 발급 날짜에 따른 정렬 가능

• 초당 10,000개 발급 가능

유일 ID 생성 방법

유일 ID 생성하는 방법은 여러 가지가 존재한다.

1. 다중 마스터 복제(Multi-Master Replication)

   • 데이터베이스의 auto_increment 기능을 활용하여 1만큼 증가 시키는 것이 아닌, k만큼 증가 시키는 방법(k=데이터 베이스 서버 수)

   • 유일성 보장

   • 시간에 따른 정렬 불가능 / 규모 확장 어려움

2. UUIDv4

   • 서버에서 생성하기 때문에 데이터베이스에 생성 부하가 발생하지 않음

   • 정렬된 값으로 생성되지 않기 때문에 데이터 추가 및 삭제 시 성능 저하(클러스터형 인덱스)

   • 36글자 문자열로 구성되어(바이너리 변환 시 16바이트) 저장 공간이 큼

   • 유일성 보장 / 서버 사이 조율이 필요 없어 동기화 이슈 X / 규모 확장 용이

   • 문자가 포함 됨 / 발급 날짜에 따른 정렬이 불가능

3. UUIDv7

   • 앞자리에 타임스탬프가 들어가 시간 기준 정렬된 순서로 생성 가능

   • 정렬된 값으로 생성되기 때문에 클러스터형 인덱스에 적합

   • 여전히 36글자 문자열로 구성되어 저장 공간이 큼(규모가 작은 곳에선 문제 없으나, 해당 경우엔 자동 증가 값을 사용해도 무방)

4. 티켓 서버

   • auto_increment 기능을 갖춘 데이터베이스 서버를 중앙 집중형으로 별도로 두어 ID를 생성하도록 하는 방법

   • 유일성 보장 / 쉬운 구현

   • SPOF(Single Point of Failure) 문제 발생(여러 티켓 서버 구축 필요 -> 동기화 이슈 발생 가능)

5. 스노우플레이크 접근법

   • 여러 섹션으로 분할 된 64비트 ID를 생성하는 방법

     • 1비트: 사인 비트 / 41비트: 타임스탬프 / 10비트: 장비 고유 번호 / 12비트: 일련번호

   • 유일성 보장 / 발급 날짜에 따른 정렬 가능 / 규모 확장 용이

   • 노드 ID 충돌 문제 발생 가능

상세 설계

여러 방법 중 요구 사항을 만족하는 방법은 스노우플레이크 접근법을 사용할 수 있다. 각 비트 별로 상세 설명은 다음과 같다.

• 타임스탬프: 가장 많은 비트를 차지하며, 시간 기반으로 정렬 가능하도록 하는 역할

  • 41비트의 길이는 밀리초로 환산 했을 때 69년간 사용 가능

  • 서비스 기원 시각을 기준으로 시작하여 오버플로 발생 시점을 늦출 수 있음

  • 69년 시간이 지나면 기원 시각을 바꾸거나 다른 ID 체계로 변경 필요

• 장비 고유 번호: 시스템 시작 시 결정

  • 5비트: 데이터 센터 ID / 5비트: 서버 ID 식으로 할당할 수 있음

  • 일반적으로 시스템 운영 중에는 변경되지 않음(잘못 변경 시 충돌 발생 가능)

• 일련번호: 같은 밀리초 동안 하나 이상의 ID를 만들어 낸 경우만 0보다 큰 값으로 증가(최대 4096개)

추가 고려 사항

• 시계 동기화(clock synchronization): 각 서버가 완벽히 같은 시간을 바라보지 않기 때문에 서버 간 시계가 동기화 방법 필요

• 섹션 길이 최적화: 동시성이 낮고 수명이 긴 서비스인 경우 타임스탬프 절의 길이를 늘리고 일련번호 길이를 줄이는 방법을 고려할 수 있음

참고자료

• 가상 면접 사례로 배우는 대규모 시스템 설계 기초