개요
파티셔닝을 사용하는 이유
- 확장성. shared-nothing architecture 에서 파티션은 다른 노드에 저장될 수 있기에, 데이터셋이 여러 디스크로 분산될 수 있고 질의 부하 역시 여러 프로세서에 분산될 수 있다.
목차
- 파티셔닝 방법
- 인덱스와 파티셔닝의 상호작용
- 노드 추가/제거로 인한 리밸런싱
- 쿼리 라우팅
Partioning and Replication
보통 복제와 파티션을 함께 적용하여, 파티션의 레플리카를 여러 노드에 저장한다. 이를 통해, 파티션에 대한 내결함성을 높일 수 있다.
Key-Value 데이터 파티셔닝
파티셔닝의 목적
- 데이터와 질의 부하를 고르게 분산시키는 것
쏠림(skewed) 현상
- 특정 파티션에 데이터와 질의 부하가 집중되는 현상
- 쏠릴 수록 파티셔닝의 효과가 떨어짐
- 쏠린 파티션을 핫스팟 이라고 한다.
키 범위 파티셔닝
백과사전처럼 각 파티션에 연속된 범위의 키를 할당하는 방법
각 파티션 내에서는 키를 정렬된 순서로 저장할 수 있다.
- 이 경우 범위 스캔이 쉬워진다.
핫스팟을 유발할 수 있는 단점이 있다.
- 타임스탬프가 키이고, 1일치의 데이터가 하나의 파티션이라고 하자.
- 이 경우 최신 파티션에만 집중적인 쓰기 연산이 이루어질 수 있다.
- 센서 데이터베이스에서 이 문제를 해결하기 위해 suffix 로 센서 이름을 붙이는 방법을 사용할 수 있다.
해시 파티셔닝
키의 해시값을 기반으로 범위 파티셔닝을 하는 방법
좋은 해시 함수는 쏠린 데이터를 균일하게 분산한다.
파티셔닝용 해시 함수는 암호적으로 강력할 필요가 없다.
프로그래밍 언어에 내장된 해시 함수가 파티셔닝에는 적합하지 않을 수도 있으니, 확인이 필요하다.
- Java 의 Object.hashCode() 는 같은 키를 넣어도 다른 프로세스에서는 다른 해시값을 반환하는 비결정적 행태를 보일 수 있다.
키 범위 파티셔닝과 달리 해시 파티셔닝은 범위 쿼리에 비효율적이다.
- 카산드라는 복합 키본키를 지정하여 범위 쿼리를 보완한다. 첫 번째 키는 해시를 사용하여 파티셔닝을 결정한다. 남은 컬럼에 대해서는 SS테이블의 정렬 키로 사용하도록 하여, 같은 키에 대해 범위 쿼리를 효율적으로 실행하도록 한다.
- 위 복합 기본키의 유즈케이스로, 소셜 미디어 사이트에서 (user_id, update_timestamp) 를 복합키로 하여 특정 사용자의 특정 시간대의 수정 문서에 대한 범위 쿼리를 효율적으로 수행할 수 있다.
쏠린 작업부하와 핫스팟 완화
(Skewed Workloads and Relieving Hot Spots)
해시 파티셔닝을 한다 해도 핫스팟을 완전히 제거할 수는 없다. 하나의 키가 핫 키인 경우 그럴 수 있다.
- 가령, 수 만 명의 팔로워가 있는 유명인은 핫 키가 될 위험이 있다.
핫 키에 대한 해결 방법 중 하나는 핫 키에 대해 suffix 나 postifx 로 숫자를 붙이는 것이다.
- 하지만 이 경우, 핫 키에 대해 조회하기 위해서 숫자를 붙인 만큼 키 쿼리가 이루어져야 한다.
- 이 방법은 요청이 몰리는 소수의 핫 키에 대해서만 적용되어야 한다.
Paritioning and Secondary Indexes
secondary index(보조 인덱스) 는 다음의 경우 사용된다.
- secondary index 는 하나의 레코드를 찾기 보단 범위 쿼리에 사용된다.
- 예를 들어, 사용자1이 실행한 액션들을 찾거나, 빨간색 자동차를 모두 찾는 작업 등에 스인다.
- secondary index 는 솔라나 엘라스틱서치 같은 검색 서버에서는 중요하게 사용된다.
secondary index 는 파티션에 깔끔하게 대응되지 않는 문제점이 있다.
secondary index 가 있는 DB 를 파티셔닝 하는 데 널리 쓰이는 두 가지 방법이 있다.
- 문서 기반 파티셔닝
- 용어 기반 파티셔닝
문서 기준 secondary index 파티셔닝
Partitioning Secondary Indexes by Document
각 파티션이 독립적인 secondary index 를 갖는 방식
예를 들어 중고차를 판매하는 웹사이트를 운영한다고 하자.
- 각 항목에는 문서 ID 라고 불리는 고유 ID 가 있고, DB 는 문서 ID를 기준으로 파티셔닝 한다.
- 차를 색상과 제조사로 필터링 할 수 있도록 color, make 속성에 secondary index 를 만든다.
이런 index 방식에선 각 파티션이 독립적으로 동작한다.
- 각 파티션은 자신의 secondary index 만 유지하며, 그 파티션에 속하는 데이터만 담당한다.
- 다른 파티션에 대해선 신경 쓰지 않는다.
- 따라서 이러한 문서 파티셔닝 색인을 지역 index(loal index) 라고도 한다.
하지만, 문서 기준으로 파티셔닝된다면 모든 파티션에 질의를 보내야한다.
- 빨간색 차를 조회하기 위해 모든 파티션을 조회한다.
- 이런 방식을 scatter/gather 방식이라고 한다.
- 단점
- secondary index 를 사용하여 읽는 질의는 큰 비용이 들 수 있다.
- 일부 요청의 지연으로 전체 요청의 응답이 지연되는 꼬리 지연 시간 증폭(tail latency amplification)이 발생하기 쉽다.
그럼에도 많은 DB 들이 문서 기준 secondary index 를 사용하고 있다.
용어 기준 secondary index 파티셔닝
Partitioning Secondary Indexes by Term
모든 파티션의 데이터를 담당하는 전역 index(global index) 를 만드는 방식
찾고자 하는 용어에 따라 secondary index 파티션이 결정되므로, 이런 방식의 index 를 용어 기준으로 파티셔닝(term-paritioned)되었다고 한다.
- 용어(term) 이란 이름은 문서에 등장하는 모든 단어를 의미한다.
용어 기준 파티셔닝에서 용어 자체를 사용할 수도 있고, 용어의 해시값을 사용할 수도 있다.
- 용어 자체를 사용하는 경우: 범위 스캔에 유용
- 용어의 해시값을 사용하는 경우: 부하가 고르게 분산
장점
- scatter/gather 를 하지 않아도 되어서 local index 에 비해 읽기가 효율적이다
단점
- 쓰기가 느리고 복잡하다. 단일 문서를 쓸 때, 해당 index의 여러 파티션에 영향을 줄 수 있다. 극단적인 경우를 생각해보면, 문서에 있는 모든 용어가 다른 노드에 있는 다른 파티션에 속할 수 있다.
- 문서 쓰기 index로 반영되는데 지연이 발생할 수 있다. 바로 반영을 원한다면, 분산 트랜잭션이 필요하나 분산 트랜잭션을 지원하는 D 는 한정적이다. 현실적으로 대개 비동기 방식으로 index 가 갱신된다.
Rebalancing Partitions
자원을 늘려야하는 경우, 장애로 인해 다른 노드가 대신 처리해야하는 경우 리밸런싱이 일어날 수 있다.
리밸런싱 시 파티셔닝 방식에 따라 기대하는 요구사항들이 있다.
- 리밸런싱 이후 부하가 균등하게 분배되어야 한다.
- 리밸런싱 도중에도 DB 읽기 쓰기 요청을 받을 수 있어야 한다.
- 리밸런싱으로 인해 옮겨지는 데이터가 최소화 되어서, 리밸런싱 시간을 최소화 해야 한다.
리밸런싱은 요청 경로를 재설정해야 하고 대량의 데이터를 노드 사이에 이동해야 하므로 비용이 큰 연산이다.
- 주의 깊게 처리하지 않으면 네트워크나 노드에 과부화가 걸릴 수 있다.
- 리밸런싱이 진행 중인 동안 실행되는 다른 요청의 성능이 저하될 수 있다.
Rebalacing 전략
쓰면 안되는 방법: 해시값에 mod N 연산을 실행
책에서는 키의 해시값 파티셔닝에서 hash(key) 값을 구간을 나누어서 할당하는 방법이 최선이라고 했다.
파티션 개수 N 에 대하여 mod N 연산을 수행하지 않는 이유는 N 이 바뀌면 대부분의 키가 리밸런싱의 영향을 받아서 리밸런싱 시간이 길어질 수 있다는 점이다. 해시링을 생각하면 될 것 같다.
파티션 개수가 고정돼있다면, 큰 문제는 아닐 것 같다.
데이터의 이동을 최소화하는 방법에 대해 알아보자.
파티션 개수 고정
파티션을 노드 대수보다 많이 만들고 각 노드에 여러 파티션을 할당하는 것이다. 예를 들어, 노드 10 대 파티션 1,000개로 설정하여 하나의 노드가 100개의 파티션을 처리하도록 한다.
클러스터에 노드가 추가되면 균등하게 분배될 때까지 기존 노드에서 파티션을 한 개 씩 뺏어온다. 클러스터에 노드가 제거되면 이 과정을 반대로 실행한다.
이렇게 하면, 파티션이 통째로 이동하므로 파티션 개수가 바뀌지 않고 파티션에 할당된 키도 변경되지 않는다.
파티션 수를 고정하기 위해, 처음 설정시 충분히 높은 값을 파티션 값으로 선택한다. 그러나 너무 큰 경우 개별 파티션의 관리 오버헤드가 있으므로 주의해야한다.
전체 데이터셋의 크기 변동이 심하다면 적절한 파티션 수를 정하기 어렵다. 파티션 자체의 크기가 너무 크면 리밸런싱 비용이 증가하고, 너무 작으면 오버헤드가 커진다. 파티션 수가 고정돼 있고, 데이터셋 크기가 변한다면 적절한 크기를 정하긴 어려울 수 있다.
동적 파티셔닝
파티션 크기에 고정 임계값을 사용하여 파티션 분할과 병합을 통해 동적 파티션을 제공하기도 한다.(HBase, 리싱크DB)
- 파티션 크기가 설정된 값을 넘어서면 파티션을 두 개로 쪼갠다.
- 반대로 데이터가 적어져서 파티션 크기가 임계값 아래로 떨어지면 인접한 파티션과 합쳐질 수 있다.
- 파티션이 쪼개진 후 부하의 규형을 맞추기 위해 분할된 파티션 중 하나가 다른 노드로 이동될 수 있다.
- 파티션 크기를 고정으로 하여 파티션 개수가 데이터셋 크기에 비례한다.
장점
- 파티션 개수가 전체 데이터 용량에 맞춰 조정된다.
한계
- 파티션 경계를 어디로 정해야 하는지 사전 정보가 없으므로 시작 할 때는 파티션이 하나다.
- 한 노드만이 파티션을 처리하기 때문에 다른 노드들은 유휴 상태가 된다.
- 이를 극복하고자 초기 파티션 집합 설정 기능을 제공하기도 한다.(HBase, 몽고DB)
노드 비례 파티셔닝
노드에 할당되는 파티션 개수를 고정한다.(카산드라, Ketama)
- 노드가 변하지 않다면 파티션 크기가 데이터셋 크기에 비례한다.
- 노드가 추가되면 파티션 크기는 작아진다.
- 노드가 추가되면 고정된 개수의 파티션을 무작위로 선택해 분할하여 새 노드에 할당한다.
운영: 자동 리밸런싱과 수동 리밸런싱
완전 자동 리밸런싱: 시스템 자동으로 리밸런싱
- 장점: 유지보수 비용이 적음
- 단점: 리밸런싱 결과를 예측하기 어려움.
완전 수동 리밸런싱: 관리자가 명시적으로 할당 정보를 설정함
- 장점: 리밸런싱으로 인한 예상치 못한 상황을 통제할 수 있음
중간 단계의 리밸런싱: 시스템이 파티션 할당을 제안하고 관리자가 확정함
Request Routing
특정 키에 대해 요청할 때 어느 파티션에 있는지 찾아야 함.
좀 더 일반적인 문제인 서비스 찾기(service discovery) 의 일종.
라우팅 결정을 내리는 구성요소(가칭 라우터, 아래 그림의 음영으로 칠해진 부분)의 위치가 다음 세 가지 정도로 추려진다.
1. node. 이러한 방식을 gossip protocol 이라고 한다.
2. routing 계층
3. 클라이언트
문제의 핵심은 라우터가 파티션 할당의 변경 사항을 어떻게 아느냐이다.
모든 라우터가 동일하게 같은 최신 파티션 할당 정보를 가지도록 하는 것이 다루기 어려운 문제이다.
많은 분산 데이터 시스템은 위 그림과 같이 ZooKeeper 와 같은 별도의 코디네이션 서비스를 사용한다.
- 각 노드는 ZooKeeper 에 자신을 등록하고, ZooKeeper 는 파티션과 노드 사이의 신뢰성 있는 할당 정보를 관리한다.
- 어떻게 신뢰성 있는 할당 정보를 만들고 관리할 수 있는 것일까...?
- 라우터는 주키퍼에 있는 정보를 구독하여 라우팅 정보를 최신으로 유지한다.
예시
- 링크드인의 에스프레소는 주키퍼에 의존하는 헬릭스(Helix) 를 써서 클러스터를 관리한다.
- 카프카, 솔라클라우드, HBase 도 주키퍼를 사용하여 파티션 할당 정보를 추적한다.
- 카프카의 경우 파티션 할당은 카프카 브로커에서 하며, 주키퍼는 할당 정보를 저장하고 broadcast 하는 역할을 한다.
- 몽고DB 는 아키텍처는 비슷하지만 자체적인 설정 서버 구현에 의존하고 몽고스 데몬을 라우팅 계층으로 한다.
가십 프로토콜(gossip protocol)
소문(gossip)이 전파돼듯이, broadcast 해주는 마스터가 없어도 각 노드가 메타데이터를 주고 받는 통신 방식.
위 그림 중 1번에 해당한다.
예시
- 카산드라, 리악이 이 방법을 사용하였다.
- 장점: 주키퍼 같은 외부 코디네이션 서비스에 의존하지 않음
- 단점: 노드에 복잡성을 더한다.
카우치베이스는 클러스터 노드로부터 변경된 라우팅 정보를 알아내는 목시(moxi) 라는 라이퉁 계층을 설정한다.(그림의 2번)
클라이언트에선 요청을 보낼 라우터의 IP 주소를 알아야 하지만, IP 주소는 자주 바뀌지 않으므로 대게 DNS 를 쓰는 것으로 충분하다고 한다.
패스트조인
- 패스트조인의 파티션 매니저에선, 파티션 클라이언트와 매니저가 서로 소켓 연결을 하였다. 클라이언트 pod 가 재시동되거나 멈추거나 네트워크 장애가 발생되면 ip 가 변경될 수 있고 소켓 연결이 소실될 위험이 있긴 하다.
- 파티션 대상(jsm)에 요청을 보내는 클라이언트(cp) 는 파티션 매니저의 쿼리 서버, 쿼리 클라이언트를 이용하여, group 의 모든 파티션 할당 정보를 받아서, 요청을 보냈다. 클라이언트 단의 복잡도가 높아지므로, 클러스터 내부의 클라이언트 컴포넌트에 구현하였다.
- 파티션 대상(jsm) 은 파티션 매니저에 리밸런싱(addPartition, dropParition) hook 을 이용하여, 할당 정보를 업데이트 하였었다. 이를 통해, 외부의 호출에 대해 라우팅을 제공했다.
병렬 질의 실행
분석용으로 자주 사용된는 대규모 병렬 처리(massively parallel processing, MPP) 관계형 데이터베이스 제품은 훨신 더 복잡한 종류의 쿼리를 지원한다.
복잡한 쿼리는 대표적으로 join, filtering, grouping, aggregation 연산 등이 있다. 이런 복잡한 쿼리를 여러 실행 단계와 파티션으로 분해하며 이들 중 다수는 서로 다른 DB 노드에서 병렬적으로 실행될 수 있다.
데이터 셋의 많은 부분을 스캔하는 연산을 포함하는 쿼리는 병렬로 실행하는 것이 효과적이다.
MPP 는 10장에서 더 살펴본다.
