mrasu’s blog

読んだ物の内容など

JPXによる、ブロックチェーンの効果について。

http://www.jpx.co.jp/corporate/research-study/working-paper/tvdivq0000008q5y-att/JPX_working_paper_No15.pdf
JPXによる、ブロックチェーンの効果について。

検証ではブロックチェーンを分散DBとしてみているだけ。
ブロックチェーンを「総当たり暗号破りが大量の時間を必要とする性質を利用して悪意あるノードの存在を許容した、不特定多数での意思合意を可能としたシステム」と思ってたから、
「マシンパワーをそんなことに使うことが資源の浪費だし、そもそも不特定多数という前提を許容しなければいいのでは」と思ってブロックチェーンに疑問だったが、
ブロックチェーンを単純に参加者が多数いる分散DBと見る見方があるなら、それは確かに有効だろう。
それを検証したのがJPX。
ただ、ブロックチェーンを名乗る必要はなくて、分散DBの種類の一つでは。マーケティング手段として名乗っているだけだろうか。

この見方をすると、
世界的に銀行が協同してブロックチェーンに乗り出しているというのは、銀行間取引としての手段を考えてのことだとよくわかる。
主体が複数あって、それぞれに影響するイベントの内容や順序を全体で合意するというのは分散環境の前提であるから、
ブロックチェーンで使われている合意アルゴリズムを使って、銀行間取引は合意できるはず。
それにしても、「合意アルゴリズム」自体は分散の技術であってそれをもって「ブロックチェーン」を名乗る意味がないけど・・・
しかもJPXの場合には合意アルゴリズムにブロックチェーンで使われてるものではないものを使ってるみたい・・・

ちなみにこの仕組みが成立した場合には、別のシステムを使用した銀行同士が取引する場合には旧来の仕組みでやるしかないので
同一システム内にいることが連合体の意味を持つが、全銀行が同一システムに入るとは思えないので、航空会社のアライアンスのように連合体が複数になるだろう。
が、国内での銀行間取引は容易に想像できるので少なくとも国内では同一システムを使うことによる効率化が必要になる(国主体?)。
となると、各システムを相互乗り入れできるようにするか、ブロック経済のように国が連合するか、国内取引と海外取引を切り離して運用するかを選ぶ必要がある。
経済面で国が連合するのを容認されると思えず、相互乗り入れをできるようにする余力があるのかは謎なので
とりあえず、切り離した運用で様子見をする必要があると思うが、すると国内銀行がまとまって分散DBを作らなくてはならないわけだけれど
そんなことはできるのか・・・?

JPXや銀行が必要としているのは、主体毎に参照な情報を制限した分散DBなのだという意味では、
マイナンバーに紐づいた情報を銀行や医療機関と連携する際に「許可された情報のみが参照できる共有DB」というのは価値があるので、使える。
しかも、単一障害点がない点から国が集中管理するよりディザスタリカバリの点で勝る上に、
国自体がマイナンバーのシステムを完璧に維持する必要性がないことからコストの削減にもなる。

というわけで、ブロックチェーンを名乗っているシステムの中には「複数主体が管理する分散DB」を使っているものがあり、
そういうものは、分散システムの一つなので有効性は自明だし、効果範囲や限界もわかりやすい

CockroachDBの中 - gossip

分散関係のコードを読んでみようと思い、CockroachDBを見つけたのでgossipのところを読んだので、メモ

CockroachDBとは

CockroachDBは分散環境下で動くDBの1つです。
不完全ですが、SQLを使えたりACIDを備えていたりと、かなりRDBに近い動きをします。
名前の由来はゴキブリのような耐久性を持つところから
言語はGo

公式は、 www.cockroachlabs.com Githubは、 github.com

CockroachDBはノード管理のためにgossipプロトコルを使用しています。これの実装を覗いてみました。
gossipは、他ノードが持っている情報と自分の持つ情報を合わせることで、各ノードが持つ情報を伝播させる方法です。
僕もよくわかっていないので、Wikipedia など見てください。

読んでいるコードは、2016年08月16日(54986344933bff1bed0a0991d03bbc0ee19c45a0)付近のmasterブランチです。

gossip関係のファイル

gossipに関わるコードは /gossip下にあります。

重要なファイルは、

  • gossip.go
  • server.go
  • client.go

gossip.goが起点となって、gossip用のサーバーと、他ノードへアクセスするためのクライアントが起動します。
送受信するデータ内容は gossip.proto で定義されています。 (protocol buffer)

gossip.go

Start()

スタート地点は、Start()関数

func (g *Gossip) Start(addr net.Addr) {
    g.server.start(addr) // serve gossip protocol
    g.bootstrap()        // bootstrap gossip client
    g.manage()           // manage gossip clients
}

これによって、サーバーとクライアントが起動します。

Gossip#bootstrap()

クライアントの最初の接続先はresolverに登録された接続先の中でアクセスできるものを採用しています。
コードではresolverの配列を順にチェックして、最初に接続できたものを採用しますが、接続ができればランダムでも問題ないと思います。

クライアントが起動したら、現在の接続先が死んだ場合に別の接続先へ切り替えるための無限ループするgoroutineを作っています。

ここで見つけた、time.Timer が面白い動きをしていました。
これは、一定時間ごとにchannelに渡すようになっているので、定期的な動作をするのに便利ですね。
bootstrapの中では下のような使われ方をしています。

var bootstrapTimer timeutil.Timer
defer bootstrapTimer.Stop()
select {
case <-bootstrapTimer.C:
    bootstrapTimer.Read = true
case <-g.server.stopper.ShouldStop():
    return
}

Gossip#manage()

クライアントとサーバーが起動した後には、
サーバーの終了シグナルや、定期的なノード数の上限管理などが下のコードで実行されます。

for {
    select {
    case <-g.server.stopper.ShouldStop():
        return
    case c := <-g.disconnected:
        g.doDisconnected(c)
    case nodeID := <-g.tighten:
        g.tightenNetwork(nodeID)
    case <-cullTicker.C:
        func() {
            g.mu.Lock()
            if !g.outgoing.hasSpace() {
                leastUsefulID := g.is.leastUseful(g.outgoing)

                if c := g.findClient(func(c *client) bool {
                    return c.peerID == leastUsefulID
                }); c != nil {
                    ...
                    c.close()
                    ...
                } else {
                    ...
                }
            }
            g.mu.Unlock()
        }()
    case <-stallTicker.C:
        g.mu.Lock()
        g.maybeSignalStalledLocked()
        g.mu.Unlock()
    }
}

Distributed Computing: Principles, Algorithms, and Systems (4章)

「Distributed Computing: Principles, Algorithms, and Systems」の4章
メモリダンプのように、分散システム全体に対する「現在状態」を取得する方法について
全コンピュータ同時に取ることはできないので、分散が牙を剥く

Distributed Computing: Principles, Algorithms, and Systems

Distributed Computing: Principles, Algorithms, and Systems

Chapter4 Global state and snapshot recording algorithms

4.1 Introduction

グローバルな状態を取得できると、デッドロックの発見やデバッグ、復旧などに使えるが
共有メモリもなく、同一時間でもないので、特定の時刻の情報を取ることは難しい。

4.2 System model and definitions

送信中であるとは、「送信イベントは発生しているが、受信イベントは発生していない状態」を指す
グローバルの状態は、プロセスのイベントとチャネル中のイベントの総和なので、
送信イベントがあるなら、チャネルにあるか受信イベントがあるかのどちらか(チャネル中と受信を同時には満たさない)
送信イベントがないなら、チャネルにも受信イベントにもない
受信イベントがあるなら、送信イベントは必ずある

cut(断面?)がconsistentな状態とは、PASTに所属する全ての受信イベントの対になる送信イベントがPASTにある状態を言う。
consistentだと、全ての状態を並列実行できる

特定の時間に対するスナップショットにどのデータを入れるかは以下のルール

  1. 時間より前に送信したメッセージは含める
  2. 時間より後に送信したメッセージは含めない

つまり、スナップショットを取得する時は、別プロセスの送信イベントが含まれていないなら受信イベントも含まないようにする

4.3 Snapshot algorithms for FIFO channels

FIFOでメッセージが処理される場合の方法として、Marker sending rule

  1. プロセスpiが自分の状態を記録する
  2. 新たなメッセージを送信する前に、チャネル全体にマーカーを送信する(マーカー送信済みのプロセスには送らない)
  3. マーカーを受け取ったプロセスpjは、
    1. 記録していなければ、Marker sending ruleを実行する(状態記録とマーカー送信)
    2. 記録済みであれば、状態を記録した時からマーカーを受信するまでのメッセージを送信中メッセージとする

記録した状態を全プロセスに渡せば、各プロセスがグローバルな状態を見ることができる。
複数のスナップショット記録を並列で走らせたいなら、マーカーにユニークな印をつければいい。

4.4 Variations of the Chandy-Lamport algorithm

4.4.1 Spezialetti-Kearns algorithm

Chandy-Lamportのアルゴリズムでは、複数の取得処理があった場合全処理分のスナップショットが必要になる。
それを回避するためにregionという概念を用いる

各取得処理はそれぞれ固有のIDを持ち、各プロセスはマーカーについたIDからどの取得処理用のマーカーかを判断する。
スナップショットを持っていない状態でマーカーを受けたとき、スナップショットを作成するが、
スナップショットを持った状態で別IDのマーカーを受けたときは、スナップショットを取らない。
各プロセスはマーカーのIDを1つしか記録せず、同一のIDを持つプロセス群をregionと呼ぶ。

各プロセスは自身のIDに対してスナップショットを返すので、各regionは自プロセスたちの状態を把握する。
そして、region間でスナップショットの差分(量削減のため?)を交換して、region外のプロセスの状態を把握し、自分のプロセス達の状態と比較することで取得対象自国の状態を把握する(マージする)

4.4.2 Venkatesan's incremental snapshot algorithm

継続的に状態を把握したい場合に、逐一 Chandy-Lamportのアルゴリズムを使用すると効率が悪いので、
変更が起きたものだけを取得すればよいという発想のアルゴリズム

状態取得のメッセージに、バージョン番号をつける。
状態を取得したくなったら、バージョンを更新して、全体にinit_snapメッセージを投げる。
メッセージを受信したら、スナップショットを取り、前回から現在までにメッセージを送信した相手にregularメッセージと、親にackを投げる。
regularを受け取ったら、スパニングツリーの葉まで渡されたら葉はsnap_completedメッセージを投げる。
snap_completedを受け取ったら、それも親に返す。
根まで行ったら終了。

4.5 Snapshot algorithms for non-FIFO channels

FIFOを前提としないと、マーカーが正しい順番でくるとも限らないので、別のアルゴリズムが必要
Helaryのアルゴリズムではマーカーを送信したら、ackレスポンスかスナップショット自体がそのプロセスから帰ってくるまでメッセージを送らない

4.5.1 Lai-Yang algorithm

プロセスを赤と白の状態で区別する。

  1. 全プロセスを白で初期化する。スナップショットを取ったら赤にして、marker sending rule 発動
  2. メッセージは発信元のプロセスの色情報が添付して送信する。
  3. 白のプロセスは赤のメッセージが来る前にスナップショットを取らなくてはならない。(スナップショットを取るのでプロセスは赤になる)
  4. 白のプロセスは全ての白のメッセージを記録する
  5. プロセスが赤になったら、グローバルの状態を取りたがっているプロセス(initiator)に対してスナップショットと白メッセージの履歴を送信する
  6. initiatorは履歴をもとに、各メッセージの状態を計算する

とすることで、送信済みメッセージは送信中か受信済みかに分類され、未送信メッセージが処理されることもない

4.6 Snapshots in a causal delivery system

メッセージの因果順序が決定しているなら、複雑なことをしなくとも簡単にできる

4.6.1 Process state recording

トークンを全プロセスに送信し、受信したらスナップショットを取り送り返す。

これだけで、十分

4.6.2 Chnnel state recordning in Acharya-Badrinath algorighm

チャネルの状態を記録するには、
各プロセスが対象プロセスに送信したidと受信したid(idは連番)を記録し、スナップショットに付加することで、
initiatorは対象のチャネル上にある送信中メッセージを、受信id ~ 送信id の間と判断できる

4.6.3 Channel state reording in Alagar-Venkatesan algorithm

トークンより前のメッセージをoldなメッセージとする

  1. トークンを受け取ったら、スナップショットをとって、完了メッセージをinitiatorを送り返す。
  2. oldなメッセージを取得したら、チャネル中のメッセージに加える
  3. initiatorはすべての完了メッセージを取得したら、全プロセスに終了メッセージを送る
  4. 終了メッセージを受けたら、oldの取得も終了する

4.7 Monitoring global state

プロセスの変数の集合である「システムの状態」を把握することはデバッガのようなアプリケーションにとって必要
Kearnsは、simultaneous regionsを用いて
プロセス中の変数が変化したら、monitorに報告を上げ、別プロセスに対しても状態を報告するように支持を出す
monitorはその情報からグローバルな状態を把握する
i番目とi+1番目のイベントの間の期間が i+1 simultaneous regionとして報告される

4.8 Necessary and sufficient conditions for consistent global snapshots

ローカルの状態を記録することも重要で、loocal chckpointと呼ばれる
各プロセスのスナップショットが合わさってグローバルな状態を作るが、consistentであるひつようもある
consistentだと、処理が再開した時に、送っていないメッセージを受信したことにならなず、不整合にならないから。

consistentな状態の必要十分条件をzigzag pathと表現し、
別プロセスの2つのスナップショットの間で、前に取られた方より後に送信され、後に取られた方では受信しているメッセージが存在する時がzigzag pathがあるといい、
Lamportの事前関係を一般化したもの。

この関係があると、consistentにはならない

4.8.1 Zigzag paths and consistent global snapshots

zipzag pathの定義と、zigzag pathを利用して、consistentなスナップショットを構成するチェックポイント群を発見する方法を見出す

consistentであるとは、すべてのチェックポイント間で因果関係がないことが条件だが、
事前の関係がなくとも、consistentではない場合がある。

定義4.1 zigzag path があるとは、2チェックポイント間(プロセスx,y)で以下を満たすメッセージ群(m1...mn)がある時を言う

  1. メッセージm1がプロセスxから、チェックポイント後に送信される
  2. メッセージmkを第三者プロセスzが受信し、同一インターバルか後のインターバルでzがmk+1を送信する(mk+1の送信はmkの受信と前後を問わない)
  3. メッセージmnをプロセスyがチェックポイント前に受信する

定義4.2 zigzag path の起点と終点が同じチェックポイント内にあるとき、zigzag cycle にあると言う

NetzerとXuにより、チェックポイント群でzigzag path が存在しない時、チェックポイントはconsistentになることと、その逆が示された。

4.9 Finding consisent global snapshots in a distributed computation

スナップショット群に対して、consistentなスナップショットの組み合わせを得る

4.9.1 FFinding consistent global snashots

Z-pathが存在しないあるチェックポイント集合Sがあるとき、consistentな状態を維持できる他のチェックポイントを探す

  1. Sとチェックポイントの間にZ-pathがないものが候補。(これを満たすチェックポイントの集合をZ-coneと呼ぶ)
  2. Sとチェックポイントの間にZ-pathがなく、チェックポイントがz-cycleでなければ、Sに含むことができる
  3. S以外のチェックポイントで、上記を満たすチェックポイントの集合をT(Tuseful)とすると、T内にZ-pathがなければ、S∪Tはconsistent

4.9.2 Manivannan-NetzerSinghal algorithm for enumerating consistent snapshots

consistentなものをすべて求めるには、
与えられた集合に含まれていないプロセスで、Tusefulなものを順に取り出すようにすれば、すべて出せる

4.9.3 Finding Z-paths in a distributed computation

以下を満たすR-graph G = (V,E)

  1. 頂点Vは全チェックポイント
  2. 辺(Cpi,Cqj)は
    1. p = q and i = j+1
    2. p ≠ q and プロセスpのi番目のインターバルからプロセスqのj番目のインターバルへメッセージがある
      のどちらかを満たす

これを作ると、
CpiとCqjにZ-pathがあるのは、

  1. p = q and i < j
  2. CpiからCqjへの経路がR-graphにある

のどちらかを満たすとき

Distributed Computing: Principles, Algorithms, and Systems (3章)

「Distributed Computing: Principles, Algorithms, and Systems」の3章
コンピュータ内の時計に誤差が発生するせいで、発生順と発生時間が同じにならないので、どのように時刻を取るかという話
時間すら定義が必要とか、分散怖い・・・

Distributed Computing: Principles, Algorithms, and Systems

Distributed Computing: Principles, Algorithms, and Systems

Chapter3 Logical time

3.1 Introduction

イベントの因果関係を把握することで

  1. イベントの生存と失敗を把握したり、デッドロック検知のアルゴリズム
  2. 復旧時にファイルの不整合を見つけて、復旧ポイントを作成できる
  3. 進捗を把握でき、古い情報の削除やGCに役立つ
  4. 並列性の度合を把握できる。

普段の生活では、腕時計や近くの時計などが「ある程度」同期していれば、遠隔のことでも因果関係が把握できるが、
分散システムでは各プロセスの数十ミリ秒の時刻差でも長すぎる。
論理時刻を使って時刻を見れるようにする

3.2 A framework for a system of logical clocks

論理時計には、2種類の時間データがある

  1. ローカルプロセスの進捗を計測するための、ローカルな時計
  2. 他プロセスとの一貫性を持った時間を持つための、グローバルに統一された時計

全ての論理時計には、時計を管理するために2つのルールがある

  1. イベントがあったときに、ローカルな時計を更新する方法
  2. 受信したメッセージに付加された論理時計の情報を見極め、グローバルな時計を更新する方法

3.3 Scalar time

Lamportが提案したScalar timeは、ローカルとグローバルの時計を分けない。
ルールは、

  1. 送信や内部イベントなどを実行する前にd時間進める(dの値はシステムによるが1が典型)
  2. メッセージには自分の時間を付加し、受信側は自分の持つ時間と比較して大きいほう+1の時間に変更する

すると、送信イベントと受信イベントの時間は、常に 送信 < 受信

順序を決める場合に、同時刻に起きたイベント(並列性がある)にも、順序をつけるときは、プロセスに序列をつけて、後の時刻で起きたとする。
時間は、イベントが起きたときに更新されるので、時間の前後に因果関係がない。つまり、強い一貫性があるわけではない。

3.4 Vector time

Fidge,Mattern,Achmuckそれぞれが、提案したVector time はn個の各プロセスにn次元行列(vt)の時間を持たせる
ルールは、

  1. イベント実行前に、vt[i]をd進める
  2. 各メッセージは送信者が持つベクトルを付加し、受信側は各値を自身の持つ時間と比較して大きいほうの時間に変更する(+1はしない)

すると、

二つのプロセスの行列vh, vkについて、

  1. vh = vk なら、全ての時間が一致している
  2. vh <= vk なら、全ての時間がvh[i]以上
  3. vh < vk なら、vh <= vk かつ、いずれかがvh[i]より大きい
  4. vh || vk なら、 ^(vh < vk)⋀vk < vh

イベントxとyが持つvh,vkについて、

vh < vk なら、 xとyは因果関係にあり、vh||vkなら、x||y
強い一貫性を持つので、時間を見れば因果関係があるかどうかわかる
各プロセスにある自分の時間は(dが1なら)自身に起きたイベントの数なので、その時にあるベクトルの合計は事前に起きた各プロセスのイベントの総量
因果関係がわかるので、いろいろなところで使いやすい

ベクトルの長さは全てのプロセスの進捗を知りたければ、全プロセス数が必要だが、nプロセス間のイベントが対象であればnでいい。

3.5 Efficient implementations of vector clocks

vector clockは規模の大きい分散だと、オーバーヘッドが大きい

3.5.1 Singhal-Keshemkalani&s differential technique

変更された時間だけを送るようにすれば、メッセージ量が減らせる。特に通信範囲を限定している場合には通信コストを削減できる
つまり、

{(i1, v1), (i2, v2)}

のように、変更部分を指定する。
この方法を実現するためには、各プロセスが他のプロセスに送った時間を覚えておく必要があり、O(n2)の空間が必要になってしまう。
これを避けるために、

  1. 最後に送った時間(LS: Last Sent)
  2. 時間を更新した時間(LU: Last Update)

を記録すれば、LS < LU になっている部分が変更があった場所だとわかるので十分

3.5.2 Fowler-Zwaenepoel's direct-dependency technique

自プロセスの時間だけを付加して送信する。
各プロセスが時間を保持すれば、他プロセスとの推移的依存関係を再帰で求めることができる。
これは、負荷情報が少ない代わりに、推移的な依存を求めるための時間と、過去データを保持する空間が必要になる。
そのため、情報がリアルタイムで必要になるアプリケーションには適さない
また、時間の更新はメッセージを受信してから送信するまでの間に行う必要がある

3.6 Jard-Jourdan's adaptive technique

前のイベントが発生した後に発生した受信イベントの時間を付加して送信すると、送信イベントに必要な直接の依存関係にあるイベントを把握できる。
プロセスに内部イベントが発生したら、受信イベントでためてきたイベント(pseudo-direct)をプロセスの依存関係に追加する

3.7 Matrix time

Matrix timeは、

  1. 自プロセスのローカル時間
  2. 自プロセスが確認した他プロセスのローカル時間 (Vector time)
  3. 他プロセスのローカル時間
  4. 他プロセスが確認した他プロセス(第3者のプロセス)のローカル時間

を持つ(つまり、各プロセスが保持する全プロセスのローカル時間を持つ)
更新方法は、

  1. 送信や内部イベントなどを実行する前にd時間進める
  2. 各メッセージは送信者が持つ行列を付加し、受信側は
    1. 自プロセスが確認した他プロセスのローカル時間は、自身の持つ時間と送信プロセスが確認した他プロセスのローカル時間を比較して大きいほうの時間に変更する
    2. 第3者のプロセスの時間は、受信データと自身のデータを比較して大きいほうの時間に変更する

全てのプロセスが確認した第3者プロセスlがtより大きい場合、自プロセスは「プロセスlは全プロセスに対してt以降の情報を送っている」と理解できる
つまり、プロセスlに関するt以前の情報は全プロセスにわたっているので、削除しても問題ないとわかる

3.8 Virtual Time

3.8,1 Virtual time definition

Virtual timeは以下を満たす必要がある。

  1. 送信時間 < 受信時間
  2. 何かのイベントの実行時間 < 次のイベントの実行時間

これで、因果関係があるイベントA, Bでは、Aが終わった時間 < Bの開始時間 を維持する

特徴は

  1. 各Virtual timeは同一のものではない
  2. 部分的に順序だっているが、全てのプロセス間の時間と実行順序が等しいわけではない
  3. 現実の時間とリンクしていたり、別物だったりする
  4. プログラマが操作できるものであったり、何らかの定義によって暗黙的に決まっているものだったりする
  5. 計測可能だったり、特定のルールに従って代入される

3.8.2 Comparison with Lamports losical clocks

Lamport のロジックとの違い

Lamportのものは時間を正確にしているので、時間の前後関係から依存関係を正確に出すことができる
Virtual time では不正確になることがあり、不正確だとわかった時に時間を修正するので、依存関係はでない

3.8.3 Time worp mechanism

メッセージの前後関係と、メッセージに付随するタイムスタンプの前後関係は必ずしも一致しない。
それを解決するために、time warpが存在する
time warp はローカルと、グローバルの2つの機能にわけられる

3.8.4 The local control mechanism

ローカルの時間はイベント間で変化し、イベント途中では変化しない。
受信したメッセージは受信時刻順に並べられ、順に処理される。
もし、処理済みのメッセージ以前のタムスタンプがついたメッセージが来た場合、ロールバックして対象のメッセージから順に処理する。
(ロールバックが発生する必要が少ないことが前提)

ロールバック対象の処理の中にメッセージの送信イベントがあった場合、送信先をロールバックする必要があり、
送信先のロールバック対象に送信イベントがあった場合には、送信先の送信先をロールバックする必要がある。

ロールバックのために、Antimessageを用意する。
Antimessageのために、各受信(送信)時間の逆数を記録する。また、イベントの実行後の状態も記憶しておく必要がある。
ロールバックが必要になったら、

  1. ロールバック直前のイベントまで状態を戻す
  2. 戻した時間以降に発生した送信イベントに対してantimessageを対象プロセスに送信する
  3. 戻した時間から処理を実行する

また、antimessageを受け取ったプロセスは

  1. 処理実行前にantimessageを受け取ったら、対象の処理キューから削除する
  2. 処理実行中または、処理後だった場合は、ロールバックを実行してantimessageを送信する
  3. antimessageに対応したメッセージが見つからない場合は、何もせず、対応メッセージが来たら何もせず削除する

Global control mechanism

Global Virtual Time(GVT) は実時間rの時のシステム状態のプロパティの1つで

  1. 全てのvirtual timeが実時間r
  2. r時点で送信はされているが処理されていないメッセージの送信時間

の小さいほう
GVTは減少しないし、システムのvirtual clockとみなすことができる。
GVTが正確に何時であるかを知ることはできないが、GVTの取得アルゴリズムでは、アルゴリズムの開始と終了の間の時間を求めることができる
ただし、O(d) (dは遅延)かかる

GVTの利用例としては、

  1. メモリ管理
    古い情報の削除、受信されていないことを送信先に伝えて送信キューからの削除
  2. 停止検知
    プロセスはメッセージがなくなってローカルのvirtual timeが無限大になったら停止し、GVTが無限大になったらメッセージを送信を停止する。
    time warpではGVTが無限大になったら停止を教えてくれる
  3. エラーハンドリング
    たいていのエラーはロールバックで直るが、直らなければ通知する
  4. IO
    ロールバックが存在するので、外部機器への出力はすぐに実行するのではなくGVTがreceive timeを超えたときに実行する
  5. スナップショット管理
    ローカルのvirtual timeがtの時にスナップショットを取り、ロールバックがtを跨いだらスナップショットを破棄する。
    GVTがtを超えたら、スナップショットは完成し、有効であると考えられる

3.9 Pysical clock syncronization: NTP

分散システムの時間が必要な理由は以下など、

  1. イベントが発生した時間
  2. 別マシンで起きたイベント間の時間差
  3. イベントが発生した順序

定義は、

  1. 時刻 (Time)
    あるマシンのもつ時刻。実時間と同じ
  2. 頻度 (Frequency)
    時計の進んだ割合
  3. 差(Offset)
    実時間との差
  4. ねじれ(Skew)
    実時間との頻度の差
  5. ドリフト(Drift)
    クロックの値の二階微分

ネットワークを挟むので、時刻差を推測する必要がある。
そこで登場するのがNTP。

Distributed Computing: Principles, Algorithms, and Systems (2章)

「Distributed Computing: Principles, Algorithms, and Systems」の2章
メッセージパッシングやイベント、現在状態の見方など分散プログラムが通常のプログラムと違う部分を紹介しています。

Distributed Computing: Principles, Algorithms, and Systems

Distributed Computing: Principles, Algorithms, and Systems


Chapter2. A model of distributed computations

2.1 A distributed program

分散プログラムはn個の非同期プロセスでできている。
実行やプロセス間通信は非同期で、遅延は有限だが予測できない。
グローバルな状態はプロセスと、プロセス同士の通信(チャネル)の状態をもって表す。

  • プロセスの状態: プロセスが動くローカルのメモリや処理内容
  • チャネルの状態: チャネルが実行しているメッセージの集合

2.2 A model of distributed executions

プロセスの行うイベントは3種類

  1. 内部イベント
    プロセス内で行われる。他プロセスには影響を与えない
  2. 送信イベント
    メッセージを送信する。送信するときと、送信が完了したときに状態が変化する
  3. 受信イベント
    メッセージを受信する。受信するときと、受信が完了したときに状態が変化する

プロセスi上のイベントxがプロセスj上のイベントyに依存しているというときは、

  1. iとjが同じプロセスで、xの後にyが起きる
  2. xからyへのメッセージ送信
  3. 別のイベントzを通して、x→z→yへの依存関係がある

のどれか。
また、依存関係がない場合でも推移律は成立しない。

二つのイベントが発生の有無によって影響しないとき、「論理的」並列だといい、同時に実行されることを「物理的」並列だという。
論理的並列性があれば、同時に実行可能であり、同時でなくともよい

2.3 Models of communication networks

通信には、

  1. 因果順序
    因果関係による順序。 2つのメッセージに因果順序がある場合、2つのメッセージの送信順と、受信順は一致する
  2. FIFO
    送受信の順番で保存される
  3. non-FIFO
    順序は保存されないので、ランダム

2.4 Global state of a distributed system

グローバルの状態は各プロセスの状態と通信の状態に左右する
プロセスiがメッセージxを送信していない時に、プロセスjがメッセージxを受信しておらず、通信上にもメッセージxが存在しないとき、グローバルの状態がconsistentだという。
また、通信中のメッセージがない時をtransitlessという。
consistentかつtransitlessであるとき、strongly consistentという。

2.5 Cuts of a distributed computation

各プロセスのそれぞれの時点をもって、過去と未来に分割(cut)すると、
過去の全ての受信が過去に送信されている場合、consistent cutといい、
同時刻で区切っているわけではないので、過去に受信しているのに未来に送信するものが存在し得、そういうものはinconsistent

2.6 Past and future cones of an event

あるイベントeに対して

  1. 因果関係があり、事前に実行しなければならないもの
  2. 因果関係があり、事後に実行しなければならないもの
  3. 上のどちらでもなく、並列で実行できるもの

と分類できる。

2.7 Models of process communications

コミュニケーションの方法には、同期と非同期があるがどちらかが優れているわけではない

  1. 非同期は高い並列性を実現するが、実装やデザイン、検証が難しく、状態を保存するコミュニケーションに関するメモリも多く必要
  2. 同期は簡単に扱えるし、実装も楽

Distributed Computing: Principles, Algorithms, and Systems (1章)

「Distributed Computing: Principles, Algorithms, and Systems」という分散システムについての教科書を読み始めました。
Hadoopが「『超人しか使えない』分散システムを凡人が使えるようにしたライブラリ」という評価を受けていて、
どれほど難しい世界なのか見たくなりました。

1章は「分散システムとは何か」というイントロです。

Distributed Computing: Principles, Algorithms, and Systems

Distributed Computing: Principles, Algorithms, and Systems


Chapter1. Introduction

1.1 Definition

「分散システム」を表すと、

  1. コンピュータが壊れても、仕事(work)を止めない
  2. メモリやクロックを共有せず、ネットワーク越しにメッセージで通信し、半自立的で疎結合に問題を解決する
  3. ユーザーには1台のコンピュータに見える独立したコンピュータ群
  4. WANのように疎結合だったり、LANのように密結合だっり、マルチプロセッサーのように超疎結合だったりする幅広い意味でつかわれる単語

と、いろいろ言われるが、特徴は

  1. 物理クロックを共有しない
    重要。これによって「分散」が可能で、プロセッサ間で各々固有に各自実行できる
  2. メモリ共有しない
    メッセージパッシングを使用する。ただ、抽象的なメモリ空間を使用することはあるし、マルチプロセッサ間の共有に関する研究は分散コンピューティングの研究にもある
  3. 地理的に疎
    よくある特徴だが、必須ではない。GoogleはLAN内にクラスタを作っている
  4. 独立・不均一
    速度やOSは統一されていないし、特定のプログラムのためだけに動いているわけでもない。リソースを貸し出すことで協調している

1.2 Relation to computer system components

コンピュータ達はWANやLANでつながっており、各コンピュータ内に設置した分散ライブラリを通じてつながっている。
そのミドルウェアは非同時性などを隠している。CORBAとかRPCとかある。

1.3 Motivation

分散システムを使う動機は以下がある

  1. もともと分散している
    銀行間の金銭移動や離れた地域を通した合議制
  2. リソース共有
    周辺機器やDB,データで完全コピーを作れない場合。地理上の関係で一ヵ所におけない場合。
  3. 遠隔からデータやリソースを使用する
    大きすぎたり、重要だったりして、複製を作れない場合。中央に巨大なシステムを作り、遠隔からはクエリを投げるようになる
  4. 高信頼性
    分散すれば、データや実行を複製でき、地理的に単一障害点にもならない
  5. コストパフォーマンスが悪くなっている
    リソースを共有したり、リモートからアクセスするのはコストが高くなっている。
  6. スケーラビリティ
    リソースを追加することがボトルネックになっていない
  7. 拡張性
    疎なプログラムを追加する場合、システムのパフォーマンスに影響しない導入をしやすい

1.4 Relation to parallel multiprocessor/multicomputer systems

並列システムと分散システムの差を考える。

並列システムの特徴は

  1. マルチプロセッサーはプロセスがメモリを共有して、メモリへのアクセスするための配置方法にはomega/butterfly
  2. マルチコンピュータはメモリを共有せず、2D-meshとHypercube
  3. アレイプロセッサーはクロックは共有するが、メモリは共有せずにメッセージパッシング

分散についての研究は80年,90年代にあったが、消えてしまった。理由は

  1. 高速計算の需要がなかった
  2. 規模の経済が働いて、高速処理をするのが高くなかった(分散するより、高速に計算するほうがコスパがよかった)

Flynnによるアーキテクチャの分類

  1. SISD
    単一のCPUで単一のメモリを対象に処理する
  2. SIMD
    異なるデータに対して同一の命令を実行する(行列演算などで行われる)
  3. MISD
    同一データに対して異なる命令を実行する(可視化とか)
  4. MIMD
    異なるデータに対して異なる命令を実行する(並列システムではよくある形)

結合度による分類

  1. UMAのように、メモリを共有しているマルチプロセッサ
  2. NUMAやメッセージパッシングを使用しているマルチプロセッサ
  3. 同一箇所に置かれるマルチコンピュータ。異なるプロセッサを使用していて分散システムと呼べるが、物理的距離が近く並列システムのように速度問題がない
  4. 地理的に分散されたマルチコンピュータ。伝統的な分散システムの形

指標群

  1. 特定システムの速度を上げるための並列化による速度比。T(n)の関数であらわされる
  2. CPUがコミュニケーションのために発生する待ち時間の時間
  3. プログラムにおける分散化(並列化)されたプログラムの割合
  4. プロセス間通信の量の比率を粒度(granularity)という。コミュニケーションコストが低いと通信が多い並列化が良いが、遠隔に分散しているなら通信回数を減らすことでオーバーヘッドが減る

1.5 Message-passing systems versus shared memory systems

共有メモリの方がメッセージパッシングより簡単だが、分散システムは共有メモリを持つことができないので、仮想の共有メモリ「分散共有メモリ(distributred shared memory)」を作成する。
逆に共有メモリ上でメッセージパッシングをすることも可能である

共有メモリ上でメッセージパッシングを再現するなら、「送信」と「受信」という操作を模倣し「送信」時に送信相手のものと割り当てられたメモリ空間に書き込めばいい
メッセージパッシングで共有メモリを再現するなら、「書込」と「読込」という操作に対応して、マスタープロセスに「送信」し、マスタープロセスから「受信」することで再現する。
ただし、共有メモリを再現したところで、当然、ネットワーク通信による遅延は避けられるわけではない

1.6 Primitives for distributed communication

いろいろな選択肢

  1. バッファリング
    メッセージを送信するときには、送信時に同時にネットワーク上のリソースに書き込むか、一度バッファしてからネットワークに書き込むかを選択できる(普通はバッファする)
  2. 同期(synchronous)
    送信時にデータが受信されるのを待って完了とみなすなら「同期」している。書き込み対象(マスタプロセスとか)に書き込まれた時点で完了とするなら「非同期」
  3. ブロッキング
    送受信処理が完了するのを待ってから次の処理に移るなら「ブロッキング」。完了前に次の処理に行くなら「ノンブロッキング」。受信でノンブロッキングだと、最新データが読まれていないないかもしれない
    ノンブロッキング時の完了処理は、ループなどでステータスを見続けるか、Wait()を呼んでそこで完了を待つか。(Wait()はノンブロッキングと違い、完了を気にしない処理が実行できるというメリットがあるのだと思う)

通信だけでなく、プロセッサでも同期の選択肢があるが、分散では無理。コード上の1点で全処理揃うまで待つということはできる。

1.7 Syncronous versus asyncronous executions

同期については、プロセッサや通信だけでなく、実行においても注目に値する

  • 非同期
    1. プロセッサの同期性が不要で、ドリフト率に制限がない
    2. メッセージの遅延に上限がない
    3. ステップ実行時間に上限がない
  • 同期
    1. プロセッサは同期され、2プロセッサ間のドリフト率には限界がある
    2. 1論理ステップに行われる必要があるので、メッセージの遅延には上限がある
    3. 1ステップ実行時間に上限がある

同期を前提としたほうがアルゴリズムの設計や検証が簡単だが、実際には完全な同期システムを作るのはかなり難しく、遅延も発生するので難しい。
そこで、「仮想同期」ができた。一定時間内では非同期にして、枠を超えたら同期するようにする。

同期システムで非同期を再現するのは簡単(同期システムは同期するようにした非同期システムとみなせる)
非同期システムで同期システムを表すにはsyncrhronizerをつかう(5章で扱う)

失敗がないシステム(落ちないシステム?)では非同期システムと同期システムでできることは変わらないが、
失敗(落ちる?)することが前提のシステムでは同期システムのほうができることが多い

1.8 Design issues and challenges

インターネット出現当初から分散システムは存在していて、現在も分散システムは重要であり、課題もある。
現存する課題は以下のように分類できる

  1. システム構成やOS
  2. アルゴリズム
  3. テクノロジーの発展や新しいアプリケーションの出現

分類に重複部分はあるが、それぞれに特徴が存在する

  1. システム面についての課題
    1. 通信
      適切な通信方法は何か(RPCか、ROIか?メッセージ型かストリームか)
    2. プロセス
      クライアントやサーバーのプロセス管理やコードマイグレーション(デプロイ?)、モバイルやソフトのデザインについて
    3. ネーミング
      透過的でスケーラブルなリソースやプロセスにするには名前が重要。モバイルは動くのでさらに難しい
    4. 同期
      同期やプロセス間協調の仕組みは重要。
    5. データ蓄積とアクセス
      高速でスケーラブルなデータ蓄積法やデータアクセスの透明性は重要
    6. 一貫性とレプリケーション
      ボトルネック回避、高速アクセス、スケーラビリティの確保のためにレプリケーションが必要だが、一貫性の問題と衝突する
    7. フォールトトレランス
      リンクやノード、プロセスが落ちてもシステムが動いている必要がある。
    8. セキュリティ
      暗号化、通信、アクセスコントロール、鍵の生成と配布、認可、グループ管理など
    9. APIと透過性
      APIは差異吸収に重要である
      透過性には、アクセス、場所、マイグレーション、再配置、レプリケーション、平行実行、障害に対して吸収することが期待される
    10. スケーラビリティとモジュラリティ
  2. アルゴリズムの課題
    1. 実行モデルとフレームワーク
      interleaving model と partial order modelがあるらしい(詳細は別章?)。input/output automata modelとかTLAとか
    2. 動的な分散グラフアルゴリズムと分散ルーティング
      分散システムは動的にグラフの負荷が変わったりするので、普通とは違う。最短経路は、ユーザーのためだけでなく、ネットワーク負荷などにも影響する
    3. 時間などのグローバルな状態
      正確な物理時間を維持することと、相対的な論理時間を維持するという課題がある。
      論理時間は物理時間を共有するオーバーヘッドを削減し、分散環境下のロジックやプロセスの依存関係を把握し、進み具合を確認できる
      他のグローバル状態を見るためにも、特別なアクセス法が必要
    4. 同期・協調のメカニズム
      分散システムは並列で動くべきだが、システム状態などの情報共有やリソース管理のために同期・協調が必要。時間合わせとかリーダー決定、排他制御デッドロック解決などで
    5. グループ内のコミュニケーションやマルチキャスト、メッセージ送信順序
      コンテクストを共有し、アプリケーション単位の共通タスクを行うプロセスのグループが必要なものがあり、グループ内ではプロセスの参加・脱退・失敗を考慮する必要がある
    6. イベントや述語(?)のモニタリング
      各環境で定義され別の環境からは見えない述語は、システム全体の状況を把握したり、デバッグなどに役に立つ。
    7. 分散プログラムに適した設計と、検証ツール
      系統だった設計がされ、正しいことを検証されたプログラムはデバッグや設計など多くの時間の節約になる
    8. デバッガ
      分散下では実行可能であろう選択肢があまりにも多いため、デバッグが必要
    9. レプリケーション、一貫性、キャッシュ
      高速にアクセスのために、レプリケーションやキャッシュに対する一貫性は重要で、どこに置くかも重要
    10. World Wide Webデザイン
      wwwは分散で、キャッシュや先読みなどがある。これらの性能を向上させることも課題
    11. 分散共有メモリ
      実現はできるが、まだ高価。他のプロセスで待たされないとか、排他制御、非同期アクセスを完全に許容するメモリ管理、(完全な一貫性は遅すぎるので)現実に即した一貫性の定義などが必要
    12. 信頼性とフォールトトレランスの備わったシステム
      不正なメッセージに対処する合意(consensus)アルゴリズムレプリケーション、冗長性と選挙、分散DBとトランザクション、自動修正、チェックポイントの作成と復元、異常検知
    13. 負荷分散
      データ分散、プロセス分散、スケジューリングによって、より高スループット
    14. リアルタイムスケジューリング
      決められた時間に終わらなければならないミッションクリティカルなアプリケーションではリアルタイムスケジューリングが重要だが、遅延や断絶の可能性があるネットワークでは全体の状態を見ることすらできない
    15. パフォーマンス
      分散において、高スループットが主目的であるわけではないが、ユーザーが感じる速さは重要。パフォーマンス測定や測定法作成のためにもメトリクスは必要だし、測定ツールも必要
  3. アプリケーションに関する課題
    1. モバイル
    2. センサーネットワーク
    3. ユビキタスコンピューティング
    4. P2P
    5. pub-subの仕組み
    6. 分散エージェント
    7. データマイニングのための分散
    8. グリッドコンピューティング
    9. セキュリティ

算機プログラムの構造と解釈(5章)

「計算機プログラムの構造と解釈(SICP)」の5章(最終章)です

レジスタを使用するような計算を実装します。
レジスタを使用するような表現法を再現し、
Lispで書かれたものをレジスタ表現に置き換えます。

つまり、「アセンブリ言語を入力としてLispを実行し、Lisp言語を入力としてアセンブリ言語に置き換える」ようなことをします。
(ただし、アセンブリ言語に似た言語を作るのであって、アセンブリ自体ではありません。)

計算機プログラムの構造と解釈 第2版

計算機プログラムの構造と解釈 第2版


5章 レジスタ計算機での計算

5.1 レジスタ計算機の設計

5.1.1 レジスタ計算機の記述言語

  1. 入力を識別するラベル
  2. 命令
    • test (cmp)
    • branch (jump if equal)
    • goto

を用意する。記法は、

(controller  
    test-b  
    (test (op = ) (reg b) (const 0))  
    (branch (label gcd-done))  
    (assign t (op rem) (reg a) (reg b))  
    (assign a (reg b))  
    (assign b (reg t))  
    (goto (label test-b))  
    gcd-done  
)  

と記述する(見た目はLispだが、アセンブリ的)。
外部へ影響がある演算をperfomとする

5.1.2 計算機設計における抽象

rem 演算がない場合以下が必要

(controller  
    test-b  
        (test (op =) (reg b) (const 0))  
        (branch (label gcd-done))  
        (assign t (reg a))  
    rem-loop  
        (test (op <) (reg t) (reg b))  
        (branch (label rem-done))  
        (assign t (op -) (reg t) (reg b))  
        (goto (label rem-loop))  
    rem-done  
        (assign a (reg b))  
        (assign b (reg t))  
        (goto (label test-b))  
    gcd-done  
)  

5.1.3 サブルーチン

サブルーチンを作成して、サブルーチンに飛び、元の場所へ戻る処理は、
単純なものなら、フラグを作って、呼び出し元と1対1にすればよい。
もっとやるなら、呼び出し元のアドレスをどこかへ記録すればいい。
が、記録場所が常に同じだと再帰ができない

5.1.4 再帰を実装するためのスタックの使用

スタックを作れば、呼び出し元や元の値を再現できる

(controller  
        (assign continue (label fact-done))  
    fact-loop  
        (test (op =) (reg n) (const 1))  
        (branch (label base-case))  
        (save continue)  
        (save n)  
        (assign n (op -) (reg n) (const 1))  
        (assign continue (label after-fact))  
        (goto (label fact-loop))  
    after-fact  
        (restore n)  
        (restore continue)  
        (assign val (op *) (reg n) (reg val))  
        (goto (reg continue))  
    base-case  
        (assign val (const 1))  
        (goto (reg continue))  
    fact-done  
)  

5.3 記憶の割り当てとごみ集め

5.3.1 ベクタとしてのメモリ

(vector-ref! <vector\> <n\>)  
(vector-set! <vector\> <n\> value\>)  

ができるモデル「ベクタ」を定義する。

基本リストは、
0. (assign <reg1> (op car) (reg <reg2>))は
(assign <reg1> (op vector-ref) (reg the-cars) (reg <regs2>))
0. (perform (op set-car!) (reg <reg1>) (reg <reg2>))は
(perform (op vector-set!) (reg the-cars) (reg <reg1>) (reg <reg2>))

スタックは、

  1. (save <reg>)は
    (assign <reg> (op cons) (reg <reg>) (reg the-stack))
  2. (restore <reg>)は
    (assign <reg> (op car) (reg the-stack))
    (assign the-stack (op cdr) (reg the-stack))

と表現できる

5.3.2 無限メモリの幻想の維持

ガーベッジコレクションすることもできる。
ストップアンドコピー法として、使っているものを順に新領域に移動し、移動されなかったものを削除すればよい。

5.4 積極制御評価器

5.4.1 積極制御評価器の中核

手続きを評価する前に、現在の状態を保存する必要があり、戻ってくる場所も保存する
手続きの引数もスタックに入れる。使用時には、それらを吐き出す

5.4.2 並びの評価と末尾再帰

再帰には、末尾再帰もあるので、それを判断できるとループにすることができる

5.5 翻訳系

Lispを入力として、上の気法を出力する