7. 분산 시스템을 위한 유일 ID 생성기
요구사항
ID는 유일해야한다
ID는 숫자로만구성되어야 한다
ID는 64 비트로 표현될 수 있는 값이 어야 한다
unsigned 64bit = 0 ~ 2^64 - 1
signed 64 bit = -2^63 ~ 2^63 - 1
ID는 발급 날짜에 따라 정렬 가능해야 한다
초당 10,000 개의 ID를 만들 수 있어야 한다
해결 방법
다중 마스터 복제
데이터베이스의 auto_increment 기능을 활용하는 것
다음 ID의 K (데이터베이스 서버의 수) 만큼 증가 시킴
문제점
여러 데이터 센터에 걸쳐 규모를 늘리기 어렵고,
ID 유일성은 보장되지만, 시간이 흐름에 맞추어 커지도록 보장할 수 없음.
서버를 추가하거나 삭제할 때도 정상적으로 동작하도록 보장하기 어려움
UUID
시스템에 저장되는 정보를 유일하게 식별하기 위한 128 비트의 수
장점
단순, 서버가 조율 필요없음. 동기화 이슈 없음
규모 확장도 쉽다. 왜? 각 서버가 자기가 쓸 ID를 알아서 만드는 구조여서
단점
128비트, 길다. (요구사항에 맞지 않는다.)
시간 순으로 정렬할 수 없다 (요구사항에 맞지 않음)
ID에 숫자가 아닌 문자가 들어간다. (요구사항에 맞지 않음)
티켓 서버
![[Pasted image 20250824132226.png]]
auto_increment 기능을 갖춘 데이터베이스 서버(=티켓 서버) 를 하나만 가져간다.
장점
유일성 보장되는 구조.
숫자로 만든 ID
구현 쉽고, 중소 규모 애플리케이션에 적합
단점
SPOF (Single-Point-Of-Failure)
티켓 서버 장애는 모든 시스템에 영향
트위터 스노플레이크
생성해야하는 ID 구조를 여러 절로 분할 하는 것 ![[Pasted image 20250824132413.png]]
sign bit : 1bit, 음수 양수를 구분하는데 사용
timestamp bit : 41bit, 기원시각(epoch) 이후 몇밀리초가 경과했는지 나타내는 값.
datacenter id : 5bit, 2^5 = 32개 데이터 센터를 지원
server id : 5bit 데이터센터당 32개 서버 사용할 수 있음.
일련 번호 : 12 bit, 각 서버에서는 ID를 생성할 때 마다 일련번호를 1만큼 증가. 이 값은 1 밀리초 가 경과할 때 마다 0으로 초기화 됨.
상세 설계
![[Pasted image 20250824132413.png]]
데이터 센터 ID, 서버 ID는 시스템 시작할 때 결정 = 운영 중에는 변경되지 않음.
타임스탬프, 일련번호는 운영 중에 생성되는 값
타임 스탬프
시간 순으로 정렬되어야 한다는 조건을 만족해야함
과정
현재 시간을 밀리초로 가져오기
기준 시간 (Epoch) 빼기
41비트에 맞추기
왜 기준 시간(Epoch) 를 빼는가?
절약 : 2010년 이후의 시간만 저장하면 더 오래 사용 가능
2^41 - 1 = 2,199,023,255,551
1970년 기준: 이미 한계에 근접
2010년 기준: 69년의 여유 확보
효율성 : 더 작은 숫자로 더 긴 시간을 표현
41비트로 얼마나 오래 사용할 수 있는가?
2^41 밀리초 = 약 69년
2010년 기준으로 2079년까지 사용가능
마무리
시계 동기화 (clock synchronization)
ID 생성 서버가 전부 같은 시계를 사용했다.
그러지 않을 수 있음.
NTP(Network Time Protocol)
각 selection 의 길이 최적화
동시성이 낮고, 수명이 긴 어플리케이션이라면 '일련번호' 의 비트를 줄이고, '타임스탬프' 길이를 늘리는게 효과적일 수 있음
clock synchronization
문제
시계 동기화 오차
노드가 가지고 있는 시계에 따라서 ID 순서가 다를 수 있음.
해결 방법
NTP(Network Time Protocol)
인터넷을 통해, 컴퓨터들의 시계를 정확하게 맞춰줌
어떻게 동작하는 가?
네트워크 지연까지 고려한다.
정확도
LAN 환경: ±1ms 이내
인터넷: ±10-100ms
일반적: ±50ms 정도 한계
네트워크 지연에 영향 받음
완벽한 동기화는 불가능
Last updated