이번 장에서는 수평적 분산 노드 설계를 가능하게 하도록 해시 함수를 통해 데이터를 서버에 분배하는 법을 설명해준다. 안정해시로 구성하는 DB가 Apache Cassandra, Amazon Dynamo DB 등 다양했다. 사실 그 두개의 DB를 잘 모르고 있었는데, 내부 설계를 살펴보고 이런 DB도 있구나 알게된 거 같아 좋은 기회라 생각됐다. 그럼 안정 해시 설계가 왜 나오게 된 건지, 그리고 해당 설계를 사용하고 있는 Apache Cassandra 클러스터에 데이터가 분산되는 방식을 살펴보자.
rehash(해시 재분배) 문제
우선 가장 기초적인 해시 함수이며 많은 사람들이 배웠을 Mod를 활용한 해시 함수가 예제로 나온다.
server index = hash key % 서버 개수
이 해시 함수는 서버가 다운되기 전까지는 데이터가 균등하게 분배될 수 있다. 그림 5-1을 살펴보면 균등하게 분배된 것이 보인다. 그러나 장애가 발생하면 5 - 2처럼 모든 데이터를 해시 함수를 통해 재배치해야 하며, 균등하게 데이터가 분배되지 않는 것을 볼 수 있다. 또한, 모든 데이터에 대해 복제 데이터가 없어 대규모 캐시 미스가 발생할 수 있다.
안정 해시
이를 보완하기 위해 안정 해시 설계가 나온다. 우선 안정 해시의 특징으로는 서버가 삭제되거나 추가되더라도 기존 mod를 활용한 해시 함수와 달리 전체 키를 재배치하는 게 아니라, n이 슬롯 개수, k가 해시 키라고 가정하면, k/n 개만 재배치가 이루어져 효율적인 알고리즘이다.
안정 해시는 다음과 같이 해시 링이 나온다. 서버를 균등하게 분배시킨 후, 시계 방향으로 해시 링을 순회하면서 만나는 서버에 데이터가 분배되는 형태이다. 그림 5-8처럼 서버가 한 대 추가되었을 때 모든 키가 재배치되는 게 아니라 s3~s4에 해당하는 해시 키만이 서버 재배치가 일어난다.
그리고 서버 삭제의 경우에도 s0~s2 사이의 해시 키만 영향을 받는다.
그런데 안정 해시에는 서버가 추가되거나 삭제되는 상황을 감안하면 데이터가 균등하게 분배되지 않는다는 문제가 여전하다. 어떤 서버에는 매우 많은 데이터가 몰리는데, 다른 서버에는 비교적 적은 데이터가 몰릴 수 있다. 따라서 제안된 기법은 가상노드 혹은 복제라는 개념이다.
가상 노드 or 복제
서버는 여러 개의 파티션으로 나뉘어 가상노드를 가질 수 있다. 그리고 파티션을 나누면 나눌수록 더욱 균등하게 분포할 수 있다. 그러나 파티션을 나누게 되면 그만큼의 많은 파티션을 나누는 데 필요한 공간이나, 시간이 필요하게 되어 트레이드 오프가 존재한다. 따라서 요구사항에 맞도록 적절히 조정하는 것이 중요하다.
Apache Cassandra 가상 노드
아파치 카산드라는 MongoDB, Redis와 같은 No SQL 형태의 DB이다. 그리고 클러스터링 구조로 이뤄져있는데, 기본적인 클러스터링 구조와는 다르다. master-slave 구조가 아닌 위에서 설명된 안정 해시 구조이다. 일단 master가 없으므로 모든 서버가 read/write를 수행하며, 데이터를 복제한다.
위 그림에서 보는 것처럼 A 시계방향으로 바로 보이는 선이 node 1, 그다음이 node 2.. 데이터가 이런 식으로 분배된다. 그리고 master slave 구조가 없으므로 시계방향으로 E에서 A까지의 데이터를 node 1이, 그다음 F에서 B까지를 node 2가 배치되어있다. 그리고 그 아래는 파티션으로(가상노드로) 나뉘어있는 걸 볼 수 있다.
다른 클러스터링과 차이는 서버를 균등하게 분배하는 방식이 해시 함수를 사용하다 보니 그러한 소요시간이나, 파티션을 구성하는 추가 데이터가 필요한 트레이드 오프가 있을 거 같다. 그리고 어찌보면 각 노드가 모두 마스터로 되는 것과 같을 수 있어 데이터 정합성이 일치할 수 있게끔 알고리즘 설정이 필요할 거 같다.
'시스템 설계' 카테고리의 다른 글
| [가상 면접 사례로 배우는 대규모 시스템 설계 기초] 처리율 제한 장치의 설계 (3) | 2024.09.29 |
|---|
