분산 ID 생성기 설계 면접 퀴즈

ID 생성기는 만드는 것이 쉬워 보여서 요구사항을 건너뛰기 쉽습니다. 그런데 어떤 순서를 포기하는지에 따라 설계가 완전히 달라집니다.

기능 요구사항과 범위 밖

빈틈 없는 연속 번호를 뺀 것이 이 설계의 출발점입니다. 1, 2, 3처럼 빈틈이 없어야 한다면 모든 발급이 한 곳을 지나야 하고, 그러면 그곳이 처리량 상한이자 장애점이 됩니다. 빈틈을 허용하면 각 노드가 스스로 만들 수 있습니다.

왜 정렬이 필요한가

ID는 대개 저장소의 기본 키가 됩니다. 그 값이 시간순으로 커지면 새 행이 인덱스의 한쪽 끝에만 붙습니다. 그 부분만 메모리에 있으면 되므로 삽입이 값쌉니다.

무작위 값이면 삽입 위치가 전체에 흩어져 매번 다른 페이지를 건드립니다. 하루 86억 건 규모에서 이 차이가 디스크 접근 수를 정합니다.

정렬은 취향이 아니라 저장 비용 요구사항입니다. 이 이유를 말하지 못하면 왜 무작위 방식을 안 쓰는지 설명할 수 없습니다.

왜 64비트 인가

수명 30년 에 하루 86억 건이면 총 발급량이 약 9경 4천조입니다. 64비트 정수가 담는 범위가 그보다 훨씬 크므로 충분합니다.

크기가 두 배면 인덱스도 두 배이고, 인덱스가 메모리에 들어가는지가 조회 속도를 정합니다. ID 하나의 크기가 시스템 전체의 메모리 예산에 곱해집니다.

"대략" 시간순의 뜻

같은 밀리초 안에서는 순서를 보장하지 않습니다. 이 포기가 결정적입니다.

보장한다면: 같은 밀리초에 발급하는 노드들이 서로 조율해야 한다
포기하면: 각 노드가 혼자 만든다. 왕복이 0이 된다

지연 1ms 는 외부에 물어볼 시간이 없다는 뜻입니다. 조율을 없애야 지킬 수 있고, 조율을 없애려면 밀리초 안 순서를 포기해야 합니다.

무엇을 절대 포기하지 않는가

중복은 허용하지 않습니다. 같은 ID가 두 번 나오면 다른 두 데이터가 하나로 취급되고, 그 사실을 나중에 알아채기도 어렵습니다.

유일성은 확률이 아니라 구조로 보장해야 합니다. 뒤의 모든 판단에서 이 기준이 가장 앞섭니다.

유일성을 구조로 보장하는 가장 단순한 방법은 한 곳에서만 발급하는 것입니다. 이 방법부터 재 보고 왜 탈락하는지 봅니다.

한 곳에서 번호를 센다

저장소의 증가하는 번호나 전용 서버 하나가 번호를 셉니다. 중복이 원리적으로 불가능하고, 요구사항에서 뺐던 빈틈 없는 연속 번호까지 얻습니다.

문제는 둘입니다.

발급량 초당 10만 도 그 한 곳의 처리량 상한에 걸립니다.

구간을 미리 받아 두면

한 번에 1,000개를 받아 로컬에서 나눠 쓰면 왕복이 1,000번에 한 번으로 줄어듭니다. 이 방법은 실무에서 널리 쓰입니다.

그런데 대가가 둘 생깁니다.

재시작하면 남은 구간이 버려진다. 번호에 빈틈이 생긴다
노드마다 다른 구간을 쓰므로 시간순 정렬이 깨진다

정렬이 깨지는 것이 치명적입니다. 앞 단계에서 정렬을 저장 비용 요구사항으로 정했는데, 구간 임대는 그것을 지키지 못합니다. 노드 A가 11000을, 노드 B가 10012000을 받으면 시간 순서와 번호 순서가 무관해집니다.

노드마다 증가폭을 다르게 주는 방법

노드 수만큼 증가폭을 두고 시작점을 다르게 주는 방법도 있습니다. 노드 셋이면 1, 4, 7 과 2, 5, 8 과 3, 6, 9 를 각각 씁니다.

이 방법은 왕복이 없지만 노드 수가 규칙에 들어 있습니다. 노드를 추가하려면 증가폭을 바꿔야 하고, 그러면 이미 발급한 번호와 충돌할 수 있습니다. 안정 해시에서 본 문제와 같은 모양입니다.

그래도 이 방법이 맞는 경우

중앙 발급기를 나쁜 방법으로 외우면 안 됩니다.

요구사항에 연속 번호가 있으면 다른 선택지가 없습니다. 이 설계는 그것을 뺐기 때문에 다른 길이 열렸습니다.

이 요구사항에서는 탈락한다

지연 1ms 와 정렬 요구를 함께 지킬 수 없습니다. 왕복을 없애려면 구간 임대가 필요하고, 구간 임대는 정렬을 깨뜨립니다.

그래서 다음 단계에서 아무에게도 묻지 않고 만드는 방법을 봅니다.

중앙 발급기가 탈락한 이유는 왕복이었습니다. 왕복을 없애는 가장 단순한 방법은 아무에게도 묻지 않고 아주 큰 무작위 값을 뽑는 것입니다.

충돌하지 않는 이유

값의 범위가 충분히 크면 두 번 같은 값이 나올 확률이 무시할 만큼 작아집니다. 128비트 규모에서는 하루 86억 건을 수십 년 뽑아도 충돌 확률이 사실상 0입니다.

이것은 확률에 기대는 보장입니다. 구조로 막는 것과 다르지만, 확률이 충분히 작으면 실무에서는 같은 값으로 취급합니다. 무작위성이 나쁜 생성기를 쓰면 이 전제가 깨지므로 그 부분만 주의합니다.

얻는 것과 잃는 것

크기가 요구사항 64비트 를 어깁니다. 그리고 정렬이 없으므로 앞 단계에서 본 삽입 비용 문제가 그대로 생깁니다.

두 대가는 서로 다른 무게다

크기는 저장과 인덱스 메모리를 두 배로 만듭니다. 아프지만 계산 가능한 비용입니다.

정렬이 없는 것이 더 무겁습니다. 삽입 위치가 흩어지면 쓰기가 느려지고, 그 영향은 데이터가 커질수록 나빠집니다. 인덱스가 메모리에 다 들어가는 규모에서는 차이가 작지만, 넘어가는 순간 급격히 벌어집니다.

앞부분에 시각을 넣는 변형

무작위 값의 앞부분을 시각으로 바꾸면 정렬을 되찾을 수 있습니다. 뒷부분은 그대로 무작위로 둡니다.

앞: 시각. 시간순으로 커진다
뒤: 무작위. 같은 순간의 충돌을 확률로 막는다

이 방식은 정렬과 조율 없음을 함께 얻습니다. 크기는 여전히 크지만 요구사항이 크기를 강하게 제한하지 않는다면 좋은 선택입니다. 실제로 많이 쓰입니다.

이 요구사항에서는 크기가 발목을 잡는다

64비트 정수 요구가 남아 있습니다. 무작위 부분을 줄여 64비트에 맞추면 충돌 확률이 급격히 올라갑니다. 초당 10만 규모에서 확률에 기대기에는 여유가 부족합니다.

그래서 다음 단계에서 무작위를 쓰지 않고 유일성을 구조로 얻는 방법을 봅니다. 같은 순간에 같은 값이 나올 수 없도록 칸을 나눠 쓰는 방식입니다.