誰か検索結果を返すか

検索部分を作っていて思ったことと実装メモ。

Winnyの検索クエリは、6ノードを経由するか、または検索結果が31個になった時点で発信元へ戻ってきます。
（Winnyの技術によると検索クエリを折り返す条件となる検索結果数は30個らしいですが、実際は31個返ってくることが多いです。たまに33個返ってくることもあり。）
悩みどころは、誰が検索結果をどんな感じで返すのがよいかというところ。

＠よく意味が分からないだろうから例えを交えながら
ノードA<-->ノードB<-- ノードX と繋がっているとして、ノードAがノードBへ検索クエリ「キーワード=ポエム」を送信したとします。
ノードBは「ポエム」にヒットするキーを100個持っています。
さて、どうするか？
問題としては２つあります。

ノードBが31個のキーをパックしてノードAへ折り返すべきか？
1をするとしたら、キーをどのように選択するか？

1について。
ノードBは、検索結果となるキーを31個以上持っていますが、これを全てノードBがパックして折り返してしまうと、ノードAへ常にノードBの保持するキーしか返らなくなります。ただし、ノードBは、その他のノードXと繋がっていて、キーは常に更新されていますから、そう気にするきこともないように思えますが、例えば、1ノードがパックするキーは最大5つ！として、いくつかのノードを経由させたほうが偏りがなく、キーの拡散にも一役立つのではないか？という気もします。

個人的結論としては、Winnyはキー拡散を前提に動いているから、ノードBが結果全部を返しちゃっても問題ない。そのほうが帯域を圧迫しない。
ということで、そういう実装になっています。

2について。
定期的にノードAから送られてくる検索クエリに対してどれを返すべきか。
今、ノードBは検索結果となるキーを100個持っていて、これが増えたり減ったり、更新されたりしています。
検索クエリが来る毎に31個ずつきっちり前回送っていないキーを返すことが理想ですが、完全にそうするのは難しいですし、そこまでする必要がない気がします。

個人的結論としては、検索結果となるキー候補(100個)をノードBの負荷にならない程度の割合でシャッフルして、ランダムに選んだ31を返す。
ということで、そういう実装になっています。

少し別の話。

折り返し地点で検索結果数=0の検索クエリは折り返す必要がない

戻ってきてもうれしくないし、わざわざ戻す意味もよく分からないので、捨てる実装にします。

だんだん、Winnyの実装を見なくなってきたので、動きも怪しくなってきそうですががんばります。