Distributed Hash Table and p2p Search Engine

この記事はなに

ipfsにsemantic searchの機能を持たせるにはどうしたらいいかと考えていたら、分散ハッシュテーブルと検索エンジンの関係性は思っていた以上に技術的に深く、面白い話題だということに気が付いたので、そのリサーチメモ。

IPFS上の検索エンジンは(今の所実用的なものは)存在しない、というのが結論です。

Searching the Distributed IPFS Web

https://blogs.cornell.edu/info2040/2016/10/24/searching-the-distributed-ipfs-web/

👆このブログ、かなりエモくておすすめです

IPFSのフォーラムの関連するディスカッション

https://discuss.ipfs.io/t/any-suggestion-to-make-ipfs-content-searchable-addressable-by-a-user-defined-tag/827/2

https://discuss.ipfs.io/t/decentralized-search-engines-for-the-decentralized-web/629/10

Understanding how the DHT is implemented

https://github.com/ipfs/go-ipfs/issues/1396

Distributed search on IPFS

https://gist.github.com/RangerMauve/81432928f7aa85086884f083bde1e093

Indexing content addressable and linked data

https://github.com/gpestana/notes/issues/6

分散ハッシュテーブルの復習

kademlia, s/kademlia, ....

分散ハッシュテーブル上の検索

exact matchとその問題点

関連研究

range-query等

ipfsとipfs-search

decentralized search engineのサーベイ

DHT(Distributed Hash Table)の復習

DHT(Distributed Hash Table, 分散ハッシュテーブル)とは、peer2peerなネットワークで一つのハッシュテーブルを管理、つまりキーを分散させて管理するためのアルゴリズムなり、ネットワークの構造のこと

ハッシュの値は有限(具体的なハッシュ関数によるが256bitなり160bitなり)なので、以下のような図を考えるとわかりやすい

https://www.cs.rutgers.edu/~pxk/417/notes/images/dht-dynamo-vnode.png

円状に分散しているキーを各ネットワークノードが分散で管理している様子がわかる。

例えばIPFS(shuntak.iconさんの資料: IPFS) であれば、ファイル(なりそのチャンクなりディレクトリなり)が円周が$ 2^{260}である円上の各点に対応していて、それをどのように各ノードが管理(保管)するのか、のような問題。

もちろん特定のキーに対応するバリューを取り出したいユーザーは、ある特定のノードからp2pネットワークにアクセスし、探しているキーを保有するノードを探さなければならない。そのための効率的なキーの配置や高速にキーをlookupするためのアルゴリズムも備えていなければならない。

まとめると、DHTとは

p2pオーバーレイ・ネットワーク(物理的なノードの配置から独立した、上の円周のような仮想的なネットワーク)で

キーのregister, lookupの効率的なアルゴリズムを備える

スケールする・単一障害点がない設計

探索アルゴリズムの計算量がデータ量に依存しないのが主流

等の性質を持つものである。

kademlia https://en.wikipedia.org/wiki/Kademlia

kademlia はおそらく最も有名なDHT(の仕様)の一つ。👆で紹介したような円周ではなく、binary tree上にハッシュを配置している。IPFSはこれをベースにしている。頻繁にノードが入れ替わることを想定して設計されている(テーブルの更新性・対称性等)

ノードIDやkeyは(SHA1を想定して)160bit

２つのノードまたはkey$ x, yに対して、それらの間の距離をXOR演算で定義: $ d(x, y) := x \oplus y

各ノードは自分自身との距離が$ 2^i \sim 2^{i+1}であるような160個のリストを常にメモリに持っておく

リストの長さはパラメータとして事前に決められている$ Kで、交信があった新しいものの中から$ K個保持しておく

具体的には$ K = 20とする場合が多いらしい

言い換えると、$ 2^i \sim 2^{i+1}に対応するリストにあるノードは、自分自身のノードIDとビット数が$ i個違う

K bucketと呼ぶらしい

https://gyazo.com/278f2c03e7450f0a484a6a2c8bb99ee3

キーペアは、キーに距離が近い$ K個のノード保存される。

特定のキーを検索する手順は以下のよう $ O(\log N):

自信のノードIDと、キーの距離を計算

その距離に対応するk bucketを探す

https://gyazo.com/fbc2f7536c4d78dd320e056acdf9ebad

そのk bucketの中のノードIDとキーとの距離を計算

距離が小さいものから(事前に決めてあるネットワークのパラメータである)$ \alpha個のノードをピックアップ

その$ \alpha個のノードに対してkeyの検索リクエスト。

以上を各ノードで繰り返す…

https://gyazo.com/e77c8436e89c51b986dc8eee531a28c3

Chord https://ja.wikipedia.org/wiki/Chord

Chordはkademliaの少し前に発表されたDHT

kademliaとは異なり、データ構造は最初に出てきたように円周の形をしている

kademliaと同様に、ノードは160bitのノードIDを持ち、円周上に配置される

配置した上で、自分自身のノードからの$ 2^m足した各点からスタートして時計回りに一番近いノード(successor)の情報を保持しておく(kademliaでいうk bucketの役割。routing tableと呼ぶこともあるらしい)

https://gyazo.com/b8e424cd7940f86b79b093ac634551c7

キーペアを保存する場合は、キーからスタートして時計回りに一番近いノード(successor)を👆のrouting tableを辿って探してそこに保存する ($ O(\log N))

検索も同様にrouting tableを辿って探す

CAN https://en.wikipedia.org/wiki/Content_addressable_network

can = content addressable network

chordが一次元だったのに対して、CANでは二次元のアドレス空間を持つ:

https://gyazo.com/be9c015c5c61f9defc9b358b8613d2c7

👆のように、各ノードは四角形領域を担当する

routing tableとして四辺が接するノードの情報を保持しておく

2つのハッシュ関数$ h_x, h_yを用意

アイテム$ Iに対する座標(キー)を $ (h_x(I), h_y(I)) として、👆のルーティングテーブルを辿ってその担当領域に座標を持つノードがアイテムを保持する

https://gyazo.com/715df5c99890fc6c01d8126462e891ae

分散ハッシュテーブル上の検索

exact matchと問題点

ここまで出てきたDHTは、検索に関してキーのルックアップ機能しかもたない

言い換えるとkeyがexact matchする場合のみ値が得られる

一方で「○○という単語を含む文書」をN件探したいのような、実用的な機能は備えていないことがほとんど　

DHT上の検索アルゴリズム(search oriented modification)

DHTに対してexact matchだけでないクエリを処理する機能を持たせようとする研究もいくつかあったので紹介。

Complex Queries in DHT-based Peer-to-Peer Networks(2002)

This paper outlines a research agenda for building complex query facilities on top of these DHT-based P2P systems.

https://www.cs.utexas.edu/~browne/CS395Tf2002/Papers/ComplexQueries-StoicaEtAl.pdf

データに紐づくメタデータ(名前、時刻etc)に対してクエリを投げられるようなレイヤーを作ろう的な取り組み。

先駆け的で重要な論文だが、これを引用している論文は2014年以降で15件しかない

https://scholar.google.co.jp/scholar?as_ylo=2014&hl=ja&as_sdt=2005&sciodt=0,5&cites=5892488670971274430

それだけ研究が下火だというのがわかる

Prefix Hash Tree An Indexing Data Structure over Distributed Hash Tables (2004)

https://www.csie.ntu.edu.tw/~b91055/PHT.pdf

Preifx Hash Tree() というデータ構造を提案し、それを用いる。

一次元のRangeクエリを投げることが出来る:

キー $ L, H \ (L \leq H) に対して $ L \leq H \leq Kとなるキー$ Hを検索することが出来るデータ構造

文書検索とかの文脈だとあまり意味がない…

DHTs over Peer Clusters for Distributed Information Retrieval (2007)

http://www.softnet.tuc.gr/~papapetrou/publications/SiberskiWPeerClusters.pdf

インデックスの管理をすべてのピアがやるのは辛いから、クラスタリングして一つの代表のピアがクラスタ内でのインデックスをまとめてパブリッシュしようね、的なやつ

Efficient Indexing of the BitTorrent Distributed Hash Table (2010)

https://arxiv.org/abs/1009.3681

BitTorrentのKademiliaが用いられているDHT層のインデックスを作ろう、という話(Student Research Projectらしい)

BitTorrentクライアントのプラグインとして実装した(らしい)

BitTorrentはデフォルトでネットワークでやりとりされているノードを収集出来るらしく、それを使っているっぽい

DART: Distributed Adaptive Radix Tree for Eicient Aix-based Keyword Search on HPC Systems (2018)

http://delivery.acm.org/10.1145/3250000/3243207/a24-zhang.pdf

HPCみたいなスパコン環境だと、データは分散で持つしデータ量が尋常じゃない。そういうときにいわゆる転置インデックスで検索エンジン作ってもちょっとパフォーマンスでないよね、というモチベーションでDARTというデータ構造を提案

ちょっとp2pの文脈からは離れてるが重要っぽさはある

見てわかるように、オブジェクトストレージとしてのDHTの上に検索のレイヤーをもう一段作る、というのが筋が良さそう。

そもそもhashのキーに対してフレキシブルに検索をかけられるようにハッシュを設計する、というのは筋が悪い。そもそもハッシュって情報を落として一次元で検索するためのものなので。

ipfsとipfs-search

IPFSは優れたDHTの一つで、効率的にファイルを分散保持できる分散オブジェクトストレージである。

が、一方で既存のDHTと同様exact match以外の検索の機能は存在しない。

なので、現状は以下のようにして自前でインデックスを作るしかなく、筋が悪い

Writing a Simple IPFS Crawler

https://gkbrk.com/2018/03/writing-a-simple-ipfs-crawler/

IPFSのオブジェクトに対するクローラをどう作るかという記事

現状は

ノードを自前で立ててネットワークに参加

その上でロギングしてオブジェクトのハッシュを取得

取得したハッシュに対応するオブジェクトを解析してインデクシングする

ipfs-search https://ipfs-search.com

ipfs-searchはIPFSに対して検索エンジンを作ろうとしている唯一の取り組み

OSSでコードが公開されている

https://github.com/ipfs-search/ipfs-search

ほぼ一人でメンテ

クローリングしたインデックスをIPFSに保存してそのハッシュを保持しておく

完全に中央集権的で、筋が悪い感じが…

普通にメンテつらそう

decentralized search engine

一方で、decentralized Googleを作ろうという取り組みは結構たくさんある。

(広い意味で転置インデックスを管理するDHTもこれに含まれるのでそれもリストアップ。)

Distributed Search Engine

wikipedia: https://en.wikipedia.org/wiki/Distributed_search_engine

p2p foundation : http://wiki.p2pfoundation.net/Distributed_Search_Engines

Reserch papers

Building a Distributed Full-Text Index for the Web (2001)

http://infolab.stanford.edu/~byang/pubs/tois01.pdf

Efficient Peer-to-Peer Keyword Searching(2003)

https://piki.org/patrick/papers/search.pdf

Towards a Fully Distributed P2P Web Search Engine(2004)

http://security.riit.tsinghua.edu.cn/share/Towards.pdf

Survey of research towards robust peer-to-peer networks: Search methods(2006)

http://www.cs.umd.edu/projects/p2prg/p2p-overview.pdf

Survey of Search and Replication Schemes in Unstructured P2P Networks(2010)

https://arxiv.org/abs/1008.1629

Censorship-Resistant and Privacy-Preserving Distributed Web Search(2014)

https://www.esat.kuleuven.be/cosic/publications/article-2422.pdf

This paper presents a blockchain-based keyword search called Searchain that aims to enable oblivious search over conditional keyword privacy in the decentralized storage

Decentralized Web Search(2012)

https://uwspace.uwaterloo.ca/handle/10012/6795

どこかの学生の修論。各Web ServerにP2Pのネットワークに参加してもらう前提で話をしていて、まあ無理やなという

GENAUM: NEW SEMANTIC DISTRIBUTED SEARCH ENGINE (2017)

https://www.riverpublishers.com/journal/journal_articles/RP_Journal_1550-4646_1333.pdf

Despite their diversity, none of distributed search engines is able to reach a sufficient level of quality and efficiency, to really compete with traditional search engines.

Gnutella(2000)

https://ja.wikipedia.org/wiki/Gnutella

Gnutella（グヌーテラ、ニューテラ）はP2Pプロトコルおよびファイル共有クライアント。

p2pファイル共有 + メタデータに対して検索がかけられる

ユーザの裾野が広がるにつれ、システムの重大な問題が取り沙汰されはじめた。ネットワークはPINGリクエストで溢れかえり、同時に非常に多くの検索クエリーで高負荷になった。

ネットワーク管理者のためのGnutella入門

http://www.atmarkit.co.jp/fwin2k/experiments/gnutella_for_admin/gnutella_for_admin_0.html

余談

作者(25歳)はうつ病で自殺したらしい

Gnutellaでググると昔懐かしいウェブが見られる

Faroo(2005)

https://en.wikipedia.org/wiki/FAROO

独FAROO、完全分散型P2Pサーチエンジンのベータテストを開始

https://internet.watch.impress.co.jp/cda/news/2007/09/19/16931.html

Seeks(2005)

https://en.wikipedia.org/wiki/Seeks

https://github.com/beniz/seeks

yacy(2006)

https://yacy.net/en/index.html

YaCy（ヤシー、ヤスィー）とは、「人民による人民のためのウェブ検索」を標語する、オープンソースの分散型検索エンジンである。

おそらく最大級のp2p検索エンジン written in Java

Description of the YaCy Distributed Web Search Engine

https://www.esat.kuleuven.be/cosic/publications/article-2459.pdf

YaCyのシステムのオーバービュー。結構詳しく書いてある

DHTで検索のインデックスを共有

最初はローカルのブラウジングをプロキシして、URLを収集・インデクシング

一定以上溜まったらgreedyにクローリングするモードに入る

ランキングはクライアントが独自で付けられる

検索ログは取られないのでprivacy preserving

Searchain(2017)

Searchain: Blockchain-based Private Keyword Search in Decentralized Storage

http://epubs.surrey.ac.uk/842634/1/Searchain%20%20Blockchain-based%20Private%20Keyword%20Search%20in%20Decentralized%20Storage%20.pdf

In this paper, we introduce Searchain, a blockchain-based keyword search system.

Desearch(2018)

https://desearch.com/

ブロックチェーンbasedなdecentralized検索エンジンらしい

BitClave社によって開発されている: https://www.bitclave.com/

only for crypt related searching っぽい

Our search engine is optimized to aggregate cryptocurrency news from trusted and relevant websites.

ホワイトペーパーとかがないからちょっと怪しい

QueenBee(2018)

ペーパー: Decentralized Search on Decentralized Web (2018) https://arxiv.org/abs/1809.00939

Eth上のスマコンとipfsを組み合わせて参加ノードにインセンティブを与えつつ、みたいな検索エンジンを作ることを提案

PoCはある(ipfs上でホストされている)

http://ipfs.io//ipns/QmZkAQebh5CWvsayZNneejVEPVpk1jQPnt1pUphTJQ8g6M/queenbee.html

が、ページ数少なすぎるし技術的にちょっと怪しい…

とはいえこれが一番ナウくて新しい

Tribler (2005~)

公式: https://www.tribler.org/about.html

https://gyazo.com/affa65188582846505b5b2d7b2cd85e5

wikipedia: https://en.wikipedia.org/wiki/Tribler

github: https://github.com/Tribler/tribler

オーバービュー: Open Source Column: Tribler: P2P Search, Share and Stream

http://sigmm.org/records/records1201/featured03.html

今最も活発に開発されている(last updated: October 9, 2018)

BitTorrentのプロトコルを改良して、ファイルシェアリングだけじゃなくてその上で検索もかけられるようにしている

加えてvideoのストリーミングも行えるようにしたらしい

Gossip Protocolというものを使っているらしい

https://ja.wikipedia.org/wiki/ゴシッププロトコル

分散DBにおける有名なアルゴリズムっぽい(知らなかった)

Tribler is a research project of Delft University of Technology. Tribler was created over nine years ago as a new open source Peer-to-Peer file sharing program. During this time over one million users have installed it successfully and three generations of Ph.D. students tested their algorithms in the real world.

ヤバイ: Our ambition is to make darknet technology

Roughly 10 to 15 scientists and engineers work on it full-time. Our ambition is to make darknet technology, security and privacy the default for all Internet users. As of 2017 we have received code from 56 contributors and 146.003 lines of code.

強い

Today Tribler is robust: "the only way to take Tribler down is to take The Internet down"

IPFS(DHT)上のp2p(decentralized)検索エンジンを作る上での障害

データ量と検索のフレキシビリティが正の相関

データ一つ一つに対してtagを付けたりなんなりすると、それだけ検索のフレキシビリティが上がるが、それと同時に容量も食う

distributedな転置インデックスのようなものを作ってもよいが、悪意あるノードが大量にゴミを挿入することが考えられる

yacyはそれを防ぐような仕組みが一切ないらしい

https://news.ycombinator.com/item?id=11956268

今であればマイニングベースにしたりとかで色々プロトコルで解決できそう

インセンティブ設計がムズイ

インデックスが似たコンテンツで溢れかえってしまう

IPFSはほとんど同じコンテンツでも、1バイトでも異なれば違うアドレスになるので。

ランキングアルゴリズムが、centralizedなものに比べて圧倒的にしょぼくなってしまう

ユーザーの行動ログ等が上手く集められない

Google, Yahoo, Bing等と戦うには、かなりの低レイテンシーを求められる

Distributed indexing and decentralized searching of the Web are very difficult to achieve given the bandwidth limitation and response time constraints. In addition to indexing and searching, a distributed web search engine should be able to rank the search results in a decentralized manner, which requires global knowledge about the hyper-link structure of the Web and keyword-document relevance. Predicting such global information based on local knowledge only is extremely challenging in any large scale distributed system.

所感

思っていた以上に深い話題だった

IPFS上の、とかを抜きにしてめちゃくちゃおもしろい課題

現状上で上げた問題点解決するプロトコルは誰も提案していないというのもまた

研究がかなり下火になっている(関連論文が圧倒的に少ない)

p2p全盛期(2000年代初期から中期)を過ぎるとピタッと論文がなくなって楽しい

普通にコンピュータサイエンス的に楽しい

ブロックチェーンと、分散検索エンジン(分散インデックスの管理)は少し求められる性質が違う

後者は状態遷移をグローバルで共有しなくても問題ない

無駄を取り込むことさえ防ぐことができればおｋ

よしななタイミングで分散しているインデックス(keyword -> urlの配列)をマージできればおｋ

一方でマイニングやzkProofなど、分散検索エンジンに取り入れることができそうなところもある説