deadbeaf.orgThis domain may be for sale!
DHTのアルゴリズム - WebLab.ota
分散ハッシュテーブル - Wikipedia DHTは、ピュアP2Pであってもネットワーク負荷はそれほど上がらず、ネットワーク上のコンテンツを漏れなくかつ高速に探索することを可能にする。従来のピュアP2Pで採用されていた通信では、数10万ピアぐらいが限界だとされているが、DHTを使うと数10億ピアを探索範囲とすることが可能となる。しかし、実装がむずかしいことが欠点となる。 DHTの欠点は、一般的に完全一致探索しか行えないことである。特に正規表現のような複雑な検索をDHTのみで実現することは不可能である。 代表的なDHTのアルゴリズムを説明している日本語文献を探してみた． Chord この節では，DHT の代表的なアルゴリズムであるChord について説明する．Chordのハッシュ空間上での距離の定義は，ハッシュ値の差の絶対値である．図3.5のように，データ保有ノード (図中の青点) を，そ
P2Pと分散ハッシュテーブル〜その１
さて、P2Pでは最近「分散ハッシュテーブル」というキーワードをよく聞きます。分散ハッシュテーブルついては後で紹介しますが、これを用いるとルーティング、検索が高速に、しかもP2Pネットワーク全体に対して適用することができます。例えば既にeMuleと呼ばれるファイル共有システムでは分散ハッシュテーブルの一種であるkademliaが使われています。ではそもそも分散ハッシュテーブルとはどういうものなのでしょうか？それを説明するにはまず検索で使われるハッシュ法を説明する必要があります。 [お知らせ]分散ハッシュテーブル（ＤＨＴ）についてわかりやすく解説したページを作りました。 ＤＨＴに興味のある方はまずこちらをご覧下さい。 分散ハッシュテーブル（ＤＨＴ）入門〜その１ ハッシュ法 今、あるデータベースを考えてください。ここには人の名前と身長が書いてあるテーブルとしましょう。例えば table_1={
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ページを開く
