가상면접 사례로 배우는 대규모 시스템 설계 기초(7) - 분산 시스템을 위한 유일 ID 생성기 설계
7장 분산 시스템을 위한 유일 ID 생성기 설계
Mar 30, 2024
분산 시스템에서 사용될 유일 ID 생성기를 굳이 할 필요성을 느끼지 못할 수도 있다. 일반적인 관계형 데이터베이스의 경우, auto_increment 속성이 설정된 key를 사용하는 대중적인 사용방식이 있기 때문이다.
하지만, 분산 환경에서 이런 안일한 발상은 위험할 수 있다.
1단계 문제 이해 및 설계 범위 확정
시스템서 설계 면접에서 문제를 푸는 첫 단계는 적절한 질문을 통해 모호함을 없애고 설계 방향을 정리하는 것이다.
면접장에서 ID를 설계할 일은 쉽사리 접하기 어렵겠지만 만약 요구사항이 들어온다면 다음과 같을 순 있겠다.
- ID는 유일해야 한다.
- ID는 숫자로만 구성되야 한다.
- ID는 64비트로 표현될 수 있는 값이어야 한다.
- 저장 용량을 절약할 수 있다.
- 데이터 전송 효율이 더 좋다.
- 인덱싱 성능을 향상 할 수 있다. 더 많은 레코드를 동일한 양의 캐시에 저장할 수 있기 때문에 인덱스 성능이 향상될 수 있습니다.
- 가독성이 좋다.
왜 128비트가 아닌, 64비트를 사용해야 하는가도 중요하다고 생각한다. 인스타그램은 과거(2012년)에 기술 블로그에서 ID는 이상적으로 64비트여야 한다고 했다. 왜 64비트일까?
- ID는 발급 날짜에 따라 정렬 가능해야 한다.
- 초당 10,000개의 ID를 만들 수 있어야 한다.
만약 위와 같은 조건의 설계 요구사항에 대한 문제를 해결해야 한다.
2단계 개략적 설계안 제시 및 동의 구하기
정렬 가능한 기준을 생각한다면 순서대로 늘어나는 auto-increment나 timestamp같은 날짜 값이나 혹은 uuid, ulid를 생각할 수 있다.
일반적인 관계형 데이터베이스에서 사용하는 auto-increment 값은 유일하고 숫자로 구성되고… 64비트고… 어쩌고 저쩌고 하지만, 발급 날짜에 따라 정렬 가능하진 않다.
그렇다면 날짜 값을 숫자로 바꾼 unix time이나 epoch time혹은 타임 스탬프를 사용하면 날짜 값에 따라 정렬될 순 있지만 중복을 막을 수는 없을 것이다.
그렇다면 uuid와 ulid는 어떨까,
uuid를 사용하면 중복문제는 거의 발생하지 않으니 충족한다고 치지만 숫자로 구성되지도 않으며 64비트보다 더 크고 정렬도 불가능하다. ulid는 시간과 임의성을 기반으로 생성되며 중복문제가 해결되고 발급 날짜에 따라 정렬이 가능하지만 64비트 이상이며 숫자로만 구성되진 않는다.
일반적 id를 생성하는 방법들 몇 가지를 살펴봤지만, 주제애 해당되진 않는다.
이제 책 내용을 살펴보면,
분산 시스템에서 유일성이 보장되는 ID를 만드는 방법은 여러가지로, 다음과 같은 선택지가 있다.
- 다중 마스터 복제
- UUID
- 티켓 서버
- 트위터 스노플레이크 접근법
다중 마스터 복제
이 접근법은 데이터베이스의 auto_increment 기능을 활용하는 것이다. 다만 ID 값을 구할 때 1만큼 증가시켜 얻는 것이 아닌, k만큼 증가시킨다. k는 현재 사용중인 데이터베이스 수를 의미한다.
이 방법은 다음과 같은 중대한 단점이 있다.
- 데이터 센터 간 물리적 거리나 네트워크 지연 등의 문제로 동기화가 어려워 여러 데이터 센터에 걸쳐 규모를 늘리기 어렵다.
- ID의 유일성은 보장되지만, 그 값이 시간의 흐름에 맞출 수는 없다.
- 서버를 추가하거나 삭제할 때 잘 동작하도록 만들기 어렵다.
UUID
UUID는 유일성이 보장되는 또 하나의 간단한 방법이다. 128비트 수로서, 중복 UUID가 생길 확률을 50%로 끌어올리기 위해선 초당 10억개의 UUID를 100년동안 만들어야 할 정도로 중복가능성이 낮다.
Pros
- 단순하다.
- 규모 확장이 쉽다.
Cons
- 64비트 이상으로 길다.
- 시계열로 정렬할 수 없다.
- 숫자가 아닌 값이 포함될 수 있다.
티켓 서버
티켓서버 또한 유일성이 보장되는 ID를 만든 방법 중 하나로서, 플리커는 분산 기본 키를 만들어내기 위해 이 기술을 이용했다.
이 아이디어의 핵심은 auto_increment 기능을 갖춘 데이터베이스 서버, 즉 auto_increment 기능이 있는 하나의 서버로 id를 관리하는 티켓 서버로 운영한다는 것이다.
Pros
- 유일성이 보장되는 숫자로만 구성된 ID를 쉽게 만들 수 있다.
- 구현하기 쉽고, 중소 규모 Application에 적합하다.
Cons
- 티켓 서버가 SPOF가 될 수 있다. 이 서버에 장애가 발생하면 모든 시스템이 영향을 받게된다. 이렇게 되면 티켓 서버를 여러대 운영해야 하는데 그렇다면 원래 티켓 서버를 운영하는 본 목적에도 맞지 않고 동기화 문제도 발생하게 된다.
트위터 스노플레이크 접근법
여태까지는 모든 요구사항을 충족하는 방법은 없었다.
트위터는 스노플레이크라는 ID 기법을 사용하고 있다. 이 신기한 기법은 모든 요구사항을 충족시킬 수 있다.
스노 플레이크 방법은, 생성해야 하는 ID의 구조를 여러 section으로 나눠 생성하는 것이다. 각 절의 쓰임새는 다음과 같다.
- 사인 비트 : 1비트를 할당한다. 음수와 양수를 구분하는데 사용될 수 있다.
- 타임스탬프 : 41비트를 할당한다. epoch 이후로 몇 밀리초 경과 했는지의 시계열 값을 숫자로서 표현될 값이다.
- 데이터센터 ID : 5비트를 할당한다. 따라서 2^5 = 32개 데이터센터를 지원할 수 있다.
- 서버 ID : 5비트를 할당한다. 따라서 데이터 센터당 32개의 서버를 운용할 수 있다.
- 일련번호 : 12비트를 할당한다. 각 서버에서 ID를 생성할 때마다 이 값을 1씩 증가시킨다. 1 밀리초가 경과할 때마다 0으로 초기화된다.
3단계 상세 설계
1비트의 사인 값이나 데이터 센터 서버 ID는 넘어가고, 타임스탬프부터 살펴보면
타임스탬프
스노 플레이크에서 타임스탬프는 가장 큰 41자리를 차지하고 있다. 타임 스탬프는 시간의 흐름에 따라 값이 점점 커지기 때문에 시계열로 정렬이 가능하다.
위 사진은 타임스탬프를 통해 이진 표현 형태로 UTC 시간을 추출하는 방법이다. 이 방법을 역으로 적용하면 어떤 UTC 시간도 상술한 타임스탬프 값으로 변환할 수 있다.
41비트로 표현할 수 있는 최대 타임스탬프 값은 2^41 - 1 = 2999023225551 밀리초로서 69년이다. 따라서 트위터 기원 시각을 기준으로 69년 동안만 정상작동하기 때문에, 69년 뒤에는 기원 시각을 변경하거나 다른 기준을 사용해야 한다.
일련번호
일련번호는 12비트기 때문에, 2^12 = 4096개의 값을 가질 수 있다. 특정 서버가 같은 밀리초 동안 하나 이상의 ID를 만들어 낸 경우에만 0보다 큰 값을 갖게 된다.
4단계 마무리
스노 플레이크 방식을 선택한건 제안된 모든 요구사항을 충족했기 때문이다. 추가적으로 살펴볼만한 주제는,
- 시계 동기화: 만약 하나의 서버가 여러 코어에서 실행될 경우 같은 시계가 아닐 수도 있다. 혹은 서버가 완전히 물리적으로 독립된 여러 곳에서 실행되는 경우도 같은 시계가 아닐 것이다. 이런 경우 해결책으로서 네트워크 타임 프로토콜이 존재한다.
- 네트워크 타임 프로토콜
네트워크 타임 프로토콜 줄여서 NTP의 핵심은 NTP 서버이다. NTP 서버는 UTC로 나타내는 시간 정보를 전송해준다. 전송시 걸리는 시간만큼 정확히 예상하여 보정한 값을 보내줘야 하기 때문에 보정이 매우 중요하다.
- 스노우 플레이크 각 섹션의 최적화: 동시성이 낮고 수명이 긴 Application이라면 일련번호의 길이를 줄이고 타임스탬플 절의 길이를 늘리는 것이 효율적일 수 있다.
Share article
