이 글은 책 「가상 면접 사례로 배우는 대규모 시스템 설계 기초」를 공부하고 정리한 글입니다.
이번 장에서는 분산 시스템에서 사용될 유일 ID 생성기를 설계해 보자. 'auto_increment 속성이 설정된 관계형 데이터베이스의 기본 키를 쓰면 되지 않을까?'라고 생각할 수도 있겠지만, 분산 환경에서 이 접근법은 통하지 않는다. 데이터베이스 서버 한 대로는 그 요구를 감당할 수 없을 뿐더러, 여러 데이터베이스 서버를 쓰는 경우에는 지연 시간(delay)을 낮추기가 무척 힘들다.
📌 요구사항 정리
이번 문제에 대한 답안이 만족해야 할 요구사항은 아래와 같다.
- ID는 유일해야 한다.
- ID는 숫자로만 구성되어야 한다.
- ID는 64비트로 표현될 수 있는 값이어야 한다.
- ID는 발급 날짜에 따라 정렬 가능해야 한다.
- 초당 10,000개의 ID를 만들 수 있어야 한다.
[ 개략적 설계안 제시 및 동의 구하기 ]
분산 시스템에서 유일성이 보장되는 ID를 만드는 방법은 여러 가지다.
- 다중 마스터 복제(multi-master replication)
- UUID(Universally Unique Identifier)
- 티켓 서버(ticket server)
- 트위터 스노플레이크(twitter snowflake) 접근법
다중 마스터 복제
이 접근법은 데이터베이스의 auto_increment 기능을 활용하는 것이다. 다만 다음 ID 값을 구할 때 1만큼 증가시켜 얻는 것이 아니라, k(현재 사용 중인 데이터베이스의 서버의 수)만큼 증가시킨다.
어떤 서버가 만들어 낸 다음 아이디는, 해당 서버가 생성한 이전 ID 값에 전체 서버의 수(여기서는 2)를 더한 값이다. 이렇게 하면 규모 확장성 문제를 어느 정도 해결할 수 있는데, 데이터베이스 수를 늘리면 초당 생산 가능 ID 수도 늘릴 수 있기 때문이다. 하지만 이 방법은 다음과 같은 중대한 단점이 있다.
- 여러 데이터 센터에 걸쳐 규모를 늘리기는 어렵다.
- ID의 유일성은 보장되겠지만 그 값이 시간 흐름에 맞추어 커지도록 보장할 수는 없다.
- 서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어렵다.
UUID
UUID는 유일성이 보장되는 ID를 만드는 또 하나의 간단한 방법이다. UUID는 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트짜리 수다. UUID 값은 충돌 가능성이 지극히 낮다.
"중복 UUID가 1개 생길 확률을 50%로 끌어 올리려면 초당 10억 개의 UUID를 100년 동안 계속해서 만들어야 한다." - 위키피디아
UUID 값은 서버 간 조율 없이 독립적으로 생성 가능하다. 다음은 UUID를 사용하는 시스템의 구조다.
이 구조에서 각 웹 서버는 별도의 ID 생성기를 사용해 독립적으로 ID를 만들어 낸다.
장점
- UUID를 만드는 것은 단순하다. 서버 사이의 조율이 필요 없으므로 동기화 이슈도 없다.
- 각 서버가 자기가 쓸 ID를 알아서 만드는 구조이므로 규모 확장도 쉽다.
단점
- ID가 128비트로 길다. -> 문제의 요구사항은 64비트였다.
- ID를 시간순으로 정렬할 수 없다.
- ID에 숫자(numeric) 아닌 값이 포함될 수 있다.
티켓 서버(ticket server)
티켓 서버는 유일성이 보장되는 ID를 만들어 내는 데 쓰일 수 있는 방법이다. 이 기술은 다음과 같이 동작한다.
이 아이디어의 핵심은 auto_increment 기능을 갖춘 데이터베이스 서버, 즉 티켓 서버를 중앙 집중형으로 하나만 사용하는 것이다.
장점
- 유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있다.
- 구현하기 쉽고, 중소 규모 애플리케이션에 적합하다.
단점
- 티켓 서버가
SPOF(Single-Point-of-Failure)가 된다. 이 서버에 장애가 발생하면, 해당 서버를 이용하는 모든 시스템이 영향을 받는다.- 이 이슈를 피하려면 티켓 서버를 여러 대 준비해야 하는데, 그렇게 하면 데이터 동기화 같은 새로운 문제가 발생할 것이다.
트위터 스노플레이크 접근법
지금까지 살펴본 여러 가지 ID 생성기 구현 방법 중 아직 위에서 언급한 문제의 요구사항을 만족시키는 것은 없었다. 트위터는 스노플레이크(snowflake)라고 부르는 독창적인 ID 생성 기법을 사용하는데, 이것은 문제의 요구사항을 만족시킬 수 있다.
그러나 ID를 바로 생성하는 대신, 생성해야 하는 ID의 구조를 여러 절(section)로 분할하는 각개격파 전략(divide and conquer)을 먼저 적용해 보자. 다음은 우리가 생성할 64비트 ID의 구조다.
- 사인(sign) 비트: 1비트를 할당한다. 지금으로서는 쓰임새가 없지만 나중을 위해 유보해 둔다. 음수를 양수를 구별하는 데 사용할 수 있을 것이다.
- 타임스탬프(timestamp): 41비트를 할당한다. 기원 시각(epoch) 이후로 몇 밀리초가 경과했는지를 나타내는 값이다.
- 데이터 센터 ID: 5비트를 할당한다. 따라서 2^5=32개 데이터센터를 지원할 수 있다.
- 서버 ID: 5비트를 할당한다. 따라서 데이터센터당 32개 서버를 사용할 수 있다.
- 일련번호: 12비트를 할당한다. 각 서버에서는 ID를 생성할 때마다 이 일련번호를 1만큼 증가시킨다. 이 값은 1밀리초가 경과할 때마다 0으로 초기화(reset)된다.
