파티셔닝

파티셔닝이란

• 데이터 셋이 매우 크거나 질의 처리량이 매우 높다면, 복제만으로는 부족하며 데이터를 파티션으로 쪼갤 필요가 있음. 이를 샤딩이라고도 함

• 파티션은 보통 각 데이터 단위(레코드, 로우, 문서)를 기준으로 구성

• 파티셔닝을 하는 목적

  • 확장성 : 데이터 셋을 여러 디스크에 분산
  • 부하 분배 : 핫스팟(불균형적으로 높은 부하를 받는 노드)가 생기지 않게 하면서 질의 부하를 여러 장비에 균일하게 분배

파티셔닝과 복제

• 복제 복제와 파티셔닝을 함께 적용해 각 파티션의 복사본을 여러 노드에 저장

• 각 레코드가 하나의 파티션에 속하더라도 내결함성을 위해 여러 다른 노드에 저장하는 것

• 하나의 노드에 여러 파티션을 정할 수도 있음
  

  • 리더 팔로워 복제 모델을 사용한다면, 각 파티션의 리더가 하나의 노드에 할당되고, 팔로워들은 다른 노드에 할당되는 식으로 구성할 수 있음

파티셔닝 종류

• 파티셔닝을 하기 위해선 어떤 레코드를 어떤 노드에 저장할지 선택할 기준이 필요함

• 이를 위해서는 파티셔닝의 목적을 생각해볼 필요가 있음 즉, 데이터와 질의 부하를 노드 사이에 고르게 분산되도록 처리되야 함

• 가장 단순한 방법은 레코드를 할당할 노드를 무작위로 선택하는 것이지만, 이 때에는 레코드가 어느 노드에 저장됐는지 알 수 없으므로 모든 노드에서 병렬적으로 질의를 실행해야 함

• Key-Value 데이터 파티셔닝

  • 각 파티션에 연속된 범위에 하나의 키를 할당하고, 데이터를 저장하는 것

  • 키를 통해 어떤 노드에 데이터가 저장되어 있는지 쉽게 찾을 수 있음

  • 단, 데이터를 고르게 분산하기 위해선 키가 포함하는 연속된 범위(파티션 경계)를 데이터 크기에 맞게 적절히 조정해줘야 함

  • 파티션 경계는 관리자가 수동으로 선택하거나 데이터베이스에서 자동으로 선택하게 할 수 있음

  • Key-Value 파티셔닝 전략은 빅테이블, HBase(빅테이블의 오픈소스 구현체), 리싱크DB, 몽고 DB(2.4버전 이하)에서 사용됨

  • 주의할 점은, 특정한 접근 패턴이 핫스팟을 유발할 수 있다는 것

    • 타임스탬프로 키를 구성했을 때, 오늘 하루의 데이터는 특정 파티션 하나가 담당하게 됨

    • 즉, 모든 데이터가 동일한 파티션으로 전달된다는 것을 의미

    • 이런 경우에는 키의 첫 번째 요소로 다른 것을 사용해야 함. ex) 타임스탬프 앞에 센서 이름을 붙여서 사용

• 키의 해시값 기준 파티셔닝

  • 좋은 해시 함수는 쏠린 데이터를 입력으로 받아 균일하게 분산되게 하는 함수

  • 암호학적으로 강력할 필요는 없음

  • 해시 함수를 설정했다면, 각 파티션에 키 범위 대신 해시값 범위를 할당

  • 단점

    • 키 범위 파티셔닝에서의 좋은 속성 바로 범위 질의를 효율적으로 실행할 수 있는 능력을 잃어버림

    • 키 범위 파티셔닝에서 인접하게 존재했던 키들이 모든 파티션에 흩어져서 정렬 순서가 유지되지 않기 때문

    • 몽고DB에서는 해시 기반 샤딩 모드를 활성화하면 범위 질의가 모든 파티션으로 전송되도록 설계되어 있음

    • 카산드라는 두 가지 파티셔닝 전략 사이에서 타협. 카산드라는 테이블을 선언할 때 여러 칼럼을 포함하는 복합 기본키를 지정

      • 이는 키의 첫 부분에만 해싱을 적용하고 남은 칼럼은 카산드라의 SS테이블에서 데이터를 정렬하는 색인으로 사용하는 방식

      • 이를 통해 첫 번째 칼럼에 대한 범위 질의는 불가능하지만, 첫 번째 칼럼에 고정된 값을 지정한 후, 다른 칼럼에 대해 범위 질의를 할 수 있도록

      • 이를 테면, (user_id, update_timestamp)로 지정하여 어떤 사용자가 수정한 모든 문서를 타임스탬프 순으로 정렬해서 읽을 수 있음

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

• 때때로 키를 해싱해서 파티션을 정하더라도 쏠림 작업부하가 완벽히 해결되지 않을 수 있음

• 이를 테면, 소셜 미디어에서 수천 만명의 팔로워를 거느린 유명인이 무언가를 할 경우가 있음

• 이 경우, 쏠린 작업부하를 완화하기 위한 가장 간단한 해결책은 각 키의 시작이나 끝에 임의의 숫자를 붙이는 것

• 임의의 10진수 두 개만 붙이더라도 한 키에 대한 쓰기 작업을 100개의 다른 키로 균등하게 분산될 수 있음

보조 색인

• 보조 색인은 보통 레코드를 유일하게 식별하는 용도가 아니라 특정 값이 발생한 항목을 검색하는 수단으로 사용

  • 사용자 123이 실행한 액션을 모두 찾거나 hogwash라는 단어를 포함하는 모든 글을 찾는 등의 작업에서 쓰임

• 보조 색인은 관계형 데이터베이스의 핵심 요소이며 문서 데이터베이스에서도 흔함. 솔라나 엘라스틱 서치와 같은 검색 엔진에서는 존재의 이유라고 말할 수 있음

• 보조 색인은 파티션에 깔끔하게 대응되지 않는 문제점이 존재

• 크게 문서 기준 보조 색인 파티셔닝과 용어 기준 보조 색인 파티셔닝으로 나눌 수 있음

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

  • 각 항목에 문서 ID라는 고유 ID가 있고, 데이터베이스를 문서 ID를 기준으로 파티셔닝

  • 이를테면 0~499까지 파티션 0에, 500~999까지는 파티션 1에 할당

  • 사용자들이 차를 검색할 때 색상과 제조사로 필터링할 수 있게 color와 make로 보조 색인을 만듦

  • 만일 빨간색 자동차가 데이터베이스에 추가되면 데이터베이스는 자동으로 그것을 color:red 색인 항목에 해당하는 문서 ID 목록에 추가하는 방식

  • 이런 방식은각 파티션이 완전히 독립적으로 동작하는 것을 의미 즉, 각 파티션은 자신의 보조 색인을 유지하며 그 파티션에 속하는 문서만 담당

  • 이런 이유로 문서 파티셔닝 색인은 지역 색인(local index)라고 함

  • 단점은 특정한 색상이거나 특정한 제조사가 만든 자동차가 동일한 파티션에 저장되지 않는 다는 것. 즉, 빨간색 자동차는 파티션 0에도 있고 파티션 1에도 있음(위 그림). 빨간색 자동차를 찾고 싶다면 모든 파티션으로 질의를 보내서 얻은 결과를 모두 모아야 함

  • 이러한 질의 방법을 스캐터/개더(scatter/gather)라고 함. 이런 단점에도 불구하고 몽고DB, 카산드라, 엘라스틱 서치 등은 모두 문서 기준으로 파티셔닝된 보조 색인을 사용

  • 보조 색인 질의가 단일 파티션에서만 실행되도록 피티셔닝 방식을 설계하여 사용하기를 권장하지만, 언제나 그렇게 사용하는 것이 쉬운 일은 아님

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

  • 각 파티션이 자신만의 보조 색인(=지역색인)을 갖게 하는 대신, 모든 파티션의 데이터를 담당하는 전역 색인을 만드는 것을 용어 기준 보조 색인 파티셔닝이라고 함

  • 전역 색인을 하나의 노드에 저장한다면, 해당 노드가 병목점이 될 수 있으므로 여로 노드에 분산되어 저장됨

  • 그림과 같이 빨간색 자동차 정보는 색인에서 color:red에 저장되지만 색깔 색인은 a부터 r까지의 글자로 시작하는 색깔은 파티션 0에 s부터 z까지의 글자로 시작하는 색깔은 파티션 1에 저장됨

  • 즉, 찾고자 하는 용어를 기준으로 파티셔닝됐다는 점에서 용어 기준 보조 색인 파티셔닝이라고 부름

  • 문서 파티셔닝과 비교하자면 전역 색인이 갖는 이점은 읽기가 효율적이라는 점임

    • 클라이언트는 모든 파티션에 scatter/getter를 실행할 필요 없이 원하는 용어를 포함하는 파티션에만 요청을 보내면 되기 때문

    • 하지만, 쓰기가 느리고 복잡하다는 단점이 존재: 쓰기를 수행할 때 여러 파티션에 영향을 줄 수 있기 때문(문서에 있는 모든 용어가 다른 노드에 있는 다른 파티션에 속할 수 있음)

  • 전역 보조 색인은 대개 비동기로 갱신됨(즉, 쓰기를 실행한 후 바로 색인을 읽으면 반영되지 않았을 수 있음) 예를 들어 아마존 다이나모 DB는 보조 색인을 갱신하는 데 1초도 걸리지 않지만, 인프라에 결함이 생기면 지연시간이 더 길어질 수 있음

파티션 재균형화

• 시간이 지나면 데이터 베이스에 변화가 생김

  • 질의 처리량이 증가해서 부하가 늘어나고 이를 처리하기 위해 CPU를 추가해야하는 상황

  • 데이터셋 크기가 증가해서 데이터셋 저장에 사용할 디스크와 램을 추가해야하는 상황

  • 장비에 장애가 발생해서 그 장비가 담당하던 역할을 다른 장비가 넘겨받아야하는 상황 등

• 이런 변화가 생긴다면, 데이터와 요청이 다른 노드로 옮겨져야 하며, 이런 과정을 재균형화라고 함

• 재균형화의 요청사항

  • 재균형화 후, 부하가 균등하게 분배되어야 함

  • 재균형화 중에도 데이터베이스는 읽기 쓰기 요청을 받을 수 있어야 함

  • 재균형화 진행 중 네트워크와 디스크 I/O 부하가 최소화 되어야 함

• 재균형화 전략

  • 해시값에 모드 N 연산을 실행(쓰면 안 되는 방법)

    • 앞서 키의 해시값을 기준을 파티셔닝했지만, 왜 mod(나머지 연산)으로 하지 않을까?

    • N이 바뀔 경우 대부분의 키가 노드 사이에 옮겨져야 하기 때문

  • 파티션 개수 고정
    

  • mod연산의 간단한 해결책은 파티션을 노드 대수보다 많이 만들고 각 노드에 여러 파티션을 할당하는 것

    • 노드 10 대로 구성된 클러스터라면 처음부터 파티션을 1,000개로 쪼개서 각 노드마다 100개의 파티션을 할당

    • 만일 클러스터에 노드가 추가되면 새 노드는 파티션이 균일하게 배치될 때까지 기존 노드에서 파티션 몇 개를 가져오면 됨

    • 파티션을 통째로 가져오므로써 파티션 개수와 파티션에 할당된 키를 변경하지 않고, 단지 노드에 어떤 파티션이 할당되는지에 대한 정보만을 변경

    • 데이터 전송이 진행중인 동안에는 읽기나 쓰기를 기존에 할당된 파티션을 사용하여 처리

    • 이런 방식은 리악, 엘라스틱서치, 카우치베이스, 볼드모트에서 사용

  • 동적 파티셔닝

    • 키 범위 파티셔닝에서 파티션 경계와 개수가 고정되어 있다면 매우 불편함

    • 경계를 잘못 지정하면 모든 데이터가 한 파티션에 저장될 수 있음

    • HBase나 리싱크DB는 파티션을 동적으로 만듦

    • HBase는 피티션이 10GB가 넘어가면 하나의 파티션을 두 개로 쪼개고 각 파티션에 절반의 데이터를 할당함

    • HBase는 데이터를 분산하기 위해 HDFS를 통해 파티션 파일이 전송됨

    • 하지만 빈 데이터베이스에서는 결국 모든 요청이 하나의 노드에서 처리된다는 점이 불편함. 이를 위해 HBase는 초기 파티션 집합을 설정(사전 분할)할 수 있음

  • 노드 비례 파티셔닝

    • 동적 파티셔닝에서 파티션의 개수는 데이터 셋의 크기에 비례

    • 반면, 고정 파티션에서는 파티션의 크기가 데이터 셋 크기에 비례

    • 두 경우 모두 파티션 개수는 노드의 대수와 독립적임

    • 노드 비례 파티셔닝은 파티션의 개수가 노드의 대수와 비례하게 하는 것

    • 즉, 노드 당 할당되는 파티션의 개수를 고정하는 방식

    • 새 노드가 클러스터에 추가되면 고정된 개수의 파티션을 무작위로 선택해 분할하고, 각 분할된 파티션의 절반은 그대로 두고 다른 절반을 새 노드에 할당하는 방식으로 재균형화 됨

요청 라우팅

• 클라이언트가 요청을 보내려고 할 때 어느 노드로 접속해야하는지 어떻게 알 수 있을까?

• 결국 이를 위해선 재균형화 이후에 파티션 할당 변경 정보에 대해 누군가는 알고 있어야 함을 의미

• 이를 위한 세 가지 방법

  • 클라이언트는 아무 노드에 접근해 요청하고 요청을 올바른 노드에 전달해서 응답을 받아 클라이언트로 응답을 전송

  • 클라이언트의 요청을 라우팅 계층이 받아 알맞은 노드에 전달

  • 클라이언트가 파티셔닝 방법과 할당 정보에 대해 알고 있어, 해당 노드로 바로 요청

  

• 이를 위해 많은 분산 데이터 시스템은 클러스터 메타데이터를 추적하기 위해 주키퍼(Zookeeper)와 같은 코디네이션 서비스를 사용

  • 노드는 주키퍼에 자신을 등록하고, 주키퍼는 할당 정보를 관리

  • 라우팅 계층이나 파티션 인지 클라이언트는 주키퍼에 있는 정보를 구독

  • 파티션 변경이 일어나면 노드에서 이를 주키퍼에 알려 라우팅 정보를 최신으로 유지

• HBase, Kafka는 주키퍼에 의존

• 몽고DB는 설정 서버 구현에 의존하고 몽고스(mongos) 데몬을 라우팅 계층으로 사용

• 카산드라와 리악은 가십 프로토콜을 사용해 클러스터 상태 변화를 모든 노드에 퍼트림. 즉, 아무 노드나 요청을 받을 수 있으며 요청을 받은 노드는 요청을 처리할 노드로 요청을 전달하는 방식

• 병렬 질의 실행이라면?

  • 분석용으로 사용되는 대규모 병렬 처리(MPP, massively parallel processing) 관계형 데이터베이스는 훨씬 더 복잡한 질의를 지원

  • MPP 질의 최적화기는 복잡한 질의를 여러 실행 단계와 파티션으로 분해하고, 이들 중 다수는 데이터베이스 클러스터 내의 서로 다른 노드에서 병렬적으로 실행됨

  • 이러한 경우는 10장에서 살펴볼 예정