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

가상 면접 사례로 배우는 대규모 시스템 설계 기초 7장: 분산 시스템을 위한 유일 ID 생성기 설계를 읽고 배운 점을 정리합니다.

 

분산 환경에서는 auto_increment 같은 방법을 적용하기 어렵습니다. 분산 시스템에서 유일성이 보장되는 ID를 만드는 것은 아래와 같은 방법이 있습니다.

• multi-master replication
• UUID
• ticket server
• twitter snowflake 접근법

Multi-master replication

다중 마스터 복제는 아래와 같은 구성을 가집니다.

이 접근법은 데이터베이스의 auto_increment를 사용하며, 증가시킬 때 1만큼 증가시키는 것이 아닌 k(데이터베이스 수)만큼 증가시키는 방법입니다.

 

이렇게 하면 규모 확장성 문제를 어느정도 해결할 수 있습니다. 데이터베이스 수를 늘리면 초당 생산 가능한 ID 수도 늘릴 수 있기 때문입니다. 다만 이 접근법은 아래와 같은 단점들이 존재합니다.

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

UUID

UUID는 128비트의 유일한 수를 생성하여 이용하는 방법입니다. UUID 생성기를 각 웹 서버에 sidecar 형식으로 붙이는 식으로 구현합니다. 

 

장점

• 구현이 단순하며, 서버 사이의 조율이 필요 없으므로 동기화 이슈가 없습니다.
• 규모 확장에 용이합니다.

단점

• ID 128비트로 다소 깁니다. 
• ID를 시간순으로 정렬할 수 없습니다.
• ID에 숫자가 아닌 값이 포함될 수 있습니다.

Ticket server

Flicker는 distributed primary key를 만들어 내기 위해 이 기술을 이용합니다. 구성은 아래와 같습니다.

이 아이디어의 핵심은 auto_increment 기능을 갖춘 데이터베이스 서버를 중앙 집중형으로 하나만 사용하는 것입니다. 

 

장점

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

단점

• 티켓 서버가 SPOF가 될 수 있습니다. 이를 위해 티켓 서버를 여러 대 둘 수 있지만, 이 경우 동기화 문제를 해결해야 합니다.

 

Twitter snowflake 접근법

이름이 이렇긴 한데, 그냥 트위터가 Snowflake라고 부르는 ID 생성 기법을 사용해서 이렇게 부르는 것 같습니다.

먼저, 생성해야 하는 ID의 구조를 여러 section으로 분할합니다.

여기서 첫 번째 비트는 sign bit로, 음수와 양수를 구별할 때 사용합니다. 마지막의 serial number는 12비트를 할당하며, 각 서버에서 ID를 생성할 때마다 이 serial number를 1만큼 증가시킵니다. 이 값은 1 밀리초가 경과할 때마다 0으로 초기화됩니다. Serial number는 동일한 시점에 여러 개의 데이터가 생성될 때 이를 구분하기 위해 사용됩니다. 

 

상세 설계

트위터 스노우플레이크 기법을 사용하여 상세한 설계를 해보겠습니다.

 

데이터센터 ID와 서버 ID는 시스템이 시작할 때 결정되며, 일반적으로 시스템 운영 중에는 바뀌지 않습니다. 타임스탬프 및 serial number는 생성기가 돌고 있는 도중에 만들어지는 값입니다.

 

타임스탬프

타임스탬프는 앞서 살펴본 ID 구조에서 가장 중요합니다. 타임스탬프는 시간이 흐름에 따라 점점 더 큰 값을 갖게 되므로, 결국 ID는 시간순으로 정렬 가능하게 될 겁니다. 다만, 41비트로 표현할 수 있는 타임스탬프의 최대값은 2^41 - 1 밀리초입니다. 이 값은 대략 69년에 해당하며, 이 ID 생성기는 69년동안만 정상 동작하는데, 기원 시각을 현재에 가깝게 맞춰서 overflow가 발생하는 시점을 늦춰 놓는 것이 좋습니다. 69년이 지나면 기원 시각을 바꾸거나 ID 체계를 다른 것으로 migration 해야 합니다.

 

Serial nubmer

Serial number는 12비트이므로 2^12 (4096)개의 값을 가질 수 있습니다. 어떤 서버가 같은 밀리초 동안 하나 이상의 ID를 만들어 낸 경우에만 0보다 큰 값을 갖게 됩니다.