5. 안정 해시 설계

안정 해시가 왜 등장했는가?

• modular 연산에 따라서 분포된 데이터들에서, 서버가 제거된다면 거의 모든 데이터의 위치가 변경된다.

• 그러므로 서비스에 큰 부담이 된다.

안정 해시란?

• 서버를 추가/제거해도 최소한의 데이터만 이동하자임

기본 원리

• hash ring

• hash function

![[Pasted image 20250810151336.png]] ![[Pasted image 20250810151407.png]]

• modular 연산을 사용하지 않으며, 키는 해시 링의 어느 지점에 배치됨.

![[Pasted image 20250810151449.png]]

• 키가 저장되는 위치는 시계방향으로 링을 탐색하다가 만나는 첫 번째 서버

서버 추가

![[Pasted image 20250810151611.png]]

• s4가 추가됨

• 그러면 key0 만 재배치됨.

• 왜?

  • 서버 4가 추가된다음에 key0만 시계방향으로 돌 때 가장 처음 만나게 될 서버이기 때문

• 다른 키들을 재배치 되지 않는다.

서버 제거

![[Pasted image 20250810151725.png]]

• 서버 1 제거

• key1 만 서버 2로 재배치

• 나머지 키에는 영향 없음

안정 해시 알고리즘

• 서버, 키를 균등 분포 해시 함수를 이용해서 해시 링에 배치

• 키의 위치에서 링을 시계방향으로 탐색하다가 만나는 최초의 서버가 키가 저장될 서버

문제점

• 서버 추가, 삭제를 감안하면 균등한 크기의 파티션 유지를 불가

• 키의 균등 분포를 달성하기 어려움

• 이러한 문제점을 해결하기 위해?

  • 가상 노드 또는 복제 노드 기법이 나옴

가상 노드

• 실제 노드 또는 서버를 가르키는 노드

• 하나의 서버는 링 위에 여러개의 가상 노드를 가질 수 있음.

![[Pasted image 20250810153017.png]]

• sx_x -> 가상 노드

• 서버 0을 링위에 배치하기 위해서 s0_0, s0_1, s0_2 세개의 가상노드를 사용

• 데이터는 시계방향으로 돌면서, 가장 가까운 가상노드를 만났을 경우에, 해당 키를 저장할 서버가 된다.

  • 그러나 가상노드는 실제 서버(s0, s1)를 바라보고 있음.

• 왜 가상 노드를 사용하는가?

  • 가상 노드의 갯수를 늘리면 키의 분포는 균등해진다.

재배치할 키 결정

![[Pasted image 20250810153235.png]]

• s4추가

• key0이 s4로 재배치되어야함

정리

• 안정 해시 이점

  • 서버 추가, 삭제 될 때 재배치되는 키의 수가 최소화됨

  • 수평적 규모 확장성 달성하기 위함

  • 핫스팟 문제 줄인다.

    • 특정 샤드에 대한 지나친 접근, 서버 과부하 이슈

• 안정해시가 사용되는 기술

  • amazon dynamoDB의 partition

  • apache cassandra 클러스터에서의 data partition

  • discord

  • akamai cdn

  • meglev 네트워크 부하 분산기

기타

• 대규모 웹 서비스를 위한 분산 캐시 시스템을 설계해주세요. 캐시 서버가 자주 추가/제거될 수 있고, 캐시 미스를 최소화

  • 캐시 서버가 동적으로 스케일링되는 환경에서 캐시 무효화를 최소화가 핵심

  • 해시 기반 샤딩(key % N)을 사용하면 서버 추가/제거 시 거의 모든 키의 위치가 변경되어 대규모 캐시 미스가 발생

  • 안정 해시(Consistent Hashing) 사용

  • 캐시 미스 최소화 전략

    • 예열(Warming) 전략, 새 서버를 링에 추가하기 전 필요한 데이터 미리 복사

• 안정 해시를 사용하는 시스템에서 특정 서버에 부하가 집중되는 핫스팟 문제가 발생했습니다. 어떻게 해결하시겠습니까

  • 핫 스팟이 발생하는 이유?

    • 데이터 스큐(Skew): 특정 키가 매우 인기 있음

    • 해시 공간 불균등: 가상 노드가 충분하지 않음

    • 시간적 패턴: 특정 시간대 특정 데이터 집중

  • 해결

    • 인기 데이터 복제 전략

    • 가상 노드 동적 조정

• 안정 해시를 사용하는 분산 스토리지에서 서버 장애 시 데이터 손실 없이 빠르게 복구하는 방법을 설계

  • 데이터 손실을 막으려면 복제가 필수

  • W (쓰기 쿼럼) + R (읽기 쿼럼) > N (복제 수)

    • 쓰기: 3개 중 2개 서버가 성공해야 완료

    • 읽기: 3개 중 2개 서버에서 읽어서 최신 버전 선택