# 안정 해시

### 해시 키 재비치(rehash) 문제

- 보편적인 해시 함수 : `serverIndex = hash(key) % N` (N은 서버 개수)

- 서버의 개수가 바뀌면 serverIndex를 모두 다시 계산 ⇒ 대규모 캐시 미스가 발생

## 안정 해시(consistant hash)

- 해시 함수로 SHA-1를 사용한다고 가정하면 총 해시 공간은 0~2^{160}-1

- 서버 : 서버의 고유한 값(IP, 이름 등)을 해싱해서 이 공간 어딘가에 배치한다.

- 키 : 키를 해싱해서 이 공간 어딘가에 배치한다.

- 해시 공간의 앞 뒤를 이어붙이면 아래 그림처럼 된다.

- 그리고 모든 키값은 자기 바로 다음에 나오는 서버(노드)에 할당된다.

![Image](https://upload.cafenono.com/image/slashpageHome/20240820/134345_mwA5F6pTuQYRnegsrG?q=80&s=1280x180&t=outside&f=webp)

- 서버 추가 : 오른쪽 그림과 같이 주황색 서버가 추가되면 파랑과 주황 사이의 키값들만 재배치된다.

- 서버 제거 : 주황색 서버가 제거된다면, 주황색 서버에 배치된 키들만 재배치된다.

### 문제점

- 파티션(서버 사이의 해시 공간)이 균일하지 않다.

    - 서버를 추가 또는 삭제할 경우 파티션의 크기가 급격하게 달라진다.

- 키값이 균등하게 분포하지 않는다.

⇒ 가상 노드 또는 복제 기법을 사용해 해결한다.

## 가상 노드

하나의 서버를 여러 해시 공간에 가상으로 두는 방법이다. 

![Image](https://upload.cafenono.com/image/slashpageHome/20240820/134345_lhpdyezz3Vw5r3yEVV?q=80&s=1280x180&t=outside&f=webp)

- 가상 노드의 개수가 많아질 수록 표준 편차가 줄어들어 키의 분포는 점점 균등해진다.

- SHA-1에서 가상 노드가 200개 일 때 표준 편차가 평균의 5%로 제일 낮았다.

- 재배치 방법은 안정 해시와 비슷하게 가상 노드 사이의 키들만 재배치한다.

- 표준 편차와 노드의 저장 공간 사이의 트레이드 오프가 필요하다.

## 장점

- 재배치되는 키의 수가 최소화된다.

- 데이터가 균등하게 분포하므로 수평적 규모 확장에 용이하다.

- 특정 노드(샤드)에 접근이 몰리는 핫스팟 문제를 줄일 수 있다.

### 용례

- AWS DynamoDB 파티셔닝 관련 컴포넌트

- Apache Cassandra 클러스터의 데이터 파티셔닝

- 디스코드 채팅 앱

## 추가

데이터를 여러 대의 노드에 저장하는 방법이다. 키의 위치 다음 N개의 노드에 데이터를 저장한다.

![Image](https://upload.cafenono.com/image/slashpageHome/20240820/134346_FTZw8RB1xnmyyaVM9K?q=80&s=1280x180&t=outside&f=webp)

For the site tree, see the [root Markdown](https://slashpage.com/kaonmir.md).