개발 공부 기록하기/20. 일반

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

lannstark 2021. 11. 25. 12:41

분산 시스템에서 사용될 유일 ID 생성기

요구사항

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

 

선택지

다중 마스터 복제

특징

  • DB의 auto increment 기능을 활용하는 것이다. 다만 다음 ID를 구할 때 1만큼 증가시키지 않고 k 만큼 증가시킨다.
  • 간단하게 적용할 수 있는 방식이고, 한 데이터 센터에서 어느정도 확장도 가능하다

단점

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

 

UUID

특징

  • 128비트의 UUID를 활용. 서버간의 조율 없이 독립적으로 생산 가능하다

장점

  • 단순하다. 동기화 이슈도 없다. 규모 확장도 용이하다

단점

  • 128비트로 용량이 조금 크다 (요구사항에서는 64비트로 제한이 걸려 있다)
  • ID를 시간순으로 정렬할 수 없다.
  • ID에 숫자가 아닌 값이 포함될 수 있다.

 

티켓 서버

특징

  • 다중 마스터 복제와 유사하게 DB의 auto increment를 활용하지만 application server로 wrapping 하는 방법

장점

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

단점

  • 티켓 서버가 SPOF가 된다

 

트위터 snowflake

특징

  • 64비트 내에서 적절한 비트 단위로 정보를 기록하는 기법

각 비트의 쓰임새는 다음과 같다.

  • 1비트 - 사인비트, 쓰임새가 현재는 없지만 나중을 위해 유보. 음수 양수를 구분할 수 있을 것이다
  • 41비트 - 타임스탬프, 기원 시각 이후 millisecond 단위로 값을 표현한다. 총 41비트 이므로 약 69년을 cover할 수 있고 기원 시각 이후 69년이 지나면 migration 또는 기원시각 조정이 필요하다
  • 5비트 - 데이터 센터 ID로 총 32개의 데이터 센터를 지원할 수 있다
  • 5비트 - 서버 ID, 한 데이터 센터당 32개의 서버를 지원할 수 있다.
  • 12비트 - 일련번호 - 각 서버에서는 ID를 생성할 때마다 일련번호를 1만큼 증가시키고, 이 값은 1밀리초 기준으로 0으로 초기화 시킨다 (그러면 타임스탬프가 바뀌게 되어 구분할 수 있다)

(예전에 System Programing에서 하던 비트 쪼개기가 여기서 또..!)

추가적으로 얘기할 주제

  • 시계 동기화
    • ID 생성 서버들은 OS 타임이 동기화되어 있어야 한다.
    • NTP(Network Time Protocol)은 이 문제를 해결하는 가장 보편적인 수단이다.
  • Application의 특징에 따라 snowflake의 비트를 조절할 수 있다