[대규모 시스템 설계 기초 정리 + Cassandra] 안정 해시 설계 + Cassandra Virtual Node

카산드라 DB를 요즘 공부하고 있는데, 해당 개념에 이번 장의 개념이 들어가 있어서 공부해보며 정리해봅니다.

Cassandra DB

---

Cassandra DB는 대용량의 데이터 시스템을 관리하기 위해 개발되었으며, 대용량 저장 장치 및 가용성을 요구한다.

• Cassandra DB는 가용성을 확보하기 위해 여러 노드를 다음 그림처럼 논리적으로 링 구조로 구성하였다.

• 여러 개의 노드로 클러스터를 구성하여, 동일 데이터를 여러 노드에 복제하여 저장함으로써, 특정 노드에 장애가 발생하더라도 복제된 노드에서 데이터를 제공해서 가용성을 충족한다. (여기서 노드는 Master-Slave 개념이 아닌 모두 동등 위치를 갖는다)

 

Cassandra DB에서 데이터를 저장할 때, 여러 노드 중 어떤 노드에 저장할지 결정해야 하는데, 이곳에 Virutal Node 개념이 등장한다.

그럼 과연 Virtual Node는 무엇이고 안정 해시 개념은 무엇일까?

안정 해시 설계

---

수평적 규모 확장성

• 수평적 규모 확장성을 달성하기 위해서는 요청 또는 데이터를 여러 서버에 균등하게 나누는 것이 중요하다.
• 안정 해시는 수평적 규모 확장성의 목표를 달성하기 위해 보편적으로 사용하는 기술.

해시 키 재배치 문제

N개의 서버가 있을 때, 데이터 혹은 트래픽을 균등하게 나누는 방법은 해시 함수를 이용하는 것이다.

• 서버 index = hash % 서버의 개수
• 이 방법은 서버 풀의 크기가 고정되어 있을 때, 데이터 분포가 균등할 때는 잘 동작한다.
• 하지만 서버가 추가되거나 기존 서버가 삭제되면 문제가 생긴다.
  • ex) 1번 서버에 장애가 발생하면 1번 서버에 보관되어 있는 키뿐만 아니라 대부분의 키가 재분배되는 문제가 존재.
  • 그 결과로 대규모 캐시 미스가 발생하게 된다.

안정 해시

---

 

• 안정 해시는 해시 테이블의 크기가 조정될 때 평균적으로 오직 키의 개수/슬롯의 개수 개의 키만 재배치하는 해시 기술이다.

해시 공간을 양쪽으로 구부려 접으면 다음과 같은 해시 링이 만들어진다. (논리적인 개념)

• (해시 공간이 1 ~ 100 이 있을때, 1에서 100까지 증가하다가 100까지 모두 가면 다시 1로 돌아오는 개념이라고 보면 될 거 같다.)

• 캐시 할 키 또한 해시 링 위의 어느 지점에 배치할 수 있다.

서버 조회

• 특정 키가 주어졌을 때, 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫 번째 서버에 해당 데이터가 존재한다고 할 수 있다.
• 예시를 들면 1 ~ 100의 해시 공간이 있다고 할 때, 서버 1: 30, 서버 2: 50, 서버 3: 70에 배치되어 있다고 하자. (순차적으로 증가한다고 가정) 키가 10인 경우에는 서버 1(30)에 먼저 만나므로, 해당 키에 해당하는 데이터는 서버 1에 존재한다는 의미.

서버 추가

• 안정 해시의 경우에는 서버를 추가하더라도 키 가운데 일부만 재배치하면 된다.
• 위의 그림에서 서버 D가 추가되어도, 서버 C-D 사이에 존재하는 키만 서버 A → 서버 D로 재배치하면 된다.

 

서버 제거

• 서버가 삭제되어도 키 가운데 일부만 재배치된다.
• (서버 D가 삭제되어도 서버C-서버D 사이의 키만 서버 D → A로 재배치된다)

 

안정 해시 기본 구현법 정리

• 서버와 키를 균등 분포 해시 함수를 사용해 해시 링에 배치.
• 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버.

 

기본 구현법의 한계

• 서버가 추가되거나 삭제되는 상황을 고려하면 파티션의 크기를 균등하게 유지하는 게 불가능. (어떤 서버는 굉장히 작은 해시 공간을 할당받고, 어떤 서버는 굉장히 큰 해시 공간을 할당받는 상황이 가능)
• 키의 균등 분포를 달성하기 어려움

 

가상 노드

기본 구현법의 문제를 해결하기 위해 제안된 기법

하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다. (위의 기본 구현에는 링 위에 서버는 1개의 노드만 가지고 있었는데, 가상 노드의 경우에는 서버 1개는 N개의 노드를 가질 수 있다)

• 가상 노드의 개수를 늘릴수록 키의 분포는 점점 더 균등해진다.
  • 반면 가상 노드 데이터를 저장할 공간은 더 많이 필요해지기 때문에, 적절한 트레이드오프 결정이 필요하다.

 

Cassandra DB에서의 Virtual Node

https://docs.datastax.com/en/cassandra-oss/2.2/cassandra/architecture/archDataDistributeDistribute.html

 

참고

• 가상 면접 사례로 배우는 대규모 시스템 설계 기초: http://www.yes24.com/Product/Goods/102819435
• Cassandra Documentation: https://docs.datastax.com/en/cassandra-oss/2.2/cassandra/architecture/archDataDistributeVnodesUsing.html