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

개요

분산 시스템에서 유일키를 생성하는 방법으로 auto_increment 속성이 설정된 관계형 DB 사용을 생각할 수 있지만 DB서버 한 대로는 이 접근법은 통하지 않고 여러 DB 서버를 쓰는 경우 지연시간을 낮추기가 무척 힘들 것이다.
이번에는 유일성이 보장되는 ID의 몇가지 예를 학습해볼 것이다.

 

유일 ID 생성 요구사항

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

 

유일 ID를 만드는 여러 방법

1. 다중 마스터 복제 (multi-master replication)

• DB의 auto_increment기능을 활용하는 것이다.
  • 다음 ID를 구할 때 1을 증가시키는 것이 아닌 k 즉, 현재 사용중인 DB서버 수만큼 증가시킨다.
• 아래 그림은 이 접근법에 대한 구성이다.
  
  • 어떤 서버가 만들 다음 ID는 해당 서버가 생성한 이전 ID에 2를 더한 값이다.
    • DB수를 늘리면 초당 생산 가능 ID 수도 늘릴 수 있어 규모 확장성의 문제를 어느정도 해결할 수 있다.
    • 하지만 다음과 같은 단점이 있다.
      • 여러 데이터 센터에 걸쳐 규모를 늘리기 어렵다.
      • ID의 유일성은 보장되겠지만 그 값이 시간 흐름에 맞춰 커지도록 보장할 수 없다.
      • 서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어렵다.

다중 마스터 복제의 구성

2. UUID (Universally Unique Identifier)

• UUID는 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트 자리 숫자이다.
• UUID값은 충돌 가능성이 지극히 낮다.
• 위키디피아의 UUID 개념

중복 UUID가 1개 생길 확률을 50%로 끌어 올리려면 초당 10억개의 UUID를 100년 동안 계속 만들어야한다. 

• UUID는 09c93e62-50b4-468d-bf8d-bf8a-c07e1040bfb2와 같은 형태를 띤다.
• UUID는 서버 간 조율 없이 독립적으로 생성 가능하다.
• UUID의 장점
  • UUID를 만드는 것은 단순하고 서버 사이의 조율이 필요 없어 동기화 이슈도 없다
  • 각 서버가 자기가 쓸 ID를 알아서 만드는 구조로 규모 확장이 쉽다.
• UUID의 단점
  • ID가 128비트로 길다.  위에서 언급한 내용은 64비트이다.
  • ID를 시간순으로 정렬할 수 없다.
  • ID에 숫자가 아닌 값이 포함될 수 있다.

 

3. 티켓 서버 (ticket server)

• 티켓 서버는 유일성이 보장되는 ID를 만들어내는데 쓰일 수 있는 방법 중 하나이다.
• 플리커(Flicker)는 분산 기본 키 (distributed primary key)를 만들어 내기 위해 이 기술을 이용했다.
• 이 기술은 아래 그림처럼 동작 하는데 여기서 핵심은 auto-increment기능을 갖춘 DB서버 즉, 티켓 서버를 중앙 집중형으로 하나만 사용하는 것이다.
• 장점
  • 유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있다.
  • 구현하기 쉽고 중소 규모 애플리케이션에 적합하다.
• 단점
  • 티켓 서버가 SPOF(Single-Point-of-Failure)가 된다. 이 서버에 장애 발생 시 해당 서버를 이용하는 모든서버에 영향이 가고 이 이슈를 피하려면 여러 티켓 서버를 두어야한다. 이렇게 되면 또다시 데이터 동기화 등의 새로운 문제가 발생할 것.

 

4. 트위터 스노플레이크 (twitter snowflack) 접근법

• 트위터는 스노플레이크 (snowflack)라고 부르는 독창적인 ID 생성 기법을 사용하며 이 고무적인 기법은 위 요구사항을 만족할 수 있다.
• ID를 바로 생성하기 전에 각개 전파 전략(divide and conquer)을 적용한다. (생성해야 하는 ID의 구조를 여러 절로 분할하는 것)

 

생성할 64비트 ID의 구조

• 각 절의 쓰임새
  • 사인(sign) 비트 : 1비트를 할당하고 지금으로 아직 쓰이지는 않지만 나중을 위해 유보. 양수와 음수를 구별하는데 사용
  • 타임스탬프 (timestamp) : 41비트를 할당. 기원 시각 (epoch)이후로 몇 밀리초가 경과했는지 나타내는 값
  • 데이터센터 ID : 5비트를 할당하며 데이터 센터당 32개 서버를 사용할 수 있다.
  • 일련번호 : 12비트 할당. 각 서버에서는 ID를 생성할 때 마다 이 일련번호를 1만큼 증가시킨다. 이 값을 1밀리초가 경과할 때 마다 0으로 초기화 된다.
• 상세 설계
  • 위 그림에서 데이터센터 ID와 서버ID는 시스템이 시작할 때 결정되며 운영중에는 바뀌지 않는다.
    • 데이터센터ID나 서버ID를 잘못 변경하면 ID 충돌이 일어날 수 있어 신중해야 함
  • 타임스탬프나 일련번호는 ID 생성기가 돌고 있는 중에 만들어지는 값
  • 타임스탬프
    • 시간이 지날 수 록 점점 큰 값을 가져 시간 순으로 정렬 가능
  • 일련번호
    • 12비트로 2¹² = 4096개의 값을 가질 수 있다. 어떤 서버가 같은 밀리초 동안 하나 이상의 ID를 만들어 낸 경우에만 0보다 큰 값을 갖게 된다. 

 

마무리

• 시계 동기화 (clock synchronization) : 위 내용에는 ID생성 서버들이 같은 시계를 사용한다고 가정했지만 이런 가정은은 하나의 서버가 여러 코어에서 실행될 경우 유효하지 않을 수 있다. 그리고 여러 서버가 물리적으로 독립된 여러 장비에서 실행되는 경우에도 마찬가지다. NTP(Network Time Protocol)은 이 문제를 해결하는 가장 보편적인 수단이다.
• 각 절의 최적화 : 예들 들어 동시성이 낮고 수명이 긴 애플리케이션이라면 일련번호 절의 길이를 줄이고 타임스탬프 절의 길이를 늘리는 것이 효과적일 수 있다.
• 고가용성 (high availability) : ID생성기는 필수 불가결 컴푸넌트 이므로 아주 높은 가용성을 제공해야할 것이다.