V-FIELD 通信分散
困った…とても困った…
P2P分散ディスク共有システムのV-FIELDですが、一番最初に起動したノードに負荷が集中してしまうと言う問題があります。これを解決したいのですが、まったく方法が思いつかない…。
原因は、ダウンロードしたいデータを、どのノードが持っているかを検索するときのアルゴリズムにあります。
どのノードがどこのデータを持っているかというテーブルを保持していて、これをV-Tableと読んでいるのですが、これは「持っているデータ範囲の開始位置」でソートしています。
V-Table:
IP 持っているデータ範囲 192.168.0.1 ********************************************************* 192.168.0.2 ************ 192.168.0.7 ****** 192.168.0.3 *********** 192.168.0.8 ****** 192.168.0.4 ************ 192.168.0.5 ************* 192.168.0.6 ***********
IPアドレスはDHCPで配るので、起動した順に振られていきます(実際には逆順に振られますが)
一番最初に起動したノードは、すべてのデータを持っています。そこから多重化しながら分散していって、全体が二重化されたら次は三重化されるように保持していきます。
ここであるノードが2つめの*から8つの*までダウンロードしたいと言うときに、現在のアルゴリズムでは、まず「8つめの*を持っている最後のノード」をV-Tableの上から順に探します。この例では192.168.0.7になります。それより下のノードは、間違いなくデータを持っていません。
続いてV-Tableの先頭から、2つめの*から8つめの*の一部でも持っているノードを探していきます。ヒットしたらそのノードからダウンロードします。
問題なのは、持っているデータ範囲の開始位置でソートしているので、上から順番に探すと必ず一番最初に起動したノード(ここでは192.168.0.1)にヒットしてしまうという点です。しかも一部分だけでなく必ずすべてヒットするので(一番最初に起動したノードはデータを全部持っている)、負荷はすべて192.168.0.1に集中してしまいます。
一度全体が二重化されたら、一番最初に起動したノードを再起動させてしまうと、ある程度分散されるようになります。
IP 持っているデータ範囲 192.168.0.2 ************ 192.168.0.7 ****** 192.168.0.3 *********** 192.168.0.8 ****** 192.168.0.1 ************* 192.168.0.4 ************ 192.168.0.5 ************* 192.168.0.6 ***********
しかしこの場合でも、192.168.0.7などにはまったくダウンロード要求がこないで、192.168.0.2に集中します。
とにかくダウンロード要求を分散するなら、V-Table位置Aから検索を開始をすることにして、位置Aを一定時間に一度ランダムな数値に更新する方法を考えていますが、検索が全部線形検索になるので(上のアルゴリズムは、半分は2分検索)、ノードの台数が増えると検索に時間がかかってしまうように思えます。(位置Aをダウンロードのたびに変更すると、コストがかかる&あまりに分散されると、要求先のノードがデータをHDDに保持しているときシーケンシャルリードにならなくて性能が落ちる気がする。ネットワークよりHDDの方が遅い)
検索にかかる時間が増えることと、特定のノードに負荷が集中してしまうことのどちらがコストが大きいのか…うーん…どっちなんでしょう?