분산 시스템을 위한 유일 ID 생성기를 설계 해보라!
이런 질문을 받았다면 요구사항을 이해하고 모호함을 해소하는데 초점을 맞추어야 한다.
면접관과의 QnA를 통해 ID 체계나 ID생성기에 대한 특성을 파악하자
1단계 문제 이해 및 설계 범위 확정
요구사항은 다음과 같다
•
ID는 유일해야 한다.
•
ID는 숫자로만 구성되어야 한다.
•
ID는 64비트로 표현될 수 있는 값이어야 한다.
•
ID는 발급 날짜에 따라 정렬 가능해야 한다.
•
초당 10,000개의 ID를 만들 수 있어야 한다.
2단계 개략적 설계안 제시 및 동의 구하기
방법은 여러가지가 있지만 우리는 다음과 같은 선택지를 살펴 볼 것이다.
•
다중 마스터 복제(multi-master replication)
•
UUID(Universally Unique Identifier)
•
티켓 서버(ticket server)
•
트위터 스노우플레이크(twitter snowflake) 접근법
다중 마스터 복제(multi-master replication)
이 접근법은 데이터베이스의 auto_increment 기능을 활용하는 것이다.
단, 1만큼 증가시켜 얻는것이 아니라 K(Primary DB의 수) 만큼 증가시키는 것이다.
예를들어 Primary DB가 3대가 있다고 해보자.
(k = 3)
1번 DB의 PK > 0, 3, 6, 9, ...
2번 DB의 PK > 1, 4, 7, 10, ...
3번 DB의 PK > 2, 5, 8, 11, ...
JavaScript
복사
이렇게 하면 ID끼리의 충돌없이 유일한 ID를 얻을 수 있다.
하지만 다음과 같은 중대한 단점이 있다.
•
유일성은 보장되지만 그 값이 시간 흐름에 맞추어 커지도록 보장할 수 없다.
•
여러 데이터 센터에 걸쳐 규모를 늘리기 어렵다.
•
서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어렵다.
→ 즉, 단순 증가값이기 때문에 시간 흐름이 보장되지 않으며
→ 최초 생성할 때의 데이터베이스 수에서 변경이 일어난다면 기존 k값으로 생성된 ID나 생성될 ID를 관리하기가 매우 힘들 것이다.
MySQL의 경우 auto_increment_increment 의 값을 변경하여 증가값을 제어할 수 있다.
mysql> SHOW VARIABLES LIKE 'auto_inc%';
+--------------------------+-------+
| Variable_name | Value |
+--------------------------+-------+
| auto_increment_increment | 1 |
| auto_increment_offset | 1 |
+--------------------------+-------+
2 rows in set (0.00 sec)
UUID(Universally Unique Identifier)
유일성이 보장되는 ID를 만드는 또 하나의 간단한 방법이다.
UUID는 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트짜리 수다.
UUID는 32개의 십육진수로 표현되며 총 36개 문자(32개 문자와 4개의 하이픈)로 된 8-4-4-4-12라는 5개의 그룹을 하이픈으로 구분한다. (위키피디아)
UUID값이 충돌할 확률을 50%로 끌어 올리려면 초당 10억 개의 UUID를 100년동안 계속해서 만들어야 한다.
이 방법은 방식도 간단하고, 동기화 이슈도 없어 매우 간단하다.
또한 각 서버가 자기가 쓸 ID를 알아서 만드는 구조이므로 규모 확장도 쉽다.
하지만 다음과 같은 단점이 있다.
→ ID가 128비트로 길다
→ ID를 시간순으로 정렬할 수 없다.
→ ID에 숫자가 아닌 값이 포함될 수 있다.
티켓 서버(ticket server)
이 아이디어의 핵심은 auto_increment 기능을 갖춘 데이터베이스 서버, 즉 티켓 서버를 중앙 집중형으로 하나만 사용하는 것이다.
이 방법은 유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있다.
또한 구현하기 쉽고, 중소 규모 애플리케이션에 적합하다.
하지만 아래와 같은 문제점이 있다.
→ 티켓 서버 자체가 SPOF(Single Point Of Failure)가 된다
→ 이슈를 피하기위해 다중화를 고려한다면 이때는 동기화 같은 새로운 문제에 직면한다.
티켓 서버 : 저렴한 분산형 고유 키
Flickr(플리커)는 2004년 2월부터 운영되고 있는 온라인 사진 공유 서비스이다.
플리커에서 티켓 서버는 하나의 데이터베이스가 있는 전용 데이터베이스 서버이며 32비트 ID를 위한 Tickets32 테이블과 64비트 ID를 위한 Tickets64 테이블이 있다. Tickets64 테이블 스키마는 다음과 같다.
CREATE TABLE `Tickets64` (
`id` bigint(20) unsigned NOT NULL auto_increment,
`stub` char(1) NOT NULL default '',
PRIMARY KEY (`id`),
UNIQUE KEY `stub` (`stub`)
) ENGINE=InnoDB
SQL
복사
64비트 아이디가 필요할 때면 다음과 같은 쿼리를 수행한다고 한다
REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();
SQL
복사
REPLACE INTO의 경우 중복인 경우 기존 같은 값을 가지는 new row를 삽입하고, 기존 old row를 삭제한다.
이 과정에서 auto_increment 값이 증가하게된다.
비슷한 구문으로 INSERT ... ON DUPLICATE KEY UPDATE Statement 가 있다.
이 구문은 REPLACE INTO 와 다르게 중복인 경우 중복 컬럼에 대해서 update가 발생하는데, auto-increment 컬럼이 존재한다면 auto_increment 값을 증가시킨다.
플리커에서 사용하고자하는 목적에 대해서는 같은 기능을한다고 보면 된다.
LAST_INSERT_ID ?SELECT LAST_INSERT_ID
SQL
복사
써본적은 없지만 구글링을 해보니 현재까지도 종종 쓰는 경우가 많은 듯 하다.
구글링하다보니 알게된 주의점(?)이 있다.
바로, ‘성공적으로 삽입된 첫번째 auto_increment 값’을 반환한다는 점이다
INSERT INTO table_name(col1) VALUES (’row1’),(’row2’),(’row3’); 과 같은 Multiple Values Insert Query를 사용한다면 auto_increment의 값이 3이길 기대하겠지만 실제로는 1을 반환한다.
같은 예시로
INSERT INTO table_name(col1) VALUE(’row1’);
INSERT INTO table_name(col1) VALUE(’row2’);
INSERT INTO table_name(col1) VALUE(’row3’);
이렇게 3개의 INSERT를 실행한다면 3을 반환한다.
트위터 스노우플레이크(twitter snowflake) 접근법
생성해야하는 ID의 구조를 여러 절(section)으로 분할하여 독창적인 ID 생성 기법을 활용하는 방법이다.
각 절의 쓰임새를 살펴보면 다음과 같다
•
사인(sign) 비트
◦
1 비트를 할당한다.
◦
당장은 쓰임새가 없지만 나중을 위해 유보해둔다.
◦
음수와 양수를 구별하는데 사용할 수 있을 수 있다.
•
타임스탬프(timestamp)
◦
41비트를 할당한다.
◦
기원 시각(epoch) 이후로 몇 밀리초가 경과했는지를 나타내는 값이다.
◦
트위터 스노플레이크 구현에서 사용하는 값 1288834974657(Nov 04, 2010, 01:42:54 UTC)를 이용할 것이다.
•
데이터센터 ID
◦
5비트를 할당한다.
◦
따라서 32개의 데이터센터를 지원할 수 있다.
•
서버 ID
◦
5비트를 할당한다.
◦
따라서 데이터센터 당 32개 서버를 사용할 수 있다.
•
일련번호
◦
12비트를 할당한다.
◦
각 서버에서는 ID를 생성할 때마다 이 일련번호를 1만큼 증가시킨다.
◦
이 값은 1밀로초가 경과할 때마다 0으로 초기화 된다.
실제 Twitter의 Snowflake의 ID 체계처음 41비트는 선택한 epoch 이후의 밀리초를 나타내는 타임스탬프 입니다.
다음 10비트는 컴퓨터 ID를 나타내며 충돌을 방지합니다.
12비트 이상의 추가 비트는 동일한 밀리초 내에 여러 Snowflake를 생성할 수 있도록 시스템당 시퀀스 번호를 나타냅니다.
3단계 상세 설계
여러 방법 중 트위터 스노우플레이크 접근법을 사용한다면 구현 가능할듯 하다.
이 방법을 선택해서 좀 더 상세한 설계를 진행해보자.
데이터 센터ID와 서버ID는 시스템이 시작할 때 결정되며, 일반적으로 시스템이 운영 중에는 바뀌지 않는다.
타임스탬프는 41비트를 차지하고 있다.
시간이 흐름에 따라 점점 큰 값을 갖게 되므로, 시간순 정렬이 가능하다
41 비트로 표현할 수 있는 최대값은 약 69년에 해당한다.
69년이 지나면 ID 체계를 다른것으로 마이그레이션하거나, 기원 시각(epoch)를 변경해야 할 것이다.
40~42비트가 표현할 수 있는 최대 값 그리고 밀리초 변환 시간일련번호는 12비트이므로 4096개의 값을 가질 수 있다.
어떤 서버가 같은 밀리초 동안 하나 이상의 ID를 만들어 낸 경우에만 0보다 큰 값을 갖게된다.
초당 10,000개의 ID를 만들 수 있어야 한다라는 요구사항을 충족하고도 훨씬 남는다.
4단계 마무리
유일성이 보장되는 ID 생성기 구현에 쓰일 수 있는 다양한 전략 중 다중 마스터 복제, UUID, 티켓 서버, 트위터 스노플레이크 네 가지 방법을 살펴 보았다
우리가 선택한 방식은 스노플레이크인데, 모든 요구사항을 만족하면서도 분산 환경에서 규모 확장이 가능했기 때문이다.
설계를 진행하고 시간이 조금 남았다면 면접관과 다음을 추가로 논의할 수 도 있을 것이다.
•
시계 동기화(clock synchronization)
◦
이번 설계에서는 우리 ID 생성 서버들이 전부 같은 시계를 사용한다고 가정하였다.
◦
하나의 서버가 여러 코어에서 실행되는 경우나 물리적으로 독립된 장비에서 실행되는 경우에 시간이 다를 수 있다.
◦
그런 문제가 있다는 점을 알아두고 이 문제를 해결하려면 NTP(Network Time Protocol)을 살펴보라.
•
각 절(section)의 길이 최적화
◦
동시성이 낮고 수명이 긴 어플리케이션이라면 일련번호에 할당한 비트를 줄이고 타임스탬프의 절에 비트를 더 할당하는것이 더 효과적일 수 있다.
•
고가용성
◦
ID 생성기는 필수 불가결 컴포넌트이므로 아주 높은 가용성을 제공해야 할 것이다.