[대규모 시스템 설계 기초] 07. 분산 시스템을 위한 유일 ID 생성기 설계

in Devlog on Book, Study



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

  • 분산환경에서 DB의 auto_increment는 사용할 수 없다.
    1. 데이터베이스 서버 한대로는 트래픽을 감당할 수 없다.
    2. 여러 DB 서버를 사용한다면 지연시간을 낮추기가 힘들다.

1단계. 문제 이해 및 설계 범위 확정

  • ID는 유일해야 한다.
  • ID는 숫자로만 구성되어야 한다.
  • ID는 64비트로 표현될 수 있는 값이어야 한다.
  • ID는 발급날짜에 따라 정렬가능해야한다.
  • 초당 10,000개의 ID를 만들 수 있어야한다.

2단계. 개략적 설계안 제시 및 동의 구하기

분산시스템에서 유일성이 보장되는 ID를 만드는 방법은 다음과 같다.

  • 다중 마스터 복제(multi-master replication)
  • UUID
  • 티켓 서버
  • 트위터 스노플레이크(twitter snowflake) 접근법

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

image-20231103162104433

  • DB의 auto_increment 기능을 활용하는 것.
    • 다만 다음 ID의 값을 구할 때 1만큼 증가시키는게 아니라 k만큼 증가시킨다. k는 사용중인 데이터베이스 서버의 수다.

장점

  • DB 수를 늘리면 초당 생산가능 ID수를 늘릴 수 있다.

단점

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

UUID

  • 유일하게 식별할 수 있는 128비트짜리 수.
  • 충돌 가능성이 지극히 낮다. (중복 UUID 생성 1개 확률을 50%로 끌어올리려면 초당 10억개의 UUID를 100년동안 만들어야한다.)
  • 09c93e62-50b4-468d-bf8a-c007e1040bfb2 와 같은 형태를 띔.
  • 서버간 조율 없이 독립적으로 생성 가능하다.

image-20231103162542788

장점

  • 생성이 단순하다.
  • 서버 사이의 조율이 필요없어 동기화 이슈가 없다.
  • 각 서버가 ID를 만드는 구조라 규모 확장도 쉽다.

단점

  • ID가 128비트로 길다. (이번 문제의 요구사항은 64비트다.)
  • ID를 시간순으로 정렬할 수 없다.
  • ID에 숫자가 아닌 값이 포함될 수 있다.

티켓 서버

image-20231103162720234

  • auto_increment 기능을 가진 DB서버(티켓 서버)를 중앙 집중형으로 하나만 사용하는 것.

장점

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

단점

  • 티켓 서버가 SPOF가 된다.
    • 이 문제를 피하려면 서버를 여러대 준비해야하나, 데이터 동기화 같은 새로운 문제가 발생한다.

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

image-20231103162926830

  • 사인(sign) 비트
    • 1비트를 할당.
    • 지금은 쓸모 없지만 나중을 위해 유보해둠. 대체적으로 음수와 양수를 구별하는데 사용할 수 있을 것이다.
  • 타임스탬프
    • 41비트를 할당.
    • 기원 시각(epoch) 이후의 밀리초 경과를 나타내는 값.
  • 데이터 센터
    • 5비트를 할당.
    • 2^5 = 32개 데이터 센터를 지원할 수 있다.
  • 서버 ID
    • 5비트를 할당.
    • 데이터 센터당 2^5 = 32개 서버를 사용할 수 있다.
  • 일련번호
    • 12비트를 할당.
    • 각 서버에서는 ID 생성시 이 일련번호를 1만큼 증가시키고, 이 값은 1밀리초가 경과할 때마다 0으로 초기화 됨.

3단계. 상세 설계

스노플레이크 접근법이 사용하기 좋아보인다. 해당 방식으로 상세설계를 진행한다.

타임스탬프

image-20231103163845253

  • 시간의 흐름에 따라 점점 큰 값을 갖게 되어 시간 순으로 정렬 가능하다.
  • 최대값은 대략 69년에 해당하기 때문에, 이 ID 생성기는 69년동안만 정상 동작한다.
    • 이후에는 기원 시각을 바꾸거나 ID 체계를 다른것으로 이전하여야 한다.

일련번호

  • 2^12 = 4096개의 값을 가질 수 있다.
  • 서버가 같은 밀리초동안 하나 이상의 ID를 만들어 낸 경우에만 0보다 큰 값을 갖게 된다.

4단계. 마무리

결국 스노플레이크 접근법으로 선택하게 되었다.

시간이 남는다면 아래 사항을 논의할 수 있다.

  • 시계 동기화 (clock synchronization)
    • ID 생성기 서버가 동일한 시계를 사용하지 않을 때 NTP(Network Time Protocol)을 사용하여 문제를 해결할 수 있다.
  • 각 절(section)의 길이 최적화
    • 동시성(concurrency)가 낮고, 수명이 긴 애플리케이션이라면 일련번호 절의 길이를 줄이고 타임스탬프 절의 길이를 늘리는것이 효과적일 수 있다.
  • 고가용성
    • ID 생성기는 필수 불가결 컴포넌트이므로 아주 높은 가용성을 제공해야 한다.

© 2019. by mintheon

Powered by mintheon