Post

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

Posted Updated
By ,
11 min read

개요

auto_increment속성이 설정된 관계형 데이터베이스의 기본 키를 쓰는 방법이 있겠다. 하지만 분산환경에서 데이터베이스 서버 한 대로는 이 요청을 감당할 수 없을 것이고, 여러 데이터베이스를 쓰는 경우 서버들이 중복된 값을 반환하면 안되기에 이를 관리해줘야할텐데 이 때문에 지연시간을 낮추기가 어려울 것이다.

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

어떤 문제를 풀던 적절한 질문을 통해 모호함을 없애 설계 하며 풀어가야 한다.

  • ID는 어떤 특성을 가지는가? 유일해야하나?
  • ID는 숫자로 구성되어 있는가?
  • ID는 최대 몇 비트로 표현되어야하는가?
  • ID가 꼭 1씩 증가해야하는가?
  • 초당 몇 개의 ID를 만들 수 있는가? 시스템 규모가 얼마나 되는가?

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

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

  • 다중 마스터 복제(multi-master replication)
  • UUID(Universally Unique Identifier)
  • 티켓 서버(ticket server)
  • 트위터 스노플레이크(twitter snowflake) 접근법

각각의 동작 원리와 장단점을 살펴봐야 한다.

다중 마스터 복제

image

이 접근법은 데이터베이스의 auto_increment기능을 활용하는 것이다. 하지만 다음 ID를 구할 때 1씩 증가하는것이 아닌 서버의 대수 k만큼 증가시키는 것이다. 서버가 3개라면 서버1은 1,4,7 …이렇게 증가하고 서버2는 2,5,8,… 이런식으로 증가할 것이다.

이렇게 하면 규모 확장성 문제를 어느정도 해결할 수 있다. 데이터베이스 수를 늘리면 초당 생산 가능 ID수도 늘릴 수 있기 때문이다. 하지만 서버가 추가되면 이 id들이 고유할까? 단점이 존재한다.

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

UUID

UUID는 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트짜리의 수다. UUID 값은 충돌 가능성이 극히 낮다. 위키피디아를 인용하면 "중복UUID가 1개 생길확률을 50%로 끌어 올리려면 초당 10억 개의 UUID를 100년 동안 계속해서 만들어야 한다."고 한다.

UUID는 09c93e62-50c4-487q-bfz8n-e05g4687bfs3같은 형태를 띈다.

image

이 구조에서 웹 서버는 별도의 ID 생성기를 사용해 독립적인 ID를 만들어낸다.

장점

  • UUID만드는것이 단순하다. 서버간 조율이 불필요해서 동기화 이슈도 없다.
  • 각 서버가 독립적으로 자기가 쓸 ID를 만드는것이기에 규모 확장이 쉽다.

단점

  • ID가 128비트로 길다.
  • ID를 시간순으로 정렬이 불가능하다.
  • ID에 숫자가 아닌 값이 포함될 수 있다.

티켓 서버

image

간단하다. auto_increment 기능을 갖춘 데이터베이스 서버, 즉 티켓 서버를 중앙 집중형으로 하나만 사용하는 것이다. 즉, 고유한 ID를 반환하는 서버 한 대를 둬서 동기화 이슈를 없애는 것이다.

장점

  • 유일성이 보장되는 오직 숫자로만 구성된 ID를 만들 수 있다.
  • 구현하기 쉽다.

단점

  • 티켓 서버가 SPOF(Single-Point-Of-Failure)가 된다. 이 서버에 장애가 발생하면 해당 서버를 이용하는 모든 시스템에 영향을 준다. 이 이슈를 피하려면 티켓 서버를 여러대 둬야하는데, 이러면 동기화 문제를 피할 수 없다.

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

트위터 스노플레이크를 통해서 문제의 요구사항을 만족시킬 수 있다. 기본 개념은 생성해야 하는 ID의 구조를 여러 공간으로 분할하는 것이다.

image

  • 사인(sign) 비트: 1비트를 할당한다. 개발자가 필요하면 쓰는 공간이다. 음수와 양수를 구분하는데 쓰일 수도 있고 다른 의미로 쓸 수도 있다.
  • 타임스탬프(timestamp): 41비트를 할당한다. Unix-time이후로 몇 밀리초가 경과했는지를 나타내는 값이다.
  • 데이터센터 ID: 5비트를 할당한다. 따라서 $ 2^5 $ 개의 데이터센터를 지원할 수 있다.
  • 서버 ID: 5비트를 할당한다. 따라서 데이터센터당 $ 2^5 $개의 서버를 사용할 수 있다.
  • 일련번호: 12비트를 할당한다. 각 서버에서는 ID를 생성할 때마다 일련번호를 1씩 증가시킨다. 이 값은 1밀리초가 경과할 때마다 0으로 초기화된다.

✏️ 3단계 상세설계

일단 위 방식에서 데이터센터ID와 서버 ID는 시스템이 시작될 때 결정되며, 일반적으로 시스템 운영중에는 바뀌지 않는다. 이 두 값을 잘못 변경하게 되면 ID 충돌이 날 수 있으니 신중해야 한다.

타임스탬프나 일련번호는 ID 생성기가 돌고 있는 중에 만들어지는 값이다.

타임스탬프

타임스탬프는 시간이 흐름에 따라 점점 큰 값을 가져서 정렬이 가능해진다.

image

이러한 방식으로 UTC 시각을 추출할 수 있다.

중간에 이해 안되는게 있을 것같다.

트위터 기원 시각(epoch)을 더함이라는 것인데, 트위터 스노플레이크 접근법은 무조건 Unix-time(1970년 1월1일)을 기원 시각으로 보지 않는다. 책의 예제에서는 Nov 04, 2010, 01:42:54 UTC에 해당하는 값인 1288834974657를 사용한다. 그렇기에 1970년에서 해당 값을 더해서 기원시각을 맞춰주는 것이다.

실제 위 그림의 $ 1586451091225 - 297616116568$ 을 한다면 기원시각인 $ 1288834974657 $이 될 것이다.

또한 이 기술에서 타임스탬프는 41비트로 표현이 가능하므로 최대 $ 2^41 - 1 $만큼 표현이 가능할 것이다. 이는 약 69년에 해당한다. 만약 69년에 근접한다면 기원시각을 현재로 맞추거나, ID 체계를 다른 것으로 이전해야 한다.

일련번호

일련번호는 12비트로, $ 2^12 $개의 값을 가질 수 있다.

🤔 정리

분산환경에서 고유한 ID를 만드는 방법을 알아봤다.

그나마 트위터 스노우 플레이크를 제외한 다른 방법들은 장단점이 명확하고 구현이 간단하여 이 챕터에서 어려운 점은 없었다.

  • 다중 마스터 복제: 단순하게 서버의 갯수만큼 Id값을 증가시키는 것이다. 하지만 서버가 삭제되거나 추가될 때 취약하다는 단점이 있다.
  • UUID: 128비트를 가져 중복 확률이 줄지만 고유한 값을 128비트보다 적게 만들 수 있었다.
  • 티켓 서버: 고유한 ID를 반환하는 중앙집중형 서버를 하나 뒀다. 하지만 이 서버가 장애가 난다면 어떻게 해결할 것인가에 대한 의문이 있었다.
  • 트위터 스노우 플레이크: 모든 요구사항을 만족하며 분산환경에서 규모확장도 가능하다.
Book, 가상 면접 사례로 배우는 대규모 시스템 설계 기초
book interview
This post is licensed under CC BY 4.0 by the author.