Post

[Book - 가상 면접 사례로 배우는 대규모 시스템 설계 기초] 7. 분산 시스템을 위한 유일 ID 생성기 설계

분산 환경에서 auto_increment 속성이 설정된 기본 키는 통하지 않을 뿐더러,
여러 DB 서버를 쓰는 경우에는 delay를 낮추기가 무척 힘들 것이다.

1단계. 문제 이해 및 설계 범위 확정

시스템 설계 면접 문제를 푸는첫 단계는 적절한 질문ㅇ르 통해 모호함을 없애고 설계 방향을 정하는 것이다.

질문을 할 때는 요구사항을 이해하고 모호함을 해소하는 데 초점을 맞추어야 한다.

  • ID는 유일해야 한다.
  • ID는 숫자로만 구성되어야 한다.
  • ID는 64비트로 표현될 수 있는 값이어야 한다.
  • ID는 발급 날짜에 따라 정렬 가능해야 한다.
  • 초당 10,000개의 ID를 만들 수 있어야 한다.

2단계. 개략적 설계안 제시 및 동의 구하기

분산 시스템에서 유일성이 보장되는 ID를 만드는 방법은 여러 가지다.

다중 마스터 복제 (multi-master replication)

CAP 정리

이 접근 법은 auto_increment 기능을 화용하는 것인데, k만큼 증가시킨다. (k는 DB 서버 수)
이렇게 하면 규모 확장성 문제를 어느 정도 해결할 수 있지만, 아래와 같은 중대한 단점이 있다.

  • 여러 데이터 센터에 걸쳐 규모를 늘리기 어렵다.
  • ID의 유일성은 보장되겠지만 그 값이 시삭ㄴ 흐름에 맞추어 커지도록 보장할 수는 없다.
  • 서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어렵다.

UUID (Universally Unique Identifier)

UUID는 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트짜리 수로,
UUID 값은 충돌 가능성이 지극히 낮다.

UUID는 서버 간 조율 없이 독립적으로 생성 가능하다.

  • 장점
    • UUID를 만드는 것은 단순하다.
    • 서버 사이의 조율이 필요없으므로 동기화 이슈도 없다.
    • 각 서버가 자기가 쓸 ID를 알아서 만드는 구조이므로 규모 확장도 쉽다.
  • 단점
    • ID가 128비트로 길다. (이번 장에서의 요구사항은 64비트)
    • ID를 시간순으로 정렬할 수 없다.
    • ID에 숫자(numeric) 아닌 값이 포함될 수 있다.

티켓 서버 (ticket server)

플리커(Flickr)는 분산 기본 키(distributed primary key)를 만들어 내기 위해 이 기술을 이용했다.

티켓 서버

이 아이디어의 핵심은 auto_increment 기능을 갖춘 DB 서버,
즉 티켓 서버를 중앙 집중형으로 하나만 사용하는 것이다.

  • 장점
    • 유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있다.
    • 구현하기 쉽고, 중소 규모 애플리케이션에 적합하다.
  • 단점
    • 티켓 서버가 SPOF(Single-Point-of-Failure)가 된다.
    • 이 서버에 장애가 발생하면, 해당 서버를 이용하는 모든 시스템이 영향을 받는다.
    • 이 이슈를 피하려면 티켓 서버를 여러 대 준비해야 한다.
    • 하지만 그렇게 하면 데이터 동기화 같은 새로운 문제가 발생할 것이다.

트위터 스노플레이크 (twitter snowflake) 접근법

각개격파 전략(divide and conquer)을 먼저 적용해 보자.
생성해야 하는 ID의 구조를 여러 절(section)로 분할하는 것이다.

각개격파 전략

  • 사인(sign) 비트
    • 1비트를 할당한다.
    • 음수와 양수를 구별하는 데 사용할 수 있다.
  • 타임스탬프(timestamp)
    • 41 비트를 할당한다.
  • 데이터센터 ID
    • 5비트를 할당한다.
  • 서버 ID
    • 5비트를 할당한다.
  • 일련번호
    • 12비트를 할당한다.
    • 1밀리초가 경과할 때마다 0으로 초기화된다.

3단계. 상세 설계

트위터 스노플레이크 접근법 사용

4단계. 마무리

설계를 진행하고 시간이 남았다면 면저보가과 아래 내용을 추가로 논의할 수도 있을 것이다.

  • 시계 동기화(clock synchronization)
    • ID 생성 서버들이 전부 같은 시계를 사용한다고 가정했는데, 하나의 서버가 여러 코어에서 실행될 경우 유효하지 않을 수 있다.
    • NTP(Network Time Protocol)은 이 문제를 해결하는 가장 보편적 수단이다.
  • 각 절(section)의 길이 최적화
    • 동시성이 낮고 수명이 긴 애플리케이션이라면 일련번호 절의 기이를 줄이고, 타임스탬프 절의 길이를 늘리는 것이 효과적일 수도 있을 것이다.
  • 고가용성(high availability)
    • ID 생성기는 필수 불가결 컴포넌트이므로 아주 높은 가용성을 제공해야 할 것이다.
This post is licensed under CC BY 4.0 by the author.

© Yn3. Some rights reserved.