목차
M3DB 노드 하나의 장애가 번지는 범위를 줄인 서브클러스터 (2026-09)
원문 정보
- 원문: From Chaos to Control: Addressing Shard Distribution Challenges in M3DB with Subclusters
- 매체 · 게시일: Uber Engineering Blog · 2026-09-01
- 저자: Riya Tyagi(Senior Software Engineer), Ramnik Jain(Senior Staff Engineer), Padma Chitturi(Manager II, Engineering)
- 원문 내용을 바탕으로 재구성한 요약입니다.
노드 하나를 정비해도 바빠지는 클러스터
M3DB의 기존 샤드 배치는 중소 규모 클러스터에서 잘 동작했습니다. 규모가 커지자 운영이 어려워졌습니다. 노드 하나의 장애가 많은 노드의 I/O와 네트워크를 압박하고, 서로 다른 노드를 정비하는 작업도 간섭할 수 있어 안전하게 진행하려면 순서를 기다려야 했습니다.
M3DB는 데이터를 샤드로 나누고 각 샤드를 복제 인수(RF)만큼 여러 노드에 복제하는 분산 시계열 데이터베이스입니다. 어느 노드에 샤드를 놓을지, 노드 구성이 바뀌면 어디로 옮길지는 배치(placement) 알고리즘이 정합니다. 기존 샤디드 배치가 강제하는 제약은 하나였습니다. 같은 샤드의 복제본들을 같은 격리 그룹에 놓지 않는 것입니다. 격리 그룹은 랙이나 가용 영역 같은 장애 도메인이며, 이 조건만 지키면 어느 노드든 어느 샤드를 가질 수 있었습니다.
자유롭게 흩어진 샤드는 복구할 때 노드들을 서로 의존하게 만듭니다. 노드가 새로 맡은 샤드의 데이터를 따라잡는 부트스트래핑에서는 그 샤드를 가진 피어에게서 데이터를 복제해야 합니다. 통신 상대를 따로 고르는 여지가 없습니다. 앞서 복제본을 어디에 배치했느냐가 복구에 관여할 노드까지 결정합니다.
격리 그룹을 어떻게 설정하느냐에 따라 의존 범위는 달라집니다. 노드마다 별도 그룹을 주면 샤드가 자유롭게 움직여 모든 노드가 연결된 의존 그래프가 생기고, 어떤 변경이든 O(N)개 노드에 영향을 줍니다. RF=3에서 격리 그룹을 3개 존으로 제한하면 샤드 이동은 존 안으로 묶입니다. 그래도 노드가 데이터를 공유하는 범위는 클러스터의 최대 66.67%에 이릅니다. 이 비율은 RF에 달려 있어 클러스터를 키워도 줄지 않습니다.
정비할 노드가 서로 다른 격리 그룹에 있다는 것만으로는 충분하지 않았습니다. 두 노드가 같은 샤드를 공유하는 일이 흔했기 때문입니다. 장애 하나가 넓은 범위에 복구 부하와 운영 소음을 만들고, 유지보수도 병렬로 진행하기 어려운 배치였습니다.
샤드 공유의 경계를 정한 서브클러스터
Uber는 노드가 샤드를 공유할 수 있는 범위부터 줄였습니다. 노드를 고정 크기의 서브클러스터로 나누고, 각 그룹에 서로 겹치지 않는 샤드 구간을 배정했습니다. 배치가 안정된 상태에서는 다른 서브클러스터와 샤드를 공유하지 않으며, 각 그룹 안에서 복제와 복구를 감당합니다.
노드 12개에 RF=3, 서브클러스터당 노드 6개라면 그룹은 2개입니다. 각 서브클러스터는 격리 그룹마다 노드 2개를 두고 전체 샤드의 정확히 절반을 소유합니다. 복제본을 서로 다른 격리 그룹에 두는 조건은 그대로 지키면서, 샤드를 공유하는 노드의 범위만 좁힌 배치입니다.
이제 노드 하나가 내려가도 복구 작업은 그 서브클러스터 안에서 끝납니다. 유지보수 자동화도 여러 서브클러스터에서 서로 조율할 부담 없이 병렬로 작업할 수 있습니다. 어떤 노드와 상호작용할지가 작고 고정된 집합으로 정해져 변경의 영향을 예측하기도 쉬워집니다. 샤드 공유로 생기는 의존 범위가 O(클러스터)에서 O(서브클러스터)로 줄면서, 촘촘하던 의존 그래프가 성겨진 것입니다.
그 경계를 유지하려면 배치에 제약이 붙습니다. 하드웨어는 동질적이어야 하며, 알고리즘은 아래 조건을 지킵니다.
- 모든 인스턴스의 가중치 동일
- 격리 그룹 수와 RF 일치
- 서브클러스터당 노드 수인
instancesPerSubcluster는 RF의 배수
초기화할 때 노드를 instancesPerSubcluster 단위로 묶고 샤드 공간을 균등하게 나눕니다. 나누어떨어지지 않은 샤드는 하나씩 배분해 균형을 맞춥니다. 그룹 안의 배치는 기존 샤디드 알고리즘이 맡아 격리 그룹 제약을 지키며 노드에 샤드를 분산합니다.
운영 방식에도 조건이 있습니다. 클러스터 크기는 서브클러스터 크기의 배수 단위로 바꿔야 하고, 복제 인수를 바꾸는 AddReplica는 지원하지 않습니다. 장애 범위를 줄이는 효과를 크게 얻으려면 서브클러스터가 전체 클러스터보다 충분히 작아야 합니다. 작은 클러스터나 이런 단위의 확장이 현실적이지 않은 환경에는 기존 샤디드 배치가 여전히 알맞습니다.
부트스트래핑 폭풍을 피하는 인스턴스 단위 인터페이스
노드를 그룹으로 묶었다고 해서 운영 도구까지 그룹 단위로 바꾸지는 않았습니다. Uber는 원자적으로 서브클러스터를 추가하거나 제거하는 AddSubcluster, RemoveSubcluster를 도입하는 대신, 기존 인스턴스 단위 메서드를 유지했습니다.
호환성이 한 이유였습니다. 기존 호출자와 도구는 코드를 수정하지 않아도 되고, 내장 배치 플래그를 바꾸는 설정 변경만으로 새 알고리즘으로 이전할 수 있습니다. 서브클러스터는 배치 알고리즘 내부의 개념으로 남습니다.
부하도 한꺼번에 몰리지 않아야 했습니다. 서브클러스터 전체를 원자적으로 추가하거나 제거하면 읽기 트래픽과 마이그레이션이 급증하는 부트스트래핑 폭풍을 일으킬 수 있습니다. 기존 AddInstances와 RemoveInstances는 노드를 하나씩 순차적으로 바꿔 부하를 시간에 걸쳐 분산합니다. 최종 클러스터 크기는 서브클러스터 단위로 맞추되, 그 상태에 도달하는 작업은 노드 단위로 진행하는 방식입니다.
증설과 축소 때 잠시 풀리는 서브클러스터 경계
노드를 하나씩 바꾸는 동안에는 완성되지 않은 서브클러스터가 생깁니다. 안정 상태에서 지키던 샤드 공유의 경계도 잠시 열립니다. 이때 허용하는 것은 서브클러스터 사이의 공유이며, 복제본을 서로 다른 격리 그룹에 두는 규칙은 한 번도 완화하지 않습니다.
증설할 때 새 노드는 덜 찬 서브클러스터부터 채우고, 그 뒤에 새 그룹을 만듭니다. AddInstances로 그룹을 점진적으로 구성하는 동안에는 샤드가 기존 그룹과 새로 만드는 그룹에 걸쳐 존재합니다. 서브클러스터를 넘는 이동도 격리 그룹 제약을 지키며, 작업이 끝나면 일시적인 공유도 끝납니다.
축소할 때는 샤드가 여러 서브클러스터에 흩어져 남지 않도록 해야 합니다. 인스턴스는 하나씩 제거하더라도, 한 샤드의 모든 복제본은 같은 대상 서브클러스터로 옮깁니다. 제거할 그룹 안의 다른 노드를 거쳤다가 다시 옮기는 일도 피합니다. 처음부터 목적지 서브클러스터로 보내는 방식입니다.
완성되지 않은 서브클러스터는 한 번에 하나만 허용합니다. validatePartialSubclusters가 이를 검사해 작업의 중첩을 막습니다. 작업을 자유롭게 겹칠 수 있는 여지는 줄지만, 전환 중의 상태를 이해하고 문제가 생겼을 때 복구하기는 쉬워집니다. 잠시 서브클러스터 경계를 넘더라도 복제본들은 항상 서로 다른 격리 그룹에 있으므로 장애 격리는 유지됩니다.
균형을 나중에 고칠 때 치르는 샤드 이동 비용
새 서브클러스터의 샤드는 기존 그룹들이 일부씩 내줘야 합니다. 여기서 어려운 일은 수량을 맞추는 데 그치지 않습니다. 같은 수를 내주더라도 어떤 샤드를 고르느냐에 따라 남은 노드들의 부하가 달라집니다.
그 차이를 나타내는 값이 서브클러스터 내부 스큐입니다. 한 그룹에서 샤드를 가장 많이 가진 노드의 샤드 수와 가장 적게 가진 노드의 샤드 수를 뺀 값입니다. 스큐가 커지면 샤드가 많은 노드는 읽기·쓰기 트래픽뿐 아니라 부트스트래핑 작업과 메모리 압박도 더 받습니다. 그룹 사이의 의존을 끊었어도, 내부에 부하가 쏠리면 각 그룹이 스스로 부하를 감당한다는 설계가 흔들립니다.
RF=3인 6노드 서브클러스터를 예로 들 수 있습니다. 존마다 A11/A21, B11/B21, C11/C21처럼 노드가 2개씩 있고, 고유 샤드 400개의 복제본을 노드당 200개씩 가진 상태입니다. 여기서 새 서브클러스터에 샤드 200개를 내줘야 합니다. 무작위로 고르면 특정 노드가 가진 샤드를 지나치게 많이 뽑을 수 있습니다. 그 결과 한 노드에는 50개, 다른 노드에는 150개가 남을 수 있습니다.
일단 내주고 나중에 리밸런싱하면 어떨까요? 균형은 고칠 수 있지만 샤드를 두 번 옮기게 됩니다. 새 그룹에 내주려고 한 번, 남은 노드의 균형을 고치려고 다시 한 번입니다. 샤드는 한 번만 옮겨도 비용이 큽니다. 데이터를 네트워크로 전송해야 하고, 받는 노드에서는 과거 데이터를 재생하는 부트스트래핑도 수행해야 합니다. 사후 리밸런싱은 그 비용을 한 차례 더 치르게 합니다.
Uber는 내줄 샤드를 고르는 단계에서부터 남은 노드의 균형을 계산했습니다. 이동 내내 균형을 유지해 나중에 교정하려고 다시 옮기는 일을 피하려는 선택입니다.
샤드 1 다음에 샤드 6을 고르는 탐욕 선택
탐욕 알고리즘은 각 후보 샤드를 내준 뒤의 상태를 미리 계산합니다. 해당 샤드의 모든 복제본을 서브클러스터에서 제거한다고 가정하고, 복제본을 가진 각 노드의 샤드 수를 하나씩 줄여 봅니다. 그 상태에서 max_count - min_count를 계산하면 샤드를 내준 뒤의 스큐를 알 수 있습니다.
후보마다 구한 샤드와 스큐의 쌍을 스큐가 작은 순서로 정렬합니다. 남은 노드들을 가장 균형 있게 만드는 샤드부터 내주는 방식입니다. 하나를 골랐다면 그 결과로 바뀐 노드별 샤드 수를 기준으로 남은 후보를 평가합니다. 처음의 균형만 보고 이동 순서를 정할 수는 없습니다.
RF=3, 노드 6개, 존마다 노드 2개인 그룹에 샤드 8개를 배치한 예시를 보면 차이가 드러납니다. 첫 라운드에는 배치가 완전히 대칭이어서 어느 샤드를 빼도 스큐가 1입니다. 알고리즘은 그중 샤드 1을 고릅니다.
이제 남은 7개 후보의 조건은 같지 않습니다. A1, B1, C1에는 샤드가 각각 3개, A2, B2, C2에는 각각 4개 남아 있습니다. 이미 샤드가 적어진 노드에서 다시 빼는 후보를 고르면 스큐가 커집니다. 이 상태에서 제거 후 스큐가 0인 후보는 샤드 6뿐입니다. 그래서 다음으로 내줄 샤드는 6입니다. 연이어 고른 샤드의 복제본이 서로 다른 노드에 분포하도록 선택하면, 특정 노드에서만 계속 샤드가 빠지는 일을 막고 전체 부하를 고르게 줄일 수 있습니다.
매번 가장 좋아 보이는 선택이 전체 순서의 최적해를 보장하지는 않습니다. 최적 순서를 찾으려면 모든 부분집합을 평가하는 지수 시간 탐색이 필요합니다. 1200개 샤드 중 600개를 내주는 경우라면 실행하기 어려운 탐색량입니다.
탐욕 방식은 그 탐색을 근사합니다. 정렬 비용은 O(S log S), 노드별 샤드 수를 바꿔 보는 시뮬레이션 비용은 O(S × N)입니다. S는 샤드 수이며 N은 서브클러스터 안의 노드 수입니다. 실제로는 두 수가 모두 작고, 적용 결과에서도 마이그레이션을 마친 뒤 샤드를 내준 그룹의 스큐는 거의 0에 가까웠습니다. 샤드를 내보낼 순서를 먼저 계산한 덕분에, 남은 노드의 균형을 고치기 위한 추가 이동을 피했습니다.
설계 조건과 예시 수치
| 항목 | 값 |
|---|---|
| 샤디드 배치에서 노드가 데이터를 공유하는 범위 | RF=3일 때 클러스터의 최대 66.67% |
| 샤디드 배치의 노드 장애 영향 범위 | 클러스터의 최대 (n-1)/n |
| 서브클러스터 예시 | 노드 12개, RF=3, 서브클러스터당 6노드, 서브클러스터 2개, 각각 샤드 절반 |
| 불변식 | 인스턴스 가중치 동일, 격리 그룹 수 = RF, instancesPerSubcluster는 RF의 배수 |
| 스큐 예시 | 6노드 서브클러스터, 고유 샤드 400개, 노드당 200개, 200개 기부 |
| 무작위 기부 시 불균형 예 | 한 노드 50개, 다른 노드 150개 |
| 탐욕 선택 복잡도 | 시간 O(S log S), 시뮬레이션 O(S × N) |
| 최적 탐색이 불가능한 예 | 1200개 샤드 중 600개 기부 |
| 동시에 존재할 수 있는 부분 서브클러스터 | 1개 (validatePartialSubclusters로 강제) |