샤딩

데이터를 조각으로 나눠 서로 다른 서버에 나눠 담는 일입니다. 조각 하나를 샤드라고 부릅니다. 한 대가 감당하지 못하는 양을 여러 대가 나눠 집니다.

상세

책이 많아 책장 하나에 다 안 들어가면 책장을 여러 개 둡니다. ㄱ부터 ㅁ까지는 첫째 책장, ㅂ부터 ㅇ까지는 둘째 책장으로 정해 두면 찾는 책의 제목만 보고 어느 책장으로 갈지 압니다.

샤딩은 하나의 데이터 집합을 서로 겹치지 않는 조각으로 가르는 것입니다. 그리고 각 조각을 서로 다른 노드가 맡습니다. 노드는 데이터를 맡아 두는 서버 한 대를 가리킵니다. 조각 하나를 샤드라고 부릅니다. 어떤 행이나 문서가 어느 샤드로 가는지는 샤드 키가 정합니다.

flowchart TD
    D["데이터 집합"]
    subgraph A["노드 A"]
        S1["샤드 1"]
    end
    subgraph B["노드 B"]
        S2["샤드 2"]
    end
    subgraph C["노드 C"]
        S3["샤드 3"]
    end
    D --> S1
    D --> S2
    D --> S3

한 집합이 겹치지 않는 조각으로 갈리고, 조각마다 다른 노드가 맡습니다. 어느 노드도 전체를 들고 있지 않습니다.

읽거나 쓰는 쪽은 먼저 샤드 키를 뽑습니다. 그 키를 샤드로 옮기는 매핑을 거쳐 해당 노드로 갑니다. 이 계산을 앞단의 라우터가 대신하기도 합니다. 클라이언트가 매핑을 들고 직접 계산하기도 합니다. 샤드를 다른 노드로 옮기는 일도 있습니다. 옮기는 도중에도 읽고 쓰는 요청은 계속 들어옵니다.

flowchart TD
    A["읽기·쓰기 요청"] --> B["샤드 키"]
    B --> C["키를 샤드로 옮기는 매핑"]
    C --> D["샤드 1"]
    C --> E["샤드 2"]
    C --> F["샤드 3"]

복제와는 무엇을 여럿 두느냐가 다릅니다. 복제는 같은 데이터를 여러 곳에 둡니다. 샤딩은 서로 다른 데이터를 여러 곳에 나눠 둡니다. 둘은 배타적이지 않습니다. 샤드마다 복제본을 두는 구성이 흔합니다. 복제본은 원본 샤드와 다른 노드에 둡니다. 그래야 노드 한 대가 죽거나 연결이 끊겨도 그 샤드를 대신 내줄 자리가 남습니다.

block-beta
columns 3
  block:A:1
    columns 1
    a0("노드 A") a1["샤드 1"] a2["샤드 3 복제본"]
  end
  block:B:1
    columns 1
    b0("노드 B") b1["샤드 2"] b2["샤드 1 복제본"]
  end
  block:C:1
    columns 1
    c0("노드 C") c1["샤드 3"] c2["샤드 2 복제본"]
  end

노드마다 자기가 맡은 샤드 하나와 남의 샤드 복제본 하나가 함께 삽니다. 샤드 1 은 노드 A 와 노드 B 두 자리에 있습니다. 데이터를 겹치지 않는 조각으로 가르는 것이 샤딩이고, 같은 조각을 한 벌 더 두는 것이 복제입니다. 복제본을 어느 노드에 두느냐는 구성이 정합니다.

파티셔닝과 헷갈리는 자리도 있습니다. 파티셔닝은 논리적으로 하나인 큰 테이블을 더 작은 물리 조각으로 쪼개는 것을 가리킵니다. 그 조각들이 한 서버 안에 머물러도 파티셔닝입니다. 샤딩은 조각이 노드 경계를 넘어간다는 점이 다릅니다.

같은 것을 부르는 이름은 자리마다 갈립니다. 어떤 저장소는 조각을 파티션이라 부릅니다. 어떤 저장소는 샤드라 부릅니다. 샤드를 더 잘게 나눈 단위에 청크라는 이름을 따로 붙이는 곳도 있습니다.

파티션이라는 낱말에는 뜻이 하나 더 있습니다. 노드 사이의 연결이 끊겨 서로를 못 보게 갈라지는 사고도 파티션이라 부릅니다. 설계로 데이터를 가르는 여기의 파티션과는 다른 것입니다. 이 문서는 헷갈리지 않게 조각을 끝까지 샤드로만 부릅니다.

배경

한 대의 서버가 담을 수 있는 데이터에는 상한이 있습니다. 데이터가 커지면 디스크가 먼저 찹니다. 작업 집합이 메모리보다 커지면 디스크 입출력이 밀립니다. 질의가 몰리면 서버의 연산 능력도 바닥납니다.

상한을 미루는 첫 방법은 더 큰 장비로 갈아타는 것입니다. 이것을 수직 확장이라 부릅니다. 다만 쓸 수 있는 하드웨어 구성에는 현실적인 최대치가 있습니다. 복제도 이 상한을 다 걷어내지는 못합니다. 복제본을 늘리면 읽기는 여러 대로 나눠집니다. 그래도 복제본마다 데이터를 통째로 들고 있어야 합니다. 전체 데이터 크기와 쓰기 부담은 그대로 남습니다.

그래서 데이터 자체를 갈라 여러 대에 나눠 싣습니다. 시스템의 데이터와 부하를 여러 서버로 나눕니다. 용량이 더 필요하면 서버를 붙입니다. 이것이 수평 확장입니다. 대가는 인프라와 운영이 복잡해진다는 것입니다. 데이터를 조각내 나눠 담는 이 일에 붙은 이름이 샤딩입니다.

갈래

갈리는 축은 하나입니다. 샤드 키를 어느 샤드로 보낼지 정하는 방법입니다.

flowchart TD
    K["샤드 키"] --> H["해시 함수"]
    K --> R["값 구간"]
    K --> C["해시 링"]
    K --> L["룩업 표"]
    H --> S["샤드"]
    R --> S
    C --> S
    L --> S

네 갈래는 모두 같은 자리에 놓입니다. 샤드 키를 받아 어느 샤드인지를 내놓는 자리입니다. 그 자리에 해시 함수를 놓는 것이 해시 샤딩, 값 구간을 놓는 것이 범위 샤딩, 해시 링을 놓는 것이 일관성 해싱, 룩업 표를 놓는 것이 룩업 샤딩입니다.

해시 샤딩

샤드 키를 해시한 값으로 조각을 정합니다. MongoDB 는 이 자리에 해시 인덱스를 씁니다. 필드 하나의 해시값을 인덱스 값으로 삼고, 그 값이 샤드 키가 됩니다. 해시를 거치고 나면 값이 가까운 문서끼리 같은 청크나 샤드에 있을 법하지 않게 됩니다.

이 방식은 데이터를 클러스터에 더 고르게 흩는 대신 겨냥한 연산을 브로드캐스트 연산으로 바꾸는 것을 대가로 냅니다. 동등 비교로 들어온 질의는 한 샤드로 겨냥할 수 있습니다. 구간을 훑는 질의는 라우터가 브로드캐스트 연산을 수행할 가능성이 더 큽니다. 샤드 키로 고를 필드는 카디널리티가 커야 합니다. 서로 다른 값이 많아야 한다는 뜻입니다. MongoDB 문서는 ObjectId 나 타임스탬프처럼 단조롭게 변하는 필드에 해시 키가 잘 맞는다고 적습니다.

범위 샤딩

샤드 키 값으로 정해지는 이어진 구간으로 데이터를 가릅니다. 이 모델에서는 값이 가까운 문서끼리 같은 청크나 샤드에 있을 법합니다. 이어진 구간 안의 문서를 겨냥하는 읽기가 효율적으로 도는 것이 그 대가로 얻는 것입니다. 다만 샤드 키를 잘못 고르면 읽기와 쓰기 성능이 모두 떨어질 수 있습니다. MongoDB 에서는 해시 샤딩이나 존에 필요한 설정을 따로 하지 않으면 이 방식이 기본입니다.

단조롭게 커지는 값을 샤드 키로 쓰면 값이 언제나 커지는 쪽으로만 갑니다. 상한이 maxKey 인 청크가 들어오는 삽입의 대부분을 받습니다. 삽입이 그 청크를 가진 샤드 하나로 묶입니다. 쓰기를 여러 샤드로 나눈 이점이 줄거나 사라집니다.

일관성 해싱

노드 수가 바뀔 때 무엇이 옮겨지느냐가 이 갈래를 가릅니다. 키를 노드 수로 나눈 나머지에 배정하는 순진한 해싱은 노드를 하나 더하는 것만으로 거의 모든 매핑을 무효로 만들 수 있습니다. 나눠 담는 자리를 버킷이라 부르기도 합니다. 노드와 같은 것을 가리킵니다. Cassandra 는 대신 노드마다 토큰을 하나 이상 연속된 해시 링 위에 두고, 키를 링 위로 해싱한 뒤 한 방향으로 걸어가서 소유자를 정합니다. 노드 수가 바뀌어도 옮겨야 하는 키가 일부에 그칩니다.

flowchart TD
    subgraph 해시 링
        direction TD
        T1(["토큰 · 노드 A"]) --> T2(["토큰 · 노드 B"])
        T2 --> T3(["토큰 · 노드 C"])
        T3 --> T4(["토큰 · 노드 A"])
        T4 --> T5(["토큰 · 노드 B"])
        T5 --> T6(["토큰 · 노드 C"])
        T6 --> T1
    end
    K["키의 해시값"] -. 한 방향으로 걸어감 .-> T3

링을 한 줄로 펴서 그렸습니다. 오른쪽 끝은 다시 왼쪽 끝으로 이어집니다. 토큰이 링 위에 자리를 잡고, 키는 자기 해시값이 떨어진 자리에서 한 방향으로 걸어가 처음 만나는 토큰의 노드에 앉습니다. 노드 하나가 링 위 여러 자리를 차지하고 있다는 점도 그림에 보입니다.

물리 노드가 적으면 토큰을 고르게 벌려 둬도 링이 균형을 유지하도록 새 노드를 끼워 넣기가 어렵습니다. Dynamo 논문은 이 불균형을 가상 노드로 풉니다. 물리 노드 하나에 링 위의 토큰을 여럿 배정하는 방식입니다. 위 그림에서 노드 A 가 두 자리에 있는 것이 그 모양입니다.

룩업 샤딩

매핑을 계산하지 않고 표에 적어 둡니다. Vitess 는 컬럼 값을 키스페이스 식별자로 옮기는 매핑을 vindex 라 부릅니다. 함수형 vindex 는 해시 함수나 항등 함수 같은 정해진 알고리즘으로 값을 옮깁니다. 룩업 vindex 는 컬럼 값과 키스페이스 식별자의 연결을 만들어 저장해 두고 나중에 꺼내 씁니다.

룩업 vindex 는 MySQL 룩업 테이블로 구현됩니다. 기본 vindex 가 아닌 컬럼을 담은 WHERE 절로 행을 효율적으로 찾아야 할 때 주로 쓰입니다. 매핑이 별도 테이블에 산다는 것이 이 방식의 대가를 정합니다. 삽입할 때마다 계산된 키스페이스 식별자가 그 테이블에도 컬럼 값과 짝지어 적힙니다.

예시

Redis Cluster 의 해시 슬롯

키 공간이 16384 개 슬롯으로 갈립니다. 클러스터 크기의 상한이 마스터 노드 16384 개라는 뜻입니다. 다만 권장하는 최대 노드 수는 1000 개 수준입니다. 마스터 노드마다 16384 슬롯의 부분집합을 맡습니다. 클러스터가 안정 상태이면 슬롯 하나는 노드 하나가 담당합니다.

HASH_SLOT = CRC16(key) mod 16384

CRC16(Cyclic Redundancy Check, 순환 중복 검사)은 XMODEM 규격입니다. 출력 16비트 가운데 14비트만 씁니다. 나머지 연산의 제수가 16384 인 이유가 그것입니다. 새 클러스터를 처음부터 만들 때 각 마스터 노드에 슬롯 묶음을 배정하는 데 주로 쓰는 명령이 ADDSLOTS · ADDSLOTSRANGE 입니다.

MongoDB 의 sh.shardCollection()

sh.shardCollection(namespace, key, unique, options)

key 문서가 샤드 키로 쓸 필드를 지정합니다. 필드 값에 1 을 주면 범위 샤딩입니다. "hashed" 를 주면 해시 샤드 키입니다. 샤드 키는 인덱스가 받쳐 줘야 합니다. 컬렉션이 비어 있지 않다면 그 인덱스가 이 명령보다 먼저 있어야 합니다.

Elasticsearch 의 index.number_of_shards

인덱스가 가질 주 샤드 개수입니다. 기본값은 1 입니다. 인덱스를 만들 때만 정할 수 있습니다. 닫힌 인덱스에서도 바꾸지 못합니다. 인덱스당 상한은 1024 개입니다. 자원 할당 탓에 클러스터가 불안정해지는 인덱스가 실수로 만들어지는 것을 막는 안전 한도입니다.

샤드가 지나치게 많으면 검색 성능이 떨어지고 클러스터가 불안정해질 수 있습니다. 이것을 오버샤딩이라 부릅니다. 크기 지침은 샤드 하나를 10GB 에서 50GB 사이로 두라는 것입니다. 샤드당 문서 수는 2억 건 아래로 유지합니다.

관련 항목

샤딩이 만들어내는 조각과 그 키

샤드 · 샤드 키 · 청크 · 해시 슬롯 · 파티션 · 파티션 키 · 키스페이스 식별자 · 키 공간

샤드 키를 노드로 옮기는 방법

일관성 해싱 · 해시 인덱스 · 해시 함수 · CRC16 · vindex · 매핑 · 인덱스 · 카디널리티 · 타임스탬프

일관성 해싱을 이루는 구조

토큰 · 토큰 링 · 해시 링 · 가상 노드 · 물리 노드

샤드 키 매핑을 계산·중개하는 구성 요소

라우터 · 설정 서버 · 노드 · 마스터 노드 · 클러스터 · 버킷

샤딩과 맞세워지는 개념

복제 · 복제본 · 파티셔닝

샤딩이 비롯된 배경

수직 확장 · 수평 확장 · 스케일 아웃 · 작업 집합 · 질의 · 성능 · 검색

샤딩이 쪼개는 대상

집합 · 컬렉션 · 테이블

샤딩에서 자주 나는 오류·장애

핫스팟 · 오버샤딩 · 브로드캐스트 연산

샤딩을 조정하는 운영 작업

리밸런싱 · 리샤딩 · 존

샤드 경계를 넘나드는 절차

크로스 샤드 조인 · 분산 트랜잭션 · 2단계 커밋

샤딩을 실제로 구현·채택한 제품

MongoDB · Redis · Cassandra · Vitess · Elasticsearch · MySQL · Dynamo