1. 문제 이해 및 설계 범위 확정
•
ID는 유일해야 한다.
•
ID는 숫자로만 구성되어야 한다.
•
ID는 64비트로 표현될 수 있는 값이여야 한다.
•
ID는 발급 날짜에 따라 정렬 가능해야 한다.
•
초당 10,000개의 ID를 만들 수 있어야 한다.
2. 개략적 설계안 제시 및 동의 구하기
2.1. 다중 마스터 복제
•
이 접근법은 데이터베이스의 auto_increment 기능을 활용하는 방안
•
단, 다음 ID의 값을 구할 때 1이 아닌 k 만큼 증가시킨다.
◦
k는 사용 중인 데이터베이스 서버의 수다.
•
단순하고 편리하지만 다음 단점이 있다.
1.
여러 데이터 센터에 걸쳐 규모를 늘리기 어렵다.
2.
ID의 유일성은 보장되겠지만, 그 값이 시간 흐름에 맞추어 커지도록 보장할 수는 없다
3.
서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어렵다.
2.2. UUID
•
UUID는 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트짜리 수다.
•
UUID는 충돌 가능성이 지극히 낮다.
◦
중복이 생길 확률을 50%로 올리려면 초당 10억개의 UUID를 100년 동안 계속 만들어야 한다.
•
장점
◦
서버간의 조율 없이 독립적으로 생산 가능하다.
◦
각 서버가 자기가 쓸 ID를 알아서 만드는 구조이므로 규모 확장도 쉽다.
•
단점
◦
ID가 128비트로 길다.
◦
시간순으로 정렬할 수 없다.
◦
ID에 숫자가 아닌 값이 포함될 수 있다.
2.3. 티켓 서버
•
플리커(Flicker)는 분산 기본 키를 만들어 내기 위해 이 기술을 이용하였다.
•
아이디어의 핵심은 auto_increment 기능을 갖춘 데이터베이스 서버를 중앙 집중형으로 하나만 사용하는 것이다.
•
장점
◦
유일성이 보장되는 오직 숫자로만 구성 된 ID를 쉽게 만들 수 있다.
◦
구현하기 쉽고, 중소 규모 애플리케이션에 적합하다.
•
단점
◦
티켓 서버가 SPOF가 될 수 있다.
◦
해당 티켓 서버의 장애가 모든 서버에 영향을 준다.
2.4. 트위터 스노플레이크 접근법
•
해당 그림은 생성해야 하는 ID의 구조를 여러 절(section)로 분할한 것으로 우리가 생성할 64비트 ID의 구조다.
•
각 절의 쓰임세는 다음과 같다.
◦
사인(sign) 비트 : 나중을 위해 유보해주는 값
◦
타임스탬프(timeStamp) : 기원 시작으로 몇 밀리초가 경과했는지를 나타내는 값
◦
데이터 센터 ID : 데이터 센터 ID
◦
서버 ID : 데이터 센터 당 서버 ID. 데이터 센터당 32개 서버 사용 가능
◦
일련번호 : 각 서버에서 ID를 생성할 때마다 일련번호를 1만큼 증가. 1밀리초가 경과할 때마다 0으로 초기화
3. 상세 설계
•
데이터센터 ID와 서버 ID는 시스템이 시작할 때 결정되며, 일반적으로 시스템 운영 중에는 바뀌지 않는다.
•
데이터센터 ID나 서버 ID를 잘못 변경하게 되면 ID충돌이 발생할 수 있으므로, 신중히 작업해야한다.
3.1. 타임스탬프
•
타임스탬프는 ID 구조에서 가장 중요한 41비트를 차지한다.
•
위 그림은 이진 표현 형태로부터 UTC 시각을 추출하는 예제이다.
•
41비트로 표현 가능한 최대값은 2^41 - 1 =21990232555551ms다.
◦
이 값은 대략 69년에 해당한다.
•
때문에 69년이 지나면 기원 시각을 변경하거나 ID 체계를 다른 것으로 마이그레이션 해야한다.
3.2. 일련번호
•
일련번호는 12비트이므로 2^12 = 4096개의 값을 가질 수 있다.
•
어떤 서버가 같은 밀리초 동안 하나 이상의 ID를 만들어 낸 경우 0보다 큰 값을 갖게 된다.
4. 마무리
•
면접관과 추가 논의 가능한 이슈
◦
시계 동기화(clock synchronization)
▪
여러 서버가 물리적으로 독립된 여러 장비에서 실행되는 경우에는 시계를 동기화 할 수 있는 방법이 있어야한다.
▪
NTP(Network Time Protocol) 를 사용하여 문제를 해결하는 방법이 있음.
◦
각 절(section)의 길이 최적화
▪
동시성(concurrency)이 낮고 수평이 긴 애플리케이션이라면 일련번호 절의 길이를 줄이고 타임스탬프 절의 길이를 늘리는 것이 효과적
◦
고가용성(high availability)
▪
ID 생성기는 필수 불가별(mission critical) 컴포넌트이므로 아주 높은 가용성을 제공해야 한다.
