[System Design Interview] 7장 분산 시스템을 위한 유일 ID 생성기 설계

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

요구사항

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

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

분산 시스템에서 유일성이 보장되는 ID를 만드는 방법

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

다중 마스터 복제

• 다중 마스터 복제 방법은 데이터베이스의 auto_increment 기능을 확용하는 것이다.
• 다만 다음 ID의 값을 구할 때 1만큼 증가시켜 얻는 것이 아니라, k만큼 증가시킨다. k는 현재 사용중인 데이터베이스 서버의 수다.
• 단점
  • 여러 데이터 센터에 걸쳐 규모를 늘리기 어렴다.
  • ID의 유일성은 보장되겠지만 그 값이 시간 흐름에 맞추어 커지도록 보장할 수는 없다.
  • 서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어렵다.

UUID

• UUID는 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트짜리 수다.
• UUID 값은 충돌 가능성이 지극히 낮다.
  • 중봅 UUID 1개 생길 확률을 50%로 끌어 올리려면 초당 10여 개의 UUID를  100년 동안 계속해서 만들어야 한다.

 

firue 7-3은 UUID를 사용하는 시스템 구조다. 위 구조에서 각  웹 서버는 별도의 ID 생성기를 사용해 독립적으로 ID를 만들어 낸다.

• 장점
  • UUID를 만드는 것은 단순하다. 서버 사이의 조율이 필요 없으므로 동기화 이슈도 없다.
  • 각 서버가 자기가 쓸 ID를 알아서 만드는 구조이므로 규모 확장도 없다.
• 단점
  • ID가 128비트로 길다. 이번 장에서 다루는 문제의 요구사항은 64비트다.
  • ID를 시간순으로 정렬할 수 없다.
  • ID에 숫자아닌 값이 포함될 수 있다.

티켓 서버

이 방법의 핵심은 auto_increment 기능을 갖춘 데이터베이스 서버를 중앙 집중형으로 하나만 사용하는 것이다.

• 장점
  • 유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있다.
  • 구현하기 쉽고, 중소 규모 애플리케이션에 적합하다.
• 단점
  • 티켓 서버가 SPOF(Single-Point-of-Failure)가 된다. 이 서버에 장애가 발생하면, 해당 서버를 이용하는 모든 시스템이 영향을 받는다.

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

• 사인 비트
  • 1비트를 할당한다.
  • 음수와 양수를 구별하는 데 사용할 수 있다.
• 타임스템프
  • 41비트를 할당한다.
  • 기원 시각 이후로 몇 밀리초가 경과했는지를 나타내는 값이다.
• 데이터센터 ID
  • 5비트를 할당한다. 32개 데이터센터를 지원할 수 있다.
• 서버 ID
  • 5비트를 할당한다. 데이터센터당 32개 서버를 사용할 수 있다.
• 일련번호
  • 12 비트를 할당한다.
  • 각 서버에서 ID를 생성할 때마다 이 일련번호를 1만큼 증가시킨다. 이 값은 1밀리초가 경과할 때마다 0으로 초기화 된다.

3단계 상세 설계

• 데이터센터 ID와 서버 ID는 시스템이 시작할 때 결정된다.
• 타임스템프나 일련번호는 ID 생성기가 돌고 있는 중에 만들어지는 값이다.

타임스탬프

• 타임스탬프는 시간이 흐름에 따라 점점 큰 값을 갖게 되므로, 결국 ID는 시간순으로 정렬 가능하게 된다.
• 타임스탬프의 최댓값은 2^41-1 = 2199023255551밀리초이다.

일련번호

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