[면접 스터디] 개념정리: 7. 분산 시스템을 위한 유일 ID 생성기 설계

단일 시스템에서의 유일 ID 생성은 쉽다. auto_increment 와 같이 단순하게 설계 가능하다.

하지만 분산 시스템에서는 증분을 서로 동기화 시켜야한다는 점에서 어렵다.

분산 시스템에서의 유일 ID 생성 전략은 다음과 같다.

• 다중 마스터 복제: auto_increment를 1 씩 하는게 아닌 DB서버 개수 만큼 증가시켜서 각 서버의 유일한 ID를 만드는 방식
  • 단점: 규모를 늘리거나 줄이기 어렵다(기존의 것이 겹침)
• UUID: 128비트 숫자와 문자를 사용한 유일한 ID 생성기. 겹칠 확률이 매우 적다. 또한 각 서버가 별도로 생성할 수 있어서 동기화 필요가 없다.
• 티켓 서버: auto_increment를 하는 역할을 맡은 서버를 별도로 두고 ID를 하나가 만드는 것
  • 장점: 유일성 보장 쉽고, 구현이 쉽다.
  • 단점: 이 서버가 SPOF가 될 수 있다.
• 트위터 스노우플레이크 접근법: 64비트 정수 기반의 전역 유일 ID 생성기이다. 시간 정렬 가능하고 충돌 없이 빠르게 생성할 수 있는 분산 ID 시스템

요구사항 파악

ID 유일 성

64비트 정수 타입

날짜 정렬 가능

다음과 같은 요구사항을 만족하는 전략은 트위터 스노우플레이크 전략이다.

조금 더 자세하게 알아보겠다.

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

64비트 정수 기반의 전역 유일 ID 생성기이다. 시간 정렬 가능하고 충돌 없이 빠르게 생성할 수 있는 분산 ID 시스템

64비트 ID 구조

1비트 41비트 10비트 12비트

사용 안함

타임스탬프(ms)

데이터센터ID + 머신ID

시퀀스 번호

• 사인 비트: 1 비트 할당. 지금으로서는 쓰임새는 없지만 음수 양수 구분 가능
• 타임스탬프: 41비트 할당. 특정 기준 시점(epoch)부터 경과한 밀리초(69년치 밀리초 표현가능)
• 데이터센터ID: 5비트 할당. 32개의 데이터센터
• 서버ID: 5비트 할당. 32개의 서버
• 일련번호: 12비트 할당. 각 서버가 ID 생성할 때마다 1씩 증가 1밀리초 경과 시 0으로 초기화 즉 1밀리초에 생성할 수 있는게 4096개

마무리

유일성이 보장되는 ID 생성기 구현에 쓰일 수 있는 다양한 전략을 알아봤다.

면접 요구사항에 맞는 건 트위터 스노우플레이크 방식이었다.

다음과 같은 걸 추가 고려해볼 수 있을 것이다.

• 시계 동기화: 각 서버는 같은 시간을 사용해야한다. 여기서는 그게 된다고 가정했지만 쉬운 것은 아니다. 보편적으로 이 문제를 해결하는 방식은 NTP이다.
• 각 절의 길이 최적화: 64비트를 적절히 조절할 수 있을 것이다. 동시성이 낮은 경우 타임스탬프를 늘리는 등의 방식으로
• 고가용성: ID 생성기는 필수불가결 이게 다운되면 동작을 멈출 수 있음 그렇기에 높은 고가용성을 보장해야한다.

추가) NTP(Network Time Protocol)란

네트워크 상에서 서버들의 시간을 정확히 동기화하기 위한 프로토콜

동기화 과정

타임스탬프 설명

T1	클라이언트가 요청을 보낸 시각
T2	서버가 요청을 받은 시각
T3	서버가 응답을 보낸 시각
T4	클라이언트가 응답을 받은 시각

왕복 시간(RTT): (T4 - T1) - (T3 - T2)

시간 차(offset): ((T2 - T1) + (T3 - T4)) / 2

이 오프셋을 이용해 클라이언트는 자신의 시스템 시간을 조정함