[System Design Interview] 07. 분산 시스템 환경에서의 고유 유일 ID 값 생성하기 (feat UUID)

가상 면접 사례로 배우는 대규모 시스템 설계 기초 (System Design Interview) - 저 : 알렉스 쉬, 역 : 이병준 을 읽고 정리한 글입니다.

 

7장에서는 분산환경에서의 유일 ID 생성기를 설계하는 방법에대해서 다룹니다.

보통 MySQL 같은 RDB 를 위주로 사용하는 저(?) 같은 사람은 유일 ID로 'auto_increment' 를 생각하는데 분산환경에서는 이러한 접근법이 통하지 않습니다.

분산환경에서 'auto_increment'가 통하지 않는 이유는, 보통 데이터베이스 1대만 사용하지 않는  것은 물론이고 여러 데이터베이스 서버를 쓰는 경우에는 지연시간을 낮추기가 무척 힘들기 때문이라고 합니다.

그렇기 때문에 이번 글에서 유일성이 보장되는 ID 설계방법을 정리해봅니다.

 

 

[목차]

1. 다중 마스터 복제(multi-master replication)
2. UUID (Universally Unique Identifier)
3. 티켓 서버 (ticket server)
4. 트위터 스노플레이크 (twitter snowflake) 접근법

 

 

---

📌 01. 다중 마스터 복제

 multi master replicateion 은 기본적으로 auto_increment를 사용합니다.

다중 마스터 복제 방법은, auto_increment 를 사용하지만 다음 ID 값을 +1 증가시켜 얻는게 아닌 +n 값을 증가시킵니다. 여기서 n 은 현재 사용중인 데이터베이스 서버의 개수입니다.

이렇게 하면 어느 정도의 규모 확장성 문제를 어느 정도 해결할 수 있지만, 몆가지 단점이 존재합니다.

 

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

1. 여러 데이터 센터에 걸쳐 규모를 늘리기 어렵다.
2. ID 의 유일성은 보장되지만 그 값이 시간 흐름에 맞추어 커지도록 보장할 수 없다.
3. 서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어렵다.

 

---

📌 02. UUID

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

 

UUID 는 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트짜리 수 이며 아래와 같은 구조로 이루어집니다.

구조	길이 (바이트 /비트)	내용
Low Time	4 / 8 (8자리)	시간의 low 32비트를 부여하는 정수
Mid time	2 / 4 (4자리)	시간의 middle 16비트를 부여하는 정수
Mid time + version	2 / 4 (4자리)	최상위 비트에서 4비트 "version", 그리고 시간의 high 12비트
Clock sequence and variant	2 / 4 (4자리)	최상위 비트에서 1-3비트는 UUID의 레이아웃형식, 그리고 13-15비트 클럭 시퀀스
Node	6 / 12 (12자리)	48비트 노드 id

 

구조를 쓱 보면, 완전히 유일한 키는 아닙니다. 중복된 UUID 키가 우연히 발생할 수 있는 구조이고 이를 UUID 의 충돌이라고 합니다. 위키피디아를 인용하면, "1개의 UUID 충돌 확률을 50%로 끌어올리기 위해서는 초당 10억개의 UUID 를 100년간 계속 만들어야 한다" 고 합니다.

즉 지극히 낮습니다.

→ 참고로 저는, 주로 UUID 를 사용할 때 생성날짜 + UUID 를 사용합니다, 원래도 중복확률이 낮지만 더 안전하게 사용하기 위한 의도를 가졌습니다.

 

UUID 장점

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

UUID 단점

1. ID 가 128비트로 길다
2. ID 를 시간순으로 정렬할 수 없다.
3. ID 에 숫자가 아닌 값이 포함될 수 있다.

 

---

📌 03. 티켓 서버 (ticket server)

티켓서버는 유일성이 보장되는 ID를 만들어 내는데 쓰일 수 있는 또 하나의 흥미로운 방법이고, 플리커(Flickr)는 분산 기본 키를 만들어 내기 위해 이 기술을 이용하였다고 합니다.

티켓 서버는 위의 그림과 같이 auto_increment 기능을 갖춘 데이터베이스 서버, 즉 티켓 서버를 중앙 집중형으로 하나만 사용하는 것입니다.

 

티켓서버 장점

1. 유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있습니다.
2. 구현하기 쉽고, 중소 규모 어플리케이션에 적합합니다.

 

티켓서버 단점

1. 티켓 서버가 SPOF(Single-Point-of-Failure)가 됩니다.
   이 서버에 장애가 발생했을 때 해당 서버를 이용하는 모든 시스템이 영향을 받습니다. 이 문제를 해결하기 위해서는 티켓서버를 여러대 두어야하는데, 이때는 데이터 동기화 같은 문제가 새롭게 발생합니다.

 

---

📌 04. 트위터의 스노플레이크(snowflake) 접근법

트위터는 스노플레이크(snowflake)라고 부르는 독창적인 ID 생성 기법을 사용합니다. 이 방버으로 생성된 키는 숫자로 이루어졌고, 64비트이며, 생성순으로 정렬이 가능합니다.

 

스노플레이크 접근법은 생성해야 하는 ID 구조를 여러 절(section)로 분할하는 분할정복을 적용했습니다. 

각 절에대한 할당은 다음과 같습니다.

• 사인(sign) 비트 : 1비트를 할당한다. 지금으로서는 쓰임새가 없지만 나중을 위해 유보해 둔다. 음수와 양수를 구별하는 데 사용할 수 있을 것이다.
• 타임스탬프 : 41비트를 할당한다. 기원 시각(epoch) 이후로 몇 밀리초가 경과햇는지를 나타내는 값이다. 본 설계안의 경우에는 기원 시각으로 트위터 스노플레이크 구현에서 사용하는 값 1288834974657(Nov 04, 2010, 01:42:54 UTC에 해당)을 이용할 것이다.
  • 41비트로 표현할 수 있는 타임스탬프의 최대값은 241 - 1 = 2199023255551 밀리초로, 69년에 해당합니다.
  • 즉 해당 ID값은 69년간만 유효하며, 69년이 지나면 기원 시각을 바꾸거나 ID 체계를 다른 것으로 이전해야 합니다.
• 데이터센터 ID: 5비트를 할당한다. 따라서 25 = 32개 데이터센터를 지원할 수 있다.
• 서버 ID : 5비트를 할당한다. 따라서 데이터센터당 32개 서버를 사용할 수 있다.
• 일련번호 : 12비트를 할당한다. 각 서버에서는 ID를 생성할 때마다 이 일련번호를 1만큼 증가시킨다. 이 값은 1밀리초가 경과할 때마다 0으로 초기화 된다.