ピュア P2P ベースの 完全な2ちゃんねる実装は、 CAP 定理により相当に困難である (追記あり)

本日の [[残念なお知らせ]] (たぶん)

まあ、僕は前々から P2P-based な Web Applciation に興味が有って、今日もふと、

Pure P2P ベースの 2ch 実装って作れないのかなぁ

なんて考えていたのですが 、色々考えた結果、

ピュア P2P ベース の _完全な分散 2 ちゃんねる実装_ は、 [CAP 定理 により相当に困難である]

という結論に達してまいました。ので、今日はその辺りの詳細を忘れないようにメモっておきます。

1. 完全な 2ch 実装では、最終的な読み書きデータに対し、強い一貫性を求められる

まず最初に。

• Pure P2P に限らず分散システムを実装する上で関連する法則というか定理に、

• CAP 定理 - Wikipedia

って言うのが有ります。

これは、上記リンク先の Wikipedia から引用すると、 [[CAP 定理]] では、 [[分散ネットワーク]] を持つ [[ソフトウェア]] では、

[[一貫性]] (Consistency) 全てのノードにおいて同時に同じデータが見えなければならない。

[[可用性]] (Availability) ノード障害により生存ノードの機能性は損なわれない。つまり、ダウンしていないノードが常に応答を返す。 単一障害点が存在しないことが必要。

[[分断耐性]] (Partition-tolerance) システムは任意の通信障害などによるメッセージ損失に対し、継続して動作を行う。 通信可能なサーバーが複数のグループに分断されるケース（ネットワーク分断）を指し、 1 つのハブに全てのサーバーがつながっている場合は、これは発生しない。 ただし、そのような単一障害点のあるネットワーク設計は可用性が成立しない。

の三つの特徴の内、 _[分散システム_ ではその内の二つまでしか実装できない] と定義されています。で、この法則は厳密な数学的証明が 2002 年に証明されています (Wikipedia より)。

で、上記定理を踏まえた上で言うと、少なくとも、2ch ブラウザで 旧 2ch 形式 の dat を読み書きしようと思うと、

一貫性 (Consistency) 全てのノードにおいて同時に同じデータが見えなければならない。

と言う性質を求められます。で、それはなんでかって言えば、 2ch の dat は、レスが削除されたりすると、2ch ブラウザでは再読み込みが求められるし、あと少なくとも、レスに含まれているレス番は連番だからです。 そして連番ってことは、レスの順番が入れ替わったりすると、その整合性が崩れる、というコトでも有ります。

あと、2ch の各板のスレッド番号とかも unixtime で有る以上、2ch っぽいシステムでは、少なくとも、

• (レスの) 順序に対する強い一貫性

が、最低でも求められる、というコトになります。

で、次。

2. ぶっちゃけ、強い一貫性が求められる分散システムを P2P ノードの参加と離脱が活発な P2P システムで実現するのは、かなりのムリゲー！

はい、ぶっちゃけたー！！１

まあ、これどういうコトかって説明すると、まず基本的に、クライアントサイド P2P 、例えば Linux の ISO ファイルを配布するのに良く使われる BitTorrent なんかを想像して欲しいのですが、ああいう P2P は、良く、繋がってるノード (他に [[BitTorrent]] 使って Linux をダウンロードしている人) が、結構頻繁に変わります。

そして、その 繋がってるノードが頻繁に変わる っていう状態を持つ P2P 実装は、少くとも [[ファイル共有 P2P]] では、

[結果整合性 ＝ [[弱い整合性]] ]

を採用しています。

それで、この弱い整合性っていうのは、例えば先に上げた BitTorrent なんかだと、

最終的に 落としてきた Linux の ISO ファイルがきちんと動作すれば良い

みたいな感じで、

最終的な出力結果 で、 或る種の整合性 (例えばファイルが壊れてないとか) が保たれたら良い

という様な実装になっています。

んで、なんでここで BitTorrent を例に上げたかっていうと、別にファイルの共有が云々、っていう話がしたいんじゃなくて、 24 時間駆動させない人が一般的な利用者である P2P 実装って、

参加者の ネットワークへの参加と離脱が、かなりバラバラ である

という特徴があるんですよ。で、その特徴を持つネットワークでは、先にも言った様に、大体は 結果整合性＝弱い整合性 を採用しています。

それで、これは何故かっていうと、ネットワークへの参加と離脱がバラバラで活発なネットワークでは、 そのネットワークへの参加者全員 に、 まったく同一のデータを保持させる 、っていうのが、 かなり困難 だからです。

例えば。学校とかでクラスメンバーの出席下校時間がバラバラなところを想像して欲しいのですが、そういう所で、

ある時点 (例えば午前 9 時時点) で、クラスメンバー全員に、同じ情報を行き渡らせる

というのを、

クラスメンバーの口頭での伝言のみで行え！

みたいなコトをやれって言われたら、

えっ！？ それ LINE とか使わないかぎり無理っしょ、それ。

と思われるかと思います。

そして、このクラスメンバーの比喩と、実際の P2P ネットワークシステムを対比させると、

出席下校時刻がバラバラなクラス → _ ネットワークへの参加と離脱が、かなりバラバラ な P2P ネットワーク_

クラスメンバー全員で同時刻に同じ情報を行き渡らせる → _ ある時点での強い一貫性が求められる_

LINE とか使わないかぎり無理 → _ どこかに全員が参加する単一のネットワークが無いと厳しい_

という感じで、まぁ、

ネットワークへの参加と離脱がバラバラな状態になる P2P ネットワークでは、強い一貫性を持たせることが困難である

と言えるかと思います。

で、最後。

3. 結論から言えば、2ch っぽいシステムを P2P で実装しようと思うと、どこかで何かを調整しないと多分ムリゲー

という感じです。はい。

まあ少なくとも言えるのは、

1. _ 2ch のスレッドとレス_ の様な _ 強い一貫性を求められるシステム_ と
2. _ ネットワークへの参加と離脱が頻繁_ な _ クライアントサイド P2P_ 、という実装形態は
3. _ ピュア P2P というネットワーク形態_ では、相当に工夫しないとたぶん _ ムリゲー_

ということです。

そして、上記の [[CAP 定理]] が数学的な証明である以上、それが理由で今の今まで、完全に 2ch ぽい感じを再現した P2P 実装は出てこなかったし、そして今後も、 CAP 定理の要素の内のいずれかか、若しくはすべての要素についてある程度の妥協や調整を行なう高度な技術を持ってないと、2ch っぽい感じの P2P 掲示板実装は、多分、誰も作り得ないであろう、というのが、僕の現地点での予想です。

まあ、自分も

えー、マジでー。それー……

って感じになっていますが、マジでそういう結論にしか俺はならなかった。っていうか反例が有るなら、誰か教えてほすぃ。

で、今ある著名な P2P 掲示板実装だと、例えば、

• 新月 - P2P 匿名掲示板
• Lair (匿名掲示板) - Wikipedia
• Freenet/Frost - Wikibooks

が挙げられますが、恐らく、これらのいずれも、強い一貫性は持ってないはずです。 っていうか僕が調べた限りでは、どれも結果整合性しか持ってないと思う。

まーだからなんだ。一言で言えば、今回の結論は、

2ch を ピュア P2P で実装するのは、どう考えても相当にムリゲー

という感なりますッ！ 数学的にムリなもんはムリッ！！ 残念無念なのは俺も一緒だッー！！１

というワケで以上です。はい。割と無慈悲な結論になった。そして俺は一歩、また諦めることを覚えた。

まぁ、どうして 2ch っぽいやつが P2P で出来ないんだろうか、と前々から思っていたんだけれども、そりゃ CAP 定理に引っかかってたら無理だわ。少なくとも自分には実装出来そうにない、と言うのは良く判った。

で、この記事を書きつつ CAP 定理について調べてもみたんだけど、CAP 定理っていうのは、確かに覆しがたい定理では有るだけど、実際には、 C (Consistency ＝一貫性) の側に寄せるか、あるいは A (Availability ＝可用性) の側に寄せるか、っていうバランスの取り方の問題でも有る、って何処かのブログか何かに書かれていたので、その辺りの加減を上手く取れる方がもし居るとするならば、もしかすると、誰かがその実装を実現するかもしれません。

まあ、だからと言ってそこら辺に居そうなメンヘラニートの自分にはムリゲーな話なので、まあ僕は無理です、と言っておきます。はい。

という事で以上。終わります。

追記

えー、早速ですが追記です。

先ほど、このブログを書き終え、 リラックスした状態で毎日の風呂掃除 して戻ってきたところ、Twitter で、

@nyarla この記事の「本当に分散されたのか?」ってところが問題の解決策を提案してくれるかもしれません。 翻訳 GitTorrent を発表 - 分散型 GitHub http://t.co/mP8oFFsLDJ - @173210

というコメントを頂き、そのリンク先をである、

を読んだところ、ちょっとした実装のヒントが見えてきたのでその辺りメモっておきます。

1. 2ch っぽい掲示板実装の一貫性の実装には、 blockchain 技術が少なくとも使えそう

一個目がこれ。

まあ、 blockchain については各自調べてくださいって感じではあるんですが、blockchain 技術は、少なくともノードの参加と離脱が激しい P2P ネットワーク上で、通貨のトランザクションに強い一貫性を持たせる、というのをかなり力技で実現しています。

で、その辺り上手く利用すれば良いんじゃね？ と思いついたので、その辺りメモると、

1. 板全体のスレ立て情報を持つ blockchain と、スレ全体のレスの情報を持つ blockchain を用意する
2. その上で、スレ立て時には 板 blockchain にスレ立てのリクエストを送り、それが Accept されたら、今度は レス用の blockchain を作る
3. そして板のスレ情報やスレのレス情報は、板 blockchain や スレ blockchain から取得し、レスを返すときはスレ blockchain に リクエスト投げる

という感じ。

まあこれなら多分出来るかな、っていうイメージです。

2 blockchain 技術を使う際の問題点

1. 独自実装しようと思うと、 blockchain 技術のコアの部分まで理解しないと実装できない
2. 各種 blockchain を使う Cryptocurrency に寄生しようとすると、その通貨が必要となり、カネが掛かる
3. blockchain の設定によっては、非常にネットワーク効率が悪い。そして某会長に Dis られる

まあ blockchain 技術を使うにしろ実装するにしろ、アレ、実装するには結構な知識と技量が要求される感じなので、その辺りクリアしないと先に進めない問題は有るっちゃあありますね。はい。

まあそんな感じ

僕の勘では、恐らく blockchain 技術を上手く利用できれば、もしかすると 2ch っぽいやつを作れるのでは？ という所まで勘が働いたのですが、まあ、僕には blockchain を独自実装する技量もないし、また他の Cryptocurrency の blockchain に寄生するのも、それに乗せられる情報量や、あるいはその Cryptocyrrency の存続性の問題が有るので、その辺りは難しい問題かな、と思っています。

まーなんだ、少なくとも、 [[Blockchain]] 技術を使えば出来そうな感はあるけれども、それはそれで結構茨の道っぽいので、誰から実力の有る方でいっちょやったろう！という方は名乗りを挙げると良いと思います ;-)

ということで追記は以上です。はい。

※ ちなみに今現在の僕の技量では、なんらかの toolchain がないと blockchain 技術の利用は難しいです。はい。

追記 2

先ほどの追記によって、最初に書いた文章中で、文章が微妙な感じになった部分を直しました。

以上です。