P2Pと分散ハッシュテーブル〜その2
前章「P2Pと分散ハッシュテーブル〜その１」では 分散ハッシュテーブルの概要と分散ハッシュテーブルの一つであるＣＡＮについて説明しま した。この章では分散ハッシュテーブルの中でも最もポピュラーなChordについて 説明をします。 CANはＮ次元トーラスでハッシュ空間を形成しましたが、Chordでは円状のハッシュ空間、すわなり1次元空間がハッシュ空間全体となります。Chordではスキップリストという概念を使う事によって、非常に高速にオブジェクトの検索をすることができます。例えば、ノード数Ｎに対して、CANでは次元数dに対しO(N1/d)かかりますが、ChordではO(log N)となります。では早速Chordの概要について説明しましょう。 Chordではハッシュ空間を2160使い、ハッシュ関数としてSHA-1を想定しています。ここではハッシュ空間を説明しやすくするため、16=24にしましょう
Home
The Chord project explored how to build scalable, robust distributed systems using peer-to-peer ideas. The basis for much of our work is the Chord distributed hash lookup primitive. Chord is completely decentralized and symmetric, and can find data using only log(N) messages, where N is the number of nodes in the system. Chord's lookup mechanism is provably robust in the face of frequent node fail
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
