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는 시스템 시작할 때 결정 = 운영 중에는 변경되지 않음.

  • 타임스탬프, 일련번호는 운영 중에 생성되는 값

타임 스탬프

  • 시간 순으로 정렬되어야 한다는 조건을 만족해야함

  • 과정

    1. 현재 시간을 밀리초로 가져오기

    2. 기준 시간 (Epoch) 빼기

    3. 41비트에 맞추기

// 1. 현재 시간을 밀리초 단위로 얻기
const currentTime = Date.now(); // 예: 1724484123456

// 2. Snowflake의 기준 시간 (보통 서비스 시작 시점을 설정)
const EPOCH = 1288834974657; // 2010-11-04 01:42:54 (Twitter 기준)

// 2. 실제 타임스탬프 = 현재시간 - 기준시간
const timestamp = currentTime - EPOCH;

// 3. 41비트로 제한 (최대값: 2^41 - 1)
const snowflakeTimestamp = timestamp & 0x1FFFFFFFFFF;

  • 왜 기준 시간(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

  • 문제

    • 시계 동기화 오차

노드1: 2025-08-24 15:30:00.100
노드2: 2025-08-24 15:30:00.050  (50ms 늦음)
노드3: 2025-08-24 15:30:00.200  (100ms 빠름)

  • 노드가 가지고 있는 시계에 따라서 ID 순서가 다를 수 있음.

  • 해결 방법

  • NTP(Network Time Protocol)

# 정기적으로 시계 동기화
ntpdate -s time.nist.gov

  • 인터넷을 통해, 컴퓨터들의 시계를 정확하게 맞춰줌

  • 어떻게 동작하는 가?

Stratum 0: 원자시계, GPS 위성 (최고 정확도)
    ↓
Stratum 1: 직접 연결된 서버들 (time.nist.gov 등)
    ↓
Stratum 2: Stratum 1에서 시간을 받는 서버들
    ↓
Stratum 3: 일반 회사 서버들
    ↓
Stratum 4: 개인 컴퓨터들
1. 내 컴퓨터 → NTP 서버: "지금 몇 시예요?" (T1 시점에 전송)
2. NTP 서버: 요청 받음 (T2 시점에 도착)
3. NTP 서버 → 내 컴퓨터: "지금 XX시입니다" (T3 시점에 응답)
4. 내 컴퓨터: 응답 받음 (T4 시점에 도착)

네트워크 지연까지 고려한다.

왕복 시간 = (T4 - T1) - (T3 - T2)
한쪽 지연 = 왕복 시간 / 2
실제 서버 시간 = T3 + 한쪽 지연

정확도

  • LAN 환경: ±1ms 이내

  • 인터넷: ±10-100ms

  • 일반적: ±50ms 정도 한계

  • 네트워크 지연에 영향 받음

  • 완벽한 동기화는 불가능

Previous6. 키-값 저장소 설계Next8. URL 단축기

Last updated

Was this helpful?