[가상 면접 사례로 배우는 대규모 시스템 설계 기초] 7. 분산 시스템을 위한 유일 ID 생성기 설계

분산 시스템에서는 단순히 DB 의 auto_increment 속성을 통한 기본 키를 사용하기 어렵다. 서버 한 대로는 모든 요청을 처리하기 힘들고, 여러 DB를 사용하게 되면 키의 유일성과 딜레이를 두고 고민해야한다. 그런 이유에서 이 장에서는 분산 시스템에서 사용할 수 있는 유일 ID 생성기를 설계해본다.

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

이 장에서 설계할 시스템에 대한 요구 사항을 다음과 같이 정리했다.

 

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

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

분산 시스템에서 유일성이 보장되는 ID를 만드는 여러 방법들과 각각의 장단점을 정리한다.

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

DB의 auto_increment 기능을 활용한 방식이다. 다만 ID의 값을 구할 때 1씩 구하는 것이 아니라 k만큼 증가시킨다. 여기서 k는 현재 DB 서버의 개수로 k만큼 증가시킴으로 여러 DB에서 생성하는 ID의 유일성을 해결한다.

 

하지만 서버를 추가하거나 삭제할 때 이에 맞춰서 k값을 변경해주고 초기 값을 설정해줘야 하는 어려움이 있다. 또한 어떤 DB에 값이 저장되느냐에 따라서 먼저 발급된 ID보다 작은 값을 ID로 가질 수 있기 때문에 시간 흐름에 맞춘 ID 정렬이 불가능하다.

- UUID

UUID는 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트짜리 수로 값이 충돌할 가능성이 지극히 낮다. UUID는 ebf290c4-46ff-42ba-a46b-9e89dd6be7b7 와 같은 형식으로 서버 간 조율없이 각각 독립적으로 생성 가능하다.

 

UUID를 사용하는 방법은 단순하고 쉽다. 서버간의 조율도 필요없고, 이에따라 서버를 추가하고 삭제하는 규모 변동에도 유리하다. 하지만 ID 크기가 128비트로 요구사항의 64비트보다 크고, 시간순 정렬이 불가능하며, 숫자가 아닌 값이 ID에 포함되기 때문에 요구사항에 맞지 않다.

- 티켓 서버

티켓 서버는 auto_increment 기능을 갖춘 DB 서버를 하나만 티켓 서버로 두고 중앙 집중형으로 사용하는 것이다. 이러한 방식을 이용하면 하나의 서버에서만 키를 생성하기 때문에 유일성이 보장되며 숫자로만 구성된 ID를 간단하게 생성할 수 있다.

 

그러나 중앙 집중형이라는 것은 결국 해당 서버에 장애가 발생하면 전체 시스템에 문제가 된다는 것이다. 이는 곧 SPOF를 의미한다. 이를 해결하기 위해서는 티켓 서버를 여러대 준비해야 하는데, 이는 데이터 동기화 같은 새로운 문제를 발생시킨다.

- 트위터 스노우플레이크

트위터는 스노우플레이크 (snowflake) 라는 방식을 사용하여 유일 ID 생성 문제를 해결하였다. 이 방식에서는 64비트의 ID를 다음과 같이 분할하여 사용한다.

 

sign bit (1bit)

timestamp ID (41bit)

machine ID (10bit)

sequence number (12bit)

- sign bit: 후에 음수 양수를 구별하는데 사용될 수 있도록 1비트를 할당해둔다.
- timestamp id: 기원 시각 (epoch) 이후로 몇 밀리초 (millisecond) 가 경과했는지를 나타내는 값이다. 트위터의 기원 시각은 1288834974 (Nov 04, 2010, 01:42:54 UTC) 이다.
- machine id: 10비트를 할당하여 1024개의 머신을 지원할 수 있도록 한다. 책에서는 데이터센터에 5비트, 서버에 5비트를 할당하여 각각 32개의 데이터센터와 서버를 지원할 수 있도록 설계했다.
- sequence number: 12비트를 할당하여 각 서버에서 ID를 생성할 때마다 1씩 증가시키도록 한다. 이 값은 1밀리초마다 0으로 초기화된다. 이론적으로 한 서버당 1초에 4096개의 ID를 생성할 수 있다.

3. 상세설계

트위터의 스노우플레이크 방식을 사용한다면 기본적으로 machine id는 데이터센터의 ID와 서버 ID의 조합으로 고정이 된다. 이외에 타임스탬프와 일련번호는 생성기의 런타임에 생성된다.

- 타임스탬프

타임스탬프는 UTC 시간을 기반으로 생성되어 ID를 시간순으로 정렬할 수 있게 해준다.

 

기원 시각을 기준으로 지난 시간을 값으로 사용하여 정의하는데, 타임스탬프의 최댓값은 2^41 - 1 로 대략 69년에 해당한다. 이 말은 ID 생성기가 69년동안 중복없이 정상 동작한다는 의미로 69년이 지나면 기원 시각을 바꾸거나 ID 체계를 다른 것으로 마이그레이션 해야한다.

- 일련번호

일련번호는 12비트로 최대 4096개의 값을 가질 수 있다. 밀리초마다 0으로 초기화 되기 때문에 어떤 서버가 같은 밀리초 동안 하나 이상의 ID를 만들어 낸 경우에만 0보다 큰 값을 갖게된다.

4. 마무리

유일 ID 생성기에 대해서 추가적으로 고민해볼 만한 주제로는 다음과 같은 것들이 있다.

- 시계 동기화 (clock synchronization): 여러 서버가 모두 같은 시계를 사용하는 것이 아니라 여러 코어 또는 물리적으로 독립된 장비에서 실행되어 다른 시계를 사용하는 경우 ID의 유일성, 시간순 정렬 등이 어긋날 수 있다. 이러한 경우 각 서버의 시계를 동기화해야 하는데, 이때 NTP (Network Time Protocol) 등의 방법을 사용한다.
- 각 절의 길이 최적화: 동시성이 낮고 수명이 긴 애플리케이션의 경우 일련번호 절의 길이를 줄이고 타임스탬프 절의 길이를 늘려서 초당 생산성을 낮추고 타임스탬프의 최대값을 늘리는 것이 더 효과적일 수 있다.
- 고가용성 (high availability): ID 생성기는 모든 서버에 필수불가결한 컴포넌트이기 때문에 장애없이 높은 가용성을 제공해야 한다

[Reference]

- https://medium.com/developers-keep-learning/twitter-snowflake-approach-is-cool-3156f78017cb