❐ 0. Description
샤딩 (sharding)
- 데이터 셋이 매우 크거나 질의 처리량이 매우 높다면 복제만으로는 부족함.
- 이런 경우, 데이터를 파티션(partitions)들로 쪼개야 함.
- 이를 샤딩이라고 함.
데이터 파티셔닝을 원하는 이유
❐ 1. 파티셔닝과 복제
파티셔닝과 복제
- 보통 파티셔닝은 복제와 함께 존재함(combined).
- 각 파티션의 복사본이 여러 노드에 저장됨
- 한 노드에 여러 파티션을 저장할 수도 있음.
- 리더 팔로워 복제 모델을 사용한 "파티션닝 + 복제"
- 각 파티션의 리더는 하나의 노드에 할당되고 팔로워들은 다른 노드에 할당
❐ 2. Key-Value 데이터 파티셔닝
- 파티셔닝의 목적
- 데이터와 질의 부하를 노드 사이에 고르게 분산 시키는 것
- Skewed(쏠림)
- 파티셔닝이 고르게 이뤄지지 않아 다른 파티션 보다 데이터가 많거나 질의를 많이 받는 파티션이 있는 경우
- 이런 경우 파티셔닝의 효과가 매우 떨어짐
- 이때 불균형하게 부하가 높은 파티션을 "핫스팟"이라 함.
🌀 2-1. 키 범위 기준 파티셔닝
- 각 파티션에 연속된 범위(min ~ max)의 키를 할당하는 것
- 각 범위들 사이의 경계를 알면 어떤 키가 어느 파티션에 속하는지 쉽게 찾을 수 있음.
- 어떤 파티션이 어느 노드에 할당됐는지 알면 적절한 노드로 요청을 직접 보낼수도 있음.
- 데이터가 고르게 분포하지 않을 수도 있기 때문에 키 범위가 반드시 동일할 필요 없음.
- 각 파티션 내에서는 키를 정렬된 순서로 저장할 수 있음.
- 이렇게 하면 범위 스캔이 쉬워짐
- 키를 연쇄된 색으로 간주해서 질의 하나로 관련 레코드를 여러 개 읽어오는데 사용할 수 있음.
- 특정한 접근 패턴이 핫스팟을 유발하는 단점을 가지고 있음.
- 예를 들면, 1일치의 데이터를 파티션 하나가 담당하는 경우
- 이 단점을 피하려면 타임스탬프가 아닌 다른 것을 키의 첫 번째 요소로 사용해야 함.
🌀 2-2. 키의 해시 값 기준 파티셔닝
- 쏠림과 핫스팟의 위험 때문에 많은 분산 데이터스토어는 키의 파티션을 정하는데 해시 함수를 사용
- 좋은 해시 함수는 쏠린 데이터를 균일하게 분산
- 파티셔닝용 해시 함수는 암호적으로 강력할 필요는 없음.
- 범위 질의를 효율적으로 할 수 없음.
- 키들이 모든 파티션에 흩어져있어, 정렬 순서가 깨지기 때문
- 카산드라DB의 경우
- 테이블을 선언할 때 여러 컬럼을 포함하는 "복합 기본키(compound primary key)"를 지정할 수 있음.
일관성 해싱(consistent hashing)
- CDN(content delivery network) 같은 인터넷 규모의 캐시 시스템에서 부하를 균등하게 분시키는 방법
- 파티션 경계를 동일 or 무작위로 선택
- 데이터베이스에서 잘 동작하지 않아서, 거의 사용되지 않음.
🌀 2-3. 쏠린 작업부하와 핫스팟 완화(Skewed Workloads and Relieving Hot Spots)
- 키를 해싱해서 파티션을 정하면 핫스팟을 줄이는데 도움은 되지만, 100%는 아님
- 항상 동일한 키를 읽고 쓰는 극단적인 상황에서는 모든 요청이 동일한 파티션으로 쏠리게 됨.
- 현대 데이터 시스템은 대부분 크게 쏠린 작업부하를 자동으로 보정하지 못함
- 따라서 애플리케이션에서 쏠림을 완화해야 함.
- 예를 들어,
- 요청이 매우 많이 쏠리는 키를 발견한 경우
- 각 키의 시작이나 끝에 임의의 숫자를 붙이는 방법
- user123-00 ~ user123-99
- 근데 이렇게 키를 100개로 쪼개면 읽을 때 문제가 있음.
- 원래는 user123만 읽으면 되는데, 이제는 `user123-00 ~ user123-99`를 모두 읽어서 합쳐야 함
- 이 기법은 추가적인 관리(bookkeeping)도 필요
- 난수를 덧붙이는 건 소수의 핫 키들에만 의미가 있음.
- 대부분의 쓰기 빈도가 낮은 키들에는 불필요한 오버헤드가 됨
❐ 3. 파티셔닝과 보조 색인 (Partitioning and Secondary Indexes)
🌀3-1. 문서(Document) 기준 보조 색인 파티셔닝
- 각 항목에는 document ID 라고 부르는 고유ID가 있음.
- 그리고 데이터베이스를 문서ID 기준으로 파티셔닝함
- 사용자의 차를 검색할 때 색상(color) & 제조사(make)로 필터링
- 위와 같은 색인 방법을 사용하면 각 파티션이 완전히 독립적으로 동작함
- 각 파티션은 자신의 보조 색인을 유지하며 그 파티션에 속하는 문서만 담당
- 지역(local) 색인 이라고도 함
- 문서 기준으로 파티셔닝된 색인을 사용해서 읽을 때
- 어떤 데이터를 읽을 떄 동일한 파티션에 저장되리라는 보장이 없음.
- 따라서, 원하는 데이터를 찾고 싶다면 모든 파티션으로 질의를 보내서 얻은 결과를 모두 combine
- 이런 방법을 스캐터/개터(scatter/gather)라고 함
- 보조 색인을 써서 읽는 질의는 큰 비용이 들 수 있음.
🌀3-2. 용어(Term) 기준 보조 색인 파티셔닝
- 모든 파티션의 데이터를 담당하는 전역(global) 색인을 만들 수 있음.
- 문서 안에서 등장하는 **용어(term)**를 기준으로 색인을 분산.
- 예: color:red라는 색인 항목은 특정 파티션에, color:silver는 다른 파티션에 저장.
- 따라서 "빨간색 차"를 찾는 요청은 color:red 항목이 저장된 파티션으로 바로 라우팅 가능.
- 이런 방식을 용어 기반 색인 파티셔닝(term-partitioned index)이라고 함.
- 특정 용어와 관련된 색인이 한 파티션에 모이므로, 읽기 효율이 매우 좋음.
- 클라이언트가 전체 색인을 스캔하지 않고 필요한 파티션에만 요청을 보낼 수 있음
- 단점
- 쓰기 시 오버헤드
- 하나의 문서가 여러 용어를 포함하므로, 문서가 저장될 때 여러 파티션 색인을 동시에 갱신해야 함
- 분산 트랜잭션 필요.
- 일관성 문제: 쓰기 직후 색인이 최신 상태가 아닐 수 있음 (갱신 지연).
❐ 4. 파티션 재균형화 (Rebalancing Partitions)
재균형화란?
- 클러스터에서 한 노드가 담당하던 부하를 다른 노드로 옮기는 과정
재균형화를 통해 기대하고자 하는 바
- 재균형화 후, 부하가 클러스터 내에 있는 노드를 사이에 균등하게 분배돼야 함
- 재균형화 도중에도 데이터베이스는 읽기 쓰기 요청을 받아들여야 함.
- 재균형화가 빨리 실행되고 네트워크와 디스크 I/O 부하를 최소화할 수 있도록
노드들 사이에 데이터가 필요 있상으로 옮겨져서는 안됨
🌀4-1. 재균형화 전략
쓰면 안되는 방법 : 해시 값에 모든 N 연산을 실행
: How not to do it: hash mod N
- mod(%) 연산을 사용하면 안되는 이유는?
- 노드 개수 N이 바뀌면 대부분의 키가 노드 사이에 옮겨져야 하기 때문
- 키가 자주 이동하면 재균형화 비용이 지나치게 커짐
파티션 개수 고정
- 위 방법의 해결책
- 파티션을 노드 대수보다 많이 만들고 각 노드에 여러 파티션을 할당하는 것.
- 클러스터에 노드가 추가되면 파티션이 균일하게 분배될 때까지 기존 노드에서 파티션을 몇개 뺏어올 수 있음.
- 여기서는 개수, 할당된 키가 변경되지 않은 상채로, 파티션이 노드 사이를 이동함
- 오직 변하는건 노드에 어떤 파티션이 할당되는가 뿐
- 근데 네트워크를 통해 대량의 데이터를 옮겨야 해서 시간 쫌 걸림
동적 파티셔닝
- 키 범위 파티셔닝을 사용하는 데이터베이스에서는 파티션 경계와 개수가 고정돼있는게 불편
- 파티션 경계를 잘못 지정하면 모든 데이터가 한 파티션에 저장되는 문제도 있음.
- 이런 이유로 HBase나 리싱크DB처럼 키 범위 파티셔닝을 사용하는 데이터베이스에서는
- 동적 파티셔닝은 파티션 개수가 전체 데이터 용량에 맞춰 조정이 됨.
- 데이터 양이 적으면 파티션 개수가 적어도 되믈모 오버헤드 작음.
- 빈 데이터베이스의 경우
- 파티션 경계를 어디로 정해야하는지에 관한 사전 정보가 없음.
- 그래서 시작할 때는 파티션이 한 개임.
노드 비례 파티셔닝
- 노드당 할당되는 파티션 개수를 고정
- 새 노드가 클러스터에 추가되면 고정된 개수의 파티션을 무작위로 선택해 분할
- 각 분할된 파티션의 절반은 그대로 두고 다른 절반은 새 노드에 할당
- 파티션 경계를 무작위로 선택하려면 해시 기반 파티셔닝을 사용해야 함.
🌀 4-2. 운영: 자동 재균형화와 수동 재균형화
재균형화는 자동? 수동?
- 완전 자동 재균형화
- 관리자의 개입이 전형 없음. 시스템이 자동으로 결정
- 손이 덜 가서 편한데 예측하기 어려움
- 재균형화는 비싼 작업이기 때문에, 주의 깊게 처리하지 않으면 네트워크나 노드에 과부하가 걸릴 수 있음.
- 완전 수동 재균형화
❐ 5. 요청 라우팅
🌀 5-1. 요청 라우팅
서비스 찾기 (Service discovery)
- 무작위로 노드 선택. 요청을 처리할 수 있을 때 까지 올바른 노드로 요청을 전달
- 라우팅 계층으로 클라의 모든 요청을 보내기(라우팅 계층은 partition-aware 로드 밸런서의 역할)
- 클라가 모든 걸 알고 있음.(파티셔닝 방법, 처리할 수 있는 올바른 노드의 정보)
라우팅 결정을 내리는 구성요소가 노드에 할당된 파티션의 변경사항을 어떻게 알까?
- 이 문제는 어려운 문제임
- 노드 간에 “어디에 어떤 데이터가 있는지”에 대한 합의가 깨지면 요청이 잘못 라우팅됨
- 이를 막기 위해 합의(consensus) 프로토콜이 필요하지만 구현이 매우 어려움
코디네이션 서비스 : 주키퍼(ZooKeeper)
- 분산 데이터 시스템 환경에서 클러스터 메타데이터를 추적하기 위해 주키퍼 사용
- 각 노드는 주키퍼에 자신을 등록
- 주키퍼는 파티션과 노드 사이의 신뢰성 있는 할당 정보를 관리
🌀 5-2. 병렬 질의 실행
대규모 병렬 처리(Massively parallel processing, MPP)
- MPP 관계형 데이터베이스 제품은 훨씨 더 복잡한 종류의 질의를 지원함.
- MPP query optimizer는
- 복잡한 질의를 여러 실행 단계와 파티션으로 분해함.
- 이들 중 다수는 데이터베이스 클러스터내의 서로 다른 노드에서 병렬적으로 실행될 수 있음.
- 데이터셋의 많은 부분을 스캔하는 연산을 포함하는 질의는 더 혜택을 볼 수 있음.
