Peer-to-Peer Information Retrieval: An Overview
これはなに
p2p環境下での情報検索(Information Retrieval, IR)に関するサーベイの要約
Tigelaar, Almer S., Djoerd Hiemstra, and Dolf Trieschnigg. "Peer-to-peer information retrieval: An overview." ACM Transactions on Information Systems (TOIS) 30.2 (2012): 9.
おそらく最も最新かつ唯一のp2p情報検索に関するサーベイ論文であり、ここまでまとまっているものはないように思われる
(ファイル共有なりドキュメント共有なりの)p2pネットワーク上に検索のインデックスを作る際、
なにが問題になるのか
どのようなトポロジーのネットワークが良いのか
等についてまとめてある非常に貴重な論文
ただし、セキュリティ上の問題(malicious nodeがほげほげ)等には触れていない
単純な分散ハッシュテーブル上のセキュリティ問題に関しては次のサーベイがある
Urdaneta, Guido, Guillaume Pierre, and Maarten Van Steen. "A survey of DHT security techniques." ACM Computing Surveys (CSUR) 43.2 (2011): 8.
p2p情報検索に関する僕の個人的な論文サーベイ
最近一人でコツコツと作ってるp2p検索エンジンのPoC(wip)
本題に入る前に
p2p IRが通常のブロックチェーンと違うところ
すべてのノードが同じデータを持たなくて良い
むしろデータが重いので分散して管理しようというのが基本的なネットワーク構造である分散ハッシュテーブル
つまり、globalで状態を合意する必要がない
例えば {単語 -> 単語に関連するURLのリスト}というデータを保持する分散ハッシュテーブルの場合、 "猫" (単語)というクエリに対する結果が多少ノード毎に違っても問題がない(クライアントサイドで結果をいい感じにマージすればいい)
とはいえ、コインによるインセンティブを与えたりと、組み合わせることも可能性的には考えられる(はず)
インセンティブ設計を兼ね備えたp2p検索エンジンは今の所この世に存在しない
そもそも2018年にもなってp2p検索エンジンを作ってる人なんていない
悪意あるノードを排除する等にブロックチェーンの文脈で近年(2010~)発達してきたコンセンサスアルゴリズムが使えるはず
p2p情報検索が流行った時期(~2008)には考えられなかった応用があるはず
Introduction
近年発達してきた情報検索サービスにおいては、中央サーバーが情報を集める・検索のインデックスを作成する・検索結果のランキングの作成までを行っている
検閲・情報(ユーザーデータ)の独占・プライバシーの問題がある
ほげoogleは自由に検索結果をいじれる
中央集権サーバーの存在なしにp2pでそのようなサービスがもし作れたら良いよね
いまのところ実用的なものは存在しない
In the past decade a number of prototype peer-to-peer information retrieval systems have been developed. Unfortunately, none of these have seen widespread real-world adoption and thus, in contrast with file sharing, information retrieval is still dominated by centralised solutions.
コンテンツのクリエイター、そしてその消費者が協力して検索サービスを提供するような世界観、良くない?
We believe users and creators of web content should collectively provide a search service.
とはいえp2pでやろうとすると色々キツイ問題が出てくるよね
計算量、レイテンシーの問題
セキュリティの問題
いままでコンテンツのシェアリングのプラットフォームとしてp2pは使われてきたけど、情報検索のプラットフォームとしては誰も使ってない
この論文はそこに焦点を絞ったサーベイ
※以下ではすべてpeer to peer networkと言ったら情報検索(つまり検索機能をもたせる)を念頭においたものです
peer to peer network overview
challenges
How to make efficient use of resources?
ネットワークのパフォーマンスをいかに高く保つか
もしほげoogleのようなサービスを提供するならば、それ相応のレイテンシーが
How to provide acceptable quality of service?
低レイテンシ、十分なクオリティの検索結果等
How to guarantee robustness?
ダウンタイムや混雑等がない安定したサービスになっているか。
データの汚染、データの欠損からいかにリカバーできるか。
How to provide anonymity?
アプリケーション毎に適切な匿名性を提供しなければならない
検閲、プライバシーの問題を解決
また次のようなピアの行動に対して対処法を持っていなければならない
Churn
p2pは基本的にネットワークの 参加 / 脱退で負荷がかかる
join, leaveを繰り返してネットワークに負荷をかけることをchurnと呼ぶ
Malicious behaviour
無駄なデータを入れる
大量のノードを支配してルーティングテーブルを支配
悪意ある応答をする
を防がなければならない
また、応用からの文脈からは離れるが、以下のような研究課題もあるため、適切な学術的な発展が難しい
シミュレータの作成
データセットの作成から評価まで行えるフレームワークの作成
標準データセットの作成
異なるネットワーク構造の間の評価
peer to peer network tasks
検索可能なp2p networkには以下の3つのタスクが存在する:
searching
クエリに対して、該当するデータへのポインタ(WEBの検索エンジンならurl, ipfsならデータのハッシュ値)を返却
Locating
与えられたポインタを解決する
urlなら実際のhtmlをサーブしているサーバーのipアドレスとポートを取得する
ipfsならハッシュ値に対応するデータ(の各断片)を持っているノードのipアドレスとポートを取得する
Transferring
実際に実体をダウンロードする
これらがすべてp2pのネットワークで行われるとは限らず、それは実装方法やアプリケーションに依存する。
例えばほげoogleの検索エンジンをp2pだと仮に仮定した場合 searchingでurlのリストを受け取ったあと、
urlのlocatingはDNSサーバがやってくれる
Transferringは自身のPCと対応するサーバーのHTTPクライアントが行ってくれる。
重要なのはsearchingとLocation/Transferringは本質的に異なるという点(分離可能)。
以下個人的なコメント: mathetake.icon
例えばipfsは現状でlocating, transferringまでipfsのp2pネットワークで完結するが、searchingの機能は持っていない
が、searchingはそれらとは分離可能であるので、ipfsのネットワークに別のレイヤーを用意して検索可能性をもたせる、ということも可能なはず
searchable peer to peer network
p2pのアーキテクチャの選定には複数考えなければならないことがあるが、そのうちの一つが 検索機能をどう持たせるかという点
検索が可能であるためには、索引(インデックス)を作成・保持する必要がある
文書検索(広い意味でウェブの検索)であれば転置インデックスが主流
広い意味で一番素朴なdistributed hash tableもインデックスである
{コンテンツのハッシュ値 -> コンテンツ}というインデックスを保持している
どのようなアプリケーションにおいても、レイテンシーは極めて重要な課題である。ほげoogleはミリ秒の世界でレスポンス。
レイテンシに一番効いてくるsearchingのサブタスクは以下のようなものがある
indexing
誰が索引を作るのか?
誰が更新をするのか?
どこに索引が保持されるのか
DHTで持つ?とか
索引を実際に保持するピアはそうではないノードに比べて負荷が大きいことに留意
巨大な索引を分散で持つのもありえるし、各ノードが独自に索引を保持することもありえる
細かいアーキテクチャの分類は後ほど
Query Routing
クエリに応答するためにどのようにピアを巡ればよいのか
もちろん多くのノードが関われば関わるほどきつくなる
Query Processing
実際に索引結果を使って最終的にリストを作成する
誰がそれを行うのか?どのように行うのか?ランキングはどうするの?
searchable peer to peer network architecture
ここでは検索の索引をどのように保持するかという点で、4つの具体的なネットワーク構造を紹介
図を見ながら読むとわかりやすいと思います
https://gyazo.com/21cb0587075c14b22adf109aa720aafe
Central Global Index
central global indexはその名の通り、一箇所のサーバー(ならびにサービス)に検索のインデックスが集中管理されているネットワーク
ユーザー同士がp2pでファイルを共有するが、そのファイルの情報はNapsterの中央サーバーにより管理され、検索等が可能になっていた
それによりNapsterはマネタイズ
ある意味でほげoogleもこのようなモデル
$ O(1)で検索が可能だが、単一障害点になってしまったりするのであまり良くない
Distributed Global Index
distributed global indexは、ネットワーク全体で一つの索引を管理するようなネットワーク
基本的な分散ハッシュテーブルで索引を管理するようなネットワークはこれに該当
ある意味でipfsもこれに該当
分散で一様に管理した場合、基本は$ \log(N)の計算量がかかってしまう($ Nは参加しているノードの数)
皆で常に同じ(巨大な)単一の索引を保持すれば$ O(1)となるが(そのような構造をReplicated Global Indexと呼ぶらしい)、それではスケールしない(普通にメモリに乗らない)。
Strict Local Index
strict local indexでは各ノードがそれぞれ独自の索引を保持する
検索時は閾値回数までノードをホップして索引を探して検索結果を返す
Gnutellaでは各クライアントノードがローカルのファイルをインデクシングして索引を保持している
もちろんglobal系に比べてこの種のネットワークの検索の質は低いし、スケーラビリティがないことが実証されている (特定のノードにアクセスが集中したりする. 一様ランダム性がないので。)
が、一方でlow latency。(ホップ数の閾値でバウンドできる)
加えて索引のメンテナンスがローカルで完結するのでcheap
Aggregated Local Index
aggregate local indexでは、各ノード(leaf)はsuper peerに割り当てられる
各super peerが自身が担当するノードのインデックスをaggreagte
その上で定期的に他のsuper nodeとやりとりをしてインデックスを更新していく
leaf <-> super nodeのやりとりが頻繁に発生するのでそこがオーバーヘッドとなる
superノードが単一障害点になってしまう(悪意があるときどうするの?とか)
peer to peer information retrieval
peert to peer information retrieval network (indexを備えたp2p)では、各ノードに対して検索のクエリを発行できる
その結果の種類によって次の二種類に分類できる
検索結果が最終的なデータへのポインタのリストになっている
ウェブの検索エンジンはこれに該当
検索結果はurlであり、実際のデータ(htmlファイル)へのポインタ
データそのものの管理がp2pのプロトコルのその側にあるのでexternal document referencesと呼ばれる
検索結果がデータそのもののリスト
ipfs等のファイル共有ネットワークはこれに該当
データの管理もp2pのプロトコルの内側にあるので internal document references と呼ばれる
Comparison with Federated Information Retrievals
https://gyazo.com/dd697b43ab1c6373547471c99dda6322
Federated Information Retrieval = centeredなクラスタ上の分散処理で行う情報検索
ほげoogleのような巨大システム
👆の図はクエリの処理の流れを表している
クライアントからmediatorにアクセスが行き、そこから分散で管理されたインデックスにリクエストがいき、最終的にマージして検索結果がクライアントに返される
strict local indexに似ている
以下ではこのFederated Information Retrievalとp2p information retrievalを比べる
類似点
resource description problem
それぞれのpeer/nodeがどのようなデータを保持しているかどうかをmediator(クエリを受け付ける人) は知っていなければならない
DHTであればアドレス空間とrouting tableを最新に保つとか
federatedの場合は、どう水平分割されているかの情報を保持しておくとか
collection selection problem
resource descriptionをもとに、実際にどのnode/peerにクエリを発行するのか、その決定をする必要がある
result merging problem
実際に受け取った複数の検索結果をどのようにマージするか、と言う問題
どのようにランキング付をして、どのように足切りして、duplicationを判定するのか、とかそういう問題
異なる点
各nodeはインデックスを処理するだけでなく、federatedでいうmediatorの役割もしなければならない
単一のmediatorは用意しない
インデックスの結果を信用できるとは限らない
federatedの場合はmalicious nodeは存在しないと仮定して良い(でないとアカン)
THE FUTURE OF PEER-TO-PEER INFORMATION RETRIEVAL
Challenges
Latency
ミリ秒の世界で検索結果は返さないといけないよね
たくさんのノードが処理に絡めば絡むほどレイテンシーが上がる
分散でインデックスを管理しているということはたくさんのノードが絡まないと検索結果はしょぼい
Freshness
検索結果をどうフレッシュに保つか
クローラーを各ノードで動かす?
Evaluation
ランキングをどうつくるか
分散のPageRank計算?
mathetake.icon >security
mallicious behaviorをどう検知するか?
インセンティブ設計とかどうすれば?
広告収入のレベシェアとか?
Key Focus Areas
global indexとlocal indexの強みを融合させる
load balancingを意識
キーを分散しても、特定のインデックスにアクセスが集中とかは全然あり得る
キャッシュの機構をいかにセキュアに作るとか、そういうの
Focusing on search results
ランキングはやはり重要
これがfederatedな既存システムの強み
Developing real-time distributed relevance-feedback mechanisms
ユーザーの行動ログをランキングに反映させるfeedbackのメカニズムを入れる
これもセキュアにしないとSEOハックされてしまう
Applying clustering at various levels
as it simplifes both the construction of resource descriptions and query routing, resulting in reduced latency.
所感
mathetake.icon< 考えるべきことが多すぎてマジでムズイ
mosa_siru.icon < つらみとむずさに対してうれしみが少ない…