[가상 면접 사례로 배우는 대규모 시스템 설계 기초] 7. 분산 시스템을 위한 유일 ID 생성기 설계

이번 장에서는 분산 시스템에서 사용될 유일 ID 생성기를 설계해 볼 것이다.

참고) 관계형 DB에서 AUTO_INCREMENT를 사용할 수 있지만, 이 방식은 분산환경에 적합하지 않다.

• DB 서버 한 대로는 AUTO_INCREMENT 방식의 처리량을 감당하기 어렵다.
  
• 여러 DB 서버를 쓰는 경우에는 지연시간을 낮추기가 매우 어렵다.
  

문제 이해 및 설계 범위 확정

설계할 유일 ID 생성기에 대한 요구사항은 다음과 같다.

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

개략적 설계안 제시

분산 시스템에서 유일성이 보장되는 ID를 만드는 방법은 여러가지가 있다. 아래와 같은 방식에 대해 알아볼 것이다.

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

다중 마스터 복제

다중 마스터 복제 방식은 데이터베이스의 AUTO_INCREMENT 기능을 활용하는 것이다.

• AUTO_INCREMENT 처럼 ID값을 순차적으로 늘리지만, DB 서버의 수 만큼 증가시킨다.
  • 위의 예시에선 서버 수가 2이므로 각 DB서버는 ID를 2씩 늘린다.
    
• DB 수를 늘리면 초당 생산 가능 ID 수를 늘릴 수 있어 규모 확장성 문제를 어느정도 해결할 수 있다.
  

단점

• 여러 데이터 센터에 걸쳐 규모를 늘리기 어렵다.
  • 데이터 센터간 시간지연 고려, 동기화 문제
    
• ID의 유일성은 보장되지만, 그 값이 시간 흐름에 맞추어 커지도록 보장할 수는 없다.
  • 위 예에서 5번 ID값이 4번보다 나중에 만들어졌다고 보장할 수 없음
    
• 서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어렵다.
  • 서버 수가 달라지면 증가하는 ID 값이 달라지는 문제
    

UUID

UUID는 유일성이 보장되는 128비트 크기의 ID이다. 여러 시스템에서 동시에 생성된 UUID가 중복될 가능성은 없다고 봐도 무방하다.

• 128bit로 구성되어 총 32개의 문자가 5묶음으로 구분되어 있는 형태 (8-4-4-4-12개의 형태)
  
• ex) 123e4567-e89b-12d3-a456-426614174000
  

UUID는 서버 간 조율 없이 독립적으로 생성될 수 있으며, 비교적 간단히 생성할 수 있다.

장점

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

단점

• ID가 128비트로 길다. (설계 요구사항은 64비트)
  
• ID를 시간 순으로 정렬할 수 없다. (?)
  
• ID에 숫자가 아닌 값이 포함될 수 있다. (설계 요구사항에서 ID는 모두 숫자로 구성)
  

UUID는 시간 순으로 정렬 할 수 없다?

UUID도 버전이 여러가지가 있는데, 생성 시 사용되는 값에 따라서 UUID도 조금씩 달라진다.

• V1: Timestamp와 MAC 주소를 기반으로 UUID를 생성
  
• V2: Timestamp와 MAC 주소, DCE 보안 버전을 기반으로 UUID를 생성
  
• V3: Namespace 기반으로 MD5 해싱 알고리즘을 활용해 생성
  
• V4: 무작위로 UUID를 생성
  
• V5: Namespace 기반으로 SHA-1 해싱 알고리즘을 활용해 생성
  

UUID V4의 경우 unique한 값이 생성될지라도 DB입장에서는 인덱싱 비용이 많이 든다.

이런 문제에 대해 MySQL에서 Sequencial UUID를 생성하는 방식은 다음과 같다.

DELIMITER // CREATE DEFINER=`root`@`localhost` FUNCTION `ordered_uuid`(uuid BINARY(36)) RETURNS binary(16) DETERMINISTIC RETURN UNHEX(CONCAT(SUBSTR(uuid, 15, 4),SUBSTR(uuid, 10, 4),SUBSTR(uuid, 1, 8),SUBSTR(uuid, 20, 4),SUBSTR(uuid, 25))); // DELIMITER ;

결과

참고)

• https://chanos.tistory.com/entry/MySQL-UUID%EB%A5%BC-%ED%9A%A8%EC%9C%A8%EC%A0%81%EC%9C%BC%EB%A1%9C-%ED%99%9C%EC%9A%A9%ED%95%98%EA%B8%B0-%EC%9C%84%ED%95%9C-%EB%85%B8%EB%A0%A5%EA%B3%BC-%ED%95%9C%EA%B3%84
  
• https://devs0n.tistory.com/39
  
• https://www.percona.com/blog/store-uuid-optimized-way/
  

티켓 서버

티켓 서버는 유일성이 보장되는 ID를 만들 때 사용된다. 아이디어의 핵심은, AUTO_INCREMENT 기능을 갖춘 티켓 서버를 중앙 집중형으로 하나만 사용하는 것이다.

장점

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

단점

• 티켓 서버가 단일 장애 지점(SPOF)이 된다. 이를 피하기 위해선 여러 대의 티켓 서버가 필요한데, 그러면 동기화 이슈를 해결해야 한다.
  

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

트위터는 스노플레이크(snowflake)라고 부르는 독창적인 ID 생성 기법을 사용한다. 이 방식은 분산 환경에서 고유하고 순차적인 ID를 생성할 수 있도록 설계되었다. 구조는 다음과 같다.

• 사인(sign) 비트 1bit: 음수와 양수 구별 등의 용도로 사용될 수 있는 값
  
• 타임스탬프 41bit: 기원 시각 이후 몇 밀리초가 경과했는지 나타내는 값
  
• 데이터센터 ID 5bit: 32개의 데이터센터 표현 가능
  
• 서버 ID 5bit: 32개의 서버 표현 가능
  
• 일련번호(sequence number) 12bit: 각 서버에서 ID를 생성할 때마다 일련번호를 1만큼 증가시키고, 이 값은 1 밀리초가 경과할 때마다 0으로 초기화
  

일반적으로 데이터센터 ID와 서버 ID는 시스템 시작시에 결정되며, 일반적으론 시스템 운영중에 바뀌지 않는다.

반면 타임스탬프나 일련번호는 시스템 운영 중 동적으로 생성된다.

상세 설계

다양한 기술적 선택지를 살펴본 가운데 트위터 스노플레이크 접근법을 사용하여 상세 설계를 진행해보자. 동적으로 변경될 수 있는 부분인 타임스탬프와 일련번호에 대해 구체적으로 설계해볼 것이다.

타임스탬프

타임스탬프는 앞서 살펴본 ID 구조에서 가장 중요한 41비트를 차지하고 있다. 타임스탬프는 시간이 흐름에 따라 점점 큰 값을 갖게 되므로 정렬 가능하다.

아래 그림은 41비트의 타임스탬프를 UTC 시간으로 변환하는 과정이다.

• 41비트로 표현할 수 있는 타임스탬프의 최댓값은 2^41 - 1밀리초 이며, 이는 약 69년에 해당한다.
  • 따라서 이 ID 생성기는 69년동안만 유효하며, 69년이 지나면 기원 시각을 바꾸거나 ID 체계를 변경해야 한다.
    
• 이 방법을 역으로 적용하면 UTC 시간을 타임스탬프로 변환할 수도 있다.
  

일련번호

일련번호는 12비트이므로 4096(=2^12)개의 값을 가질 수 있다. 1밀리초 안에 둘 이상의 ID를 만들어낸 경우에만 0보다 큰 값을 갖게 된다.

마무리

다중 마스터 복제, UUID, 티켓 서버, 트위터 스노플레이크의 네 가지 방식을 살펴보았다. 선택한 방식은 스노플레이크인데, 모든 요구사항을 만족하면서도 분산 환경에서 규모 확장이 가능했기 때문이었다.

추가 논의 주제

시계 동기화(clock synchronization)

• ID 생성 서버가 같은 시계를 사용하지 않을 수 있다.
  
• 또한 여러 서버가 물리적으로 독립된 여러 장비에서 실행되는 경우에도 다른 시계를 사용한다.
  
• 이런 경우 시계 동기화가 필요하며 NTP(Network TIme Protocol)는 이 문제를 해결하는 가장 보편적인 수단이다.
  

NTP(Network TIme Protocol)

보통서버는 ntp서버 라는 시간의 기준이되는 서버가 존재한다. 일반서버들은 대부분 ntp서버와 통신을하여 시간을 맞추게 된다. 널리 사용되는 공용 ntp 서버는 다음과 같다.

• time.bora.net (203.248.240.140)
  
• time.nuri.net (211.115.194.21)
  
• time2.kriss.re.kr (210.98.16.101)
  

NTP는 Stratum이라는 계층 구조를 가지는데 분산된 장비들에 대해서 정확한 기준 시간 제공이 가능해진다.

참고) https://louis-j.tistory.com/entry/NTP-NTPNetwork-Time-Protocol-%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC-%EC%8B%9C%EA%B0%84-%EB%8F%99%EA%B8%B0%ED%99%94%EC%9D%98-%EB%AA%A8%EB%93%A0-%EA%B2%83#google_vignette

각 절(section)의 길이 최적화

• 어플리케이션의 성격에 따라 각 섹션의 비트 수를 조정할 수 있다.
  • ex) 동시성이 낮고 수명이 긴 어플리케이션 → 타임스탬프 늘리고 일련번호 줄이기
    

고가용성(high availability)

• ID 생성기는 필수 불가결 컴포넌트이므로 아주 높은 가용성을 제공해야 한다.