일관된 해싱
일관된 해싱은 노드가 늘거나 줄어들 때 이동해야 하는 키를 최소화하도록 해시 공간에 노드와 키를 매핑한다 분산 키 배치 알고리즘 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용...
| 분류 | 알고리즘 · 분산 키 배치 알고리즘 |
|---|---|
| 목적 | 노드가 늘거나 줄어들 때 이동해야 하는 키를 최소화하도록 해시 공간에 노드와 키를 매핑한다 |
| 처리 방식 | 원형 해시 링에 노드를 배치하고 키의 위치에서 시계 방향으로 처음 만나는 노드에 키를 할당한다 |
| 복잡도·성능 | 탐색 자료구조에 따라 O(log m) 노드 검색; 재배치 비율은 노드 구성에 의존 |
| 필수 조건 | 키와 노드에 일관된 해시 함수를 적용하고 노드 멤버십 정보가 일관되게 관리되어야 한다 |
| 참고 문헌 | 기술 참고 자료 |
| 관련 분야 | 알고리즘, 자료구조 |
일관된 해싱은 노드가 늘거나 줄어들 때 이동해야 하는 키를 최소화하도록 해시 공간에 노드와 키를 매핑한다 분산 키 배치 알고리즘 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로 분석할 수 있다.[1]
처리 과정은 원형 해시 링에 노드를 배치하고 키의 위치에서 시계 방향으로 처음 만나는 노드에 키를 할당한다. 가상 노드와 복제 배치를 사용하면 노드별 부하의 불균형을 완화할 수 있다. 실제 구현에서는 각 단계의 결과가 어떤 의미를 갖는지 불변식을 정하고, 입력·갱신·질의의 처리 경로를 구분한다.
성능은 탐색 자료구조에 따라 O(log m) 노드 검색; 재배치 비율은 노드 구성에 의존 올바르게 적용하려면 키와 노드에 일관된 해시 함수를 적용하고 노드 멤버십 정보가 일관되게 관리되어야 한다 데이터의 범위와 해시·비교·수치 처리 규칙, 실패 시의 동작 등을 명확히 해야 구현체에 따라 결과가 달라지는 상황을 줄일 수 있다.
활용 및 관련 기법과 비교하면 분산 캐시·샤딩·스토리지 배치에 사용한다. 해시만으로 복제 일관성이나 합의가 해결되지는 않는다. 성능 평가에서는 초기 자료구조 구성과 질의·갱신, 저장 공간을 분리하여 분석하고, 실제 하드웨어의 캐시 및 메모리 접근 비용도 함께 고려한다.[2]