5. Consistent Hashing
안정 해시
Last updated
안정 해시
Last updated
해싱(Hashing)은 대규모 시스템 설계에서 데이터를 균등하게 분배하기 위해 사용하는 기술 중 하나입니다. 해싱은 주로 데이터베이스 샤딩(Database Sharding), 캐시 분배(Cache Distribution), 로드 밸런싱(Load Balancing) 등의 상황에서 활용됩니다.
기존 해싱 방식은 간단히 말해, 특정 해시 함수를 사용해 데이터를 고정된 개수의 서버(노드)에 균등하게 분배하는 방법입니다. 예를 들어, 해시 함수 hash(key) % N을 사용해 데이터를 N개의 서버에 나눌 수 있습니다. 여기서 key는 데이터의 식별자, N은 서버의 개수입니다.
이 방식은 기본적으로 매우 효율적이지만, 서버의 수가 변경될 때 문제가 발생합니다. 서버가 추가되거나 제거될 경우, 전체 데이터의 해시 값을 재계산해야 하며, 이는 시스템의 성능에 큰 부담을 줄 수 있습니다.
기존 해싱 방식에서의 주요 문제점은 서버의 수가 변경될 때 대부분의 데이터가 재배치된다는 점입니다. 예를 들어, 4개의 서버가 있을 때 해시 함수 hash(key) % 4을 사용해 데이터를 분배한다고 가정합니다. 이때 서버가 하나 추가되어 5개가 된다면, 모든 키의 위치가 변경되어 전체 데이터의 대부분이 새로운 서버로 이동해야 합니다.
이러한 재배치 문제는 특히 대규모 시스템에서 매우 비효율적입니다. 데이터 이동이 많아지면 네트워크 트래픽이 증가하고, 서버 간의 데이터 일관성을 유지하기 어려워지며, 시스템의 성능 저하로 이어질 수 있습니다. 이 문제를 해결하기 위해 안정 해시(Consistent Hashing) 기법이 고안되었습니다.
안정 해시에서 핵심 개념은 "해시 공간(Hash Space)"과 "해시 링(Hash Ring)"입니다. 해시 공간은 해시 값이 가질 수 있는 모든 값을 포함하는 공간으로, 일반적으로 0에서 2^32-1까지의 범위를 갖습니다. 이 해시 공간을 원형으로 연결한 것이 해시 링입니다.
해시 링에서는 각 서버가 해시 공간의 특정 위치에 존재하게 됩니다. 즉, 서버와 데이터 키 모두 해시 링에 매핑되며, 데이터 키는 자신과 가장 가까운 서버에 할당됩니다. 이 구조 덕분에 서버의 추가 및 제거가 발생해도, 영향을 받는 데이터 키의 수가 적어집니다.
해시 링에 위치한 각 서버는 특정 해시 값을 가지며, 이 값은 서버의 고유 식별자나 IP 주소를 해싱하여 결정됩니다. 서버의 위치는 해시 링 상에서 고정되며, 각 서버는 자신의 위치에서 시계방향으로 가장 가까운 서버까지의 데이터를 담당합니다.
데이터 키 또한 해시 링에 매핑됩니다. 특정 데이터 키는 해시 함수를 통해 해시 링의 특정 위치에 배치되며, 해당 위치에서 시계방향으로 가장 가까운 서버에 할당됩니다. 이 과정은 서버가 추가되거나 제거될 때에도 동일하게 적용됩니다.
데이터 키에 해당하는 서버를 찾기 위해서는 키를 해싱하여 해시 링에 위치시킨 후, 시계방향으로 가장 가까운 서버를 찾으면 됩니다. 이로 인해 서버 추가 및 제거 시에도 대부분의 데이터가 그대로 유지되며, 재배치되는 데이터는 최소화됩니다.
새로운 서버를 해시 링에 추가할 때는 해당 서버의 위치를 결정하고, 그 위치에서 시계방향으로 가장 가까운 서버까지의 데이터를 새로운 서버로 이동시킵니다. 이때 재배치되는 데이터는 이전 서버에 위치했던 일부 데이터뿐이므로, 전체 데이터 이동의 비율은 매우 적습니다.
서버가 제거될 경우, 그 서버가 담당하던 데이터는 시계방향으로 가장 가까운 서버로 이동됩니다. 이 과정에서도 재배치되는 데이터의 양이 최소화되므로, 시스템의 안정성이 유지됩니다.
안정 해시의 기본 구현에는 두 가지 문제점이 존재합니다.
첫째, 서버가 고르게 분포되지 않을 경우 특정 서버에 데이터가 집중될 수 있다는 점입니다.
둘째, 해시 링에서 서버의 위치가 겹칠 가능성이 있어, 일부 서버에 부하가 집중될 수 있습니다.
위의 문제를 해결하기 위해 도입된 개념이 가상 노드(Virtual Nodes)입니다. 가상 노드는 실제 서버를 여러 개의 논리적 서버로 분할하여 해시 링에 여러 위치에 배치하는 방법입니다. 이를 통해 해시 링에서의 서버 분포를 더욱 고르게 할 수 있으며, 데이터의 부하를 분산시킬 수 있습니다.
서버 추가 및 제거 시 재배치할 키를 결정하는 것은 안정 해시의 핵심 기능입니다. 가상 노드를 도입함으로써 재배치되는 키의 수를 최소화할 수 있으며, 데이터의 균등한 분배를 유지할 수 있습니다. 이로 인해 시스템은 확장성과 안정성을 동시에 확보할 수 있습니다.
