대규모 시스템 설계 공부 007

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

분산 시스템에서 사용될 유일 ID생성기를 설계할 때 'auto_increment 속성이 설정된 관계형 DB의 PK를 쓰면 되지 않을까?' 할 수도 있는데... 분산 환경에서 이 접근법은 통하지 않는다.
DB서버 한 대로는 그 요구를 감당할 수 없을뿐 아니라 여러 DB서버를 쓰는 경우에는 지연시간을 낮추기가 무척 힘들 것이기 때문이다.

-> Auto increment는 따로 동기화가 되어있지 않으면 각각의 분산 환경에서 동일한 ID가 나타날 수 있다.
-> Auto increment 추가적인 단점은 외부에서 해당 시스템의 id를 예측하기 쉽다는 것이다...이는 트래픽의 파악과 SQL Injection에 취약해지기 쉽다는 단점을 낳는다.

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

시스템 설계 면접 문제를 푸는 첫 단계는 적절한 질문을 통해 모호함을 없애고 설계 방향을 정하는 것이다.
이런 요구사항이 있다고 하면

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

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

분산 시스템에서 유일성이 보장되는 ID를 만드는 방법은 여러 가지이다.
그 중 이런 선택지를 살펴본다.

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

---

다중 마스터 복제

이 접근법은 Auto_increment 기능을 활용하는 방법이다.
다만, 다음 ID의 값을 구할 때에 1만큼이 아니라 k만큼 증가시킨다.(k는 현재 사용중인 DB 서버의 개수이다.)
위의 예제에서 보면 어떤 서버가 만들어낼 다음 아이디는 해당 서버가 생성한 이전 ID값에 전체 서버의 수 2를 더한 값이다.
이렇게 하면 규모 확장성 문제도 어느정도 해결할 수 있는데, DB수를 늘리면 초당생성 가능 ID수도 늘릴 수 있기 때문이다.
그런데 여기는 중대한 단점이 있다.

• 여러 데이터 센터에 걸쳐 규모를 늘리기 어렵다.
• ID의 유일성은 보장되겠지만 그 값이 시간 흐름에 맞추어 커지도록 보장할 수는 없다.
  • 보장 되지 않나...? 계속 커질것같은데
• 서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어렵다.
  • 본래 3씩 곱해주다가 4씩 곱해주면 안되니까..

---

UUID

UUID는 유일성이 보장되는 ID를 만드는 또 하나의 간단한 방법이다.
UUID는 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트짜리 수이며, 이 값은 충돌 가능성이 지극히 낮다.
(중복 UUID가 1개 생길 확률을 50%로 끌어올리려면 초당 10억개의 UUID를 100년동안 계속 만들어야 한다고 한다.) -> 10^-38 의 확률이라 한다.

UUID는 128비트의 크기를 갖는 고유한 값이며, 어떠한 시스템에 의존하지 않고 생성된다.

각 웹 서버는 별도의 ID생성기를 사용해 독립적으로 ID를 만들어낸다.

장점

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

단점

• ID가 128비트로 길다...우리가 이번 예제에서 원하는건 64비트이다.
• ID를 시간순으로 정렬할 수 없다.
• ID에 숫자가 아닌 값이 포함될 수 있다.

---

티켓 서버

티켓 서버는 유일성이 보장되는 ID를 만들어 내는 데 쓰일 수 있는 또 하나의 흥미로운 방법이다.
이 기술은 분산 기본 키를 만들어내기 위해 사용된다.

이런 식으로 auto_increment 기능을 갖춘 티켓 서버를 중앙 집중적으로 하나만 사용하는 아이디어이다.

장점

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

단점

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

---

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

지금까지 알아본 ID생성기들 중 이번 장에서 요구하는 문제를 만족하는 친구는 없었다.
트위터는 스노플레이크라고 부르는 독창적인 ID생성 기법을 사용하는데, 이를 사용하면 이 문제의 요구사항을 만족할 수 있다.

먼저 ID생성 전에 각개 격파 전략을 적용한다.
생성해야 하는 ID의 구조를 여러 section으로 분할하는 것이다.

이는 64비트 ID의 구조이다.

각 section의 쓰임새는 다음과 같다.

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

상세 설계

이전 단계에서 유일성 보장 ID생성기를 설계하는 데 쓰일 수 있는 다양한 기술적 선택지를 살펴보았다.
그 중 트위터 스노플레이크 접근법을 사용하여 상세한 설계를 진행한다.

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

타임스탬프

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

이 방법은 이진 표현 형태로부터 UTC시간을 추출하는 예제이며, 이를 반대로 사용하면 UTC->타임스탬프 값으로 변경도 가능할 것이다.

그리고 41비트로 표현 가능한 타임스탬프로는 대량 69년정도 데이터를 담을 수 있다.
이 아이디 생성기는 해당 기간동안만 정상 동작한다.
즉 69년이 지나면 기원 시각을 바꾸거나 ID체계를 다른 것으로 이전해야 한다.

일련번호

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

-> 그러면 같은데이터서버+같은서버+같은밀리초+5000개가 동일하게 만들어지면 겹칠수 있겠군

마무리

일단 여기서는 스노플레이크 방법을 사용했다.
이 방법은 모든 요구사항을 만족하며 동시에 분산 환경에서 규모 확장이 가능했기 때문이다.

추가로 논의해 볼 사항은 다음과 같다.

• 시계 동기화
  이번 설계에서는 ID생성 서버들이 전부 같은 시계를 사용한다고 가정했는데, 이런 가정은 하나의 서버가 여러 코어에서 실행되는 경우 유효하지 않을 수 있다.
• 각 절(section)길이 최적화
  예를 들어 동시성이 낮고 수명이 긴 애플리케이션이라면 일련번호 절의 길이를 줄이고 타임스탬프를 늘리는게 나을것이다.
• 고가용성
  ID생성기는 필수불가결 컴포넌트이므로 아주 높은 가용성을 제공해야 한다.