분산 시스템을 위한 Unique ID 생성기 설계

https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=278536695

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

 

 

개요

---

이번 파트에서는 분산 시스템에서 사용될 Unique ID 생성기를 설계해보자.

 

간단한 프로젝트, 개인 프로젝트 등으로 ID를 설계할 때는 'auto_increment' 속성이 설정된 기본 키를 사용하곤 했다.

하지만 분산 환경에서는 'auto_increment'를 사용할 수 없는데, 데이터베이스 서버 한 대로는 요구를 감당할 수 없을뿐더러, 여러 서버가 동시에 auto_increment 값을 생성한다면 중복된 값이 발생할 수도 있기 때문이다.

 

분산 시스템에서 유일성이 보장되는 ID를 만드는 방법은 여러 가지 있을텐데, 여기선 다음과 같은 선택지를 살펴볼 예정이다.

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

위의 방법들에 대해 자세히 살펴보자.

 

 

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

다중 마스터 복제는 데이터베이스의 auto_increment 기능을 활용하는데, 다음 ID 값을 구할 때 1만큼 증가시키는 것이 아닌 현재 사용중인 데이터베이스의 서버 수에 해당하는 k만큼 증가시킨다.

 

위의 예제에서는 특정 서버가 만들어 낼 다음 ID 값은, 해당 서버에서 이전에 생성한 ID 값 + 2 을 얻게 된다. 이렇게 하면 규모 확장성 문제를 어느 정도 해결할 수 있고, 충돌 없는 분산 ID를 생성할 수 있겠지만 다음과 같은 치명적인 문제점이 존재한다.

• ID의 유일성은 보장되겠으나 시간 흐름에 맞추어 커지도록 순서 보장이 어렵다.
• 서버를 추가하거나 삭제할 때도 기존 값들과 충돌 없이 동작하도록 만들기가 어렵다.

 

 

UUID (Universally Unique Identifier)

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

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

 

중복이 발생할 확률이 일반적으로 거의 없기에, ID값 뿐만이 아니라 Unique 한 값이 필요한 상황에서 많이들 사용하는 것 같다.

 

https://www.linkedin.com/pulse/pros-cons-using-uuids-unique-identification-saeed-anabtawi/

 

 

UUID 값은 '09c93e62-50b4-468d-bf8a-c031842b' 와 같은 형식으로, 서버 간 조율 없이 독립적으로 생성이 가능하다.

UUID에 대한 추가 설명은 아래 링크를 참고해주세요:
https://docs.tosspayments.com/resources/glossary/uuid

 

 

장점

• UUID를 만드는 것이 단순하고, 서버 간 조율이 필요 없기에 동기화 이슈도 없다.
• 각 서버에서 ID를 직접 만드는 구조이므로 규모 확장도 쉽다.

import java.util.UUID

val uuid = UUID.randomUUID()

 

단점

• ID가 128비트로 길기에 저장 공간을 많이 차지한다.
• 순서 보장이 없기에 ID를 시간순으로 정렬할 수 없다.

ID를 정렬할 수 없는 부분이 굉장히 치명적인 문제가 될 것 같다. 데이터가 많아져서 count가 불가능한 경우 id 값 기준으로 정렬해서 대략적인 데이터 규모를 추정하는 경우도 있고, 그 외 ID 값으로 정렬을 해야 하는 상황이 있을텐데 이러한 로직 자체가 불가능한 것이기 때문에 치명적인 문제가 될 것 같다.

 

 

티켓 서버

티겟 서버는 유일성을 보장하는 ID를 만들어내는 데 사용할 수 있는 또 하나의 방법이다.

 

플리커(Flicker)는 분산 환경의 기본 키를 만들어내기 위해 티켓 서버 기술을 사용하고 있다.

Ticket Servers: Distributed Unique Primary Keys on the Cheap

 

티켓 서버의 핵심은 auto_increment 기능을 갖춘 데이터베이스 서버를 중앙 집중형으로 하나만 사용한다.

 

장점

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

단점

• 티켓 서버가 SPOF(Single Point Of Failure)가 된다.
• 즉, 티켓 서버에서 장애가 발생하면 해당 서버를 이용하여 ID를 생성하는 모든 시스템이 영향을 받게 된다. 이를 해결하려면 티켓 서버를 여러 대 준비해야 하는데, 그러면 데이터 동기화와 같은 새로운 문제가 발생할 수 있다.

 

 

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

위에서 살펴본 방법들은 모두 특정 문제들이 존재하였고, 이번에는 트위터(X)가 사용하는 스노플레이크 라는 ID 생성 기법을 살펴보겠다.

아래는 스노플레이크를 통해 생성할 64비트 ID의 구조이다.

• 사인(sign) 비트: 1비트를 할당한다. 당장에 쓰임새는 없으나 추후 음수/양수 구별에 사용할 수 있다.
• 타임스탬프: 41비트를 할당한다. 기원 시각 이후 몇 밀리초가 경과했는지를 나타내는 값이다.
• 데이터센터 ID: 5비트를 할당한다. 따라서 2^5 = 32개의 데이터센터를 지원할 수 있다.
• 서버 ID: 5비트를 할당한다. 따라서 데이터센터당 32개의 서버를 사용할 수 있다.
• 일련번호: 12비트를 할당한다. 각 서버에서 ID를 생성할 때마다 일련번호를 1만큼 증가시킨다.

 

상세 설계

https://apoorvtyagi.tech/generating-unique-ids-in-a-large-scale-distributed-environment

데이터센터 ID와 서버 ID는 시스템이 시작될 때 결정되며, 일반적으로 시스템 운영 중에는 바뀌지 않는다.

 

Snowfalke ID는 총 4개의 부분으로 이루어져있다.

 

sign

• 음수/양수를 구분하는데 사용하나 큰 용도는 없음

timestamp

• ID 구조 중 가장 중요한 41비트를 차지한다.
• 기원 시각(epoch) 이후 경과한 밀리초의 시간
• 시간의 흐름에 따라 점점 값이 커지므로 결국 시간 순 정렬이 가능해진다.

workerId

• 고유한 인스턴스의 ID 값으로 총 1,024대(2^10) 까지 사용이 가능하다.

sequence

• ID를 생성할 때마다 증가되는 값으로, 1밀리 초가 경과하면 값은 0으로 초기화가 된다.

 

장점

• 64bit로 UUID에 비해 차지하는 저장 공간이 작다.
• timestamp 기반으로 값이 생성되기 때문에 정렬이 가능하다.
• 분산 시스템에 적합하다.

단점

• UUID에 비해 구현이 더 복잡하다.