데이터 셋이 매우 크거나, 질의 처리량이 높으면 복제만으론 부족하다. 데이터를 파티션으로 쪼개야 하고, 이 작업을 샤딩이라 한다.
개요
•
대용량 데이터셋을 파티셔닝하는 몇 가지 방법
•
데이터 색인과 파티셔닝의 상호작용
•
클러스터에 노드를 추가하거나, 노드를 제거할 때 re-balancing
•
DB가 어떻게 요청을 올바른 파티션에 전달하고 질의를 실행하는가
이 챕터는 앞에서 복제를 다뤘기 때문에 복제에 대한 내용은 대부분 생략한다.
이 책은 row, document, record 단위의 파티셔닝을 설명한다.
파티셔닝과 복제
사례
복제와 파티셔닝을 함께 사용할 수 있다.
레코드는 한 파티션에 속하면서, 여러 노드에 저장하여 내결함성을 보장할 수 있다.
Leader-follower 모델을 적용한 파티셔닝
•
하나의 노드에 여러 파티션을 저장할 수 있다.
•
Leader-follower 모델을 사용한다면 그림과 같다.
◦
각 파티션의 노드는 하나의 노드에 할당하고, 팔로워는 다른 노드에 할당한다.
◦
임의의 파티션 P는 리더이거나, 팔로워가 될 수 있다.
노드
파티션
기본 키
Partitioning of Key-Value data
임의의 레코드 r을 노드 집합 N중 어떤 노드에 저장할지 결정을 어떻게 할까?
목적
파티셔닝의 목적은 질의 부하를 N에 속한 모든 노드에게 고르게 분산시키는 것이다.
N에 속한 노드가 1개 → 10개로 늘어난다면, 집합 N은 이론상 10배의 읽기, 쓰기를 감당할 수 있다.
파티셔닝 핫스팟
•
고르게 분배되지 못해 하나의 하나의 노드로 쏠리는 현상을 skewed 라고 한다.
•
불균형하게 부하가 높은 파티션을 hotspot 이라 한다.
핫스팟을 피하는 방법, Partitioning by Key Range
•
노드 무작위 선출
◦
장점: 데이터가 노드 사이에 고르게 분산된다.
◦
단점: 데이터를 검색할 때 어떤 노드를 선택해야 할지 모르기 때문에 모든 노드에 병렬 질의해야 한다.
키 범위를 기준으로 파티셔닝 된 백과사전
•
백과사전과 같이 연속된 범위의 키 할당
◦
각 범위 사이의 경계를 명확히 한다.
◦
장단점
▪
장점: 임의의 키 k가 어느 노드에 속했는지 알 수 있다.
▪
단점: T, U, V, W, X, Y, Z 가 12권에 속해있다.
•
각 파티션은 안에서 k는 정렬된 순서로 저장할 수 있다.(Sorted String Table, SSTable)
•
센서 데이터 베이스(주식 데이터와 같은 스트리밍 데이터)
◦
장점: 센서 데이터를 저장하는 경우 timestamp로 저장하면 임의의 month 데이터를 가져올 수 있다.
◦
단점: 하루치 데이터를 하나의 파티션에 저장하는 경우, 하나의 파티션이 hotspot이 된다.
◦
이 문제를 해결하려면 센서의 이름, 주식의 이름 등을 prefix로 붙여 index를 적용한다.
Partitioning by Hash of Key
Skew, hot spot 문제를 해결하기 위해 분산 데이터 저장소는 hash function을 사용한다.
여기서 hashing 로직은 강력한 암호화가 될 필요까진 없다.
자바의 Object.hashCode() 정도만 되어도 다른 프로스세스에서 같은 key에 대해 동일한 hash 을 반환한다.
Java HashMap, 왜 hash 는 균일하게 분산될 수 있을까?
•
장점
◦
적당한 해시 값을 찾아 해시 값의 범위대로 파티션을 분배한다.
▪
일관성 해싱
•
단점
◦
Range query, sort에 매우 비효율적이다.
카산드라는 여기서 중간에 타협한다.
복합키를 사용하며 첫 컴포넌트는 해싱, 그 다음 컴포넌트는 SSTable 에서 사용하는 sorting 필드를 사용하여 범위 검색을 허용한다.
Skewed Workloads and Relieving Hot Spots (쏠린 작업부하와 핫스팟 완화)
•
항상 동일한 키를 읽고 쓰는 극단적인 상황은 모든 요청이 동일한 파티션으로 쏠리게 된다.
◦
ex. 트위터 레이디가가, 트럼프의 경우 이 유저가 저장된 파티션으로 요청이 쏠린다.
•
Hashing을 해도 동일한 hash key가 요청되기 때문에 의미가 없다.
•
현대 시스템은 애플리케이션에서 skew를 완화해야 한다.
완화하는 가장 간단한 방법
•
Skewd key를 발견하면 임의의 10진수 두 개를 붙인다.
◦
장점
▪
100개의 키로 균등하게 분산된다.
▪
100개의 키를 다른 파티션으로 분산한다.
◦
단점
▪
쓰기(upsert)를 실행하면 추가작업이 필요하다.
▪
100개 데이터에 모두 접근해야 한다.
파티셔닝과 보조 색인
•
Key-value 모델에서 벗어나 record 개념으로 들어가면 secondary index 에 대해 언급해야 한다.
•
보조 색인이 연관되면 상황은 복잡해진다.
◦
레코드를 유일하게 식별하는 용도가 아닌, 특정 값을 검색하는 수단이다.
◦
중복이 많을 수 있다.
•
Solr, Elastic search, RDB, NoSQL
•
보조색인은 파티션에 우아하게 대응되지 않는다. 대신 크게 사용되는 두 방법을 다룬다.
문서 기준 보조 색인 파티셔닝 (지역 색인, Local index)
중고차를 판매하는 사이트를 예제로 color, make(제조사)를 찾기위해 보조색인들 둔다.
빨간색이 partition0, partition1 모두에 존재한다.
위 그림에서 red는 두 파티션에 모두 존재한다. → 원하는 record가 어느 파티션에 존재하는지 모르기 때문에 모든 인스턴스에 질의하고, 그 결과를 모아야 한다.
이 방법을 scatter/gather 라 한다.
•
장점
◦
쓰기는 간편하다.
•
단점
◦
읽기에 큰 비용이 발생할 수 있다.
◦
99분위에 튀는 현상이 발생할 수 있다.
보조 색인 질의가 단일 파티션에 실행되도록 설계하기를 권장하지만, 현실은 항상 가능하지 않다.
특히 color:red make:xxx 인 상황
용어 기준 보조 색인 파티셔닝 (Global index)
용어를 기준으로 index을 생성하였으며, 이 색인은 모든 instance를 대응한다.
•
모든 파티션 데이터를 담당하는 전역 색인을 만든다.
◦
한 노드에만 색인을 저장할 순 없다. (hotspot 발생으로 병목)
◦
예시) color:red → a~r 은 파티션0, s~z 는 파티션 1
•
찾는 용어에 따라 파티션이 결정되므로 용어 기준 파티셔닝됐다고 한다.
•
용어 자체를 쓰거나 용어의 hash 를 사용할 수 있다.
◦
더 고르게 분산
•
장점
◦
읽기가 효율적이다.
▪
원하는 용어를 포함하는 파티션에 질의할 수 있다.
•
단점
◦
쓰기가 느리가 복잡하다.
◦
단일 document가 여러 파티션에 영향을 줄 수 있다.
◦
분산 트랜잭션(2PC, 3PC 등등) or 트랜잭션 이후 최종적 일관성으로 색인이 데이터와 동기화 된다.
파티션 재균형화(rebalancing)
서비스가 운영되면서 데이터베이스에 변화가 발생한다.
이 변화 중 장비 혹은 장애로 인해 데이터를 다른 노드로 옮겨야 하는 일이 발생한다.
이를 rebalancing 재균형화라고 한다.
Rebalancing을 할때 만족할 것으로 기대하는 기능은 다음과 같다.
•
Rebalancing의 결과로 cluster의 노드들의 요청은 균등하게 분배된다.
•
Rebalancing 도중에도 읽고 쓰는 요청을 받아들여야 하낟.
•
네트워크, 디스크 부하를 최소화하기 위해 필요 이상으로 데이터가 옮겨지지 않는다.
재균형화 전략
쓰면 안되는 방법: hash 값에 mod N 연산
•
AWS의 SA 분들의 이야기를 들어보면 고객사 중에 많이 사용하는 방법이라 함.
•
사용하지 말라는 이유는 mod N 에서 N이 변경되는 것을 고려하기 때문이다.
◦
키를 기준으로 많은 이동이 필요하다.
◦
hash(key)=12345 이면 10개일때 6에 할당되지만, 11개로 노드가 늘어나면 3으로 옮겨져야 한다.
◦
자주 이동하는 경우 비용이 지나치게 커진다.
3가지 파티셔닝 방법
파티션 개수 고정
mod N의 간단한 해결책
파티션 개수를 고정하고, 노드보다 많은 파티션을 할당한 사례에서 새 노드를 추가한 경우
•
파티션을 노드 대수보다 많이 만들고, 임의의 에 여러 파티션을 할당한다.
◦
노드가 10대면, 파티션을 1000개로 정의하고, 하나의 노드에 100개 파티션 할당
•
클러스터에서 노드가 추가되거나 제거되면 파티션이 이동한다.
•
파티션 개수는 변경되지 않는다.
•
유일한 변화는 파티션이 어느 노드에 할당되느냐 이다.
•
전송이 진행중이면 읽기 쓰기는 기존 할당된 파티션이 감당한다.
•
하드웨어 성능이 좋은 노드가 있다면 더 많은 파티션을 할당할 수 있다.
리악, Elasticsearch, couch base, volt db
이 방법을 사용하면 처음 구축시 파티션 개수가 고정되고 이후 변화를 하지 않게끔 한다.
이론적으론 분할과 병합이 가능하지만, 운영이 단순해지기 때문이다.
미래를 위해 충분히 높은 값으로 파티션 개수를 설정해야 하지만, 동시에 너무 많은 파티션이면 운영의 오버헤드가 발생한다.
동적 파티셔닝
HBase, RethinkDB와 같은 경우는 파티션 개수가 동적이다.
임계치를 넘어가면 파티션을 두개로 쪼개 절반씩 나누어 갖는다. → B+tree와 비슷
또한 데이터가 많이 삭제되면 인접한 파티션을 병합한다. → B+tree와 비슷
•
장점
◦
전체 데이터 용량에 맞춰 조정됨
◦
데이터 양이 작으면 오버헤드도 작다.
•
단점
◦
빈 데이터베이스는 경계를 어디로 정해야 하는지 모르기 때문에 파티션이 하나이다.
Hbase, MongoDB는 이 단점을 해결하기 위해 pre-spliting (사전분할)을 수행한다.
노드 비례 파티셔닝
정의: 파티션 개수는 노드 대수에 비례한다.
부연설명
노드 개수가 변함이 없다면 → 개별 파티션의 크기는 전체 데이터셋에 비례한다.
노드 대수를 늘리면 → 파티션의 크기가 줄어든다.
클러스터에 새 노드가 추가되면 고정된 개수의 파티션을 무작위로 선택해서 분할하고, 분할된 파티션의 절반은 그대로 두고 다른 절반은 새 노드에 할당한다.
운영: Automatic or Manual Rebalancing
지금까지 rebalancing에서 자동, 수동에 대한 언급은 없었다.
Couchbase, 리악, volt는 중간이다 → 자동으로 파티션 할당을 제안하고, 반영하려면 수동이다.
완전 자동
•
장점
◦
유지보수에 손이 덜간다.
•
단점
◦
예측이 어렵다.
Rebalancing은 요청 경로 재설정, 데이터 이동 등 노드간 네트워크 과부하가 발생할 수 있고, rebalancing 도중 다른 요청으로 인해 성능이 저하될 수 있다.
장애 모니터링이 동작하여 rebalancing 도중 특정 노드가 죽었다고 가정하자.
그럼 leader를 제외하는 알고리즘이 실행되며 데이터가 또 이동된다.
즉, 악순환이 시작되어 더 장애 지속시간이 늘어날 수 있다.
따라서 rebalancing엔 사람이 개입하는 것이 좋다.
요청 라우팅
Rebalancing이 일어났다. 그렇다면 원하는 데이터를 찾기 위해 어디로 query 요청을 보내야할까?
임의의 파티션 p는 N의 어느 노드에 있을까?
상위 수준에서 보면 3가지 방법으로 접근한다.
클라이언트가 아무 노드나 접속한다.
•
요청 r은 N의 요소중 아무 n에 접속한다.
◦
마침 n에 r이 찾는 파티션 p가 있다면 p에서 d를 찾아 반환한다.
◦
n에 요청 r에 맞는 파티션 p가 없다면, 올바른 n으로 전달한다.
라우팅 계층으로 먼저 보낸다.
•
라우팅 계층은 요청 r에 알맞은 p가 어느 n에 있는지 안다.
•
라우팅 계층에서 요청을 전달한다.
•
요청 r에 대한 다른 어떠한 것도 처리하지 않느낟.
파티션 인지(partition-aware) LB라 한다.
클라이언트가 파티셔닝 방법, 어떤 노드인지 안다.
이 경우 client는 proxy 없이 요청 r이 찾는 p가 있는 n에 직접 요청한다.
이 문제는 원천 데이터가 다를 수 있다. 어느곳에서 어떻게 참여하든 동일한 데이터를 반환해야 하기 때문에 어렵다.
분산 환경에서 cluster metadata를 추적하기 위해 zookeeper를 사용한다.
N의 모든 요소는 zookeeper에 자신을 등록하고 n, p에 대해 신뢰성 있는 정보를 저장하낟.
라우팅 계층, 파티션 인지 클라이언트와 같은 component는 이 주키퍼의 정보를 구독하여 임의의 p, 혹은 d가 어느 n에 속해있는지 알아낸다.
Helix, Hbase, solr, kafka 가 주키퍼를 사용하고, mongo는 mongos를 사용한다.
Gossip protocol
주키퍼 사용 사례를 보면 failover를 위해 기본적으로 주키퍼만 3개가 필요하다.
이러한 의존성을 줄이기 위해 가십 프로토콜을 사용하여 cluster 의 상태변화를 노드 사이에 퍼트린다.
어느 노드던 요청을 받을 수 있고, 올바른 노드로 요청을 전달한다.
하지만, 노드에 복잡성을 일으킨다.
병렬 질의 실행
지금까지 설명한 사례는 OLTP 에 어울리는 사례이다.
OLAP 는 어떠할까? join, filtering, grouping, aggregation 과 같은 복잡한 쿼리를 사용할 수 있다.
IoT device의 sensor 데이터를 처리하고, 검색엔진에서 유저 행동에 대해 특정시간 쌓이는 데이터가 70TB였이다. 이러한 데이터를 상대로 OLAP 쿼리를 한다면 하나의 쿼리가 몇시간씩 걸릴 수 있다.
이런 케이스에서 사용하는 것이 대규모 병렬 처리(massively parallel processing, MPP)이다.
복잡한 질의를 여러 단계, 파티션으로 분해하여 cluster 안에 있는 n에 분배한다.
References
JDK 11 HashMap
