Chord

컴퓨팅에서 Chord(코드)는 peer-to-peer 분산 해시 테이블에 대한 프로토콜 및 알고리즘이다. 분산 해시 테이블은 다른 컴퓨터(노드)에 키를 할당하여 키-값 쌍을 저장한다 (노드는 그것이 담당하는 모든 키에 대한 값을 저장한다). Chord는 노드에 키가 할당되는 방법과 주어진 키에 해당하는 첫번째 노드를 찾아 해당 키에 대한 값을 해당 노드가 찾을 수 있는 방법을 정한다.
Chord는 CAN, Tapestry 그리고 Pastry와 함께, 4개의 원조 분산 해시 테이블 프로토콜 중 하나이다. 이 프로토콜은 Ion Stoica, Robert Morris, David  Karger, Frans Kaashoek, Hari Balakrishnan가 도입했으며, MIT에서 개발되었다.
개요.
노드와 키는 일관된 해싱을 통해 -비트 식별자를 할당 받는다. SHA-1 알고리즘은 일관된 해싱을 위한 기반 해싱 함수이다. 일관된 해싱은 Chord의 견고함과 성능을 위해 필수적인데, 이는 키와 노드(정확히는 노드의 IP 주소)가 동일한 식별 공간 내에 무시할 만한 충돌 가능성과 함께 균일하게 분산되기 때문이다. 따라서, 방해 없이 노드를 네트워크에 참가시키거나 내보내는 것이 가능하다. 해당 프로토콜 내에서, 노드라는 용어는 모호할 것 없이 노드 자체와 그것의 식별자(ID) 모두를 가리킨다. '키'라는 용어도 마찬가지이다.
Chord 탐색 프로토콜을 사용하면, 노드와 키는 formula_1에서 formula_2까지의 범위를 가지는 식별 서클 (Identifier circle) 내에 할당된다(여기서 formula_3은 충돌을 피할 수 있을 만큼 충분히 커야 한다). 이러한 노드 중 일부는 컴퓨터 나 키에 매핑되는 반면 다른 노드는 대부분 비어 있다.
각 노드는 '다음 노드(successor)'와 '이전 노드(predecessor)'를 가지고 있다. 다음 노드는 식별 서클 내에서 시계 방향에 있는 노드이다. 이전 노드는 시계 반대 방향에 있는 노드이다. 모든 ID 각각에 대해 하나의 노드가 있는 경우 노드 0의 다음 노드는 노드 1이며, 노드 0의 이전 노드는 노드 formula_2이다. 그러나 보통 시퀀스 내에는 "구멍"이 있다. 예를 들어, 노드 154부터 노드 166까지 존재하지 않으면 노드 153의 다음 노드는 노드 167가 되며 노드 167의 이전 노드는 노드 153가 된다.
다음 노드에 대한 개념은 키의 경우에도 사용될 수 있다. 키 formula_5 의 다음 노드는 아이디가 formula_5 와 같거나 식별 서클 내에서 formula_5 다음에 오는 첫번째 노드로, formula_8 로 표시한다. 모든 키는 그것의 다음 노드에 할당되므로, 키 formula_5 를 탐색하는 것은 formula_8를 조회하는 것이다.
한 노드의 다음 노드(혹은 이전 노드)가 (오류나 이탈로 인해) 네트워크에서 사라질 수도 있기 때문에, 각 노드는 서클 내에서 자신과 인접한 세그먼트 전체를 기록한다. 이 리스트는 문제의 네트워크가 높은 오류율을 겪고 있더라도, 높은 확률로 자신의 다음 노드 혹은 이전 노드를 정확하게 찾게 해준다.
프로토콜 상세.
기본적인 조회.
Chord 프로토콜의 핵심 용도는 클라이언트(노드)에서 키를 조회, 즉 formula_8를 찾는 것이다. 기본적인 해결책은 근처에서 키를 찾지 못한 경우, 노드의 다음 노드에 쿼리를 전달하는 것이다. 이는 formula_12 조회 시간을 따르는데, 여기서 formula_13 은 링 내 머신의 개수이다.
핑거 테이블.
위에서 선형 검색을 피하기 위해, Chord는 각 노드가 formula_3 개의 엔트리를 포함하는 핑거 테이블을 유미하도록 함으로써 더 빠른 검색 메서드를 구현한다. 여기서, formula_3 은 해시키에 있는 비트수이다. 노드 formula_16 의 formula_17 엔트리는 formula_18를 포함한다. 핑거 테이블의 첫번째 엔트리는 실제로 노드에 인접한 다음 노드이다 (그러므로 다음 노드에 대한 여분의 필드를 필요로 하지 않다). 노드가 키 formula_5를 탐색하려고 할 때마다, 핑거 테이블(ID가 formula_5 보다 더 작은 서클 상에서 "가장 큰" 것) 내에서 formula_5 의 가장 가까운 다음 노드 또는 이전 노드에 쿼리를 전달한다.
그런 핑거 테이블을 사용해, N-노드 네트워크 내에서 다음 노드를 찾기 위해 반드시 접촉되어야 하는 노드의 개수는 formula_22이다. (아래에서 증명한다)
노드 조인.
새로운 노드가 들어올 때면, 세 가지 불변 사항들이 유지되어야 한다(첫 두 가지는 정확성을 보장하는 것이고 마지막 것은 조회를 빠르게 유지한다):
이 세 가지 불변 사항들을 만족하려면, 각 노드에 대해 'predecessor' 필드가 유지되어야 한다. 다음 노드가 핑거 테이블의 첫번째 엔트리이므로, 이 필드를 개별적으로 유지할 필요가 전혀 없다. 다음 작업들이 새로 들어오는 노드 formula_16에 대해 이루어져야 한다:
formula_16 의 이전 노드는formula_27 (이전 서클 내에서)의 이전 노드로부터 쉽게 얻을 수 있다. 핑거 테이블에는 다양한 초기화 메서드가 있다. 가장 간단한 것은 모든 formula_3 의 엔트리에 대해 다음 노드 찾기 쿼리를 실행하는 것인데, formula_29 초기화 시간이 걸립니다. 더 나은 메서드는 핑거 테이블 내 formula_17 개의 엔트리가 formula_31 엔트리에 대해 여전히 올바른지를 검사하는 것이다. 이것은 formula_32. 최고의 메서드는 인접하는 이웃 노드로부터 핑거 테이블을 초기화하고 갱신하는 것인데, formula_22 이 걸립니다.
안정화.
정확한 탐색을 보장하기 위해, 모든 다음 노드를은 항상 최신으로 유지되어야 한다. =&gt; 백그라운드에서 주기적으로 실행되는 안정화 프로토콜. 핑거 테이블과 다음 노드 포인터의 갱신. 안정화 프로토콜: Stabilize(): n은 자신의 다음 노드에게 이전 노드 p에 대해 묻고 대신해서 p가 이전 노드가 되어야 하는지 결정한다(이는 p가 최근에 시스템에 들어온 경우를 말한다. Notify(): formula_16 의 존재를 다음 노드에게 알려줘서, 그것의 이전 노드를 formula_16으로 변경할 수 있다. Fix_fingers(): 핑거 테이블을 갱신한다.
증명 스케치.
'높은 개연성을 가지고, Chord는 formula_22' '개의 노드에 접근해formula_13-노드 네트워크 내에서 다음 노드를 찾는다.'
노드 formula_16 이 키 formula_5 에 대한 다음 노드를 찾으려고 한다고 가정해보겠다. formula_40 가 formula_5 의 이전 노드라고 해보자. 메시지를 formula_16 에서 formula_40 로 라우팅하는데 몇 단계가 걸리는지, 그 상한선을 찾고자 한다. 노드 formula_16 은 핑거 테이블을 검사하여 그것이 가진 formula_5 의 가장 인접한 이전 노드에게 요청을 라우팅한다. 이 노드를 formula_46 라고 해보자. 만약 formula_46 가 formula_16 의 핑거 테이블의 formula_17 번째 엔트리라면, formula_46 와 formula_40 는 formula_16 으로부터 formula_53 와 formula_54 사이의 거리에 있다. 따라서, 이 서클을 따른 formula_46 와 formula_40 사이의 거리는 최대 formula_53이다. 따라서, formula_46 에서 formula_40 까지의 거리는 formula_16에서 formula_46 까지의 거리보다 더 작다. formula_40 까지의 새로운 거리는 초기 거리의 절반 이하이다.
남은 거리를 반으로 나누는 이 과정이 반복되므로, formula_63 단계 이후에, formula_40 까지의 남은 거리는 최대 formula_65 가 된다. 특히, formula_66 단계 이후에, 남은 거리는 최대 formula_67 가 된다. 노드가 무작위로 식별 서클을 따라 고르게 분산되기 때문에, 이 길이 구간에 속하는 예상 노드의 수는 1이며, 그런 노드가 formula_66 개 보다 더 적게 있을 확률이 높다. 메시지가 항상 적어도 하나 이상의 노드에 의해 진행되기 때문에, 남은 거리를 탐색하는 메시지의 경우 formula_69 단계가 소요된다. 그래서 총 예상 라우팅 시간은 formula_22이 된다.
Chord가 formula_71 개의 이전 노드 및 다음 노드에 대한 트래킹을 유지할 경우, 또 각 노드가 실패할 확률이 1/4인 경우, find_successor (아래 참고)와 find_predecessor (see below)가 정확한 노드를 반환할 확률이 높다.
단순히, 모든 formula_72 노드가 실패할 확률은 formula_73이며, 이는 낮은 확률이다. 그러므로 그들 중 한 개는 살아있고 노드는 정확한 포인터를 가질 가능성이 높다.
의사 코드.
아이디에 대한 'successor' 노드를 찾는 의사 코드는 다음과 같다:
 // ask node n to find the successor of id
 n.find_successor(id)
 //Yes, that should be a closing square bracket to match the opening parenthesis.
 //It is a half closed interval.
 if (id ∈ (n, successor] )
 return successor;
 else
 // forward the query around the circle
 n0 = successor.closest_preceding_node(id);
 return n0.find_successor(id);
 // search the local table for the highest predecessor of id
 n.closest_preceding_node(id)
 for i = m downto 1
 if (finger[i]∈(n,id))
 return finger[i];
 return n;
노드 참가나 이탈 이후 Chord 링 혹은 서클을 안정화하는 의사 코드는 다음과 같다:
 // create a new Chord ring.
 n.create()
 predecessor = nil;
 successor = n;
 // join a Chord ring containing node n'.
 n.join(n')
 predecessor = nil;
 successor = n'.find_successor(n);
 // called periodically. n asks the successor
 // about its predecessor, verifies if n's immediate
 // successor is consistent, and tells the successor about n
 n.stabilize()
 x = successor.predecessor;
 if (x∈(n, successor))
 successor = x;
 successor.notify(n);
 // n' thinks it might be our predecessor.
 n.notify(n')
 if (predecessor is nil or n'∈(predecessor, n))
 predecessor = n';
 // called periodically. refreshes finger table entries.
 // next stores the index of the finger to fix
 n.fix_fingers()
 next = next + 1;
 if (next &gt; m)
 next = 1;
 finger[next] = find_successor(n+2^{next-1});
 // called periodically. checks whether predecessor has failed.
 n.check_predecessor()
 if (predecessor has failed)
 predecessor = nil;