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

 

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

 

요구사항

- ID는 유일해야한다. 숫자로만 구성되어야 한다

- 64비트로 표현될 수 있는 값이어야 한다. 

- 발급 날짜에 따라서 정렬 가능해야한다.

- 초당 10,000개의 ID를 만들 수 있어야 한다. 

 

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

1. 다중 마스터 복제 (Multi-master replication)

auto_increment 기능을 활용한다. 다음 ID를 구현할 때 1만큼 증가시키는건 아니고, K만큼씩 증가시킨다. K는 현재 사용중인 데이터베이스 서버의 수다. DB수를 늘리면 초당 생산 가능한 ID수도 늘릴 수 있음으로, 규모 확장성 문제를 어느정도 해소한다. 

 

2. UUID

유일성이 보장되느 ㄴID를 만드는 또하나의 간단한 방법이다. UUID는 128비트짜리 수다. 

중복 UUID를 1개 생길 확률을 50% 끌어올릴려면 초당 10억개의 UUID를 100년동안 계속해서 만들어야 한다. [1]

각각의 웹서버는 별도의 ID 생성기를 사용해서 독립적으로 ID를 만들어낸다. 

 서버사이 조율이 필요없음으로 동기화 이슈도 없다. 각 서버가 자기가 쓸 ID를 알아서 만들기 때문에 규모 확장도 쉽다. 

시간순 정렬이안된다. 숫자가 아닌 값이 포함된다. ID가 128비트임으로 길다. 

 

3. 티켓 서버

플리커(Flickr)는 분산 기본 키를 만들어 내기 위해 이기술을 이용했다. [2]

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

구현이 쉽고, 중소 규모 애플리케이션에 적합하다.

티켓 서버가 SPOF(Single-Point-of-Failure)가 된다. 

 

4. 트위터 스노플레이크 

트위터는 스노플레이크(snoewflake)라고 부르는 독창적인 ID 생성 기법을 사용한다. 

생성해야 하는 ID의 구조를 여러 절로 분할 하는 것이다. 우리가 생성할 64비트의 ID 구조를 위와 같이 분할한다. 

각절의 쓰임새는 다음과 같다. 

 

- 사인(sign) 비트: 1비트 할당. 

- 타임스탬프 : 41비트 할당. epoch 이후로 몇 밀리초가 경과했는지를 나타낸다. 1288834974657(Nov 04,2010,01:42:54 UTC)

 

ID구조에서 가장 중요한 41비트를 차지한다. 시간 흐름에 따라서 점점 큰 값을 갖음으로, 결국 ID는 시간순으로 정렬이 가능해진다.

이진 표현 형태로부터 UTC 시각을 추출하는 예제이다. 어떠한 UTC시각도 상술한 타임스탬프 값으로 변환이 가능해진다. 

2^41-1=2199023255551밀리초이다. 대략 69년에 해당한다. 2199023255551밀리초/ 1000/365일 /24시간/3600초 

따라서 69년 동안만 동작한다. 기원 시각을 현재에 가깝게 맞춰서 overflow가 발생하는 시점을 늦춰놓는다. 69년이 지나면 기원시각을 바꾸거나 id체계를 다른거로 이전해야한다. 

 

 

 

- 데이터 센터 : 5 비트 할당. 2^5=32 데이터 센터를 지원할 수 있다. 

- 서버 ID  : 5 비트 할당. 데이터 센터당 32개 서버를 사용할 수 있다. 

- 일련번호 : 

12비트임으로, 2^12=4096개의 값을 가진다. 각 서버에서는 ID를 생성할 때마다 일련번호를 1만큼 증가 시킨다. 이 값은 1밀리초가 경과할 때마다 0으로 초기화(reset)된다. 

같은 밀리초 동안 하나 이상의 ID를 만들어낸 경우만 0보다 큰 값을 갖는다. 

 

 

 

상세 설계 

 

• 시계 동기화(clock synchronization): 이번 설계를 진행하면서 우리는 ID 생성 서버들이 전부 같은 시계를 사용한다고 가정하였다. 하지만 이런 가정은 하나의 서버가 여러 코어에서 실행될 경우 유효하지 않을 수 있다. 여러 서버가 물리적으로 독립된 여러 장비에서 실행되는 경우에도 마찬가지다. 시계 동기화의 실제 방법은 이 책이 다룰 주제는 아니지만, 그런 문제가 있다는 점을 알아두는 것은 중요하다. NTP(Network Time Protocol)은 이 문제를 해결하는 가장 보편적 수단이다. 관심 있는 독자는 [4]를 참고하기 바란다.
• 각 절(section)의 길이 최적화: 예를 들어 동시성(concurrency)이 낮고 수명이 긴 애플리케이션이라면 일련번호 절의 길이를 줄이고 타임스탬프 절의 길이를 늘리는 것이 효과적일 수도 있을 것이다.
• 고가용성(high availability): ID 생성기는 필수 불가결(mission critical) 컴포넌트이므로 아주 높은 가용성을 제공해야 할 것이다.

 

참고문헌

[1] Universally unique identifier: https://en.wikipedia.org/wiki/Universally_unique_identifier

[2] Ticket Servers: Distributed Unique Primary Keys on the Cheap: https://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/

[3] Announcing Snowflake: https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake.html

[4] Network time protocol: https://en.wikipedia.org/wiki/Network_Time_Protocol