개요
분산 시스템에서 데이터베이스 서버 한 대로는 요구를 감당하기 어렵고, 여러 데이터베이스 서버를 사용하면 지연시간(delay)를 낮추기 힘들어 auto_increment 속성을 사용하는 것은 통하기 않는다.
이러한 이유로 분산 시스템에서 사용될 유일 ID를 생성하는 유일 ID 생성기를 설계해보자.
1단계 문제 이해 및 설계 범위 확정
면접 문제에 대해 적절한 질문을 통해 설계를 구체화 해보자.
지원자: ID는 어떤 특성을 갖나요?
면접관: ID는 유일해야 하고, 정렬 가능해야 합니다.
지원자: 새로운 레코드에 붙일 ID는 항상 1만큼 큰 값이어야 하나요?
면접관: ID의 값은 시간이 흐름에 따라 커질 때지만 언제나 1씩 증가한다고 할 수는 없습니다. 다만 확실한 것은, 아침에 만든 ID보다는 저녁에 만든 ID가 큰 값을 갖는다는 점입니다.
지원자: ID는 숫자로만 구성되나요?
면접관: 그렇습니다.
지원자: 시스템 규모는 어느 정도입니까?
면접관: 초당 10,000 ID를 생성할 수 있어야 합니다.
Plain Text
복사
위 질문을 통해 정의된 요구사항은 다음과 같다.
•
ID는 유일(unique)해야한다.
•
ID는 숫자로만 구성되어야 한다.
•
ID는 64비트로 표현될 수 있는 값이어야 한다.
•
ID는 발급 날짜에 따라 정렬 가능해야 한다.
•
초당 10,000개의 ID를 만들 수 있어야 한다.
2단계 개략적 설계안 제시 및 동의 구하기
분산 시스템에서 유일성이 보장되는 ID를 만드는 방법은 여러가지가 있다.
•
다중 마스터 복제(multi-master replication)
•
UUID(Universally Unique Identifier)
•
티켓 서버(ticket server)
•
트위터 스노플레이크(twitter snowflake) 접근법
다중 마스터 복제
다중 마스터 복제는 데이터베이스의 auto_increment 기능을 활용되, 다음 번의 ID 값을 획득할 때 1만큼 증가하는 것이 아니라 k(데이터베이스 서버의 수)만큼 증가시켜서 얻는 방법이다.
위 그림처럼 서버가 이전에 생성한 이전 ID 값에 전체 서버의 수(2)만큼 증가시켜 다음 ID를 생성한다.
•
장점
◦
규모 확장성 문제를 어느정도 해결할 수 있다.
•
단점
◦
여러 데이터 센터에 걸쳐 규모를 늘리는 것이 어렵다.
◦
ID의 유일성은 보장되지만 시간의 흐름에 맞춰 커진다는 보장을 할 수 없다.
◦
서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어렵다.
UUID
UUID는 유일성이 보장되는 ID를 만드는 128비트짜리 문자열이다. UUID는 충돌 가능성이 존재하지만, 중복 UUID가 생성될 확률을 50%로 끌어올리기 위해서는 초당 10억 개의 UUID를 100년 동안 계속 만들어야 할 정도로 극히 낮다.
UUID 값은 09c93e62-50b4-468d-bf8a-c07e1040bfb2와 같은 형태를 띄는데, 랜덤하게 생성되는 값이기 때문에 서버 간의 조율이 필요없이 독립적으로 생성 가능하다.
•
장점
◦
생성이 아주 단순하고, 서버 간의 조율이 필요없어 동기화 이슈도 없다.
◦
각 서버가 자기가 쓸 ID를 만들기 때문에 규모 확장성이 높다.
•
단점
◦
ID가 128비트로 길다.
◦
ID를 시간순으로 정렬할 수 없다.
◦
ID에 숫자가 아닌 값이 포함된다.
티켓 서버
티켓 서버는 위 그림처럼 auto_increment 기능을 갖춘 하나의 데이터베이스 서버를 티켓 서버로 하여, 중앙 집중형으로 ID를 생성하여 관리하는 방법이다.
•
장점
◦
유일성이 보장되는 오직 숫자로만 이루어진 ID를 쉽게 만들 수 있다.
◦
구현하기 쉽고, 중소 규모 애플리케이션에 적합하다.
•
단점
◦
티켓 서버가 단일장애지점(SPOF)이 된다. 이를 피하기 위해 여러 서버를 준비하면 데이터 동기화 문제가 발생한다.
트위터 스노우플레이크 접근법
트위터에서 독창적으로 만들어 사용하는 스노플레이크 접근법은
위 그림처럼 생성해야할 ID 구조를 여러 절(section)으로 분할하여 ID를 생성하는 방식이다.
•
사인(sign) : 음수와 양수를 구분하는 비트로 지금은 쓰이고 있지 않지만 나중을 위해 유보해둔 공간으로 1 비트를 할당
•
타임스탬프 : 기원 시각(epoch) 이후로 몇 밀리초(ms)가 지났는지를 나타내는 값을 저장하는 키트으로 41 비트를 할당
•
데이터 센터 ID : 지원하는 데이터 센터의 ID를 저장하는 비트으로 5 비트 할당
•
서버 ID : 데이터 센터의 어떤 서버에 저장되어 있는지를 나타내는 비트로 5 비트를 할당
•
일련번호 : 각 서버에서 ID를 생성할 때 1씩 증가시키는 값을 저장하는 비트로 12비트 할당 (1ms가 경과할 때마다 0으로 초기화)
3단계 상세 설계
2단계에서 제시한 여러 기술적 해결 방법들 중 문제의 요구사항을 만족하는 것은 스노우플레이크 접근법 뿐이니, 해당 방법을 통해 상세 설계를 진행해보자.
타임스탬프
41비트의 공간을 차지하고 있는 타임스탬프는 시간에 따라 큰 값을 가지게 되므로 ID를 시간순으로 정렬 가능하게 될 것이다.
타임스탬프는 41비트만 사용하므로 2199023255551ms만 저장할 수 있는데, 이는 69년이고 이 시간이 지나면 기원 시간(epoch)를 바꾸거나 ID 체계를 다른 것으로 이전(migration) 해야한다.
일련 번호
12비트를 차지하는 일련번호는 4096개의 값을 가질 수 있는데, 동일한 서버에서 1ms 동안 하나 최대 4096개만 생성할 수 있다.
일련번호는 1ms동안 한 개 이상의 ID를 만들어낸 경우에만 0보다 큰 값을 가진다.
4단계 마무리
이번 장에서는 다중 마스터 복제, UUID, 티켓 서버, 트위터 스노우플레이크의 네 가지 유일 ID 생성기 설계 방법을 살펴보았다. 여기서 추가적으로 논의해볼만한 내용은 다음과 같다.
•
시계 동기화(clock synchronization) : 위 설계에서 모든 ID 생성 서버들이 전부 같은 시계를 사용한다고 가정했지만, 하나의 서버가 여러 코어에서 실행되는 경우나 여러 서버가 물리적으로 독립된 여러 장비에서 실행되는 경우 유효하지 않을 수 있다. 이에 대한 해결법으로 NTP 같은 것이 있을 수 있다.
•
ID의 section 길이 최적화 : 동시성이 낮고 수명이 긴 애플리케이션이라면 일련번호를 줄이고 타임스탬프를 늘리는 등 애플리케이션 환경에 맞춰 최적화할 수 있다.
•
고가용성(high availability) : ID 생성기는 필수 불가결(mission critical) 컴포넌트이므로 아주 높은 가용성을 제공해야 할 것이다.
NTP(Network Time Protocol)
NTP는 네트워크로 구성된 환경에서 구동되는 시스템들 간의 시간을 동기화하기 위해 UTC(세계협정시)로 시간을 동기화하기로 한 규약이다. 계층 구조로 되어있어 상위 계층의 시간 기준으로 하위 계층이 동기화 된다.
여러 버전이 존재하지만 간단하고 자주 쓰이는 SNTP가 대표적이다.