6. 파티셔닝

• 데이터셋이 매우 크거나 질의 처리량이 매우 높다면 복제만으로 부족하며 데이터를 파티션으로 쪼갤 필요가 있으며 이를 샤딩이라고 합니다.
• 파티션을 나눌 때는 보통 각 데이터 단위가 하나의 파티션에 속하게 합니다.
• 데이터 파티셔닝을 원하는 주된 이유는 확장성입니다.
  • 비공유 클러스터에서 다른 파티션은 다른 노드에 저장될 수 있습니다.
  • 따라서 대용량 데이터셋이 여러 디스크에 분산될 수 있고 질의 부하는 여러 프로세서에 분산될 수 있습니다.

아래에서는 대용량 데이터셋을 파티셔닝하는 방법과 데이터 색인과 파티셔닝의 상호작용을 알아보고, 그 다음으로 클러스터에 노드를 추가하거나 클러스터에서 노드를 제거할 때 필요한 재균형화에 대해 설명합니다. 마지막으로 데이터베이스가 어떻게 요청을 올바른 파티션에 전달하고 질의를 실행하는지 개략적으로 봅니다.

파티셔닝과 복제

• 보통 복제와 파티셔닝을 함께 적용해 각 파티션의 복사본들 여러 노드에 저장합니다.
• 한 노드에 여러 파티션을 저장할 수도 있습니다.

키-값 데이터 파티셔닝

• 파티셔닝의 목적은 데이터와 질의 부하를 노드 사이에 고르게 분산시키는 것입니다.
• 파티셔닝이 고르게 이뤄지지 않는 경우, 쏠렸다(skewed) 라고 말하며 파티셔닝의 효과가 매우 떨어집니다.
  • 이때 불균형하게 부하가 높은 파티션을 핫스팟이라고 합니다.
• 핫스팟을 회피하는 가장 단순한 방법은 레코드를 할당할 노드를 무작위로 설정하는 것입니다.
  • 큰 단점으로 어떤 레코드를 읽을 때 해당 레코드를 어느 노드에 저장했는지 알 수 없으므로 모든 노드에서 병렬적으로 질의를 실행해야합니다.
• 더 좋은 방법 중 하나는 책의 목차처럼 기본키를 통해서 레코드를 접근하는 방법이 있습니다.

키 범위 기준 파티셔닝

• 파티셔닝하는 방법 중 하나는 종이 백과사전처럼 각 파티션에 연속된 범위의 키를 할당하는 것입니다.
• 각 범위들 사이의 경계를 알면 어떤 키가 어느 파티션에 속하는지 쉽게 찾을 수 있습니다.
• 키의 범위 크기가 반드시 동일할 필요는 없습니다. 다만, 데이터를 고르게 분산시키려면 파티션 경계를 데이터에 맞춰 조정해야합니다.
• 파티션 경계는 관리자가 수동으로 선택하거나 데이터베이스에서 자동으로 선택되게 할 수 있습니다.
• 각 파티션 내에서는 키를 정렬된 순서로 저장할 수 있습니다.
  • 이를 통해 범위 스캔이 쉬워지는 이점과 키를 연쇄된 색인으로 간주해서 질의 하나로 관련 레코드 여러 개를 읽어오는 데 사용할 수 있습니다.
• 키 범위 기준 파티셔닝은 특정한 접근 패턴이 핫스팟을 유발한다는 단점이 있습니다.
  • ex. 타임스탬프카 키라면 파티션은 시간 범위에 대응되며 최근 시간만 요구되는 상황을 예상할 수 있습니다.
  • 이러한 문제를 해결하기 위해서 키를 첫번째 요소로 사용하지 않아야 합니다.

키의 해시값 기준 파티셔닝

• 쏠림과 핫스팟의 위험 때문에 많은 분산 데이터스토어는 키의 파티션을 정하는 데 해시 함수를 사용합니다.
• 좋은 해시 함수는 쏠린 데이터를 입력받아 균일하게 분산되게 합니다.
• 파티셔닝 해시 함수는 암호적으로 강력할 필요가 없습니다.
• 키에 적합한 해시 함수를 구했다면 각 파티션에 해쉬값 범위를 할당하고 해시값이 파티션의 범위에 속하는 모든 키를 파티션에 할당하면 됩니다.
• 이러한 기법은 파티션 사이에 균일하게 분산시키는데 좋습니다. 이를 일관성 해싱이라고 부릅니다.
• 파티셔닝에 키의 해시값을 사용해서 파티셔닝하면 키 범위 파티셔닝의 좋은 속성을 잃어버립니다.
  • 바로 범위 질의를 효율적으로 실행할 수 있는 능력입니다.
  • 카산드라는 이러한 장점을 위해 복합 기본키를 지정할 수 있습니다. 즉이 경우 첫번째 칼럼에 고정된 값을 지정하면 다른 칼럼에 대해 범위 스캔을 효율적으로 실행할 수 있습니다.
• 연쇄된 색인을 사용하면 일대다 관계를 표현하는 우아한 데이터 모델을 만들 수 있습니다.

일관성 해싱(해시 파티셔닝)

• CDN같은 인터넷 규모의 캐시 시스템에서 부하를 균등하게 시키는 방법
• 파티션 경계를 무작위로 선택합니다.
• 일반적으로 혼용하기 쉬운 단어이므로 해시 파티셔닝 용어로를 사용하는 것이 좋습니다.

쏠린 작업부하와 핫팟 완화

• 키를 해싱해서 파티션을 정하면 핫스팟을 줄이는 데 도움이 됩니다. 그러나 핫스팟을 완전히 제거할 수 없습니다.
  • 항상 동일한 키를 읽고 쓴느 극단적인 상황에서는 모든 요청이 동일한 파티션으로 쏠리게 됩니다.
  • ex. 수만 명의 팔로워를 거느린 유명인인 경우 후폭풍이 발생합니다.
• 현대 데이터 시스템은 대부분 크게 쏠린 작업부하를 자동으로 보정하지 못하므로 애플리케이션에서 쏠림을 완화해야 합니다.
• 다른 키에 쪼개서 쓰면 읽기를 실행할 때 추가적인 작업이 필요해집니다.

파티셔닝과 보조 색인

• 파티셔닝 방식은 키-값 데이터 모델에 의존합니다.
• 레코드를 기본키를 통해서만 접근한다면 키로부터 파티션을 결정하고 이를 사용해 해당 키를 담당하는 파티션으로 읽기 쓰기 요청을 전달할 수 있습니다.
• 보조 색인이 연관되면 상황은 복잡해집니다.
  • 보조 색인은 보통 레코드를 유일하게 식별하는 용도가 아닌 특정한 값이 발생한 항목을 검색하는 수단입니다.
• 보조 색인은 관계형 데이터베이스의 핵심 요소이며 문서 데이터베이스에서도 흔합니다.
  • 많은 키-값 저장소에서는 구현 복잡도가 추가되는 것을 피하려고 보조 색인을 지원하지는 않지만 데이터모델링에서 매우 유용합니다.
  • 보조 색인은 솔라나 ES 같은 검색 서버에서는 존재이 이유입니다.
• 보조 색인은 파티션에 깔끔하게 대응되지 않는 문제점이 있습니다.
  • 보조 색인이 있는 데이터베이스를 파티셔닝하는데 널리 쓰이는 두가지 방법이 문서 기반 파티셔닝과 용어 기반 파티셔닝입니다.

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

• 각 항목에는 문서 ID(document ID) 라고 부르는 고유 ID가 있고 데이터베이스를 문서 ID 기준으로 파티셔닝합니다.
• 문서데이터베이스에서는 필드, 관계형 데이터베이스에서는 칼럼에 보조 색인을 만들어야 합니다.
• 색인을 선언했다면 데이터베이스가 자동으로 색인 생성을 할 수 있습니다.

• 이러한 색인 방법을 사용하면 각 파티션이 완전히 독립적으로 동작합니다.
  • 각 파티션은 자신의 보조 색인을 유지하며 그 파티션에 속하는 문서만 담당합니다.
  • 다른 파티션에 어떤 데이터가 저장되는지 신경쓰지 않습니다.
  • 이러한 이유로 문서 파티셔닝 색인은 지역 색인(local index) 이라고 부릅니다.
• 문서 기준으로 파티셔닝된 색인을 써서 읽을 때는 주의를 기울여야 합니다.
  • 예를 들어 빨간색 자동차를 찾는 경우, 모든 파티션으로 질의를 보내서 얻은 결과를 모두 모아야합니다.
• 파티셔닝된 데이터베이스에 이런 식으로 질의를 보내는 방법을 스캐터/개터(scatter/gather) 라고도 하는데 보조 색인을 써서 읽는 질의는 큰 비용이 들 수 있습니다.
  • 여러 파티션에서 질의를 병렬 실행하더라도 스캐터/개터는 꼬리 지연 시간 증폭이 발생하기 쉽습니다.
  • 그럼에도 보조 색인을 문서 기준으로 파티셔닝하는 경우가 많습니다. (몽고DB, 카산드라, ES 등) 모
  • 일반적으로 보조 색인 질의가 단일 파티션에서만 실행되도록 파티셔닝 방식을 설계하기를 권장하지만 항상 가능하지는 않습니다.

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

• 각 파티션이 자신만의 보조 색인 대신 모든 파티션의 데이터를 담당하는 전역 색인을 만들 수도 있습니다.
• 그러나 한 노드에만 색인을 저장할 수는 없습니다.
  • 해당 노드가 병목이 되어 파티셔닝의 목적을 해치기 때문입니다.
• 전역 색인도 파티셔닝해야 하지만 기본 키 색인과는 다른 식으로 할 수 있습니다.

• 찾고자 하는 용어에 따라 색인의 파티션이 결정되므로 이런 식의색인을 용어 기준으로 파티셔닝됐다(term-partitioned) 라고 합니다.
• 용어라는 이름은 전문 색인에서 나왔으며 문서에 등장하는 모든 단어를 의미합니다. 색인을 파티셔닝할 때 용어 자체를 사용할수도 용어의 해시값을 사용할 수도 잇습니다.
• 문서 파티셔닝 색인에 비해 전역 색인이 가지는 이점은 읽기가 효율적입니다.
  • 클라이언트는 모든 파티션에 스캐터/개더를 실행할 필요없이 원하는 용어를 포함하는 파티션으로만 요청을 보내면 됩니다.
  • 그렇지만 전역 색인은 쓰기가 느리고 복잡하다는 단점이 있습니다.
• 전역 보조 색인은 대개 비동기로 갱신됩니다.

파티션과 재균형화

시간이 지나면 데이터베이스에 변화가 생깁니다.

• 질의 처리량이 증가해서 늘어난 부하를 처리하기 위해 CPU가 추가로 필요한 경우
• 데이터셋 크기 증가로 인한 디스크와 램 추가가 필요한 경우
• 장비에 장애 발생으로 장비가 담당하던 역할을 다른 장비가 받아야하는 경우

데이터와 요청이 한 노드에서 다른 노드로 옮겨져야 합니다. 클러스터에서 한 노드가 담당하던 부하를 다른 노드로 옮기는 과정을 재균형화(rebalancing) 라고 합니다.

일반적으로 재균형화가 실행될 때 보통 만족시킬 것으로 기대되는 최소 요구사항이 있습니다.

• 재균형화 후, 부하가 클러스터 내에 있는 노드들 사이에 균등하게 분배돼야 합니다.
• 재균형화 도중에도 데이터베이스는 읽기 쓰기 요청을 받아들여야 합니다.
• 재균형화가 빨리 실행되고 네트워크와 디스크 I/O 부하를 최소화할 수 있도록 노드들 사이에 데이터가 필요 이상으로 옮겨져서는 안 됩니다.

재균형화 전략

• 파티션을 노드에 할당하는 여러가지 방법이 있습니다.

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

• 모드 N 방식의 문제는 노드 개수 N이 바뀌면 대부분의 키가 노드 사이에 옮겨져야 한다는 점입니다. 즉, 재균형화 비용이 지나치게 큽니다.
• 데이터를 필요 이상으로 이동하지 않는 방법이 필요합니다.

파티션 개수 고정

• 상당히 간단한 해결책은 파티션을 노드 대수보다 많이 만들고 각 노드에 여러 파티션을 할당하는 것입니다.
  • 즉, 노드 10대로 구성된 클러스터 에서 실행되는 데이터베이스는 파티션을 1000개로 쪼개서 각 노드마다 약 100개의 파티션을 할당할 수 있습니다.
• 클러스터에 노드가 추가되면 새 노드는 파티션이 다시 균일하게 분배될 때까지 기존 노드에서 파티션 몇 개를 뺏어올 수 있습니다.
  • 파티션은 노드 사이에서 통째로 이동하기만 합니다.
• 파티션 개수는 바뀌지 않고 파티션에 할당된 키도 변경하지 않으며, 유일한 변화는 노드에 어떤 파티션이 할당되는가 뿐입니다.
• 리악, ES, Couchbase, 볼드모트 등에서 사용됩니다.
• 일반적으로 처음 설정된 파티션 개수가 사용 가능한 노드 대수의 최대치가 되므로 미래에 증가될 것을 수용하기에 충분한 높은 값을 선책하는 것이 좋습니다.
• 전체 데이터셋의 크기 변동이 심하다면 적절한 파티션 개수를 정하기 어렵습니다.

동적 파티셔닝

• 키 범위 파티셔닝을 사용하는 데이버테이스에서는 파티션 경계과 개수가 고정되어 있는게 매우 불편합니다.
  • 파티션경계를 잘못지정하면 모든 데이터가 한 파티션에 저장되고 나머지 파티션은 텅 빌수도 있습니다.
• 이러한 이유로 HBase나 리싱크DB처럼 키 범위 파티셔닝을 사용하는 데이터베이스에서는 파티션을 동적으로 만듭니다.
  • 파티션 크기가 설정된 값을 넘어서면 파티션을 두 개로 쪼개서 각각에 원래 파티션의 절반 정도의 데이터가 포함하게 됩니다.
  • 반대로 데이터가 많이 삭제되어서 파티션 크기가 임곗값 아래로 떨어지면 인접한 파티션과 합쳐질 수 있습니다.
• 파티션 개수가 고정된 경우와 마찬가지로 각 파티션은 노드 하나에 할당되고 각 노드는 여러 파티션을 담당할 수 있습니다.
• 동적 파티셔닝은 파티션 개수가 전체 데이터 용량에 맞춰 조정되는 이점이 있습니다. (파티션 개수가 적어도 되므로 오버헤드도 작습니다.)
• 그러나 빈 데이터베이스는 파티션 경계를 어디로 정해야 하는지에 관한 사전 정보가 없으므로 시작할 때는 파티션이 하나라는 함정이 있습니다.
  • 이 문제를 해결하기 위해 빈 데이터베이스에 초기 파티션 집합을 설정할 수 있게 됩니다. (사전분할, pre-splitting)
• 동적 파티셔닝은 키 범위 파티셔닝에만 적합한 것으은 아니고 해시 파티셔닝에서도 똑같이 사용될 수 있습니다.

노드 비례 파티셔닝

• 동적 파티셔닝에서는 파티션 분할과 병합을 통해 개별 파티션 크기가 어떤 고정된 최솟값과 최댓값 사이에 유지되게 하므로 파티션 개수가 데이터셋 크기에 비례합니다.
  • 반면에 파티션 개수를 고정하면 개별 파티션 크기가 데이터 셋 크기에 비례합니다.
  • 두 경우 모두 파티션 개수는 노드 대수와 독립적입니다.
• 카산드라에서 사용되는 방법은 파티션 개수가 노드 대수에 비례하게 합니다.
  • 즉, 노드당 할당되는 파티션 개수를 고정합니다.
  • 일반적으로 데이터 용량이 클수록 데이터를 저장할 노드도 많이 필요하므로 이 방법을 쓰면 개별 파티션 크기도 상당히 안정적으로 유지됩니다.
• 새 노드가 클러스터에 추가되면 고정된 개수의 파티션을 무작위로 선택해 분할하고 각 분할된 파티션의 절반은 그대로 두고, 다른 정반은 새 노드에 할당합니다.
• 파티션 경계를 무작위로 선택하려면 해시 기반 파티셔닝을 사용해야 합니다.
  • 최근 나온 해시 함수를 쓰면 메타데이터 오버헤드를 낮추면서도 비슷한 효과를 얻을 수 있습니다.

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

• 완전 자동 재균형화와 완전 수동 재균형화 사이에는 중간 지점이 있습니다.
• Couchbase, 리악, 볼드모트는 자동으로 파티션 할당을 제안하지만 반영되려면 관리자가 확정지어야 합니다.

완전 자동 재균형화

• 일상적인 유지보수에 손이 덜 가므로 편리합니다.
• 예측하기 어려운 단점이 있습니다.
• 비용이 큰 연산이므로 네트워크나 노드에 과부하가 걸리기 쉽습니다.
• 자동 장애 감지와 조합되면 위험해질 수도 있습니다.

이러한 이유로 재균형화 과정에 사람이 개입하는 것이 좋을 수도 있습니다.

요청 라우팅

• 클라이언트에서 요청을 보내려고 할 때 어느 노드로 접속해야하는지 아는 문제가 필요하며 이는 데이터베이스에 국한되지 않은 서비스 찾기(service discovery)의 일종입니다.
• 상위 문제에서 보면 이 문제는 다른 접근법이 있습니다.
  • (1) 클라이언트가 아무 노드에 접속한 후, 있으면 사용하고 없으면 올바른 노드로 전달해 응답을 받고 클라에게 응답을 전달합니다.
  • (2) 클라리언트의 모든 요청을 라우팅 계층으로 먼저 보내고, 라우팅 계층에서 각 요청을 처리할 노드를 알아내고 해당 노드로 요청을 전달합니다.
  • (3) 클라이언트가 파티셔닝 방법과 파티션이 어떤 노드에 할당됐는지 알고 있게합니다.

• 모든 경우에 핵심 문제는 라우팅 결정을 내리는 구성요소가 노드에 할당된 파티션의 변경 사항을 어떻게 아는지입니다.
• 일단적으로 많은 분산 데이터 시스템은 클러스터 메타데이터를 추적하기 위해 주키퍼(ZooKeeper) 같은 별도의 코디네이션 서비스를 사용합니다.

• 링크드인의 에스프레소는 헬릭스를 사용해서 클러스터를 관리합니다.,
• HBase, 솔라클라우드, 카프카도 파티션 할당을 추적하는 데 주키퍼를 사용합니다.
• 몽고DB도 아키텍처는 비슷하지만 자체적인 설정 서버(config server) 구현에 의존하고 몽고스(mongos) 데몬을 라우팅 계층으로 사용합니다.
• 카산드라나 리악은 가십 프로토콜(gossip protocol)을 사용해서 클러스터 상태 변화를 노드 사이에 퍼뜨립니다.
• Couchbase는 재균형화를 자동으로 실행하지 않기 때문에 설계가 단순하며, 클러스터 노드로부터 변경된 라우팅 정보를 알아내는 목시(moxi)라는 계층을 설정합니다.

병렬 질의 실행

• 위에서는 단일 키를 읽거나 쓰는 간단한 질의에 대한 이야기였습니다. 이는 대부분의 NoSQL 분산 데이터스토어에서 지원되는 접근 수준입니다.
• 분석용으로 자주 사용되는 대규모 병렬 처리(massively parallel processing, MPP) 관계형 데이터베이스 제품은 훨씬 더 복잡한 종류의 질의를 지원합니다.
  • 이에 대한 내용은 전문적이며 10장에서 추가 설명합니다.

정리

• 대용량 데이터셋을 더욱 작은 데이터셋으로 파티셔닝하는 다양한 방법을 살폈습니다.
• 파티셔닝의 목적은 핫스팟(불균형적으로 높은 부하를 받는 노드)가 생기지 않게 하면서 데이터와 질의 부하를 여러 장비에 균일하게 분배하는 것입니다.
• 주요한 파티셔닝 기법은 아래와 같습니다.
  • 키 범위 파티셔닝, 키가 정렬되어 있고 개별 파티션은 어떤 최솟값과 최댓값 사이에 속하는 모든 키를 담당
  • 해시 파티셔닝, 각 키에 해시 함수를 적용하고 개별 파티션은 특정 범위의 해시값을 담당합니다.
  • 위 두 기법을 섞어서 쓸 수도 있습니다.
• 파티셔닝과 보조 색인 사이의 상호작용에 대해 이야기하였으며, 보조 색인도 파티셔닝이 필요합니다.
  • 문서 파티셔닝 : 보조 색인을 기본키와 같이 저장된 파티션에 저장합니다.
  • 용어 파티셔닝 색인된 값을 가용해 보조 색인을 별도로 파티셔닝을 합니다.
• 단순한 파티션 인지 로드 밸런서에서 복잢한 병렬 질의 처리 엔진까지 질의를 올바른 파티션으로 라우팅하는 기법도 있습니다.
• 설계상 모든 파티션은 대부분 독립적으로 동작합니다. 따라서 여러 장비로 확장될 수 있습니다. (쓰기는 다른 문제)