1. 파티셔닝
•
데이터셋이 매우 크거나 질의 처리량이 매우 높다면 복제만으로는 부족하고 데이터를 파티션으로 쪼갤 필요가 있다.
◦
이 작업을 파티셔닝 또는 샤딩이라고 한다.
•
파티션을 나눌 때는 보통 각 데이터 단위(레코드, 로우, 문서)가 하나의 파티션에 속하게 한다.
◦
데이터베이스가 여러 파티션을 동시에 건드리는 연산을 지원할 수도 있지만 결과적으로 각 파티션은 그 자체로 작은 데이터베이스가 된다.
•
데이터 파티셔닝을 원하는 주된 이유는 확장성이다.
•
단일 파티션에 실행되는 질의를 생각해 보면 각 노드에서 자신의 파티션에 해당하는 질의를 독립적으로 실행할 수 있으므로 노드를 추가해 처리량을 늘릴 수 있다.
1.1. 파티셔닝과 복제
복제와 파티셔닝 조합
•
보통 복제와 파티셔닝을 함께 적용해 각 파티션의 복사본을 여러 노드에 저장한다.
•
각 레코드는 정확히 한 파티션에 속하더라도 이를 여러 다른 노드에 저장해서 내결합성을 보장할 수 있다는 의미이다.
•
한 노드에 여러 파티션을 저장할 수도 있다.
1.2. 키-값 데이터 파티셔닝
•
파티셔닝의 목적은 데이터와 질의 부하를 노드 사이에 고르게 분산시키는 것이다.
•
파티셔닝이 고르게 이뤄지지 않아 데이터가 많거나 질의를 많이 받는 파티션이 있다면 쏠렸(skewed)다고 한다.
•
불균형하게 부하가 높은 파티션을 핫스팟(hotspot) 이라고 부름
◦
회피하는 방법은 레코드를 할당할 노드를 무작위로 선택하는 것
•
더 좋은 키-값 데이터 모델 = 항상 기본키를 통해 레코드에 접근한다.
1.2.1. 키 범위 파티셔닝
키를 기준으로 파티셔닝된 백과사전
•
각 파티션에 연속된 범위의 키를 할당하는 것이다.
•
각 범위들 사이의 경계를 알면 어떤 키가 어느 파티션에 속하는지 쉽게 찾을 수 있다.
•
어떤 파티션이 어느 노드에 할당됐는지 알면 적절한 노드로 요청을 직접 보낼 수 있다.
•
데이터가 고르게 분포하지 않을 수 있기 때문에 키 범위 크기가 반드시 동일 할 필요는 없다.
•
장점
◦
각 파티션 내에서는 키를 정렬된 순서로 저장할 수 있다.
◦
이렇게 하면 범위 스캔이 쉬워지는 이점이 있고 키를 연쇄적 색인으로 간주해서 질의 하나로 관련 레코드 여러 개를 읽어 오는데 사용할 수 있다.
•
단점
◦
특정한 접근 패턴이 핫스팟을 유발한다.
◦
reg_date가 키라면 파티션은 년(year) 범위에 대응된다. 예를 들어 1년의 데이터를 파티션 하나가 담당하는 식이다.
◦
데이터를 갱신할 때 마다 데이터베이스에 기록하므로 쓰기 연산이 모두 동일한 파티션(해당하는 year)으로 전달되어 해당 파티션만 과부하가 걸리고 나머지 파티션은 유휴 상태로 남을 수 있다.
1.2.2. 키의 해시값 기준 파티셔닝
키의 해시값 기준 파티셔닝
•
해시 파티션은 특정 해시 함수에 의해 레코드가 저장될 파티션을 결정하는 방법이다.
•
파티셔닝용 해시 함수는 암호적으로 강력할 필요는 없다.
•
장점
◦
쏠림과 핫스팟의 위험을 줄여 쏠린 데이터를 입력으로 받아 균일하게 분산되게 한다.
•
단점
◦
범위 질의를 효율적으로 실행할 수 있는 키 범위 파티셔닝의 좋은 속성을 잃어버린다.
◦
전에는 인접했던 키들이 이제는 모든 파티션에 흩어져서 정렬 순서가 유지되지 않는다.
1.2.3. 쏠린 작업부하와 핫스팟 완화
•
키를 해싱하면 핫스팟을 줄이는데 도움은 되지만 완벽히 제거할 수는 없다.
•
항상 동일한 키를 읽고 쓰는 극단적인 상황에서는 모든 요청이 동일한 파티션으로 쏠리게 된다.
•
해결책
◦
각키의 시작이나 끝에 임의의 숫자를 붙인다.
▪
임의의 10진수 두 개만 붙이더라도 한 키에 대한 쓰기 작업이 100개의 다른 키로 균등하게 분산되고 그 키들은 다른 파티션으로 분산될 수 있다.
◦
그러나 다른 키에 쪼개서 쓰면 읽기를 실행할 때 추가적인 작업이 필요해진다.
▪
100개의 키에 해당 하는 데이터를 읽어서 조합해야 하기 때문이다. 추가적으로 저장해야 할 정보도 있다.
◦
이 기법은 요청이 몰리는 소수의 키에만 적용하는게 타당하다.
▪
쓰기 처리량이 낮은 대다수의 키에도 적용하면 불필요한 오버헤드가 생긴다. 따라서 어떤 키가 쪼개졌는지 추적할 방법도 있어야 한다.
2. 파티셔닝과 보조 색인
•
레코드를 기본키를 통해서만 접근한다면 키로부터 파티션을 결정하고 이를 사용해 해당 키를 담당하는 파티션으로 읽기 쓰기 요청을 전달할 수 있다.
•
그러나 특정한 값이 발생한 항목을 검색하는 수단인 보조색인이 연관되면 복잡해 진다.
◦
보조 색인은 파티션에 깔끔하게 대응되지 않는 문제점이 있기 때문이다.
2.1. 문서 기준 보조 색인 파티셔닝
문서 기준 보조 색인 파티셔닝
•
각 항목은 문서ID라는 고유 ID가 있고 해당 ID를 기준으로 파티셔닝 한다.
•
각 파티션이 완전히 독립적으로 동작하기 때문에 보조 색인을 유지하며 그 파티션에 속하는 문서만 담당한다.
◦
문서 파티셔닝 색인은 지역 색인(Local Index)이라고 한다.
•
주의점
◦
문서 ID에 뭔가 특별한 작업을 하지 않는다면 특정한 색상이거나 특정한 제조사가 만든 자동차가 동일한 파티션에 저장되리라는 보장이 없다.
◦
위 이미지를 보면 빨간색 자동차는 파티션 0에도 있고 파티션 1에도 있다.
◦
따라서 빨간색 자동차를 찾고 싶다면 모든 파티션으로 질의를 보내서 얻은 결과를 모두 모아야 한다.
•
파티셔닝된 데이터베이스에 이런 식으로 질의를 보내는 방법을 스캐터/개더(scatter/gather)라고도 하는데 보조 색인을 써서 읽는 질의는 큰 비용이 들 수 있다.
2.2. 용어 기준 보조 색인 파티셔닝
용어 기준 보조 색인 파티셔닝
•
지역 색인과 다르게 모든 파티션의 데이터를 담당하는 색인을 전역 색인을 만들 수도 있다.
◦
그러나 한 노드에만 색인을 저장할 수는 없다.
◦
해당 노드가 병목이 되어 파티셔닝의 목적을 헤칠 수 있기 때문에 여러 노드에 나눠서 저장한다.
•
찾고자 하는 용어에 따라 색인의 파티션이 결정되므로 이런 식의 색인을 용어 기준으로 파티셔닝됐다(term-partitioned)고 한다.
•
용어란 문선에 등장하는 모든 단어를 말한다.
•
장점
◦
문서 파티셔닝 색인에 비해 전역(용어 파티셔닝) 색인이 갖는 이점은 읽기가 효율적이라는 것이다.
◦
클라이언트는 모든 파티션에 스개터/개더를 실행할 필요 없이 원하는 용어를 포함하는 파티션으로만 요청을 보내면 된다.
•
단점
◦
단일 문서를 쓸 때 해당 색인의 여러 파티션에 영향을 줄 수 있으며 쓰기가 느리고 복잡하다.
▪
단일 문서를 쓸 때 해당 색인의 여러 파티션에 영향을 줄 수 있기 때문이다.
•
이상적으로는 색인은 항상 최신 상태에 있고 데이터베이스에 기록된 모든 문서는 바로 색인에 반영돼야 한다.
◦
하지만 용어 파티셔닝 색인을 사용할 때 그렇게 하려면 쓰기에 영향받는 모든 파티션에 걸친 분산 트랜잭션을 실행해야 하는데, 모든 데이터베이스에서 분산 트랜잭션을 지원하지는 않는다.
•
현실에서는 전역 보조 색인은 대개 비동기로 갱신된다.
◦
즉 쓰기를 실행한 후 바로 색인을 읽으면 변경 사항이 색인에 반영되지 않았을 수도 있다.
3. 파티션 재균형화
•
시간이 지남에 따라 DB에 변화가 생긴다.
◦
질의 처리량이 증가해서 늘어난 부하를 처리하기 위해 CPU를 더 추가하고 싶다.
◦
데이터셋 크기가 증가해서 데이터셋 저장에 사용할 디스크와 램을 추가하고 싶다.
◦
장비에 장애가 발생해서 그 장비가 담당하던 역할을 다른 장비가 넘겨받아야 한다.
•
재균형화(rebalancing) = 클러스터에서 한 노드가 담당하던 부하를 다른 노드로 옮기는 과정을
•
재균형과가 실행될 때 만족시킬 것으로 기대되는 최소 요구사항
◦
리밸런싱 이후, 부하가 클러스터 내에 있는 노드들 사이에 균등하게 분배돼야 한다.
◦
리밸런싱 도중에도 데이터베이스는 읽기 쓰기 요청을 받아들여야 한다.
◦
리밸런싱이 빨리 실행되고, 네트워크와 디스크 I/O 부하를 최소화할 수 있도록 노드들 사이에 데이터가 필요 이상으로 옮겨져서는 안 된다.
3.1. 재균형화 전략
3.1.1. 쓰면 안되는 전략 : 해시값에 mod(N) 연산을 실행
•
mod(N) 방식의 문제는 노드 개수 N이 바뀌면 대부분의 키가 노드 사이에 옮겨져야 한다는 점이다.
•
키가 자주 이동하면 재균형화 비용이 지나치게 커진다.
3.1.2. 파티션 개수 조정
•
파티션을 노드 대수보다 많이 만들고 각 노드에 여러 파티션을 할당하는 방법
◦
예를 들어 노드 10대에 파티션 1000개
•
클러스터에 노드가 추가되면 새 노드는 파티션이 다시 균일하게 분배될 때까지 기존 노드에서 파티션 몇 개를 뺏어올 수 있다.
◦
노드가 제거될 경우 반대로 실행된다.
•
파티션은 노드 사이에서 통째로 이동하기만 한다.
◦
파티션 개수는 바뀌지 않고 파티션에 할당된 키도 변경되지 않는다.
◦
유일한 변화는 노드에 어떤 파티션이 할당되는가 뿐이다.
•
이 방식을 사용할 때, 보통 데이터베이스가 처음 구축될 때 파티션 개수가 고정되고 이후에 변하지 않는다.
•
처음 설정된 파티션 개수가 사용 가능한 노드 대수의 최대치가 되므로 미래에 증가될 것을 수용하기에 충분히 높은 값으로 선택해야 한다.
◦
그러나 개별 파티션도 관리 오버헤드가 있으므로 너무 큰 수를 선택하면 역효과를 낳을 수 있다.
3.1.3. 동적 파티셔닝
•
키 범위 파티셔닝을 사용하는 DB에서는 파티션 경계와 개수가 고정돼 있으면 매우 불편하다.
◦
경계를 잘못 지정하면 모든 데이터가 한 파티션에 저장되고 나머지 파티션은 빌 수도 있기 때문이다.
•
이런 이유로 HBase처럼 키 범위 파티셔닝을 사용하는 DB에서는 파티션을 동적으로 만든다.
◦
파티션 크기의 설정값에 따라 쪼개지거나 합쳐진다 (B트리와 유사)
•
동적 파티셔닝은 파티션 개수가 전체 데이터 용량에 맞춰 조정된다는 이점이 있다.
◦
데이터 양이 작으면 파티션 개수가 적어도 되므로 오버헤드도 작다.
•
But 비어있는 DB는 파티션 경계를 어디로 정해야 하는지에 관한 사전 정보가 없으므로 시작할 때는 파티션이 1개라는 함정이 있다.
•
이런 문제를 해결하기 위해 HBase와 몽고DB에서는 빈 DB에 초기 파티션 집합을 설정할 수 있는 기능을 제공
3.1.4. 노드 비례 파티셔닝
•
동적 파티셔닝에서는 파티션 분할과 병합을 통해 개별 파티션 크기가 어떤 고정된 최솟값과 최댓값 사이에 유지되게 하므로 파티션 개수가 데이터셋 크기에 비례한다.
◦
반면 파티션 개수를 고정하면 개별 파티션의 크기가 데이터셋 크기에 비례한다.
◦
두 경우 모두 파티션 개수는 노드 대수와 독립적이다.
•
파티션 개수가 노드 대수에 비례하게 하는 방법
◦
노드당 할당되는 파티션 개수를 고정한다.
•
노드 대수가 변함없는 동안은 개별 파티션 크기가 데이터셋 크기에 비례해서 증가하지만 노드 대수를 늘리면 파티션 크기는 다시 작아진다.
◦
일반적으로 데이터 용량이 클수록 데이터를 저장할 노드도 많이 필요하므로 이 방법을 쓰면 개별 파티션 크기도 상당히 안정적으로 유지된다.
•
새 노드가 클러스터에 추가되면 고정된 개수의 파티션을 무작위로 선택해 분할하고 각 분할된 파티션의 절반은 그대로 두고 다른 절반은 새 노드에 할당한다.
◦
파티션을 랜덤으로 선택해 균등하지 않은 분할이 생길 수 있지만 여러 파티션에 대해 평균적으로 보면 새 노드는 기존 노드들이 담당하던 부하에서 균등한 몫을 할당받게 된다.
3.2. 운영: 자동 재균형화와 수동 재균형화
•
재균형화는 자동으로 실행될까? 아니면 수동으로 실행해야 할까?
•
완전 자동 재균형화와 완전 수동 재균형화 사이에는 중간 지점이 있다.
◦
예를 들어 카우치베이스, 리악, 볼드모트는 자동으로 파티션 할당을 제안하지만 반영되려면 관리자가 확정해야 한다.
3.2.1. 완전 자동 재균형화
•
완전 자동 재균형화는 일상적인 유지보수에 손이 덜 가므로 편리할 수 있다.
◦
하지만 예측하기 어렵다.
•
재균형화는 요청 경로를 재설정해야 하고 대량의 데이터를 노드 사이에 이동해야 하므로 비용이 큰 연산이다.
•
재균형화 과정에서 사람이 개입하는 게 좋을 수 있다.
◦
완전 자동 처리보다는 느릴 수 있지만 운영상 예상치 못한 일을 방지하는 데 도움이 될 수 있기 때문
3.3. 요청 라우팅
•
클라이언트에서 요청을 보내려고 할 때 어느 노드로 접속해야할까?
◦
파티션이 재균형화 되면서 노드에 할당되는 파티션이 바뀜 = 데이터 위치가 바뀐다는 의미
3.3.1. 서비스 찾기(service discovery)
•
데이터베이스에 국한되지 않은 일반적인 문제인 서비스 찾기의 일종
•
고가용성을 지향하는 소프트웨어라면 모두 가지고 있는 문제
•
접근법
◦
클라이언트가 아무 노드에나 접속하게 한다.
▪
요청을 적용할 파티션이 있다면 직접 처리를 한다.
▪
만약 찾고자 하는 파티션이 아니었다면 올바른 노드로 전달해서 응답을 받고 클라이언트에게 응답을 전달한다.
◦
클라이언트의 모든 요청을 라우팅 계층으로 먼저 보낸다.
▪
라우팅 계층은 파티션을 정하는 로드밸런서로 동작만 할 뿐 그 자체에서는 아무 요청도 처리하지 않는다.
◦
클라이언트가 파티셔닝 방법과 파티션이 어떤 노드에 할당됐는지를 알고 있게 한다.
▪
중개자 없이 올바른 노드로 직접 접속한다.
•
이 문제는 참여하는 모든 곳에서 정보가 일치해야 하므로 다루기 어렵다.
◦
그렇지 않으면 요청이 잘못된 노드로 전송되고 제대로 처리되지 못한다.
◦
또한 분산 시스템에서 합의를 이루는 데 쓰이는 프로토콜이 있지만 제대로 구현하기가 까다롭다.
3.3.2. 코디네이터
•
많은 분산 데이터 시스템은 클러스트 메타데이터를 추적하기 위해 주키퍼(ZooKeeper)와 같은 별도의 코디네이션 서비스를 사용한다.
•
각 노드는 주키퍼에 자신을 등록하고 주키퍼는 파티션과 노드 사이의 신뢰성 있는 정보를 관리한다.
•
그래서 파티션 소유자가 바뀌거나 클러스터에 노드가 추가 혹은 삭제가 되면 주키퍼는 라우팅 계층에 이를 알려서 라우팅 정보를 최신으로 유지할 수 있게 한다.
•
그리고 이 라우팅 계층을 바라보는 다른 구성요소들은 주키퍼에 있는 정보를 구독한다.
