일관된 해싱

컴퓨터 과학에서 일관성 있는 해싱은^[1][2] 해시 테이블의 크기를 조정할 때 $평균적$으로 n${\displaystyle /m}$ ${\displaystyle$ n$/m}$ 키만$$ 재전송하면 되는 특수한 종류의 해싱 기법이다. 여기서 $n{\displaystyle }$ ${\displaystyle n}$은 키 수이고 m$${\$displaystym$m}은$$ 슬롯 수입니다. 대조적으로, 대부분의 전통적인 해시 테이블에서는, 키와 슬롯 사이의 매핑이 모듈 연산에 의해 정의되기 때문에 어레이 슬롯의 수가 변경되면 거의 모든 키가 다시 연결된다.

역사

"일치 해싱"이라는 용어는 MIT의 David Karger 등이 분산 캐싱, 특히 웹에 사용하기 위해 도입했다.^[3] 1997년부터 시작된 컴퓨팅 이론 심포지엄에서 본 학술 논문은 변화하는 웹 서버 인구 사이에 요청을 분산시키는 방법으로 "일관된 해싱"이라는 용어를 도입했다.^[4] 그런 다음 각 슬롯은 분산 시스템 또는 클러스터의 서버로 표시된다. 서버를 추가하고 서버를 제거(확장성 또는 중단 중)하려면 슬롯 수(예: 서버)가 ${\displaystyle \mathrm{변경}}$될 때 ${\displaystyle n}$ u m ${\displaystyle \mathrm{\_}}$ ${\displaystyle k}$ ${\displaystyle e}$ ${\displaystyle ys}$ / n ${\displaystyle u}$ m ${\displaystyle \mathrm{\_}}$ s$$ l ${\displaystyle t}$ o s {\$displaystyle num\_keys/num\_slots}$ 항목만$$ 재분할 필요가 있다. 저자들은 선형 해싱과 순차적 서버 추가 및 제거 처리 능력에 대해 언급하는 한편, 일관된 해싱은 임의의 순서로 서버를 추가 및 제거할 수 있다. ^[1] 이 논문은 나중에 분산 해시 테이블과 같은 피어투피어 네트워크에서 파일을 추적하는 기술적 문제를 다루기 위해 다시 구매되었다.^[5][6]

Teradata는 이 용어를 사용하지 않았지만 1986년에 발표된 분산형 데이터베이스에 이 기술을 사용했다. Teradata는 여전히 해시 테이블의 개념을 사용하여 정확히 이 목적을 달성한다. 아카마이 테크놀로지는 1998년 과학자인 다니엘 르윈과 F에 의해 설립되었다. Thomson Leighton(공저자)은 "일관된 해싱"을 코칭하는 글의 공동저자. 아카마이의 컨텐츠 전달 네트워크에서는,^[7] 일관된 해싱이 서버 클러스터 내의 부하를 분산시키기 위해 사용되고, 클러스터 간 부하를 분산시키기 위해 안정적인 결혼 알고리즘이 사용된다.^[2]

또한 대형 웹 애플리케이션에서 부분적인 시스템 장애의 영향을 감소시켜 시스템 전체에 걸친 장애 여파를 초래하지 않고 강력한 캐싱을 제공하는 데 일관된 해싱이 사용되어 왔다.^[8] 일관성 있는 해싱은 분산 해시 테이블(DHT)의 초석이기도 하며, 해시 값을 사용하여 분산 노드 집합에 걸쳐 키 공간을 분할한 다음 키로 효율적인 노드 검색을 제공하는 연결된 노드의 오버레이 네트워크를 구축한다. 1996년에 고안된 랑데부 해싱은 보다 단순하고 일반적인 기술이다^{[citation needed]}. 그것은 매우 다른 최고 무작위 중량(HRW) 알고리즘을 사용하여 일관된 해싱의 목표를 달성한다.

기본 기법

예를 들어, 로드 밸런싱의 $문제$에서,$$BLOB 개체를 클러스터의$$ n {\$displaystyle n}$ 서버 중 하나에 할당해야 하는 경우, 해시의 결과 값이 $\beta {\displaystyle }$ ${\displaystyle \beta$$}$이라고 가정할 때, 우리는 모듈식 연산자를 수행한다.on with the number of servers (${\displaystyle n}$ in this case) to determine the server in which we can place the BLOB: ${\displaystyle \zeta =\beta \ \%\ n}$; hence the BLOB will be placed in the server whose ${\displaystyle {\text{server ID}}}$ is successor of ${\displaystyle \zeta }$ in this 단, 정전이나 확장(n{\displaystyn}변경 시)시 서버를 추가 또는 제거할 경우(n{\displaystyn n}), 모든 서버의 BLOB를 재할당하여 이동해야 하지만,많이 든다 비용이가 작업은.

일관성 있는 해싱은 클러스터 전체에 서버를 추가하거나 제거할 때 모든 BLOB를 재할당해야 하는 문제를 방지하기 위해 설계되었다. 중심 아이디어는 BLOB와 서버를 임의로 단위 원에 매핑하는 해시함수를 사용하는데, 보통 2 ${\displaystyle \pi }$ ${\displaystyle 2\pi }$ 라디안이다$$. 예를 들어 $\zeta {\displaystyle }$= ${\displaystyle \mathrm{\phi }\mathrm{}}$% ${\displaystyle 360}$ ${\displaystyle \zeta =\Phi \%\$ 360$}(여기$서$where{\displaystyle \mathrm{}}$ {\$displaystyle \Phi$}은$($는) BLOB 또는 서버 식별자의 해시(예$$: IP 주소 또는 UUID)이다.$$ 그런 다음 각 BLOB는 시계 방향으로 원에 나타나는 다음 서버에 할당된다. Usually, binary search algorithm or linear search is used to find a "spot" or server to place that particular BLOB in ${\displaystyle O(\log N)}$ or ${\displaystyle O(N)}$ complexities respectively; and in every iteration, which happens in clockwise manner, an operation ${\displaystyle \zeta \ \leq$$\Psi$}($$$여기$서 $\displaystyle \Psi }$은(는) 클러스터 내의 서버의 값)을 사용하여 BLOB를 배치할 서버를 찾으십시오. 이것은 서버에 BLOB의 균일한 분배를 제공한다. 그러나, 더 중요한 것은, 서버가 실패하여 서클에서 제거되면, 실패한 서버에 매핑된 BLOB만 시계 방향으로 다음 서버에 재할당하면 된다. 마찬가지로, 새로운 서버가 추가되면 유닛 서클에 추가되며, 해당 서버에 매핑된 BLOB만 재할당하면 된다.

중요한 것은 서버를 추가하거나 제거할 때 대부분의 BLOB는 이전 서버 할당을 유지하며, $n{\displaystyle {}^{}}$ t ${\displaystyle h^{}}$ ${\$ 서버를$$ 추가하면${\displaystyle }$BLOB의 1/${\displaystyle n}$ ${\displaystyle 1/n}$ 부분만$$ 재배치된다. 클러스터 내의 캐시 서버 간에 BLOB를 이동하는 과정은 컨텍스트에 따라 달라지지만, 일반적으로 새로 추가된 캐시 서버는 그것의 "successor"를 식별하고 매핑이 이 서버(즉, 해시 값이 새 서버의 그것보다 적은)에 속하는 모든 BLOB를 그것으로부터 이동시킨다. 그러나 웹 페이지 캐시의 경우, 캐시된 BLOB가 충분히 작다고 가정할 때 대부분의 구현에서는 이동이나 복사에 관여하지 않는다. 새로 추가된 캐시 서버에 요청이 들어오면 캐시 누락이 발생하고 실제 웹 서버에 대한 요청이 이루어지고 향후 요청을 위해 BLOB가 로컬로 캐시된다. 이전에 사용한 캐시 서버의 중복 BLOB는 캐시 제거 정책에 따라 제거된다.^[9]

실행

$h{\displaystyle {}_{}}$ ${\displaystyle b_{}}$( ${\displaystyle x}$) ${\displaystyle h_{b}(x)}$ 및$$ ${\displaystyle h_{}}$( ${\displaystyle x}$) ${\displaystyle h_{s}(x)$를 각각 BLOB와 서버의 고유 식별자에 사용되는 해시 함수로 한다$$. 실제로, 이진 검색 트리(BST)는 ${\displaystyle \text{클러스터}}$나 해시링 $내$에서 서버 ID ${\displaystyle {\$text{server $ID}}$을(를) 동적으로 유지하고, BST 내에서 후속 또는 최소값을 찾기 위해 트리 트래버설이 사용된다.

$클러스터$에 x ${\displaystyle x}$ 삽입

Let ${\displaystyle \beta }$ be the hash value of a BLOB such that, ${\displaystyle h_{b}(x)=\beta \ \%\ 360}$ where ${\displaystyle x\in \mathrm {BLOB} }$ and ${\displaystyle h_{b}(x)=\zeta }$. To insert ${\displaystyle x}$, find the successor of ${\displaystyle \zeta }$${\displaystyle \text{서버 ID}}$ ${\$의 BST에 있는$$ ${\displaystyle \zeta }.$ $▼{\displaystyle \zeta }}$이($가{\displaystyle }$) ${\displaystyle \text{모든 서버}}$ ID$${\$displaystyle${\$text{server$ ID$}}$보다 큰 경우, BLOB는 가장 ${\displaystyle \text{작은 서버}}$ ID$${\$displaystyle${\$text{server$ ID$} 값$을 가진 서버에$$ 배치된다.

$클러스터$에서 x ${\displaystyle x}$ 삭제

BST에서$$ ${\displaystyle \zeta}$의 후속 버전을 찾고, 반환된 ${\displaystyle \text{서버 ID}}$ ${\$$server$ ID$}}$에서 BLOB를 $제거$하십시오$.$$${\$displaystyle \zeta}}$에 후속 프로그램이 없는 경우, 서버 ${\displaystyle \text{ID}}${\$displaystystyle {\type{server$ ID$}$}s}s}s}s}^[10]s}s.

클러스터에 서버 삽입

${\displaystyle h_{}}$ ${\displaystyle \Phi }$을(를) 서버 식별자의 해시 값으로 설정$$(${\displaystyle 예}$: h${\displaystyle {}_{}}$s${\displaystyle }$(${\displaystyle }$x ) = ${\displaystyle 360\mathrm{}}$% 360$${\$displaystyle h_{s$}(x$)=).$$\Phi$\$\%\ 360}$ $여기$서 x ${\displaystyle \in }${ ${\displaystyle \text{IP 주소, UUID}}$ ${\displaystyle \}}$ ${\displaystyle$ x$\in \{\text}$$IP address, UUID}}\}}$ and ${\displaystyle h_{s}(x)=\theta }$. Move all the BLOBs, whose hash value is smaller than ${\displaystyle \theta }$, from the server whose ${\displaystyle {\text{server ID}}}$ is successor of ${\displaystyle \theta }$. If ${\displaystyle \theta }$ is larges${\displaystyle \text{모든}}$ ${\displaystyle \text{서버}}$ ${\displaystyle \text{ID}}$ ${\$ 중 가장 작은 서버 ID ${\$ ID$}}$에서 $관련$ BLOB를 ${\displaystyle$\teta$}s$로 이동하십시오$.$^[11]

클러스터에서 서버 삭제

BST에서$$ $\theta {\displaystyle }$ ${\displaystyle \theta}$의 후속 버전을 찾고, $\theta {\displaystyle }$ ${\displaystyle \thea}$의 BLOB를 후속 서버로 이동하십시오$$. $\theta {\displaystyle }$ ${\displaystyle \theta}$에 후속 항목이 없는$$ 경우 BLOB를 ${\displaystyle \text{서버 ID}}${\$displaystyle${\$text{server$ ID$}$ $중$ 가장 작은 값으로 이동하십시오.^[12]

환원분산

클러스터 내 서버 분포에서 랜덤성이 부족하여 발생하는 라디안 내 여러 노드의 왜곡을 방지하기 위해 여러 개의 레이블을 사용한다. 이러한 중복 레이블을 "가상 노드"라고 하며, 즉 클러스터 내의 단일 "실제" 레이블 또는 서버를 가리키는 다중 레이블을 가리킨다. 클러스터 내의 특정 서버에 사용되는 가상 노드 또는 중복 레이블의 양을 특정 서버의 "중량"이라고 한다.^[13]

실용적인 확장

실제 부하 분산을 위해 일관된 해싱을 효과적으로 사용하기 위해서는 기본 기법에 대한 많은 확장이 필요하다. 위의 기본 체계에서, 서버에 장애가 발생할 경우, 모든 BLOB가 시계 방향으로 다음 서버에 재할당되어, 잠재적으로 그 서버의 부하가 두 배가 될 수 있다. 이것은 바람직하지 않을 수도 있다. 서버 장애 시 BLOB의 보다 고른 재분배를 보장하기 위해, 각 서버는 유닛 서클의 여러 위치에 해시될 수 있다. 서버가 실패하면 단위 서클의 각 복제본에 할당된 BLOB는 시계 방향으로 다른 서버에 재할당되므로 BLOB를 보다 균등하게 재분배한다. 또 다른 확장자는 단일 BLOB가 "핫"되어 다수의 서버에 접속되어 호스트되어야 하는 상황에 관한 것이다. 이러한 상황에서 BLOB는 시계방향으로 단위 원을 통과하여 여러 연속 서버에 할당될 수 있다. 보다 복잡한 실무적 고려사항은 두 개의 BLOB가 유닛 서클에서 서로 가까이 해시되고 동시에 두 개 모두 "핫"될 때 발생한다. 이 경우, 두 BLOB는 유닛 서클에서 동일한 연속 서버 집합을 사용할 것이다. 이러한 상황은 각 BLOB가 유닛 서클에 서버를 매핑하기 위해 다른 해시 함수를 선택함으로써 개선될 수 있다.^[2]

랑데부 해싱 및 기타 대안과의 비교

1996년에 설계된 랑데부 해싱은 보다 단순하고 일반적인 기법이며, 가능한 $n{\displaystyle }$ ${\displaystyle$ n$}$ 옵션$$ 집합에서 $k{\displaystyle }$ ${\displaystyle$ $k$$}$ 옵션$$ 집합에 대해 완전히 분산된 합의를 허용한다. 사실 일관된 해싱은 랑데부 해싱의 특별한 경우라는 것을 보여줄 수 있다. 단순성과 일반성 때문에, 랑데부 해싱은 현재 많은 애플리케이션에서 Consistent Hashing 대신 사용되고 있다.

키 값이 항상 단조롭게 증가한다면, 일관된 해싱보다 단조로운 키가 있는 해시 테이블을 사용하는 대체 접근법이 더 적합할 수 있다.^{[citation needed]}

복잡성

$N{\displaystyle }$ ${\displaystyle N}$ 노드$$(또는 슬롯) 및 $K{\displaystyle }$ ${\displaystyle K}$ 키에$$ 대한 점근성 시간 복잡성

	클래식 해시 테이블	일관된 해싱
노드를 추가하다.	$O(K)}$	${\displaystyle O(K/N+\log N)}$
노드를 제거하다	$O(K)}$	${\displaystyle O(K/N+\log N)}$
열쇠를 넣다	${\displaystyle O(1)}$	${\displaystyle O(\log N)}$
열쇠를 빼다	${\displaystyle O(1)}$	${\displaystyle O(\log N)}$

$O{\displaystyle }$( ${\displaystyle K}$/ ${\displaystyle N}$) ${\displaystyle O(K/N)}$은 키 재분배에 대한 평균 비용이며$$, 일관된 해싱을 $위한{\displaystyle }$ O${\displaystyle (\mathrm{로그}}$ $($ ${\displaystyle N}$ )$displaystyle$ O$(\log$ N$)}$의 복잡성은 링에서 다음 노드를 찾기 위해 노드 각도 간의 이진 검색이 필요하다는 사실에서 비롯된다.^{[citation needed]}

예

일관된 해싱 사용의 알려진 예는 다음과 같다.

• 카우치베이스 자동 데이터 파티셔닝
• OpenStack의 객체 스토리지 서비스 스위프트^[15]
• Amazon 스토리지 시스템 Dynamo의^[16] 파티션 구성 요소
• Apache Cassandra에서^[17] 데이터 파티셔닝
• 볼드모트의^[18] 데이터 파티셔닝
• Akka의 일관된 해싱 라우터^[19]
• 분산^[20] 키 값 데이터베이스인 Riak
• 네트워크 연결 스토리지 파일 시스템인^[21] Gluster
• Akamai 컨텐츠 전송 네트워크^[22]
• 불협화음 응용^[23] 프로그램
• Maglev 네트워크 로드 밸런서^[24]
• Azure Cosmos DB에서의 데이터 파티셔닝

참조

• Roughgarden, Tim; Valiant, Gregory (28 March 2021). "The Modern Algorithmic Toolbox, Introduction to Consistent Hashing" (PDF). Stanford University. Archived (PDF) from the original on 25 July 2021. Retrieved 7 October 2021.
• Moitra, Ankur (10 February 2016). "Advanced Algorithms, 6.854" (PDF). Massachusetts Institute of Technology. Archived (PDF) from the original on 13 April 2021. Retrieved 8 October 2021.

외부 링크

• 일관된 해싱 이해
• 2009년 6월 3일 Michael Nielsen의 일관된 해싱
• 일관된 해싱, 대니 르윈, 아카마이 창조
• 점프 일관성 해싱: 빠른 최소 메모리, 일관된 해시 알고리즘
• 랑데부 해싱: 일관된 해싱의 대안
• 다양한 언어로 구현:
  • C
  • C++
  • C#
  • 얼랑
  • 가다
  • 자바
  • PHP
  • 루비
  • 파이톤
  • 파이톤 (Again)
  • 펄
  • 펄6