Skip to content

juneyr.dev

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

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

참고