5. 안정 해시
Last updated
Last updated
여러 서버들에 부하를 균등하게 나누어야 할 때, 해시 함수를 이용할 수 있다.
즉, 특정 키를 기준으로 하여 hash(key) % N 번째의 서버에 요청을 보내는 것이다.
이 방식은 서버 풀의 크기가 고정되어 있고, 데이터 분포가 균등할 때에 정상 동작한다.
특정 서버에 장애가 발생한 경우, 서버 개수 N 값이 변하게 되고 이로 인해 나머지 연산 수행 시 키에 매핑되는 서버의 인덱스도 변하게 된다.
이렇게 되면 잘못된 서버로 요청이 분배되므로 대규모 캐시 미스가 발생할 수 있다.
consistent hash
서버와 키를 균등 분포 해시 함수를 이용해 해시 링에 배치하는 방식이다.
키위 위치에서 링을 시계 방향으로 탐색하다 만나는 최초의 서버에 키를 저장한다.
해시 테이블 크기가 조정될 때 평균적으로 키의 개수 / 슬롯 개수개의 키만 재배치하는 해시 기술이다.
해시 링의 해시 공은 배열으로 존재한다. 배열을 원형 큐처럼 논리적으로 말아올린 형태로 사용하게 된다.
해시 함수로 SHA-1을 사용할 경우 해시 공간 범위는 0부터 2^160 - 1까지이다.
해시링 기반의 서버 선택은 다음과 같이 수행된다.
서버의 IP나 이름을 해시 함수에 넣어 해시링 상의 위치를 특정한다. ex) s0, s1, s2, s3
키 이름 등의 특성을 해시 함수에 넣어 해시링 상의 위치를 특정한다. ex) k0, k1, k2, k3
키 위치 기준으로 시계방향으로 이동했을 때 가장 처음 만나는 서버에 데이터를 저장한다.
서버가 새로 추가되거나 삭제되면 다음 과정이 수행된다.
노드를 해시링에 추가/제거한다.
새로운 노드가 생겼을 경우 기존 키들이 새로운 노드로 재배치될 수 있다. 노드가 사라졌을 경우 기존 키들이 다른 노드로 재배치될 수 있다.
재배치라 함은 해당 키를 담당하는 서버가 변경되었다는 의미이다.
서버 추가/제거 시 재배치되는 키의 수가 최소화된다.
데이터가 균등히 분포되어 수평적 규모 확장성에 용이하다.
데이터 균등 분배로 인해 핫스팟 키 문제가 줄어든다.
DynamoDB의 파티셔닝 방식
Cassandra 클러스터의 데이터 파티셔닝
서버가 추가/삭제되는 상황이 발생하면서 각 서버들의 파티션의 크기를 균등히 유지하는게 불가능해진다.
파티션: 인접한 서버 사이의 해시 공간
키의 균등 분포가 어려울 수 있다.
아래 그림은 s1~s2 사이의 파티션이 유독 넓어 대부분의 데이터가 s2에 저장되므로, 키의 균등 분포가 이뤄지지 않는 것을 볼 수 있다.
안정 해시 만의 문제점을 개선하기 위한 해결책이다.
가상 노드란 실제 노드 또는 서버를 가리키는 노드로, 한 서버가 해시링 위에 여러개의 노드를 가질 수 있도록 한다.
각 서버는 여러개의 파티션을 관리하게 된다.
가상 노드의 개수를 늘리면 표준 편차가 작아져서 키의 분포가 더욱 균등해진다.
하지만 가상노드의 개수를 늘리면 가상 노드에 대한 데이터 저장 공간이 필요해지기 때문에, 최적의 개수로 조정해야 한다. (tradeoff)
