DHTのアルゴリズム - WebLab.ota
分散ハッシュテーブル - Wikipedia DHTは、ピュアP2Pであってもネットワーク負荷はそれほど上がらず、ネットワーク上のコンテンツを漏れなくかつ高速に探索することを可能にする。従来のピュアP2Pで採用されていた通信では、数10万ピアぐらいが限界だとされているが、DHTを使うと数10億ピアを探索範囲とすることが可能となる。しかし、実装がむずかしいことが欠点となる。 DHTの欠点は、一般的に完全一致探索しか行えないことである。特に正規表現のような複雑な検索をDHTのみで実現することは不可能である。 代表的なDHTのアルゴリズムを説明している日本語文献を探してみた． Chord この節では，DHT の代表的なアルゴリズムであるChord について説明する．Chordのハッシュ空間上での距離の定義は，ハッシュ値の差の絶対値である．図3.5のように，データ保有ノード (図中の青点) を，そ
Erlangで分散ハッシュテーブルを実装してみた - NO!と言えるようになりたい
並行言語であるErlangでPeer-to-Peer Network技術の一つである分散ハッシュテーブルを実装してみたところ，わずか1000行程度で実現できました．ノードが頻繁に出たり入ったりする，いわゆるchurn下でもそれなりの性能が出せたので，SourceForge.netで公開してみます．興味のある方はどうぞ． http://sourceforge.net/projects/ermdia/ 内部アルゴリズムはKademliaと呼ばれるものを利用しています．BitTorrent等でおなじみのアルゴリズムですが，データのput/getなどの通常のメッセージの交換時にルーティングテーブルをアップデートするため，ルーティングテーブルの維持コストがChord等に比べて低いという特徴があります．実装もそれなりに簡単で，過去にSymphonyと呼ばれる分散ハッシュテーブルを実装したのですが，それ
分散ハッシュテーブル（ＤＨＴ）入門〜その2
分散ハッシュテーブル（ＤＨＴ）入門〜その2 分散ハッシュテーブル入門（ＤＨＴ）〜その2 ３．あいうえおＤＨＴからＤＨＴへ さて、「あいうえおDHT」ではなにが問題なのだろうか？考えてみよう。 「あいうえお」ということは少なくともノードが数１０個あれば「あいうえお」で 書かれているデータは全て分散管理ができる。 ところで、「あ」で始まるファイル名と「ぬ」で始まるファイル名はどちらの方が 多いだろうか？一般的には明らかに「あ」の方が管理しているデータ量が多いはず だ。つまり「あいうえおDHT」では各ノードによってデータの保持している量に ばらつきがあって、不公平感があるのだ。ノード「あ」とノード「ぬ」では負荷に かなりの違いがある。 もうひとつ問題がある。それはノードの数に拡張性が無い事だ。「あいうえお」は 50音だから50個あるわけなので、「あいうえおDHT」では50個ノードがあればデータ
分散ハッシュテーブル（ＤＨＴ）入門〜その３
分散ハッシュテーブル（ＤＨＴ）入門〜その３ 分散ハッシュテーブル入門（ＤＨＴ）〜その３ ５．あいうえおＤＨＴのルーティング そもそもルーティングとはなんでしょう？ 例えば、ある人が東京から大阪に行きたいとする。今、自動車で大阪に行くと すると、首都高速に乗って高速道路に行く手もあれば、国道や一般道を使って ゆっくり安上がりに行く手もある。このように、あるところから目的にのところ までどうやって行くかを決める手段をルーティングと呼ぶ。 インターネットの場合にはIPアドレスというのがユーザのPCやサーバに 割り当てられる。ルーティングはこのIPアドレスを使って、例えばある人が 私のBlogをどうやって見ることができるか決める事ができる。 ルーティングなしには、インターネットのどんなページも見ることが できなくなってしまう。 ところで、DHTでのルーティングというのはどういうことだろうか？ 例え
分散ハッシュテーブル（ＤＨＴ）入門
分散ハッシュテーブル（ＤＨＴ）入門〜その１ 分散ハッシュテーブル入門（ＤＨＴ）〜その１ この章ではPure-P2Pにおいて最近必須技術となりつつある分散ハッシュテーブル （DHT:Distributed Hash Table)についてわかりやすく説明します。 まずはこのページを見てＤＨＴに対する感覚を覚えていただき、その後に 著名な論文等で具体的な内容等を見て頂ければ理解が進むと思います。 1.イントロダクション ではまずおさらいとしてP2Pの種類について復習しましょう。 P2Pは大きく分けて ・Hybrid-P2P（Napster型） ・Pure−P2P（Gnutella型） の2種類があった。 Hybrid型は中央サーバが存在し、中央サーバに各ユーザの情報を登録しておく。 ユーザは中央サーバの情報を基に各PCとP2Pで通信するわけである。 逆にPure-P2Pにはサーバと言うものが存在
Distributed Hash Tables, Part I | Linux Journal
In the world of decentralization, distributed hash tables (DHTs) recently have had a revolutionary effect. The chaotic, ad hoc topologies of the first-generation peer-to-peer architectures have been superseded by a set of topologies with emergent order, provable properties and excellent performance. Knowledge of DHT algorithms is going to be a key ingredient in future developments of distributed a
Distributed hash table - Wikipedia
A distributed hash table (DHT) is a distributed system that provides a lookup service similar to a hash table. Key–value pairs are stored in a DHT, and any participating node can efficiently retrieve the value associated with a given key. The main advantage of a DHT is that nodes can be added or removed with minimum work around re-distributing keys.[1] Keys are unique identifiers which map to part
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ページを開く
The Design of a Robust Peer-to-Peer System Rodrigo Rodrigues, Barbara Liskov, Liuba Shrira MIT Laboratory for Computer Science¡ rodrigo, liskov, liuba¢ @lcs.mit.edu Abstract Peer-to-peer (P2P) overlay networks have recently become one of the hottest
OpenDHT: A Shared, Public DHT Service
Journal of acme (189)
When Multi-Hop Peer-to-Peer Routing Matters
http://www-db.stanford.edu/~manku/phd/index.html
Robust and Efficient Data Management for a Distributed Hash Table
DHT Routing Using Social Links
Azureus - DistributedTrackerAndDatabase