가상 면접 사례로 배우는 대규모 시스템 설계 기초 - 7장

시스템 설계가상 면접 사례로 배우는 대규모 시스템 설계 기초

7. 분산 시스템을 위한 유일 ID 생성기 설계

  • 문제 이해 및 설계 범위 확정
    • 요구사항
      • ID는 유일해야 함
      • ID는 숫자로만 구성되어야 함
      • ID는 64비트로 표현될 수 있는 값이어야 함
      • ID는 발급 날짜에 따라 정렬 가능해야 함
      • 초당 10000개의 ID를 만들 수 있어야 함
  • 개략적 설계안 제시 및 동의 구하기

    • 다중 마스터 복제(Multi-Master Replication)

      다중 마스터 복제 구성도

      • DB의 auto_increment 기능을 활용하는 것
      • 다음 ID의 값을 구할 때 1만큼 증가시켜 얻는 것이 아니라, k만큼 증가시킴
      • 단점
        • 여러 데이터 센터에 걸쳐 규모를 늘리기 어려움
        • ID의 유일성은 보장되겠지만 그 값이 시간 흐름에 맞추어 커지도록 보장할 수 없음
        • 서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어려움

    • UUID

      서버별 독립적인 ID 생성기 구성도

      • 유일성이 보장되는 ID를 만드는 또 하나의 간단한 방법
      • 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트짜리 수
      • 충돌 가능성이 매우 낮음 → 중복 UUID가 1개 생길 확률을 50%로 끌어올리려면 초당 10억 개의 UUID를 100년 동안 계속해서 만들어야 함
      • UUID는 서버 간 조율 없이 독립적으로 생성 가능
      • 장점
        • UUID를 만드는 것은 단순하고 서버 사이의 조율이 필요 없으므로 동기화 이슈도 없음
        • 각 서버가 자기가 쓸 ID를 알아서 만드는 구조이므로 규모 확장도 쉬움
      • 단점
        • ID가 128비트로 긺
        • ID를 시간순으로 정렬할 수 없음
        • ID에 숫자가 아닌 값이 포함될 수 있음

    • 티켓 서버

      티켓 서버 구성도

      • 유일성이 보장되는 ID를 만드는 또 하나의 방법
      • auto_increment 기능을 갖춘 DB 서버(티켓 서버)를 중앙 집중형으로 하나만 사용하는 것
      • 장점
        • 유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있음
        • 구현하기 쉽고, 중소규모 애플리케이션에 적합
      • 단점
        • 티켓 서버가 SPOF가 됨
        • 티켓 서버에 장애가 발생하면 해당 서버를 이용하는 모든 시스템이 영향을 받음

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

      트위터 스노플레이크 ID 구조

      • 각개 격파 전략(Divide and Conquer)
        • 생성해야 하는 ID의 구조를 여러 절(Section)로 분할하는 것
        • 각 절의 쓰임새
          • 부호(Sign) 비트
            • 1비트를 할당
            • 쓰임새가 없지만 나중을 위해 유보
            • 음수와 양수를 구별하는 데 사용할 수 있음
          • 타임스탬프(Timestamp)
            • 41비트를 할당
            • 기원 시각(Epoch) 이후로 몇 밀리초(Millisecond)가 경과했는지를 나타내는 값
          • 데이터센터 ID
            • 5비트를 할당
            • 2^5 = 32개의 데이터센터를 지원할 수 있음
          • 서버 ID
            • 5비트를 할당
            • 데이터센터 당 32개 서버를 사용할 수 있음
          • 일련번호
            • 12비트를 할당
            • 각 서버에서는 ID를 생성할 때마다 일련번호를 1만큼 증가시킴
            • 이 값은 1밀리초가 경과할 때마다 0으로 초기화 됨
  • 상세 설계
    • 데이터센터 ID와 서버 ID는 시스템이 시작할 때 결정되고 일반적으로 시스템 운영 중에는 바뀌지 않음
    • 타임스탬프

      • 가장 중요한 41비트를 차지하고 있음

      • 시간이 흐름에 따라 점점 큰 값을 갖게 되므로 ID는 시간 순으로 정렬 가능하게 됨

      • ID 구조를 따르는 값의 이진 표현 형태로부터 UTC 시각을 추출하는 방법

        타임스탬프 값에서 UTC 시각 추출 과정

        • 역으로 적용하면 UTC 시각도 타임스탬프 값으로 변환 가능

      • 41비트로 표현할 수 있는 타임스탬프의 최대 값은 2^41 - 1초로 대략 69년

        • 따라서 69년동안만 정상 동작함
        • 69년이 지나면 기원 시각을 바꾸거나 ID 체계를 다른 것으로 이전(Migration)하여야 함
    • 일련번호
      • 12비트이므로 2^12 = 4096개의 값을 가질 수 있음
  • 마무리
    • 보완할 점
      • 시계 동기화(Clock Synchronization)
        • ID 생성 서버들이 전부 같은 시계를 사용한다고 가정
        • 하나의 서버가 여러 코어에서 실행될 경우 유효하지 않을 수 있음
        • NTP는 이 문제를 해결하는 가장 보편적 수단
      • 각 절(Section)의 길이 최적화
        • 동시성(Concurrency)이 낮고 수명이 긴 애플리케이션이라면 일련번호 절의 길이를 줄이고 타임스탬프 절의 길이를 늘리는 것이 효과적일 수 있음
      • 고가용성(High Availability)
        • ID 생성기는 필수 불가결(Mission Critical) 컴포넌트이므로 아주 높은 가용성을 제공해야 함