데이터 중심의 애플리케이션 설계 - 키-값 데이터 파티셔닝

대량의 데이터가 있고 이를 분할해서 저장해야한다면, 어떤 레코드를 어떤 노드에 저장할지 어떻게 결정할까?

파티셔닝의 목표

파티셔닝은 데이터와 쿼리 부하를 노드 간에 고르게 분산시키는 것이다. 파티셔닝은 이론적으로 10개의 노드는 단일 노드보다 10배의 데이터와 10배의 읽기 및 쓰기 처리량을 처리할 수 있어야 한다.

왜곡된 파티션과 핫스팟

일부 파티션에 다른 파티션보다 더 많은 데이터 또는 쿼리가 있는 경우를 왜곡된 파티션이라고 한다. 왜곡이 있으면 파티셔닝의 효율성이 떨어진다. 극단적인 경우에는 모든 부하가 하나의 파티션에 집중되어 10개 노드 중 9개 노드가 유휴 상태이고 병목 현상은 하나의 사용 중인 노드에 집중될 수 있다. 이렇게 불균형적으로 부하가 높은 파티션을 핫스팟이라고 한다.

핫스팟을 피하는 방법

레코드 무작위 할당

핫스팟을 피하는 가장 간단한 방법은 노드에 레코드를 무작위로 할당하는 것이다. 이렇게 하면 데이터를 노드에 고르게 분산시킬 수 있지만, 특정 항목을 읽으려고 할 때 어느 노드에 있는지 알 수 없기 때문에 모든 노드를 병렬로 쿼리해야 한다는 큰 단점이 있다.

알파벳 순으로 분산하여 할당

더 나은 방법으로는, 키를 알파벳순으로 분산하여 저장한다. 예를 들어, 우리는 백과사전을 가지고 제목으로 항목을 찾는다. 모든 항목이 제목에 따라 알파벳순으로 정렬되어 있기 때문에 원하는 항목을 빠르게 찾을 수 있다.

파티셔닝 구현

키 범위별 파티셔닝

파티셔닝의 한 가지 방법은 백과사전의 볼륨처럼 각 파티션에 연속적인 범위의 키를 할당하는 것이다. 어떤 파티션이 어떤 노드에 할당되었는지 알고 있다면 해당 노드에 직접 요청할 수 있다.

데이터가 균등하게 분포되지 않을 수 있으므로 키의 범위가 반드시 균등한 간격일 필요는 없다.

예를 들어,

• 볼륨 1에는 A와 B로 시작하는 단어가 포함되어 있지만,
• 볼륨 12에는 T, U, V, X, Y, Z로 시작하는 단어가 포함되어 있다.

단순히 알파벳 두 글자당 하나의 볼륨이 있으면 일부 볼륨이 다른 볼륨보다 훨씬 커질 수 있다. 데이터를 균등하게 분배하려면 파티션 경계가 데이터에 맞게 조정되어야 한다.

파티션 경계는 관리자가 수동으로 선택하거나 데이터베이스에서 자동으로 선택할 수 있다. 이 파티셔닝 전략은 Bigtable, 오픈 소스에 해당하는 HBase, RethinkDB 및 버전 2.4 이전의 MongoDB에서 사용된다.

각 키범위 파티션 내에서 키를 정렬된 순서대로 유지할 수 있다. 이렇게 하면 범위 스캔이 쉽고 키를 연결된 인덱스로 처리하여 하나의 쿼리에서 여러 관련 레코드를 가져올 수 있다는 장점이 있다. 예를 들어, 센서 네트워크의 데이터를 저장하는 애플리케이션에서 키가 측정의 타임스탬프(연-월-일-시-분-초)인 경우를 가정하자. 이 경우 범위 스캔은 특정 월의 모든 판독값을 쉽게 가져올 수 있기 때문에 매우 유용하다.

키범위 파티셔닝의 단점

키 범위 파티셔닝의 단점은 특정 액세스 패턴으로 인해 핫스팟이 발생할 수 있다는 것이다. 키가 타임스탬프인 경우, 파티션은 시간 범위(하루에 하나의 파티션)에 해당한다.

측정이 이루어질 때마다 센서에서 데이터베이스에 데이터를 쓰면, 모든 쓰기가 동일한 파티션(오늘에 대한 파티션)으로 이동하게 된다. 따라서, 파티션이 쓰기로 과부하가 걸리는 반면 다른 파티션은 유휴 상태가 되는 문제가 있다.

키 범의 파티셔닝 특정 파티션 과부하 해결책

센서 데이터베이스에서 특정 파티션 과부하 문제를 방지하려면 키의 첫 번째 요소로 타임스탬프가 아닌 다른 것을 사용해야 한다.

예를 들어,

1. 각 타임스탬프 앞에 센서 이름을 붙여서 센서 이름별로 먼저 분할한다.
2. 그 다음은 센서 데이터를 시간별로 분할하도록 한다.

동시에 많은 센서가 활성화되어 있다고 가정하면 쓰기 부하가 파티션 전체에 더 고르게 분산된다.

만약, 시간 범위 내에서 여러 센서의 값을 가져오려면 각 센서 이름에 대해 분할 속도 범위 쿼리를 수행해야 한다.

키 해시를 기준으로 파티셔닝

왜곡 및 핫스팟의 위험 때문에 많은 분산형 데이터스토어는 해시 함수를 사용해 특정 키에 대한 파티션을 결정한다.

좋은 해시 함수는 왜곡된 데이터를 가져와 균일하게 분산한다.

예를 들어, 문자열을 받는 32비트 해시 함수가 있다고 가정하자.
이 함수는 새로운 문자열을 입력할 때마다 0과 23^2 - 1 사이의 임의의 숫자를 반환한다. 입력 문자열이 매우 유사하더라도 해시는 해당 숫자 범위에 걸쳐 균등하게 분포된다.

분할을 위해 해시 함수는 암호학적으로 강력할 필요는 없다. 예를 들어 Cassandra와 MongoDB는 MD5를 사용하고 Voldemort는 파울러-놀-보(Fowler-Noll-Vo) 함수를 사용한다.

한편, 많은 프로그래밍 언어에는 해시 테이블에 사용되는 간단한 해시 함수가 내장되어 있지만 파티셔닝에 적합하지 않을 수 있다. 예를 들어 Java의 Object.hashCode()와 Ruby의 Object#hash에서는 동일한 키가 다른 프로세스에서 다른 해시 값을 가질 수 있다.

해시 키 분배 기술은 파티션 간에 키를 공정하게 분배하는 데에 효과적이다. 파티션 경계는 균등한 간격을 두거나 무작위로 설정할 수 있다. 이 기법을 일관된 해싱이라고 한다.

해시 키 분배의 일관된 해싱

일관된 해싱은 Karger 가 정의한 대로 콘텐츠 전송 네트워크(CDN)와 같은 인터넷 전반의 캐시 시스템에서 부하를 균등하게 분산하는 기술에서 우래되었다. 중앙 제어나 분산 합의의 필요성을 피하기 위해 무작위로 선택된 파티션 경계를 사용한다.

해시 파티셔닝의 정렬 순서 손실 문제

키의 해시를 분할에 사용하면 키 범위 분할의 좋은 특성인 효율적인 범위 쿼리를 수행할 수 있는 기능을 잃게 된다. 한때 인접했던 키가 이제 모든 파티션에 흩어져 있으므로 정렬 순서가 손실된다.

Cassandra는 두 가지 파티셔닝 전략 사이에서 절충점을 찾았다. Cassandra의 테이블은 여러 열로 구성된 복합 기본 키로 선언할 수 있다. 해당 키의 첫 번째 부분만 해시되어 파티션을 결정하지만, 다른 열은 카산드라의 SSTables에서 데이터를 정렬하기 위한 연결 인덱스로 사용된다.

이러한 방식을 사용하면, 파티션 내에서 복합 키의 첫 번째 열에 고정 값을 지정하여 키의 다른 열에 대해 효율적인 범위 스캔을 수행할 수 있다.

예를 들어, 소셜 미디어 사이트에서 한 사용자가 여러 개의 업데이트를 게시할 수 있다. 업데이트에 대한 기본 키를 (user_id, update_timestamp)로 선택하면 특정 사용자가 일정 시간 간격 내에 작성한 모든 업데이트를 타임스탬프별로 정렬하여 효율적으로 검색할 수 있다. 사용자마다 다른 파티션에 저장될 수 있지만, 각 사용자 내에서 업데이트는 단일 파티션에 타임스탬프별로 정렬되어 저장된다.

해시 키 파티셔닝의 왜곡된 워크로드

키를 해시화하여 파티션을 결정하면 핫스팟을 줄일 수 있다. 그러나 모든 읽기 및 쓰기 요청이 동일한 파티션으로 라우팅될 수 있는 경우는 드물지만 존재한다.

예를 들어, 소셜 미디어 사이트에서 수백만 명의 팔로워를 보유한 유명 사용자가 어떤 활동을 하면, 동일한 키에 대량의 글이 쓰여질 수 있다. 두 개의 동일한 ID의 해시는 여전히 동일하기 때문에 키를 해시하는 것은 도움이 되지 않는다.

오늘날 대부분의 데이터 시스템은 이러한 고도로 왜곡된 워크로드를 자동으로 보정할 수 없다. 이러한 왜곡된 워크로드를 줄이는 것은 애플리케이션이 해야한다.

해시 키 파티셔닝의 핫스팟 해결책

하나의 키에 요청이 쏠릴경우, 키의 시작 또는 끝에 난수를 추가하는 간단한 기법을 사용할 수 있다. 두 자리 소수점 난수를 추가하면 해당 키에 대한 쓰기를 100개의 다른 키로 균등하게 분할하여 해당 키를 다른 파티션에 분산할 수 있다.

하지만 쓰기를 여러 키로 분할하면 읽기는 이제 100개 키 모두에서 데이터를 읽고 결합해야 하므로 추가 작업을 수행해야 하는 문제가 발생한다. 이 기술은 또한 추가적인 작업이 필요하다. 소수의 핫키에 대해서만 난수를 추가하는 것이 합리적이며, 쓰기 처리량이 적은 대다수의 키에서는 불필요한 오버헤드가 발생한다. 따라서 어떤 키가 분할되는지 추적할 수 있는 방법도 필요하다.