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

*<가상 면접 사례로 배우는 대규모 시스템 설계 기초> 을 참고하여 작성한 게시물입니다.

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

분산 시스템에서는 auto_increment 속성으로 유일 ID를 생성할 수 없다. DB 서버 한 대만으로는 그 요구를 감당할 수 없으며, 여러 DB 서버를 쓰면 지연 시간을 낮추기가 힘들기 때문이다.

문제 이해 및 설계 범위 확정

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

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

• 다중 마스터 복제(multi-master replication)
  • auto_increment 기능을 활용하되, 다음 ID의 값을 구할때 1이 아니라 k(사용중인 DB 서버의 수)만큼 증가시킨다. (즉, A서버는 1,3,5... B서버는 2,4,6..이런 식으로 ID 증가) 이렇게 하면 구모 확장성 문제를 어느 정도 해결할 수 있는데, DB 수를 늘리면 초당 생산 가능 ID수도 늘릴 수 있기 때문이다. 그러나 1)여러 데이터 센터에 걸쳐 규모를 늘리기 어렵다. 2)ID의 유일성은 보장되겠지만 그 값이 시간 흐름에 맞추어 커지도록 보장할 수는 없다. 3)서버를 추가/삭제할 때도 잘 동작하도록 만들기 어렵다. 라는 단점이 있다.
• UUID(Universally Unique Identifier)
  • 컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128비트짜리 수로, 충돌 가능성이 지극히 낮다. 서버간 조율 없이 독립적으로 생성 가능하여, 각 웹 서버가 별도의 ID 생성기를 사용해 독립적으로 ID를 만들 수 있다. UUID를 만드는 것은 단순하고, 서버 사이의 조율이 필요없으므로 동기화 이슈도 없고, 각 서버가 자기가 쓸 ID를 알아서 만드는 구조이므로 규모 확장도 쉽다. 그러나 ID가 128비트로 길고, 시간 순으로 정렬할 수 없으며, 숫자가 아닌 값이 포함될 수 있다.
• 티켓 서버(ticket server)
  • 플리커(Flickr)는 분산 기본 키를 만들기 위해 이 기술을 사용했다. auto_increment 기능을 갖춘 DB 서버, 즉 티켓 서버를 중앙 집중형으로 하나마나 사용하는 것이다. 유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있고, 구현하기 쉬우며, 중소 규모 어플리케이션에 적합하다. 그러나 티켓 서버가 SPOF가 되어 이 서버에 장애가 발생하면 해당 서버를 이용하는 모든 시스템이 영향을 받는다. 이를 피하기 위해 티켓 서버를 여러 대 준비해야하는데, 이렇게 되면 데이터 동기화 같은 새로운 문제가 발생하게 된다.
• 트위터 스노플레이크(twitter snowflake) 접근법
  • 이 방법을 통해 요구사항 만족 가능. 생성해야 하는 ID의 구조를 여러 절로 분할(사인 비트, 타임스탬프-기원 시각 이후 몇 밀리초, 데이터센터ID, 서버ID, 일련번호-ID 생성 시마다 일련 번호 1만큼 증가. 1밀리초 경과시마다 0으로 초기화.)하여 사용하도록 한다.

상세 설계

데이터 센터 ID, 서버 ID는 시스템 시작시 결정되며, 일반적으로 시스템 운영 중에는 바뀌지 않는다. 타임스탬프, 일련번호는 ID 생성기가 돌고 있는 중에 만들어지는 값이다.

• 타임스탬프

  • 가장 중요함. 시간의 흐름에 따라 점점 큰 값을 갖게 되므로 ID가 시간 순으로 정렬 가능하게 된다. 타임스탬프->십진수 변환->기원 시각(epoch)더함->밀리초를 UTC 시각으로 변환 하는 방법을 역으로 전환하면 어떤 UTC시각도 타임스탬프 값으로 변환할 수 있다. 41비트로 표현할 수 있는 타임스탬프 최대값은 대략 69년에 해당한다. 따라서 기원 시각을 현재에 가깝게 맞춰서 오버플로가 발생하는 시점을 늦춰놓은 것이다. 69년이 지나면 기원 시각을 바꾸거나, ID 체계를 다른 것으로 이전해야한다.

• 일련번호

  • 12비트로, 4096개의 갑슬 가질 수 있다. 어떤 서버가 같은 밀리초 동안 하나 이상의 ID를 만들어낸 경우만 0보다 큰 값을 갖게 된다.

마무리

스노플레이크의 경우에 모든 요구사항을 만족하면서도 확장이 가능하다. 추가적으로 논의할 수 있는 사항은 다음과 같다.

• 시계 동기화(clock synchronization): ID 생성 서버들이 전부 같은 시계를 사용한다고 가정하고 설계를 진행한 것인데, 하나의 서버가 여러 코어에서 실행될 경우 이러한 가설은 유효하지 않을 수 있다. 여러 서버가 물리적으로 독립된 여러 장비에서 실행되는 경우에도 마찬가지다. 이를 해결하기 위한 수단으론 NTP(Network Time Protocl)이 있다.
• 각 절(section)의 길이 최적화: 옐르 들어 동시성이 낮고 수명이 긴 애플리케이션이라면 일련번호 절의 길이를 줄이고 타임스탬프 절의 길이를 늘리는 것이 효과적일 수도 있다.
• 고가용성: ID 생성기는 필수 불가결 컴포넌트이므로 아주 높은 가용성을 제공해야 한다.