7. 분산 시스템을 위한 유일 ID 생성기 설계
Last updated
Last updated
ID는 유일해야 한다.
ID는 숫자로만 구성되어야 한다.
ID는 64비트로 표현될 수 있는 값이여야 한다.
ID는 발급 날짜에 따라 정렬 가능해야 한다.
초당 10,000개의 ID를 만들 수 있어야 한다.
요구사항을 이해하고 모호함을 해소하는데 초점을 갖고 질문을 해야 한다.
데이터베이스의 Auto increment 기능을 활용한다.
다음 ID 값을 구할 때1만큼 증가 시키는 것이 아닌 K 만큼 증가시킨다.
K는 현재 사용중인 데이터베이스 서버의 수다.
여러 데이터 센터에 걸쳐 규모를 늘리기 어렵다.
ID의 유일성은 보장되지만 그 값이 시간 흐름에 맞추어 커지도록 보장할 수는 없다.
서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어렵다.
서버를 추가/삭제 시 키 설정 시 정했던 K가 변동이 되어 이전 키와 신규 생성 키의 생성 규칙이 달라지게 됩니다.
유일성이 보장되는 ID를 만드는 또 하나의 간단한 방법
컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트의 수
단순하다. 서버 사이의 조율이 필요 없으므로 동기화 이슈도 없다.
각 서버가 자기가 쓸 ID를 알아서 만드는 구조이므로, 규모 확장도 쉽다.
ID가 128비트로 길다. (요구사항에서는 64비트 ID를 요구)
ID를 시간 순으로 정렬할 수 없다.
ID에 숫자 아닌 값이 포함될 수 있다.
Auto Increment 기능을 갖춘 데이터베이스 서버, 즉 티켓 서버를 중앙 집중형으로 하나만 사용
유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있다.
구현하기 쉽고, 중소 규모 애플리케이션에 적합하다.
티켓 서버가 SPOF(Single Point of Faliure, 단일 장애 포인트)가 된다.
이 서버에 장애가 발생하면, 해당 서버를 이용하는 모든 시스템에 영향을 받는다.
해당 이슈를 피하려면 티켓 서버를 여러 대 준비해야 한다. 그렇게 하면 데이터 동기화 같은 새로운 문제가 발생할 것이다.
결론적으로 해당 서버만을 위해서 추가적인 작업을 진행해야 하기 때문에 관리 범위가 커지는 단점이 발생합니다.
시스템 내에서 충돌없이 전역적으로 유일한 식별자를 생성하기 위해 트위터에서 개발한 방법
수평 확장(Scale-out)에 대응하기 위해 해당 방법을 고안하였고 트위터의 트윗, 사용자, 팔로우 관계 등 여러 객체에 대해서 고유 식별자를 할당하면서, 시스템의 확장성과 속도를 유지하기 위해서 채택하였다.
사인 비트: 1비트 할당, 지금으로서는 쓰임새가 없지만 나중을 위해 유보해둔다.
타임스탬프: 41비트 할당, 기원 시각(Epoch) 이후로 몇 밀리초가 경과했는 지를 나타내는 값이다. UTC 기준으로 저장
데이터센터 ID: 5비트 할당, 2 ** 5 = 32개의 데이터센터를 지원할 수 있다.
서버 ID: 5비트 할당, 데이터 센터 당 32개의 서버를 사용할 수 있다.
일련 번호: 12비트 할당, 각 서버에서는 ID를 생성할 때마다 이 일련 번호를 1만큼 중가시킨다. 이 값은 1밀리초가 경과할 때마다 0으로 초기화된다.
트위터 스노우플레이크 접근법을 사용
데이터 센터 ID와 서버 ID는 시스템이 시작할 때 결정되며, 일반적으로 시스템 운영 중에는 변하지 않는다. 두 아이디를 변경하면 ID 충돌이 발생할 수 있기 때문에 신중해야 한다.
타임스템프나 일련번호는 ID생성기가 돌고 있는 중에 만들어지는 값이다.
시간이 흐름에 따라 점점 큰 값을 갖게 되므로, 결국 ID는 시간 순으로 정렬 가능할 것이다.
41비트로 표현할 수 있는 최대 타임스템트 값은 2**41–1 = 2,199,023,255,551 (약 69년)
ID 생성기는 69년 동안 정상 동작하는데, 기원 시각을 현재에 가깝게 맞춰서 오버플로가 발생하는 시점을 늦춰놓은 것
69년이 지나면 기원 시각을 변경하거나, ID 체계를 다른 것으로 이전해야 한다.
12비트, 2 ** 12 = 4,096개의 값을 가질 수 있다.
어떤 서버가 값은 밀리초를 하나 이상의 ID를 만들어 낸 경우에만 0보다 큰 값을 갖게 된다.
위 요구사항을 만족하면서 분산 환경에서의 스케일 아웃이 가능한 트위터 스노우플레이크 접근법을 사용하여 문제를 해결함.
이번 설계를 진행하면서 우리는 ID 생성 서버들이 전부 같은 시계를 사용하였다고 가정하였음.
이런 가정은 하나의 서버가 여러 코어에서 실행될 경우나 여러 서버가 물리적으로 독립된 여러 장비에서 실행되는 경우에 유효하지 않을 수 있다.
NTP(Network Time Protocol)은 이 문제를 해결하는 가장 보편적인 수단
동시성이 낮고 수명이 긴 애플리케이션이라면 일련번호 절의 길이를 줄이고 타임스템프 절의 길이를 늘리는 것이 효과적일 수 있다.
ID 생성기는 필수 불가결(Mission Critical) 컴포넌트이므로 아주 높은 가용성을 제공해야 한다.
UUID 값은 충돌 가능성이 매우 낮다. ()
에서 분산 기본 키(Distributed primary key)를 만들기 위해 해당 기술을 사용