[Data-Intensive] Ch6. 파티셔닝 (Partitioning)

파티셔닝

‘데이터 중심 애플리케이션 설계’를 읽고 정리하고자함

대용량 데이터셋을 작은 데이터셋으로 파티셔닝하는 전략에 대해 설명
- 저장하고 처리할 데이터가 한대의 서버에서 처리하지 못할 시, 파티셔닝을 해야함

파티셔닝의 목적

핫스팟이 생기지 않게 해야함
- 불균형적으로 높은 부하를 받는 노드 = 핫스팟
데이터와 질의 부하를 여러장비에 균등하게 분배해야함

그러기 위해서는 ?

데이터에 적합한 파티셔닝 방식을 선택해야함
노드가 추가/제거 될 때, 파티션 재균형화를 실행해야함

파티셔닝 방법론

키 범위 파티셔닝
- 키가 정렬돼 있고, 개별 파티션은 어떤 최솟값과 최댓값 사이에 속하는 모든 키를 담당함
- 키가 정렬돼 있어 범위 질의에 효과적
- 정렬 순서가 서로 가까운 키에 자주 접급하면 핫스팟이 생길 위험이 있음
- 일반적으로, 한 파티션이 너무 크면 키범위를 두개로 쪼개 동적으로 재균형화를 실행함
해시 파티셔닝
- 각 키에 해싱 함수 적용하고, 개별 파티션은 특정 범위의 해시값으 담당함
- 키 순서가 보장되지 않아 범위 질의에 비효율적이지만, 부하를 균일하게 분산할 수 있음
- 보통 고정된 개수의 파티션을 미리 만들어 각 노드에 몇 개씩 파티션을 할당함
- 노드가 추가/삭제되면 파티션을 통째로 노드사이에서 이동함
- 동적 파티셔닝 적용 가능

두가지 방법을 섞어서 사용할 수 있음

키 일부분은 파티션 식별용으로, 나머지는 정렬용으로 복합키 설계 가능

파티셔닝과 보조 색인 사이의 상호작요

문서 파티셔닝 색인(지역 색인)
- 보조 색인을 기본키와 값이 저장된 파티션에 저장
- 쓸 때는 파티션 하나만 갱신하면 됨
- 읽을 때는 모든 파티션에 걸쳐 Scatter gather를 실행해야함
용어 파티셔닝 색인(전역 색인)
- 색인된 값을 사용해서 보조 색인을 별도로 파티셔닝
- 보조 색인 항목은 기본키의 모든 파티션에 있는 레코드를 포함할 수 있음
- 문서를 쓸 때는 여러개를 갱신해야함
- 읽을 때는 단일 파티션에서 실행할 수 있음

모든 파티션은 대부분 독립적으로 동작함
- 그래서, 파티셔닝된 데이터베이스는 여러 장비에 확장할 수 있음
하지만 여러 파티션에 기롣해야하는 연산은 ..?
예를 들어, 한 파티션에는 쓰기 성공했지만, 다른 파티션에서 실패하면..?
이 문제는 다음 블로그, 트랜잭션에서 다룰 예정

방금까지가 정리였고, 이제 파티셔닝에 대해 세세하게 알아봅시다~

파티셔닝

데이터 파티셔닝을 원하는 주된 이유 : 확장성

대용량 데이터셋이 여러 디스크에 분산될 수 있고, 질의 부하는 여러 프로세스에서 분산될 수 있음

파티셔닝과 복제

보통 복제와 파티셔닝을 함께 적용해 각 파티션의 복사본을 여러 노드에 저장
- 각 레코드는 정확히 한 파티션에 속하더라도 이를 여러 다른 노드에 저장해서 내결함성을 보장할 수 있음
한 노드에 여러 파티션을 저장할 수 있음
- 위의 그림이 리더 팔로워 복제 모델에서의 파티셔닝과 복제의 모습
- 각 파티션의 리더는 하나의 노드에 할당되고 팔로워들은 다른 노드에 할당
- 각 노드는 어떤 파티션에서는 리더, 팔로워 일 수 있음

키-값 데이터 파티셔닝

어떤 레코드를 어느 노드에 저장할지 어떻게 결정할 것 인가?

파티션의 목적

데이터와 질의 부하를 노드 사이에 고르게 분산시키는 것

쏠렸다(skewed) = 쏠린, 불균형하게 부하가 높은 파티션 = 핫스팟

파티션이 고르게 이뤄지지 않아 다른 파티션보다 데이터가 많거나 질의를 많이 받는 파티션을 칭함

핫스팟을 피하는 방법

레코드를 할당할 노드를 무작위로 선책
- 간단하게 고르게 분산된다는 장점
- 어떤 레코드를 읽으려면 해당 레코드가 어딨는지 몰라, 모든 노드에서 병렬적으로 질의를 수행해야함

1. 키 범위 기준 파티셔닝

각 파티션에 연속된 범위(어떤 최솟값에서 최댓값까지)의 키를 할당하는 것

키 범위들 사이의 경께를 알면, 어떤 키가 어느 파티션에 속하는지 찾을 수있음

즉, 어떤 파티션이 어느 노드에 할당됐는지 알면 적절한 노드로 요청을 직접 보낼 수 있음

키 범위 크기가 반드시 동일할 필요없음

파티션 경계는 수동으로 선택하거나, 데이터베이스에서 자동을 선택되게 할 수 있음

빅테이블, Hbase, RethinkDB , 2.6이전의 몽고DB

키 파티션 내에서는 키로 정렬된 순서로 저장할 수 있음

범위 스캔이 쉬어지고, 키를 연쇄된 색인으로 간주해서 질의 하나로 관련 레코드를 여러개 읽어올 수 있음

2. 키의 해시값 기준 파티셔닝

쏠림과 핫스팟 위험으로 많은 분산 데이터스토어는 키의 파티션을 정하는데 해시 함수 사용

파티셔닝용 해시 함수는 암호적으로 강렬할 필요 없음
- 카산드라, 몽고DB는 MD5
- 볼드포트는 Fowler-Noll-Vo 함수
프로그래밍 언어에 간단한 해시 테이블을 사용하는 해시 함수가 내장돼 있지만, 파티셔닝에는 적합하지 않을 수 있음
- Object.hashCode() 는 같은 키를 넣어도 다른 프로세스에서는 다른 해시값을 반환할 수 있음

키에 적합한 해시함수로 각 파티션에 해시값 범위를 할당하고 해시값이 파티션의 범위에 속하는 모든 키를 그 파티션에 할당

일관성 해시

CDN 같은 인터넷 규모의 캐시 시스템에서 부하를 균등하게 분산시키는 방법

파티션 경계를 무작위로 선택

일관성은 재균형화 방법을 의미

그냥 해시 파티셔닝오 같은 의미로 생각하자

단점

범위 질의를 효율적으로 실행하기 어려움
- 인접했던 키들이 모든 파티션에 흩어져서 정렬 순서가 유지되지 않음

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

키를 해싱하면 핫스팟을 줄이는데 도움이 되지만, 완벽하게 제거할 수 없음

항상 동일한 키를 읽고 쓰는 극단적인 상황에서는 모든 요청이 동일한 파티션으로 쏠림

방법

요청이 쏠린 키에 대해 임의의 숫자를 붙이는 것
- 임의의 10진수 두개만 붙이더라도 한 키에 대한 쓰기 작업이 100개의 다른 키로 균등하게 분산되고, 그 키들은 다른 파티션으로 분산될 수 있음
문제
- 읽기를 실행할 때 추가적인 작업이 필요해짐
- 100개의 키에 해당하는 데이터르 읽어서 조합해야함
쓰기 처리량이 낮은 대대수의 키에도 적용하면 불필요한 오버헤드가 생김

파티셔닝과 보조 색인

레코드를 기본키를 통해서만 접근한다면 키로부터 파티션을 결정하고 이를 사용해 해당 키를 담당하는 파티션으로 읽기쓰기요청을 전달함

보조 색인은 보통 레코드를 식별하는 용도가 아님

특정한 값이 발생한 항목을 검색하는 수단
e.g) 사용자 A이 실행한 액션을 모두 찾거나, hogwash 단어를 포함한 글을 모두 찾거나 등등

보조 색인은 관계형 데이터베이스의 핵심 요소

HBase나 볼드모트 같은 키-값 저장소에서는 구현 복잡도를 추가되는 것을 피하려고, 보조 색인을 지원하지 않음

보조 색인은 데이터 모델링에 유용함

솔라나 엘라스틱 서치 같은 검색 서버에게는 보조색인이 존재의 이유임

보조 색인을 파티셔닝하는데 널리 쓰이는 두 방법

문서 기반 파티셔닝
용어 기반 파티셔닝

1. 문서 기분 보조 색인 파티셔닝

중고차 판매하는 사이트라고 가정

각 항목에는 문서ID가 있고, ID기준으로 파티서닝함

사용자가 검색할 때는 색상, 제조사 별로 필터링할 수 있게 보조 색인을 만듬

각 파티션은 자신의 보조 색인을 유지하며 그 파티션에 속하는 문서만 담당

다른 파티션에 어떤 데이터가 저장되어있는지는 중요하지 않음
데이터베이스에 문서 추가/삭제/갱신 등의 쓰기 요청을 할때는 쓰려고 하는 문서ID를 포함하는 파티션만 다룸 그래서 문서 타피셔닝 색인은 지역 색인(local index)라고도 함

문제

문서 기준으로 파티셔닝된 색인을 써서 읽을 때 주의해야함
문서 ID에 뭔가 작업하지 않는다면 특정 색상이거나 특정한 제조사가 만든 자동차가 동일한 파티션에 저장되리라는 보장이 없음
빨간색 자동차를 찾고 싶으면 모든 파티션으로 질의를 보내서 얻은 결과를 얻어야함

스캐터/개터(scatter/gather)

파티셔닝된 데이터베이스에 모든 파티션에 질의를 보내서 얻은 결과를 모으는 방법
보조 색인을 써서 읽는 질의는 큰 비용이 들 수 있음
대부분 보조 색인 질의가 단일 파티션에서만 실행되도록 파티셔닝 방식을 설계하도록 권장하지만 항상 그럴 수 없음
- 단일 질의에서 여러 보조 색인을 사용할 때
- 자동차를 색상으로 필터링하면서 동시에 제조사로 필터링할 경우

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

각 파티션이 자신만의 보조색인,지역색인을 갖게하는 대신, 모든 파티션을 담당하는 전역 색인을 만들 수 있음

전역 색인 정보를 한 노드에 저장하지 않음
- 해당 노드가 병목이 되어 파티셔닝의 목적을 해치기 때문
전역 색인도 파티셔닝해야하지만, 기본키 색인과는 다른 식으로 할 수 있음

이렇게!!
모든 파티션에 있는 빨간색 자동차는 색인에서 color:red 항목에 저장
하지만, 색깔 색인은 a~r까지의 글자로 시작하는 색깔은 파티션 0번, s~z는 파티션 1에 저장되도록 파티셔닝됌

찾고자하는 용어에 따라 색인의 파티션이 결정되므로 이런식의 색인을 용어 기준으로 파티셔닝됐다(term-partitioned)라고 함

color:red가 용어의 예시

이점

읽기가 효율적
- 클라이언트는 모든 파티션에 스캐터/개더를 실행할 필요없이 원하는 용어를 포함하는 파티션에게만 요청을 보냄

단점

전역 색인은 쓰기가 느리고, 복잡하다는 단점
- 단일 문서를 쓸 때 해당 색인의 여러 파티션에 영향을 줄 수 있기 떄문
- 문서에 있는 모든 용어가 다른 노드에 있는 다른 파티션에 속할 수 있음

현실적으로 전역 보조 색인은 대개 비동기로 갱신

쓰기를 실행한 후, 바로 색인을 읽으면 변경 사항이 색인에 반영되어있지 않을 수 있음

리악의 검색기능, 오라클의 데이터웨어하우스가 대표적인 예시

파티션 재균형화

시간이 자나면서 생기는 데이터베이스의 변화

질의 처리량이 증가해서 늘어난 부하를 처리하기 위해 CPU 더 추가하고 싶음
데이터 셋이 키져서 디스크 및 램을 추가하고 싶음
장비가 장애가 발생해서 그 장비가 담당하던 역할을 다른 장비로 넘겨받아야함

이런 변화가 생기면 데이터와 요청이 한 노드에서 다른 노드로 이동해야함

재균형화(Rebalancing)

클러스터에서 한 노드가 당당하던 부하를 다른 노드로 옮기는 과정

재균형화가 실행될 떄, 만족시킬 것으로 기대되는 최소 요구사항

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

1. 해시값에 Mod N 연산 수행

쓰면 안되는 방법

노드 개수 N이 바뀌면 대부분의 키가 노드 사이에 옮겨짐
즉, 키가 자주 이동하면 재균형화의 비용이 커짐

2. 파티션 개수 고정

파티션을 노드 대수보다 많이 만들고 각 노드에 여러 파티션을 할당하는 ㅂ아법

10대의 노드에 파티션을 1000개로 쪼갠 뒤, 각 노드마다 약 100개의 파티션 할당

클러스터에 노드가 추가되면 새 노드는 파티션이 다시 균일하게 분배될 때까지 기존노드에서 파티션 몇개를 뺏어올 수 있음

파티션은 노드 사이에서 통쨰로 이동하기만 함
파티션 개수는 바뀌지 않고 파티션에 할당된 키도 변경되지 않음
유일한 변화는 노드에 어떤 파티션이 할당되는가 뿐
파티션 할당 변경은 즉시 반영되지 않고 네트워크를 통해 대량의 데이터를 전송해야하므로 시간이 좀 걸림
- 데이터 전송 중에 요청이 들어오면, 기존에 할당된 파티션 사용
이론상으로, 클러스터 내 성능 좋은 서버에 더 많은 파티션을 할당함으로써 더 많은 부하를 부담하게 할 수 있음
- 리악, 엘라스틱서치, 카우치베이스, 볼드모트에서 사용
처음 설정한 파티션 개수가 사용 가능한 노드 대수의 최대치로 충분히 높은 값을 선택해야함
- 개별 파티션도 관리 오버헤드가 있으므로, 너무 큰 수를 선책하면 역효과가 될 수 있음
전체 데이터셋의 크기 변동이 심하면, 적절한 파티션 개수를 정하기 어려움
파티션이 너무 크면 재균형화를 실행할 때와 노드 장애로부터 복구할 때 비용이 큼
그러나 파티션이 너무 작으면 오버헤드가 너무 큼

3. 동적 파티셔닝

키 범위 파티셔닝을 사용하는 데이터베이스는 파티션 경계와 개수가 고정돼 있는게 매우 불편함

파티션 경계를 잘 못 설정하면 모든 데이터가 한 파티션에 저장되고 나머지는 빌 수 있음
즉, 파티션 경계를 수동으로 재설정하는 것은 매우 성가심

Hbase, 리싱크DB처럼 키 범위 파티셔닝을 사용하는 데이터베이스는 파티션을 동적으로 만듬

파티션 크기가 설정된 값을 넘어서면 파티션을 두개로 쪼갬 ( Hbase는 10G )

반대로 데이터가 많이 삭제되어 파티션 크기가 임계치보다 작아지면 인접 파티션과 합침

이 과정은 B트리의 최상위 레벨에서 행되는 작업과 유사

각 파티션은 노드 하나에 할당되고, 각 노드는 여러 파티션을 담당

큰 파티션을 쪼갠 후 부하의 균형을 맞추기 위해 분할된 파티션 중 하나가 다른 노드에 이동될 수 있음
HBase 경우 hdfs를 통해 파티션 파일이 전송됌

장점

파티션 개수가 전체 데이터 용량에 맞춰 조정된다는 이점
데이터 양이 작으면 파티션 개수가 적어도 되므로 오버헤드가 작음
데이터 양이 크면 개별 파티션의 크기는 설정된 최대치로 제한함

그러나

빈 데이터베이스는 파티션 경계를 어디로 정해야하는지에 대한 사전 정보가 없음
그래서, 시작할 때는 파티션이 하나라는 함정이 있음
이 문제를 해결하고자 Hbase나 몽고DB에서는 빈 데이터베이스에 초기 파티션 집합을 설정할 수 있게 함
- 이를 사전 분할(pre-splitting)이라 함

동적 파티셔닝은 키 범위 파티셔닝뿐아니라, 해시 파티셔닝에도 똑같이 사용될 수 있음

4. 노드 비례 파티셔닝

동적 파티셔닝에서는 파티션 분할과 병합을 총해 개별 파티션 크기가 어떤 고정된 최솟값과 최댓값 사이에 유지되게 하므로 파티션개수가 데이터 크기에 비례힘

반면 파티션 개수를 고정하면 개별 파티션의 크기가 데이터셋 크기에 비례
모두 파티션 개수는 노드 대수와 독립적

파티션 개수는 노드 대수에 비례하게 하는 것

카산드라와 케타마(Ketama)에서 사용하는 방법
노드 당 할당되는 파티션 개수를 고정하는 것
노드 대수가 변하지않은 동안은 개별 파티션 크기가 데이터셋 크기에 비례해서 증가함
그러나 노드 대수를 늘리면 파티션 크기는 다시 작아짐
데이터 용량이 클수록 데이터를 저장할 노드도 많이 필요하므로 개별 파티션 크기도 상당히 안정되게 유지됌

새 노드가 추가되면 고정된 개수의 파티션을 무작위로 선책해 분할하고 각 분할된 파티션의 절반은 그대로두고 나머지는 새 노드에 할당

무작위로 선택해서 균등하지 않은 분할이 생길 수 있음
하지만, 여러 파티션에 대해 평균적으로 보면 새 노드는 기존 노들이 담당하던 부하에서 균등한 몫을 할당받게 된다

파티션 경계를 무작위로 선택하려면 해시 기반 파티셔닝을 사용해야함

해시 함수를 통해 생성된 숫자 범위로부터 파티션 경계를 선택할 수 있음

최근에 나온 해시 함수를 쓰면 메타데이터 오버헤드를 낮추면서도 비슷한 효과를 얻을 수 있음

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

그러면.. 자동으로 실행될까, 수동으로 실행될까?

완전 자동 재균형화

관리자의 개입없이 시스템이 자동으로 언제 파티션을 노드 사이에 이동할지 결정함

완전 수동 재균형화

관리자가 명시적으로 파티션을 노드에 할당하도록 설정하고, 관리자가 재설정할 때만 파티션 할당이 변경됌

이 두개의 중간 지점이 있음

카우치베이스, 리악, 볼드모트는 자동으로 파티션 할당을 하지만, 반영하려면 관리자가 확정해야함

완전 자동 재균형화

손이 안가 편리함

에측하기 어려움

요청 경로를 재설정해야하고 대량의 데이터를 이동하므로 비용이 큰 연산

주의깊게 처리하지 않으면 네트워크나 노드에 과부화 + 재균형화 중에는 다른 요청이 성능 저하가 될 수 있음

요청 라우팅

클라이언트가 요청을 어디에다가 보내야하는가? 밑에 사진과 같이 3가지 방법이 있을 수 있음

클라이언트가 아무 노드에나 접속함
- 라운드로빈 로드 밸런서 등을 활용해서..
- 만약 해당 노드에 요청이 적용할 파티션이 있다면, 직접 처리
- 없다면, 요청을 올바른 노드로 전달해서 응답을 받고 클라이언트에 응답 전달
클라이언트의 모든 요청울 라우팅 계층으로 먼저 보냄
- 라우팅 계층에서는 각 요청을 처리할 노드를 알아내고, 해당 노드로 요청 전달
- 라우팅 계층 자체에는 아무 처리도 하지 않고, 파티션 인지 로드 밸런서로 동작할 뿐 (partition-aware)
클라이언트가 파티셔닝 방법과 파티션이 어떤 노드에 할당됐는지 알고 있게 함
- 클라이언트는 중개자 없이 올바른 노드에 바로 접속

모든 경우에 핵심 문제는 라우팅 결정을 내린는 구성요소가 노드에 할당된 파티션의 변경사항을 어떻게 하는가?

노드 중 하나일 수 도, 라우팅 계층일 수 도, 클라이언트 일 수도 있음

이 문제는 모든 노드에서 가지고 있는 정보가 일치해야므로 다루기 어려움..

그렇지 않으면 요청이 잘못된 노드로 전송되고 제대로 처리 못함
분산 시스템에서 합의를 이루는데 쓰는 프로토콜이 있지만 제대로 구현하기가 까다로움

그래서!!!

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

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

예시)

링크드인의 에스프레소는 헬릭스(Helix)
- 헬릭스는 다시 주키퍼에 의존함
HBase, 솔라 클라우드, 카프카도 파티션 할당을 추적하는데 주키퍼를 사용함
몽고DB는 자체적인 설정서버(config server) 구현에 의존하고 몽고스(mongos)데몬을 라우팅 게층에 사용함
카산드라, 리악은 가십 프로토콜(gossip protocol) 사용해 클러스터의 상태변화를 노드 사이에 퍼트림
- 아무나 요청을 받을 수 있고, 요청받은 노드는 적한한 노드에 라우팅함
카우치베이스는 재균형화를 자동으로 실행하지 않아, 클러스터 노드로부터 변경된 라우팅 정보를 알아내는 목시(moxi)라는 라우팅 계층을 설정

클라이언트는 라우팅 계층을 사용하든, 노드에 요청을 보낼 때도 접속할 IP를 주소를 알아야함

IP주소는 노드에 할당된 파티션 정보만큼 자주 바뀌지 않으므로, IP주소를 찾는데는 대개 DNS 쓰는 것이 충분함

병렬 질의 실행

분석용으로 자주 쓰는 대규모 병렬 처리(massively parallel processing, MPP) 관계형 데이터베이스는 복잡한 종류의 질의를 지원

join, filter, grouping, aggregation 등

MPP 질의 최적화기

복잡한 질의를 여러 실행 단계와 파티션으로 분해하고
이들 중 다수는 데이터베이스 클러스터 내의 서로 다른 노드에서 병렬적으로 실행
데이터셋의 많은 부분을 스캔하는 연산을 포함하는 질의는 특히 병렬 실행의 혜택을 받음