분산 시스템을 위한 유일 ID 생성기 설계
- 분산 시스템에서는 auth_increment 속성이 설정된 관계형 데이터 베이스의 기본 키는 적용되지 않음
1단계 문제 이해 및 설계 범위 확정
- 요구 사항
- ID는 유일해야 함
- ID는 숫자로만 구성되어야 함
- ID는 64비트로 표현될 수 있는 값이어야 함
- ID는 발급 날짜에 따라 정렬 가능해야 함
- 초당 10,000 개의 ID를 만들 수 있어야 함
2단계 개략적 설계안 제시 및 동의 구하기
- 다중 마스터 복제 (multi-master replication)
- 데이터의 auth_increment 기능을 활용하면서 k(= 데이터 베이스 서버 수) 만큼 아이디를 증가시킴
- 단점
- 여러 데이터 센터에 걸쳐 규모를 늘리기 어려움
- ID의 유일성은 보장되지만 시간 흐름에 맞춰 커지도록 보장 불가
- 서버를 추가하거나 삭제할 때도 잘 동작하게 만들기 어려움
- UUID (universally unique identifier)
- 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트짜리 수
- 충돌 가능성은 지극히 낮음
- 중복 1개가 생길 확률을 50%로 끌어 올리려면 초당 10억개의 UUID를 100년동안 계속해서 만들어야 함
- 장점
- 생성이 단순
- 서버 사이의 조율이 필요 없어 동기화이슈도 없음
- 각 서버가 자기가 쓸 ID를 만드는 구조이므로 규모 확장도 쉬움
- 단점
- ID가 128비트로 길다
- ID를 시간순으로 정렬 불가
- ID에 숫자(numeric)가 아닌 값이 포함될 수 있음
- 티켓 서버 (ticket server)
- 유일성이 보장되는 ID를 만들어 내는데 쓰일 수 있음
- auto_increment 기능을 갖춘 데이터 베이스 서버인 티켓 서버를 중앙 집중형으로 사용
- 장점
- 유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 생성
- 구현하기 쉽고 중소 규모 애플리케이션에 적합
- 단점
- 티켓 서버가 SPOF(single point of failure)가 됨
- 안정성을 위해 티켓 서버를 여러대로 구성하면 동기화 이슈 발생
https://en.wikipedia.org/wiki/Snowflake_ID
- 트위터 스노플레이크 (twitter snowflake)
- 각개격파 전략 (divide and conquer)
- 생성해야 하는 ID의 구조를 여러 절로 분할
- 데이터센터 ID와 서버ID는 시스템이 시작할 때 결정되며 일반적으로 시스템 운영중에는 변경되지 않음
- 타임스탬프나 일련번호는 ID 생성기가 돌고 있는 중에 만들어지는 값
- ex) 요구사항의 64비트 ID를 다음과 같이 나눔
- 사인비트
- ex) 1비트를 할당
- 지금은 사용되지 않지만 추후 나중을 위해 유보
- 음수 양수를 구별하는데에 사용될 수 있음
- 타임스탬프
- ex) 41비트를 할당
- 기원 시간 이후로 몇밀리초가 경과했는지 나타내는 값
- 시간에 따라서 점점 큰 값을 가지게 되므로 결국 시간순으로 정렬이 가능해짐
- 데이터센터 ID
- ex) 5비트를 할당
- 2^5 = 32개의 데이터센터를 지원할 수 있음
- 서버 ID
- ex) 5비트를 할당
- 데이터 센터당 2^5 = 32개 서버를 사용할 수 있음
- 일련번호
- ex) 12바이트를 할당
- 각 서버에서는 ID를 생성할 때 마다 이 일련번호를 1만큼 증가시킴
- 1밀리초가 경과할 때마다 0으로 초기화 됨
3단계 상세 설계
- 타임스탬프
- 앞서 설계한 구조에서 가장 중요한 41비트를 차지
- 시간에 따라서 점점 큰 값을 가지게 되므로 결국 시간순으로 정렬이 가능해짐
- 표현 형태를 이용해서 어떤 UTC 시간도 상술한 타임스탬프 값으로 변환 가능
- 41비트의 경우 표현 가능한 타임스탬프의 최대 값은 2^41 -1 = 2199023255551밀리초 = 약 69년
- 따라서 이 ID 생성기는 69년동안만 정상 동작하고, 기원 시각을 현재에 가깝게 맞춰서 오버플로가 발생하는 시점을 늦춰 높은 것
- 69년이 지나면 기원 시각으로 바꾸거나 ID 체계를 다른 것으로 이전해야 함
- 일련번호
- 12비트 = 2^14 = 4096개의 값을 가질 수 있음
- 어떤 서버가 같은 밀리초 동안 하나 이상의 ID를 만들어 낸 경우에만 0보다 큰 값을 갖게 됨
4단계 마무리
- 추가 논의 가능한 부분
- 시계 동기화 (clock synchronization)
- 하나의 서버가 여러 코어에서 실행될 경우 전부 같은 시계값을 사용하지 않을 수 있음
- NTP (Network Time Protocol)은 이 문제를 해결하는 가장 보편적인 수단
- 각절(section)의 길이 최적화
- 동시성이 낮고 수명이 긴 애플리켄이션이라면 일련번호 절의 길이를 줄이고 타임스탬프 절의 길이를 늘리는 것이 효과적
- 고가용성 (high availability)
- ID 생성기는 필수 불가결(mission critical) 컴포넌트이므로 아주 높은 가용성을 제공해야 함