5. 안정 해시

💬 해시 키 재배치 문제

  • 여러 서버들에 부하를 균등하게 나누어야 할 때, 해시 함수를 이용할 수 있다.

  • 즉, 특정 키를 기준으로 하여 hash(key) % N 번째의 서버에 요청을 보내는 것이다.

  • 이 방식은 서버 풀의 크기가 고정되어 있고, 데이터 분포가 균등할 때에 정상 동작한다.

  • 특정 서버에 장애가 발생한 경우, 서버 개수 N 값이 변하게 되고 이로 인해 나머지 연산 수행 시 키에 매핑되는 서버의 인덱스도 변하게 된다.

  • 이렇게 되면 잘못된 서버로 요청이 분배되므로 대규모 캐시 미스가 발생할 수 있다.

서버 개수가 4일 때 해시 결과
서버 개수가 3일 때 해시 결과

💬 안정 해시

  • consistent hash

  • 서버와 키를 균등 분포 해시 함수를 이용해 해시 링에 배치하는 방식이다.

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

  • 해시 테이블 크기가 조정될 때 평균적으로 키의 개수 / 슬롯 개수개의 키만 재배치하는 해시 기술이다.

동작 원리

  • 해시 링의 해시 공은 배열으로 존재한다. 배열을 원형 큐처럼 논리적으로 말아올린 형태로 사용하게 된다.

  • 해시 함수로 SHA-1을 사용할 경우 해시 공간 범위는 0부터 2^160 - 1까지이다.

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

    1. 서버의 IP나 이름을 해시 함수에 넣어 해시링 상의 위치를 특정한다. ex) s0, s1, s2, s3

    2. 키 이름 등의 특성을 해시 함수에 넣어 해시링 상의 위치를 특정한다. ex) k0, k1, k2, k3

    3. 키 위치 기준으로 시계방향으로 이동했을 때 가장 처음 만나는 서버에 데이터를 저장한다.

Untitled
  • 서버가 새로 추가되거나 삭제되면 다음 과정이 수행된다.

    • 노드를 해시링에 추가/제거한다.

    • 새로운 노드가 생겼을 경우 기존 키들이 새로운 노드로 재배치될 수 있다. 노드가 사라졌을 경우 기존 키들이 다른 노드로 재배치될 수 있다.

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

장점

  • 서버 추가/제거 시 재배치되는 키의 수가 최소화된다.

  • 데이터가 균등히 분포되어 수평적 규모 확장성에 용이하다.

  • 데이터 균등 분배로 인해 핫스팟 키 문제가 줄어든다.

사례

  • DynamoDB의 파티셔닝 방식

  • Cassandra 클러스터의 데이터 파티셔닝

문제점

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

    파티션: 인접한 서버 사이의 해시 공간

  • 키의 균등 분포가 어려울 수 있다.

  • 아래 그림은 s1~s2 사이의 파티션이 유독 넓어 대부분의 데이터가 s2에 저장되므로, 키의 균등 분포가 이뤄지지 않는 것을 볼 수 있다.

💬 가상 노드

  • 안정 해시 만의 문제점을 개선하기 위한 해결책이다.

  • 가상 노드란 실제 노드 또는 서버를 가리키는 노드로, 한 서버가 해시링 위에 여러개의 노드를 가질 수 있도록 한다.

  • 각 서버는 여러개의 파티션을 관리하게 된다.

  • 가상 노드의 개수를 늘리면 표준 편차가 작아져서 키의 분포가 더욱 균등해진다.

  • 하지만 가상노드의 개수를 늘리면 가상 노드에 대한 데이터 저장 공간이 필요해지기 때문에, 최적의 개수로 조정해야 한다. (tradeoff)

Last updated