Erlangで分散ハッシュテーブルを実装してみた - NO!と言えるようになりたい
並行言語であるErlangでPeer-to-Peer Network技術の一つである分散ハッシュテーブルを実装してみたところ，わずか1000行程度で実現できました．ノードが頻繁に出たり入ったりする，いわゆるchurn下でもそれなりの性能が出せたので，SourceForge.netで公開してみます．興味のある方はどうぞ． http://sourceforge.net/projects/ermdia/ 内部アルゴリズムはKademliaと呼ばれるものを利用しています．BitTorrent等でおなじみのアルゴリズムですが，データのput/getなどの通常のメッセージの交換時にルーティングテーブルをアップデートするため，ルーティングテーブルの維持コストがChord等に比べて低いという特徴があります．実装もそれなりに簡単で，過去にSymphonyと呼ばれる分散ハッシュテーブルを実装したのですが，それ
Erlang で分散ハッシュテーブル(kademlia)を使った Key-Value Store 作ってみたよ - cooldaemonの備忘録
Kai に kademlia の組み込みを提案する為、試しに作っていたのですが、README に書いた How to Use の項目が動くようになったので晒してみます。 cooldaemon's ermlia at master ― GitHub 設置方法なんかも README に書いてあるので、ご興味のある方は、そちらをご参考に。 まだ、いくつかの機能が未実装(定期的にデータを publish していない)だったり、不具合(Key のバージョン管理がされていない)があるけれど、そこそこに動きます。 おまえは kademlia を勘違いしている！等、突っ込み大歓迎。 参考 URI Erlangで分散ハッシュテーブルを実装してみた - NO!と言えるようになりたい id:ytakano 氏に多謝！ Amazon.co.jp： P2P教科書 (インプレス標準教科書シリーズ): 江崎 浩: 本
Kademlia -首藤一幸 - 産業技術総合研究所 グリッド研究センター
1 Kademlia 首藤一幸 産業技術総合研究所 グリッド研究センター 2004年 7月 27日（火） 2 資料 IPTPS02 の論文とスライド � “Kademlia: A Peer-topeer Information System Based on the XOR Metric” ウェブページ � http://kademlia.scs.cs.nyu.edu/ 7/26時点では参照できず。 3 Kademlia の位置付け 論文中に現れる比較対象: � Chord � Chord の悪い点: � 経路表が厳格。 � ノードの failure や、経路表の欠損からの復旧が複雑。 � qeury 転送の方向が一方向。 � Incoming traffic を元に経路表を更新できない。 � Kademlia では、2ノード間の関係は symmetric。 � x が y の経路表に載っ
「Kademlia: A Peer-to-peer Information System Based on the XOR Metric」のまとめ: Akito's IT技術 メモ
タイトル: Kademlia: A Peer-to-peer Information System Based on the XOR Metric 著者: Petar Maymounkov and David Mazieres Kademliaは実装が容易だとされているDHT手法である． Wikipedia(en)を見ると，Kademliaのライブラリがいくつか並んでることからもわかる． というのは，データの検索や配置のメッセージの送受信を通じて，ルーティングテーブルを更新していけるからだと思う． * Abstract KademliaはXORベースのDHT * 1 Introduction Kademlia lookupのメッセージに，ルーティング情報をのせることができる． パラレルクエリによるタイムアウト防止 他のDHTと違って，式で性能を証明できる 160b
Microsoft PowerPoint - Kademlia-Shudo-20040727.ppt
2004年 7月 27日（火） Kademlia 首藤一幸 産業技術総合研究所 グリッド研究センター 1 資料 IPTPS02 の論文とスライド “Kademlia: A Peer-topeer Information System Based on the XOR Metric” ウェブページ http://kademlia.scs.cs.nyu.edu/ 7/26時点では参照できず。 2 Kademlia の位置付け 論文中に現れる比較対象: Chord Chord の悪い点: 経路表が厳格。 ノードの failure や、経路表の欠損からの復旧が複雑。 qeury 転送の方向が一方向。 Incoming traffic を元に経路表を更新できない。 x が y の経路表に載ってれば、y は x の経路表に載ってる。 incoming traffic を元にして経路表を更
Kademlia: A Peer-to-peer Information System Based on the XOR Metric Petar Maymounkov and David Mazi`eres {petar,dm}@cs.nyu.edu http://kademlia.scs.cs.nyu.edu New York University Abstract. We describe a peer-to-peer distributed hash table with prov- able
Kademlia: A Peer-to-peer Information System Based on the XOR Metric Petar Maymounkov and David Mazi`eres {petar,dm}@cs.nyu.edu http://kademlia.scs.cs.nyu.edu New York University Abstract. We describe a peer-to-peer distributed hash table with prov- able consistency and performance in a fault-prone environment. Our system routes queries and locates nodes using a novel XOR-based met- ric topology t
inforno :: Python: 勉強がてらDHT(Kademliaっぽいもの)を実装しました
前々から一度じっくり勉強しないとなぁと思っていたDHTまわりの勉強がてらKademliaっぽいものをPythonで実装してみました。 Kademliaはいろいろ実装があるので、ソースを読んじゃうと答えみちゃった感じになるかなーと思って、元論文と 首藤様の資料 くらいしか見ずに実装してみました。ので、いろいろ間違ってるかも知れませんが･･･。 本家Kademliaとの主な違いは UDPではなくTCPを使っている ローカル環境しかもっていないので、UDPパケットがロスしやすい場合(WAN)を想定して実装するのがめんどくさい。 よってRPC-IDをつけていない。 パケットの分割や再送もTCPにおまかせ。 original publisherから一定時間publishを受けなくてもインデックス情報をexpireしていない 実装するのは簡単です。 ノードがネットワークに参加したとき、Index情報を
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Good night, Posterous
Microsoft PowerPoint - 参考資料DHT.ppt [互換モード]
http://0821.org/author/kuroda_thesis.pdf