Chord

Chord(코드)는 컴퓨팅에서 peer-to-peer 분산 해시 테이블에 대한 프로토콜 및 알고리즘이다. 분산 해시 테이블은 ("노드"라고 알려진) 다른 컴퓨터에 키를 할당하여 키-값 쌍을 저장한다(한 노드는 그것이 담당하는 모든 키에 대한 값을 저장한다). Chord는 노드에 키가 할당되는 방법과 주어진 키에 해당하는 첫번째 노드를 찾아 해당 키에 대한 값을 해당 노드가 찾을 수 있는 방법을 정한다.
Chord는 CAN, Tapestry 그리고 Pastry와 함께, 4개의 원조 분산 해시 테이블 프로토콜 중 하나이다. 이 프로토콜은 Ion Stoica, Robert Morris, David  Karger, Frans Kaashoek, Hari Balakrishnan가 도입했으며, MIT에서 개발되었다.

개요

노드와 키는 비트 '식별자'를 'consistent(일관된) hashing'을 사용해 할당한다. SHA-1 알고리즘은 consistent hashing을 위한 기반 해싱 함수이다. Consistent hashing은 Chord의 견고함과 성능을 위해 필수적인데, 이는 키와 노드 모두(사실 그들의 IP 주소)가 동일한 식별 공간 내에 무시할 만한 충돌 가능성과 함께 균일하게 분산되기 때문이다. 따라서, 분열 없이 노드를 네트워크에 참가시키거나 내보내는 것이 가능하다. 해당 프로토콜 내에서, '노드'라는 용어는 모호할 것 없이 노드 자체와 그것의 식별자(ID) 모두를 참조한다. '키'라는 용어도 마찬가지이다.
Chord 탐색 프로토콜을 사용하면, 노드와 키는 에서 까지의 범위를 가지는  노드들의 식별 서클 (Identifier circle) 내에서 할당된다(여기서 은 충돌을 피할 수 있을 만큼 충분히 커야 한다). 이러한 노드들 중 일부는 머신 또는 키에 매핑되는 반면 다른 것들(대부분)은 비어 있다.
각 노드는 '다음 노드(successor)'와 '이전 노드(predecessor)'를 가지고 있다. 한 노드의 이전 노드는 식별 서클 내에서 시계 방향으로 있는 다음 노드이다. 다음 노드는 시계 반대 방향에 있다. 잠재적인 ID 각각에 대해 하나의 노드가 있는 경우 노드 0의 다음 노드는 노드 1이며, 노드 0의 이전 노드는 노드 그러나 보통 시퀀스 내에는 "구멍"이 있다. 예를 들어, 노드 153의 다음 노드는 노드 167일 수 있다(그리고 노드 154에서 166은 존재하지 않다). 이 경우에 노드 167의 이전 노드는 노드 153이다.
다음 노드에 대한 개념은 키의 경우에도 사용될 수 있다. 키  의 다음 노드는 아이디가  와 같거나 식별 서클 내에서  다음에 오는 첫번째 노드로,  로 표시한다. 모든 키는 그것의 다음 노드에 할당되므로, 키  를 탐색하는 것은  를 조회하는 것이다.
한 노드의 다음 노드(혹은 이전 노드)가 (오류나 이탈로 인해) 네트워크에서 사라질 수도 있기 때문에, 각 노드는 서클 내에서 자신과 인접한 전체 세그먼트(즉, 해당 노드 앞에  노드가 있고   노드 다음에는 해당 노드가 있다)를 기록한다. 이 리스트는 문제의 네트워크가 높은 오류율을 겪고 있더라도, 자신의 다음 노드 혹은 이전 노드를 정확하게 찾을 가능성이 높다.

기본 쿼리

Chord 프로토콜의 핵심 용도는 클라이언트(일반적으로 노드일수도 있다)에서 키를 조회, 즉 . 기본적인 해결책은 근처에서 키를 찾지 못한 경우, 노드의 다음 노드에 쿼리를 전달하는 것이다. 이는  조회 시간을 따르는데, 여기서  은 링 내 머신의 개수이다.

핑거 테이블

위에서 선형 검색을 피하기 위해, Chord는 각 노드가  개의 엔트리를 포함하는 핑거 테이블을 유미하도록 함으로써 더 빠른 검색 메서드를 구현한다. 여기서,  은 해시키에 있는 비트수이다. 노드  의  엔트리는 를 포함한다. 핑거 테이블의 첫번째 엔트리는 실제로 노드에 인접한 다음 노드이다 (그러므로 다음 노드에 대한 여분의 필드를 필요로 하지 않다). 노드가 키  를 탐색하려고 할 때마다, 핑거 테이블(ID가  보다 더 작은 서클 상에서 "가장 큰" 것) 내 에서  의 가장 가까운 다음 노드 또는 이전 노드에 쿼리를 전달한다.
그런 핑거 테이블을 사용해, N-노드 네트워크 내에서 다음 노드를 찾기 위해 반드시 접촉되어야 하는 노드의 개수는  이다. (아래에서 증명한다)

안정화

정확한 탐색을 보장하기 위해, 모든 다음 노드를은 항상 최신으로 유지되어야 한다. => 백그라운드에서 주기적으로 실행되는 안정화 프로토콜. 핑거 테이블과 다음 노드 포인터의 갱신. 안정화 프로토콜: Stabilize(): n은 자신의 다음 노드에게 이전 노드 p에 대해 묻고 대신해서 p가 이전 노드가 되어야 하는지 결정한다(이는 p가 최근에 시스템에 들어온 경우를 말한다. Notify():  의 존재를 다음 노드에게 알려줘서, 그것의 이전 노드를  으로 변경할 수 있다. Fix_fingers(): 핑거 테이블을 갱신한다.

증명 스케치

'높은 개연성을 가지고, Chord는 ' '개의 노드에 접근해-노드 네트워크 내에서 다음 노드를 찾는다.'
노드  이 키  에 대한 다음 노드를 찾으려고 한다고 가정해보겠다.  가  의 이전 노드라고 해보자. 메시지를  에서  로 라우팅하는데 몇 단계가 걸리는지, 그 상한선을 찾고자 한다. 노드  은 핑거 테이블을 검사하여 그것이 가진  의 가장 인접한 이전 노드에게 요청을 라우팅한다. 이 노드를  라고 해보자. 만약  가  의 핑거 테이블의  번째 엔트리라면,  와  는  으로부터  와  사이의 거리에 있다. 따라서, 이 서클을 따른  와  사이의 거리는 최대  이다. 따라서,  에서  까지의 거리는  에서  까지의 거리보다 더 작다.  까지의 새로운 거리는 초기 거리의 절반 이하이다.
남은 거리를 반으로 나누는 이 과정이 반복되므로,  단계 이후에,  까지의 남은 거리는 최대  가 된다. 특히,  단계 이후에, 남은 거리는 최대  가 된다. 노드가 무작위로 식별 서클을 따라 고르게 분산되기 때문에, 이 길이 구간에 속하는 예상 노드의 수는 1이며, 그런 노드가  개 보다 더 적게 있을 확률이 높다. 메시지가 항상 적어도 하나 이상의 노드에 의해 진행되기 때문에, 남은 거리를 탐색하는 메시지의 경우  단계가 소요된다. 그래서 총 예상 라우팅 시간은 이 된다.
Chord가  개의 이전 노드 및 다음 노드에 대한 트래킹을 유지할 경우, 또 각 노드가 실패할 확률이 1/4인 경우, find_successor (아래 참고)와 find_predecessor (see below)가 정확한 노드를 반환할 확률이 높다.
단순히, 모든  노드가 실패할 확률은  이며, 이는 낮은 확률이다. 그러므로 그들 중 한 개는 살아있고 노드는 정확한 포인터를 가질 가능성이 높다.