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

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

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

• 지원자 & 면접관
  • ID는 어떤 특성?
    → 유일, 정렬 가능
  • 새로운 레코드에 붙일 ID는 항상 1만큼 큰 값?
    → 같은 시간 흐름에 따라 커지지만, 언제나 1씩 증가한다고 할 수 없음. 확실한 것은 아침에 만든 ID보다는 저녁에 만든 ID가 큰 값을 가짐
  • ID는 숫자로만 구성?
    → Yes
  • 시스템 규모는 어느 정도?
    → 초당 10,000 ID 생성
• 요구사항을 이해하고 모호함을 해소하는데 초점

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

• 유일성이 보장되는 ID를 만드는 방법
  • 다중 마스터 복제 multi-master replication
  • UUID Universally Unique Identifier
  • 티켓 서버 ticket server
  • 트위터 스노플레이크 twitter snowflake 접근법

다중 마스터 복제

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

UUID

• 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128bit 숫자
  • ex. 09c93e62-50b4-468d-bf8a-c07e1040bfb2
• 충돌 가능성 ⬇️
• 서버 간 조율없이 독립적으로 생성 가능
  • 생성 단순: 각 서버가 자기가 쓸 ID를 알아서 만드는 구모
  • 동기화 이슈 X
• 단점
  • ID가 길다 (문제의 요구사항은 64비트)
  • 시간순으로 정렬 X
  • 숫자 아닌 값이 포함될 수 있음

티켓 서버

• Flicker는 분산 기본 키를 만들어 내기 위해 이 기술을 이용
• auto_increment 기능을 갖춘 데이터베이스 서버(티켓 서버)를 중앙 집중형으로 하나만 사용
• 유일성 보장되는 오직 숫자로만 구성된 ID 쉽게 만들 수 있음
• 구현 간단. 중소 규모 애플리케이션에 적합
• 단점
  • 티켓 서버가 SPOF
  • 이를 해결하기 위해 티켓 서버를 여러 대 준비하면 데이터 동기화 같은 새로운 문제가 발생

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

• divide and conquer
• 생성해야하는 ID의 구조를 여러 절로 분할
  • sign 비트 1bit
    • 당장은 쓰임새 X, 나중을 위해 유보
    • 음수, 양수 구별하는 데 사용
  • timestamp 41bit
    • 기원 시작(epoch) 이후 몇 ms 경과했는지
  • 데이터센터 ID 5bit
    • 2^5=32개의 데이터센터 지원 가능
  • 서버 ID 5bit
    • 데이터센터당 32개 서버 사용
  • 일련번호 12bit
    • 각 서버에서는 ID를 생성할 때마다 이 일련번호를 1만큼 증가시킴
    • 1ms가 경과할 때마다 0으로 reset

3. 3단계 상세 설계

타임스탬프

• 가장 중요한 41bit 차지
• 시간의 흐름에 따라 점점 큰 값을 갖게 됨
  • 41bit로 표현 가능한 타임스탬프의 최댓값 = 2^41 - 1 := 69년
  • 69년동안만 정상 동작
• 69년이 지나면 기원 시각을 바꾸거나 ID 체계를 다른 것으로 migration

일련 번호

• 12bit → 2^12 = 4096개
• 같은 밀리초 동안 하나 이상의 ID를 만들어 낸 경우에만 0보다 큰 값을 가짐

4. 4단계 마무리

면접관과 추가로 논의할 부분

• clock synchronization
  • ID 생성 서버들이 전부 같은 시계를 사용한다고 가정
  • but, 하나의 서버가 여러 코어에서 실행될 경우 유효하지 않을 수 있음
  • 여러 서버가 물리적으로 독립된 여러 장비에서 실행되는 경우도.
  • NTP(Network Time Protocol): 위 문제를 해결하는 보편적 수단
• 각 section 길이 최적화
  • ex. 동시성 ⬇️, 수명 ⬆️
    → 일련번호 절의 길이 줄이고 타임스탬프 절의 길이 늘리는 것이 효과적
• 고가용성 high availability
  • ID 생성기는 필수 불가결 컴포넌트
  • 아주 높은 가용성 제공 필요