P2Pと分散ハッシュテーブル〜その2
前章「P2Pと分散ハッシュテーブル〜その１」では 分散ハッシュテーブルの概要と分散ハッシュテーブルの一つであるＣＡＮについて説明しま した。この章では分散ハッシュテーブルの中でも最もポピュラーなChordについて 説明をします。 CANはＮ次元トーラスでハッシュ空間を形成しましたが、Chordでは円状のハッシュ空間、すわなり1次元空間がハッシュ空間全体となります。Chordではスキップリストという概念を使う事によって、非常に高速にオブジェクトの検索をすることができます。例えば、ノード数Ｎに対して、CANでは次元数dに対しO(N1/d)かかりますが、ChordではO(log N)となります。では早速Chordの概要について説明しましょう。 Chordではハッシュ空間を2160使い、ハッシュ関数としてSHA-1を想定しています。ここではハッシュ空間を説明しやすくするため、16=24にしましょう
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Distributed K-ary System (DKS)
原稿・資料 ― ありえるえりあ
