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

가상 면접 사례로 배우는 대규모 시스템 설계 기초 – System Design Interview

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

---

어떻게 유일 ID 생성기를 설계할 것인가.

단일 서버라면 auto_increment 속성을 설정해도 좋을 것이다.
그러나 분산 시스템에서는 문제가 달라지게 된다.

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

이번 장에서 만족해야할 요구사항는 다음과 같다.
- ID는 유일해야 한다.
- ID는 64비트로 표현될 수 있는 값이어야 한다.
- ID는 발급 날짜에 따라 정렬 가능해야 한다.
- 초당 10,000개의 ID를 만들 수 있어야 한다.

* 참고
여기서 64비트는 8바이트 이고
이는 Mysql을 기준으로 생각해보았을 때 bigint 타입이다.
https://dev.mysql.com/doc/refman/8.0/en/integer-types.html

 

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

분산 시스템에서 유일성이 보장되는 ID를 만드는 대표적인 방법은 다음과 같다.
- 다중 마스터 복제(multi-master replication)
- UUID(Universally Unique Identifier)
- 티켓 서버(ticket server)
- 트위터 스노플레이크(snowflake) 접근법

 

각 방법에 대해 알아보고 요구사항을 충족하는지 확인해 볼 것이다.

 

다중 마스터 복제

데이터 베이스의 auto_increment 기능을 활용한다. 다만 다음 ID의 값을 구할 때 증가시켜 얻는것이 아니라 k 만큼 증가시킨다. (여기서 k는 사용 중인 데이터베이스 서버의 수다.)

 

db1 : 1 + k -> 1, 1+k, 1+2k, 1+3k
db2 : 2 + k -> 2, 2+k, 2+2k, 2+3k
db3 : 3 + k -> 3, 3+k, 3+2k, 3+3k
…
dbk : k + k -> 2k, 3k, 4k, 5k

 

장점

단순한 방법을 통해 ID의 유일성을 보장하면서 규모 확장성 문제를 어느정도 해결할 수 있다.

 

단점

여러 데이터 센터에 걸쳐 규모를 늘리기 어렵다.
ID를 시간순으로 정렬할 수 없다.
서버를 추가하거나 삭제할 때 처리가 복잡하다.

 

* 참고
실제로 Mysql에서 구현하려면 아래와 같이 increment 증가 값을 변경할 수 있다고 한다.
특정 테이블에서만 증가 값을 변경하는 것은 불가능 하다고 하며
특정 테이블에서만 증가 값을 핸들링 하고 싶다면 trigger 같은 것을 통해서 핸들링 해야한다고 한다.

-- AUTO_INCREMENT 값을 k로 설정 SET @@auto_increment_increment=k;

 

UUID(Universally Unique Identifier)

UUID는 유일성이 보장되는 ID를 만드는 또 하나의 간단한 방법이다.

 

UUID는 128 비트 이며, 충돌 가능성이 지극히 낮다.

위키피디아에 따르면 중복 UUID가 1개 생길 확률을 50%로 끌어올리려면 초당 10억 개의 UUID를 100년 동안 연속해서 만들어야 한다고 한다.

https://en.wikipedia.org/wiki/Universally_unique_identifier

 

장점

서버 사이의 조율이 필요 없으므로 동기화 이슈가 없다.
각 서버가 자기가 쓸 ID를 알아서 만드는 구조이므로 규모 확장이 쉽다.

 

단점

ID가 128비트로 길다. ( = 애초에 요구사항에 충족하지 않는다. )
ID를 시간순으로 정렬할 수 없다.
ID에 숫자가 아닌 값이 포함될 수 있다.

 

* 참고
128비트 는 16 바이트이다.

 

티켓 서버(ticket server)

티켓 서버를 중앙 집중형으로 사용하는 컨셉이다. (대표적으로 플리커에서 이 방식을 이용하여 시스템을 구축한 히스토리가 있다고 한다.)

 

장점

유일성이 보장되면서 오직 숫자로만 구성된 ID를 쉽게 만들 수 있다.
ID를 시간순으로 정렬할 수 있다.
구현하기 쉽다. 따라서 중소 규모 애플리케이션에 적합하다.

 

단점

티켓 서버가 SPOF(Single-Point-of-Failure)가 된다.
이 이슈를 피하려면 여러 대의 티켓 서버를 구축해야하는데 그렇게 하면 데이터 동기화 이슈가 발생된다.

 

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

스노플레이크는 트위터에서 공개한 ID 생성 기법이다.

위에서 살펴본 방식들 중에서 제대로 요구사항을 충족하는 방식은 없었다. 그러나 이 방식은 충족할 수 있다.

 

각 부분에 대해 살펴보면 다음과 같다.

사인(Sign) 비트: 1비트. 지금은 쓰임새가 없다. 나중을 위해 유보해둔 비트
타임스탬프(timestamp): 41비트를 할당한다. 기원 시간 이후 몇 밀리초(millisecond)가 경과했는지를 나타내는 값이다. 이에 대해서는 상세 설계에서 더 자세히 다룬다.
데이터센터 ID: 5비트를 할당한다. 따라서 32개의 데이터 센터를 지원할 수 있다.
서버 ID: 5비트를 할당한다. 따라서 데이터 센터당 32개의 서버를 지원할 수 있다.
일련번호: 12비트를 할당한다. 각 서버에서 ID를 생성할 때마다 이 일련 번호를 1만큼 증가시킨다. 이 값은 1밀리초가 경과할 때마다 0으로 초기화 한다.

3단계 상세 설계

각 부분의 길이 (비트 수) 는 조절이 가능하다.

데이터센터ID와 서버ID는 시스템이 시작할 때 결정되면 된다. 이 과정에서 충돌이 생기지 않도록 주의해야 한다.

타임스탬프

초기 UNIX 시스템 개발 과정에서 시간 기준을 정해야 했고  1970년 1월 1일 일 기준으로 잡았다.
일반적으로 이야기 하는 timestamp는 이 일자를 기준으로 몇 밀리초 만큼 지났는지를 나타내는 값이다.

하지만 이 값을 다 DB에 반영할 필요는 없다. 사용 가능한 비트가 제한되어있기 때문에 최대한 데이터를 담아내야 한다. 이를 위해 별도의 기원시간을 둔다.

 

책의 예시를 그대로 활용해서 설명을 하면 아래와 같다.

(javascript가 가장 익숙하므로 javascript를 기준으로 설명해본다.)

 

// 1. 현재의 timestamp를 구한다.
let now = new Date();
console.log(now.getTime());
// 1685988380030

// 기원 시간을 뺀다.
// 트위터 기원 시간은 2010-11-04T01:42:54.657Z (1288834974657) 이다.
// 시스템에 맞게 다시 재설정 하면 더 많은 데이터를 사용 가능할 것이다.
let diff = now.getTime() - 1288834974657;
console.log(diff)
// 397153405373

// 해당 값을 2진수로 변환하여 타임스탬프 부분에 넣는다.
console.log(diff.toString(2));
// 101110001111000001100000000100110111101

참고로 41비트로 표현할 수 있는 시간은 약 69년이다.
2^41 - 1 (2,199,023,255,551) / 1000 (밀리초) / 3600 (초) / 24 (시간) / 365 (일) = 69.73057

일련번호

일련번호는 2^12 (4096) 개의 값을 가질 수 있다.

 

4단계 마무리

면접관과 추가로 논의할 수 있는 부분

- 시계 동기화(clock synchronization) : 각각의 서버는 시간을 동기화를 해야 한다. 일반적으로 NTP를 사용한다.

- 각 부분의 길이 최적화 : 필요에 따라 각 부분의 비트를 조절할 수 있다. 69년보다 더 긴 수명이 필요하다면 타임스탬프의 비트수를 늘릴 수 있을 것이다.

- 고가용성: ID 생성기는 필수 불가결 컴포넌트이므로 높은 가용성을 제공해야 한다.

---

- 고가용성에 대해서는 스노플레이크의 경우 각 어플리케이션 서버에 담길 부분이라고 생각했는데 왜 따로 언급을 했는지 의문이다. 별도의 생성 서버를 두는 걸 고려한 것 같은데 왜 그래야 하는지 잘 모르겠다. 32x32를 넘어설 정도로 서버의 수가 많기 때문에 그런걸까?

 

- 위 내용에서 각 방법의 장단점 을 보면 ID를 시간순으로 정렬할 수 없다. 있다. 이 부분에 대한 언급들이 나와 있다. 이 부분을 언급한 이유는 무엇일까? 아마 그 이유는 생성순으로 데이터들이 정렬되었을 때 DB 튜닝에 유리하기 때문일 것이다. 순차적인 키 값은 인덱스의 리프 노드를 효율적으로 탐색하는 데 유리하기 때문이다. 이에 대해서 추후에 정리할 기회가 있으면 정리해보겠다.

 

- 참고로 Firebase Realtime Database 에서 push 시에 생성되는 key 값도 동시성을 갖추도록 설계되어있다. (생성 알고리즘은 공개되지 않았다 함.) 

 

진짜 fin.