Databases #3 - Data Partitioning

본 글은 educative.io 의 Grokking Modern System Design Interview 코스의 Databases 챕터 내용을 정리한 글입니다.

 

Why do we partition data?

Data 는 조직에서 주요한 자산이고, 늘어나는 데이터와 동시성 읽기/쓰기 트래픽은 전통적 DB 가 확장성을 가지길 요한다. 전통적인 DB는 range query, secondary index, 트랜잭션 등의 속성때문에 매력적이다.

단일 노드 기반 DB 는 로드를 처리하기에 충분하지 않아서 데이터를 여러 노드로 분산시키면서도 RDB 의 좋은 특징들을 유지할 필요가 있는데, 실제로는 분산 DB 가 단일노드DB 의 특징을 가지게 하는 것은 어려운 일로 판명되었다.

NoSQL 과 같은 시스템으로 데이터를 옮기는 것이 방법이 될 수도 있지만, 과거 코드와 전통적 DB 의 강결합이 이를 어려운 문제로 만들기도 한다.

서드파티 솔루션으로 전통적 DB 를 확장할 수 있지만 보통 서드파티 솔루션을 통합하는것도 나름대로 복잡하다.

데이터 파티셔닝 또는 샤딩은 각 노드가 전체 데이터의 일부를 관리하여 여러개의 노드를 쓸 수 있게 해준다. 다양한 파티셔닝 방법과 관련 과제를 이번 세션에서 다룰 것이다.

Sharding

로드를 여러 노드로 나누기 위해서 파티셔닝 또는 샤딩이라는 방법으로 데이터를 분할해야 한다. 이 방법은 큰 데이터를 작은 데이터 조각으로 나누어 서로 다른 노드에 저장하게 한다.

파티셔닝은 각 파티션이 동일한 양의 데이터를 받을 수 있도록 균형잡혀야 한다. 만약 파티셔닝이 밸런스가 잡혀있지 않다면 대부분의 쿼리가 일부 파티션으로만 전달될 수 있다. 이렇게 과중된 부하를 받는 파티션은 시스템 병목이 될 수 있다. 이러한 파티션을 핫스팟이라고 하며, 파티션의 효율성이 저하될 수 있다. 일반적으로 데이터를 샤딩하는데는 vertical, horizontal 샤딩의 두가지 방식이 있다.

Vertical sharding

버티컬 샤딩은 길이가 매우 긴 문자열이나 binary large object (blob) 등의 컬럼이 있는 테이블에서 데이터 추출 속도를 높이기 위해 사용된다. 이런 경우 해당 컬럼들은 서로 다른 테이블로 나누어 저장된다.

아래 그림에서 Employee 테이블은 Employee, EmployeePicture 테이블로 나누어 저장되는데, 이 구조는 데이터 읽기와 쓰기 및 테이블의 재구성이 효율적으로 동작할 수 있게 한다.

버티컬샤딩은 복잡하며 데이터를 어떻게 분할할지 직접 결정해야 한다. 이에 비해 horizontal sharding 은 여러 조건에서도 자동화하기에 적합하다.

Horizontal sharding

horizontal sharding 은 테이블을 row 기반으로 나누는 방식으로, 각 파티션은 샤드라는 이름으로 DB 서버에 분산 저장된다. 보통 Key-range based sharding, Hash based sharding 두가지 방법이 사용된다

• Key-range based sharding
  • 아래 그림에서 Invoice 테이블은 Customer_Id 를 파티션 키로 해서 샤딩한 것이다.
  • 외래키로 엮인 여러개의 테이블이 있을 수 있는데, 이 경우 horizontal sharding은 관계된 모든 테이블의 동일한 파티션키를 기반으로 수행된다.
  • 장점
    • range-query-based scheme 을 구현하기 쉽다
    • range query 는 파티션키를 기반으로 수행될 수 있으며, 파티션을 정렬된 상태로 유지할 수 있다.
  • 단점
    • 파티션 키 외의 다른 키로 range query 할 수 없다
    • 키가 적합하지 않을 경우 일부 노드에 데이터가 쏠릴 수 있다.

• Hash-based sharding
  • 아래 그림에서 해시 함수는 value mod n 이고, n 은 노드 갯수로, 4이다. value mod n 값을 구해서 나온 숫자가 node 번호가 되어 해당하는 node 에 저장된다.
  • hash-based sharding 은 특정 속성에 대해 hash 류의 함수를 사용하여 나온 값을 기반으로 파티션을 수행한다. 해시 함수를 키에 사용해 해시값을 구한 다음 파티션 수로 mod 연산을 한다. 적당한 해시함수를 찾았다면 각 파티션에 해시 range 를 할당해줄 수 있고, 특정 해시 range 로 해시 값이 떨어지는 키를 가진 데이터는 대응하는 파티션에 저장된다.
  • 장점
    • 키가 균등하게 분산된다
  • 단점
    • 키에 대해 range query 를 할 수 없다.

• Consistent hashing
  • consistent hashing 은 서버의 수와 관계 없이 ring 이라고 하는 원형 공간에 각 서버 또는 분산 해시테이블의 아이템을 할당시킨다. 이 방법은 전체 시스템의 성능을 저하시키지 않고 서버를 확장시킬 수 있다. 
    • 장점
      • 수형 확장이 쉽다
      • 앱의 처리량과 지연을 향상시킨다
    • 단점
      • 링에 랜덤하게 할당된 노드들은 균등하지 않은 분산을 야기할 수 있다.

Rebalance the partitions

쿼리 로드는 여러 이유로 불균등하게 분산될 수 있다

• 데이터 분산이 균등하지 않거나
• 하나의 파티션에 너무 많은 로드가 있거나
• 쿼리 트래픽이 늘어서 노드를 더 추가해야 하거나

이러한 경우에 적용 가능한 파티션 리밸런싱 전략을 살펴보자

• Avoid hash mod n
• 보통 키의 해시값으로 파티션을 하는 상황을 만들지 않는다. 이런 경우 노드 추가 제거시 모든 노드의 파티션 번호가 바뀌고, 많은 데이터들이 이동해야 하기 때문이다. 하나의 노드에서 다른 노드로 데이터를 이동하면 리밸런싱 비용이 많이 든다.
• Fix number of partitions이 방법의 단점은 전체 데이터 양이 늘어날수록 각 파티션의 크기도 증가한다는 것이다. 파티션이 너무 작으면 너무 많은 수의 조그만 파티션들을 관리하는 오버헤드가 너무 많이 발생할 수 있다. 파티션이 너무 크면 리밸런싱이나 노드 복구 작업에 드는 비용이 많이 소모될 수 있다. 따라서 적당한 파티션수를 고르는 것이 중요하다. 이 방식은 Elasticsearch, Riak 등 많은 곳에서 사용된다.
• 이 방법에선 파티션 수가 DB 를 처음 셋업할때부터 정해져있다. 노드보다 많은 수의 파티션을 만들어서 파티션들을 노드에 할당하여 새로운 노드가 추가되면 몇개의 파티션만을 기존 노드에서 새 노드로 옮겨오면 된다.
• Dynamic partitioning하지만 이 방식은 실시간으로 읽기 쓰기 작업을 처리하면서 동적으로 리밸런싱 작업까지 수행하기는 어렵다. 이 방식은 HBase 와 MongoDB 에서 사용된다.
• 이 방식에서는 파티션 크기가 임계치에 다다르면 동일한 크기의 두 파티션으로 분할한다. 분리된 두 파티션은 서로 다른 노드에 할당되며, 이에 따라 로드도 동일하게 분산된다. 파티션수는 전체 데이터양에 비례하며, 이 방식의 장점이다.
• Partition proportionally to nodes
• 이 방식에서는 파티션수가 노드 수에 비례하고, 각 노드는 고정된 파티션을 갖는다. 노드 수는 일정하게 유지되지만 각 파티션의 크기는 데이터 크기가 커질수록 증가한다. 그러나 노드 수가 증가하면 파티션 크기가 축소된다. 새 노드가 추가되면 특정 수 의 파티션을 랜덤으로 분할하여 분할된 파티션의 반은 남기고, 반은 가져간다. 이 방식은 불균등한 분할을 야기할 수 있다. 이 방식은 Cassandra 와 Ketama 에서 사용된다.

Partitioning and secondary indexes

secondary index 를 통해 레코드에 접근하고 싶은 경우는 어떻게 해야 할까? 다음과 같은 방법들로 secondary index 를 이용한 파티션을 할 수 있다.

• partition secondary indexes by document
  • 이 방식은 비용이 많이 들기 때문에 성능이 낮은 파티션의 지연에 제한을 받게되고, 따라서 읽기 쿼리 지연이 증가할 수 있다.
  • 이 방식에서는 각 파티션이 완전히 독립적이다. 각 파티션은 documents 들에 대한 secondary index 를 가지고 있으며 다른 파티션에 저장된 데이터와는 상관없다. DB 에 데이터를 쓸때는 해당 document Id 가 포함된 파티션만 처리하면 되고, 이는 로컬 인덱스라고도 한다. 아래 그림에서 customer id 로 쿼리해서 데이터를 읽어오려면 모든 파티션에 요청을 보내야 한다.

• partition secondary indexes by the term
  • 아래 그림에서 cust_name 에 대한 인덱스를 만들고 모든 인덱스를 분리된 노드에 저장한다. cust_name 으로 쿼리하려면 term index 가 어디있는지 알아야 한다. index 0 은 이름이 A-M 으로 시작하는 데이터들의 인덱스 정보를, index 1 은 이름이 N-Z 로 시작하는 데이터들의 인덱스 정보를 담고있다.
  • 이 방식은 document 기반 방식보다는 읽기에 효율적이다. 해당하는 term 을 가진 파티션만을 접근하면 되기 때문이다. 하지만 단일 쓰기가 여러 파티션에 영향을 주는것이 단점이다.
  • 각 파티션에 보조 인덱스를 저장하는 대신 (local index), 모든 파티션의 데이터를 포함하는 secondary term 의 global index 를 만들 수 있다.

Request routing

클라이언트는 요청시에 어떤 노드에 붙어야 할지 어떻게 알 수 있을까? 파티션이 어떤 노드에 할당되었는지는 리밸런싱 이후에 달라질 수 있다. 만약 특정 키를 읽으려고 한다면 연결해야할 IP 주소를 어떻게 알 수 있을까?

이 문제는 service discovery 라고도 알려져 있으며 아래와 같은 접근법이 있다.

• 클라이언트가 어떤 노드에게도 요청을 보낼 수 있도록 한다. 요청을 받은 노드가 데이터가 없으면 데이터를 들고있는 노드에게 요청을 전달한다.
• 라우팅 계층을 포함하는 방법이 있다. 모든 요청은 라우팅 계층으로 먼저 전달되며, 여기서 요청을 처리할 노드를 결정해준다.
• 클라이언트가 이미 파티션 관련 정보를 가지고 있어서 어느 파티션에 연결해야할지 알수 있도록 한다.

이 방법들어서 주요 도전과제는 노드의 파티션 정보가 업데이트 될 때 연관 컴포넌트에 이를 전달하는 방법을 정하는 것이다.

zookeeper

클러스터의 변화를 추적하기 위해 많은 분산 시스템은 zookeeper 와 같은 별도의 관리 서버가 필요하다. 주키퍼는 네트워크의 모든 매핑을 추적하고, 각 노드는 이 정보를 위해 주키퍼에 연결된다. 파티셔닝에 변화가 있거나 노드가 추가 제거되면 주키퍼는 업데이트되고 이 변화를 라우팅 계층에 알린다. HBase, Kafka, SolrCloud 등이 주키퍼를 사용한다.