• 데이터셋이 매우 크거나 질의 처리량이 매우 높다면 복제만으로는 부족하고, 데이터를 파티션으로 쪼갤 필요가 있다. 이 작업을 샤딩이라고 한다.
• 각 파티션은 그 자체로 작은 데이터베이스가 된다.
• 데이터 파티셔닝을 원하는 주된 이유는 확장성이다. 대용량 데이터셋이 여러 디스크에 분산될 수 있고 질의 부하는 여러 프로세서에 분산될 수 있다.

파티셔닝과 복제

보통 복제와 파티셔닝을 함께 적용해 각 파티션의 복사본을 여러 노드에 저장한다. 각 레코드는 정확히 한 파티션에 속하더라도 이를 여러 다른 노드에 저장해서 내결함성을 보장한다.

키-값 데이터 파티셔닝

• 파티셔닝의 목적은 데이터와 질의 부하를 노드 사이에 고르게 분산시키는 것이다.
• 파티셔닝이 고르게 이뤄지지 않아 다른 파티션보다 데이터가 많거나 질의를 많이 받는 파티션이 있다면 쏠렸다(skewed)고 하고, 쏠림이 있으면 파티셔닝의 효과가 매우 떨어진다.
• 불균형하게 부하가 높은 파티션을 핫스팟이라고 한다. 핫스팟을 회피하는 간단한 방법은 키-값 데이터 모델을 사용하는 것이다. 항상 기본키를 통해 레코드에 접근한다.
  

키 범위 기준 파티셔닝

• 종이 백과사전처럼 각 파티션에 연속된 범위의 키를 할당하는 것이다. 각 범위들 사이의 경계를 알면 어떤 키가 어느 파티션에 속하는지 쉽게 찾을 수 있다.
• 키 범위 크기가 반드시 동일할 필요는 없다. 데이터가 고르게 분포하지 않을 수도 있기 때문이다. 데이터를 고르게 분산시키려면 파티션 경계를 데이터에 맞춰 조정해야 한다.
• 각 파티션 내에서는 키를 정렬된 순서로 저장할 수 있다. 이렇게 하면 범위 스캔이 쉬워지고, 키를 연쇄된 색인으로 간주해서 질의 하나로 관련 레코드 여러 개를 읽어오는 데 사용할 수 있다.
• 키 범위 기준 파티셔닝은 특정한 접근 패턴이 핫스팟을 유발하는 단점이 있다.

키의 해시값 기준 파티셔닝

• 쏠림과 핫스팟의 위험 때문에 많은 분산 데이터스토어는 키의 파티션을 정하는 데 해시 함수를 사용한다.
• 키에 적합한 해시 함수를 구했다면 각 파티션에 해시값 범위를 할당하고 해시값이 파티션의 범위에 속하는 모든 키를 그 파티션에 할당하면 된다.
• 파티셔닝에 키의 해시값을 사용해서 파티셔닝하면 키 범위 파티셔닝의 좋은 속성인 범위 질의 능력을 잃는다. 인접했던 키들이 여러 파티션에 흩어지기 때문이다.
• 일부 DB는 두가지 파티셔닝 전략 사이에서 타협한다. (카산드라, 다이나모) 테이블을 선언할 때 여러 칼럼을 포함하는 복합 기본키를 지정할 수 있다. 키의 첫 부분에만 해싱을 적용해 파티션 결정에 사용하고, 남은 칼럼은 SS테이블에서 데이터를 정렬하는 연쇄된 색인으로 사용한다. 따라서 복합 키의 첫번째 칼럼에 대해서는 값 범위로 검색하는 질의를 쓸 수 없지만, 첫번째 칼럼에 고정된 값을 지정하면 키의 다른 칼럼에 대해서는 범위 스캔을 효율적으로 실행할 수 있다.
  

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

핫스팟을 완벽히 제거할 수는 없다. ex. 유명인 문제

현대 데이터 시스템은 대부분 크게 쏠린 작업부하를 자동으로 보정하지 못하므로 애플리케이션에서 쏠림을 완화해야 한다.

파티셔닝과 보조 색인

• 보조 색인은 보통 레코드를 유일하게 식별하는 용도가 아니라 특정한 값이 발생한 항목을 검색하는 수단이다.
• 보조 색인은 파티션에 깔끔하게 대응되지 않는 문제점이 있다. 보조 색인이 있는 데이터베이스를 파티셔닝하는 데에 쓰이는 두 가지 방법이 아래 나온다.

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

• 색인을 선언했다면 데이터베이스가 자동으로 색인을 생성할 수 있고, 파티션은 자동으로 색인 항목에 해당하는 문서를 구분한다.
• 이런 색인 방법을 사용하면 각 파티션이 완전히 독립적으로 동작한다. 각 파티션은 자신의 보조 색인을 유지하며 그 파티션에 속하는 문서만 담당한다. 그래서 문서 파티셔닝 색인을 지역 색인이라고도 한다. (local index)
• 특별한 작업을 하지 않으면, 색인에 속하는 모든 문서가 동일한 파티션에 저장되리라는 보장이 없다. 모든 파티션으로 질의를 보내 얻은 결과를 모두 모아야 한다. 이 방법을 스캐터/개더 라고 하는데, 보조 색인을 써서 읽는 질의는 큰 비용이 들 수 있다.
  

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

• 각 파티션이 자신만의 보조 색인(지역 색인)을 갖게 하는 대신, 모든 파티션의 데이터를 담당하는 전역 색인을 만들 수 있다.
• 찾고자 하는 용어에 따라 색인의 파티션이 결정되므로, 이런 식의 색인을 용어 기준 파티셔닝이라고 한다. 용어는 문서에 등장하는 모든 단어를 의미한다.
  
• 장점 읽기가 효율적이다. 클라이언트는 모든 파티션에 스캐터/개더를 실행할 필요 없이 원하는 용어를 포함하는 파티션으로만 요청을 보내면 된다.
  
• 단점 쓰기가 느리고 복잡하다. 단일 문서를 쓸 때, 해당 색인의 여러 파티션에 영향을 줄 수 있다.
  

파티션 재균형화

클러스터에서 한 노드가 담당하던 부하를 다른 노드로 옮기는 과정을 재균형화라고 한다.

• 재균형화의 최소 요구사항
  • 재균형화 후, 부하가 클러스터 내 노드들 사이에 균등하게 분배되야 한다.
  • 재균형화 도중 데이터베이스는 읽기 쓰기 요청을 받아들일 수 있어야 한다.
  • 노드들 사이에 데이터가 필요 이상으로 옮겨져서는 안된다.

재균형화 전략

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

모드 연산은 모듈러 연산을 의미함

모드 N 방식의 문제는 노드 개수 N이 변하면 대부분의 키가 노드 사이에 옮겨져야 한다는 점이다. 키가 자주 이동하면 재균형화 비용이 지나치게 커진다.

파티션 개수 고정

• 파티션 개수는 고정해두고, 클러스터에 노드가 추가되면 새 노드는 파티션이 다시 균일하게 분배될 때까지 기존 노드에서 파티션 몇 개를 뺏어올 수 있다. 제거되면 이와 반대로 실행된다.
• 유일한 변화는 노드에 어떤 파티션이 할당되는가 뿐이다.
• 데이터베이스가 처음 구축될 때 파티션 개수가 고정되고 이후에 변하지 않는다. 처음 설정된 파티션 개수가 사용 가능한 노드 대수의 최대치가 되므로 미래에 증가될 것을 수용하기에 충분히 높은 값으로 설정해야 한다.
  

동적 파티셔닝

• 키 범위 파티셔닝을 사용하는 데이터베이스에서는 파티션 경계와 개수가 고정돼있는 게 매우 불편하다.
• 동적 파티셔닝에서는 파티션이 쪼개지고, 파티션끼리 합쳐질 수 있다.
• 동적 파티셔닝은 파티션 개수가 전체 데이터 용량에 맞춰 조정된다는 이점이 있다.

노드 비례 파티셔닝

• 파티션 개수가 노드 대수에 비례하게 하는 것이다. 노드당 할당되는 파티션 개수를 고정한다.
  
• 새 노드가 클러스터에 추가되면 고정된 개수의 파티션을 무작위로 선택해 분할하고 각 분할된 파티션의 절반은 그대로 두고 다른 절반은 새 노드에 할당한다.

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

완전 자동 재균형화는 일상적인 유지보수에 손이 덜 가므로 편리할 수 있지만, 예측하기 어렵다. 재균형화 과정에 사람이 개입하는 것이 좋을 수 있다.

요청 라우팅

클라이언트에서 요청을 보내려고 할 때 어느 노드로 접속해야 하는지 어떻게 알 수 있을까?

• 몇 가지 접근법 (라우팅 결정을 내리는 구성요소로 구분)
  • 라우팅 결정을 노드 중 하나가 함 클라이언트가 아무 노드에나 접속하게 한다. 접속한 노드에서 올바른 노드로 요청을 전달한다.
    
  • 라우팅 결정을 라우팅 계층에서 함 클라이언트의 모든 요청을 라우팅 계층으로 먼저 보낸다. 라우팅 계층에서는 각 요청을 처리할 노드를 알아내고 그에 따라 해당 노드로 요청을 전달한다. 라우팅 계층은 파티션 인지 로드 밸런서로 동작한다.
    
  • 라우팅 결정을 클라이언트가 함 클라이언트가 파티셔닝 방법과 파티션이 어떤 노드에 할당됐는지를 알고 있어, 직접 접속한다.
    

이 방법들의 핵심 문제는 라우팅 결정을 내리는 구성요소가 노드에 할당된 파티션의 변경 사항을 어떻게 아느냐이다.

많은 분산 데이터 시스템은 클러스터 메타데이터를 추적하기 위해 주키퍼 같은 별도의 코디네이션 서비스를 사용한다.

• 주키퍼 동작 원리 각 노드는 주키퍼에 자신을 등록하고, 주키퍼는 파티션과 노드 사이의 신뢰성있는 할당 정보를 관리한다. 라우팅 계층이나 파티션 인지 클라이언트 같은 다른 구성요소들은 주키퍼에 있는 정보를 구독할 수 있다. 파티션 소유자가 바뀌든지, 노드가 추가되거나 삭제되면 주키퍼는 라우팅 계층에 이를 알려서 라우팅 정보를 최신으로 유지할 수 있게 한다.