Database Sharding

Recommanded Free YOUTUBE Lecture: <% selectedImage[1] %>

yundream
2022-10-26
2022-09-24
2091

## Database Sharding
Database Shard(이하 샤드)는 데이터베이스 혹은 검색엔진에서 사용하는 데이터의 수평 파티션이다. 각 샤드는 데이터 부하를 분산시키기 위해서 별도의 데이터베이스 서버 인스턴스에 보관된다.

간단히 말해서, 데이터를 분산해서 저장하고 읽게하여서 병렬적으로 성능을 높이기 위한 파티션 방식이라고 생각할 수 있다.

* 데이터베이스 샤딩은 데이터를 여러 데이터베이스 인스턴스에 파티션으로 나누는 프로세스다.
* 키를 이용해서 데이터를 분할하는데 사용한다. 키는 데이터의 저장 속성중 하나이다.

예를 들어서 1억명의 사용자가 있다고 가정해보자. 그동안 하나의 데이터베이스 서버에서 관리했는데, 유저가 늘어나면서 느려지고 있다.

이 문제는 크게 두 가지 방식으로 해결 할 수 있을 것이다.
1. 데이터베이스 서버의 용량을 늘린다. 더 많은 CPU, 더 빠른 디스크, 더 많은 메모리를 추가한다. 수직 확장이다.
2. 서버를 여러개 만들고 데이터를 나눠서 저장한다. 수평 확장이다.

샤드는 2번 방식이다. 2번 방식을 사용하여 5개의 데이터베이스 서버로 증설하기로 했다. 그렇다면 UserID를 이용하여 아래와 같은 방식으로 데이터를 분할 할 수 있을 것이다.
  1. User ID 1 ~ 20000000 -> Database Server-1
  1. User ID 20000001 ~ 40000000 -> Database Server-2.
  1. User ID 40000001 ~ 60000000 -> Database Server-3.
  1. User ID 60000001 ~ 80000000 -> Database Server-4.
  1. User ID 80000001 ~ 100000000 -> Database Server-5.
이제 12,000,005 사용자에 대한 읽기/쓰기 작업은 Database Server-2에서만 이루어진다. 이 서버는 사용자가 20,000,000개 밖에 없기 때문에 처리가 빠를 것이다.

## 샤딩 유형
### 범위 기반 샤딩
위의 1억 고객을 샤딩하는 방식이 범위 기반 샤딩이다.

키의 범위를 기반으로 샤딩한다. 1~100은 1, 101 ~ 200은 2 이런 식이다. **구현이 단순**하지만 **데이터가 고르게 샤드에 분산되지 않을 수 있다는 단점**이 있다.

위의 예제를 보자. 고객이 200명이 추가로 늘어서 100,000,200가 됐다고 가정해보자. 그럼 Database Server-6이 추가 될건데, 여기에는 200 건의 고객 정보만 들어가게 될 것이다.

![Range shard](https://docs.google.com/drawings/d/e/2PACX-1vQTRuh57NxxlREKx7cAuosG83HlUEB3puIa8aP-ScunD0VaKuHpk5KSzi8oXDki6LxN5CyZ2JlmRvEC/pub?w=975&h=336)

### 해시기반 샤딩
키의 해시 값을 생성하고, 이 해시 값으로 데이터를 저장할 샤드를 결정한다. 단순 해시 함수를 사용 해서 샤딩할 경우 왜곡된 배포가 발생 할 수 있기 때문에 이를 극복하기 위해서 **Consistent Hashing**를 사용 할 수 있다.

가장 간단한 해시는 **mod 연산** 일 것이다. 예를 들어서 3개의 노드가 있다면 **h(x) = x%3** 이된다.

![hash shard](https://docs.google.com/drawings/d/e/2PACX-1vS6AiYMIbBKsXGfOhlIbxGgdGnQsO6OMt7TS265CXPyH6zxisWwUaYKWVuWFBjQV-uuiCVpLLXzKs_m/pub?w=965&h=338)

### 디렉토리 기반 샤딩 
어떤 샤드에 어떤 데이터가 있는지에 대한 정보를 가진 조회 테이블을 만든다. 조회 테이블을 조작하는 것으로 샤딩을 조절 할 수 있기 때문에 해시/범위 기반 샤딩보다 유연하지만, **조회 테이블이 단일 실패 지점**이라는 단점이 있다.

![Directory base shard](https://docs.google.com/drawings/d/e/2PACX-1vTfQflVirnCY0ANScCAAzXDckvBBBZMPi6HHnDcOEBGXXODY1M8UQzSGf3QcYNaF55lfs6ciEmcgdrL/pub?w=1196&h=352)

## 샤딩의 장점과 단점
### 장점
* 데이터가 여러 데이터베이스 시스템으로 분산되기 때문에, 하나의 샤드에 문제가 생기더라도 다른 샤드는 여전히 작동한다. 따라서 데이터베이스는 부분적으로 작동한다. 
* 각 샤드마다 서로 다른 액세스 제어 메커니즘을 구현할 수 있다. 
* 데이터의 크기가 작아지기 때문에 인덱스 크기도 작아지고, 그 결과 쿼리 처리 속도도 빨라진다.
* 읽기/쓰기가 분산되기 때문에 읽기/쓰기 처리가 전반적으로 증가한다.
* 여러 머신에 부하를 분산하기 때문에 메모리, CPU, 네트워크 대역폭을 관리하기가 쉬워진다.

### 단점
* 서버는 쿼리를 적절한 샤드로 라우팅하는 방법을 알아야 한다. 샤드를 찾는 코드를 추가하면 서버가 더 복잡해질 수 있다.
* 각 샤드의 데이터는 완전히 독립적이기 때문에, 트랜잭션과 롤백 처리가 불가능하거나 (매우)어려워질 수 있다.
* 각 샤드의 데이터가 완전히 독립적이기 때문에 데이터 조인(join)이 힘들어진다. 서로 다른 샤드로 이동해서 데이터를 가져와서 연산해야 하기 때문이다.
* 샤딩을 위해서는 독립적인 서버가 필요하기 때문에 단일 데이터베이스에 비해서 더 많은 컴퓨팅 성능이 필요하다. 적절한 최적화가 없으면 비용이 크게 증가할 수 있다.

#### 계층적 샤딩 
샤드수를 늘리거나 줄이는 것은 매우 어려운 작업이다. 예를들어 mod 함수로 shard를 하는 시스템이 있다고 가정해보자. 현재 시스템이 4개라면 **h(x) = mod%4** 일 것이다. 시스템을 4개로 증설해야 하는 경우 **h(x) = mod%5**가 될건데, 이 경우 모든 데이터를 전부 재조정해야 한다.

보통은 샤드 수를 고정하며, 샤드 중 하나가 너무 커질 수 있다. 이 경우에 큰 샤드를 다시 샤딩하는 **계층적 샤딩**을 수행 하기도 한다.

![계증적 샤딩](https://docs.google.com/drawings/d/e/2PACX-1vT1SU1XD26qw-0WgTmTUNyk1LLVGz-sEZnxXaWFu3rxWWAInae4f4sDuzmyaU0FUHSbX0ekmzWWyl0V/pub?w=1628&h=439)

#### Consistent Hashing
Consistent hashing는 Key의 집합을 K, 슬롯의 크기를 N라고 했을 때, N의 갯수가 바뀌더라도 대부분의 키들이 슬롯을 그대로 사용할 수 있는 해싱 기법을 의미한다. 슬롯이 추가되거나 삭제됐을 때, K/n만큼만 조정된다. 추가된 노드만큼 재 조정되는 것이니, consistent 하다고 할 수 있다. 다른 해쉬들은 슬롯을 변경할 경우 거의 대부부분의 key들을 재 조정 해야 한다.

Consistent hash 알고리즘은 1997년 Karger가 개발했다. 웹 캐시를 구현하기 위해서 개발 했는데, 캐시 노드의 추가와 삭제에 관계없이 높은 수준의 웹 히트율을 보장한다. 분산 캐시, 분산 스토리지, 라우팅, 분산 요청 처리 등 다양한 영역에서 사용하고 있는 성공한 알고리즘이다.

Consistent Hashing에 대한 자세한 내용은 [consistent hashing](https://www.joinc.co.kr/w/man/12/hash/consistent) 문서를 참고하자.

Search For:

BY TAGS

Recent Posts

Archive Posts

Tags

About

Get in Touch

Categories