designing-data-intensive-applications

처리량이 매우 높다면 파티션으로 쪼갤 필요가 있다. 이러한 작업을 샤딩이라고한다.

파티션을 나눌 때는 보통 각 데이터 단위(레코드, 로우, 문서)가 하나의 파티션에 속하게 한다. 여러 파티션을 동시에 건드리는 연산을 지원할 수 있지만, 결과적으로 각 파티션은 그 자체로 작은 데이터베이스가 된다.

파티셔닝을 원하는 주된 이유는 확장성이다. 비공유 클러스터에서 다른 파티션은 다른 노드에 저장될 수 있다. 따라서 여러 디스크에 분산 시켜 질의 부하를 여러 프로세서에 분산시킬 수 있다.

단일 파티션에 실행되는 질의를 생각해보면, 독립적으로 실행할 수 있으므로 노드를 추가함으로써 질의 처리량을 늘릴 수 있다. (Scale out)

파티셔닝과 복제

• 복제와 파티셔닝을 함께 적용하여 각 파티션의 복사본을 여러 노드에 저장
• 내결함성을 보장
• 한 노드에 여러 파티션을 저장할 수 있다.
• 각 파티션의 리더는 하나의 노드에 할당
• 팔로워들은 다른 노드에 할당 각 노드의 파티션들은 리더가 될 수 있고, 팔로워가 될 수 있다.

Key-Value 데이터 파티셔닝

파티셔닝의 목적

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

A 파티션이 B 파티션보다 데이터가 많거나 질의를 많이 받는 파티션이 있다면 쏠렸다(skewed)고 말한다.

• 이러한 경우 효과가 매우 떨어진다.
• 부하가 높은 파티션을 핫스팟이라고 한다.

레코드를 할당할 노드를 무작위로 선택하면 핫스팟을 피할 수 있다. 하지만 어떤 레코드를 읽으려고 할 때 레코드가 어느 노드에 저장되어있는지 찾기 위해 모든 노드에서 병렬적으로 질의를 실행해야 한다.

키 범위 기준 파티셔닝

방법 하나는 각 파티션에 연속된 범위의 키를 할당하는 것이다. 범위들 사이의 경계를 알면 어떤 키가 어느 파티션에 속하는지 알 수 있다.

• 키 범위 크기가 동일할 필요는 없다.
• 데이터를 고르게 분산시키려면 파티션 경계를 데이터에 맞춰 조정해야 한다.

파티션 경계는 관리자가 수동으로 하거나, 자동으로 DB가 선택하게 할 수 있다.

각 파티션 내에서는 키를 정렬된 순서로 저장할 수 있다.

장점

• 범위 스캔이 쉬워짐
• 질의 하나로 관련 레코드 여러 개를 읽어올 수 있다. ex) 측정 값의 타임스탬프를 key로 사용하게 되면 범위 스캔이 매우 유용하다.

단점

• 특정한 접근 패턴이 핫스팟을 유발 ex) 타임스탬프가 key라면 파티션은 시간 범위에 대응된다.

키의 첫 번째 요소로 타임스탬프가 아닌 다른 것을 사용해야 한다.

키의 해시값 기준 파티셔닝

키의 파티션을 정하는 데 해시 함수를 사용한다.

해시 함수는 쏠린 데이터를 입력으로 받아 균일하게 분산되게 한다. 해시 함수를 사용하면 입력 문자열이 거의 유사해도, 해시값은 숫자 범위 내에서 균일하게 분산된다.

해시 함수를 정한 후 해시값 범위를 할당하고 해시값이 파티션의 범위에 속하는 모든 키를 파티션에 할당하면 된다.

파티션 경계

1. 크기가 동일하도록 나누는 방법
2. 무작위에 가깝게 선택하는 방법 일관성 해싱이라고 부름.

일관성 해싱

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

단점

• 범위 질의를 효율적으로 실행할 수 없다. 리악, 카우치베이스, 볼드모트에서는 기본키에 대한 범위 질의를 지원하지 않는다.

카산드라

• 복합 기본키를 지정한다.
• 키의 첫 부분만 해싱하고 남은 키는 데이터를 정렬하는 연쇄된 Index로 사용한다. -> 해싱 키는 범위 질의를 할 수 없지만, 해싱 키를 고정된 값을 지정하면, 다른 컬럼에 대해서는 범위 스캔을 할 수 있다.

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

핫스팟은 완벽히 제거할 수 없다. 항상 동일한 키를 읽고 쓰는 극단적인 상황에서는 모든 요청이 동일한 파티션으로 쏠리게 된다.

ex) 유명인 A의 게시글에 많은 사람들이 댓글을 달 경우 -> A게시글의 해싱 값을 계속 사용하기 때문에 핫스팟이 생긴다.

이러한 경우 애플리케이션에서 완화시켜야 함. 가장 간단한 해결책은 키의 시작이나 끝에 임의의 숫자를 붙이는 것이다. 한 키에 대한 쓰기 작업을 다른 키로 균등하게 분산시키고 그 키들은 다른 파티션으로 분산될 수 있다.(????)

다른 키에 쪼개서 쓰면 읽기를 실행할 때 추가적인 작업이 필요하다.

• 트레이드 오프를 잘 고려하여 필요한 부분에만 적용시키는 것이 좋다. 아무곳이나 적용하면 오버헤드가 발생하고, 어디에도 적용하지 않으면 핫스팟이 발생함.

파티셔닝과 보조 색인

보조 색인은 레코드를 유일하게 식별하는 용도가 아닌, 특정한 값이 발생한 항목을 검색하는 수단이다.

ex)

• 사용자123이 실행한 액션 찾기
• hogwash 라는 단어를 포함하는 모든 글 찾기
• 빨간색 자동차를 모두 찾기

보조 색인은 RDB에선 핵심이며, 문서 DB에서도 흔하다. 또한 ELK나 솔라 같은 전문 검색에서는 존재의 이유다.

보조 색인은 2가지 방법으로 나뉜다.

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

문서 기준 보조 색인 파티셔닝

• 문서ID(Document)를 기준으로 파티셔닝
• 색상과 제조사로 파티셔닝 하기 위해 color, make 보조색인 생성.
• DB 파티션은 자동으로 그것을 color:OO 색인 항목에 해당하는 문서 ID 목록에 추가한다.

이렇게 하면 각 파티션이 완전히 독립적으로 동작한다. 각 파티션은 자신의 보조 색인을 유지하며, 그 파티션에 속하는 문서만 담당한다. 다른 파티션은 전혀 신경쓰지 않을 수 있다.

지역 색인(Local Index)이라고도 부름

하지만 이렇게 할 경우 모든 파티션에 질의를 보내 얻은 결과를 모아야 한다. 이러한 방식을 스캐터/개더(scatter/gather) 라고 한다. 스캐터/개더는 꼬리 지연 시간이 증폭하기 쉽다.

대부분은 단일 파티션에서만 사용하도록 하는것을 권장하며 많은 DB에서 이러한 방식을 사용한다.

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

자신만의 보조 색인을 갖게하는 대신, 모든 파티션의 데이터를 담당하는 전역 색인을 만들 수 있다.

이러한 색인을 파티셔닝 할 때 용어의 해시값을 사용할 수도 있다.

• 용어 자체로 하면 범위 스캔에 유용하다.
• 해시값을 사용하면 부하가 좀 더 고르게 분산된다.

장점

• 읽기가 효율적
• 스캐터/개더를 할 필요가 없다.

단점

• 쓰기가 느리다.
• 복잡하다. 전역 색인은 비동기로 갱신된다. 실제 갱신하는데에는 1초도 걸리지 않지만, 여러 결함 문제로 인해 지연시간이 길어질 수 있다.

파티션 재균형화

시간이 지나면 DB에 변화가 생기게 된다.

• 질의 처리량이 증가해서 CPU를 추가하고 싶다.
• 데이터셋 크기가 증가해서 디스크와 램을 추가하고 싶다.
• 장비에 장애가 발생해서 다른 장비가 넘겨받아야 한다.

이러한 경우 요청을 A 노드에서 B 노드로 옮겨야 한다. A가 담당하던 부하를 B로 옮기는 과정을 재균형화(Rebalancing) 라고 한다.

최소 요구사항

• 재균형화 후, 부하가 클러스터 내에 있는 노드들 사이에 균등하게 분배
• 재균형화 도중에도 DB는 정상적으로 읽기 쓰기 처리
• 빨리 실행되고, 네트워크와 디스크 I/O 부하를 최소화 할 수 있도록 노드들 사이에 데이터가 필요 이상으로 옮겨져서는 안 된다.

쓰면 안되는 방법 : 해시값에 모드 N 연산을 수행

노드 개수 N이 바뀌게 되면 키가 노드 사이에서 옮겨져야 된다는 문제가 있다. 키가 자주 이동하게 되면 재균형화 비용이 지나치게 커진다.

데이터를 필요 이상으로 이동하지 않는 방법이 필요하다.

파티션 개수 고정

해결책 : 파티션을 노드 대수보다 많이 만들고, 각 노드에 여러 파티션을 할당

클러스터에 노드가 추가되면 새 노드는 파티션이 다시 균일하게 분배될 때까지 기존 노드에서 파티션 몇 개를 뺏어올 수 있다. 클러스터에서 노드가 제거되면 이 과정이 반대로 실행된다.

파티션은 노드 사이에서 통째로 이동하기만 한다. 파티션 개수는 변하지 않고, 파티션에 할당된 키도 변경되지 않는다. 하지만 네트워크를 통해 대량의 데이터를 전송해야 하므로 시간이 많이 걸린다.

이러한 방식을 사용하게 되면 처음 DB를 구축할 때 파티션 개수가 고정되고 이후엔 변하지 않는다.

처음 설정된 파티션 개수가 사용 가능한 노드 대수의 최대치가 되므로 미래에 증가될 것을 수용하기에 충분히 높은 값으로 설정해야 한다. 하지만, 관리 오버헤드가 있으므로 너무 큰 수를 선택하면 역효과를 낳을 수 있다.

동적 파티셔닝

동작 방식

• 파티션 크기가 설정된 값을 넘어가면 (ex. 10GB) 파티션을 두 개로 쪼개 각각에 파티션의 절반 정도의 데이터가 포함되게 한다.
• 반대로 많이 삭제될 경우 임계값 아래로 떨어지면 인접한 파티션과 합쳐질 수 있다.
• Like B트리

장점

• 파티션 개수가 전체 데이터 용량에 맞춰 조정된다.
• 데이터 양이 작으면 파티션 개수도 적다.
• 데이터 양이 많으면 개별 파티션의 크기는 설정된 최대치로 제한된다.

ZeroBase 데이터베이스는 파티션 경계를 어디로 정해야 하는지에 관한 사전 정보가 없으므로 시작할 때는 파티션이 하나이다. 데이터 셋이 작을 때는 모든 쓰기 요청이 하나의 노드에서 실행되고, 다른 노드들은 유휴 상태에 머물게 된다.

또한 해시 파티셔닝에서도 사용할 수 있다.

노드 비례 파티셔닝

동적 파티셔닝

• 파티션 개수가 데이터셋 크기에 비례한다. 고정 파티셔닝
• 개별 파티션의 크기가 데이터셋 크기에 비례한다. 두 경우 모두 파티션 개수는 노드 대수와 독립적이다.

노드 비례 파티션

• 노드 대수가 변함이 없으면 개별 파티션 크기가 데이터셋 크기에 비례해서 증가한다.
• 노드 대수를 늘리면 파티션 크기는 다시 작아진다.

새 노드가 클러스터에 추가되면 고정된 개수의 파티션을 무작위로 선택해 분할한다. 균등하지 않은 분할이 생길 수 있지만 평균적으로는 균등한 몫을 할당받게 된다.

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

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

자동 재균형화

• 유지보수에 손이 덜 가므로 편리하다.
• 하지만 예측하기 어렵다.

수동 재균형화

• 관리자가 직접 파티션을 노드에 할당하도록 설정

카우치베이스, 리악, 볼드모트는 자동으로 할당을 제안하지만 반영하려면 수동으로 하는 방법을 사용한다.

요청 라우팅

서비스 찾기(Service discovery)

• 어떤 노드로 접속해야 할 지 알아야 한다.
  1. 클라이언트가 아무 노드에나 접속하게 한다.(ex. 라운드 로빈 로드밸런서)
  1. 자신이 처리할 수 있다면 처리한다.
  2. 처리를 못한다면 다음 노드에게 넘긴다.
     1. 모든 요청을 라우팅 계층으로 먼저 보낸다.
  3. 라우팅 계층에서 노드를 찾는다.
  4. 찾은 노드에 요청을 전달한다.
     1. 클라이언트가 어떤 노드에 할당됐는지 알게 한다.
  5. 바로 해당 노드로 요청을 전송한다.

보통 대부분은 클러스터 메타데이터를 추적하기 위해 주키퍼 같은 별도의 코디네이션 서비스를 사용한다. 각 노드는 주키퍼에 자신을 등록하고, 주키퍼는 파티션과 노드 사이의 신뢰성 있는 할당 정보를 관리한다.

라우팅 계층은 주키퍼에 있는 정보를 구독할 수 있다. 노드가 추가되거나 삭제되거나, 파티션 소유자가 바뀌게 되면 주키퍼는 라우팅 계층에 이를 알려서 라우팅 정보를 최신으로 유지한다.

클라이언트는 라우팅 계층을 사용하거나, 임의의 노드로 요청을 보낼 때도 접속할 IP 주소를 알아내야 한다. IP 주소는 노드에 할당된 파티션 정보만큼 자주 바뀌지 않으므로 IP 주소를 찾는 데는 대개 DNS를 쓰는 것으로 충분하다.

병렬 질의 실행

대규모 병렬 처리(massively parallel processing, MPP)

• join, filtering, grouping, aggregation 연산을 포함한다.
• MPP 옵티마이저는 복잡한 질의를 여러 실행 단계와 파티션으로 분해한다.
• 병렬적으로 실행한다.