[대규모 시스템 설계] 7장. 분산 시스템을 위한 유일 ID 생성기 설계

📕 목차

1. 유일 ID 생성기
2. 개략적 설계
3. 상세 설계

---

1. 유일 ID 생성기

 

📌 auto_increment는 답이 될 수 있을까?

DB가 단일 서버라면 auto_increment가 답이 될 수 있다.

하지만 사용자 트래픽이 높은 곳이라면 단일 DB만으로는 요구 사항을 감당할 수 없을 것이다.

그래서 DB 서버를 분산화하면, 더 이상 auto_increment만으로는 유일성을 보장할 수 없기에 이를 동기화하는 작업이 필요한데 지연 시간(delay)을 낮추기가 매우 힘들어질 수 있다.

 

그리고 NoSQL을 사용한다면, 애초에 선택지가 존재하질 않는다는 문제가 존재한다.

 

(여기서부터는 책에서 나온 내용이 이해가 안 가서, 추가 자료 조사와 추론을 기반으로 작성했습니다.)

 

🤔 DB를 다중화?

샤딩을 통해 master/slave 구조를 만든다 하더라도, 단일 DB 서버 내에서 동작하므로 auto_increment로 인한 ID 유일성을 보장될 것이라 생각한다.

그러나 물리적으로 분리된 multi-master 구조에선 MySQL의 auto_increment_increment와 auto_increment_offset과 같은 설정 등을 사용해야 한다.
(master1은 increment=2, offset=1을 가지며 {1, 3, 5, ...}의 ID를 할당하고, master2는 increment=2, offset=2를 주어 {2, 4, 6, ...}의 ID를 할당하게 하는 전략)
이러면 유일성은 보장되지만, 데이터 생성 시간이 pk 순서임을 보장하지 않으므로 결국 추가 작업이 필요하다. (거의 동시에 생성되면 created_at 으로 판단하는 게 불가능하며, 순서를 보장하지 않으므로 탐색 순서에 영향을 준다.)

DB 서버 자체가 여러 개인 경우가 있을 수도 있다. (이를, 수평적 파티셔닝이라 부르는 듯 하다.)
소셜 미디어 플랫폼은 사용자 정보를 지역별로 다른 DB에 저장하거나, 대규모 이커먼스 서비스는 제품 카테고리 별로 다른 DB를 사용할 수도 있을 것이다. (실제로 그렇게 하는 지는 모르겠으며, 그저 DB를 물리적으로 두는 경우를 추측한 내용)

 

📌 요구 사항

• ID는 유일성을 보장해야 한다.
• ID는 숫자로만 구성되어 있어야 한다.
• ID는 64bit로 표현 가능해야 한다.
• ID는 발급 날짜에 따라 정렬 가능해야 한다.
• 초당 10,000개의 ID를 만들 수 있어야 한다.

 

📌 분산 시스템에서 유일성이 보장되는 ID 생성 방법

일반적으로 다음 방법을 사용한다.

• 다중 마스터 복제
• UUID
• 티켓 서버
• 트위터 스노플레이크 접근법

 

---

2. 개략적 설계

 

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

위에서 대충 찾아본 내용이었는데, 책에 바로 등장 😅

 

데이터베이스의 auto_increment를 사용하는데, ID의 값을 1만큼 증가시키지 않고 k만큼 증가시킨다. (k는 사용 중인 DB 서버의 수)

DB의 수를 늘리면 초당 생산 가능 ID 수도 늘릴 수 있으므로, 자연스레 성능 또한 보장된다.

 

그러나 이 방법에는 중대한 결합이 존재한다.

• 여러 데이터 센터에 걸쳐 규모를 늘리기 어렵다. (k를 매번 모두 수정해야 한다.)
• ID의 유일성은 보장되지만, 시간의 흐름에 맞추어 커짐을 보장하지는 않는다. (id 10,000이 9,999보다 먼저 생성되었을 수도 있다.)
• 서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어렵다.

 

📌 UUID(Universally Unique Identifier)

컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128bit 수. 워낙 유명해서 자세한 설명은 필요 없을 것이다.

UUID는 랜덤 문자열을 생성하지만, 충돌 가능성이 매우 낮다고 판단한다. (고유성을 완벽하게 보장하진 못 하지만, 사실상 고유하다고 취급)

 

Universally unique identifier - Wikipedia

wiki에 적혀있는 말을 인용하면, "최소한 한 번의 충돌 확률이 50%가 되도록 생성해야 하는 4UUID의 수는 2.71조개로, 약 86년 동안 초당 10억개의 UUID를 약 86년 동안 생성해야 한다. 따라서 103조 개의 4UUID 버전에서 중복을 찾을 확률은 10억 분의 1이다."

 

🟢 pros

• 서버 간의 조율이 필요 없으므로, 동기화 이슈도 없다.
• 각 서버가 알아서 ID를 생성하므로, 규모 확장에 용이하다.

 

🔴 cons

• ID가 128 bit이므로, 현재 요구 사항에서 벗어난다.
• ID를 시간순으로 정렬할 수 없다. (인덱싱에 용이하질 않다.)
• ID에 숫자(numeric)이 아닌 값을 포함할 수 있다.

 

📌 티켓 서버(ticket server)

Ticket Servers: Distributed Unique Primary Keys on the Cheap | code.flickr.com

auto_increment가 여러 데이터베이스에서 보장할 수 없으니, 하나의 데이터베이스만을 사용한다는 전략이다.

 

사용자가 사진을 업로드 할 때마다, 하나의 데이터베이스에서 새 행을 삽입하여 만들어진 auto_increment 값을 사용한다는 것이다.

 

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

그러나 서버가 1대이므로 성능 저하를 피할 수 없고, 티켓 서버가 SPOF가 된다.

이 문제를 해결하려면 티켓 서버를 여러 대 준비해야 하는데, 그러면 데이터 동기화 문제가 발생한다.

 

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

생성해야 하는 64-bit ID를 단순히 랜덤값 혹은 증가값으로 지정하는 것이 아닌, ID의 구조를 여러 section으로 분할하는 방법이다.

 

• 사인(sign) 비트
  • 크기: 1bit
  • 현재로는 쓰임새가 없지만, 추후 변경 사항에 대비하기 위한 여분 bit
• 타임스탬프(timestamp)
  • 크기: 41bit
  • 기원 시각(epoch) 이후로 몇 밀리초(millisecond)가 경과했는지를 나타내는 값. (책에 있어서 적긴 했는데, 그냥 timestamp에 대한 설명)
  • ID 생성기가 돌고 있는 중에 만들어진다.
• 데이터센터 ID
  • 크기: 5bit
  • 2^5 = 32개의 데이터 센터를 지원 가능하다.
  • 시스템이 시작할 때 결정되며, 일반적으로 시스템 운영 도중 변경되지 않는다.
• 서버 ID
  • 크기: 5bit
  • 데이터 센터당 32개의 서버를 사용 가능하다.
  • 시스템이 시작할 때 결정되며, 일반적으로 시스템 운영 도중 변경되지 않는다.
• 일련번호
  • 크기: 12bit
  • 각 서버에서 ID를 생성할 때마다 일련 번호를 1씩 증가시킨다.
  • 이 값은 1밀리초가 경과할 때마다 0으로 초기화된다.
  • 동시에 생성된 데이터를 구분해주기 위한 값이다.
  • ID 생성기가 돌고 있는 중에 만들어진다.

 

---

3. 상세 설계

 

📌 Timestamp

Timestamp 값을 사용하면, 시간의 흐름에 따라 점점 큰 값을 가지므로 ID를 시간순으로 정렬할 수 있게 된다.

단, 41-bit로 표현 가능한 timestamp의 최댓값이 2^(41)-1 = 2199023255551ms ≅ 69 year 이라는 점을 유의해야 한다. 

 

트위터 기원 시각을 사용하는 이유는 기원 시각을 현재에 가깝게 맞추어 오버 플로가 발생하는 시점을 늦추기 위함이다.

따라서 69년이 지나면 기원 시각을 바꾸거나, ID 체계를 migration해야 한다.

 

근데 그건 69년 뒤의 개발자 팀이 할 일임. ㅋ

 

📌 일련 번호

일련 번호는 12bit이므로, 4,096개의 값을 가질 수 있다.

어떠한 서버가 같은 밀리초 동안 하나 이상의 ID를 만들어 낸 경우에만 0보다 큰 값을 갖게 된다.

 

이는 단순히 고유성 보장 뿐만 아니라, 같은 worker 내에서 같은 밀리초에 생성된 ID 순서를 보장한다.

그리고 밀리초 단위의 timestamp 만으로는 초당 1,000개의 고유 ID만을 생성 가능하지만, 일련 번호 필드를 사용하면 이론적으로 4,096,000개/sec의 ID를 생성할 수 있다.

 

🤔 timestamp가 충돌할 수도 있나?

timestamp가 고유하다고 보장할 수 없다는 내용은 얼핏 들어서 알고 있었지만, 제대로 찾아본 게 이번이 처음이라는 게 부끄러울 따름.
해당 사이트에서는 나노초 타임스탬프 충돌은 흔하다고 알려주고 있다. (4개의 물리 코어에서 시계를 동시에 읽을 때 약 5%의 샘플에서 발생)

이런 경우가 흔한지는 모르겠지만, 충돌 가능성이 존재하는 이상 무시할 수 없는 조건임은 분명하다.

 

📌 추가로 고려해볼 내용

• 시계 동기화(clock synchronization)
  • ID 생성 서버가 전부 같은 시계를 사용한다고 가정했으나, 하나의 서버가 여러 코어에서 실행될 경우 유효하지 않을 수 있다.
  • 여러 서버가 물리적으로 독립된 여러 장비에서 실행되는 경우 또한 보장할 수 없다.
  • NTP(Network Time Protocol)은 시계 동기화 문제를 해결하는 가장 보편적 수단으로 사용할 수 있다.
• 각 절(section) 길이 최적화
  • 동시성이 낮고, 수명이 긴 애플리케이션이라면 timestamp 충돌이 흔하지 않을 것이므로 일련번호 절을 줄이고, timestamp section을 늘리는 것이 효과적일 수 있다.
• 고가용성(high availability)
  • ID 생성기는 필수 불가결(mission critical) 컴포넌트이므로, 아주 높은 가용성을 제공해야 한다.