🏗️ ARCHITECTURE

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

1HOON 2024. 11. 18. 00:18

분산 환경에서 데이터베이스 서버 한 대로는 요구사항을 감당할 수 없을 뿐더러, 여러 데이터베이스 서버를 쓰는 경우에는 지연 시간을 낮추기가 힘들것이다.

분산 시스템에서 유일성이 보장되는 ID를 만드는 방법은 아래와 같다.

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

데이터베이스의 auto_increment 기능을 활용한다.

다음 ID의 값을 구할 때 1씩 증가시키는 것이 아니라, 데이터베이스 서버의 수(k)만큼 증가시킨다.

단점

  • 여러 데이터 센터에 걸쳐 규모를 늘리기 어렵다.
  • ID의 유일성은 보장되겠지만 그 값이 시간 흐름에 맞추어 커지도록 보장할 수는 없다.
    → 로드밸런싱 로직에 따라 하나의 데이터베이스 서버에서 ID를 연속해서 생성하면,
        이후 다른 서버에서 생성한 ID는 앞서 생성한 ID보다 값이 작을 수 있기 때문이다.
  • 서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어렵다.
    → 추가된 서버의 증가 폭이 다른 서버에서 생성한 ID와 겹칠 수 있기 때문이다. (공배수를 생각해보자)

 

UUID(Universally Unique Identifier)

UUID는 유일성이 보장되는 ID를 만드는 간단한 방법이다.

UUID 값은 충돌 가능성이 지극히 낮으며, 서버 간 조율 없이 독립적으로 생성 가능하다.

장점

  • UUID를 만드는 것은 단순하며, 서버 사이의 조율이 필요 없어 동기화 이슈도 없다.
  • 각 서버가 자기가 쓸 ID를 알아서 만드므로 규모 확장도 쉽다.

단점

  • ID가 128bit로 길다.
  • ID를 시간순으로 정렬할 수 없다.
    → ULID(Universally Unique Lexicographically Sortable Identifier)를 사용하면 생성 순서대로 정렬할 수 있다.
  • ID에 숫자가 아닌 값이 포함될 수 있다.

 

티켓 서버

auto_increment 기능을 갖춘 데이터베이스 서버(티켓 서버)를 중앙 집중형으로 하나만 사용하는 방법이다.

장점

  • 유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있다.
  • 구현하기 쉽고, 중소 규모 애플리케이션에 적합하다.

단점

  • 티켓 서버가 SPOF(Single Point of Failure)가 된다. 이 서버에 장애가 발생하면, 해당 서버를 이용하는 모든 시스템이 영향을 받는다. 이 이슈를 피하려면 티켓 서버를 여러대 준비해야하는데, 이 때 데이터 동기화 이슈가 발생한다.

 

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

생성해야 하는 ID의 구조를 여러 절(section)으로 분할한다.

사인(sign) 비트

1비트를 할당한다. 나중을 위해 유보하는 비트.

타임스탬프(timestamp)

41비트를 할당한다. epoch 이후로 몇 밀리초가 경과했는지를 나타낸다.

41비트로 표현할 수 있는 타임스탬프의 최댓값은 약 69년이기 때문에 이 방법은 69년동안만 정상동작한다.

데이터센터 ID

5비트를 할당한다. $2^5$개 데이터센터를 지원할 수 있다.

일련번호

12비트를 할당한다. 각 서버에서 ID를 생성할 때마다 일련번호를 1씩 증가시킨다.

이 값은 1밀리초가 경과할 때마다 0으로 초기화되기 때문에 같은 밀리초 동안 하나 이상의 ID를 만들어 낸 경우에만 0보다 큰 값을 가진다.

 

예제로 변환해보자! (X사례)

  1. 생성된 아이디 : 1858145109711222171
  2. 이진수 변환 : 001100111001001011101010010000111100101011101110111010110011011
  3. section 구분 
    •   0     0110011100100101110101001000011110010101     1101110111     010110011011
    • 사인                                            타임스탬프                                                 머신ID                일련번호
  4. 타임스탬프 십진수 변환 : 443016316821
  5. X의 epoch time(1288834974657) 더하기 : 1731851291478
  6. Readable하게 변환 : 2024년 11월 17일 일요일 오후 10:48:11.478 GMT+09:00

 

🤔 Sign bit 때문에 시간순 정렬이 깨지지 않을까? 왜 있어야하는거지??

사실상 Sign bit는 0으로 고정된다. 고정된 값임에도 해당 비트를 할당하는 가장 큰 이유는 아래와 같다.

Sign bit는 ID 값이 음수로 가는 것을 방지하고, 시스템이 커지는 과정에서 부호와 관련된 문제를 피할 수 있다.

 

이것이 무슨 말이냐.

64비트 정수에서 Sign bit 위치의 비트가 1일 경우 숫자는 음수를 나타내고, 0일 경우 양수를 나타낸다. (2의 보수를 생각해보자)

때문에 ID값이 항상 양수이길 바래서 Sign bit에 0을 고정해주는 것이다.

 

그렇다면 왜 ID 값은 항상 양수여야할까?

  1. 64비트 정수에서 최상위 비트가 1이면 음수로 간주되기 때문에, 실제로는 -9223372036854775808과 같은 매우 작은 음수 값이 될 수 있다.
    이 경우 ID 생성 시스템에서 부여된 고유 ID가 음수로 변환될 수 있는데, 이는 시스템에서 고유 ID가 양수여야 한다는 요구 사항에 맞지 않다.
  2. 만약 ID가 음수도 포함하게 되면, 추가적인 처리가 필요하고, 이를 통해 시스템 복잡성이 증가할 수 있다.
  3. 대부분의 시스템에서는 고유 ID가 양의 정수를 기대한다.
    예를 들어, 데이터베이스나 분산 시스템에서는 자동 증가하는 양의 정수를 주로 사용하고, 음수는 예외적인 경우에 사용된다.
  4. 시간 기반 시스템에서 음수 타임스탬프는 일반적으로 예외적이고, 처리하기 어려운 경우를 초래할 수 있다.
    예를 들어, 시스템이 1970년 1월 1일 이전의 시간을 음수로 해석하게 되면, 이는 예상치 못한 동작을 유발할 수 있다.

 

마무리

시계 동기화

ID 생성 서버들이 모두 같은 타임존에 있다고 가정했으나, 그렇지 않은 경우도 있을 것이다.

이 경우 NTP(Network Time Protocol)을 통해 시계를 동기화할 수 있다.

Section 길이 최적화

동시성이 낮고 수명이 긴 애플리케이션이라면, 일련번호 Section의 길이를 줄이고, 타임스탬프 Section의 길이를 늘리는 것이 효과적일 수 있다.

고가용성

ID 생성기는 필수 불가결 컴포넌트이므로 아주 높은 고가용성을 제공해야 할 것이다.

반응형
저작자표시 비영리 변경금지