대규모 시스템 설계 기초 - 5. 안정 해시 설계

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

해시 키 rehash 문제

자 여러분~ 한 번 생각해봅시다! cache 서버에 이런 저런 key-value를 넣어두려고 하는데 cache서버가 1, 2, 3, 4 총 4대 있어요!

방금 들어온 Apple 값은 어디 서버에 넣어야 할까요?!!!

 

 

우리의 목표

들어오는 req를 N개의 서버에 나눌 것인데, 1) 가능한 균일하게 2) N의 값에 변경이 있더라도 문제 없이 배분하고 싶다.

가능하면 modular 보다 좋은 방법으로...!

• 해시 : 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 mapping 하는 것
• 안정해시 : 해시 테이블의 크기가 조정될 때 평균적으로 오직 k/n개의 키만 재배치하는 해시 기술. 여기서 k는 키의 개수이고, n은 슬롯의 개수이다. 전통적인 해시 테이블은 슬롯의 수가 바뀌면 거의 대부분의 키를 재배치한다.

 

접근 1

• 서버와 key를 균등 분포 해시 함수를 이용해 해시링에 배치한다.
  • 1번서버 → 해싱 → ASDFQWEFXCVC
  • 2번서버 → 해싱 → 124osdvQ@WDF
  • Apple → 해싱 → 12039ㄴㅇㅍㅋㅌ
• key의 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버에 저장한다.

접근 1은 두 가지 문제가 있다.

1. 편향이 생길 수 있다.
2. 서버 삭제/생성시 영향 범위가 크다

 

접근 2

가상 노드를 사용한다.

• 가상 노드 : 실제 노드 또는 서버를 가리키는 노드

가상 노드의 개수를 늘리면 키의 분포는 점점 더 균등해지지만, 가상 노드 데이터를 저장할 공간은 더 많이 필요하게 된다. 시스템 요구사항에 맞도록 가상 노드 개수를 절히 조정해야 한다.