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

 

처음 이 문장을 읽었을 때 auto_increment 속성이 설정된 관계형 데이터베이스의 기본 키를 쓰면 되지 않을까?하고 생각했다.

하지만 분산 환경에서 이 접근법은 데이터베이스 서버 한 대로는 요구를 감당할 수 없을 뿐더러, 여러 데이터베이스 서버를 쓰는 경우에는 지연시간(delay)를 낮추기가 힘들기 때문에 통하지 않는다는 것을 깨달았다.

 

역시 대규모 시스템 설계시엔 고려해야할 부분이 많은 것 같다.

 

요구사항이 다음과 같을 때 

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

분산 시스템에서 유일성이 보장되는 ID를 만드는 방법들에 대해 알아보자.

 

---

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

이미지 출처 : https://pulpul8282.tistory.com/323

이 방법은 데이터베이스의 auto_increment 기능을 활용하는 것이다.

다만 다음 ID의 값을 구할 때 1만큼 증가시켜 얻는 것이 아니라, k만큼 증가시킨다.

여기서 k는 현재 사용 중인 데이터베이스 서버의 수다.

 

이 방법의 단점은

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

 

---

2. UUID

유일성이 보장되는ID를 만드는 또 하나의 간단한 방법이다.

UUID는 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트짜리 수다.

이미지 출처 : https://donghyeon.dev/%EC%9D%B8%ED%94%84%EB%9D%BC/2022/04/02/%EB%B6%84%EC%82%B0-%EC%8B%9C%EC%8A%A4%ED%85%9C%EC%97%90%EC%84%9C-%EC%9C%A0%EC%9D%BC-ID-%EC%83%9D%EC%84%B1%EA%B8%B0-%EC%84%A4%EA%B3%84/

 

웹 서버는 별도의 ID 생성기를 사용해 독립적으로 ID를 만들어낸다.

장점

• 새로운 ID를 만드는 것이므로 간단하고 동기화 이슈가 없으며 확장에 용이하다.

단점

• ID가 길다. 
• 시간순으로 나열할 수 없다.
• 숫자 아닌 값이 포함될 수 있다.

 

---

 

3. 티켓 서버

이미지 출처 : https://donghyeon.dev/%EC%9D%B8%ED%94%84%EB%9D%BC/2022/04/02/%EB%B6%84%EC%82%B0-%EC%8B%9C%EC%8A%A4%ED%85%9C%EC%97%90%EC%84%9C-%EC%9C%A0%EC%9D%BC-ID-%EC%83%9D%EC%84%B1%EA%B8%B0-%EC%84%A4%EA%B3%84/

 

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

장점

• 구현하기 쉽고, 숫자로만 구성된 ID를 쉽게 만들 수 있다.

단점

• 티켓 서버가 SPOF(Single-Point-of-Failure)가 된다.
• 이 서버에 장애가 발생하면, 해당 서버를 이용하는 모든 시스템이 영향을 받는다.
• 이 이슈를 피하려면 티켓 서버가 여러 대 필요하고 그럼 결국 데이터 동기화 같은 문제가 발생할 것이다.

 

---

 

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

이미지 출처 : https://donghyeon.dev/%EC%9D%B8%ED%94%84%EB%9D%BC/2022/04/02/%EB%B6%84%EC%82%B0-%EC%8B%9C%EC%8A%A4%ED%85%9C%EC%97%90%EC%84%9C-%EC%9C%A0%EC%9D%BC-ID-%EC%83%9D%EC%84%B1%EA%B8%B0-%EC%84%A4%EA%B3%84/

 

지금까지 배운 것들은 요구 사항을 모두 만족시키지 않으므로 요구사항을 모두 만족시키는 독창적인 ID 생성 기법을 사용한다.

• 사인 비트
  • 1비트를 할당한다.
  • 지금은 쓰임새가 없지만 음수, 양수를 구별하는 데 사용할 비트
• 타임스탬프
  • 41비트를 할당한다.
  • 기원 시각(epoch) 이후로 몇밀리초(millisecond)가 경과했는지를 나타낸다.
  • 기원 시각으로 트위터 스노플레이크 구현에서 사용하는 값 1288834974657을 이용할 것이다.
• 데이터 센터 ID
  • 5비트를 할당한다.
  • 따라서 데이터 센터당 32개 서버를 사용할 수 있다.
• 일련번호
  • 12비트를 할당한다. (2의 12승인 4096개의 값을 가질 수 있다.)
  • 각 서버에서는 ID를 생성할 때마다 이 일련번호를 1만큼 증가시킨다.
  • 이 값은 1밀리초가 결과할 때마다 0으로 초기화(reset)된다.

 

---

 

계속 반복 되지만 결국 대규모 시스템의 핵심은 

구조 분산, 분해와 (분산, 분해로 인한) 동기화인 것 같다.

 

 

---

참고 : 가상 면접 사례로 배우는 대규모 시스템 설계 기초 1