| | | | | |
|
 |
|
 |
 |
|
|
Imonyで使用する分散ハッシュテーブル(DHT)
 DHTとは何が違うのか
過去にあった分散ハッシュテーブル(DHT)はできる限り知っているノードを減らそうとする傾向がある。これはメッセンジャーP2P等、バックグラウンドで起動するようなソフトにおいては必要（無駄なメモリーや通信が必要になってしまうから）であるが、情報と言う物は出来る限り速く得られるべきものであり、その場合において知っているノードを極端に減らそうとすることは損である。Imonyでは今までのDHT(影響順にKademlia、CAN、Chord)を参考にした上で、1万人クラスまでノードを保持できる状況で100万人クラス(5000万人クラスまでは安定を要求する)のP2Pネットワークを最も効率的に維持する方法を考えた。
※ここで使われる数値は現在の予測であり、実際と異なる場合があります
概要
ユーザIDに関する知識・ユーザ探索
Imonyで使用するユーザーIDハッシュ空間は96Bitの予定である。このハッシュは出来る限り均等に並べられているものとする。ここでは説明の簡略化の為に頭の32Bit以降は省略する。Imonyの知識は以下のものである
- 知識1…1/2^0(全体)の範囲において2^12人(4096人)の知識
- 知識2…1/2^9(0.2%)の範囲において2^12人の知識
- 知識3…1/2^18(又はそれ以上)の範囲において2^10人の知識
- 知識4…1/2^23(又はそれ以上)の範囲において2^9人の知識
標準状態として9728件の知識を持つ。ただし、リクエストした時に安定した答えが返されるようにするために、ユーザーが変更できるのは知識1のみにすることに注意。
UserAがUserBを要求する場合、まず自分の所にないか確認をし、その次にUserAはUserBに最も近いノードを自分の知識1から探索する場合、期待値としては1/2^12、最低限1/2^10以上に絞れる。この時、探索要求されたノードは知識2に指定されている1/2^9の範囲においてよく知っておくべきであり、知らない場合も知識3に指定されている1/2^18の範囲における近いノードを返せるべきである。つまり、理論上
- 知識1で十分…2^12人以内であれば0回のリクエストで足りる
- 知識2で十分…2^21人以内であれば1回のリクエストで足りる
- 知識3で十分…2^28人以内であれば2回のリクエストで足りる
- 知識4で十分…2^32人以内であれば3回のリクエストで足りる
なぜ知識を階層化しているか
それはユーザの数に段々対応していくための策である。失敗した場合も、さらに知ってそうな（さらに目的の値に近い）ノードを返す仕様にする。よってここでは全体のノード数を知る必要はなく、その状態で十分稼動する。他の種類のP2Pでも登録人数を減らせば似たことができるだろう。
ファイルIDに関する知識・ファイル探索
Imonyにおいてファイル探索について重要なことはImonyはUDP通信であり出来る限りトラフィックを減らすことに重きをおいているということである。このためにパケットは1KBで256KBブロックを形成することになっている。もしTCPを使うのであれば2MBくらいのブロックを組んでも良いかもしれない。
Imonyで使用するファイルIDハッシュ空間は96Bitの予定である。このハッシュは出来る限り均等に並べられているものとする。ここでは説明の簡略化の為に頭の32Bit以降は省略する。Imonyの知識は以下のものである
- 最も近い範囲において2^22件の知識
一件あたり256Bit(=32Byte)であるので、上記の場合は128MBのHDD領域で展開できる。それぞれのノードは各レベルにおいて2^22*2^8KByte、つまり1TB分のファイルのありかを知っている。これはコンテンツ提供者の提供数の少なくとも8倍以上必要であり、できれば64倍以上であるべきである。つまりできれば提供平均量は16GB、多くても128GBであるべきである。また要求の少ないもののファイル位置情報は出来る限り少なく出すべきである。
※ファイル位置情報は匿名性確保のために機密情報扱い
|
 |
コンテンツ
トップページ
Imonyについて
Imonyアンテナ
更新履歴
リンク集
≫P2P today
≫俺が新しいP2P作ろっか？
…P2P製作 本スレ
≫Download板
|
|
Copyright(C) 2004/04/01-2008/12/05 FlashBox.
All rights reserved. Programed by Imo.
Designed by Imo, N-Style, siv.
Time: 159.4ms -145
管理モード
|