머리말

대규모 시스템 설계 기초 관련 책을 읽고 있다. 정확한 이름은 <가상 면접 사례로 배우는 대규모 시스템 설계 기초>이다. 틈틈히 읽고 있는 중인데, 7장에서 흥미로운 주제가 나왔다.

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

아쉽게도, 지금껏 내가 운영하고 경험한 서비스에서 유일한 ID를 생성하는 것은 대부분 단순했다. Application 단에서 UUID 라이브러리를 이용해 임의의 값을 생성하거나, Database에서 제공하는 auto_increment를 적용하는 수준에 그쳤다. Oracle의 경우엔 sequence를 이용했다.

---

핵심은 ‘분산’

유일한 ID를 생성하는 것은 맞는데, 여기서 중요한 키워드는 ‘분산’이다. ID 생성기가 n개 이상일 경우엔 그 사이에서 충돌이 일어나지 않을 것을 보장해야 하고, 1개일 경우엔 SPOF(Single Point Of Failure, 시스템 구성 요소 중에서, 동작하지 않으면 전체 시스템이 중단되는 요소를 의미)가 되는 점에 주의할 필요가 있다.

요구사항

자, 그럼 책에서 요구한 구체적인 내용을 확인해보자. 먼저 기본적으로 분산 시스템이며, 당연하게도 ID는 유일해야 한다. 이런 기본적인 사항을 제외하고, 추가적인 요구사항이 뭐가 있는지 보자.

1. ID는 숫자로만 구성해야 한다.

2. ID는 64비트로 표현될 수 있어야 한다.

3. ID는 발급 시간에 따라 정렬할 수 있어야 한다.

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

위 4가지 요구사항을 잘 기억하고, 이어서 다음 내용을 보겠다.

---

생성기 유형

이번에는 어떤 유형의 생성기가 있는지 알아보자. 책에서는 분산 시스템에 적절한 방안으로 아래 4가지의 유형을 제시하고 있다.

1. 다중 마스터 복제

2. UUID

3. 티켓 서버

4. snowflake 기법

이 외에 다른 방안은 없는지, 나의 든든한 AI 군단과 상의(?)했지만 대부분의 답변은 비슷했고, 명칭만 다를 뿐 대부분의 접근법이 위 4가지 범주에 속하는 것으로 확인했다.

(1) 다중 마스터 복제

보통은 DB에서 auto_increment 기능을 활용한다. 이 항목 역시 같은 내용인데, 분산 시스템에 걸맞게 ‘다중’이란 키워드가 붙어있다. ID를 생성하는 DB를 2대 이상 둔 경우이며, 각각의 DB가 생성하는 ID의 다음 값은 이전 값에서 1씩 증가하는 게 아니라, n만큼 증가하는 방식이다. 여기서 n은 DB의 개수다.

이 방식은 ID 생성기의 규모를 확장할 수 있으며, 초당 10,000개의 ID를 생성해야 하는 요구사항도 준수할 수 있을 것이다. 다만, 정확히 시간에 따라 값이 증가하는 형태는 아니므로 세 번째 요구사항을 준수하지 못한다.

(2) UUID

UUID는 값의 충돌 가능성이 극단적으로 희박한 ID 체계다. UUID에 대해서 일반적으로 알려진 표현에 따르면 다음과 같다.

1개의 중복 UUID가 생길 확률이 50%가 되려면, 매초 10억 개의 UUID를 100년 동안 생성해야 한다.

막말로 사막에서 바늘 찾기와 같은 수준이다. 어쩌면 그보다 더 어려울 지도 모르겠다.

우주에서 지구와 똑같이 생긴 행성을 찾는 수준이 아닐까?

자, 그럼 UUID를 이용하면 되겠다. 유일한 ID를 생성하고, 그로 인해 분산 시스템의 동기화를 고려할 필요도 없을 테니까 말이다. 그럼 문제 해결인가?

아니다. UUID는 요구사항 1, 2, 3번을 모두 준수하지 못한다.

첫 번째, UUID는 숫자와 문자가 포함된 구성이다.
두 번째, UUID는 128비트다.
세 번째, UUID를 시간 순으로 정렬할 수 없다.

UUID는 유일한 ID를 생성하기 쉽게 해주는 마법 같은 솔루션이다. 하지만 이와 같이 요구사항이 몇 개만 추가되어도 사용할 수 없게 된다. 역시 개발에 있어서 은탄환(Silver Bullet)은 없다.

(3) 티켓 서버

다음은 다시 Database의 auto_increment 기능을 이용한 접근법이다. 유일 ID를 생성하기 위한 티켓 발급 DB 서버를 두는 것이다. 유일한 ID를 생성하며, 숫자로만 구성할 수 있고, 정렬할 수 있도록 구현하기 쉽다.

하지만, 치명적인 단점이 하나 있다. 한 대의 서버를 두는 만큼 이 구조에서는 티켓 서버가 SPOF가 된다. 이를 회피하기 위해서 서버를 여러 대 두게 되면, ID 생성기(티켓 서버) 간의 동기화를 다시 고민해야 한다.

또 다시 동기화를 회피 하려거든 첫 번째 방법이었던 (1) 다중 마스터 복제를 채택하게 될텐데, 이는 모든 요구사항을 준수하지 못하는 결과였다는 것을 이미 확인했다.

(4) Snowflake 기법

snowflake 기법? 접근법? 전략? 다양한 표현이 있을 것 같다. 아무튼 트위터(현 ‘X’)는 이런 상황을 해결하기 위해 눈송이(snowflake) 기법을 고안했다. 근데 왜 눈송이지?

"모든 눈송이는 고유한 구조를 가진다"는 널리 알려진 믿음에서 따온 것이다. (wikipedia)

지금까지 알아본 기법(또는 전략)들은 ID를 생성하는 행위를 하나의 개체가 책임지도록 했다. 눈송이(snowflake) 기법은 ID를 생성하는, 아니 ID를 구성하는 부분을 여러 절로 나누는 방법이다. 은탄환(Silver Bullet)은 없지만, 분할 정복(Divide and conquer)은 있다. 아래는 64비트를 구성하는 snowflake 형태의 ID 구조다.

책에 있던 그림 속 구조를 그대로 표현해봤다. 여기서 중요한 것은 41비트가 할당된 타임스탬프, 그리고 각각 5비트씩 할당된 데이터센터 ID와 서버 ID일 것이다. 사실 구조만 봐도 어떤 것인지 바로 감이 온다. 무릎을 탁

타임스탬프의 값을 통해 생성된 시간을 알 수 있을 것이며, 시간 순 정렬의 요구사항을 준수할 수 있다. 41비트이므로 약 69년의 시간을 저장할 수 있다. 일반적인 서비스에서는 충분히 긴 시간이며, 그럼에도 불구하고 그 이상을 서비스하게 된다면, 기준 시점(epoch)을 새로 설정하면 더 사용할 수 있을 것이다.

데이터센터와 서버의 ID를 추가함으로써 분산 시스템에서의 중복을 방지할 수 있다. 각각 5비트이므로 32개의 데이터센터와 각 데이터센터당 32개의 서버를 지원할 수 있게 된다. 즉, 분산된 ID 생성기 간에 충돌이 일어날 수 있는 상황을 방지한다. 웬만큼 큰 규모의 서비스라도 대부분 감당할 수 있는 수준이 아닐까?

일련번호에 할당된 12비트는 동시성을 위한 것으로, 한 서버에서 같은 시간(밀리초) 동안 하나 이상의 ID를 생성하는 경우에만 0보다 큰 값을 갖게 된다고 한다. 밀리초당 4096(12비트)의 숫자를 가질 수 있으므로, 초당 최대 409만 개의 ID를 생성해도 중복되지 않는다.

위 내용을 종합해 보면 최초의 요구사항 4가지를 모두 준수한다. 64비트 숫자로 구성되며, 시간 순 정렬이 가능하고, 1초당 10,000개 생성이라는 요구사항을 훨씬 웃돈다.

만약 동시성이 트위터만큼이나 높지 않은 서비스이고, 키가 유효한 기간을 더 길게 가져가고 싶다면 타임스탬프의 비트를 늘리고, 일련번호 비트를 줄이는 방법도 있을 것이다. 아니면 데이터센터와 서버 ID의 비트를 줄여도 될 것이다. 우리가 항상 트위터(X)만큼 큰 서비스를 만드는 것은 아니니까, 언제나 트레이드 오프(trade-off)를 고려하도록 하자.

---

정리

자, 이렇게 아래 4가지 요구사항에 따른 유일 ID 생성기의 설계를 알아봤다.

1. ID는 숫자로만 구성해야 한다.

2. ID는 64비트로 표현될 수 있어야 한다.

3. ID는 발급 시간에 따라 정렬할 수 있어야 한다.

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

DB를 활용한 ID 발급이나, UUID를 이용한 접근법 모두 좋은 방법이다. 다만 위처럼 까다로운 조건이 붙었을 경우에는 snowflake와 같은 방법이 적합할 것이다.

반면, 숫자로 구성해야 할 필요가 없고, 길이나 정렬의 요구사항이 없다면 UUID를 이용하는 것이 훨씬 나은 방법일 것이다. snowflake를 적용하기 위한 구현과 운영 측면에서 비용이 발생할 것이기 때문이다. 또한 분산된 시스템 간의 시계 동기화는 아직 언급하지도 않았다. 이런 점을 고려하면 현재 시스템에서 필요한 요구사항에 비해서 snowflake는 오버엔지니어링이 아닐지 다시 한번 생각해봐야 한다.

얕은 고찰 🤔

그렇다면 snowflake를 사용하지 않는 방법. UUID를 사용하되 정렬을 하고싶을 때는 어떻게 하면 좋을까?

(1) 타임스탬프 + UUID

이 방법은 타임스탬프 값을 통한 시간 정렬과 UUID를 이용한 유일성을 보장한다. 구현도 간단하며, 분산 시스템에서의 중복 발생의 여지도 (극단적으로 낮은 확률로) 없다.

단점도 있다. 길이가 길어지므로 저장 공간이 더 필요할 것이며, 같은 밀리초 내에 발생한 ID 내에서의 순서는 보장되지 않는다. 이어 소개할 2가지 모두 그렇다.

(2) UUID v7

2022년에 표준이 된 UUID이다. 지금까지 설명한 UUID는 대부분 v4다. 이는 타임스탬프 기반이라 시간으로 정렬이 가능하다. UUID의 표준 길이를 가지고 있으므로 앞선 방법(1)에 비해 길이도 짧다.

가장 간단한 방법이긴 하나, 비교적 새로운 표준이므로 기존의 레거시 시스템과 통합하기 어려울 가능성이 있다.

(3) ULID

2016년에 등장한 표준. 역시 타임스탬프를 가지고 있어 시간 정렬이 가능하다.

하지만, UUID v7과 마찬가지로 기존 라이브러리 지원이 제한적이거나, 기존 레거시 시스템과의 통합이 어려울 수 있다.

(4) 돌고 돌아 snowflake

위 3가지 방안 모두 같은 밀리초 내에서의 순서를 보장할 수 없다. 같은 밀리초 내의 일련번호를 따로 저장하는 snowflake만 이 경우를 해결할 수 있다. 아직까지는?

다만, 밀리초 내 순서를 반드시(굳이?) 보장해야 하는 시스템이 아니라면, 타임스탬프를 활용하거나 타임스탬프가 포함된 UUID 체계를 채택하면 충분할 것이다.