안정 해시 Consistent Hash

안정 해시 설계

수평적인 규모 확장성을 달성하기 위해 요청 또는 데이터를 서버에 균등하게 나누는 방법

해시 키 재배치(rehash) 문제

• serverIndex = hash(key) % N (서버 수)
• 서버가 추가되면 전체 서버의 갯수가 달라져서, 기존의 hashKey가 달라진다
• 해시 함수를 통한 해싱 결과가 균등하지 않을 수 있다

안정 해시

• 해시 테이블의 크기가 변경될 떄 K/N개의 키만 재배치하는 해시 기술

• K : 키의 갯수

• N : slot 갯수

• SHA-1 해시함수의 공간은 0 ~ 2^160-1

• 해시 함수의 해시 공간을 구부려서 해시 링을 만든다

• 임의의 위치에 서버를 배치한다

• 해시 함수 - 해시 키 - 해시 링에서 오른쪽으로 돌면서 가장 가까운 서버에 접근

• 서버가 추가, 제거되어도 근접한 서버에 저장되었던 키들만 cache miss로 영향받음

안정 해시 문제점 2가지

• 서버가 추가, 삭제되는 상황에서 해시 링의 partition의 크기를 균등하게 유지하는게 불가능
  • 서버개 해시 링에서 담당해야하는 공간 사이에 차이가 있음
• 해시 키가 해시 공간 안에서 균등하게

안정 해시 문제점 극복 :: 가상 노드

• 서버는 여러개의 가상 노드를 가짐
• 해시 링에 가상 노드를 배치
• 각 서버는 여러개의 가상 노드에 대응되는 부분을 담당
• 대략적으로 100~200개의 가상 노드를 설정하면 표준 편차가 5%정도 발생함
  • 가상 노드 정보를 저장하기 위한 공간을 감안해서 적절한 수준을 선택해야 함

Reference

• 가상 면접 사례로 배우는 대규모 시스템 설계 기초 5장