CANはＮ次元トーラスでハッシュ空間を形成しましたが、Chordでは円状のハッシュ空間、すわなり1次元空間がハッシュ空間全体となります。Chordではスキップリストという概念を使う事によって、非常に高速にオブジェクトの検索をすることができます。例えば、ノード数Ｎに対して、CANでは次元数dに対しO(N1/d)かかりますが、ChordではO(log N)となります。では早速Chordの概要について説明しましょう。
Chordではハッシュ空間を2160使い、ハッシュ関数としてSHA-1を想定しています。ここではハッシュ空間を説明しやすくするため、16=24にしましょう。下図を見て下さい。今、ハッシュ空間にNode_IDが0〜15まで付いています。そのうち、実際にノードが存在するものを赤色で塗りました。
それではノードとそれをカバーするハッシュ空間について説明しましょう。まず、next(X)という関数を導入します。これはハッシュ空間のXにおいてハッシュ空間を右回り（つまりNode_IDを大きくする方向）で次にいるノードのNode_IＤを返します。例えば、next(3)=6、next(12)=13,next(13)=13となる。ハッシュ空間のある値Xをカバーするノードはnext(X)となります。例えば、ハッシュ値３の情報を所有しているノードはnext(3)=6です。
これでハッシュ空間とノードのマッピングができました。そこで今度は実際ノードを検索しましょう。まず非常に原始的な検索方法を考えています。今Node_ID=0がNode_ID=13のノードを検索したいとします。すると、次のようにNext()を繰り返し計算すればそのうちNode_ID=13はわかりそうです。このとき、各ノードはNext(ID)をルーティングテーブルとして保持します。今の検索の様子を絵に描いてみたのが下図です。
でもこの方法は明らかに効率が悪いですよね。特にノードが多くなるとこの傾向は顕著になります。ノード数Ｎに対してO(N)です。そこでChordはちょっとした工夫をしています。2mのハッシュ空間においてNode_IDを持つ各ノードは次のようなルーティングテーブルを持ちます。
ルーティングテーブル={IPAdress[next(Z)] }
ただし、Z=Node_ID+2i mod 2m
i=0〜m-1
ただ、式に書いても実感がわかないと思うので、実際にNode_ID=0（簡単のためにこういうノードをノード０と表記する事にします。）の場合で試してみましょう。まず、i=0のとき、next[z]=next[0+20]=next[1]=2となります。よってノード０はノード２のＩＰアドレスを知っている事にします。これを全部計算すると次のようになります。
ルーティングテーブル(ノード０）={ノード2(i=0,1[z=1,2]),ノード6（i=2[z=4]),ノード9(i=3[z=8])}
となります。これを各ノードにおいて先ほどの計算の通りルーティングテーブルを持つ事にしましょう。では、改めてノード０からノード１３への検索を行いましょう。まず、ノード13は23＜13＜24に注意して下さい。これによって、ノード０はi=3[z=8]のときのルーティングテーブル、つまりノード９に検索を依頼します。
さて、ノード9のルーティングテーブルは次のとおりです。
ルーティングテーブル（ノード９）={ノード11(i=0,1[z=10,11]),ノード13(i=2[z=13]),ノード2(i=3[z=1])}
ノード１３のルーティングテーブルがありますから、ノード９はノード１３にルーティングすることができます。今の検索の様子を絵にしたのがした図です。
明らかに先ほどよりも検索効率が良いことが分かりますよね？では、もう一度ノード０がどのノードのＩＰアドレスをルーティングテーブルとして保持しているか絵にしましたので確認して下さい。
実線が実際にルーティングしているノード、点線がz=2iが指すハッシュ値です。
さて、このようなスキップリストを使って、検索するノードを次のノードに渡す度に検索すべきハッシュ空間を1/2に絞ることがわかります。これがChordが高速に検索できる理由です。
ではノードの追加、削除するときの処理を書いておきます。今、ノード3がネットワークに参加するとします。まずノード3は現在ネットワークに参加している適当なノードにnext(3)のノードＩＰを探してもらいます。今の場合next(3)はノード６ですね。ノード３はノード６の一個前のノード、つまり実在のノードrでnext(r)となるノードを教えてもらいます。今の場合、そのノードrはノード2です。ノード3はノード６とノード２に自分の存在を教え、ルーティングテーブルの変更を行ってもらいます。また、ノード6からハッシュ値３，４，５に対応しているデータをもらいます。これでノード3がChordに参加することができます。
ノードが離脱した場合はどうでしょう？各ノードはルーティングしているノードに対して定期的にノードの生死を確認します。これによってバックグラウンドでルーティングテーブルを更新する必要があります。しかし、これではネットワークから離脱するノードＸに蓄積しているデータが失われて可能性があります。そのため、ノードXが保持しているデータはXから時計回りzに近い順番からq個存在するノードにデータを複製しておきます。これで急にノードＸがネットワークから離脱してもデータが失われる事はありません。
さて、Chordの概要について説明する事ができました。シンプルな構成ながら検索スピードが早い事は非常に魅力的なポイントと言えるでしょう。
機会があれば、P-gridなど他の分散ハッシュテーブルのアルゴリズムも紹介していきたいと 思います。