peer-to-peerはGoogleの夢を見るか

How to build a decentralized Google

Takeshi Yoneda
Dec 17, 2018 · 20 min read

こんにちは。@mathetake(https://twitter.com/mathetake)です。この記事はGunosy Advent Calendar 2018 18日目の記事です。他の皆さんは会社の公式ブログに書いていますが、今日は個人のmediumからお送りします。(完全に趣味エンジニアリングの内容なので公式ブログは自粛しました)

はじめに

最近あるきっかけがあって、不特定多数の(悪意を持つかもしれない)ノードが参加するpeer-to-peerネットワーク、より正確にはpeer-to-peer ネットワーク上のオブジェクトストレージに対して

  • 検索の機能をどのようにもたせればよいか
  • 情報検索の機能をどのようにもたせればよいか

という簡単に思えて実は非常に難しい問題について論文を読み漁って考えていました。その過程で作ったのが、先日私が公開したdoogleというOSSです:

doogleは分散ハッシュテーブル(後述)を用いてWeb Pageの転置インデックスをp2pネットワークで共有し、WEBクローラーおよび検索エンジンとしての機能を備える (自分自身の勉強のために実装したという意味で)お遊び的かつ簡単なGo言語製のソフトウェアです。

doogleを作る過程でp2p×情報検索の文脈の情報の少なさを感じ、この分野にふれるキッカケが作れたら良いなと考えこの記事を書いています。より具体的に以下では

  • peer-to-peerネットワークとは何か
  • 基本的なネットワーク構造である分散ハッシュテーブルとは何か
  • 検索エンジン×peer-to-peerの歴史とその課題
  • doogleの裏側のアルゴリズム

といった事柄について初心者にもわかりやすく入門的に解説していきます。

Introduction to peer-to-peer network

まずここでは簡単にpeer-to-peer(以下, p2p) networkについて簡単におさらいしておきます。

p2pネットワークはクライアント/サーバモデルとの対比の文脈でよく解説されるので、まず先にそちらを説明します。クライアント・サーバモデルはコンテンツを受け取る側(クライアント)とコンテンツを提供する側(サーバー)で役割を分離したコンピュータネットワークのモデルです:

クライアント・サーバモデルの概念図

現在世間一般で使われているアプリケーションの大部分がこのようなクライアント・サーバーモデルのクライアントとして提供されています。(一部、skypeのようなp2pとクライアント・サーバモデルを組み合わせたようなものもあります)。例えば私達がGoogleに代表される一般的な検索エンジンを利用してWEB上で調べ物をする場合もこのモデルに基づいています:

クライアント・サーバモデルの例

この場合、我々ユーザーのスマートフォンやコンピュータはクライアントとしてネットワークに参加し、サービスを提供する企業なり団体が用意したコンピュータがサーバーとしてネットワークに参加します。このように、クライアント・サーバモデルでは、ネットワークに参加するノード(参加者)に(クライアント・サーバーといった)役割分担が存在しています

一方で、p2pネットワークネットワークのプロトコルに参加するノード に役割分担が存在しないようなコンピュータネットワークのモデルを指します:

p2p ネットワークの概念図

図のように、中央のサーバー(コンピュータが存在せず)ネットワークに参加するノードが共通のプロトコルで相互に通信しあうネットワークです。特にこの記事では、不特定多数の(信頼できるかもわからない)ノードが参加するようなパブリックなp2pネットワークのことを考えます。

例えばレートの乱高下で近年話題となっているブロックチェーン、特にBitcoinEthereumなどのパブリックチェーンはこのようなp2pネットワーク上に実装された代表的なアプリケーションの一つです:

パブリックチェーンと参加ノードと通信するクライアント

主要なパブリックチェーンでは、参加するノードそれぞれがブロックチェーンのプロトコルに基づいて合意を取りながらマイニング・通貨の送信の処理を行っており、中央でそれを管理するサーバーが存在しません。

実際にデジタル通貨を利用する際は、図にもあるように、ユーザーはパブリックチェーンに参加する任意のノードとクライアント・サーバモデルに基づいて通信 してトランザクションを発行しますが、それはp2pネットワーク(としてのパブリックチェーン)の外側の話です。

また別のp2pネットワークを用いたアプリケーションの代表的な例として、私が検索エンジン×p2pに興味を持ったきっかけとなったipfs(InterPlanetary File System)があります。

ipfsは不特定多数のノードが参加するp2pネットワーク上に構築された分散オブジェクトストレージで、コンテンツアドレッシング、つまりオブジェクトのハッシュによりその配置(アドレス)が決まる、という特徴を持っています。大きなサイズのオブジェクトはチャンクに分割され、それぞれのチャンクのハッシュがそのアドレスとなり、アドレスに応じて個々のチャンクがネットワークで分散管理されます。そのため必然的に単一障害点(Single Point Of Failure)を持ちません。

例えばipfs.ioから始まる こちら のアドレスにアクセスすると、皆さんご存知Lenaさんの画像が表示されますが、それはipfsのネットワークで分散的に保存された画像に対して、ランダムなノードにその集約とダウンロードを依頼したことを意味します。

ipfsのように、p2pネットワーク上でオブジェクトを管理し集約(ある意味で検索)の機能をもたせるのにはそれなりの技術が必要となるのですが、ipfsでも使われているデータ構造(というよりネットワーク・プロトコル)の代表的なものとして、分散ハッシュテーブル(Distributed Hash Table)と呼ばれるものがあります。

Distributed Hash Table

分散ハッシュテーブル(Distributed Hash Table)とはその名のとおり、分散でハッシュテーブルを構成・機能させるp2pのネットワークプロトコルを指します。

例えばsha1関数をハッシュ関数に用いた場合、0から2¹⁶⁰-1までの160bitのアドレス空間がハッシュテーブルに対応するわけですが、それをネットワークに参加するノードで分担して管理します:

分散/非分散ハッシュテーブルの違い

図のように、分散ハッシュテーブルが用いられたp2pのネットワークでは、各ノードがハッシュテーブルのアドレス空間を分担で担当します。その際、それぞれのノードに対してもアドレスが割り当てられます

ipfsではこのハッシュテーブルのValueにオブジェクトを格納し、分散KVSとして分散オブジェクトストレージを実現しています。

もちろん、ipfsの利用者は特定のノードからアクセスするわけですが、その際に目星のアドレスをそのノードが担当している保証はありません。そのため分散ハッシュテーブルでは必然的にアドレスのlook upの機能を持っています。より具体的には、多くの分散ハッシュテーブルではプロトコルレベルで主に次の3つのRPCを備えています:

  • STORE … ノードに <address, value>ペアの格納を指示する
  • FIND_NODE … 与えられたアドレスに対して、自分が知っている中で一番アドレスの距離が近いノードを返す
  • FIND_VALUE … 与えられたアドレスに対するvalueを持っていた場合は返却し、そうでない場合はFIND_NODEの結果を返す

これらの機能を備えているため、分散ハッシュテーブルでは分散でアドレス空間を管理していながらもキーの検索・取得が可能となっています。どのようにこれらが実装されているのか、ipfsの基礎となっているKademliaという最もメジャーな分散ハッシュテーブルの場合に見ていきましょう

Overview of Kademlia

Kademlia(論文: https://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf) では、上述のsha1ハッシュ関数を用いて160bitのアドレス空間からなるハッシュテーブルをネットワークに参加するノードが分散で管理します。以下ではアイテムと言えば(address, value)のペアを指すこととします。

Kademliaでは他のDHTと同様に、各ノードに対しても160bitのアドレスが割り当てられます。そのため (ノード, アイテム), (ノード, ノード)の間の距離をXOR演算で定義することができます。

例えばアドレスが 0b0000のノードとアドレスが 0b1000であるようなアイテムの距離は

のように計算できます。この“距離”を用いて近い・遠いの概念を分散ハッシュテーブルのアドレス空間に導入することができます。

想像に難くないように、Kademliaではこの距離の意味でアイテム近いノードがその格納を担当します。(STORE命令の対象の選び方)

また、そのようなプレイスメントを実現するためには、各ノードはある程度自分以外のノードのアドレスを保有していなければなりません。そのためのデータ構造をrouting tableと呼びます。

Kademliaにおける各ノードのルーティングテーブルは、今まで自身が通信したノードの情報(ip address, port, etc.)から構成されるのですが、特に自身とのXO距離によって分類して保持しています。より具体的にはXOR演算後のmost significant bit毎に配列作り、それぞれ最大 K個保有しています:

Kademlia: A Peer­to­peer Information System Based on the XOR Metric より

各bitに対応する長さKのリストはそれ故Kbucketと呼ばれています。

FIND_NODEリクエストはこのルーティングテーブルを用いて、1. そのリクエストがあったアドレスと自身とのXOR距離を計算 2. most significant bitを算出し対応するバケットをみつける 3. 該当バケットの中で最もアドレスがリクエストされたアドレスに近いノードを割り出す、といった手順で処理されます。FIND_VALUEリクエストも同様に処理されます。

以上がKademliaのアルゴリズムの概要です。詳しくは論文を御覧ください: https://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf

Search engine meets peer-to-peer

ここまでの話を振り返ります: まず始めにp2pネットワークの基本とアプリケーションの一つである分散ジェクトストレージipfsを紹介しました。その後、その背景にあるネットワーク構造である分散ハッシュテーブルを紹介しました。分散ハッシュテーブルではアイテムの保存だけでなく、ルーティングテーブル, ノードのアドレス空間上の配置, そして距離関数をうまく定義することでキーの完全一致検索を効率的に可能にしていることを紹介しました。(この意味で、分散ハッシュテーブルはp2pネットワーク上に作られる情報検索の機能を兼ね備えたストレージと言うことができます。)

分散ハッシュテーブルに限らず、より一般にp2pと情報検索が交わる研究分野は、2000年代前半から中盤にかけて活発に行われていたようで、代表的な論文をサーベイしてまとめました:

特に Peer-to-Peer Information Retrieval: An Overview (2012)というサーベイ論文は素晴らしく興味がある方は一読をおすすめします。とはいえ2012年のこの論文以降、観測範囲ではあまり良い論文が見当たらず、研究が下火となっていることが感じられました。

そろそろ本題に入るために、以下では情報検索の中でも特に、検索エンジンに絞って話していきます。

そもそも(文書,WEBページ,音楽, etc. を問わず)検索エンジンとは、インデックス(索引)を作成・保持し、ユーザーからのクエリを受け取った際に索引を参照することで該当する情報をユーザーに返却するソフトウェア並びにサービスのことを指します:

検索エンジンとインデックス

例えば↑の図は簡単なWebページの検索エンジンを使うユーザーからのリクエストを処理の流れです。この裏側ではIndexを作成するクローラーや、ランキングの元となるスコアリングを行う処理も走っています:

検索エンジンの裏側

ここで述べている検索エンジンの仕組みは非常に簡単なものですが、GoogleやBingなどの巨大なウェブサービスも基本的にはこのような仕組みで動いています。ただ、これらの検索エンジンはその検索の対象へのポインタを集めてスコアリングしているだけで、その実物は所有していない、ということに注意してください。これはWEB検索エンジンの場合、URL(特定のサーバ並びにそのリソースへのポインタ)を集めて索引を作っているだけで、実体となる静的ファイルをかき集めているわけではない、ということです。

2000年代前半に話題となったNapsterもベースはp2pネットワークですが、そのようなポインタをかき集める検索エンジンとしてモデル化することが出来ます。Napsterは音楽共有サービスですが、Napsterのサーバーにはその実態は存在せず、ユーザー同士が共有するため(検索を含めた)機能を提供しているに過ぎません:

Napsterの簡単な仕組み

Napsterはこのように音楽ファイル共有を促進する検索エンジン作ったわけですが、結果としてアメリカレコード協会(RIAA)などから提訴され敗訴しました。

上で紹介したGoogleやNapsterなどはどれも、インデックスの作成を行う中央サーバーが存在し、そのサーバーがサービスの提供元として機能しています。 そのため(、実際問題として起こっているかは置いておいて、)法律や検閲の取締の対象となり、サービスが制限(またはNapsterのように閉鎖)されてしまう危険が常に存在します。

中央管理者がいると検閲の餌食になるかもしれない

このような中央集権的な検索エンジンの問題点を解決するための一つの手段として、検索エンジンをp2pネットワーク上に構築することが挙げられます。つまり、検索のインデックスの管理を不特定多数のノードで行い、管理の主体を行いようにすることです:

分散ハッシュテーブルによる検索インデックスのイメージ

上の図は、分散ハッシュテーブルを用いたそのような検索エンジンのイメージ図です。 “猫”に対応するインデックスが不特定なノードで管理されている様子がわかります。これにより先程の “にゃん.com”へのアクセスを禁止するような検閲を阻止できます。 GoogleやNapsterなどの検索エンジンがcentralizedなものである事との対比で、このような分散的な検索エンジンをdecentralized search engineと呼ぶことがあります。

Challenges towards decentralized search engines

前のセクションでは中央集権的な検索エンジンの問題点の一つであると検閲耐性について紹介し、それを解決する手段としてdecentralizedな検索エンジンを紹介しました。decentralized検索エンジンは概念としては簡単なものですがが、その実装にあたって、centralizedな検索エンジンを作る際になかった問題点が新たに発生します。ここではその問題点をざっくり紹介します。

Latency

分散管理することになるため、そのルーティングのための計算量がオーバーヘッドとなります。もし分散ハッシュテーブルを用いた場合、基本的なアルゴリズムではO(logN) (Nは参加するノードの数)のルーティングコストがかかることが知られており、そのままではmillisecの世界であるcentralized検索エンジンに対抗するのは難しい。

Freshness

インデックスの更新、削除の反映が分散でやっているが故に反映が遅くなることが考えらる。リンク切れ等のフィードバックが難しい。

Evaluation

一箇所にデータが集められているわけではないので、例えば、リンク構造からなる大域的なグラフを構築することが難しいのでPageRankを正確に計算できない。他にはユーザーの行動ログ等を用いたスコアリングも現実的ではない。それゆえに信頼性のあるランキングを作成するのが難しい。

Security

これが一番の問題点。不特定多数のノードが参加できてしまうので、例えば自身のウェブサイトがランキング上位に来るようにランキングを作成したり、悪意ある検索結果を返すことも可能となってしまう。

Algorithms behind doogle

上述の問題点は非常に難しく、結局のところ、それらを解決するアルゴリズムやプロトコルは現在までのところ誰も発明していません。私が実装したdoogleももちろん解決していません。ですがその足掛けとなるアルゴリズムはいくつか存在しており、その一部をdoogleで実装しています。

local estimation of PageRank

まずひとつ目はworld nodeと呼ばれる特別なノードを用意して部分グラフからPageRankを推定するアルゴリズムです。(論文: Efficient and decentralized pagerank approximation in a peer-to-peer web search network) そのアイデアは簡単で、1. 分散ハッシュテーブルに参加する各ノードが持つ、部分的なリンク構造からなるグラフにworld nodeと呼ばれる特別なノードを追加する 2. グラフに存在しないウェブサイトへのリンクはworld nodeへのリンクであるとしてedgeを追加する。 3.その後通常通りPageRankを計算する、というものです。

S/Kademlia

S/KademliaはKademliaをセキュリティ面で強化したものです。ランダムなアドレスの決定に公開鍵暗号を用いたり、暗号パズル(現代的な言葉で言うとマイニングに相当する)をネットワーク参加の際に課すことで特定のインデックスを汚染したり、ノード同士が共謀することを防いでいます。

例えばdoogleではアドレス生成の際上のように、sha1(address, nonce)のbitが先頭から${difficulty}個がゼロとなるまでハッシュの計算をし続けます。そして得られたnonceが証明書として機能します。

Conclusion

この記事ではdecentralizedな検索エンジンのテーマの元、 p2pネットワークの基本的なところから始め、分散ハッシュテーブルの基本とKademlia、検索エンジンの基本とcentralizedな検索エンジンの問題とdecentralizedにした場合の新たな問題点、そして私が実装したdoogleの裏側にあるアルゴリズムについて駆け足でご紹介しました。

結局の所、decentralizedな検索エンジンを一般ユーザーが満足するレベルで構築するようなプロトコルやアルゴリズムは現状存在しない上に、ここ数年で研究している人もほとんどいなくなってしまった、というのが私の結論です。

ですが、この課題は一つのコンピュータサイエンスの研究課題として非常におもしろく、冬休みの自由研究にちょうど良いのではと感じました。(私自身論文を読み漁り実装していく中で多くのことを学びました。)

この記事が少しでも多くの皆さんにとって、非中央集権的な検索エンジンの未来について考えるきっかけとなれば幸いです。

(ご意見ご感想をTwitterにてお待ちしております!)

References

Takeshi Yoneda

Written by

A yaml engineer https://mathetake.github.io/

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade