서비스의 규모가 작을때는 auto_increment 속성이 설정된 관계형 데이터 베이스의 기본키를 사용하는 방법을 고려할 수 있지만, 분산 환경에서는 이러한 방법을 사용할 수 없다.

• 데이터베이스 서버(master) 한 대로는 요구를 감당할 수 없다.
• 여러 데이터베이스 서버를 쓰는 경우 지연 시간을 낮추기 매우 힘들다.

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

• Q. ID는 어떤 특성을 낮는가?
  • A. ID는 유일해야 하고, 정렬 가능해야 한다.
• Q. 새로운 레코드에 붙일 ID는 항상 1만큼 큰 값이어야 하는가?
  • A. 시간에 따라 커지지만, 언제나 1씩 증가하지는 않아도 괜찮다.
• Q. ID는 숫자로만 구성되는가?
  • A. 예
• Q. 시스템의 규모는 어느 정도 인가?
  • A. 초당 10,000 ID 생성 가능

위 질의응답을 통해 요구 사항을 정리하면 아래와 같다.

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

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

분산 시스템에서 유일성이 보장되는 ID를 만드는 방법은 여러 가지다.

다중 마스터 복제

이 접근법은 데이터베이스의 auto_increment 기능을 활용한다.

• 다음 ID의 값을 구할 때 1만큼 증가시켜 얻는 것이 아니라, k만큼 증가시킨다.
  • k = 현재 사용중인 데이터베이스 서버 대수

이러한 방식을 통해 규모 확장성 문제를 어느정도 해결할 수 있지만, 중대한 단점이 있다.

• 여러 데이터 센터에 걸쳐 규모를 늘리기 어렵다.
• ID의 유일성을 보장되지만, 그 값이 시간 흐름에 맞추어 커지도록 보장할 수 없다.
  • 더 많은 ID를 생성한 데이터베이스의 ID가 덜 생성한 데이터베이스의 ID보다 늦게 생성되었어도 큰 값을 가질 수 있다.
• 서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어렵다.

UUID

UUID는 유일성이 보장되는 ID를 만드는 또 하나의 간단한 방법이다.

• 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트짜리 수
• 충돌 가능성이 지극히 낮다.
  • 중복 UUID가 1개 생길 확률을 50%로 끌어 올리려면 초당 10억 개의 UUID를 100년동안 계속해서 만들어야 한다.
• 09c93e62-50b4-468d-bf8a-c07e1040bfb2 와 같은 형태를 띈다.

이러한 특성으로 UUID는 서버 간 조율 없이 독립적으로 생성 가능하므로, 각 서버가 별도의 ID 생성기를 사용해 독립적으로 ID를 만들어낸다.

장점

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

단점

• ID가 128비트로 길다.
  • 요구사항은 64비트
• ID를 시간순으로 정렬할 수 없다.
  • 임의의 중복이 힘든 문자열로 생성됨
• ID에 숫자가 아닌 값이 포함될 수 있다.
  • 요구사항은 숫자로만 구성되어야함

티켓 서버

티켓 서버는 auto_increment 기능을 낮춘 데이터베이스 서버, 즉 티켓 서버를 중앙 집중형으로 하나만 사용하는 방식으로 유일성이 보장되는 ID를 만든다.

• 플리커(Flickr)는 분산 기본 키(Distributed primary key)를 만들어 내기 위해 이 기술을 이용

장점

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

단점

• 티켓 서버가 SPOF가 된다.
  • 티켓 서버에 장애가 발생하면 해당 서버를 이용하는 모든 시스템이 영향을 받는다.
  • 티켓 서버를 여러 대 준비한다면 데이터 동기화 같은 새로운 문제가 발생한다.

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

스노플레이크 접근법은 생성해야하는 ID를 여러 절로 분할하여 독립적인 ID를 만든다.

• 사인(sign) 비트: 항상 0으로 설정되어 양수로 유지한다.
  • 특별한 의미는 없는듯
• 타임스탬프(timestamp): 기원 시간 이후로 몇 밀리초가 경과했는지를 나타내는 값
  • 41비트로 약 69년 동안의 시간을 표현할 수 있음
• 데이터센터 ID: 데이터센터 ID
  • 5비트로 32개 데이터 센터를 구분할 수 있음
• 서버 ID: 서버 ID
  • 5비트로 32개의 서버 구분 가능
• 일련번호: 각 서버에서 ID를 생성할 때마다 일련번호를 1만큼 증가시킴
  • 1밀리초가 경과될 때마다 0으로 초기화됨(TS가 1ms 간격으로 증가하므로)

3단계: 상세 설계

트위터 스노플레이크 접근법을 사용하여 보다 상세한 설계를 진행한다.

• 데이터센터 ID와 서버 ID는 시스템이 시작될 때 결정되며, 일반적으로 시스템 운영중에는 바뀌지 않는다.
  • 데이터센터 ID, 서버 ID를 잘못 변경하게 되면 충돌이 발생할 수 있으므로, 신중하게 해야한다.
• 타임 스탬프나 일련번호는 ID 생성기가 돌고 있는 중에 만들어진다.

타임스탬프

타임스탬프는 시간이 흐름에 따라 점점 큰 값을 갖게 되므로, 결국 ID는 시간 순으로 정렬 가능하게 된다.

41비트로 표현할 수 있는 타임스탬프 최대값은 2^41 - 1 = 2,199,023,255,551 밀리초 이므로 대략 69년 표현할 수 있다.

따라서 이 ID 생성기는 69년동안만 정상 동작하므로 69년이 지나면 기원 시각을 바꾸거나 ID 체계를 다른 것으로 이전(migration)하여햐한다.

일련번호

일련번호는 12비트이므로,2^12 - 1 = 4096개의 값을 가질 수 있다.

어떤 서버가 같은 밀리초 동안 하나 이상의 ID를 만들어 낸 경우에만 0보다 큰 값을 갖게 된다.

4단계: 마무리

• 시계 동기화(Clock synchronization)
  • 기존 설계는 하나의 서버가 여러 코어에서 실행될 경우 유효하지 않을 수 있다.
  • 물리적으로 독립된 여러 장비에서 실행되는 경우 유효하지 않을 수 있다.
  • NTP(Network Time Protocol)은 이 문제를 해결하는 가장 보편적인 수단이다.
• 각 절(Section)의 길이 최적화
  • 동시성이 낮고 수명이 긴 애플리케이션이라면 일련번호 절의 길이를 줄이고 타임스탬프 절의 길이를 늘리는 것이 효과적일 수 있다.
• 고가용성
  • ID 생성기는 필수 불가결(mission critical) 컴포넌트이므로 아주 높은 가용성을 제공해야한다.