Skip to content

juneyr.dev

유일한 ID 생성기 설계 by 가상면접사례로 보는 시스템 설계 기초

SystemDesign4 min read

서론

블로그 쓰기를 급하게 준비하려고 최근 궁금했던 디스코드는 어떻게 수조개의 메시지를 다룰까요 블로그를 보다가 snowflake 를 알게 되었다. snowflake 는 트위터에서 제안한 유니크한 id 생성기로, 분산시스템 상에서 id 생성을 위해서 주로 사용된다.

생각해보니 전 프로젝트들의 id 생성 방식이 이와 유사한 방식을 띄고 있었고 그 이유를 정확히 알지는 못했다. 그러니 유니크한 id 생성기가 따로 필요한 이유와 설계 방식까지 간단하게 공부해본다.

왜 auto_increment 안해요?

관계형 데이터베이스를 사용하기만해도 auto increment 를 사용하면 sql 데이터베이스의 내부적인 테이블에 따라서 하나씩 증가하는 키가 생성된다. 간단한 시스템에서는 잘 통하는 방법이고, 메인 데이터베이스가 단일 관계형 데이터베이스라면 괜찮을지도 모른다.

다만 이런 접근법은 분산 환경에서는 바로 깨져버리고 만다. 여러 데이터베이스 서버를 쓸 정도로 시스템의 요구량이 높은 경우,

1) 한대에서 auto increment 로 키를 만들어서 전달한다. -> 한대로는 요구를 감당하기 어려울 가능성이 높다. 2) 만약 전달이 가능하다고 해도 delay가 어마어마할 확률이 높다. 한대에서 여러대로 해당 key를 전파해야하기때문..

따라서 어떤 데이터베이스 서버에서도 생성할 수 있지만, 유니크한 조합이 보장되는 키 생성기가 필요하게 된다.

정렬이 되고, 밤에 만든 키가 낮에 만든 키보다는 확실히 큰, 유일한 숫자 키

책에서 주어진 조건은 다음과 같다.

  • 64 bit 의 숫자 키
  • 시간에 따라 커짐
  • 정렬 가능

책에서는 4가지 접근방법을 소개하고 있다.

  • 다중 마스터 복제
  • UUID
  • 티켓 서버
  • 트위터 스노우플레이크 접근법

다중 마스터 복제

multi

다중 마스터 복제는 데이터베이스의 auto_increment 방식을 활용하는 것이다. 다만, 다음번에 정해지는 id 의 값을 구할 때 1만큼 올리는게 아니라 k만큼 증가시킨다. k는 현재 사용하고 있는 데이터베이스 서버의 수가 되겠다. 이렇게 하면 규모에 따른 확장성 문제를 어느 정도 해결할 수 있는데, 마스터가 여러개인 만큼 초당 생성가능한 ID 의 갯수도 늘릴 수 있기때문이다.

하지만 이 방법은 다음과 같은 큰 단점이 있다.

  • 여러 데이터 센터에 걸쳐서 규모를 늘리기는 어렵다. (분산환경 만족 안됨)
  • ID의 유일성은 보장되겠지만, 그 값이 시간 흐름에 맞추어 커지도록 보장할 수는 없다.
    • 예를 들어, #1 번의 3번 id가 시간 상으로 #2 번의 6번 보다 이후에 만들어진 레코드 일 수도 있다.
  • 서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어렵다.

UUID

중복되지 않는다는 조건만 생각하면 UUID 가 생각나기도 한다. UUID 는 범용 고유 식별자 (universally unique identifier) 로, 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128 bit 자리 수다. 충돌의 가능성이 거의 없어서 사실상 고유 식별자로 인정되고 있다. 표준형식에서 UUID 는 32개의 십육진수로 표현되는 값이다. e.g) 550e8400-e29b-41d4-a716-446655440000

시간값, 랜덤값, 노드의 id 등으로 구성되고 있고 갯수로는 2의 128 제곱, 약 340간 2,823구 의 값이라고 한다.

uuid

장점

  • UUID 만드는 방식이 정해져 있으므로 간단하다. 서버 사이의 조율도 필요없다.
  • 각 서버가 자기가 쓸 ID를 알아서 만들면 되므로 규모 확장도 쉽다.

단점

  • ID가 128비트로 길고 무겁다.
  • ID를 시간순으로 정렬할 수 없다.
  • ID에 숫자가 아닌 값이 포함될 수 있다. (표준방식에는 - 가 들어감)

티켓 서버

티켓 서버는 유일성이 보장되는 ID를 만들어내는 흥미로운 방법 중 하나다. Flickr 는 분산 기본 키를 만들어내기 위해서 이 방식을 사용했다고 한다.

ticket

이 아이디어의 핵심은 auto increment 기능을 갖춘 티켓 서버를 중앙 집중형으로 하나만 사용하는 것이다. 이 티켓 서버는 id 생성만을 위한 기능을 가진다. 그래서 table schema 자체를 id와 관련된 것으로 생성해서 관리하고 있다. 아래는 플리커 블로그 포스트에서 따온 예시.

장점

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

단점

  • 티켓 서버 자체가 SPOF (Single Point of Failure) 가 된다. 이 서버에 장애가 발생하면, 해당 서버를 이용하는 모든 시스템이 영향을 받는다. 이를 피하려고 티켓 서버를 증설하면, 이번엔 동기화가 문제가 된다.

플리커의 블로그 포스트 에 따르면 플리커는 이 문제를 해결하기 위해서 티켓서버를 두개로 나눠서 관리했다. 그리고 실제로는 다중 마스터 복제 방식처럼, auto-increment 하는 수를 1이 아닌 2로 책정했다. 따라서 하나의 서버에서는 홀수만, 다른 서버에서는 짝수만 하도록 설정한 것으로 보인다. 그리고 이 티켓서버로의 요청은 라운드로빈으로 처리했다.

트위터 스노우플레이크식 접근법

트위터는 스노우플레이크(snowflake)라고 불리는 독창적인 ID 생성 기법을 사용한다. 이 기법은 책에서의 요구사항을 만족시킬 수 있다.

snowflake

snowflake 와 유사한 방식으로 접근해보자. 주어진 64bit 를 다음과 같이 쪼개본다.

  • 사인(sign) 비트 : 1비트를 할당해서 양수 / 음수를 할당한다. 지금은 딱히 쓰이지 않는다.
  • 타임스탬프 비트: 41비트를 할당한다. epoch milliseconds 를 저장할 값이다. 책에서 공유된 설계안에서는 트위터 스노우플레이크 구현에서 사용하는 값 1288834974657 를 사용한다. (2010년 11월 4일, 01:42:54 UTC)
  • 데이터 센터 ID: 5비트를 할당한다. 따라서 2의 5제곱인 32개의 데이터 센터를 지원한다.
  • 서버 ID : 5비트를 할당한다. 따라서 32개의 데이터 센터 당 각각 32개의 서버를 지원한다.
  • 일련번호 : 12비트를 할당한다. 각 서버에서는 ID를 생성할 때마다 이 일련번호를 증가시킨다. 이 값은 1ms 가 지날 때마다 0으로 초기화한다.

위 ID 구성 중 데이터 센터ID와 서버 ID는 시스템이 시작할 때 결정되며, 일반적으로 시스템 운영중에는 바뀌지 않는다.

타임스탬프

타임스탬프는 절대적으로 긴 값인 41 비트를 차지하게 된다. 타임스탬프는 시간의 흐름에 따라서 점점 큰 값을 갖게되므로, 결국 ID는 시간순으로 정렬가능하게 될 것이다. 41비트로 표현할 수 있는 타임스탬프의 최대값은 2의 41승 - 1 = 2199023255551 밀리초 (~ 69년정도) 에 해당한다.

따라서 이 ID 생성기는 69년동안만 정상동작한다. 트위터에서는 기준시각을 위에서 공유한 1288834974657 (2010년 11월 4일, 01:42:54 UTC) 로 맞춰서 오버플로우가 발생하는 시점을 뒤로 늦춰놓은 것이다. 즉 어림잡아 2079년에는 이 생성기를 교체해야한다.

기준시각이 있고 타임스탬프가 있으므로 이 ID가 언제 생성되었는지 유추하는것 또한 가능하다. 타임스탬프의 41bit가 책에서 공유된 다음 값이라고 해보자.

101110010111010000111011011010100110111 은 십진수로 398259500343 이고 이에 트위터 기원시각(epoch) 를 더하면 1687094475000 다. 이 값은 최종 epoch ms 이므로 이를 UTC 로 변경하면 2023년 June 18일 Sunday PM 1:21:15 가 된다.

일련번호

일련번호는 12비트이므로 2^12 = 4096개의 값을 가질 수 있다. 어떤 서버가 같은 ms 동안 한개 이상의 값을 가질때만 0보다 큰 값을 갖게된다.

더 고려해야하는 점

  • 시계 동기화 : 위에서는 ID 생성 서버들이 모두 같은 시계를 사용한다고 가정했다. 하지만 이런 가정은 하나의 서버가 여러 코어에서 실행될 경우 유효하지 않을 수 있다. 물리적으로 독립된 여러 장비에서 실행될 때도 마찬가지다. 이를 해결하기 위해서는 NTP(Network Time Protocol) 이 흔히 사용된다고 한다.

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

  • 각 절의 길이: 위 snowflake 방식에서 팀의 프로젝트 환경에 따라 절의 길이는 조정이 필요할 것 같다. 예를 들어 데이터 센터가 많지 않지만, 서버가 많은 경우 데이터 센터 절을 줄이고 서버 절을 늘릴 수 있을 것이다. 그리고 동시성이 낮고 수명이 긴 애플리케이션이라면 일련번호의 절을 줄이고 타임스탬프 부분을 늘릴수도 있겠다.

참고