Chord
Chord(코드)는 컴퓨팅에서 peer-to-peer 분산 해시 테이블에 대한 프로토콜 및 알고리즘이다. 분산 해시 테이블은 ("노드"라고 알려진) 다른 컴퓨터에 키를 할당하여 키-값 쌍을 저장한다(한 노드는 그것이 담당하는 모든 키에 대한 값을 저장한다). Chord는 노드에 키가 할당되는 방법과 주어진 키에 해당하는 첫번째 노드를 찾아 해당 키에 대한 값을 해당 노드가 찾을 수 있는 방법을 정한다.
Chord는 CAN, Tapestry 그리고 Pastry와 함께, 4개의 원조 분산 해시 테이블 프로토콜 중 하나이다. 이 프로토콜은 Ion Stoica, Robert Morris, David  Karger, Frans Kaashoek, Hari Balakrishnan가 도입했으며, MIT에서 개발되었다.
노드와 키는 formula_1에서 formula_2까지의 범위를 가지는 formula_3 노드들의 식별 서클 (Identifier circle) 내에서 할당된다(여기서 formula_4은 충돌을 피할 수 있을 만큼 충분히 커야 한다). 이러한 노드들 중 일부는 머신 또는 키에 매핑되는 반면 다른 것들(대부분)은 비어 있다.
각 노드는 '다음 노드(successor)'와 '이전 노드(predecessor)'를 가지고 있다. 한 노드의 이전 노드는 식별 서클 내에서 시계 방향으로 있는 다음 노드이다. 다음 노드는 시계 반대 방향에 있다. 잠재적인 ID 각각에 대해 하나의 노드가 있는 경우 노드 0의 다음 노드는 노드 1이며, 노드 0의 이전 노드는 노드 formula_5 의 다음 노드는 아이디가 formula_6 와 같거나 식별 서클 내에서 formula_6 다음에 오는 첫번째 노드로, formula_8 로 표시한다. 모든 키는 그것의 다음 노드에 할당되므로, 키 formula_6 를 탐색하는 것은 formula_8 를 조회하는 것이다.
한 노드의 다음 노드(혹은 이전 노드)가 (오류나 이탈로 인해) 네트워크에서 사라질 수도 있기 때문에, 각 노드는 서클 내에서 자신과 인접한 전체 세그먼트(즉, 해당 노드 앞에 formula_11 노드가 있고  formula_11 노드 다음에는 해당 노드가 있다)를 기록한다. 이 리스트는 문제의 네트워크가 높은 오류율을 겪고 있더라도, 자신의 다음 노드 혹은 이전 노드를 정확하게 찾을 가능성이 높다.
Chord 프로토콜의 핵심 용도는 클라이언트(일반적으로 노드일수도 있다)에서 키를 조회, 즉 formula_8. 기본적인 해결책은 근처에서 키를 찾지 못한 경우, 노드의 다음 노드에 쿼리를 전달하는 것이다. 이는 formula_14 조회 시간을 따르는데, 여기서 formula_15 은 링 내 머신의 개수이다.
위에서 선형 검색을 피하기 위해, Chord는 각 노드가 formula_4 개의 엔트리를 포함하는 핑거 테이블을 유미하도록 함으로써 더 빠른 검색 메서드를 구현한다. 여기서, formula_4 은 해시키에 있는 비트수이다. 노드 formula_18 의 formula_19 엔트리는 formula_20를 포함한다. 핑거 테이블의 첫번째 엔트리는 실제로 노드에 인접한 다음 노드이다 (그러므로 다음 노드에 대한 여분의 필드를 필요로 하지 않다). 노드가 키 formula_6 를 탐색하려고 할 때마다, 핑거 테이블(ID가 formula_6 보다 더 작은 서클 상에서 "가장 큰" 것) 내 에서 formula_6 의 가장 가까운 다음 노드 또는 이전 노드에 쿼리를 전달한다.
그런 핑거 테이블을 사용해, N-노드 네트워크 내에서 다음 노드를 찾기 위해 반드시 접촉되어야 하는 노드의 개수는 formula_24 이다. (아래에서 증명한다)
새로운 노드가 들어올 때면, 세 가지 불변 사항들이 유지되어야 한다(첫 두 가지는 정확성을 보장하는 것이고 마지막 것은 조회를 빠르게 유지한다):
이 세 가지 불변 사항들을 만족하려면, 각 노드에 대해 'predecessor' 필드가 유지되어야 한다. 다음 노드가 핑거 테이블의 첫번째 엔트리이므로, 이 필드를 개별적으로 유지할 필요가 전혀 없다. 다음 작업들이 새로 들어오는 노드 formula_18 에 대해 이루어져야 한다:
formula_18 의 이전 노드는formula_29 (이전 서클 내에서)의 이전 노드로부터 쉽게 얻을 수 있다. 핑거 테이블에는 다양한 초기화 메서드가 있다. 가장 간단한 것은 모든 formula_4 의 엔트리에 대해 다음 노드 찾기 쿼리를 실행하는 것인데, formula_31 초기화 시간이 걸립니다. 더 나은 메서드는 핑거 테이블 내 formula_19 개의 엔트리가 formula_33 엔트리에 대해 여전히 올바른지를 검사하는 것이다. 이것은 formula_34. 최고의 메서드는 인접하는 이웃 노드로부터 핑거 테이블을 초기화하고 갱신하는 것인데, formula_24 이 걸립니다.
정확한 탐색을 보장하기 위해, 모든 다음 노드를은 항상 최신으로 유지되어야 한다. => 백그라운드에서 주기적으로 실행되는 안정화 프로토콜. 핑거 테이블과 다음 노드 포인터의 갱신. 안정화 프로토콜: Stabilize(): n은 자신의 다음 노드에게 이전 노드 p에 대해 묻고 대신해서 p가 이전 노드가 되어야 하는지 결정한다(이는 p가 최근에 시스템에 들어온 경우를 말한다. Notify(): formula_18 의 존재를 다음 노드에게 알려줘서, 그것의 이전 노드를 formula_18 으로 변경할 수 있다. Fix_fingers(): 핑거 테이블을 갱신한다.'높은 개연성을 가지고, Chord는 formula_24' '개의 노드에 접근해formula_15-노드 네트워크 내에서 다음 노드를 찾는다.'
노드 formula_18 이 키 formula_6 에 대한 다음 노드를 찾으려고 한다고 가정해보겠다. formula_42 가 formula_6 의 이전 노드라고 해보자. 메시지를 formula_18 에서 formula_42 로 라우팅하는데 몇 단계가 걸리는지, 그 상한선을 찾고자 한다. 노드 formula_18 은 핑거 테이블을 검사하여 그것이 가진 formula_6 의 가장 인접한 이전 노드에게 요청을 라우팅한다. 이 노드를 formula_48 라고 해보자. 만약 formula_48 가 formula_18 의 핑거 테이블의 formula_19 번째 엔트리라면, formula_48 와 formula_42 는 formula_18 으로부터 formula_55 와 formula_56 사이의 거리에 있다. 따라서, 이 서클을 따른 formula_48 와 formula_42 사이의 거리는 최대 formula_55 이다. 따라서, formula_48 에서 formula_42 까지의 거리는 formula_18 에서 formula_48 까지의 거리보다 더 작다. formula_42 까지의 새로운 거리는 초기 거리의 절반 이하이다.
남은 거리를 반으로 나누는 이 과정이 반복되므로, formula_65 단계 이후에, formula_42 까지의 남은 거리는 최대 formula_67 가 된다. 특히, formula_68 단계 이후에, 남은 거리는 최대 formula_69 가 된다. 노드가 무작위로 식별 서클을 따라 고르게 분산되기 때문에, 이 길이 구간에 속하는 예상 노드의 수는 1이며, 그런 노드가 formula_68 개 보다 더 적게 있을 확률이 높다. 메시지가 항상 적어도 하나 이상의 노드에 의해 진행되기 때문에, 남은 거리를 탐색하는 메시지의 경우 formula_71 단계가 소요된다. 그래서 총 예상 라우팅 시간은 formula_24이 된다.
Chord가 formula_73 개의 이전 노드 및 다음 노드에 대한 트래킹을 유지할 경우, 또 각 노드가 실패할 확률이 1/4인 경우, find_successor (아래 참고)와 find_predecessor (see below)가 정확한 노드를 반환할 확률이 높다.
단순히, 모든 formula_11 노드가 실패할 확률은 formula_75 이며, 이는 낮은 확률이다. 그러므로 그들 중 한 개는 살아있고 노드는 정확한 포인터를 가질 가능성이 높다.
아이디에 대한 'successor' 노드를 찾는 의사 코드는 다음과 같다:
// ask node n to find the successor of id
// search the local table for the highest predecessor of id
노드 참가나 이탈 이후 Chord 링 혹은 서클을 안정화하는 의사 코드는 다음과 같다:
// create a new Chord ring.
// join a Chord ring containing node n'.
// called periodically. n asks the successor
// n' thinks it might be our predecessor.
// called periodically. refreshes finger table entries.
// called periodically. checks whether predecessor has failed.