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

분산 시스템에서는 auto_increment 설정은 통하지 않는다.

 

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

• 설계 범위 확정을 위한 인터뷰 내용은 아래와 같다.
  • 지원자: ID는 어떤 특성을 갖나요?
  • 면접관: ID는 유일해야 하고, 정렬 가능해야 합니다.
  • 지원자: 새로운 레코드에 붙일 ID는 항상 1만큼 큰 값이어야 하나요?
  • 면접관: ID의 값은 시간이 흐름에 따라 커질 테지만 언제나 1씩 증가한다고 할 수 없습니다. 다만 확실한 것은, 아침에 만든 ID보다는 저녁에 만든 ID가 큰 값을 갖는다는 점입니다.
  • 지원자: ID는 숫자로만 구성되나요?
  • 면접관: 그렇습니다.
  • 지원자: 시스템 규모는 어느 정도입니까?
  • 면접관 초당 10,000 ID를 생성할 수 있어야 합니다.
• 이를 통해 요구사항을 이해하고 모호함을 해소할 수 있고, 따라서 이번 문제에 대한 답안이 만족해야 할 요구상항은 아래와 같다.
  • ID는 유일해야 한다.
  • ID는 숫자로만 구성되어야 한다.
  • ID는 64비트로 표현될 수 있는 값이어야 한다.
  • ID는 발급 날짜에 따라 정렬 가능해야 한다.
  • 초당 10,000개의 ID를 만들 수 있어야 한다.

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

• 분산 시스템에서 유일성이 보장되는 ID를 만드는 방법은 여러 가지다. 종류는 아래와 같다.
  • 다중 마스터 복제
  • UUID
  • 티켓 서버
  • 트위터 스노플레이크 접근법

다중 마스터 복제

• 위와 같은 구성을 갖는 것을 말한다.
• 이 접근법은 데이터베이스의 auto_increment 기능을 활용하는 것이다. 다만 다음 ID의 값을 구할 때는 1만큼 증가시켜 얻는 것이 아니라, k만큼 증가시킨다. 여기서 k는 현재 사용 중인 데이터베이스 서버 수다.
• 이를 통해 규모 확장성 문제를 어느 정도 해결 할 수 있다. 데이터베이스 수를 늘리면 초당 생산 가능 ID 수도 늘릴 수 있기 때문이다.
• 하지만 중대한 단점이 있는데, 아래와 같다.
  • k의 값을 서버 수에 맞춰줘야 하기 때문에, 서버를 추가하거나 삭제할 때마다 k값을 재설정해줘야 하고, 이로 인해 ID 중복이 발생할 수 있다.
  • ID의 유일성은 보장되지만, ID 값이 시간 흐름에 맞추어 커지도록 보장할 수 없다. 예로, 로드 밸런싱으로 인해 특정 데이터베이스에서만 ID값이 올라갔다가 나중에 다른 데이터베이스로 요청이 넘어가는 경우를 들 수 있다.

UUID

• UUID는 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트짜리 수다.
• UUID 값은 충돌 가능성이 지극히 낮다. 위키피디아에 따르면 '중복 UUID가 1개 생길 확률을 50% 끌어 올리려면 초당 10억 개의 UUID를 100년 동안 계속해서 만들어야 한다.'
• UUID 값은 14015dd5-ea7d-4093-9597-894bb4d5c5b3와 같은 형태를 띤다.
• UUID는 서버 간 조율 없이 서버마다 독립적으로 생성 가능하다.
• 장점은 아래와 같다.
  • UUID를 만드는 것은 단순하다. 서버 사이의 조율이 필요 없으므로 동기화 이슈도 없다.
  • 각 서버가 자기가 쓸 ID를 알아서 만드는 구조이므로 규모 확장도 쉽다.
• 단점은 아래와 같다.
  • ID가 128비트로 길다. 이번 문제의 요구사항은 64비트이다.
  • ID를 시간순으로 정렬할 수 없다.
  • ID에 숫자가 아닌 값이 포함될 수 있다.

티켓 서버

• 이 아이디어의 핵심은 auto_increment 기능을 갖춘 데이터베이스 서버, 즉 티켓 서버를 중앙 집중형으로 하나만 사용하는 것이다.
• 장점은 아래와 같다.
  • 유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있다.
  • 구현하기 쉽고, 중소 규모 애플리케이션에 적합하다.
• 단점은 아래와 같다.
  • 티켓 서버가 SPOF가 된다. 이 서버에 장애가 발생하면 해당 서버를 이용하는 모든 시스템이 영향을 받는다.
  • 이 이슈를 피하려면 티켓 서버를 여러 대 준비해야 한다. 하지만 그렇게 하면 데이터 동기화 같은 새로운 문제가 발생한다.

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

• 먼저 생성해야 하는 ID의 구조를 여러 section으로 분할해보자.

• 각 section의 쓰임새는 아래와 같다.
  • sign 비트: 1비트를 할당한다. 음수와 양수를 구별하는 데 사용할 수 있을 것이다.
  • 타임스탬프: 41비트를 할당한다. 기원 시각 이후로 몇 밀리초 경과했는지를 나타내는 값이다.
  • 데이터센터 ID: 5비트를 할당한다. 따라서 2^5 = 32개 데이터센터를 지원할 수 있다.
  • 서버 ID: 5비트를 할당한다. 따라서 데이터센터당 32개 서버를 사용할 수 있다.
  • 일련번호: 12비트를 할당한다. 각 서버에서는 ID를 생성할 때마다 이 일련 번호를 1만큼 증가시킨다. 이 값은 1밀리초가 경과할 때마다 0으로 초기화된다.

3단계 상세 설계

• ID 구조를 상기해보면 일반적으로 데이터 센터 ID와 서버 ID는 시스템 운영 중에는 바뀌지 않는다.
• 만약 데이터 센터 ID나 서버 ID를 잘못 변경하게 되면 ID 충돌이 발생할 수 있다.
• 결론적으로, 타임스탬프나 일련번호는 ID 생성기가 돌고 있는 중에 만들어지는 값이다.

타임스탬프

• 타임스탬프는 41비트로 69년의 값만 저장할 수 있다. 따라서 이 ID 생성기는 69년동안만 정상 동작한다.
• 따라서 69년이 지나면 ID 체계를 다른 것으로 이전해야 한다. 

일련번호

• 일련번호는 12비트이므로 2^12 = 4096개의 값을 가질 수 있다. 어떤 서버가 같은 밀리초 동안 하나 이상의 ID를 만들어 낸 경우에만 0보다 큰 값을 갖게 된다.