문제 이해 및 설계 범위 확정
- ID는 유일해야 한다.
- ID는 숫자로만 구성되어야 한다.
- ID는 64비트로 표현될 수 있는 값이어야 한다.
- ID는 발급 날짜에 따라 정렬 가능해야 한다.
- 초당 10,000개의 ID를 만들 수 있어야 한다.
개략적 설계안 제시 및 동의 구하기
다음과 같은 UID를 생성하는 방법들이 있다.
- 다중 마스터 복제
- UUID
- 티켓 서버
- 트위터 스노플레이크 접근법
다중 마스터 복제
ID의 auto_increment 를 사용 중인 데이터베이스 서버의 수만큼 증가시키도록 만든다.
데이터베이스 서버 수를 늘리면 초당 생산 가능 ID 수도 늘릴 수 있다.
단점
- 데이터 센터를 걸쳐서 확장이 어렵다.
- 데이터베이스가 개별적으로 ID를 생성하기 때문에 발급 시간에 따른 ID 정렬을 보장할 수 없다.
- 데이터베이스 서버 추가/삭제시에도 잘 동작하도록 만들기 어렵다. 데이터베이스 서버 추가/삭제시 모든 데이터베이스가 increment 상수를 변경해야 한다.
UUID
UUID는 정보를 유일하게 식별하기 위한 128비트짜리 수다. UUID는 중복될 가능성이 거의 없다고 보면 된다.
UUID는 09c93e21-40b3-428d-bf8b-c06e1030bfb2와 같은 형태를 띠며 서버 간 조율 없이 독립적으로 생성 가능하다.
장점
- 가장 단순하고 서버 사이의 조율이 필요 없으므로 동기화 이슈도 없다.
- 규모 확장도 가장 쉽다.
단점
- ID가 128비트로 길다.
- ID를 시간순으로 정렬할 수 없다.
- ID에 숫자가 아닌 값이 포함될 수 잇다.
티켓 서버
auto_increment 기능을 갖춘 데이터베이스 서버 (티켓 서버)를 중앙 집중적으로 하나만 사용한다.
장점
- 유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있다.
- 구현이 쉽다.
단점
- 티켓 서버가 SPOF가 된다.
트위터 스노플레이크 접근법
트위터에서 스노플레이크(snowflake)라고 부르는 ID 생성 기법을 사용한다.
- sign : 1비트, 음수와 양수 구별.
- timestamp : 41비트, epoch 이후 밀리초.
- datacenter ID: 5비트, 32개 데이터 센터 지원.
- server ID: 5비트, 데이터 센터 당 32개 서버.
- Sequence number: 12 Q비트. ID 생성시마다 1만큼 증가. 매 밀리초마다 0으로 초기화.
상세 설계
타임스탬프
시간 흐름에 따라 큰 값을 갖게 되므로 시간순으로 정렬 가능하다. 이진 표현 형태로부터 UTC 시각을 추출하는 예제다.
41비트 타임스탬프 최댓값은 2^41 -1 = 2199023255551 밀리초로 대략 69년이다. 따라서 이 ID 생성기는 69년동안만 정상 동작되며 69년이 지난 후에는 기원 시각을 바꾸거나 ID 체계를 다른 것으로 바꿔야한다.
일련번호
일련번호는 12비트이므로, 2^12=4096개의 값을 가질 수 있다
마무리
추가 논의 사항
- 시계 동기화 : 이 설계에서는 모든 서버가 같은 시계를 사용한다고 가정하였다. 시계 동기화는 NTP를 통해 해결할수 있다.
- Section 최적화 : 동시성이 낮고 수명이 긴 애플리케이션이라면 일련번호 절의 길이를 줄이고 타임스탬프 절의 길이를 늘릴 수 있다.
- 고가용성 : ID 생성기는 필수 불가결 컴포넌트이므로 아주 높은 가용성을 제공해야 한다.
본 포스트는 알렉스 쉬 저자의 가상 면접 사례로 배우는 대규모 시스템 설계 기초를 기반으로 스터디하며 정리한 내용들입니다.
