이번 내용은 가상면접 사례로 배우는 대규모 시스템 설계 5장 안정 해시 설계에 대한 내용이다.
- 수평적 규모 확장을 위해서는 요청 또는 데이터를 서버에 균등하게 나누는 것이 중요하다.
→ 이를 위해 안정 해시를 설계
해시 키 재배치(rebase) 문제
serverIndex = hash % 4
서버 풀의 크기가 고정되어 있고, 데이터 분포가 균등할때는 잘 작동한다.
but. 서버가 늘어나거나 기존 서버가 삭제 된다면 문제가 생긴다.
→ 키에 대한 해시값은 변하지 않지만 서버 인덱스는 서버 크기가 달라지기에 달라진다.
즉 키가 재분재 되어 대부분 캐시 클라이언트가 데이터가 없는 엉뚱한 서버에 접속한다.
→ 대규모 케시 미스 문제 발생
어떻게 해결하는가?
→ 안정 해시
안정 해시
해시 테이블 크기가 조정될때 평균적으로 k/n 개의 키만 재배치 하는 해시 기술
k: 키의 개수
n: 슬롯의 개수
해시 공간과 해시 링
✏️ 동작 원리
- 해시 함수: SHA-1 사용한다고 가정
- 출력 범위: x0,x1…..xn
- 해시 공간 범위: 0~ 2^160 -1
해시 서버
해시 함수 f 를 사용하면 서버 ip나 이름으 링 위의 어떤 위치에 대응시킬 수 있다.
해시 키
서버 조회
어떤 키가 저장된 서버는 해당 키의 위치로부터 시계 방향으로 링을 탐색해 나가면서 만나는 첫번째 서버이다
서버 추가
서버를 추가하더라고 가운데 키 일부만 재배치 하면 된다.
서버 제거
키 일부만 재배치
기존 구현법의 문제점
1) 서버와 키를 균등 분포 해시 함수를 사용해 해시 링에 재배치
2) 키의 위치에서 링을 시계 방향으로 탐색하다 처음으로 만나는 서버에 키가 저장
-> 두가지 문제점 존재
- 서버가 추가, 삭제될때 상황을 감안하면 파티션의 크기를 균등하게 유지하는 것이 불가능
- 파티션: 인접한 서버 사이의 해시 공간
-> 어떻게 해결하는가? 가상 노드 or 복제 기법
가상 노드
- 가상노드: 실제 노드 또는 서버를 가리키는 노드
- 하나의 서버는 링 위의 여러 가상 노드를 가질 수 있다.
가상 노드의 개수 ⬆️ -> 키의 분포 균등
-> 표준 편차가 작아져서 데이터가 고르게 분포되기 때문
- 표준 편차: 데이터가 어떻게 퍼져 나갔는지 보이는 척도
- 100~200개의 가상 노드를 사용했을 경우 표준 편차의 값은 평균 5% 사이라고 한다.
- 가상 노드를 늘리면 표준 편차의 값은 더 떨어지나, 가상 노드 데이터를 저장할 공간은 더 많이 필요하게 된다.
재배치할 키 결정
어느 범위의 키들을 재배치 해야하는가.
안정 해시의 이점
- 서버가 추가, 삭데 될때 재배치 되는 키의 수 최소화
- 데이터가 보다 균등하게 분포하게 되므로 수평적 규모 확장에 유리
- 핫스팟 키 문제를 줄인다.
