Consistent Hashing

2024-07-24

분산 시스템에서 데이터를 효율적이게 관리, 분배하는 접근 방식.

분산 시스템의 여러 노드에 데이터를 균등하게 분배 노드 추가/제거 시 데이터 재배치 최소화

• 데이터 재배치

  기존 데이터를 새로운 노드 구성에 맞게 재분배 과정

  만약 새 노드가 추가된다면 원래 있던 데이터를 노드 개수에 맞게 재해싱하여 공간을 할당해줘야한다.

위의 데이터 재배치를 읽었다면 이제 Consistent Hashing에서 효율적이게 데이터 재배치를 하는 과정을 이해할 수 있다.

노드 추가 상황을 설명하기 위해 예시를 들겠다.

상황은 기존에 A(10)노드와 B(100)노드가 존재했는데, 본인은 A B 사이에 M(50) 노드를 추가 하고 싶다.
기존의 노드 구조 ——A(10)—————B(100)——
원하는 노드 구조 ——A(10)—M(50)—B(100)——

기존의 데이터 할당 방식을 알려주겠다.

[5, 10, 20, 50, 90, 100, 110] 해당 정수 값이 데이터라고 생각하자

• 기존의 노드 구조

  • 5의 경우: A보다 작고, B보다 작음 → A에 할당
  • 10의 경우: 당연히…A에 할당
  • 20의 경우: A보다 크고, B보다 작음 → B에 할당
  • 50의 경우: A보다 크고, B보다 작음 → B에 할당
  • 90의 경우: A보다 크고, B보다 작음 → B에 할당
  • 100의 경우: 당연히…B에 할당
  • 110의 경우: A보다 크고, B보다 큼 → B에 할당

• 원하는 노드 구조 (M 노드 추가)

  • 5의 경우: A보다 작고, B보다 작음 → A에 할당
  • 10의 경우: 당연히…A에 할당
  • 20의 경우: A보다 크고, M보다 작음 → M
  • 50의 경우: 당연히…M에 할당
  • 90의 경우: M보다 크고, B보다 작음 → B에 할당
  • 100의 경우: 당연히…B에 할당
  • 110의 경우: A보다 크고, B보다 큼 → B에 할당

어떤 방식으로 데이터 재배치를 최적화할 수 있는 지 감이 오는가?

어떤 노드 두 개 사이에 데이터가 배치되어야 한다면, 그 데이터는 노드 번호가 큰 곳으로 배치가 된다.

이 말을 데이터 재배치에 적용시켜보면, 추가되는 노드의 데이터는 바로 이전 노드에서 가져오면 된다는 것이다.

하지만 이 경우에도 문제점은 아직 존재한다.

만약 데이터가 엄청 많지만, 노드의 개수는 적다면?

→ 데이터가 대량으로 이동 ⇒ 비효율적이다.

이 경우엔 가상 노드란 걸 사용해 해결을 할 수 있다.

가상 노드는 물리적 노드를 노드 구성 구조에서 여러 개의 가상 위치로 표현하는 방식이다.

각 물리적 노드에 여러 개의 해시 값을 할당하여 물리적 노드 개수가 부족 했을 때의 문제점을 해결할 수 있다.

• 추가/제거 시 데이터 재배치 최소화
• 특정 범위의 키가 한 서버에 집중되는 현상 방지 (핫스팟 문제)