06장. 파티셔닝

대용량 데이터셋을 파티셔닝하는 몇 가지 방법을 살펴보고 인덱스와 파티셔닝이 어떻게 상호작용하는지 살펴보자 클러스터에 노드를 추가하거나 제거할 때 필요한 재균형화(리밸런싱)에 대해서 살펴보자 데이터베이스가 어떻게 요청을 올바른 파티션에 전달하고 질의를 실행하는지 살펴보자

0. 파티셔닝

• 데이터셋이 매우 크거나 질의 처리량이 매우 높다면 복제만으로는 부족하고 데이터를 파티션으로 쪼갤 필요가 있는 이 작업을 샤딩이라고 함
• 여기서 말하는 파티션은?
  • 몽고DB, 엘라스틱서치, 솔라클라우드의 샤드에 해당함
  • HBase: 리전
  • 빅테이블: 테블릿
  • 카산드라/리악: 브이노드(vnode)
  • 카우치베이스: 브이버켓(vBucket)
• 파티셔닝의 주된 이유는 확장성
• 비공유 클러스터(shard-nothing cluster)에서 다른 파티션은 다른 노드에 저장될 수 있음
• 대용량 데이터셋이 여러 디스크에 분산될 수 있고 질의 부하는 여러 프로세서에 분산될 수 있음
• 각 노드에서 자신의 파티션에 해당하는 질의를 독립적으로 실행할 수 있으므로 노드를 추가함으로써 질의 처리량을 늘릴 수 있음
  • 여러 노드에서 병렬 실행이 가능함

1. 파티셔닝과 복제

• 보통 복제와 파티셔닝을 함께 적용해 각 파티션의 복사본을 여러 노드에 저장
  • 여러 다른 노드에 데이터를 저장하여 내결함성을 보장할 수 있다는 의미
• 한 노드에 여러 파티션을 저장할 수도 있음
  • 리더/팔로워 복제 모델을 사용한다면 각 파티션의 리더는 하나의 노드에 할당됨
  • 각 노드는 파티션에 따라 리더이면서 팔로워가 될 수 있음
• 5장 복제에 대한 모든 내용은 파티션의 복제에도 동일하게 적용됨

2. 키-값 데이터 파티셔닝

• 파티셔닝의 목적은 데이터와 질의 부하를 노드 사이에 고르게 분산시키는 것
• 트래픽이 동일하다면 10대의 노드를 사용하면 한 대를 사용할 때보다 10배의 데이터를 저장, 쓰기 요청 처리가 가능 (일단 복제 무시)
• 특정 파티션에 데이터가 많거나 질의를 많이 받으면 쏠렸다(skewed)고 말함
  • 파티셔닝의 효과가 매우 떨어짐
  • 모든 부하가 한 파티션에 몰려 병목이 될 수 있음
  • 불균형하게 부하가 높은 파티션: 핫스팟
• 핫스팟을 회피하는 가장 단순한 방법
  • 레코드를 할당할 노드를 무작위로 선택
  • 어떤 레코드를 읽으려고 할 때 레코드가 어느 노드에 저장됐는지 알 수 없으므로 모든 노드 병렬 질의 필요
• 단순한 키-값 모델
  • 기본키를 통해 레코드에 접근
  • 예시) 백과사전 알파벳 순 정렬

2.1. 키 범위 기준 파티셔닝

• 백과사전처럼 각 파티션에 연속된 범위의 키를 할당하는 것
• 각 범위들 사이의 경계를 알면 키가 어느 파티션에 속하는지 쉽게 찾을 수 있음
• 어떤 파티션이 어느 노드에 할당됐는지 알면 적절한 노드로 요청을 직접 보낼 수 있음
• 키 범위가 동일할 필요는 없으나 데이터를 고르게 분산시키려면 파티션 경계를 데이터에 맞춰 조정해야 함
• 파티션의 경계는 관리자가 수동으로 선택하거나 데이터베이스에서 자동으로 선택되게 할 수 있음
  • 파티션 재균형화
  • 빅테이블, HBase, 리싱크DB, 몽고DB 2.4 이전
• 각 파티션의 키를 정렬된 순서로 저장 가능 (SS테이블, LSM 트리)
• 키를 연쇄된 색인으로 간주해서 질의 하나로 관련 레코드 여러 개를 읽어오는데 사용 가능 (범위 질의)
  • 다중 칼럼 색인
  • 키를 타임스탬프로 사용하는 경우
• 키 범위 기준 파티셔닝은 패턴에 따라 핫스팟을 유발하는 단점이 존재
• 회피 방법
  • 키의 첫 번째 요소로 타임스탬프가 아닌 다른 것을 사용
  • 만약 이름을 첫 번째 키로 사용한다면 이름 마다 범위 질의가 필요함

2.2. 키의 해시값 기준 파티셔닝

• 핫스팟 위험으로 많은 분산 데이터스토어는 키의 파티션을 정하는 데 해시 함수를 사용함
• 좋은 해시 함수는 쏠린 데이터를 입력으로 받아 균일하게 분산되게 함
• 파티셔닝용 해시 함수는 암호적으로 강력할 필요 없음
  • 카산드라, 몽고DB: MD5
  • 볼드모트: 파울러 놀 보(Fowler-Noll-Vo)
  • 자바의 Object.hashCode() 함수는 데이터마다 다른 해시 반환 가능하므로 적합하지 않음
• 각 파티션에 해시값 변위를 할당하고 해시값이 파티션의 범위에 속하는 모든 키를 그 파티션에 할당
• 키를 파티션 사이에 균일하게 분산시키는데 적합함
• 키의 해시값을 사용해서 파티셔닝하면 키 범위 파티셔닝의 장점인 효율적인 범위 질의가 불가능함
  • 인접했던 키가 여러 파티션에 흩어져 정렬 순서 유지 불가
  • 몽고DB: 해시 기반 샤딩 모드를 활성화하면 범위 질의가 모든 파티션에 전송됨
  • 리악/카우치베이스/볼드모트: 기본키에 대한 범위 질의 불가
  • 카산드라
    • 두 가지 파티셔닝 전략 사이에서 타협
    • 테이블을 선언할 때 복합 기본키 지정 가능
    • 키의 첫 부분에만 해싱하고 파티션을 결정
    • 남은 컬럼은 카산드라 SS테이블에서 데이터를 정렬하는 연쇄된 색인으로 사용
    • 복합 키의 첫 번째 컬럼에 대해서는 값 범위로 검색하는 질의가 불가능하지만 첫 번재 컬럼에 고정된 값을 지정하면 다른 컬럼에 대해서는 범위 스캔을 효율적으로 실행 가능
    • 연쇄된 색을 사용하여 일대다 관계를 표현하는 모델을 만들 수 있음
      • 소셜미디어 사용자 한 명이 수정한 문서 여러개를 올리기
      • user_id, updated_timestamp 키로 특정 사용자의 시간 범위 문서 읽기

2.2.1. 일관성 해싱

• CDN 규모의 캐시 시스템에서 부하를 균등하게 분산시키는 방법
• 중앙 제어나 분산 합의가 필요하지 않도록 파티션 경계를 무작위로 선택
• 일관성: 복제 일관성이나 ACID 일관성과는 관련이 없으며 특별한 재균형화 방법을 의미
• 데이터베이스에서 실제로는 잘 동작하지 않아서 현실에서 거의 사용되지 않음
• 일관성 해싱이라는 단어 대신 해싱 파티셔닝이라고 하는게 더 좋음

2.3. 쏠린 작업부하와 핫스팟 완화

• 키를 해싱해서 파티션을 정하면 핫스팟을 줄이는데 도움이 되지만 항상 동일한 키를 읽고 쓰는 극단적인 상황에서는 모든 요청이 동일한 파티션으로 쏠리게 됨
• 현대의 데이터스시템 대부분은 크게 쏠린 부하를 자동으로 보정하지 못하므로 애플리케이션에서 쏠림을 완화해야함
  • 간단한 해결책은 키의 시작이나 끝에 임의 숫자를 붙이는 것
  • 다른 키에 쪼개서 쓰면 읽기를 수행할 때 여러개의 키에 해당하는 데이터를 읽어서 조합하는 추가적인 작업이 필요해짐
  • 요청이 몰리는 소수의 키에만 적용하는게 적절함
  • 쓰기 처리량이 낮은 대다수의 키에도 적용하면 불필요한 오버헤드 발생
• 애플리케이션에 대한 트레이드오프를 꼼꼼히 따져볼 필요가 있음

3. 파티셔닝과 보조 색인

• 키-값 데이터 모델은 기본키를 통해서만 레코드에 접근한다면 키로부터 파티션을 결정하고 이를 사용해 해당 키를 담당하는 파티션으로 읽기, 쓰기 요청을 전달할 수 있음
• 보조 색인은 보통 레코드를 유일하게 식별하는 용도가 아니라 특정한 값이 발생한 항목을 검색하는 수단
• 보조 색인은 관계형 데이터베이스의 핵심 요소이며 문서 데이터베이스에서도 흔함
• 많은 키-값 저장소에서는 구현 복잡도가 추가되는 것을 피하려고 보조 색인을 지원하지 않지만 보조 색인은 데이터 모델링에 매우 유용하여 일부 저장소에서 추가함
• 보조 색인은 검색 서버에게는 존재의 이유임 (솔라, 엘라스틱 서치)
• 보조 색인은 파티션에 깔끔하게 대응되지 않는 문제점이 존재함

3.1. 문서 기준 보조 색인 파티셔닝

• 각 문서에는 고유 ID가 존재하고 문서 ID 기준으로 파티셔닝 됨
• ID 외의 특정 필드로 데이터를 검색하려면 보조 색인이 필요함
• 색인을 선언하면 데이터베이스가 자동으로 색인 생성
• 이런 색인을 사용하면 각 파티션은 자신의 보조 색인을 유지하며 그 파티션에 속하는 문서만 담당
• 데이터베이스에 문서 쓰기 작업을 실행할 때에는 쓰려고하는 문서 ID를 포함하는 파티션만 다루면 됨
• 파티셔닝 색인은 지역 색인이라고 함
• 문서 ID에 뭔가 특별한 작업을 하지 않는다면 특정한 조건의 데이터가 동일한 파티션에 저장되리라는 보장이 없음
• 모든 파티션으로 질의를 보내고 얻은 결과를 모두 모아야 함
• 파티셔닝된 데이터베이스에 이런식으로 질의를 보내는 방법: 스캐터/개더 (scatter/gather)
• 보조 색인을 써서 읽는 질의는 큰 비용이 들 수 있음
• 데이터베이스 벤더들은 대부분 보조 색인 질의가 단일 파티션에만 실행되도록 파티셔닝 방식을 권장하지만 항상 가능하지는 않음
• 특히 단일 질의에서 여러 보조 색인을 사용한다면…

3.2. 용어 기준 보조 색인 파티셔닝

• 한 노드에만 색인을 저장하면 해당 노드가 병목이 되어 파티셔닝의 목적을 해칠 수 있음
• 전역 색인도 파티셔닝해야 하지만 기본키 색인과는 다른식으로 할 수 있음
• 알파벳 순처럼 특정 알파벳 범위에 따라 파티션을 나눌 수 있음
• 용어에 따라 색인의 파티션이 결정함 (term-partitioned)
• 용어: 문서에 등장하는 모든 단어 (전문 색인에서 나옴)
• 용어 자체, 용어의 해시값 사용 가능
• 용어 해시값을 사용하여 파티셔닝하면 부하가 좀 더 고르게 분산됨
• 문서 파티셔닝 색인에 비해 전역(용어 파티셔닝) 색인과 비교
  • 읽기: 용어를 포함하는 파티션으로만 요청을 보내면 됨
  • 쓰기: 쓸 문서의 색인이 여러 파티션에 영향을 줄 수 있음
• 용어 파티셔닝 색인을 사용하면 쓰기에 영향받는 모든 파티션에 걸친 분산 트랜잭션을 실행해야하는데 모든 데이터베이스에서 지원하지 않음
• 현실적으로는 전역 보조 색인은 대개 비동기로 갱신됨
• 다이나모DB는 전역 보조 색인을 갱신하는데 1초도 안걸리지만 인프라 결함이 생기면 지연이 길어질 수 있음
• 전역 용어 파티셔닝 색인의 다른 사용처로는 리악의 검색 기능, 오라클 데이터웨어하우스
• 오라클 웨어하우스는 지역 색인과 전역 색인 사이에서 선택 가능

4. 파티션 재균형화

• 시간이 지나면서 데이터베이스의 변화 발생
  • 부하가 늘어나 CPU 추가
  • 데이터셋 크기 증가로 디스크, 램 추가
  • 장비 장애로 교체
• 이러한 변화가 발생하면 데이터와 요청이 한 노드에서 다른 노드로 옮겨져야 함
• 클러스터에서 한 노드가 담당하던 부하를 다른 노드로 옮기는 과정을 재균형화(rebalancing)이라고 함
• 재균형화 요구 사항
  • 부하가 클러스터 내 노드들에 균등하게 분배
  • 재균형화 요청 중에도 읽기, 쓰기 요청을 받아야함
  • 빠르게 재균형화되고 네트워크와 디스크 I/O 부하를 최소화할 수 있도록 데이터가 필요 이상으로 옮겨져서는 안됨

4.1. 재균형화 전략

4.1.1. 쓰면 안되는 방법: 해시값에 모드 N 연산을 실행

• 해시값 기준으로 파티셔닝할 때는 사용 가능한 해시값 범위를 나누고 각 범위를 한 파티션에 할당하는게 최선
• 모드 연산을 사용하지 않는 이유는 노드 개수가 바뀌면 대부분의 키가 노드 사이에 옮겨져야 함
• 재균형화 비용이 지나치게 커짐

4.1.2. 파티션 개수 고정

• 파티션을 노드 대수보다 많이 만들고 각 노드에 여러 파티션을 할당
• 노드가 추가되면 새 노드는 파티션이 다시 균일하게 분배될 때까지 기존 노드에서 파티션을 뺏어옴
• 노드가 제거되면 반대로 기존 노드에 파티션 할당
• 파티션은 노드 사이에서 이동만고 파티션 개수와 파티션 키는 변경되지 않음
• 유일한 변화는 노드에 어떤 파티션이 할당되는가 뿐
• 파티션 할당 변경은 네트워크를 통해 대량의 데이터를 전송해야 하므로 시간이 좀 걸리기 때문에 데이터 전송중인 동안에 읽기나 쓰기가 실행되면 기존 할당된 파티션을 사용
• 이론상으로 클러스터에 성능이 다른 하드웨어가 섞여있다면 성능이 좋은 노드에 파티션을 더 할당하여 부하를 분산할 수 있음
• 보통 데이터베이스가 처음 구축될 때 파티션 개수가 고정되고 이후에 변하지 않음
• 이론적으로는 파티션을 쪼개거나 합치는 게 가능하지만 파티션 개수가 고정되면 운영이 단순해지므로 고정 파티션을 사용하는 데이터베이스는 파티션 분할을 지원하지 않는 경우가 많음
• 처음 설정된 파티션 개수가 최대 노드 개수가 되므로 미래를 예측하여 충분히 높은 값으로 선택해야 함
• 너무 큰 수를 선택하면 개별 파티션 관리 오버헤드로 역효과가 발생할 수 있음
• 전체 데이터셋 크기 변동이 심하면 파티션 개수 예측이 어려움
• 파티션이 너무 크면 리밸런싱 때 노드 장애로부터 복구 비용이 커짐
• 파티션이 너무 작으면 오버헤드가 커짐

4.1.3. 동적 파티셔닝

• 키 범위 파티셔닝을 사용하면 파티션 경계와 개수가 고정되어 불편함
• 파티션 경계를 수동으로 잘못 지정하면 데이터가 A 파티션에 몰리고 B 파티션은 빌 수도 있음
• HBase, 리싱크DB 처럼 키 범위 파티셔닝을 사용하는 데이터베이스는 파티션을 동적으로 생성
• 파티션 크기가 설정 값을 넘어서면 기존 파티션의 절반 정도의 파티션 두개로 쪼갬
• 데이터가 많이 삭제되어 파티션 크기가 임곗값 아래로 떨어지면 인접한 파티션과 합쳐질 수 있음
• B트리 최상위 레벨에서 실행되는 작업과 유사
• 각 노드는 여러 파티션을 담당할 수 있음
• 큰 파티션이 쪼개진 후 부하 균형을 위해 분할된 파티션이 다른 노드로 이동될 수 있음
• HBase의 경우 HDFS를 통해 파티션 파일이 전송됨
• 이점
  • 파티션 개수가 전체 데이터 용량에 맞춰 조정됨
  • 데이터 양이 작으면 파티션 개수가 적어도 되어 오버헤드가 적음
  • 데이터 양이 거대해지면 개별 파티션의 크기는 설정된 최대치로 제한
• 단점
  • 빈 데이터베이스는 파티션 경계의 사전 정보가 없으므로 시작할 때는 파티션이 하나임
  • 데이터셋이 작아지면 특정 노드만 트래픽을 받고 다른 노드들은 유휴 상태가 됨
• 이 문제 완화를 위해 HBase, 몽고DB는 초기 파티션 집합 설정 가능 -> 사전 분할
• 키 범위 파티셔닝의 경우 사전 분할을 하려면 키가 어떤 식으로 분할될지 미리 알아야 함

4.1.4 노드 비례 파티셔닝

• 파티션 개수 고정: 파티션 크기가 데이터셋 크기에 비례함
• 동적 파티셔닝: 파티션 개수가 데이터셋 크기에 비례함
• 카산드라, 케타마에서 사용되는 방법은 파티션 개수가 노드 대수에 비례하게 함
• 노드 당 할당되는 파티션 개수 고정
• 노드 대수가 변함이 없다면 파티션 크기가 데이터셋 크기에 비례해서 증가
• 노드 대수를 늘리면 파티션 크기가 작아짐
• 개별 파티션 크기가 안정적으로 유지됨
• 새 노드가 추가되면 파티션을 무작위로 선택해 반으로 분할하여 새 노드에 할당
• 무작위로 선택하여 균등하지 않은 분할이 생길 수 있지만 평균적으로 기존 노드의 부하에서 균등한 몫을 할당 받음
• 카산드라 3.0에는 불균등한 분할을 회피할 수 있는 대안적인 재균형화 알고리즘 추가됨
• 파티션 경계를 무작위로 선택하려면 해시 기반 파티셔닝 사용
• 이 방법은 일관성 해싱의 원래 정의에 가장 가깝게 대응 (204p)
• 최근에 나온 해시 함수를 사용하면 메타데이터 오버헤드를 낮추면서도 비슷한 효과를 얻을 수 있음

4.2. 운영: 자동 재균형화와 수동 재균형화

• 완전 자동 재균형화, 완전 수동 재균형화 사이에 중간 지점이 있음
• 완전 자동 재균형화는 자동 장애 감지와 조합되면 더 위험할 수 있음
  • 노드 과부화로 일시적인 요청 지연
  • 노드가 죽었다고 간주하고 자동 재균형화 하려고 함
  • 과부화 걸린 노드, 다른 노드들, 네트워크 부하를 더한 연쇄 장애 가능성 존재
• 재균형화에는 사람이 개입하는게 더 좋을 수 있음
• 카우치베이스, 리악, 볼드모트: 자동 파티션 할당을 제안하고 관리자가 확정해야함

5. 요청 라우팅

• 여러 노드에 여러 파티션이 할당이 됨
• 클라이언트에서 요청을 보낼 때 어떤 노드에 요청을 해야할까?
• 데이터베이스에 국한되지 않은 일반적인 문제인 서비스 찾기(service discovery)의 일종
• 주키퍼 같은 코디네이션 서비스를 사용
• 각 노드는 주키퍼에 자신을 등록
• 주키퍼는 파티션과 노드 사이의 할당 정보를 관리
• 라우팅 계층이나 파티션 인지 클라이언트 같은 구성요소들은 주키퍼에 있는 정보를 구독할 수 있음
• 파티션 소유자 변경, 노드 추가/삭제 가 발생하면 주키퍼는 라우팅 계층에 알려서 라우팅 정보를 최신으로 유지할 수 있게 함
• 링크드인 에스프레소: 헬릭스로 클러스터 관리, 헬릭스는 주키퍼에 의존
• HBase, 솔라클라우드, 카프카: 파티션 할당을 추적하는데 주키퍼 사용
• 몽고DB: 설정 서버 구현에 의존, 몽고스 데몬을 라우팅 계층으로 사용
• 카산드라, 리악: 가십 프로토콜을 사용하여 클러스터 상태 변화를 노드 사이에 전파, 외부 코디네이터 서비스에 의존하지 않음
• 카우치베이스: 재균형화를 자동으로 하지 않음. 클러스터 노드로부터 변경된 라우팅 정보를 알아내는 목시(moxi) 라우팅 계층 설정
• 클라이언트는 라우팅 게층을 사용하거나 임의 노드의 IP를 알아내야 함

5.1. 병렬 질의 실행

• 분석용 대규모 병렬 처리(massively parallel processing, MPP) 관게형 데이터베이스 제품은 훨씬 더 복잡한 질의 지원
• MPP 질의 최적화기는 복잡한 질의를 여러 실행 단계와 파티션으로 분해하며 이들 중 다수는 데이터베이스 클러스터 내의 서로 다른 노드에서 병렬적으로 실행될 수 있음
• 데이터셋의 많은 부분을 스캔하는 연산을 포함하는 질의는 특히 병렬 실행의 혜택을 받음