[시스템디자인] Unique ID Generator in Distributed Systems

Overview

분산 시스템 환경에서의 Unique Id Generator 시스템을 설계하는 기법에 대해 알아보자.

• 그냥 데이터 추가 될 때 마다 auto_increment로 id 생성하면 안 되나? -> 안 된다.
  • 일단 single database server에 large data 다 담을 수 없음
  • multiple database server를 넘나들며 최소한의 delay로 unique id를 만드는게 어려움

분산 시스템 환경의 db에서 구현해야하는 unique id와 generator system의 특징은 다음과 같다.

• ID는 Unique(고유한) 값이여야 한다.
• ID는 numerical value로 나타낸다.
• ID는 64-bit 안에 들어온다.
• ID는 날짜로 정렬이 된다. -> 시간에 따라 증가
• 초당 만 개가 넘는 unique id를 생성하는 ability

분산 시스템 환경에서 unique id를 생성할 때 사용할 수 있는 옵션들은 다음과 같다.

• Multi-master replication
• Universally unique identifier (UUID)
• Ticket server
• Twitter snowflake approach

Multi-master replication

server의 개수를 단위수로 해서 auto_increment하는 방식.

아래 예시에서는 사용하는 서버가 2개이기 때문에 각각의 서버에서 unique id가 2씩 auto increment로 생성된다.

[server1] 1, 3, 5 ...
[server2] 2, 4, 6 ...

장점

• 간단함

약점 및 한계점

• 여러개의 데이터 센터로 확장하기 어려움
• ID가 여러 서버를 걸쳐 시간에 따라 증가하지 않음
• 서버가 추가되거나 제거될 때 조정할 수 없다.

Universally unique identifier (UUID)

UUID는 128-bit로 정보를 나타내는 방식이다.
각각의 웹서버들이 하나의 ID generator를 가지고 있으며, 독립적으로 id generating을 책임진다.

장점

• 서버 간의 데이터 sync이슈가 발생하지 않음 -> 간단함
• ID 충돌나기 어려움
• 각각의 웹서버가 각각의 id generator를 담당하기 때문에 스케일 조정이 쉽다.

약점 및 한계점

• 128-bit 너무 길다.
• 시간에 따라 증가하지 않는다.
• 수치값이 아니다.

Ticket server

single database server에서 여러개의 서버에 대한 unique id generating을 담당하는 중앙 집중화 방식, auto_increment 방식 사용.

장점

• 수치값
• 구현이 쉽다

약점 및 한계점

• single point of failure. 티켓 서버가 다운되면 모든 서버에 이슈 발생.
• 그럼 multiple ticket server를 만들면 되잖아? -> 이번엔 새롭게 data sync 문제를 해결해야함

Twitter snowflake approach

64-bit의 id를 여러 개의 sections으로 쪼개어 표현하는 방식.

• Sign bit: 항상 0. 미래에 signed, unsigned number를 구분해야할 때 쓸 수 있을 듯
• Timestamp: 41 bits. epoch time으로 나타냄
• Datacenter id: 5 bits. 2^5개의 데이터 센터까지 커버 가능
• Machine id: 5 bits. 데이터센터마다 각각 2^5개의 머신까지 커버 가능
• Sequence number: 12 bits. machine/process에서 생성되는 모든 ID, 1씩 증가함

Datacenter ID, Machine ID는 startup time에 정해짐. 이후 변경하면 id conflict 발생할 수 있으니 주의 필요함.
Timestamp, Sequence number는 ID generator가 실행되면서 생성됨.

Timestamp

• Binary -> 십진법으로 변환 -> Twitter epoch를 더해줌 (밀리세컨드 단위) -> UTC time으로 변환
• timestamp는 최대 41 bits로 나타낼 수 있는데, 41 bits로 나타낼 수 있는 최대의 밀리세컨드를 변환하면 69년 정도이다.
• 따라서 69년 이후에는 새로운 epoch time으로 마이그레이션 해줘야함

Sequence number

• sequence number는 같은 서버에서 동시에(같은 밀리세컨드) ID가 생성되지 않는 이상 0이다.
• 이론상 machine은 밀리세컨드 당 최대 4096개의 id를 커버할 수 있다.

---

해당 게시물은 Alex Xu의 SYSTEM DESIGN INTERVIEW, Chap7. DESIGN A UNIQUE ID GENERATOR IN DISTRIBUTED SYSTEMS를 읽고 정리한 글입니다.