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:既に多くのアイデアと実装はあるのだろうけれど、調べきれてない。きっと知られていない、うまいやり方は多くある

Bash でスタックトレースを表示

Bash 計算機 ノート

Bash でスタックトレースを表示する方法。 caller という組み込みコマンドで関数の呼び出し元の位置がさかのぼって取れます。これを使って以下のようなスタックトレースを表示する関数が作れます。

function print_stacktrace() {
  index=1
  while frame=($(caller "${index}")); do
    ((index++))
    # at function <function name> (<file name>:<line no>)
    echo "at function ${frame[1]} (${frame[2]}:${frame[0]})" >&2
  done
}

function func_a() {
  print_stacktrace
}

function func_b() {
  func_a
}

function func_c() {
  func_b
}

func_c

実行すると下のようにスタックトレースがプリントされます。

at function func_a (stack.sh:11)
at function func_b (stack.sh:15)
at function func_c (stack.sh:19)
at function main (stack.sh:22)

Bash で Power Assert 風のものを作った

手慰み Bash 計算機

GitHub - fjkz/power-assert-bash: Power Assert for Bash

Bash で Power Assert 風のものを作りました。*1

なぜか Bash には assert がありません。なので、 Bash でテストを書くときは、 set -e として、

[ "$actual" == "$expect" ]

とか書きます。しかし、これだと失敗したときに、情報がないので困ります。set -x としてもいいのですが、これ欲しくない表示も出て、ウザイのです。また結果も見づらい。Bats もテストのどこでエラーとなったかは教えてくれるが、変数の中身とかは教えてくれません。

そこで、 Power Assert 風のものを作ってみました。 Power Assert とは、Spockに含まれる assert の結果を美しく表示してくれる機能です。

. power-assert.bash
A="HELLO WORLD"
[[[ "${A}" == "HELL WORLD" ]]]

. か source コマンドで power-assert.bash を読み込むと、 [[[ コマンド (実体は関数) が使えるようになります。 シェルスクリプトの [ コマンドとほとんど一緒で、条件が否なら 1 のステータスコードを返し、正なら 0 を返します。しかし、[ と異なり、条件が否の場合はエラーメッセージを吐きます。

上記のスクリプトを実行すると、以下のメッセージが表示されます。

assertion error:

[[[ "${A}" == "HELL WORLD" ]]]  ->  false
     |
     "HELLO WORLD"

at function main (sample.sh:3)

まあ、ただこれだけです。 assert_equals みたいな関数を用意するよりは、いいと思っているがどうなのだろう。

*1:○風としているところが、そんなに powerful ではないことを示していますが……。 powerful にしようと思ったら、Bash で Bash のパーサーをつくらんといけない……。まだ綺麗に表示されない条件も多い。

TT-Runnerの記録２：ベータ版

計算機 手慰み Python Bash

前回:

GitHub - fjkz/ttap: ttap: a testing framework with file system hierarchy

結合テスト用のテストスクリプトを実行するためのツールを作っている。

シェルスクリプトベタ書きのテスト群を整理された状態にまとめられるものが欲しいという、当初の目的は達成できたように思う。1000 LOC にも満たない小さなプログラムだが、欲しいものの仕様にたどり着くのに時間を要してしまった。

英語のドキュメントは下手なので伝わらないだろうから、日本語のドキュメントも書いた。

https://github.com/fjkz/tt-runner/tree/master/doc/jp

しばらく寝かせて、バグ修正だとか異常系の作り込みだとかをしたら、1.0版としたい。

追記

ttap と名前を変えた。

ディレクトリ構造のスキーマ

計算機 考え事

私はファイルシステムとかブロックストレージとかには少しだけ詳しいと思うが、現実に興味があるのはもう少し上の階層だ。RDB でいうとどのようにスキーマを設計すべきかという階層の話に興味がある。昔に書いた以下の記事でいうと「シンタックス層」が関心の対象だ。

データにもOSI参照モデルがある - 超ウィザード級ハッカーのたのしみ

なぜかというと、個人的な動機だが、私は情報を集めるのは好きなのだが、整理するのはあまり得意ではない。例えば本やメモであればフラットな場所、つまり一個の本棚やノート、にすべて放り込んで、目視探索か脳内検索をしてしまっている。そういうのは他人には扱えない。そのためには、体系的に情報を整理する必要があるので、どうやったらそれができるのかということに苦心している。

得意な人は苦労せずに整理してしまっているのだが、それが良い出来かというと疑問で、正直なところ勘で整理されたものも他の人には理解できない。頭の良い人が工夫して整理したもので、はじめてまともに整理されている状態と言える思える。

どのようにしたら情報をうまいこと整理できるのかという問題については、人類は長いこと悩んでいる。どのへんに学問性があるのか私には分からないのだけれども、図書館学というものもある。

近年では、情報はデータと言われてバイト列として計算機に収められている場合が多い。計算機上のデータは、紙面の情報と異なって物理的な制約がなくなった。そのためにデータの量が爆発的に増えてしまった。PC に収められるドキュメントの量では整理しないと人間が追いつけない。目視探索や脳内検索の限界を超えてしまっている。

計算機上にデータを保存する手段はいろいろある：RDBやファイルシステムだ。上で引用した昔の記事でいうところの「ウツワ層」に相当するものだ。ウツワ層は多くの人が研究してきて、もうだいたい完成しているように私は思っている。

しかし、その上のシンタックス層――つまりスキーマのこと――に関してはまだ未完成ではないかと思う。

RDB に関しては、何が良い設計で何が悪い設計なのかは概ね共通理解となっている。RDB はスキーマを定義しないと使えないし、それを設計するための専門職がいる。彼らのおかげで、デザインパターンというのか、良い設計をするための知見が蓄積されている。

しかし、ファイルシステムに関しては未だ全くダメだ。

ファイルシステムは RDB より歴史が長いにも関わらず、いや歴史が長いゆえか、ファイルシステム上のディレクトリ構成はたいていグチャグチャだ。UNIX OS のディレクトリ構成に関しては、Filesystem Hierarchy Standard といって概ね統一されている。あるいは、Java のソースコードも Apache Maven で標準のディレクトリ構成というのが定義されて統一されつつある。だが、そういうのがないデータはグチャグチャにならざるを得ない。PC 上のデータが整理されていないのは、実害は少ないが、共有フォルダが整理されていないのは目に見えた害がある。

どうしてこういうことになるかというと、ファイルシステムにはスキーマが定義されないからだ。

Filesystem Hierarchy Standard や Maven 標準ディレクトリ構成は一種のスキーマである。賢い人が設計しているので、なんとなく作ったものより使いやすい。また、規格なのでそれに合わせることで、他のプログラムとの親和性が向上する。

しかし、設計とかせずになんとなくディレクトリを作っちゃうことも可能で、ほとんどの場合はそうなっている。自由であるとも言えるのだが、自由にできたところで、間違った選択肢が増えるだけだ。正しい選択肢は少ないが、間違った選択肢は無数にある。最初にディレクトリを作ったときには、なにかしらの意図があるものだが、その意図も曖昧模糊としているし、時間が経過するとその意図を無視してファイルが配置されたり、新たなディレクトリが作られたりする。結果、整理されていないデータが氾濫することとなる。

ファイルシステムの構成にもスキーマを定義できたらよいと思う。スキーマが定義できれば、いつの間にかディレクトリ構成がグチャグチャになることが防げるだろう。

テストスクリプトのディレクトリ構成を規定するツール「ttap」というのを作っている*1。作ってから気づいたが、これもファイルシステムの構成のスキーマを定義しようとしているのだ。

これを敷衍してもう少し一般的な形でディレクトリ構成を定義できるようにしたい。XML にはスキーマを定義できる XSD というものがある。このようなイメージでディレクトリ構成のスキーマを Well-Defined に規定できる手段が欲しい。ディレクトリ構成には慣例があって、空気読めや――みたいに現状はなっている。今は人の手に頼るかたちになっているが、厳密に定義することができれば、機械によって整理することも可能だ。賢い人がスキーマを定義すれば、いろんな場所で使いまわせるようになるだろう。

以上のようなことを思いついたが、どうやって実現したらいいのか今は答えがない。ちょっと考えてみようと思う。

*1:https://github.com/fjkz/ttap

TT-Runner の記録 1

手慰み 計算機 Python

TT-Runner: テストスクリプトのディレクトリ構造フレームワーク - 超ウィザード級ハッカーのたのしみ

GitHub - fjkz/ttap: A Test Scripts Runner

TT-Runner (Test scripTs Runner あるいは Tree Tests Runner) というのをシコシコと作っています。*1

以下、作業記録。

スクリプトのある場所に cd するようにした。

シェルスクリプトはカレントディレクトリ、つまりどこの場所からスクリプトを実行したのか、にシビアである。スクリプトが存在するディレクトリから実行することを期待するのが多いかと思うので、スクリプトを実行する前にそのディレクトリがあるディレクトリに cd するようにした。

カレントディレクトリを変えないオプション (--no-chdir) も念のために用意した。

--stop-on-failure, --skip-all オプションの追加

一つでも operation が失敗したら、残りはすべて skip するオブション --stop-on-failure と、すべての operation を skip するオプション --skip-all を追加した（--dry-run の方がわかりやすいかもしれない）。主にテストスクリプトのデバッグ用です。実行にある程度時間がかかるようなテストを想定しているので、こういうオプションは欲しい。

各スクリプトの出力をファイルに保存できるようにした

-o オプションで指定されたディレクトリに各スクリプトの結果を保存するようにした。ok/ngだけですべてが分かればいいが、そうはいかないので、ログが残せないと不便だ。result.txt に ok/ng のテスト結果の出力も残す。一応、TAP っぽく出力はしているが、今の出力は本当に TAP として正しいのか。

今後すること

ファイルに結果を保存できるになったら、コンソールへの出力は再考の余地がある。一つ一つのオペレーションが重いことを想定しているので、今のままでは見づらい。何％終わっていて、経過時間はどのくらいかで、失敗があるのかは、コンソールから簡便に確認したい。

JUnit XML も出力できるようにしたい。

テストツールなのにテストがないので、書く必要がある。

ドキュメントは一応書いてみたが、読めないのでまともにしたい。添削してくれる人が欲しい。

可能であれば、TAPを介して、他のテスティングフレームワークと連携できるようにしたいが、それをし始めると大変だろうか。

次回

TT-Runnerの記録２：ベータ版 - 超ウィザード級ハッカーのたのしみ

*1:陽の目は見ないがやる。これが「でも、やるんだよ」ってやつか？

CAP定理について

計算機 ノート 考え事

CAP定理という分散ストレージシステムの設計において非常に重要な定理がある。まだ、以下の元の論文を読んでいないので、正確な理解かどうかは保証できないが、理解している範囲で考えることを記す。

https://www.comp.nus.edu.sg/~gilbert/pubs/BrewersConjecture-SigAct.pdf

CAP定理によると、分散システムでは以下の３つを同時に満たすことはできない：

  • Consistency 一貫性、
  • Availability 可用性、
  • Partition tolerance 分断耐性。

それぞれ、

  • all nodes see the same data at the same time,
  • every request receives a response about whether it succeeded or failed,
  • the system continues to operate despite arbitrary partitioning due to network failures

という意味である。*1

分散ストレージシステムはいろいろあるのだけれど、C・A・Pのいずれかを捨てるという選択を行っている。この選択がいわゆる設計思想というものなので、どの選択をしているかでシステムの特徴が分かる。

システムとして、Availability はほとんどの場合必須なので、

  • Consistency + Availability (CA)、 か
  • Partition tolerance + Availavility (PA)

の組み合わせが選択される。Consistency + Partition tolerance を選択している例は私は知らない。*2CA あるいは PA が選択されているシステムとしては以下が挙げられる：

列挙すると分かるが、CA は一貫性をとっているのだから当然だが、厳密でお固いものが並んでいる。一方で、PA の方は柔らかい印象だ。耐障害性・ロバスト性は PA の方が強い。柔らかいから、逆に壊れにくいという感じでしょうか。

どちらを選択するかは用途によるとしか言いようがないが、個人的には PA が好きだ。主観だが、PA の選択の方が設計思想としては新しい。一貫性を保証するというのも難しいので、初期はいかにして一貫性を担保するかを頑張ってきた。しかし、一貫性の問題が解決されたら、実は完全な一貫性はオーバスペックなのでは？――となってきた。一時的に不整合が起こるかもしれないが、それもほとんどないし、仮に不整合がおきても、時間がたてば辻褄が合うから別にいいじゃん――というある意味で割り切った態度を PA を選択したシステムはとることが多い。これを、結果整合性という。

例えば、SMB（Windowsの共有フォルダのこと）*4はネットワークに繋がっていなければ使えないし、遅い。しかし、現実同じファイルを複数人が同時に編集することはあまりしないので、常に最新である必要もない。その用途だと Windows の共有フォルダは非常に使いにくい。MS Office は整合性を保つために編集中のファイルをロックする機能があるが、あれはイライラする。競合が少ないなら、ちょっとぐらい不整合があってもいいじゃんと、Dropbox は割り切っており、この割り切りは合理的だと思う。個人用のネットワークドライブなんかは、私はセンスねえなと思う。

PA が好きなのは、どこか割り切ったところが入っている点で、言葉として変だが、何を割り切るかは割り切れないものだ。完全に Art の領域だ。どこを割り切ったらいいのか、つまり何を捨てて何を取るかということについて、まだ最もよいバランスというのは合意がとれていない。工夫の余地がまだ残っていて、興味深い。

*1:英語版 Wikipedia から引用。https://en.wikipedia.org/wiki/CAP_theorem。日本語版の記事はどうも間違っている気がする。

*2:もちろん、C・A・Pのうち一つだけしか満たしていないものもある。Consistency だけの場合が多いかな？ 例えば、初期の HDFS は Consistency しか満たしていなかった。なお、C・A・P以外にもスケーラビリティという別の話があって、Consistency とスケーラビリティは相反するところがある。HDFS は Consistency を満たしつつ、スケーラビリティも持たせるために、非常に大胆な割り切りをしている。

*3:例えば日米間の光ファイバーがサメに食われても、日本のサイトは覗けるのでインターネット全体として止まるわけではないという意味です。一つのサイトと多数のクライアントという風に見れば、CA です。インターネットの強力な耐障害性は PA を選択しているといった「ゆるさ」が理由だが、このネタだけでいくらでも語れるので踏み込まない。気が向けばいつか書く。

*4:クライアントキャッシュがないことを前提としている。SMBのクライアントキャッシュの取り扱いってどうなっているのかよく知らない。