요구사항
- ID는 유일해야 한다.
- ID 는 숫자로만 구성되어야 한다.
- ID는 64비트로 표현될 수 있는 값이어야 한다.
- ID는 발급 날짜에 따라 정렬 가능해야 한다.
- 초당 10,000개의 ID를 만들 수 있어야 한다.
다중 마스터 복제
이 접근법은 데이터베이스의 auto_increment 기능을 활용하는 것이다.
다만 다음 ID 의 값을 구할 때 1만큼 증가시켜 얻는 것이 아니라, k만큼 증가시킨다.
(여기서 k는 현재 사용 중인 데이터베이스 서버의 수)
단점
- 여러 데이터 센터에 걸쳐 규모를 늘리기 어렵다. (k 와 관련된 말..)
- ID의 유일성은 보장되겠지만 그 값이 시간 흐름에 맞추어 커지도록 보장할 수는 없다.
- 서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어렵다.
UUID
유일성이 보장되는 ID를 만드는 또 하나의 간단한 방법. UUID는 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트짜리 수
UUID 값은 서버 간 조율 없이 독립적으로 생성이 가능함
장점
- UUID 를 만드는 것은 단순하다. 서버 사이의 조율이 필요 없으므로 동기화 이슈도 없다.
- 각 서버가 자기가 쓸 ID 를 알아서 만드는 구조 이므로 규모 확장도 쉽다
단점
- ID 가 128비트로 길다. 이번 장에서 다루는 문제의 요구사항은 64비트다.
- ID를 시간순으로 정렬할 수 없다.
- ID에 숫자가 아닌 값이 포함될 수 있다
티켓 서버
플리커(Flickr)는 분산 기본 키(distributed primary key)를 만들어 내기 위해 이 기술을 사용함
이 아이디어의 핵심은 auto_increment 기능을 갖춘 데이터베이스 서버, 즉 티켓 서버를 중앙 집중형으로 하나만 사용하는 것이다.
장점
- 유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있다.
- 구현하기 쉽고, 중소 규모 애플리케이션에 적합하다.
단점
- 티켓 서버가 SPOF(Single-Point-of-Failure)가 된다. 이 서버에 장애가 발생하면, 해당 서버를 이용하는 모든 시스템이 영향을 받는다.
- 이 이슈를 피하려면 티켓 서버를 여러 대 준비해야 하는데, 그렇게 하면 데이터 동기화 같은 새로운 문제가 발생함
트위터 스노플레이크 접근법
- 사인 비트 : 당장은 쓰임새 없음. 나중을 위해 유보.
- 타임스탬프 : 기원 시각(epoch) 이후로 몇 밀리초(milisecond)가 경과했는지를 나타내는 값. 본 설계안의 경우에는 기원 시각으로 트위터 스노플레이크 구현에서 사용하는 값 을 이용
- 데이터센터 ID : 32개 데이터센터를 지원할 수 있다.
- 서버 ID : 데이터센터당 32개 서버를 사용할 수 있다.
- 일련번호 : 12비트를 할당한다. 각 서버에서는 ID를 생성할 때마다 이 일련번호를 1만큼 증가시킨다. 이 값은 1밀리초가 경과할 때마다 0으로 초기화(reset) 된다.
- 2^12 = 4096개의 값을 가질 수 있고, 어떤 서버가 같은 밀리초 동안 하나 이상의 ID를 만들어 낸 경우에만 0보다 큰 값을 갖게 된다.
추가 논의
- 시계 동기화 : 하나의 서버가 여러 코어에서 실행되는 경우 같은 시계를 사용하지 않을 수 있음. 여러 서버가 물리적으로 독립된 여러 장비에서 실행되는 경우에도 마찬가지.
- NTP(Network Time Protocol)은 이 문제를 해결하는 가장 보편적인 수단
- 각 절의 길이 최적화 : 동시성(concurrency)이 낮고 수명이 긴 애플리케이션 이라면 일련번호 절의 길이를 줄이고 타임스탬프 절의 길이를 늘리는 것이 효과적
- 고가용성 : ID 생성기는 필수 불가결 컴포넌트이므로 아주 높은 가용성을 제공해야 할 것이다.
참고문헌
Network Time Protocol
NTP 는 컴퓨터 시스템 사이에 시간 동기화를 위해 사용되는 네트워크 프로토콜.
NTP는 모든 참여하는 컴퓨터들의 시간을 UTC 기준으로 몇 milisec 정도의 차이 안으로 동기화하려고 함
프로토콜은 대개 client-server 모델 형태로 서술 되지만 각각의 peer 들이 다른 peer를 잠재적인 time source로 보는 peer-to-peer 관계로도 쉽게 사용된다.
구현은 UDP 프로토콜로 123 port 번호를 사용하며 timestamp 값을 전송하고 수신함
Clock strata(층위. 지층)
NTP는 계층적인 time source를 사용함. hierarchy의 각각의 층은 stratum 으로 불리고 0부터 숫자가 붙여짐
Stratum 은 reference clock 으로 부터의 거리를 의미함
Startum 이 항상 시간의 질이나 신뢰성을 의미하는 것은 아님. stratum 3의 time source가 stratum 2 time source 보다 더 정확한 시간을 가지는 경우도 많음
Stratum 0 (reference clock)
atomic clocks(원자시계), GNSS(위성 항법. GPS 포함), radio clocks, PTP -synchronized clock과 높은 정확도의 시간을 가진 기기
Stratum 1
시스템 타임이 각각의 컴퓨터에 할당된 stratum0 장치와 몇 miliseconds 차이 안으로 동기화 된 컴퓨터들
Stratum 1 서버들은 다른 stratum 1 server 들과 함께 그 값이 정확한 값인지 테스트하는 역할(Sanity check)과 backup 으로서 동작한다.
여기에 속한 컴퓨터들은 primary time server 라고도 불린다.
Stratum 2
stratum 1 에 속한 서버들과 동기화가 된 컴퓨터들. Stratum 2 컴퓨터들은 다른 peer stratum 2 컴퓨터들과 더 안정적이고 robust한 시간을 제공하기 위해 협력한다.
Stratum 3
stratum 2 서버들에 동기화된 컴퓨터들. stratum 2 에서 peering과 data sampling 에 사용하는 알고리즘을 그대로 이용함
.. 이렇게 계속 내려감. statum 16 는 동기화되지 않은 기기를 가리킴
Clock 동기화 알고리즘
보통의 NTP 클라이언트는 1개나 그 이상의 NTP server 로 부터 정기적으로 polling을 진행함.
클라이언트는 time offset과 round-trip delay를 꼭 계산해야 함
t0 : 요청 패킷을 전송할 때의 client 타임스탬프
t1 : 요청 패킷을 받았을대의 server 타임스탬프
t2 : 응답 패킷 전송할때의 서버 timestamp
t3 : 응답 패킷 수령 시의 클라이언트 timestamp
Outlier들은 버려지고 time offset의 추정치가 best 3개의 remaining candidates에서 추출됨. 이 값을 통해 clock frequency가 offset을 줄이도록 수정됨.
서버와 클라이언트의 들어오고 나가는 route의 nominal delay가 대칭적일때, 동기화가 맞춰진다.
Mac 의 경우
날짜 및 시간 설정에 들어가면 아래와 같이 time server가 time.apple.com 으로 정해져 있음
