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

 

분산 시스템에서 'auto_increment' 속성이 설정된 관계형 데이터베이스의 키는 사용이 어렵다.

=> 데이터베이스 서버 한 대로는 감당이 불가능하고, 지연 시간을 낮추기가 힘들다.

 

문제 이해 및 설계 범위

면접관에게 질문해서 파악한 설계 요구사항

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

 

유일 ID 생성

분산 시스템에서 유일성이 보장되는 ID를 만드는 방법

• 다중 마스터 복제(multi-master replication)
• UUID(Universally Unique Identifier)
• 티켓 서버
• 트위터 스노플레이크(twitter snowflake) 접근법

 

다중마스터 복제

 

특징

• auo_increment 기능을 활용한 접근법
• ID 값을 구할 때 1만큼 증가시키는 것이 아니라, K(서버 수)만큼 증가 시킨다.
• 해당서버가 생성한 이전 ID 값에 전체 서버의 수 K를 더한 값이다.

장점

• 규모 확장성 문제를 어느 정도 해결 가능
• 데이터베이스 수를 늘리면 초당 생산 가능 ID 수도 늘릴 수 있다,

단점

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

이미지 출처: https://ssdragon.tistory.com/162

UUID

특징

• 128비트짜리 수
• 중복 될 가능성이 낮다

 

장점

• UUID를 만드는 것은 단순하다. 서버 사이의 조율이 필요 없으므로 동기화 이슈도 없다.
• 각 서버가 자기가 쓸 ID를 알아서 만드는 구조이므로 규모 확장도 쉽다.

단점

• 128비트로 길다.
• 시간순으로 정렬할 수 없다.
• ID에 숫자가 아닌 값이 포함될 수 있다.

 

티켓서버

특징

• 플리커는 분산 기본키를 만들기 위해 해당 기술을 사용
• auto_increment 기능을 갖춘 데이터베이스 서버, 티켓 서버를 중앙 집중형으로 하나만 사용한 것

장점

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

단점

• 티켓 서버가 SPOF가 된다. 티켓 서버가 장애가 발생하면 모든 시스템이 영향을 받는다.

이미지 출처: https://ssdragon.tistory.com/162

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

 

특징

• ID 값을 분할정복(divide and conquer) 적용

64비트 분할

• 사인(sign): 1비트를 할당, 쓰임새가 없지만 나중을 위해 남겨 놓으며 음수와 양수를 구별하는데 사용할 수 있다.
• 타임스탬프(timestamp): 41비트를 할당한다. 기원 시각 이후로 몇 밀리초가 경과했는지를 나타내는 값
• 데이터센터ID: 5비트를 할당, 데이터센터를 지원한다.
• 서버 ID: 5비트를 할당, 32개 서버를 사용할 수 있다.
• 일련번호: 12비트 할당, 각 서버에서 ID를 생성할 때마다 일련 번호를 1만큼 증가. 1밀리초가 경과할 때마다 0으로 초기화 된다.

이미지 출처: https://ssdragon.tistory.com/162

 

상세 셜계

트위터 스노플레이크 접근법을 사용하여 상세 설계

 

타임스탬프

• 시간의 흐름에 따라 큰 값을 가지므로, 시간 순으로 정렬이 가능
• UTC 시각을 타임스탬프 값으로 변환할 수 있다.
• 2^41 -1= 2199023255551 밀리초. 대략 69년에 해당
• 즉, ID 생성기는 69년동안만 정상 동작

일련번호

• 2^12=4096 개의 값을 갖는다.
• 어떤 서버가 같은 밀리초 동안 하나 이상의 ID를 만들어 낸 경우에만 0보다 큰 값을 갖는다.

 

마무리

추가 논의 사항

• 시계 동기화
  • ID 생성 서버들이 전부 같은 시계를 사용했기 때문에 가능하다.
  • 적용할 수 없는 환경
    - 하나의 서버가 여러 코어에서 실행 되는 경우
    - 여러 서버가 물리적으로 독립된 여러 장비에서 실행 되는 경우
  • 시계 동기화 방법을 고려
• 각 절(section)의 길이 최적화
  • 동시성이 낮고 수명이 긴 애플리케이션이면
    - 일련번호의 절 길이를 줄이고 타임스탬프의 절 길이를 늘리는게 효과적
• 고가용성
  • ID 생성기는 필수 불가결 컴포넌트이므로 아주 높은 가용성을 제공해야한다.