FAST01

가상 면접 사례로 배우는 대규모 시스템 설계 기초 - 정리 5장 안정 해시 설계

7 min read

가상 면접 사례로 배우는 대규모 시스템 설계 기초 - 정리 5장 안정 해시 설계

요약

가상 면접 사례로 배우는 대규모 시스템 설계 기초 리뷰

아키텍처 개념을 실제 설계 판단에 연결하기 위한 참고 노트입니다.

핵심 포인트

  • 가상 면접 사례로 배우는 대규모 시스템 설계 기초 리뷰
  • 가상 면접 사례로 배우는 대규모 시스템 설계 기초
  • 5장 안정 해시 설계
  • 해시 키 재배치(rehash) 문제
  • 안정 해시

지식 그래프

정리 내용

가상 면접 사례로 배우는 대규모 시스템 설계 기초

학습 목적으로 정리한 내용으로 문제가 있다면 내리겠습니다.

(이 책은 한국어판 저작권은 에이전시 원을 통해 저작권자와의 독점 계약으로 인사이트에 있습니다. 저작권법에 의해 한국 내에서 보호를 받는 저작물이므로 무단전재와 무단 복제를 금합니다.)

5장 안정 해시 설계

수평적 규모 확장을 위해 요청 이나 데이터를 균등하게 저장해야 한다. 이 기술은 모든 데이터를 균등하게 보편적으로 나누기 위해 사용되는 기술이다.

해시 키 재배치(rehash) 문제

ServerIndex = Hash(Key) % N (N은 서버의 개수이다.) 이런 해쉬 함수가 있다고 가정할 때 인덱스의 키 값에 따라 N개의 서버에 균등하게 저장된다. 하지만 서버가 만약 추가되거나 없어진다면 N 의 수는 변동하고 모든 Hash함수를 통해 저장된 값들에게 변동사항이 생긴다. 안정 해시는 이러한 문제를 효과적으로 해결하고자 만들어진 기술이다.

안정 해시

안정 해시 란 테이블의 크기가 조정될 때 재배치의 횃수가 평균적으로 K/N 번인 해시 기술이다. K는 키의 개수이고 N은 슬롯의 개수이다.

  1. 해시 공간과 해시 링 X0부터 Xn크기의 슬롯이 있다고 가정하자 크기가 N인 해시를 담을 수 있는 공간이다. 이 공간을 원 형태로 만들어 슬롯의 마지막인 Xn의 다음을 다시 처음부터 X0라고 가정하는 해시 링을 생성한다.
  2. 해시 서버와 해시 키 해시 함수 Function()을 사용하면 키 값을 통해 어떤 슬롯에 해시 키가 위치하고 시계 방향으로 가장 가까운 해시 서버에 그 키를 저장하게 된다.
  3. 서버 추가 및 제거 서버를 추가하거나 제거하는 과정은 원형 링에 N(서버의 수)개의 노드를 균등하게 배치한 상태에서 시작한다. X번째 서버에 포함된 키는 슬롯의 반시계방향에 있는 X-1번째와 X번쨰 서버가 위치한 모든 키가 포함된다. 이런 과정을 상상하고 추가하고 제거하는 것은 손 쉬운 일이다.

기본 구현법 두가지

  • 서버와 키를 균등 분포 해시 함수를 사용하여 해시 링에 배치
  • 키의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버가 키가 저장될 서버이다. 이 두 가지 절차는 몇가지 문제가 있다.
  1. 서버가 추가되거나 삭제되는 상황을 감안하면 파티션의 크기를 균등하게 유지하는 게 불가능하다.
  2. 키의 균등 분포를 달성하기 어렵다는 것이다. 위 문제를 해결하기 위해 가상노드가 나왔다.

가상노드

가상노드는 실제 노드 또는 서버를 가르키는 노드로서, 하나의 서버는 링 위에 여러 개의 가상 노드를 가질 수 있다. S1이라는 서버를 S1_0, S1_1, S1_2로 가상 서버로 만들어 링위에 배치할 수 있다는 의미이다. 이런 가상 노드의 개수를 늘리면 키의 분포는 점점 균등해진다. 표준 편차가 작아져서 데이터가 고르게 분포되기 때문이다.

결론

이 장은 안정해시의 필요성과 그 동작 방법에 대해 말해보았다.

  • 서버가 추가되거나 삭제될 때 재배치되는 키의 수를 최소화한다.
  • 데이터가 보다 균등하게 분포되므로 수평적 규모확장에 유리하다.
  • 샤드에서 나올 수 있는 문제점들을 해결한다.

학습 목적으로 정리한 내용으로 문제가 있다면 내리겠습니다.

(이 책은 한국어판 저작권은 에이전시 원을 통해 저작권자와의 독점 계약으로 인사이트에 있습니다. 저작권법에 의해 한국 내에서 보호를 받는 저작물이므로 무단전재와 무단 복제를 금합니다.)

출처

그래프 뷰