# 5. 안정 해시

## 💬 해시 키 재배치 문제

* 여러 서버들에 부하를 균등하게 나누어야 할 때, 해시 함수를 이용할 수 있다.
* 즉, 특정 키를 기준으로 하여 `hash(key) % N` 번째의 서버에 요청을 보내는 것이다.
* 이 방식은 서버 풀의 크기가 고정되어 있고, 데이터 분포가 균등할 때에 정상 동작한다.
* 특정 서버에 장애가 발생한 경우, 서버 개수 N 값이 변하게 되고 이로 인해 나머지 연산 수행 시 키에 매핑되는 서버의 인덱스도 변하게 된다.
* 이렇게 되면 잘못된 서버로 요청이 분배되므로 대규모 캐시 미스가 발생할 수 있다.

<figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2FW21DJTretdsyMP0L5rJu%2Fimage.png?alt=media&#x26;token=a51ee0b8-2911-48a1-8c8c-bc6eab8477ab" alt=""><figcaption><p>서버 개수가 4일 때 해시 결과</p></figcaption></figure>

<figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2FvqEzSRKElSiNw3yXiumm%2Fimage.png?alt=media&#x26;token=0ea19c6d-a183-425b-8dcb-0883a42883b3" alt=""><figcaption><p>서버 개수가 3일 때 해시 결과</p></figcaption></figure>

## 💬 안정 해시

* consistent hash
* 서버와 키를 균등 분포 해시 함수를 이용해 해시 링에 배치하는 방식이다.
* 키위 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버에 키를 저장한다.
* 해시 테이블 크기가 조정될 때 평균적으로 `키의 개수 / 슬롯 개수`개의 키만 재배치하는 해시 기술이다.

### 동작 원리

* 해시 링의 해시 공은 배열으로 존재한다. 배열을 원형 큐처럼 논리적으로 말아올린 형태로 사용하게 된다.
* 해시 함수로 SHA-1을 사용할 경우 해시 공간 범위는 0부터 2^160 - 1까지이다.

<figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2Fi5b0Tl6GXZlpe2sPcpzE%2Fimage.png?alt=media&#x26;token=112e6d16-71c8-48aa-9935-5a981c727f87" alt=""><figcaption></figcaption></figure>

*   해시링 기반의 서버 선택은 다음과 같이 수행된다.

    1. 서버의 IP나 이름을 해시 함수에 넣어 해시링 상의 위치를 특정한다. ex) s0, s1, s2, s3
    2. 키 이름 등의 특성을 해시 함수에 넣어 해시링 상의 위치를 특정한다. ex) k0, k1, k2, k3
    3. **키 위치 기준으로 시계방향으로 이동했을 때 가장 처음 만나는 서버에 데이터를 저장**한다.

    <figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2FKVattLzcukU9VbYje0cR%2Fimage.png?alt=media&#x26;token=6f18cfaf-64ae-44e9-a9eb-7a437b06aea9" alt=""><figcaption></figcaption></figure>

![Untitled](https://s3-us-west-2.amazonaws.com/secure.notion-static.com/78dc4893-eae4-46c0-919a-869f201292d9/Untitled.png)

* 서버가 새로 추가되거나 삭제되면 다음 과정이 수행된다.
  * 노드를 해시링에 추가/제거한다.
  *   새로운 노드가 생겼을 경우 기존 키들이 새로운 노드로 재배치될 수 있다. 노드가 사라졌을 경우 기존 키들이 다른 노드로 재배치될 수 있다.

      > 재배치라 함은 해당 키를 담당하는 서버가 변경되었다는 의미이다.

### 장점

* 서버 추가/제거 시 재배치되는 키의 수가 최소화된다.
* 데이터가 균등히 분포되어 수평적 규모 확장성에 용이하다.
* 데이터 균등 분배로 인해 핫스팟 키 문제가 줄어든다.

### 사례

* DynamoDB의 파티셔닝 방식
* Cassandra 클러스터의 데이터 파티셔닝

### 문제점

*   서버가 추가/삭제되는 상황이 발생하면서 각 서버들의 파티션의 크기를 균등히 유지하는게 불가능해진다.

    > 파티션: 인접한 서버 사이의 해시 공간
* 키의 균등 분포가 어려울 수 있다.
* 아래 그림은 s1\~s2 사이의 파티션이 유독 넓어 대부분의 데이터가 s2에 저장되므로, 키의 균등 분포가 이뤄지지 않는 것을 볼 수 있다.

<figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2FuBdzf2YitbGXCTVnQk9q%2Fimage.png?alt=media&#x26;token=66173b82-d0c5-40d6-8e59-ca5a42d7b261" alt=""><figcaption></figcaption></figure>

## 💬 가상 노드

* 안정 해시 만의 문제점을 개선하기 위한 해결책이다.
* 가상 노드란 실제 노드 또는 서버를 가리키는 노드로, 한 서버가 해시링 위에 여러개의 노드를 가질 수 있도록 한다.
* 각 서버는 여러개의 파티션을 관리하게 된다.

<figure><img src="https://946524419-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FZqOTWctN1y9hEXEl4sKd%2Fuploads%2FX0jZ9Sj7Uwcs70h8R3wL%2Fimage.png?alt=media&#x26;token=8052bc50-6a3a-4427-ab0a-ab333c0f67fd" alt=""><figcaption></figcaption></figure>

* 가상 노드의 개수를 늘리면 표준 편차가 작아져서 키의 분포가 더욱 균등해진다.
* 하지만 가상노드의 개수를 늘리면 가상 노드에 대한 데이터 저장 공간이 필요해지기 때문에, 최적의 개수로 조정해야 한다. (tradeoff)
