• 요청 또는 데이터를 서버에 균등하게 분포시키기 위해서 사용하는 기술

해시 키 재배치 문제

• 서버에 부하를 균등하게 나누는 일반적인 방법은 해시 키를 서버 수로 나눈 나머지를 활용하는 것이다.

serverIndex = hashKey % n (n = 서버의 개수)

• 이러한 방법은 서버 풀(서버의 개수)가 고정되어 있을 때는 문제가 없지만, 서버의 생성 / 삭제가 발생시 문제가 발생할 수 있다.
  • n 값이 달라지기에 대부분의 해시키가 재배치될 것이고, 이는 대규모 캐시 미스가 발생하는 문제를 야기할 수 있다 (서버 부하 증가)

대안 : 안정 해시

• 안정 해시 : 서버 풀의 개수가 변경될 때 오직 평균 k/n개의 키만 재배치하는 기술

  ( k = 키의 수, n = 서버의 수)

해시 공간과 해시 링

• 해시 링 : 일정 범위의 해시 공간을 할당하고, 해당 해시 공간의 시작과 끝을 이어준 구조
  • SHA-1의 경우, 0~2의 160승-1 만큼의 해시 공간을 할당하고, 0번째 해시 공간과 마지막 해시 공간을 이어서 해시 링을 생성한다.

해시 서버

• 해시 서버 : 해시 링 위에 배치된 서버
• 해시 함수 f를 활용하면, 서버 IP나 이름을 해시 링 위에 대응시킬 수 있다.

해시 키와 서버 조회

• 해시 키를 해시 링 위의 어느 지점에 배열할 수 있다.
• 서버 조회를 하고자 한다면, 해시 키에서 시계방향으로 링 위를 탐색하면서 만나는 첫 번째 서버를 조회하면 된다.

서버 추가 / 삭제

• 서버 추가 / 삭제
  • 특정 서버가 추가된다면, 서버가 추가된 위치에서부터 시계 반대 방향으로 탐색했을 때 만나는 첫 서버까지의 해시 키가 재배치될 것이다.