> For the complete documentation index, see [llms.txt](https://real-dev.gitbook.io/real-library/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://real-dev.gitbook.io/real-library/learn_large_scale_system_design_fundamentals_with_virtual_interview_examples/readme/chapter5..md).

# Chapter5. 안정 해시 설계

## Chapter5. 안정 해시 설계

수평적 규모의 확장을 위해선 데이터를 균등하게 배분하는 설계가 중요하다. 안정 해시는 이 목표를 달성하기 위해 보편적으로 사용하는 기술이다.

### 해시 키 재배치 문제

* N개의 캐시 서버가 있고, (X % N) 해싱 함수에 따라 데이터를 분산하는 경우 별 문제 없이 균등하게 데이터를 분산할 수 있다.
* 단, 문제는 캐시 서버를 증감 할 때 발생한다. 하나의 캐시 서버가 늘어날 때 해당 캐시 서버를 비워둔 채로 유지하게 되면 데이터 불균형이 일어나고, 모든 데이터를 재정렬하는 것은 컴퓨팅 비용을 상당 부분 소모하며 시스템의 일시적 부하를 일으킨다.
* 안정해시는 이런 문제를 해결하기 위해 데이터를 해시 링을 활용하여 재배치 문제를 완화시킨다.

#### 해시 링

* SHA-1을 예로 들어 해시 공간의 범위는 0부터 2^160-1까지로 할당된다. 이 때 선형적인 해시 공간을 관념적으로 구부리면 그림 5-4와 같이 구성할 수 있다.

<figure><img src="/files/h8FfJggXrauDT2IiudK5" alt="" width="375"><figcaption><p>관념적으로 그린 해시 링</p></figcaption></figure>

#### 서버 조회

* 해시링에서 데이터와 서버의 관계는 그림 5-7과 같이 나타난다.<br>

  <figure><img src="/files/NsSHaZd3WO5DElOnEsT6" alt="" width="375"><figcaption></figcaption></figure>
* 간략히 설명해서 해시 함수를 거쳐서 지정된 키 값들은 각 키 값의 위치에서 시계방향으로 탐색해 처음 마주치는 서버에 저장된다. 이렇게되면 서버가 추가/제거되더라도 해당 서버에 저장되어 있던 키 일부만 영향을 받게된다.
* 단, 이 기본적인 안정 해시의 문제는 두 가지로 각 서버가 갖는 해시 공간의 크기가 불균형하다는 점과 키의 (갯수의) 균등 분포를 달성하기 어렵다는 점이다.}<br>

  <figure><img src="/files/qZsYzLH4blQCRMz9HSAX" alt="" width="375"><figcaption><p>불균형하게 배치된 해시 링, 대부분의 키가 S2에 할당된다.</p></figcaption></figure>

### 가상 노드, Replica

<figure><img src="/files/WDl5o9Ehd0thFod0U2kZ" alt="" width="563"><figcaption><p>가상 노드가 적용된 해시 링. 가상 노드가 늘어날 수록 표준 편차가 감소한다.</p></figcaption></figure>

* 간략히 설명해서 서버 사이사이에 서버를 가르키는 가상 노드를 심어두고 해시 키가 가상 노드를 참조 연결 - 가상 노드가 실제 서버를 참조 하는 방식으로 연결하는 형태이다.
* 해당 방식을 사용하게 되면 가상 노드의 갯수가 증가할 수록 표준편차가 줄어들어 데이터가 균형있게 저장되는 장점이 있다. 단, 가상 노드 자체가 차지하는 공간이 증가하므로 어느 정도의 타협이 필요하다.