[스터디9] 09. 분산 시스템을 위한 유일 ID 생성기 설계

목차

7장. 분산 시스템을 위한 유일 ID 생성기 설계

분산 시스템은 여러 서버가 동시에 데이터를 생성하므로, 각 데이터를 고유하게 식별하고 충돌을 방지하기 위해 유일한 ID가 필요하다. 따라서 분산 시스템에서 유일성이 보장되는 ID를 만드는 것은 흥미로우면서도 까다로운 문제다. 이번 장에서는 분산 환경에서 사용할 유일 ID 생성기를 설계한다.

1단계 문제 이해 및 설계 범위 확정

요구사항

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

2단계 개략적 설계안 제시 및 동의 구하기

분산 시스템에서 유일성이 보장되는 ID를 만드는 방법은 여러 가지가 있다.

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

데이터베이스의 auto_increment 기능을 활용하지만, 여러 데이터베이스 서버를 사용하는 방법이다.

• 동작 방식: 현재 사용 중인 데이터베이스 서버의 수를 k라고 하면, 다음 ID 값을 구할 때 이전 값에서 k만큼 증가시킨다.
• 예: 서버가 2대인 경우
  • 서버 1: 1, 3, 5, 7, 9, ...
  • 서버 2: 2, 4, 6, 8, 10, ...

장점

• 데이터베이스 수를 늘리면 초당 생산 가능 ID 수도 늘릴 수 있다.

단점

• 여러 데이터 센터에 걸쳐 규모를 늘리기 어렵다.
• ID의 유일성은 보장되지만 그 값이 시간 흐름에 맞춰 커지도록 보장할 수는 없다.
• 서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어렵다.

2. UUID(Universally Unique Identifier)

UUID는 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트 수이다.

• 형태: 09c93e62-50b4-468d-bf8a-c07e1040bfb2
• 동작 방식: 각 서버가 독립적으로 ID를 생성한다.

장점

• UUID를 만드는 방법이 단순하다. 서버 사이에 조율이 필요 없으므로 동기화 이슈가 없다.
• 각 서버가 자기가 쓸 ID를 알아서 만드므로 규모 확장이 쉽다.

단점

• ID가 128비트로 길다. 요구사항은 64비트이므로 부적합하다.
• ID를 시간순으로 정렬할 수 없다.
• ID에 숫자가 아닌 값이 포함될 수 있다.

3. 티켓 서버(Ticket Server)

auto_increment 기능을 갖춘 데이터베이스 서버(티켓 서버)를 중앙 집중형으로 하나만 사용하는 방법이다.

 

장점

• 유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있다.
• 구현하기 쉽고, 중소 규모 애플리케이션에 적합하다.

단점

• 티켓 서버가 SPOF(Single Point of Failure)가 된다. 이 서버에 장애가 발생하면 해당 서버와 관련된 모든 시스템이 영향을 받는다.
• 이를 해결하기 위해 다중화를 하면 동기화 이슈가 발생할 것이다.

4. 트위터 스노우플레이크(Twitter Snowflake) 접근법

트위터에서 사용하는 방법으로, 생성해야 하는 ID의 구조를 여러 절로 분할하는 방법이다.

• 형태: 64비트를 다음과 같이 나누어 사용한다.
  • 사인 비트(1비트): 음수와 양수를 구별하는 데 사용할 수 있음.
  • 타임스탬프(41비트): 기원 시각(epoch) 이후로 몇 밀리초가 경과했는지 나타내는 값
  • 데이터센터 ID(5비트): 2^5 = 32개 데이터센터를 지원할 수 있음.
  • 서버 ID(5비트): 데이터센터당 2^5 = 32개 서버를 사용할 수 있음.
  • 일련번호(12비트): 각 서버에서는 ID를 생성할 때마다 이 일련번호를 1만큼 증가시킴.

3단계 상세 설계

책에서는 트위터 스노우플레이크 접근법을 사용했다.

• 데이터센터 ID와 서버 ID: 시스템이 시작될 때 결정되며, 일반적으로 시스템 운영 중에는 바뀌지 않음.
• 타임스탬프와 일련번호: ID 생성기가 돌고 있는 중에 만들어지는 값

타임스탬프

시간이 흐름에 따라 점점 큰 값을 가지므로, ID는 시간순으로 정렬 가능하다.

• 41비트로 표현 가능한 타임스탬프의 최대값: 2^41 - 1 = 2199023255551 밀리초
• 기원 시각으로부터 사용 가능한 연수: 약 69년

일련번호

12비트이므로 2^12 = 4096개의 값을 가질 수 있다. 어떤 서버가 같은 밀리초 동안 하나 이상의 ID를 만들어 낸 경우에만 0보다 큰 값을 가진다.

4단계 마무리

위 내용으로부터 요구사항에 대한 스노우플레이크 ID 생성 과정을 다음과 같이 추측해볼 수 있다.

1. 현재 시간을 밀리초 단위로 구한다.
2. 기원 시각을 뺀 값을 타임스탬프로 사용한다.
3. 데이터센터 ID와 서버 ID는 시스템 시작 시 결정된다.
4. 일련번호는 같은 밀리초 내에서 생성될 때마다 증가한다.
5. 각 구성 요소를 해당 비트 위치에 배치하여 64비트 ID를 생성한다.

이번 장에서는 유일 ID를 생성하는 여러 가지 방법을 살펴보았다. 추가적으로 다음과 같은 요소를 고려할 수 있다.

• 시계 동기화(Clock Synchronization): 서버들의 시계가 동기화되어야 한다. NTP(Network Time Protocol) 같은 시계 동기화 서비스를 사용해야 한다.
• 각 절(Section)의 길이 최적화: 동시 사용자가 적다면 일련번호 비트 수를 줄이고 타임스탬프 비트 수를 늘릴 수 있다.
• 고가용성: ID 생성기는 높은 가용성을 제공해야 한다.

 

✔️ 복습하기

1. UUID 방법이 이 문제에 적합하지 않은 이유는?
2. 스노우플레이크 알고리즘이란?

 

 

이 글은 『 가상 면접 사례로 배우는 대규모 시스템 설계 기초』 책을 학습한 내용을 정리한 것입니다.