クラスの依存関係グラフ ２

前回： クラスの依存関係グラフ - 超ウィザード級ハッカーのたのしみ

クラスの依存関係のグラフについて調べています。

今回は前回よりも大きな系について調べました。

対象は、Spark 2.0.1 です。前回は、Hadoop 由来のクラスだけ調べたが、今回は Spark のクラスだでなく、Spark が呼び出している外部ライブラリ内のクラスも含めた、クラス群の依存関係のグラフについて調べます。Spark 2.0.1 の Hadoop 2.7 用ビルドに含まれている JAR をすべて調べます。*1

グラフの大きさは、頂点の数が 113434、辺の数が 1456523 となっています。可視化した結果が下の図です。Modularity を強調しています。色は可視化ツール(gephi)が計算した Modularity Class で、辺の色は元の頂点の Modularity Class を示しています。

次数の分布は以下の図のようになっていました。

入力次数に関しては、綺麗なべき乗則に従っています。クラスの依存関係は、一般的にべき指数 2 のスケールフリーネットワークとなっていると予想できます。このようになっている理由は、ネットワーク理論の枠組みで説明できそうです。

ただ、グラフに収まらないほど、次数が大きいところにも Java や Scala の標準ライブラリのクラスがあります。java.lang.Object クラスなんかは、100957 の次数を持ちます。そいつらの存在がべき乗則に従わない例外的なのか、それともべき乗則であっても確率的現れうるのかは、今後検証する必要があります。

出力次数に関しては、前回とは見た目が異なります。すべての依存関係について調べると今回の結果になるようです。よく知られた確率分布の形ではなく、この形状の意味は物理法則では説明できない感じがします。

依存するクラスの数が 8 個の場合が最も多くなっています。この値は感覚と一致しています。

また、非常に多くのクラスに依存するようなクラスも少ないながら、存在します。べき乗則っぽい見た目をしています。入力次数の場合よりべき指数は大きいです。出力次数はクラスを書いた人が決めることですが、あまり出力次数を大きくはしたくないものなので、出力次数が大きいクラスが稀になることは妥当でしょう。サンプルをさらに大きくしたら、出力次数が大きいクラスの数はべき乗則を下回ってくるのではないかと予想されます。1000個のクラスに依存したクラスなんて巨大すぎて作れないです。

Modularity という値は 0.571 という値でした。この値の詳細はよくわからないのですが、可視化の結果からも推測できるように、Modularity が高いようです。

このサンプルで得られる情報はもっとありそうなので、もうちょっと分析してみたい。

*1:Spark は Hadoop の JAR も含んでいるので、前回と重複した要素もある。

クラスの依存関係グラフ

Java のクラスの依存関係を調べてみた。

規模が大きいアプリケーションの方が統計が取りやすいので、Apache Hadoop の 3.0.0-alpha バージョンを対象に調べる。テストとアノテーションを除いた、Hadoop 由良のパッケージに含まれるクラスに依存関係のグラフについて調査する。

クラス間の依存関係を調べるのに、JDK8 に含まれる jdeps というコマンドを使った。jdeps に -verbose オプションをつけると 各 jar 内のクラスが依存しているクラスが出力される。-dotoutput オプションで DOT ファイルに結果を保存することができる。下のようなファイルが出力される。

digraph "hadoop-mapreduce-client-common-3.0.0-alpha1.jar" {
    // Path: ./mapreduce/hadoop-mapreduce-client-common-3.0.0-alpha1.jar
   "org.apache.hadoop.mapred.LocalClientProtocolProvider" -> "java.io.IOException";
   "org.apache.hadoop.mapred.LocalClientProtocolProvider" -> "java.lang.Object";
   "org.apache.hadoop.mapred.LocalClientProtocolProvider" -> "java.lang.String";
   "org.apache.hadoop.mapred.LocalClientProtocolProvider" -> "java.net.InetSocketAddress";
   "org.apache.hadoop.mapred.LocalClientProtocolProvider" -> "org.apache.hadoop.classification.InterfaceAudience (not found)";
   "org.apache.hadoop.mapred.LocalClientProtocolProvider" -> "org.apache.hadoop.classification.InterfaceAudience$Private (not found)";
   "org.apache.hadoop.mapred.LocalClientProtocolProvider" -> "org.apache.hadoop.conf.Configuration (hadoop-common-3.0.0-alpha1.jar)";

依存先のクラス名の後ろに( ) 内にパッケージ名が付く。(not found)はパッケージが見つからないという意味です。これがあると→の元と先が同じクラスでも別の名前になってしまうので、sed で取り除く。

今回は、対象の JAR 内のクラスの関係のみを調べたい。そこで、辺が示す先がorg.apache.hadoop以外から始まるパッケージに含まれるクラスとなっている辺は除いた。また、org.apache.hadoop.classification パッケージのクラスも、今回の対象のJAR内のクラスではないので、それらが先にある辺も除いた。

JAR ごとに DOT ファイルが生成されるが、全部をまとめてひとつのグラフとして調べる。

頂点が 7844, 辺が 36076 のサイズの有向グラフとなっている。

graph-tool だと描写が非力だったので、gephi で可視化をする。

上の画像はグラフを可視化したものである。大きくて色の濃い丸が、in/out を問わない次数の大きい頂点である。辺の色は頂点の色に基づく。少ない頂点のみが次数が大きく、ほとんどの頂点は次数が小さいことが可視化の結果から予想できる。

そこで、次数と、その次数のクラスの数の関係を調べてみる。

上の図は、次数とその次数を持つクラスの割合を示している。入力次数・出力次数いずれの場合も、次数が10以上100以下のクラスはべき乗則に従っているように見える。どうやらクラスの依存関係のグラフはスケールフリーネットワークの性質を持つ可能性があるようだ。べき係数は 2 程度で、スケールフリーネットワークでは典型的な値となっている。Barabási–Albert モデルのネットワークの成長過程は、ソフトウェアが拡大していく過程と似ていることから、クラスの関係がスケールフリーネットワークとなっていることが説明できるだろう。*1

次数が大きいクラスというのは、ソフトウェアの中で重要なクラスであると考えられる。べき乗則に従うということは、特定のクラスの重要度が飛び抜けて高いということを意味している。

入力次数が大きいクラスは多くのクラスから呼び出される Fan-in なクラスである。何度も再利用されている非常に有用な部品と言える。多くのクラスから利用されていることから、欠陥も少ないと考えられる。一方で、利用者が多いクラスの動きを変える場合は影響範囲が非常に大きくなるので、なかなか変更できあに。そのため、安定度が高いクラスであると言える。

出力次数が大きいクラスは多くのクラスを呼び出している。Fan-out なクラスである。GoF のデザインパターンでいうところの Facade となっていて、そのクラスから呼び出される機能が多いということを意味していると思われる。変更の影響を受けやすく、そのため欠陥密度も高いだろう。このクラスを重点的にテストすると効果が高そうだ。

入力次数の大きいところで、べき乗則に従わない特異的に大きい次数を持ったクラスが存在していて、図の右からはみ出してしまっている。具体的には、org.apache.hadoop.conf.Configuration という設定プロパティの値を得るためのクラスが 1368 の入力次数を持っている。このクラスは、非常に多くのクラスから横断的に使用されるクラスである。このようなクラスの存在が、今回調べたソフトウェアに特有のものなのか一般的に存在しうるのかは、他のソフトウェアも調査しないと分からない。もし異常に入力次数が多いクラスが存在するということが一般的であるとしたら、ソフトウェアにスケールフリーネットワークとは異なる特別なネットワーク構造があると言えるかもしれない。

*1:Barabási–Albert モデルのべき係数は 3 で完全な説明はできない。いつかちゃんとまとめたい。

graph-tool で遊ぶ１

複雑な世界のありようを理解するのに、「グラフ」の可視化だとか分析はすごく有用なのではと考え始めたので、グラフについて勉強してみる。

動くおもちゃがないと楽しくないので、いいのかどうか知らないが、検索して出てきた graph-tool というツールで可視化等をしてみる。

graph-tool.skewed.de

インストールは 「Download - graph-tool: Efficent network analysis with python」 に従えばできた。

みんな大好きな Barabási-Albert モデルのネットワークの絵を書いてみる。

import graph_tool.all as gt

# ノード数 1000 の Barabási-Albert モデルのネットワークを作る
g = gt.price_network(1000, directed=False)

# グラフを描写するときのいい感じのノードの配置を計算する。
# どうも斥力と引力が働く粒子の運動を計算して、釣り合いがとれるような場所を計算しているっぽい。
# 試行毎に違う配置になる。
p = gt.sfdp_layout(g)

# グラフを PNG 画像として出力する。
gt.graph_draw(g, pos=p, output="barabasi-albert.png")

美しい……。

権威と OSS

権威とはなんなのだろう？――というのは長いこと悩んでいる疑問である。私が権威が大好きな権威主義者ということなのだろうな。

また、OSS というのも社会学的に興味深い営みであり、これを観察することも趣味である。

さて、どうも最近 OSS が権威主義的になっている気がする。

OSS は一種の規格であるので、OSS に関して発言力を持つことはソフトウェアベンダーにとっては重要である。OSS の開発に関して発言力を持つことができれば、自社の製品と OSS との親和性を高めることができるので、自社の製品が売れる。そのため、有名どころの OSS では、いろんな企業が主導権をとろうと活発に開発に参加している。

既に存在している OSS の開発に参加するというだけが、OSS で主導権を取る手段もない。既存のものは先行者利益が大きい。先にいた人が強い発言力を持っているので、後から入ってきた人が発言力を持つというのは結構大変だ。OSS で最も偉い人は始めた人で、次に偉い人は最も手を動かした人である。これは OSS に限らずどこの業界であってもそうであろう。しからば、自分が完全にコントロールできるような OSS が欲しいのであれば、自分で OSS プロジェクトを初めてしまうというのは簡単な手段である。

ただ、企業が始めた OSS の開発に参加する人がいるかというと、いないだろう。どうして一企業の利益に、関係ない人が貢献するのだろうか。標準規格にすることを狙って、企業が始めた OSS プロジェクトで、参加者が集まって上手くいっている例は知らない。ただソースコードが公開されているだけで、実際には一企業の人が内々で作っているような OSS だけれどもオープンではない OSS は多い。

標準化したいならば、中立性が必要だ。中立であれば、一企業だけに利する恐れが少ないので、参加者が集まる可能性が高まる。もちろん、ソフトウェアとしての価値が高いことが前提である。

思うに中立性とは権威と同じである。中立とは他より偉いという特権だ。そのため OSS プロジェクトを権威の元におこうというのは自然な考えだ。OSS 界隈で権威ある団体といえば、Apache Software Foundation と Linux Foundation が挙げられよう。一企業主導であれば標準化が難しいからと、Apache Software Foundation にプロジェクトが寄贈されたりだとか、Linux Foundation 配下で開発が行われたりだとかがされる。

ASF や Linux Foundation の元で OSS の開発が行われたら、それが中立化というと実際のところそんなことはないと思うが、一企業に利するようなことは建前上できない。

おそらく、今後 ASF や Linux Foundation の元で OSS を作ろうという風潮がますます活発になって、これらの財団のブランド力が強くなっていくだろう。権威というのは偉いから偉いのであって、一旦権威がついたものはもっと偉くなる方に向かうものだ。OSS で標準化を狙うなら、ASF や Linux Foundation の中で発言力を持てるように頑張るのがオススメだ。*1

しかし、そういう風潮が強まると、OSS が政治的が強いパワーゲームになることもおそれている。みんなで協力して自由なソフトウェアを作ろうみたいな、牧歌的なものではなくなってしまうかもしれない。

*1:とはいっても ASF や Linux Foundation の中がどうなっているのかはようわからないのだが……

ブロックチェーンについての考察

タイトルが雑だが、最近ブロックチェーンについてぼんやり考えていて、その覚書。

元の bitcoin の Proof of Work (PoW) は以下の式を満たすブロックをブロックチェーンにつなげることができる。

hash(prev, tx, nonce) < 1 / difficulty * hash_max                (eq.1)

hash       : ハッシュ値（正数とする）を返す関数
hash_max   : hash が返す最大値
prev       : 前のブロックのハッシュ値
tx         : ブロックに含めたいトランザクション
nonce      : 意味のないテキトーな値
difficulty : 困難さを表す値, (0, ∞)

PoW では上の式を満たす nonce を総当り的に探すということをする。bitcoin は diffuculty を大きくとって、めったにちょうどよい nonce が見つからないようにしている。

しかし、それでは遅いので、下のようにすることが考えられる。

hash(prev, tx, nonce) < credit / difficulty * hash_max           (eq.2)

credit という指標を導入し、信用度が高い人は PoW の難易度をおまけするようにする。credit が高い人が攻撃者の可能性が低ければ、PoW の条件が緩くても、対攻撃性は下がらない。

このような実装をとっている bitcoin 類似の仮想通貨はきっとあるだろう。調べてみると Peercoin というのがこんな感じっぽい。*1Proof of Stake 方式をとっている仮想通貨は、通貨の保持量が高い人の credit を上げるということをしているようだ。

さて、面白いと思うのは、bitcoin は decentralized なシステムであると言われるが、(eq.2) は centralized なシステムも表すことができることだ。単一のノードのみ credit ≒ ∞ で、他のノードが credit ≒ 0 のシステムであれば、centralized なシステムとなる。ひとつのノードが PoW に相当する計算なしに、データベースを更新していくような、一般的な Server-Client 型システムである。*2

(eq.1) のように credit が全ノードで同じシステムは完全に decentralized である。一部のノードの credit が非常に高くで、他のノードの credit が非常に低いシステムは centralized といえる。ということは、いろんな credit のノードがあるようなシステムは、semi-centralized なシステムということになろう。Server-Client と P2P の間のようなシステムである。コンピュータシステムではない実在するシステムにはこういう形態のシステムは多いように思う。

現実のシステムと比較すると、通貨の保持量によって信用度を高めるというやり方もかなり現実を模しているように思うが、他にも良い credit の与え方はありそうだ。通貨の保持量以外の良い credit の与え方のアイデアはあるのだが、それを書くには余白が足りない。

*1:実装はおそらくもっと複雑で、多分コンセプトはこんな感じかなという推測です。詳しい人がいらっしゃったら、教えていただけると非常に嬉しい。こういうことを質問・議論できる場所(メーリスなり掲示板なりSNSなり）はないのだろうか？

*2:複数のノードが credit ≒ ∞ の場合というのも考えられる。この場合には、ちゃんとノード間で「合意」を取るようにしないとそれぞれのノードが持つデータベースがバラバラになるので上手く行かない。credit を少しずつ下げていって、どれぐらいから「合意」がなくても上手く回るようになるのかというのも興味深い問題である。あるいは、厳密に「合意」を取る場合とブロックチェーンのように「合意」を取らない場合をシームレスにつなげる方法はないかなどは、誰も解決していない問題であろう。

bitcoin と ビザンチン将軍問題

bitcoin はビザンチン将軍問題を解決したとしばしば言われます。これが厳密には誤りだそうです。私もそんなに詳しくないのだけれども、確かにそうかなと思います。

ビザンチン将軍問題というのは――離れた場所にいる複数の将軍間で作戦の合意をとりたい；ただし将軍の中に裏切り者がいたり、伝令が失踪したり遅れたりする可能性がある――という問題です。

bitcoin がこれを解決したと言われるのは、悪意のある参加者が過半数以下の場合は帳簿が改竄できないようになっていて、参加者が帳簿を共有しているので、bitcoin では帳簿の内容について合意がとれているように見えるからでしょう。

しかし、上でいう「合意」というのは「分散システムにおける合意」（以下 consensus とする）とは全く別物です。例えば、bitcoin には最も長いブロックチェーンを参加者がみんな知っている、つまり consensus がとれている、という保証はどこにもないはずです。*1だから、bitcoin はビザンチン将軍問題をちゃんと解決したわけではない。

でも、bitcoin は現実に動いているので、何かの問題は解決している。それは一体何なのだろうというのが私の疑問です。bitcoin は別にビザンチン将軍問題を解決したわけではない――と批判するのは簡単なんですが、それよりも問題の方をもう一度定式し直した方がいいのではと思うわけです。ビザンチン将軍問題は、おそらくもう解決できないし、現実に即してないので、もはや悩むだけ無駄かと。この辺をちゃんと考えた人いるのかな？

bitcoin が、別にビザンチン将軍問題を解決したわけでもないのに、悪意のある参加者がいる状況で実用的には正しい帳簿を共有できているのはなんでだろうと考えると、おそらく bitcoin は PoW によって CPU ネックになっていて、相対的にネットワークがすごく速くなっているからだと予想する。bitcoin のブロックチェーンにひとつのブロックが追加されるのに10分を要するのは、確かに遅い。しかし、インターネットみたいな不安定な通信網の上で、どんなマシンもネットワークに参加していいという条件下で、世界中に情報が伝播することがだいたい確信できるであろう時間を考えると、そこまで変な値ではないように思う。つまり、10分ぐらい待てば、consensus を保証しなくても、ほとんどのノードには情報が伝わったことを期待してもよかろうということだ。10秒では短すぎる。この辺のさじ加減も bitcoin というのはようできてる。あぶない橋を渡っている気はするが……。

詳しくないけど、ビザンチン将軍問題を解決しようとしたときに最も難しいのは、通信だろう。遅延や欠損なんて無視できるレベルで小さい、完全な通信があれば、ビザンチン将軍問題は解決できそうだ。*2『ドリフターズ』という漫画で、織田信長が無線通信装置（のようなもの）を見た時に、遠隔地にある部隊をリアルタイムで連携できるとその可能性を見出していた。これがおそらく答えで、現実に将軍がいて合意をとりたいという、実地のビザンチン将軍問題が仮にあったら、それは無線通信があれば概ね解決できるように思う。

だから、bitcoin というのはビザンチン将軍問題を解いたわけではなくて、それを解決せずに済むような条件を絶妙なバランスで作っているから上手いこと動いているのではないかというのが、今のところの仮説です。

*1:実装までは把握していないのでこれは推測です。ゴシッププロトコルか緊急連絡網方式か、何かしらの方法で最新のブロックが追加されたことを広報しているだけで、それが確実に全体に伝わっているかは保証していないはず。10分ごとにそれをするのは不可能だと思う。

*2:いくらかの制限は要りそう。そういう条件下での解法は誰かがもう証明しているにちがいない。詳しくないので知らん。

bitcoin: Proof of Work の肝

bitcoin の仕組みは「ようできてる」と感嘆します。ポイントはデータベースの更新を承認する「Proof of Work」(PoW) という仕組みです。

さて、bitcoin が PoW で上手く回っているのは、PoW の特徴によるものに思います。PoW がなかったどうなるのかというのを仮定してみて、PoW の意義について考えてみる。同期とかの用語は厳密な意味は分からずに使っています。

PoW とは、bitcoin クラスタに投げられたトランザクションをいくつかまとめて承認して、トランザクションログに追記することです。トランザクションログは、トランザクションの塊（ブロック）がチェーン上につながっているので、ブロックチェーンと呼ばれます。ブロックチェーンに追記できるブロックは特定の条件を満たす必要があり、その条件を満たすブロックを見つける作業は CPU コストがかかります。PoW の CPU コストのために、bitcoin は非常に遅いです。１つのブロックをチェーンに追加するのに10分かかります。

では、PoW の CPU コストをなくしたら、どうなるのだろうか。*1

まず、同期が非常に難しくなる。複数のノードを同期させつつ、ネットワークの不安定にも耐えて、ノードが増えたり減ったりすることにも耐えるというのは、難しい問題である。長年研究されているけれども、決定的な解決法というのは見つかっていない。bitcoin はひとつの解決法ではあるが、ネットワークネックを CPU ネックに替えることで、ネットワークを相対的に速くしているから、回っているように思う。PoW がなくなってしまうと、おそらくネットワークの不安定に対する耐性が弱くなってしまうだろう。同期がうまいこと取れなくなって、データの整合性や永続性が得られなくなる可能性が高い。一番長いチェーンがどれなのかの合意を取る仕組みも特にないから、ブロードキャストしてちゃんと届くことを期待していると思われるが、ネットワークがネックになったら、それも期待できない。

また、対攻撃性が弱くなる。承認が簡単になってしまうと、承認とその検証が同じ程度のコストになってしまう。PoW のいいところは、誰でも承認作業ができるが、承認にはコストを要して、逆にその検証は非常に容易であることだ。承認の正当性や権威性を「計算」に置き換えてしまっている。計算をなくすと、承認の正当性も権威性も失われてしまうのだ。誰でも承認ができる仕組みをやめて、特権を持った人をつくるとしても、特権を持った人を合意するにはどうするのかとか、特権を持った人の承認の正当性はどうやって保証するのかという問題が生じる。また、特権を持った人がシステムとしてクリティカルな場所になってしまう。*2

そういうわけで分かりきった結論かもしれないが、PoW は非常にコストがかかるが、このコストがなくなると bitcoin はシステムとして成立しなさそうである。bitcoin って本当にようできている。

多分、うまい解決方法はある。おそらく、bitcoin のどこかを捨てることになるのだが、それはどこなのだろう。*3

*1:bitcoin の貨幣価値の出処は PoW に要する CPU コストなので、貨幣として弱くなる可能性もあるが、そこはあまり興味の対象でないので、議論しない。

*2:Proof of Stake という通貨を多くもっている人の権限を上げる仕組みもあるらしいが、仮想通貨としての用途以外の場合には適用しづらい。仮想通貨に興味があるのでなくて、非常に堅牢なデータベースとしての bitcoin に興味がある。

*3:既に多くのアイデアと実装はあるのだろうけれど、調べきれてない。きっと知られていない、うまいやり方は多くある