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

가상 면접 사례로 배우는 대규모 시스템 설계 기초 "분산 시스템을 위한 유일 ID 생성기 설계"을 요약한 내용입니다.

• 분산 시스템에서 사용될 유일ID 생성기를 설계 해보자
• auto_increment 속성은 분산 환경에서 사용하기가 어렵다
  • 서버 한대로 사용하지도 않고 지연시간을 낮추기가 무척 힘들 것이기 때문에

문제 이해 및 설계 범위 확정

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

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

• 분산 시스템에서 유일성이 보장되는 ID를 만드는 방법은 여러가지만 다음과 같은 선택지를 살펴보자
  • 다중 마스터 복제
  • UUID
  • 티켓 서버
  • 트위터 스노플레이크 접근방법

다중 마스터 복제

• 데이터베이스의 auto_increment 기능을 활용해 만든다
  • 다음 ID값을 구할때 1만큼 증가가 아닌 k만큼 증가시킨다.
  • k는 현재 사용중인 데이터베이스 서버의 수
• 규모 확정성 문제를 어느 정도 해결 가능
  • 데이터베이스 수를 늘리면 초당 생산 가능 ID 수도 늘릴수 있음
• 단점
  • 여러 데이터 센터에 걸쳐 규모를 늘리긴 어렵다
  • ID의 유일성은 보장되겠지만 그 값이 시간 흐름에 맞춰 커지도록 보장할 수는 없다.
  • 서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어려움

UUID

• UUID는 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트 수
• UUID 값은 충돌 가능성이 지극히 낮다
  • 위키피디아를 인용하면 중복 UUID 1개 생길 확률을 50%로 끌어 올리려면 초당 10억 개의 UUID를 100년동안 계속 만들어야 함
• UUID는 서버 간 조율 없이 독립적으로 생성 가능
• 웹서버는 별도의 ID 생성기를 사용해 독립적으로 ID를 만들어 낸다
• 장점
  • UUID를 만드는 것은 단순하다
  • 서버 사이에 조율이 필요 없으므로 동기화 이슈도 없음
  • 각 서버가 자기가 쓸 ID를 알아서 만드는 구조이므로 규모 확정도 쉽다.
• 단점
  • ID가 128비트로 길다
    • 요구사항에 따라 사용하기 어려울수 있음
  • ID를 시간순으로 정렬할 수 없다
  • ID에 숫자가 아닌 값이 포함될 수 있다.

티켓 서버

• auto_increment 기능을 갖춘 데이터베이스 서버(티켓 서버)를 중앙 집중으로 사용하는 것
• 장점
  • 유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있다.
  • 구현하기 쉽고, 중소 규모 애플리케이션에 적합
• 단점
  • 티켓 서버가 SPOE(Single Point of Failure)가 된다.
  • SPOE를 피하기 위해 티켓 서버를 여러 대 준비하면 동기화 같은 새로운 문제 발생

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

• 트위터 스노플레이크라고 부르는 독창적인 ID 생성 기법을 사용한다.
• 생성해야 하는 ID 구조를 여러 절로 분할하는 것
  • 사인(sing) 비트: 1비트를 할당하고 지금은 쓰임세가 없지만 나중을 위해 유보해 둔다.
  • 타임스템프: 41비트를 할당하고 기원 시각 이후로 몇밀리초가 경과했는지를 나타내는 값
  • 데이터센터 ID: 5비트를 할당하고 32개 데이터센터를 지원할 수 있다.
  • 서버 ID: 5비트를 할당하고 데이터센터당 32개 서버를 사용할 수 있다.
  • 일련번호: 12비트를 할당하고 각 서버에서는 ID를 생성할 때마다 이 일련번호를 1만큼 증가시킨다.
    • 이 값은 1밀리초가 경과할 때마다 0으로 초기화 됨

상세 설계

• 데이터센터 ID와 서버 ID는 시스템이 시작할 때 결정되며, 일반적으로 시스템 운영 중에는 바꾸지 않는다.
  • 데이터센터 ID나 서버 ID를 잘못 변경하게 되면 ID 충돌이 발생할 수 있으므로 그런 작업을 해야 할 때는 신중해야한다.

타임스템프

• ID 구조에서 가장 중요한 41비트를 차지하고 있다.
• ID는 시간순으로 정렬이 가능하게 될 것
• ID구조를 따르는 값의 이진 표현 형태로부터 UTC 시간을 추출하는 예제

• 41비트를 사용해 표현할 수 있는 최대값은 2의 41승 -1 밀리초이다
  • 대략 69년 사용 가능

일련번호

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

마무리

추가로 논의할 수 있는 부분

• 시계 동기화: ID 생성 서버들이 전부 같은 시계를 사용한다고 가정 하였음
  • 서버가 여러 코어에서 실행되는 경우 유효하지 않을 수 있음
  • 시계 동기화 방법으로 NTP(Network Time Protocol)을 이용하는 방법도 있음
• 각 절(section)의 길이 최적화: 동시성이 낮고 수명이 긴 애플리케이션이라면 일련번호를 줄이고 타임스템프를 늘리는 것도 효과적일 수 있음
• 고가용성: ID 생성기는 필수 불가격 컴포넌트 이므로 아주 높은 가용성을 제공해야함