<div id="readability-page-1" class="page"><p><time>2023-06-18 에 작성하고, 2023-06-18 21:27:59 에 업데이트한 문서입니다. ✅</time> — <a href="/tags/system-design">SystemDesign</a> — <span>4 min read</span></p><section><h2 id="서론"><a href="#%EC%84%9C%EB%A1%A0" aria-label="서론 permalink"></a>서론</h2><p>블로그 쓰기를 급하게 준비하려고 최근 궁금했던 <a href="https://discord.com/blog/how-discord-stores-trillions-of-messages">디스코드는 어떻게 수조개의 메시지를 다룰까요</a> 블로그를 보다가 <a href="https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake">snowflake</a> 를 알게 되었다. snowflake 는 트위터에서 제안한 유니크한 id 생성기로, 분산시스템 상에서 id 생성을 위해서 주로 사용된다. </p><p>생각해보니 전 프로젝트들의 id 생성 방식이 이와 유사한 방식을 띄고 있었고 그 이유를 정확히 알지는 못했다. 그러니 유니크한 id 생성기가 따로 필요한 이유와 설계 방식까지 간단하게 공부해본다.</p><h2 id="왜-auto_increment-안해요"><a href="#%EC%99%9C-auto_increment-%EC%95%88%ED%95%B4%EC%9A%94" aria-label="왜 auto_increment 안해요 permalink"></a>왜 auto_increment 안해요?</h2><p>관계형 데이터베이스를 사용하기만해도 auto increment 를 사용하면 sql 데이터베이스의 내부적인 테이블에 따라서 하나씩 증가하는 키가 생성된다. 간단한 시스템에서는 잘 통하는 방법이고, 메인 데이터베이스가 단일 관계형 데이터베이스라면 괜찮을지도 모른다. </p><p>다만 이런 접근법은 분산 환경에서는 바로 깨져버리고 만다. 여러 데이터베이스 서버를 쓸 정도로 시스템의 요구량이 높은 경우, </p><p>1) 한대에서 auto increment 로 키를 만들어서 전달한다. -&gt; 한대로는 요구를 감당하기 어려울 가능성이 높다.
2) 만약 전달이 가능하다고 해도 delay가 어마어마할 확률이 높다. 한대에서 여러대로 해당 key를 전파해야하기때문..</p><p>따라서 어떤 데이터베이스 서버에서도 생성할 수 있지만, 유니크한 조합이 보장되는 키 생성기가 필요하게 된다. </p><h2 id="정렬이-되고-밤에-만든-키가-낮에-만든-키보다는-확실히-큰-유일한-숫자-키"><a href="#%EC%A0%95%EB%A0%AC%EC%9D%B4-%EB%90%98%EA%B3%A0-%EB%B0%A4%EC%97%90-%EB%A7%8C%EB%93%A0-%ED%82%A4%EA%B0%80-%EB%82%AE%EC%97%90-%EB%A7%8C%EB%93%A0-%ED%82%A4%EB%B3%B4%EB%8B%A4%EB%8A%94-%ED%99%95%EC%8B%A4%ED%9E%88-%ED%81%B0-%EC%9C%A0%EC%9D%BC%ED%95%9C-%EC%88%AB%EC%9E%90-%ED%82%A4" aria-label="정렬이 되고 밤에 만든 키가 낮에 만든 키보다는 확실히 큰 유일한 숫자 키 permalink"></a>정렬이 되고, 밤에 만든 키가 낮에 만든 키보다는 확실히 큰, 유일한 숫자 키</h2><p>책에서 주어진 조건은 다음과 같다. </p><ul><li>64 bit 의 숫자 키 </li><li>시간에 따라 커짐 </li><li>정렬 가능</li></ul><p>책에서는 4가지 접근방법을 소개하고 있다. </p><ul><li>다중 마스터 복제 </li><li>UUID</li><li>티켓 서버 </li><li>트위터 스노우플레이크 접근법 </li></ul><h3 id="다중-마스터-복제"><a href="#%EB%8B%A4%EC%A4%91-%EB%A7%88%EC%8A%A4%ED%84%B0-%EB%B3%B5%EC%A0%9C" aria-label="다중 마스터 복제 permalink"></a>다중 마스터 복제</h3><p><span>
      <span></span>
  <img alt="multi" title="multi" src="https://juneyr.dev/static/2ddbb7bd53cc1f0656c98bec464eba80/397ed/multi.png" sizes="(max-width: 647px) 100vw, 647px" loading="lazy" decoding="async">
    </span></p><p>다중 마스터 복제는 데이터베이스의 auto_increment 방식을 활용하는 것이다. 다만, 다음번에 정해지는 id 의 값을 구할 때 1만큼 올리는게 아니라 k만큼 증가시킨다. k는 현재 사용하고 있는 데이터베이스 서버의 수가 되겠다. 이렇게 하면 규모에 따른 확장성 문제를 어느 정도 해결할 수 있는데, 마스터가 여러개인 만큼 초당 생성가능한 ID 의 갯수도 늘릴 수 있기때문이다. </p><p>하지만 이 방법은 다음과 같은 큰 단점이 있다.</p><ul><li>여러 데이터 센터에 걸쳐서 규모를 늘리기는 어렵다. (분산환경 만족 안됨)</li><li>ID의 유일성은 보장되겠지만, 그 값이 시간 흐름에 맞추어 커지도록 보장할 수는 없다. <ul><li>예를 들어, #1 번의 3번 id가 시간 상으로 #2 번의 6번 보다 이후에 만들어진 레코드 일 수도 있다. </li></ul></li><li>서버를 추가하거나 삭제할 때도 잘 동작하도록 만들기 어렵다. </li></ul><h3 id="uuid"><a href="#uuid" aria-label="uuid permalink"></a>UUID</h3><p>중복되지 않는다는 조건만 생각하면 <a href="https://ko.wikipedia.org/wiki/%EB%B2%94%EC%9A%A9_%EA%B3%A0%EC%9C%A0_%EC%8B%9D%EB%B3%84%EC%9E%90">UUID</a> 가 생각나기도 한다. UUID 는 범용 고유 식별자 (universally unique identifier) 로,  컴퓨터 시스템에 저장되는 정보를 유일하게 식별하기 위한 128 bit 자리 수다.
충돌의 가능성이 거의 없어서 사실상 고유 식별자로 인정되고 있다. 표준형식에서 UUID 는 32개의 십육진수로 표현되는 값이다. e.g) 550e8400-e29b-41d4-a716-446655440000 </p><p>시간값, 랜덤값, 노드의 id 등으로 구성되고 있고 갯수로는 2의 128 제곱, 약 340간 2,823구 의 값이라고 한다. </p><p><span>
      <span></span>
  <img alt="uuid" title="uuid" src="https://juneyr.dev/static/c462ab4912f809dd0072285cf28ada6b/397ed/uuid.png" sizes="(max-width: 647px) 100vw, 647px" loading="lazy" decoding="async">
    </span></p><p><strong>장점</strong> </p><ul><li>UUID 만드는 방식이 정해져 있으므로 간단하다. 서버 사이의 조율도 필요없다. </li><li>각 서버가 자기가 쓸 ID를 알아서 만들면 되므로 규모 확장도 쉽다.</li></ul><p><strong>단점</strong></p><ul><li>ID가 128비트로 길고 무겁다. </li><li>ID를 시간순으로 정렬할 수 없다. </li><li>ID에 숫자가 아닌 값이 포함될 수 있다. (표준방식에는 <code>-</code> 가 들어감) </li></ul><h3 id="티켓-서버"><a href="#%ED%8B%B0%EC%BC%93-%EC%84%9C%EB%B2%84" aria-label="티켓 서버 permalink"></a>티켓 서버</h3><p>티켓 서버는 유일성이 보장되는 ID를 만들어내는 흥미로운 방법 중 하나다. <a href="https://www.flickr.com/">Flickr</a> 는 분산 기본 키를 만들어내기 위해서 이 방식을 사용했다고 한다. </p><p><span>
      <span></span>
  <img alt="ticket" title="ticket" src="https://juneyr.dev/static/557cdc2217784f8874e0f6010bf139fc/397ed/ticket.png" sizes="(max-width: 647px) 100vw, 647px" loading="lazy" decoding="async">
    </span></p><p>이 아이디어의 핵심은 auto increment 기능을 갖춘 티켓 서버를 중앙 집중형으로 하나만 사용하는 것이다.
이 티켓 서버는 id 생성만을 위한 기능을 가진다. 그래서 table schema 자체를 id와 관련된 것으로 생성해서 관리하고 있다. 아래는 플리커 블로그 포스트에서 따온 예시.</p><p><strong>장점</strong> </p><ul><li>유일성이 보장되는 오직 숫자로만 구성된 ID를 쉽게 만들 수 있다. </li><li>구현이 쉽고, 중소 규모 애플리케이션에 적합하다.</li></ul><p><strong>단점</strong></p><ul><li>티켓 서버 자체가 SPOF (Single Point of Failure) 가 된다. 이 서버에 장애가 발생하면, 해당 서버를 이용하는 모든 시스템이 영향을 받는다. 이를 피하려고 티켓 서버를 증설하면, 이번엔 동기화가 문제가 된다. </li></ul><p><a href="https://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/">플리커의 블로그 포스트</a> 에 따르면 플리커는 이 문제를 해결하기 위해서 티켓서버를 두개로 나눠서 관리했다. 그리고 실제로는 다중 마스터 복제 방식처럼, auto-increment 하는 수를 1이 아닌 2로 책정했다. 따라서 하나의 서버에서는 홀수만, 다른 서버에서는 짝수만 하도록 설정한 것으로 보인다. 그리고 이 티켓서버로의 요청은 라운드로빈으로 처리했다. </p><h3 id="트위터-스노우플레이크식-접근법"><a href="#%ED%8A%B8%EC%9C%84%ED%84%B0-%EC%8A%A4%EB%85%B8%EC%9A%B0%ED%94%8C%EB%A0%88%EC%9D%B4%ED%81%AC%EC%8B%9D-%EC%A0%91%EA%B7%BC%EB%B2%95" aria-label="트위터 스노우플레이크식 접근법 permalink"></a>트위터 스노우플레이크식 접근법</h3><p>트위터는 <a href="https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake">스노우플레이크(snowflake)라고 불리는 독창적인 ID 생성 기법</a>을 사용한다. 이 기법은 책에서의 요구사항을 만족시킬 수 있다. </p><p><span>
      <span></span>
  <img alt="snowflake" title="snowflake" src="https://juneyr.dev/static/90e8f89b7876257472b4156a6220b078/06b13/snowflake.png" sizes="(max-width: 796px) 100vw, 796px" loading="lazy" decoding="async">
    </span></p><p>snowflake 와 유사한 방식으로 접근해보자. 주어진 64bit 를 다음과 같이 쪼개본다. </p><ul><li>사인(sign) 비트 : 1비트를 할당해서 양수 / 음수를 할당한다. 지금은 딱히 쓰이지 않는다. </li><li>타임스탬프 비트: 41비트를 할당한다. epoch milliseconds 를 저장할 값이다. 책에서 공유된 설계안에서는 트위터 스노우플레이크 구현에서 사용하는 값 1288834974657 를 사용한다. (2010년 11월 4일, 01:42:54 UTC)</li><li>데이터 센터 ID: 5비트를 할당한다.  따라서 2의 5제곱인 32개의 데이터 센터를 지원한다. </li><li>서버 ID : 5비트를 할당한다. 따라서 32개의 데이터 센터 당 각각 32개의 서버를 지원한다.</li><li>일련번호 : 12비트를 할당한다. 각 서버에서는 ID를 생성할 때마다 이 일련번호를 증가시킨다. 이 값은 1ms 가 지날 때마다 0으로 초기화한다.</li></ul><p>위 ID 구성 중 데이터 센터ID와 서버 ID는 시스템이 시작할 때 결정되며, 일반적으로 시스템 운영중에는 바뀌지 않는다. </p><h4 id="타임스탬프"><a href="#%ED%83%80%EC%9E%84%EC%8A%A4%ED%83%AC%ED%94%84" aria-label="타임스탬프 permalink"></a>타임스탬프</h4><p>타임스탬프는 절대적으로 긴 값인 41 비트를 차지하게 된다. 타임스탬프는 시간의 흐름에 따라서 점점 큰 값을 갖게되므로, 결국 ID는 시간순으로 정렬가능하게 될 것이다. 41비트로 표현할 수 있는 타임스탬프의 최대값은 2의 41승 - 1 = 2199023255551 밀리초 (~ 69년정도) 에 해당한다. </p><p>따라서 이 ID 생성기는 69년동안만 정상동작한다. 트위터에서는 기준시각을 위에서 공유한 <code>1288834974657</code> (2010년 11월 4일, 01:42:54 UTC) 로 맞춰서 오버플로우가 발생하는 시점을 뒤로 늦춰놓은 것이다.  즉 어림잡아 2079년에는 이 생성기를 교체해야한다. </p><p>기준시각이 있고 타임스탬프가 있으므로 이 ID가 언제 생성되었는지 유추하는것 또한 가능하다. 타임스탬프의 41bit가 책에서 공유된 다음 값이라고 해보자. </p><p><code>101110010111010000111011011010100110111</code>  은 십진수로 398259500343 이고 이에 트위터 기원시각(epoch) 를 더하면 <code>1687094475000</code> 다. 이 값은 최종 epoch ms 이므로 이를 UTC 로 변경하면 2023년 June 18일 Sunday PM 1:21:15 가 된다. </p><h4 id="일련번호"><a href="#%EC%9D%BC%EB%A0%A8%EB%B2%88%ED%98%B8" aria-label="일련번호 permalink"></a>일련번호</h4><p>일련번호는 12비트이므로 2^12 = 4096개의 값을 가질 수 있다. 어떤 서버가 같은 ms 동안 한개 이상의 값을 가질때만 0보다 큰 값을 갖게된다. </p><h3 id="더-고려해야하는-점"><a href="#%EB%8D%94-%EA%B3%A0%EB%A0%A4%ED%95%B4%EC%95%BC%ED%95%98%EB%8A%94-%EC%A0%90" aria-label="더 고려해야하는 점 permalink"></a>더 고려해야하는 점</h3><ul><li><p>시계 동기화 : 위에서는 ID 생성 서버들이 모두 같은 시계를 사용한다고 가정했다. 하지만 이런 가정은 하나의 서버가 여러 코어에서 실행될 경우 유효하지 않을 수 있다. 물리적으로 독립된 여러 장비에서 실행될 때도 마찬가지다. 이를 해결하기 위해서는 NTP(Network Time Protocol) 이 흔히 사용된다고 한다. </p></li><li><p>고가용성 : ID 생성은 필수 불가결한 컴포넌트이므로 높은 가용성을 제공해야한다. </p></li><li><p>각 절의 길이: 위 snowflake 방식에서 팀의 프로젝트 환경에 따라 절의 길이는 조정이 필요할 것 같다. 예를 들어 데이터 센터가 많지 않지만, 서버가 많은 경우 데이터 센터 절을 줄이고 서버 절을 늘릴 수 있을 것이다. 그리고 동시성이 낮고 수명이 긴 애플리케이션이라면 일련번호의 절을 줄이고 타임스탬프 부분을 늘릴수도 있겠다. </p></li></ul><h2 id="참고"><a href="#%EC%B0%B8%EA%B3%A0" aria-label="참고 permalink"></a>참고</h2><ul><li>가상 면접 사례로 배우는 대규모 시스템 설계 기초, 알렉스 쉬 </li><li>디스코드는 어떻게 수조의 메시지를 보관하나, <a href="https://discord.com/blog/how-discord-stores-trillions-of-messages">https://discord.com/blog/how-discord-stores-trillions-of-messages</a></li><li>트위터의 스노우 플레이크를 소개합니다, <a href="https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake">https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake</a></li><li>UUID, <a href="https://ko.wikipedia.org/wiki/%EB%B2%94%EC%9A%A9_%EA%B3%A0%EC%9C%A0_%EC%8B%9D%EB%B3%84%EC%9E%90">https://ko.wikipedia.org/wiki/%EB%B2%94%EC%9A%A9_%EA%B3%A0%EC%9C%A0_%EC%8B%9D%EB%B3%84%EC%9E%90</a></li></ul></section></div>

Juneyr.dev RSS Feed

June Kim

서론 블로그 쓰기를 급하게 준비하려고 최근 궁금했던  디스코드는 어떻게 수조개의 메시지를 다룰까요  블로그를 보다가  snowflake  를 알게 되었다. snowflake 는 트위터에서 제안한 유니크한 id 생성기로, 분산시스템 상에서 id…

유일한 ID 생성기 설계 by 가상면접사례로 보는 시스템 설계 기초

댓글