[System Design Interview] 7장 분산 시스템을 위한 유일 ID 생성기 설계

auto_increment가 설정된 관계형 데이터베이스는 분산 환경에서 사용할 수 없음
1. 데이터베이스 서버 한 대로는 감당 불가
2. 다중 데이터베이스로는 지연시간(delay)를 낮추기 힘듬

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

요구사항

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

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

유일 ID 생성을 위한 선택지

다중 마스터 복제(mutli-master replication)

다중 데이터베이스에서, auto_increment 할 때 데이터베이스 서버의 수 K만큼 증가시킴

단점

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

UUID(Universally Unique Identifier)

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

UUID는 서버 간 조율 없이 독립적으로 생성 가능함

장점

• UUID를 만드는 것은 단순함. 서버 사이의 조율이 필요 없으므로 동기화 이슈도 없음
• 각 서버가 자기가 쓸 ID를 만드느 구조므로 규모 확장도 쉬움

단점

• ID가 128비트로 김. (요구사항은 64비트)
• ID를 시간순으로 정렬할 수 없음
• ID에 숫자(numberic)가 아닌 값이 포함될 수 있음

티켓 서버(ticket server)

auto_increment 기능을 갖춘 데이터베이스 서버 = 티켓 서버를 중앙 집중형으로 하나만 사용

장점

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

단점

• 티켓 서버가 SPOF(Single-Point-of-Failure)가 됨

트위터 스노플레이크(twitter snowflake) 접근법

각개 격파 전략(divide and conquer) 적용

ID의 구조를 여러 절(section)으로 분할

• 사인(sign) 비트: 1비트 할당. 음수와 양수 구별
• 타임스탬프(timestamp): 41비트 할당. 기원 시각(epoch) 이후로 몇 밀리초(ms)가 경과했는지를 나타냄
• 데이터센터 ID: 5비트를 할당 → 따라서 2^5=32개의 데이터센터를 지원할 수 있음
• 서버 ID: 5비트를 할당 → 따라서 데이터센터당 32개의 서버를 사용할 수 있음
• 일련번호: 12비트를 할당. 각 서버에서는 ID를 생성할 때마다 일련번호를 1만큼 증가시킴. 1밀리초가 경과할 떄마다 0으로 초기화(reset)됨

3단계 - 상세 설계

트위터 스노플레이크(twitter snowflake) 접근법 사용

데이터센터 ID와 서버ID는 시스템이 시작할 때 결정되므로 바뀌지 않음

타임스탬프나 일련번호는 ID 생성기가 돌고 있는 중에 만들어짐

타임스탬프

가장 중요한 41비트를 차지하고 있음

시간의 흐름에 따라 점점 큰 값을 갖게 되므로, 결국 ID는 시간순으로 정렬 가능

이진 표현 형태로부터 UTC 시각을 추출 = 41비트 십진수로 → 트위터 기원 시각(epoch) 더함 → 결과로 얻어진 밀리초 값을 UTC 시각으로 변환

⇒ 이 방법을 역으로 적용하면 어떤 UTC 시각도 상술한 타임스탬프 값으로 변환 가능

타임스탬프의 최댓값은 69년 → ID 생성기는 69년동안만 정상 동작

일련번호

서버가 같은 밀리초 동안 하나 이상의 ID를 만들어 낸 경우에만 0보다 큰 값을 갖게 됨

4단계 - 마무리

유일성이 보장되는 ID 생성기 구현에 쓰일 수 있는 다양한 전략

• 다중 마스터 복제
• UUID
• 티켓 서버
• 트위터 스노플레이크

추가로 논의하면 좋을 것들

• 시계 동기화(clock synchronization): 여러 서버가 물리적으로 독립되거나, 여러 코어에서 실행될 경우 시계가 달라질 수 있음
• 각 절(section)의 길이 최적화: 동시성이 낮고 수명이 긴 애플리케이션이라면 일련번호 절의 길이를 줄이고 타임스탬프 절의 길이를 늘릴 수 있음
• 고가용성(high availability): ID 생성기는 필수 불가결(mission critical) 컴포넌트이므로 아주 높은 가용성을 제공해야 함

 

Reference: http://www.yes24.com/Product/Goods/102819435

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