포스팅에 사용된 그림은 책에서 제공하는 그림들 입니다.

분산 시스템에서 사용될 유일 ID 생성기를 설계해 보자.

분산 시스템에서 데이터베이스의 auto_increment 속성을 사용하면 되지 않을까? 라고도 생각할 수 도 있다.

왜냐하면, 데이터베이스 서버 한 대로는 그 요구를 감당할 수 없을뿐더러, 여러 데이터베이스 서버를 쓰는 경우에는 지연 시간(delay)를 낮추기가 무척 힘들기 때문이다.

유일성이 보장되는 ID의 예시 그림

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

ID가 가져야 하는 특성

• 유일해야한다
• 발급 날짜에 따라 정렬 가능해야 한다
• ID는 숫자로만 구성되어야 한다.
• 초당 10,000 ID를 생성할 수 있어야 한다.

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

분산 시스템에서 유일성이 보장되는 ID를 만드는 방법은 더욱 다양하지만 이 중 4개를 살펴보자.

• 다중 마스터 복제
• UUID
• 티켓 서버
• 트위터 스노플레이크 접근법

다중 마스터 복제

다중 마스터 복제는 대략 아래와 같은 그림과 같은 구성을 갖는다.

이 접근법은 데이터베이스의 auto_increment 기능을 활용하는 것이다. 다만 다음 ID의 값을 구할 때 1만큼 증가시키는 것이 아니라 다중 마스터 서버 갯수 k 만큼 증가 시키면 유일한 ID를 가질 수 있게 할 수 있다.

하지만 이 방법은 단점이 있다.

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

UUID

UUID는 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트짜리 수다.

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

• 장점
  • UUID를 만드는 방법은 단순한다. 서버 사이의 조율이 필요 없으므로 동기화 이슈도 없음.
  • 각 서버가 자기가 쓸 ID를 알아서 만드는 구조이므로 규모 확장도 쉽다.
• 단점
  • ID가 128비트로 길다. 위 사례에서 요구사항은 64비트였다
  • ID를 시간순으로 정렬할 수 없음.
  • ID에 숫자가 아닌 값이 포함될 수 있다.

티켓 서버

플리커라는 웹 사이트는 분산 키를 만들어 내기 위해 이 기술을 이용했다고 한다.

동작 방식을 그림으로 보면

이 아이디어의 핵심은 auto_increment 기능을 갖춘 데이터베이스 서버, 즉 티켓 서버를 중앙 서버로 하나만 사용하는 것이다.

• 장점
  • 유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있음
  • 구현하기 쉽고, 중소 규모 애플리케이션에 적합하다.
• 단점
  • 티켓 서버가 SPOF가 된다. 이 서버에 장애가 발생하면 모든 시스템이 멈추게 된다. 이 이슈를 피하고 싶으면 티켓 서버를 여러대 두면 되는데, 여러대 두면 데이터 동기화와 같은 새로운 문제가 발생한다.

트위터 스노플레키의 접근법

지금까지 여러 가지 ID 생성기 구현 방법을 살펴보았다. 하지만 그 가운데 이번 장에서 풀어야 하는 문제의 요구사항을 만족하는 접근법은 없었다.

트위터는 스노플레이크라고 부르는 독창적인 ID 생성 기법을 사용한다. 이 기법은 위의 요구사항을 만족시킬 수 있다.

이 기법을 보기전, 각개 격파 전략을 먼저 이용해보자. 생성해야 하는 ID의 구조를 여러 절로 분할하는 것이다. 아래 그림을 봐보자.

그림의 각 요소를 살펴보면 다음과 같다.

• 사인 비트: 1비트를 할당한다. 지금으로서는 쓰임새가 없지만 나중을 위해 유보해 둔다. 음수와 양수를 구변하는데 사용할 수 있을 것이다.
• 타임스탬프: 41비트를 할당한다. 기원 시각 이후로 몇 밀리초가 경과했는지를 나타내는 값이다. 본 설계안의 경우에는 기원 시각으로 트위터 스노플레이크 구현에서 사용하는 값을 이용할 것이다.
• 데이터센터 ID: 5비트를 할당한다. 따라서 2의5승 즉 32개 데이터센터를 지원할 수 있다.
• 서버 ID: 5비트를 할당한다. 따라서 데이터센터당 32개 서버를 사용할 수 있다.
• 일련번호: 12비트를 할당한다. 각 서버에서는 ID를 생성할 때마다 이 일련번호를 1만큼 증가시킨다. 이 값은 1밀리초가 경과할 때마다 0으로 초기화 된다.

3단계 상세 설계

개략적 설계를 진행하면서 우리는 분산 시스템에서 사용할 유일성 보장 ID 생성기의 다양한 방법들을 알아보았다.

ID 구조 다이어그램을 다시 한번 봐보면, 데이터 센터 ID랑 서버 ID는 시스템이 시작할 때 결정되며, 일반적으로 시스템 운영 중에는 바뀌지 않는다. 데이터센터 ID나 서버 ID를 잘못 변경하게 되면 ID 충돌이 일어날 수 있으므로, 그런 작업을 해야 할 때는 신중해야 한다.

타임스탬프

41비트이며, 시간의 흐름에 따라 점점 큰 값을 갖게 되므로, 시간 순으로 정렬 가능하게 될것이다. 이는 UTC로 만들어 지기 때문에 역으로 어떠한 UTC라도 표현할 수 있다.

41비트로 표현할 수 있는 타임스탬프의 최댓값은 대략 69년에 해당하는데, 따라서 이 ID 생성기는 69년동안만 정상 동작한다. 기원 시각을 현재에 가깝게 맞춰서 오버플로가 발생하는 시점을 늦춰 놓은 것이다. 69년이 지나면 기원 시각을 바꾸거나 ID 체계를 다른 것으로 이전(migration)해주어야 한다.

일련번호

일련번호는 12비트이므로 4096개의 값을 가질 수 있다. 어떤 서버가 같은 밀리초 동안 하나 이상의 ID를 만들어 낸 경우에만 0보다 큰 값을 갖게 된다.

4단계 마무리

이번 장에서 설계를 진행했던 방법은 4가지 중 유일하게 요구사항을 모두 만족 시켜주면서 추가적인 확장이 가능했던 스노플레이크이다.

추가적으로 보아야할 것들을 봐보자.

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