Table of Contents
데이터셋이 매우 크거나 질의 처리량이 매우 높다면 복제만으로는 부족하다.
데이터를 파티셔닝으로 나눌 필요가 있다.
파티셔닝은 샤딩이라고도 한다.
파티셔닝을 하는 주요한 이유는 확장성 이다.
비공유 클러스터(shared-nothing cluster)에서 파티션들은 서로 다른 노드에 저장될 수 있다.
그래서 대용량 데이터셋은 여러 디스크로 분산될 수 있고 질의 부하도 여러 프로세서로 분산될 수 있다.
각 노드는 자신의 파티션 질의를 독립적으로 실행할 수 있기에 노드를 추가하는 것만으로 질의 처리량을 확장할 수 있다.
크고 복잡한 질의는 여러 노드에서 병렬로 실행도 가능하다.
하지만 이런 크고 복잡한 질의는 더욱 복잡하고 어려워진다.
파티셔닝과 복제
일반적으로 파티셔닝과 복제를 함께 사용한다.
복제를 통해서 각 파티션의 복사본을 여러 노드에 저장하게 되고 내결함성 을 보장할 수 있다.
복제에 관한 모든 내용은 파티션의 복제에도 동일하게 적용된다.
복제와 파티셔닝의 조합에 대한 예를 살펴보자.
예제와 같이 한 노드에 여러 파티션을 저장할 수도 있다.
또한 각 노드는 어떤 파티션에게는 리더이면서 다른 파티션에게는 팔로워가 될 수 있다.
Key-Value 데이터 파티셔닝
파티셔닝의 목적 : 데이터와 질의 부하를 노드 사이에 고르게 분산시키는 것
용어 설명
- 쏠림(skewed)
파티셔닝으로 여러 노드 사이에 데이터가 고르게 나눠지지 않는다면
데이터가 많거나 질의를 많이 받는 파티션이 생기게 되는데 이때 쏠렸다고 말한다. - 핫스팟(hot spot)
불균형하게 다른 파티션보다 부하가 높은 파티션
데이터베이스에서 파티셔닝을 사용했을 때, 실제 데이터를 어떤 노드에 저장할지에 대해 알아보자.
키 범위 기준 파티셔닝
각 파티션에 연속된 범위의 키를 할당하는 것이다.
특징
- 키 범위 크기가 반드시 동일할 필요가 없음
- 데이터를 고르게 분산시키려면 파티션 경계를 데이터에 맞춰 조정해야 함
- 파티션 경계는 수동 혹은 자동으로 선택 가능
- 각 파티션 내에서는 정렬된 순서로 키를 저장할 수 있음
장점
- 어떤 키가 어느 파티션에 속하는지 쉽게 찾을 수 있음
- 적절한 노드로 요청을 직접 보낼 수 있음
- 4번 특징으로 범위 스캔이 쉬움
- 키를 결합 색인(concatenated index)로 간주해서 질의 하나로 관련 레코드 여러 개를 읽어올 수 있음
단점
- 특정한 접근 패턴이 핫스팟을 유발
키의 해시값 기준 파티셔닝
쏠림과 핫스팟의 위험 때문에 많은 분산 데이터스토어는 키의 파티션을 정하는 데 해시 함수를 사용한다.
각 파티션에 해시값 범위를 할당한다.
해시 함수를 통해 키를 해시 값을 구하고 해당 해시 값이 파티션의 범위에 속하면 해당 파티션에 할당하면 된다.
파티션용 해시 함수의 특징
- 좋은 해시 함수는 쏠린 데이터를 받아 균일하게 분산되도록 할 수 있음
- 암호적으로 강력할 필요가 없음
장점
- 키를 파티션 사이에 균일하게 분산시키는 데 좋음
- 파티션 경계를 크기가 동일하도록 나눌 수도 있고 무작위에 가깝게 선택할 수도 있음
단점
- 범위 질의가 효율적이지 않음
범위 질의를 효율적으로 하기 위해 카산드라는 키 범위 기준과 키의 해시값 기준 두 가지 파티셔닝 전략 사이에서 타협한다.
테이블을 선언할 때 여러 컬럼을 포함하는 복합 기본키를 지정할 수 있다.
- 키의 첫 부분에만 해싱을 적용하고 파티션 결정에 사용
- 나머지 컬럼은 카산드라의 SS테이블에서 데이터를 정렬하는 결합 색인으로 사용
연쇄된 색인을 사용하면 일대다 관계를 표현하는 우아한 데이터 모델을 만들 수 있다.
참고
이런 기법을 일관성 해싱이라고 부르기도 한다.
일관성 해싱은 CDN 같은 인터넷 규모의 캐시 시스템에서 부하를 균등하게 분산시키는 방법이다.
중앙 제어나 분산 합의가 필요하지 않도록 파티션 경계를 무작위로 선택한다.
카산드라의 파티셔닝 기법이 일관성 해싱의 원래 정의에 가장 가깝게 대응한다.
쏠린 작업부하와 핫스팟 완화
키의 해시값 기준 파티셔닝을 사용하면 핫스팟을 줄이는 데 도움이 된다.
하지만 핫스팟을 완벽히 제거할 수는 없다.
항상 동일한 키를 읽고 쓰는 극단적인 상황에서는 모든 요청이 동일한 파티션으로 쏠리게 된다.
현대 데이터 시스템은 대부분 크게 쏠린 작업부하를 자동으로 보정하지 못한다.
그래서 애플리케이션에서 쏠림을 완화해야 한다.
예로 간단한 해결책은 각 키의 시작이나 끝에 임의의 숫자를 붙이는 것이다.
시작에 2개의 숫자를 붙인다면 “[0-9][0-9]키 -> 해시 함수 적용” 와 같다.
- 같은 키라도 100개의 다른 키로 균등하게 나뉘어지며 다른 파티션으로 분산될 수 있음
- 다른 키에 쪼개서 쓰면 읽기를 실행할 때 추가적인 작업이 필요
100개의 키에 해당 하는 데이터를 읽어서 조합해야 하기 때문 - 추가적으로 저장해야 할 정보도 있다.
- 요청이 몰리는 소수의 키에만 적용하는 게 좋음
쓰기 처리량이 낮은 대다수의 키에도 적용하면 불필요한 오버헤드가 발생 - 어떤 키가 쪼개졌는지 추적할 방법 필요
파티셔닝과 보조 색인
보조 색인은 보통 레코드를 유일하게 식별하는 용도가 아니라 특정한 값이 발생한 항목을 검색하는 수단이다.
많은 키-값 저장소에서는 구현 복잡도가 추가되는 것을 피하기 위해 파티션에서 보조 색인을 지원하지 않는다.
하지만 보조 색인은 데이터 모델링에 매우 유용하며, 솔라나 엘라스틱서치 같은 검색 서버에게는 존재 이유이기도 하다.
보조 색인은 파티션에 깔끔하게 대응되지 않는 문제점이 있다.
이제 파티셔닝에서 보조 색인을 사용하는 대표적인 2가지 방법에 대해 살펴보자.
문서 기준 보조 색인 파티셔닝
보조 색인을 살펴보기 위해 중고차를 판매하는 웹사이트를 운영한다고 가정하고 예제를 살펴보자.
각 항목에는 문서 ID(document ID)라 불리는 고유 ID가 있고 데이터베이스를 *문서 ID 기준(키 범위 기준 파티셔닝)으로 파티셔닝한다.
각 파티션은 완전히 독립적으로 동작하며 보조 색인은 자신이 속한 파티션의 문서만 담당한다.
그래서 문서 기준 보조 색인 파티셔닝은 지역 색인(local index)라고도 한다.
특징
- 보조색인을 통해 질의하고 싶다면, 모든 파티션으로 질의를 해야 함
그리고 얻은 결과를 모두 합쳐야 한다.
이런 방법을 스캐터/개더(scatter/gather)라고 한다. - 질의를 병렬 실행 가능
- 보조색인을 사용한 읽기 질의는 큰 비용이 들 수 있음
병렬 실행을 하더라도 꼬리 지연 시간 증폭이 발생하기 쉬움
용어 기준 보조 색인 파티셔닝
용어란 문서에 등장하는 모든 단어를 말한다.
용어라는 이름은 전문 색인에서 나왔다.
위의 그림을 보면 color와 make란 속성의 black, red, silver, yellow, audi 등 용어가 존재한다.
또한 파티션 별로 용어는 겹치지 않고 각 파티션에 고유한 용어가 할당되어 있다.
즉, 용어 기준으로 파티셔닝 됐다고 한다.
각 보조 색인들은 해당 파티션의 문서 ID 뿐만 아니라 다른 파티션의 문서 ID도 포함한다.
그래서 전역 색인 이라고 부른다.
여기서 색인을 파티셔닝할 때, 키-값 데이터 파티셔닝과 동일하게 파티셔닝할 수 있다.
여기서는 키가 용어라고 생각하면 된다.
- 키(용어) 범위 기준 파티셔닝
- 키(용어)의 해시값 기준 파티셔닝
위의 단어는 키-값 데이터 파티셔닝의 방식과 쉽게 매칭하기 위해 단어를 그대로 사용했다.
실제 단어는 아닐 수 있다.
특징
- 문서 기준 보조색인 파티셔닝 대비 읽기가 효율적
스캐터/개더를 실행할 필요 없이 대상 파티션에 요청 가능 - 쓰기가 느리고 복잡하다
단일 문서를 쓸 때 여러 파티션에 영향을 줄 수 있음
이상적으로는 색인은 항상 최신 상태를 유지해야 한다.
이를 위해서는 용어 파티셔닝 색인을 사용할 때 쓰기에 영향 받는 모든 파티션에 걸친 분산 트랜잭션을 실행해야 한다.
하지만 모든 데이터베이스에서 분산 트랙잭션을 지원하지 않는다.
현실에서는 전역 보조 색인은 대개 비동기로 갱신된다.
이로 인해서 쓰기를 수행 후 바로 색인이 반영되지 않을 수도 있다.
파티션 재균형화
시간이 지나면 데이터베이스에 변화가 생긴다.
- 질의 처리량이 증가해 CPU를 추가하고 싶다.
- 데이터셋 크기가 증가해 디스크와 램을 추가하고 싶다.
- 장비에 장애가 발생해 역활을 다른 장비로 옮기고 싶다.
이런 변화가 생기면 데이터와 요청이 한 노드에서 다른 노드로 옮겨져야 한다.
클러스터에서 한 노드가 담당하던 부하를 다른 노드로 옮기는 과정을 재균형화(rebalancing) 라고 한다.
재균형화가 실행될 때 보통 만족시킬 것으로 기대하는 최소 요구사항
- 재균형화 후, 부하가 클러스터 내에 있는 노드들 사이에 균등하게 분배돼야 한다.
- 재균형화 중, 읽기 쓰기 요청을 받을 수 있어야 한다.
- 재균형화가 빨리 완료되고 네트워크와 디스크 I/O 부하를 최소화할 수 있도록
노드 사이에 데이터가 필요 이상으로 옮겨서는 안 된다.
재균형화 전략
쓰면 안 되는 방법: hash mod N
모드 N 방식의 문제는 노드 개수 N이 바뀌면 대부분의 키가 노드 사이에 옮겨져야 한다는 점이다.
키가 자주 이동하면 재균형화 비용이 지나치게 커진다.
데이터를 필요 이상으로 이동하지 않는 방법이 필요 하다.
파티션 개수 고정
상당히 간단한 해결책으로 파티션을 노드 대수보다 많이 만들고 각 노드에 여러 파티션을 할당하는 것이다.
클러스터에 새로운 노드가 추가된 경우, 신규 노드는 파티션이 다시 균일하게 분배가 될 때까지 기존의 노드에서 파티션 몇 개를 가져올 수 있다.
클러스터에서 노드가 제거된 경우, 이 과정을 반대로 수행하면 된다.
클러스터에 새로운 노드가 추가된 경우의 과정은 아래 그림을 참고하자
특징
- 노드 사이에서 파티션은 통째로 이동 시키며, 파티션의 개수와 파티션에 할당된 키도 변경되지 않음
유일한 변화는 노드에 어떤 파티션이 할당되는가 뿐이다. - 보통 데이터베이스가 처음 구축될 때 파티션 개수가 고정되고 이후에 변하지 않음
전체 데이터셋의 크기 변동이 심하다면 적절한 파티션 개수를 정하기 어렵다.
파티션이 너무 크면 재균형화를 실행할 때와 노드 장애로부터 복구할 때 비용이 커진다.
하지만 파티션이 너무 작으면 오버헤드가 너무 커진다.
동적 파티셔닝
파티션 경계와 개수가 고정돼 있는 게 매우 불편할 수 있다.
처음에 절적한 파티션 개수를 정하기 어려운데, 잘 못 지정할 경우 쏠림 현상이 발생할 수 있다.
또한 파티션 경계를 수동으로 재설정하는 것은 매우 성가시다.
이런 이유로 동적 파티셔닝을 지원하는 데이터베이스들이 있다.(HBase, 리싱크DB 등)
동적 파티셔닝은 설정 값을 기준으로 동적으로 파티션을 나누거나 합친다.
- 파티션 크기가 설정된 값을 넘어서면
파티션을 두 개로 나누고 대략 반의 데이터를 각각 나눠 가진다. - 데이터가 많이 삭되어 임계값 아래로 떨어지면
인접한 파티션과 합쳐질 수 있다.
특징
- 큰 파티션이 쪼개진 후 부하의 균형을 맞추기 위해 분할된 파티션 중 하나가 다른 노드로 이동될 수 있다.
- 파티션 개수가 전체 데이터 용량에 맞춰 조정(장점)
데이터 양이 적으면 파티션 개수가 적어 오버헤드도 적다 - 키 범위 파티셔닝과 해시 파티셔닝 모두 사용 가능
문제점으로 시작할 때는 파티션이 하나라는 점이다.
이 문제를 완화하기 위해 HBase와 몽고DB는 빈 데이터베이스에 초기 파티션 집합을 설정할 수 있게 한다.
이것을 사전 분할(pre-splitting)이라 한다.
노드 비례 파티셔닝
고정 파티셔닝과 동적 파티셔닝 모두 파티션 개수는 노드 대수와 독립적이다.
반면 해당 방법은 노드 대수에 비례하게 하는 것이다.
즉, 노드당 할당되는 파티션 개수를 고정한다.
노드의 수가 변함 없는 동안은 개별 파티션 크기가 데이터셋 크기에 비례해서 증가한다.
노드 수를 늘리면 파티션 크기는 다시 작아진다.
일반적으로 데이터 용량이 클수록 데이터를 저장하는 노드도 많이 필요하므로 이 방법을 쓰면 개별 파티션 크기도 상당히 안정적으로 유지된다.
새 노드가 클러스터에 추가되면
- 고정된 개수의 파티션을 무작위로 선택해 분할하고
각 분할된 파티션의 절반은 그대로 두고 다른 절반은 새 노드에 할당한다. - 파티션을 무작위로 선택해서 균등하지 않은 분할이 생길 수 있다.
카산드라 3.0에는 대안적인 재균형화 알고리즘이 추가됨
파티션 경계를 무작위로 선택하려면 해시 기반 파티셔닝을 사용해야 한다.
운영: 자동 재균형화와 수동 재균형화
완전 자동 재균형화는 손이 덜 들어 편리하지만 예측하기 어렵다.
재균형화는 요청 경로를 재설정해야 하고 대량의 데이터를 노드 사이에 이동해야 해서 비용이 큰 연산이다.
즉, 재균형화 중에는 다른 요청의 성능이 저하될 수 있다.
이런 자동화는 자동 장애 감지와 조합되면 위험해질 수도 있다.
그래서 재균형화 과정에 사람이 개입하는 게 좋을 수도 있다.
요청 라우팅
파티션에는 클라이언트는 어느 노드로 접속해야 하는지 알아야 하는 문제가 있다.
또한 재균형화 후에는 노드에 할당되는 파티션이 바뀐다.
이 문제는 데이터베이스에 국한되지 않은 더욱 일반적인 문제인 서비스 찾기(service discovery) 의 일종이다.
상위 수준에서 보면 이 문제는 몇 가지 다른 접근법이 있다.
- 클라이언트가 아무 노드에 접속
해당 노드에 마침 요청 대상 파티션이 있다면 요청을 직접 처리
그렇지 않다면 요청을 올바른 노드로 전달해서 응답을 받고 클라이언트에게 응답을 전달 - 클라이언트가 모든 요청을 라우팅 계층으로 먼저 전달
라우팅 계층에서 각 요청을 처리할 노드를 알아내서 해당 노드로 요청을 전달 - 클라이언트가 파티셔닝 방법과 파티션이 어떤 노드에 할당됐는지 알고 있게 한다.
바로 대상 노드로 접속
모든 경우에 핵심 문제는 라우팅 결정을 내리는 구성요소가 노드에 할당된 파티션의 변경 사항을 어떻게 아느냐다.
많은 분산 데이터 시스템은 클러스터 메타데이터를 추적하기 위해 주키퍼 같은 별도의 코디네이션 서비스를 사용한다.
각 노드는 주키퍼에 자신을 등록하고 주키퍼는 파티션과 노드 사이의 신뢰성 있는 할당 정보를 관리한다.
라우팅 계층이나 파티션 인지 클라이언트 같은 다른 구성요소들은 주키퍼에 있는 정보를 구독할 수 있다.
실제 사용 사례들
라우팅 계층 + 외부 코디네이션 서비스(2번)
링크드인의 에스프레소는 헬릭스(Helix)를 사용해서 클러스터를 관리하며 위의 그림의 라우팅 계층을 구현한다.
헬릭스는 다시 주키퍼에 의존한다.
몽고 DB도 아키텍처는 비슷하지만 자체적인 설정 서버 구현에 의존하고 몽고스(mongos) 데몬을 라우팅 계층으로 사용한다.노드가 라우팅 정보 관리(1번)
가십 프로토콜(gossip protocol)을 사용해서 클러스터 상태 변화를 노드 사이에 퍼뜨린다.(카산드라와 리악이 사용하는 방식)
아무 노드나 요청을 받을 수 있고 요청을 받은 노드는 요청을 처리할 파티션을 가진 올바른 노드로 요청을 전달한다.
데이터베이스 노드에 복잡성을 더하지만 외부 코디네이션 서비스에 의존하지 않는다.라우팅 계층(2번)
카우치베이스에서는 보통 클러스터 노드로부터 변경된 라우팅 정보를 알아내는 목시(moxi)라는 라우팅 계층을 사용한다.
클라이언트는 라우팅 계층을 사용하거나 임의의 노드로 요청을 보낼 때도 접속할 IP 주소를 알아내야 한다.
IP 주소는 노드에 할당된 파티션 정보만큼 자주 바뀌지 않으므로 보통은 DNS로 충분하다.
병렬 질의 실행
지금까지는 단일 키를 읽거나 쓰는 매우 간단한 질의에 대해서만 설명했다.
그러나 분석용으로 자주 사용되는 대규모 병렬 처리(massively parallel processing, MPP) 관계형 데이터베이스 제품은 훨씬 복잡한 종류의 질의를 지원한다.
전형적인 데이터 웨어하우스 질의는 조인(join), 필터링(filtering), 그룹화(grouping), 집계(aggregation) 연산을 몇 개 포함한다.
MPP 질의 최적화기는 복잡한 질의를 여러 실행 단계와 파티션으로 분해하며 이들 중 다수는 데이터베이스 클러스터 내의 서로 다른 노드에서 병렬적으로 실행될 수 있다.
데이터셋의 많은 부분을 스캔하는 연산을 포함하는 질의는 특히 병렬 실행의 혜택을 받는다.