[대규모 시스템 설계 스터디] 7장 정리

김연준·2026년 7월 30일

[대규모 시스템 설계 스터디]

목록 보기
7/13
post-thumbnail

분산 시스템을 위한 유일 ID 생성기

1. 유일 ID 생성기가 필요한 이유

  • 관계형 데이터베이스의 기본 키에 auto_increment 속성을 설정하면 간단하게 유일 ID 생성 가능

  • 그러나 대규모 분산 환경에서는 단일 데이터베이스가 병목 또는 단일 장애 지점이 될 수 있음

  • 여러 데이터베이스 서버를 사용하면 처리량을 늘릴 수 있지만 다음 문제 발생 가능

    • ID 충돌 방지를 위한 서버 간 조정 필요
    • ID 생성 순서 보장 어려움
    • 네트워크 통신으로 인한 지연 시간 증가
    • 서버 추가 및 제거 시 운영 복잡도 증가

시스템 설계 면접의 첫 단계는 질문을 통해 모호한 요구사항을 제거하고 설계 범위를 확정하는 것임.

2. 문제 이해 및 설계 범위 확정

이번 장에서 주어진 요구사항은 다음과 같음.

  • ID는 유일해야 함
  • ID는 숫자로만 구성되어야 함
  • ID는 64비트로 표현할 수 있어야 함
  • ID는 발급 날짜에 따라 정렬 가능해야 함
  • 초당 10,000개의 ID를 생성할 수 있어야 함

3. 개략적인 설계안

분산 시스템에서 유일성이 보장되는 ID를 생성하는 방법은 다음과 같음.

  • 다중 마스터 복제
  • UUID
  • 티켓 서버
  • Twitter Snowflake 방식

4. 다중 마스터 복제

4.1 기본 원리

  • 여러 데이터베이스 서버의 auto_increment 기능 활용
  • 각 서버의 시작값을 다르게 설정
  • ID 증가폭 k를 전체 데이터베이스 서버 수로 설정

데이터베이스 서버가 3대인 경우:

서버 A: 1, 4, 7, 10 ...
서버 B: 2, 5, 8, 11 ...
서버 C: 3, 6, 9, 12 ...
  • 각 서버의 시작값은 각각 1, 2, 3
  • 각 서버의 ID 증가폭은 3
  • 서로 다른 서버가 같은 ID를 생성하는 문제 방지

4.2 장점

  • 데이터베이스 서버 수를 늘려 ID 생성 처리량 증가 가능
  • 단일 데이터베이스의 처리량 한계 일부 완화
  • 기존 데이터베이스의 auto_increment 기능 활용 가능

4.3 단점

  • 여러 데이터센터에 걸쳐 규모를 확장하기 어려움
  • ID의 유일성은 보장할 수 있지만 생성 시간에 따라 값이 증가하는 것은 보장하기 어려움
  • 서버 수가 변경되면 증가폭과 시작값 규칙을 다시 조정해야 함
  • 서버를 추가하거나 제거하는 과정의 운영 복잡도가 높음

5. UUID

5.1 기본 개념

  • 컴퓨터 시스템의 정보를 유일하게 식별하기 위한 128비트 식별자
  • 여러 서버가 서로 조율하지 않고 독립적으로 생성 가능
  • 중복 UUID가 생성될 확률이 0은 아니지만 현실적으로 무시할 수 있을 정도로 낮음

5.2 장점

  • 생성 방식이 비교적 단순함
  • 서버 사이의 조율이 필요 없음
  • 중앙 ID 생성 서버가 필요 없음
  • 서버를 추가하더라도 별도의 ID 범위 할당이 필요 없음
  • 수평적 규모 확장이 쉬움

5.3 단점

  • 128비트로 구성되어 64비트 요구사항을 만족하지 못함
  • 일반적으로 많이 사용하는 무작위 기반 UUIDv4는 생성 시간순 정렬이 어려움
  • 일반적인 문자열 표현에 16진수 문자와 하이픈이 포함됨

예시:

550e8400-e29b-41d4-a716-446655440000
  • UUID 자체는 128비트 값임
  • 문자열로 표현할 때 a~f와 하이픈이 포함되므로 숫자로만 구성되어야 한다는 요구사항을 만족하지 못함

6. 티켓 서버

6.1 기본 원리

  • auto_increment 기능을 갖춘 데이터베이스 서버를 중앙 ID 생성 서버로 사용
  • 다른 서비스는 ID가 필요할 때 티켓 서버에 요청
  • 티켓 서버가 순차적으로 증가하는 유일 ID 발급

6.2 장점

  • 유일성이 보장되는 숫자 ID를 쉽게 생성 가능
  • 구현이 비교적 단순함
  • 생성된 ID가 순차적으로 증가함
  • 중소 규모 애플리케이션에 적합

6.3 단점

  • 모든 ID 생성 요청이 하나의 티켓 서버에 집중
  • 티켓 서버 장애 시 ID를 생성할 수 없는 단일 장애 지점 발생
  • 티켓 서버의 처리 능력이 전체 시스템의 ID 생성 한도 결정

6.4 다중 티켓 서버 구성

  • 단일 장애 지점을 피하기 위해 여러 티켓 서버를 둘 수 있음
  • 여러 티켓 서버가 서로 다른 ID를 발급하도록 조정 필요
  • 서버 간 상태 동기화와 충돌 방지 문제 발생
  • 구조가 복잡해지면서 티켓 서버 방식의 단순성 감소

7. Twitter Snowflake 방식

7.1 기본 개념

  • 하나의 64비트 ID를 여러 영역으로 분할
  • 생성 시각과 ID 생성 서버 정보를 하나의 정수에 포함
  • 각 서버가 다른 서버와 매번 통신하지 않고 독립적으로 ID 생성 가능
  • ID의 상위 영역에 타임스탬프를 배치하여 대체로 생성 시각 순으로 정렬 가능

7.2 64비트 구조

7.3 사인 비트

  • 1비트 사용
  • 현재 구조에서는 별도의 값을 저장하지 않고 0으로 유지
  • 추후 ID 체계를 확장하거나 용도를 변경할 때 활용 가능

7.4 타임스탬프

  • 41비트 사용
  • 시스템이 정한 기원 시각 이후 몇 밀리초가 경과했는지 저장
타임스탬프 값 = 현재 시각 - 자체 epoch
  • 밀리초 단위의 41비트로 약 69.7년 표현 가능
  • Unix epoch가 아닌 서비스 시작 시점과 가까운 자체 epoch 설정 가능
  • 자체 epoch를 사용하면 제한된 비트 범위를 서비스 운영 기간에 효율적으로 사용 가능

7.5 데이터센터 ID

  • 5비트 사용
  • 최대 32개의 데이터센터 식별 가능
2⁵ = 32
  • 서로 다른 데이터센터에서 생성한 ID를 구분하는 데 사용

7.6 서버 ID

  • 5비트 사용
  • 하나의 데이터센터에서 최대 32개의 ID 생성 서버 식별 가능
2⁵ = 32
  • 데이터센터 ID와 서버 ID의 조합으로 최대 1,024개의 생성 서버 구분 가능
32 × 32 = 1,024

7.7 일련번호

  • 12비트 사용
  • 같은 서버가 같은 밀리초 안에서 여러 ID를 생성할 때 중복 방지
  • 동일한 밀리초 안에서 ID를 생성할 때마다 1씩 증가
  • 밀리초가 변경되면 0으로 초기화

같은 밀리초에서 생성되는 ID:

첫 번째 ID: 일련번호 0
두 번째 ID: 일련번호 1
세 번째 ID: 일련번호 2
...
  • 12비트로 한 서버가 1밀리초에 최대 4,096개의 ID 생성 가능
2¹² = 4,096
  • 같은 밀리초 안에서 4,096개를 모두 사용하면 다음 밀리초가 될 때까지 대기 필요

7.8 이론적 처리량

한 서버가 1밀리초에 최대 4,096개의 ID를 생성할 수 있으므로 이론적인 초당 처리량은 다음과 같음.

4,096 × 1,000
= 초당 4,096,000개
  • 요구사항인 초당 10,000개의 ID 생성 가능
  • 실제 처리량은 언어, 구현 방식, 락, 하드웨어 등의 영향을 받음

8. 상세 설계

8.1 정적 값

다음 값은 ID 생성기가 시작될 때 결정됨.

  • 데이터센터 ID

  • 서버 ID

  • 자체 epoch

  • 일반적으로 운영 중에는 변경하지 않음

  • 동시에 동작하는 생성기는 서로 다른 데이터센터 ID와 서버 ID 조합을 가져야 함

  • 서로 다른 생성기가 같은 식별자 조합을 사용하면 ID 충돌 가능

ID 충돌 조건:

  • 동일한 데이터센터 ID
  • 동일한 서버 ID
  • 동일한 타임스탬프
  • 동일한 일련번호

운영 중 서버 ID를 재할당할 때는 기존 생성기와 중복되지 않도록 관리 필요.

8.2 동적 값

다음 값은 ID 생성기가 동작하는 동안 계속 변경됨.

  • 타임스탬프

  • 일련번호

  • 타임스탬프는 현재 시각에 따라 증가

  • 일련번호는 같은 밀리초 안에서 ID를 생성할 때마다 증가

  • 밀리초가 변경되면 일련번호 초기화

9. 타임스탬프 영역의 수명

  • 41비트 타임스탬프로 약 69.7년 표현 가능
  • 기원 시각으로부터 약 69.7년이 지나면 타임스탬프 영역 소진
  • 소진되기 전에 새로운 ID 형식이나 별도의 버전 체계로 마이그레이션 필요
  • 동일한 ID 공간에서 epoch만 단순히 변경하면 과거 ID와 충돌할 수 있음
  • 새로운 형식임을 구분할 별도의 버전 또는 네임스페이스 필요

10. 동시성 문제

10.1 여러 스레드 또는 코어에서의 실행

  • 하나의 ID 생성기가 여러 스레드나 CPU 코어에서 동시에 실행될 수 있음
  • 여러 실행 흐름이 같은 일련번호를 동시에 읽고 증가시키면 중복 ID 발생 가능

예시:

스레드 A: 현재 일련번호 10 확인
스레드 B: 현재 일련번호 10 확인

스레드 A: 일련번호 11로 ID 생성
스레드 B: 일련번호 11로 ID 생성
  • 동일한 타임스탬프와 서버 정보에서 같은 일련번호를 사용하면 ID 충돌 발생

10.2 해결 방법

  • 락을 사용해 한 번에 하나의 스레드만 일련번호 수정
  • 원자적 연산을 이용해 일련번호 증가
  • 단일 스레드 ID 생성기 사용
  • 생성 요청을 큐에 넣고 순차적으로 처리

11. 시계 동기화 문제

11.1 여러 서버의 시계 오차

  • 물리적으로 독립된 여러 서버는 시스템 시각이 완전히 같지 않을 수 있음
  • 서버 간 시계 차이가 크면 나중에 생성된 ID가 더 작은 타임스탬프를 가질 수 있음
  • 실제 생성 순서와 ID 정렬 순서가 달라질 수 있음

11.2 NTP 활용

  • NTP를 이용해 여러 서버의 시스템 시계를 동기화 가능
  • 서버 간 시계 오차를 줄여 타임스탬프 차이 완화 가능

12. 비트 길이 최적화

서비스 특성에 따라 각 영역의 비트 수 변경 가능.

12.1 동시성이 낮고 운영 기간이 긴 서비스

  • 짧은 시간에 생성하는 ID 수가 적음
  • 일련번호 비트 수 축소 가능
  • 줄인 비트를 타임스탬프 영역에 추가
  • ID 체계의 사용 가능 기간 증가

12.2 생성 서버가 적은 서비스

  • 데이터센터 ID 또는 서버 ID 비트 수 축소 가능
  • 타임스탬프나 일련번호 영역 확대 가능

12.3 동시성이 높은 서비스

  • 일련번호 비트 수 확대 가능
  • 한 밀리초에 더 많은 ID 생성 가능
  • 대신 타임스탬프 또는 서버 식별 영역 축소 필요

비트 분할은 다음 요소를 기준으로 결정해야 함.

  • 예상 서비스 운영 기간
  • 데이터센터 수
  • ID 생성 서버 수
  • 밀리초당 최대 ID 생성량

13. 고가용성

  • ID 생성기는 여러 서비스에서 공통으로 사용하는 핵심 컴포넌트
  • ID 생성기가 중단되면 데이터 생성, 주문, 게시물 등록 등의 기능도 중단될 수 있음
  • 높은 가용성 제공 필요

13.1 고려 사항

  • 여러 ID 생성 서버 운영
  • 생성 서버마다 고유한 데이터센터 ID와 서버 ID 할당
  • 생성 서버 장애 자동 감지
  • 장애 서버의 트래픽을 정상 서버로 전환
  • 서버 식별자 중복 할당 방지
  • 모니터링과 경고 체계 구성
  • 생성 실패 및 지연 시간 측정

14. 방식 비교

방식ID 길이시간순 정렬서버 간 조율규모 확장주요 단점
다중 마스터 복제설정에 따라 다름완전 보장 어려움설정 조정 필요보통서버 수 변경이 어려움
UUID128비트UUIDv4는 어려움불필요쉬움64비트·숫자 요구사항 불충족
티켓 서버설정에 따라 다름가능중앙 서버 필요제한적단일 장애 지점
Snowflake64비트대체로 가능생성 시 불필요쉬움시계와 서버 ID 관리 필요

15. 정리

다중 마스터 복제

  • 각 데이터베이스 서버가 서로 다른 시작값과 공통 증가폭 사용
  • ID 생성 처리량 증가 가능
  • 서버 수 변경과 다중 데이터센터 확장에 불리함

UUID

  • 서버 간 조율 없이 독립적으로 생성 가능
  • 규모 확장이 쉬움
  • 128비트이며 UUIDv4는 시간순 정렬이 어려움
  • 숫자로만 구성된 64비트 ID 요구사항에 부적합

티켓 서버

  • 중앙 데이터베이스의 auto_increment 기능 활용
  • 구현이 단순하고 순차적 ID 생성 가능
  • 단일 장애 지점과 중앙 병목 발생 가능

Twitter Snowflake

  • 타임스탬프, 데이터센터 ID, 서버 ID, 일련번호를 64비트에 조합
  • 서버 간 통신 없이 유일 ID 생성 가능
  • 대체로 시간순 정렬 가능
  • 한 서버에서 매우 높은 처리량 지원
  • 시계 동기화, 동시성, 서버 식별자 중복 관리 필요

16. 내가 생각한 우리 시스템에 적합한 유일 ID 생성기는

우리 시스템에는 Snowflake보다 관계형 데이터베이스의 auto_increment 또는 sequence 방식이 적합하다고 판단함.

우리 시스템은 여러 데이터센터와 독립된 데이터베이스에 걸쳐 운영되는 대규모 서비스가 아니라 일회성 애플리케이션임. 처리해야 하는 ID 생성량도 Snowflake가 제공하는 초당 수백만 개 수준의 처리량을 요구하지 않음.

Snowflake를 사용하면 다음 요소를 추가로 관리해야 함.

  • 데이터센터 ID와 서버 ID 할당
  • 생성 서버 간 식별자 중복 방지
  • 일련번호 동시성 제어
  • 서버 간 시계 동기화
  • 시계 역행 처리
  • 별도의 ID 생성기 배포와 장애 대응

이러한 기능은 여러 서버가 중앙 데이터베이스와 통신하지 않고 독립적으로 ID를 생성해야 할 때 유용함. 하지만 우리 시스템에서는 얻을 수 있는 이점보다 구현 및 운영 복잡도가 더 클 것으로 판단됨.

관계형 데이터베이스의 auto_increment 또는 sequence를 사용하면 다음 장점이 있음.

  • 별도의 ID 생성 시스템이 필요하지 않음
  • 숫자로 구성된 유일 ID 생성 가능
  • ID가 순차적으로 증가함
  • 여러 애플리케이션 서버가 동시에 요청해도 데이터베이스가 유일성 보장
  • 구현과 운영이 단순함

우리 시스템에서 중요한 요구사항은 높은 가용성임. 그러나 이를 위해 ID 생성기만 별도로 분산시키기보다는 데이터를 저장하는 데이터베이스 자체를 고가용성으로 구성하는 것이 더 적절함.

예를 들어 주 데이터베이스와 대기 데이터베이스를 구성하고, 주 데이터베이스 장애 시 대기 데이터베이스로 자동 전환하도록 설계할 수 있음. 데이터베이스가 중단되면 ID를 별도로 생성하더라도 실제 데이터를 저장할 수 없으므로, ID 생성기와 데이터베이스의 가용성을 분리하여 해결할 필요성이 낮음.

따라서 우리 시스템에서는 다음 방식을 선택함.

  • 유일 ID 생성: BIGINT auto_increment 또는 데이터베이스 sequence 사용
  • 애플리케이션 가용성: 여러 애플리케이션 서버와 로드밸런서 구성
  • 데이터베이스 가용성: 주 데이터베이스와 대기 데이터베이스 및 자동 장애 조치 구성

Snowflake는 향후 시스템이 여러 데이터센터나 독립된 데이터베이스로 확장되고, 각 서버가 중앙 조정 없이 대량의 ID를 생성해야 할 때 다시 검토하는 것이 적절함.

profile
김연준
Live a life you will remember
이전 포스트

[대규모 시스템 설계 스터디] 6장 정리

다음 포스트

[대규모 시스템 설계 스터디] 8장 정리

0개의 댓글