일관된 해싱

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사
- 2.1. 초기 개념
- 2.2. 발전과 확장
3. 일관된 해싱의 필요성
4. 기본 원리 및 동작 방식
5. 기술적 특징
- 5.1. 구현
- 5.2. 복잡도
6. 실제 환경에서의 확장
7. 랑데부 해싱(Rendezvous Hashing)과의 비교
8. 단조 키(Monotonic Key)
9. 한국 정보통신 환경과 활용 사례
10. 비판적 관점
참조

1. 개요

일관된 해싱은 분산 캐시 및 웹 애플리케이션에서 부분적인 시스템 장애의 영향을 줄이기 위해 1997년에 처음 소개된 기술이다. 이 기술은 서버의 추가 또는 제거 시 데이터 재분배를 최소화하여 시스템의 확장성과 안정성을 향상시킨다. 일관된 해싱은 데이터를 해시 링에 매핑하고, 각 서버를 링의 여러 지점에 배치하여 데이터의 위치를 결정한다. 서버 장애 시에는 해당 서버의 데이터만 다른 서버로 재할당되며, 새로운 서버가 추가될 때는 해당 서버에 매핑되는 데이터만 조정된다. 랑데부 해싱, 단조 키를 사용한 해시 테이블 등과 비교되며, Couchbase, OpenStack Swift, Amazon DynamoDB, Akamai Technologies 등 다양한 시스템에서 활용되고 있다.

2. 역사

"일관된 해싱"이라는 용어는 1997년 MIT의 데이비드 카거 등이 웹의 분산 캐시에 사용하기 위해 처음 소개하였다.^[2] 1997년 컴퓨팅 이론 심포지엄에서 발표된 이 학술 논문은 웹 서버의 변화하는 집단 간에 요청을 분산하는 방법으로 "일관된 해싱"이라는 용어를 소개했다.^[7] 각 슬롯은 분산 시스템 또는 클러스터의 서버로 표현되며, 서버 추가 및 제거(확장성 또는 중단 시) 시 슬롯(즉, 서버) 수가 변경될 때 $num\_keys/num\_slots$ 개의 항목만 재분배하면 된다. 저자들은 선형 해싱과 순차적인 서버 추가 및 제거를 처리하는 능력을 언급하는 한편, 일관된 해싱은 서버를 임의의 순서로 추가하고 제거할 수 있도록 한다.^[2] 이 논문은 나중에 P2P 네트워크와 같은 분산 해시 테이블(DHT)에서 파일을 추적하는 기술적 과제를 해결하기 위해 재사용되었다.^[3]

테라데이터는 이 기술을 1986년에 출시된 분산 데이터베이스에 사용했지만 이 용어를 사용하지는 않았다. 테라데이터는 여전히 정확히 이 목적을 달성하기 위해 해시 테이블의 개념을 사용한다. 아카마이 테크놀로지스는 "일관된 해싱"이라는 용어를 만든 논문의 공동 저자인 다니엘 레빈과 F. 톰슨 레이턴에 의해 1998년에 설립되었다. 아카마이의 콘텐츠 전송 네트워크에서^[4] 일관된 해싱은 서버 클러스터 내에서 부하를 분산하는 데 사용되는 반면, 안정적 결혼 문제 알고리즘은 클러스터 간에 부하를 분산하는 데 사용된다.^[5]

일관된 해싱은 대규모 웹 애플리케이션에서 부분적인 시스템 장애의 영향을 줄여 장애 발생 시 시스템 전체의 여파 없이 강력한 캐싱을 제공하는 데에도 사용되었다.^[6] 일관된 해싱은 또한 키 공간을 분산된 노드 집합에 분할하고 키별로 효율적인 노드 검색을 제공하는 연결된 노드의 오버레이 네트워크를 구성하는 분산 해시 테이블(DHT)의 초석이기도 하다.

1996년에 설계된 랑데부 해싱은 더 간단하고 일반적인 기술이다. 이 기법은 매우 다른 최고 임의 가중치(HRW) 알고리즘을 사용하여 일관된 해싱의 목표를 달성한다.

이와 같은 개념은, 복수의 캐싱 HTTP 프록시를 웹 브라우저에서 최적으로 사용하기 위해 SHARP가 개발한 Super Proxy Script의 기술 속에서 1996년에 등장했다.^[22]

2. 1. 초기 개념

"일관된 해싱"이라는 용어는 1997년 MIT의 데이비드 카거 등이 웹의 분산 캐시에 사용하기 위해 처음 소개하였다.^[2] 컴퓨팅 이론 심포지엄에서 발표된 이 학술 논문은 웹 서버의 변화하는 집단 간에 요청을 분산하는 방법으로 "일관된 해싱"이라는 용어를 소개했다.^[2] 각 슬롯은 분산 시스템 또는 클러스터의 서버로 표현되며, 서버 추가 및 제거(확장성 또는 중단 시) 시 슬롯(즉, 서버) 수가 변경될 때

num\_keys/num\_slots

개의 항목만 재분배하면 된다.^[2]

이 개념은 1996년 SHARP가 개발한 Super Proxy Script 기술에서 복수의 캐싱 HTTP 프록시를 웹 브라우저에서 최적으로 사용하기 위해 등장했다.^[22]

테라데이터는 이 기술을 1986년에 출시된 분산 데이터베이스에 사용했지만 이 용어를 사용하지는 않았다. 아카마이 테크놀로지스는 "일관된 해싱"이라는 용어를 만든 논문의 공동 저자인 다니엘 레빈과 F. 톰슨 레이턴에 의해 1998년에 설립되었다. 아카마이의 콘텐츠 전송 네트워크에서^[4] 일관된 해싱은 서버 클러스터 내에서 부하를 분산하는 데 사용되는 반면, 안정적 결혼 문제 알고리즘은 클러스터 간에 부하를 분산하는 데 사용된다.^[5]

일관된 해싱은 대규모 웹 애플리케이션에서 부분적인 시스템 장애의 영향을 줄여 장애 발생 시 시스템 전체의 여파 없이 강력한 캐싱을 제공하는 데에도 사용되었다.^[6]^[23] 일관된 해싱은 또한 키 공간을 분산된 노드 집합에 분할하고 키별로 효율적인 노드 검색을 제공하는 연결된 노드의 오버레이 네트워크를 구성하는 분산 해시 테이블(DHT)의 초석이기도 하다.

1996년에 설계된 랑데부 해싱은 더 간단하고 일반적인 기술이다. 이 기법은 매우 다른 최고 임의 가중치(HRW) 알고리즘을 사용하여 일관된 해싱의 목표를 달성한다.

2. 2. 발전과 확장

"일관된 해싱"이라는 용어는 데이비드 카거 등 MIT에서 특히 웹의 분산 캐시에 사용하기 위해 처음 소개되었다.^[2] 1997년 컴퓨팅 이론 심포지엄에서 발표된 이 학술 논문은 웹 서버의 변화하는 집단 간에 요청을 분산하는 방법으로 "일관된 해싱"이라는 용어를 소개했다.^[2] 각 슬롯은 분산 시스템 또는 클러스터의 서버로 표현된다. 서버 추가 및 제거(확장성 또는 중단 시) 시 슬롯(즉, 서버) 수가 변경될 때

num\_keys/num\_slots

개의 항목만 재분배하면 된다. 저자들은 선형 해싱과 순차적인 서버 추가 및 제거를 처리하는 능력을 언급하는 한편, 일관된 해싱은 서버를 임의의 순서로 추가하고 제거할 수 있도록 한다.^[2] 이 논문은 나중에 P2P 네트워크와 같은 분산 해시 테이블(DHT)에서 파일을 추적하는 기술적 과제를 해결하기 위해 재사용되었다.^[3]

테라데이터는 이 기술을 1986년에 출시된 분산 데이터베이스에 사용했지만 이 용어를 사용하지는 않았다. 테라데이터는 여전히 정확히 이 목적을 달성하기 위해 해시 테이블의 개념을 사용한다. 아카마이 테크놀로지스는 "일관된 해싱"이라는 용어를 만든 논문의 공동 저자인 다니엘 레빈과 F. 톰슨 레이턴에 의해 1998년에 설립되었다. 아카마이의 콘텐츠 전송 네트워크에서^[4] 일관된 해싱은 서버 클러스터 내에서 부하를 분산하는 데 사용되는 반면, 안정적 결혼 문제 알고리즘은 클러스터 간에 부하를 분산하는 데 사용된다.^[5]

일관된 해싱은 대규모 웹 애플리케이션에서 부분적인 시스템 장애의 영향을 줄여 장애 발생 시 시스템 전체의 여파 없이 강력한 캐싱을 제공하는 데에도 사용되었다.^[6] 분산 해시 테이블(DHT)은 노드의 집합 사이에서 키 공간을 나누는 데 일관된 해싱을 사용하며, 또한 임의의 키를 담당하는 노드를 효율적으로 특정할 수 있도록 노드를 연결하는 오버레이 네트워크를 제공하고 있다.

1996년에 설계된 랑데부 해싱은 더 간단하고 일반적인 기술이다. 이 기법은 매우 다른 최고 임의 가중치(HRW) 알고리즘을 사용하여 일관된 해싱의 목표를 달성한다.

이와 같은 개념은, 복수의 캐싱 HTTP 프록시를 웹 브라우저에서 최적으로 사용하기 위해 SHARP가 개발한 Super Proxy Script의 기술 속에서 1996년에 등장했다.^[22]

3. 일관된 해싱의 필요성

일반적으로 n개의 캐싱 머신에 데이터를 분산하는 방법은 데이터(O)의 해시값을 n으로 나눈 나머지(모듈러 연산)를 이용하는 방식(hash(O) (mod n))이다. 그러나 이 방식은 캐싱 머신(서버)이 추가되거나 제거될 때 문제가 발생한다. n 값이 변하면 모든 데이터가 새로운 위치로 재배치되어야 하기 때문이다. 이는 기존 데이터가 있는 서버에 과부하를 일으켜 시스템 전체에 치명적인 영향을 줄 수 있다.
일관된 해싱은 이러한 문제를 해결하기 위해 등장했다. 일관된 해싱은 데이터가 가능한 한 동일한 캐싱 머신에 계속 저장되도록 한다. 즉, 캐싱 머신이 추가되면 새로운 머신은 다른 모든 머신으로부터 데이터를 공유받고, 제거될 때는 해당 머신의 데이터가 나머지 머신들에 분산된다.

일관된 해싱의 핵심은 각 캐시를 서로 다른 해시 값 구간과 연결하는 것이다. 이 구간의 경계는 각 캐시 식별자(identifier)의 해시를 계산하여 결정된다. 만약 캐시가 제거되면, 해당 캐시의 구간은 인접한 구간을 가진 다른 캐시에 의해 처리된다. 이때, 다른 캐시들은 영향을 받지 않고 그대로 유지된다.

만약 특정 버킷을 사용할 수 없게 되면, 해시 링(hash ring)에서 해당 버킷의 지점(point)이 제거된다. 그리고 그 버킷에 매핑되었던 모든 데이터 요청은 해시 링 상의 다음 지점으로 매핑된다. 각 버킷은 무작위로 분산된 여러 지점(가상 노드, vnode 또는 vbucket)과 연결되어 노드 제거 시 부하 불균형을 해결한다. 제거된 버킷의 데이터는 남아있는 버킷들로 재분산되지만, 다른 버킷에 매핑된 값은 그대로 유지되므로 이동할 필요가 없다.

4. 기본 원리 및 동작 방식

일관된 해싱은 모든 데이터를 해시 링의 각 지점에 매핑하는 데 기반을 둔다. 시스템은 각 서버(노드)를 해시 링 상의 여러 지점에 매핑한다.

데이터의 위치를 찾기 위해, 시스템은 해시 링 상에서 데이터 키의 위치를 찾은 후, 처음 만나는 버킷(서버)에 도달할 때까지 링을 순회한다. 각 버킷은 해당 버킷의 지점과 이전 버킷의 지점 사이에 있는 모든 리소스를 포함한다.

이 경우, 일관된 해싱을 사용하면 "BLOB"이 서버 139에 저장됩니다. BLOB는 시계 방향으로 원에 나타나는 다음 서버에 매핑되어 $\zeta \le \text{서버 ID}$ 인 서버에 도달할 때까지 매핑됩니다.

예를 들어, 부하 분산 문제에서 BLOB을 클러스터의

n

개 서버 중 하나에 할당해야 할 때, 표준 해시 함수를 사용하여 BLOB의 해시 값

\beta

를 계산할 수 있다. 서버 수(

n

)로 모듈러 연산을 수행하여(

\zeta = \beta\ \%\ n

) BLOB을 배치할 서버를 결정한다. BLOB은

\text{서버 ID}

가

\zeta

의 다음인 서버에 배치된다. 그러나 서버가 추가되거나 제거되면(

n

이 변경될 때) 모든 BLOB는 재해싱으로 인해 재할당되어야 하는데, 이는 비용이 많이 든다.

일관된 해싱은 이러한 문제를 피하기 위해 설계되었다. BLOB과 서버를 모두 단위 원(일반적으로

2\pi

라디안)에 매핑하는 해시 함수를 사용한다(예:

\zeta = \Phi\ \%\ 360

, 여기서

\Phi

는 BLOB 또는 서버의 식별자). 각 BLOB는 시계 방향으로 원에 나타나는 다음 서버에 할당된다. 이진 탐색 알고리즘 또는 선형 탐색을 사용하여 특정 BLOB를 배치할 서버를 찾을 수 있다.

서버가 추가되거나 제거될 때, 대부분의 BLOB는 이전 서버 할당을 유지한다.

n^{th}

서버를 추가하면

1/n

분수의 BLOB만 재배치된다. 클러스터 내 캐시 서버 간의 BLOB 이동 프로세스는 상황에 따라 다르다. 웹 페이지 캐시의 경우, 대부분의 구현에서 캐시된 BLOB가 충분히 작다고 가정하여 이동 또는 복사가 수행되지 않는다. 요청이 새로 추가된 캐시 서버에 도달하면 캐시 미스가 발생하고, BLOB는 향후 요청을 위해 로컬에 캐시된다.

분산 캐시로 사용하는 경우, 노드마다 수백 개의 슬롯을 준비한다. 이렇게 함으로써, 노드를 추가·삭제했을 때, 슬롯이 해시 테이블 전체에 분산되어 처리 부하가 분산된다.

4. 1. 해시 링(Hash Ring)

일관된 해싱은 데이터를 해시 링의 각 지점에 매핑하는 데 기반을 둔다. 시스템은 각 서버(노드)를 해시 링 상의 여러 지점에 매핑한다.

데이터의 위치를 찾기 위해, 시스템은 해시 링 상에서 데이터 키의 위치를 찾은 후, 처음 만나는 버킷(서버)에 도달할 때까지 링을 순회한다. 각 버킷은 해당 버킷의 지점과 이전 버킷의 지점 사이에 있는 모든 리소스를 포함한다.

예를 들어, 부하 분산 문제에서 BLOB을 클러스터의

n

개 서버 중 하나에 할당해야 할 때, 표준 해시 함수를 사용하여 BLOB의 해시 값

\beta

를 계산할 수 있다. 서버 수(

n

)로 모듈러 연산을 수행하여(

\zeta = \beta\ \%\ n

) BLOB을 배치할 서버를 결정한다. BLOB은

\text{서버 ID}

가

\zeta

의 다음인 서버에 배치된다. 그러나 서버가 추가되거나 제거되면(

n

이 변경될 때) 모든 BLOB는 재해싱으로 인해 재할당되어야 하는데, 이는 비용이 많이 든다.

일관된 해싱은 이러한 문제를 피하기 위해 설계되었다. BLOB과 서버를 모두 단위 원(일반적으로

2\pi

라디안)에 매핑하는 해시 함수를 사용한다(예:

\zeta = \Phi\ \%\ 360

, 여기서

\Phi

는 BLOB 또는 서버의 식별자). 각 BLOB는 시계 방향으로 원에 나타나는 다음 서버에 할당된다. 이진 탐색 알고리즘 또는 선형 탐색을 사용하여 특정 BLOB를 배치할 서버를 찾을 수 있다.

서버가 추가되거나 제거될 때, 대부분의 BLOB는 이전 서버 할당을 유지한다.

n^{th}

서버를 추가하면

1/n

분수의 BLOB만 재배치된다. 클러스터 내 캐시 서버 간의 BLOB 이동 프로세스는 상황에 따라 다르다. 웹 페이지 캐시의 경우, 대부분의 구현에서 캐시된 BLOB가 충분히 작다고 가정하여 이동 또는 복사가 수행되지 않는다. 요청이 새로 추가된 캐시 서버에 도달하면 캐시 미스가 발생하고, BLOB는 향후 요청을 위해 로컬에 캐시된다.

분산 캐시로 사용하는 경우, 노드마다 수백 개의 슬롯을 준비한다. 이렇게 함으로써, 노드를 추가·삭제했을 때, 슬롯이 해시 테이블 전체에 분산되어 처리 부하가 분산된다.

4. 2. 데이터 배치

일관된 해싱은 모든 데이터를 해시 링의 각 지점에 매핑하는 데 기반을 둔다. 시스템은 각각의 이용 가능한 머신을 해시 링의 무수한 랜덤하게 분산된 포인트에 매핑시킨다.

데이터의 위치를 찾기 위해, 시스템은 해시 링 상에서 데이터 키의 위치를 찾은 후, 처음으로 만나는 버킷에 도달할 때까지 해시 링을 돈다. 각 버킷은 그 버킷의 포인트와 이전 버킷의 포인트 사이에 존재하는 모든 리소스를 포함한다.

예를 들어, 부하 분산 문제에서, BLOB을 클러스터의

n

개 서버 중 하나에 할당해야 할 때, 표준 해시 함수를 사용하여 해당 BLOB에 대한 해시 값을 계산할 수 있다. 해시 결과 값이

\beta

라고 가정하면, 서버의 수(

n

)로 모듈러 연산을 수행하여 BLOB을 배치할 서버를 결정한다.

\zeta = \beta\ \%\ n

; 따라서 BLOB은 이 경우

\text{서버 ID}

가

\zeta

의 다음인 서버에 배치된다. 그러나 서버가 추가되거나 제거될 때(

n

이 변경될 때), 모든 서버의 모든 BLOB는 재해싱으로 인해 재할당되고 이동되어야 하지만, 이 작업은 비용이 많이 든다.

일관된 해싱은 클러스터 전체에서 서버가 추가되거나 제거될 때 모든 BLOB를 재할당해야 하는 문제를 피하도록 설계되었다. 핵심 아이디어는 BLOB과 서버를 모두 단위 원, 일반적으로

2\pi

라디안에 매핑하는 해시 함수를 사용하는 것이다. 예를 들어,

\zeta = \Phi\ \%\ 360

(여기서

\Phi

는 BLOB 또는 서버의 식별자, 예를 들어 IP 주소 또는 UUID)의 해시)이다. 그런 다음 각 BLOB는 시계 방향으로 원에 나타나는 다음 서버에 할당된다.

키의 해시값과 같거나 더 큰 값 중에서 가장 가까운 슬롯을 찾는다. 이분 탐색을 사용하면 빠르게 찾을 수 있다. 자신보다 큰 해시값을 가진 슬롯이 존재하지 않는 경우에는, 최소 해시값을 가진 슬롯을 사용한다. 해당 슬롯에 키의 추가, 삭제, 획득을 수행한다.

4. 3. 서버 추가/제거

일관된 해싱은 데이터를 해시 링의 각 지점에 매핑하는 방식으로 작동한다. 시스템은 사용 가능한 각 머신을 해시 링 상의 무작위로 분산된 여러 지점에 매핑한다.

데이터의 위치를 찾기 위해 시스템은 해시 링에서 데이터 키의 위치를 찾은 후, 처음 만나는 버킷에 도달할 때까지 링을 따라 이동한다. 각 버킷은 해당 버킷의 지점과 이전 버킷의 지점 사이에 있는 모든 리소스를 포함한다.

예를 들어, 부하 분산 문제에서 BLOB을 클러스터의

n

개 서버 중 하나에 할당해야 할 때, 표준 해시 함수를 사용하여 해당 BLOB에 대한 해시 값을 계산할 수 있다. 해시 결과 값이

\beta

라면, 서버 수(

n

)로 모듈러 연산을 수행하여 BLOB을 배치할 서버를 결정한다:

\zeta = \beta\ \%\ n

. 따라서 BLOB은

\text{서버 ID}

가

\zeta

의 다음인 서버에 배치된다. 그러나 서버가 추가되거나 제거될 때(

n

이 변경될 때) 모든 서버의 모든 BLOB는 재해싱으로 인해 재할당되고 이동되어야 하는데, 이는 비용이 많이 드는 작업이다.

일관된 해싱은 서버가 추가되거나 제거될 때 모든 BLOB를 재할당해야 하는 문제를 피하도록 설계되었다. BLOB과 서버를 모두 단위 원(일반적으로

2\pi

라디안)에 매핑하는 해시 함수를 사용한다. 예를 들어,

\zeta = \Phi\ \%\ 360

(여기서

\Phi

는 BLOB 또는 서버의 식별자, 예를 들어 IP 주소 또는 UUID)의 해시이다. 각 BLOB는 시계 방향으로 원에 나타나는 다음 서버에 할당된다. 이진 탐색 알고리즘 또는 선형 탐색을 사용하여 특정 BLOB를 배치할 "지점" 또는 서버를 찾는다. 시계 방향으로 반복하면서

\zeta\ \le\ \Psi

(여기서

\Psi

는 클러스터 내의 서버 값) 연산을 수행하여 BLOB을 배치할 서버를 찾는다. 이는 BLOB의 서버에 대한 균등한 분포를 제공한다.

서버가 실패하여 제거되면, 실패한 서버에 매핑된 BLOB만 시계 방향으로 다음 서버에 다시 할당하면 된다. 새 서버가 추가되면 단위 원에 추가되고, 해당 서버에 매핑된 BLOB만 다시 할당하면 된다.

서버가 추가되거나 제거될 때, 대부분의 BLOB는 이전 서버 할당을 유지하며,

n^{th}

서버를 추가하면

1/n

분수의 BLOB만 재배치된다. 클러스터 내 캐시 서버 간의 BLOB 이동 프로세스는 상황에 따라 다르다. 일반적으로 새로 추가된 캐시 서버는 자신의 "전임자"를 식별하고, 매핑이 이 서버에 속하는 (즉, 해시 값이 새 서버보다 작은) 모든 BLOB를 전임자로부터 이동시킨다. 웹 페이지 캐시의 경우, 대부분의 구현에서 캐시된 BLOB가 충분히 작다고 가정하여 이동 또는 복사가 수행되지 않는다. 요청이 새로 추가된 캐시 서버에 도달하면 캐시 미스가 발생하고 실제 웹 서버에 대한 요청이 이루어지며 BLOB는 향후 요청을 위해 로컬에 캐시된다. 이전에 사용된 캐시 서버의 중복 BLOB는 캐시 삭제 정책에 따라 제거된다.

새로운 버킷(슬롯)을 추가하면, 새 버킷과 그 옆의 버킷 사이의 모든 리소스는 새 버킷에 추가된다. 이 리소스들은 더 이상 이전의 버킷과 연관되지 않으며, 데이터 선택 메서드에 의해 이전의 버킷에서 찾아지지 않는다. 슬롯을 추가할 때는 자신보다 큰 해시 값 중 가장 가까운 슬롯에서 자신이 담당해야 할 키를 이동한다. 슬롯을 삭제할 때는 자신이 담당했던 키를 자신보다 큰 해시 값 중 가장 가까운 슬롯으로 이동한다.

4. 4. 가상 노드 (Virtual Node)

일관된 해싱은 모든 데이터를 해시 링의 각 지점에 매핑하는 데 기반을 둔다. 시스템은 각각의 이용 가능한 머신을 해시 링의 무수한, 랜덤하게 분산된 지점에 매핑시킨다.

데이터의 위치를 찾기 위해 시스템은 해시 링 상에서 데이터 키의 위치를 찾는다. 그 후 처음으로 만나는 버킷에 도달할 때까지 해시 링을 돈다. 각 버킷은 그 버킷의 지점과 이전 버킷의 지점 사이에 존재하는 모든 리소스를 포함한다.

버킷을 추가할 때도 비슷한 과정이 일어난다. 버킷을 추가하면서 그 버킷과 그 옆의 버킷 사이의 모든 리소스는 새로운 버킷에 추가된다. 이 리소스들은 더 이상 이전의 버킷과 연관되지 않으며, 데이터 선택 메서드에 의해 이전의 버킷에서 찾아지지 않는다.

각 버킷과 연관된 키의 부분들은 버킷이 매핑된 각들의 개수가 변함에 따라 바뀔 수 있다. 여러 노드가 반경 내에 왜곡되는 것을 피하기 위해, 클러스터 내 서버의 균등 분포 부족으로 인해 여러 레이블이 사용된다. 이러한 중복 레이블을 "가상 노드"라고 하며, 클러스터 내의 단일 "실제" 레이블 또는 서버를 가리키는 여러 레이블이다. 클러스터 내 특정 서버에 사용되는 가상 노드 또는 중복 레이블의 양을 해당 서버의 "가중치"라고 한다.

5. 기술적 특징

5. 1. 구현

BLOB 및 서버 고유 식별자에 사용되는 해시 함수는 각각 $h_{b}(x)$, $h_{s}(x)$로 정의된다. 클러스터 내 서버 ID는 이진 탐색 트리(BST)를 사용하여 동적으로 유지되며, BST 내에서 후임자 또는 최솟값을 찾기 위해 트리 순회가 사용된다.

클러스터에 $x$ 삽입: BLOB의 해시 값 $\beta$는 $h_{b}(x)=\beta\ \%\ 360$ ($x \in \mathrm{BLOB}$)이며, $h_{b}(x)=\zeta$이다. $x$를 삽입하기 위해 서버 ID의 BST에서 $\zeta$의 후임자를 찾는다. $\zeta$가 모든 서버 ID보다 크면, BLOB는 가장 작은 서버 ID 값을 가진 서버에 배치된다.

클러스터에서 $x$ 삭제: BST에서 $\zeta$의 후임자를 찾아, 반환된 서버 ID에서 BLOB를 제거한다. $\zeta$에 후임자가 없으면, 가장 작은 서버 ID에서 BLOB를 제거한다.

클러스터에 서버 삽입: 서버 식별자의 해시 값 $\Phi$는 $h_{s}(x)=\Phi\ \%\ 360$ ($x \in \{\text{IP 주소, UUID}\}$)이며, $h_{s}(x)=\theta$이다. 해시 값이 $\theta$보다 작은 모든 BLOB를 $\theta$의 후임자인 서버 ID를 가진 서버에서 이동한다. $\theta$가 모든 서버 ID 중에서 가장 크면, 관련 BLOB를 가장 작은 서버 ID에서 $\theta$로 이동한다.

클러스터에서 서버 삭제: BST에서 $\theta$의 후임자를 찾아, BLOB를 $\theta$에서 후임자 서버로 이동한다. $\theta$에 후임자가 없으면, BLOB를 가장 작은 서버 ID로 이동한다.

키의 해시값과 같거나 더 큰 값 중에서 가장 가까운 슬롯을 찾는다. 이분 탐색을 사용하면 빠르게 찾을 수 있다. 자신보다 큰 해시값을 가진 슬롯이 존재하지 않는 경우에는 최소 해시값을 가진 슬롯을 사용한다. 해당 슬롯에 키의 추가, 삭제, 획득을 수행한다.

5. 2. 복잡도

''N''개의 노드(또는 슬롯)와 ''K''개의 키에 대한 점근적 시간 복잡도
	일반적인 해시 테이블	일관된 해싱
노드 추가	O(K)	O(K/N + log N)
노드 제거	O(K)	O(K/N + log N)
키 조회	O(1)	O(log N)
키 추가	O(1)	O(log N)
키 제거	O(1)	O(log N)

''O(K/N)''은 키 재분배에 대한 평균 비용이며, 일관된 해싱에서 ''O(log N)'' 복잡성은 링에서 다음 노드를 찾기 위해 노드 각도 간의 이진 검색 알고리즘이 필요하기 때문이다.

6. 실제 환경에서의 확장

실제 로드 밸런싱에 일관된 해싱을 효과적으로 사용하기 위해서는 몇 가지 확장이 필요하다. 기본적인 방식에서는 서버에 장애가 발생하면 해당 서버의 모든 BLOB가 시계 방향으로 다음 서버에 재할당되어 해당 서버의 로드가 두 배로 증가할 수 있다. 이는 바람직하지 않을 수 있다.^[5]

서버 장애 시 BLOB의 더욱 균등한 재분배를 보장하기 위해 각 서버는 단위 원의 여러 위치에 해싱될 수 있다. 서버에 장애가 발생하면 단위 원의 각 복제본에 할당된 BLOB는 시계 방향으로 다른 서버에 다시 할당되어 BLOB를 더욱 균등하게 재분배한다. 단일 BLOB가 "핫"해져서 여러 서버에서 호스팅해야 하는 경우, BLOB는 시계 방향으로 단위 원을 순회하여 여러 연속 서버에 할당될 수 있다.^[5]

두 개의 BLOB가 단위 원에서 서로 가깝게 해싱되고 동시에 "핫"해지는 경우 더 복잡한 실제 고려 사항이 발생한다. 이 경우 두 BLOB는 단위 원에서 동일한 연속 서버 집합을 사용한다. 이 상황은 각 BLOB가 서버를 단위 원에 매핑하기 위해 다른 해시 함수를 선택하여 개선할 수 있다.^[5]

7. 랑데부 해싱(Rendezvous Hashing)과의 비교

랑데부 해싱은 1996년에 설계된 기술로, 가능한 n개의 옵션 중 k개의 옵션 집합에 대한 분산 합의를 가능하게 한다. 일관된 해싱은 랑데부 해싱의 특수한 경우로 볼 수 있다. 랑데부 해싱은 단순성과 일반성 덕분에 여러 애플리케이션에서 일관된 해싱을 대체하여 사용되기도 한다.

만약 키 값이 항상 단조 증가하는 경우에는 단조 키를 가진 해시 테이블을 사용하는 것이 일관된 해싱보다 더 적합할 수 있다.

8. 단조 키(Monotonic Key)

키 값이 단조 증가하는 환경에서는 단조 키를 가진 해시 테이블을 사용하는 것이 일관된 해싱보다 더 적합할 수 있다. 만약 키 값의 증가가 단조 증가임을 미리 알고 있다면, 단조 키를 사용한 해시 테이블/Hash_table#Monotonic_keys^영어을 사용할 수도 있다.

9. 한국 정보통신 환경과 활용 사례

일관된 해싱은 분산 캐싱 및 웹 애플리케이션에서 발생 가능한 부분적 장애의 영향을 최소화하는 데 사용된다. 이는 시스템 전반의 장애 없이 강력한 캐시를 사용할 수 있도록 돕는다.

한국의 IT 환경에서 일관된 해싱은 대규모 사용자 트래픽을 처리하는 카카오, 네이버 등의 주요 서비스에서 활용될 가능성이 있다.

일관된 해싱의 활용 사례는 다음과 같다:

Couchbase 자동 데이터 분할^[7]
OpenStack의 객체 스토리지 서비스 Swift^[8]^[35]
Dynamo의 파티션 구성 요소^[9]^[36]^[37]
Apache Cassandra의 데이터 분할^[10]^[38]^[39]
ScyllaDB의 데이터 분할^[11]
Voldemort의 데이터 분할^[12]
Akka의 일관된 해싱 라우터^[13]^[40]
분산 키-값 데이터베이스인 Riak^[14]^[41]
네트워크 연결 스토리지 파일 시스템인 Gluster^[15]^[42]
Akamai 콘텐츠 전송 네트워크^[16]^[32]
Discord 채팅 애플리케이션^[17]^[33]
SpiceDB의 분산 캐시에 대한 gRPC 요청의 로드 밸런싱^[18]
Chord 알고리즘^[19]
MinIO 객체 스토리지 시스템^[20]
Skylable^영어,오픈 소스 배포 객체 저장 시스템^[43]
Maglev: A Fast and Reliable Software Network Load Balancer^[34]

10. 비판적 관점

참조

_[1] 서적 Designing Distributed Systems Patterns and Paradigms for Scalable, Reliable Services O'Reilly Media
_[2] conference Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web http://portal.acm.or[...] ACM Press New York, NY, USA
_[3] 간행물 Chord: a scalable peer-to-peer lookup protocol for Internet applications 2003-02
_[4] 간행물 The Akamai Network: A Platform for High-Performance Internet Applications https://www.akamai.c[...] 2023-08-29
_[5] 간행물 Algorithmic nuggets in content delivery http://www.sigcomm.o[...]
_[6] 간행물 Web Caching with Consistent Hashing http://www8.org/w8-p[...] 2008-02-05
_[7] 웹사이트 What Exactly Is Membase? https://blog.couchba[...] 2014-12-16
_[8] 웹사이트 Building a Consistent Hashing Ring https://docs.opensta[...] 2011-02
_[9] 간행물 Dynamo http://www.allthings[...] 2018-06-07
_[10] 간행물 Cassandra: a decentralized structured storage system
_[11] 웹사이트 NoSQL Comparison: MongoDB vs ScyllaDB https://benchant.com[...] 2024-03-21
_[12] 웹사이트 Design -- Voldemort http://www.project-v[...] 2015-02-09
_[13] 웹사이트 Akka Routing http://doc.akka.io/d[...] 2019-11-16
_[14] 웹사이트 Riak Concepts http://docs.basho.co[...] 2016-12-06
_[15] 웹사이트 GlusterFS Algorithms: Distribution http://www.gluster.o[...] 2012-03-01
_[16] 웹사이트 Modern Algorithmic Toolbox http://theory.stanfo[...] 2016-03-28
_[17] 웹사이트 How Discord Scaled Elixir to 5,000,000 Concurrent Users https://discord.com/[...] 2017-07-06
_[18] 웹사이트 Consistent Hash Load Balancing for gRPC https://authzed.com/[...] 2021-11-24
_[19] 간행물 Chord: a scalable peer-to-peer lookup protocol for Internet applications 2003-02-25
_[20] 웹사이트 MinIO Versioning, Metadata and Storage Deep Dive https://blog.min.io/[...] 2023-10-24
_[21] conference Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web http://portal.acm.or[...] ACM Press New York, NY, USA 2008-06-17
_[22] 웹사이트 Super Proxy Script - How to make distributed proxy servers by URL hashing http://www.pacfiles.[...] 2011-08-04
_[23] 간행물 Web Caching with Consistent Hashing http://www8.org/w8-p[...] 2008-06-17
_[24] url http://docs.openstac[...]
_[25] 간행물 Dynamo: Amazon's Highly Available Key-Value Store http://www.allthings[...] 2018-06-07
_[26] 간행물 Cassandra: a decentralized structured storage system
_[27] 웹사이트 Design -- Voldemort http://www.project-v[...] 2015-02-09
_[28] Akka Routing Akka Routing http://doc.akka.io/d[...]
_[29] 웹사이트 Riak Concepts http://docs.basho.co[...] 2014-05-05
_[30] url http://www.gluster.o[...]
_[31] 웹사이트 Skylable architecture http://wiki.skylable[...] 2014-06-21
_[32] 웹사이트 Modern Algorithmic Toolbox http://theory.stanfo[...] 2016-11-08
_[33] 웹사이트 How Discord Scaled Elixir to 5,000,000 Concurrent Users https://blog.discord[...] 2017-07-12
_[34] 웹사이트 Maglev: A Fast and Reliable Software Network Load Balancer https://static.googl[...] 2017-07-30
_[35] url http://docs.openstac[...]
_[36] 저널 Dynamo: Amazon's Highly Available Key-Value Store
_[37] URL http://www.allthings[...]
_[38] 저널 Cassandra: a decentralized structured storage system
_[39] 웹인용 Design -- Voldemort http://www.project-v[...] 2015-02-09
_[40] Akka Akka Routing http://doc.akka.io/d[...]
_[41] 웹인용 Riak Concepts https://web.archive.[...] 2015-12-13
_[42] URL http://www.gluster.o[...]
_[43] 웹인용 Skylable architecture https://web.archive.[...] 2014-06-21

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com