トランザクション、Argus、投機的・楽観的実行/Transaction,Argus,speculative/optimistic execution

並行システム

                               システム情報系情報工学域,
			       システム情報工学研究科コンピュータサイエンス専攻
                               新城 靖
                               <yas@cs.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2019/2019-08-09
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/cs/
http://www.cs.tsukuba.ac.jp/~yas/

■連絡事項

■今日の重要な話

■トランザクション/Transaction

相互排除、デッドロックより高いレベルの抽象が欲しい。 We need better abstracts than mutual exclusion and dead locks.

ロックよりも楽にプログラムを作りたい。 We would like to write programs more easily than that with locks.

特に分散では。集中でも、フォールト・トレランスの実現では必要。 Especially in distributed systems. Transaction is essential to realize fault tolerance.

◆トランザクションの意味/Transaction semantics

商談は、成立するか、しないか。 all or nothing。

歴史:1960年代、テープの時代。 失敗したら、巻き戻す(rollback)。

銀行口座間の預金の移動。

  1. 口座1から出金
  2. 口座2に入金

◆トランザクションを実現するための命令/Transaction operations

◆ACID

Atomic
外の世界からみると1つ。中間状態が見えない。不可分。
Consistency
不変量(invariant)を保つ。例:口座間の預金の移動。預金の総額は不変。
Isolated
並行するトランザクションは、孤立している。直列化可能(serializable)
Durable
Commit すると永続的。

◆直列化可能(serializable)

注意:Java の serializable とは意味が全く違う。

複数のトランザクションは、並行に実行可能。しかし、その複数のトランザク ションの最終結果は、それらを「ある順序」で「逐次的に」実行した時と同じ結果 になる。

逆に、トランザクションは、直列化可能なスケジュールが存在するなら、並行 に実行してもよい。直列化可能でないなら、トランザクションは、開始を遅ら せるか、アボートする。

トランザクション、複数並行実行

図? トランザクションの処理(並行実行)/Concurrent execution of transactions

トランザクション、直列化

図? トランザクションの処理(直列化の例その1)/A serialized execution of transaction No.1

トランザクション、直列化

図? トランザクションの処理(直列化の例その2)/A serialized execution of transaction No.2

トランザクション、直列化

図? トランザクションの処理(直列化の例その3)/A serialized execution of transaction No.3

◆例/An example

航空券の乗り継ぎの予約のプログラムの例。 成田からサンフランシスコ経由でオーランドまで行きたい。
Begin_Transaction();
  reserve("NRT-SFO");
  reserve("SFO-MCO");
Commit();
プログラムの記述としては、これだけ。どこにもロックは出てこない。内部的 には、ロックは行われる(ことがある)。

途中の reserve() が失敗したら、トランザクション全体を abort() する。

◆入れ子トランザクション(nested transactoin)

目的 親が abort されたら、子供が commit したものも無効になる。

◆トランザクションの実装(集中)/Implementation of transaction in centralized systems

◆プライベート作業空間/Private work space

全てのデータをコピーすると重たい。

ファイルのコピー、インデックス、ブロック、copy-on-write

図? ファイルの変更されたブロックだけをコピー)

◆先行書き込みログ(write-ahead log)

実行予定リスト(intentions list)

シャドー・コピーを作らず、ファイルのその場所を書き換える。 その前に、次の情報を安定記憶にログとして書き込む。

コミットされると、何もしない。 アボートされると、ログを後ろから前に読み込み undo する。

クラッシュからの回復もできる。

◆安定記憶(stable storage)

RAM
電源が落ちると消える
ディスク
ディスクヘッドのクラッシュで消える
安定記憶
洪水や地震でも生き残るように設計されている。
安定記憶の実現方法:2個のディスクの組みを使う(図?(a))。

テキスト、データ、スタック複数

図? 安定記憶の実現

更新時:
  1. ディスク1のあるセクタに書き込む。
  2. ディスク1からそのセクタを読み込む。
  3. 内容を比較する。同じなら、ディスク2の同じ位置に書き込む。

3 の前にクラッシュしても、常にディスク1が正しい(図?(b))。 この場合は、ディスク1からディスク1へコピーする。

チェックサムエラーが起きた場合(図?(c))、他のディスクからコピーして回復する。

◆並行性制御/Concurrency Control

できるだけ効率のよい、直列化可能なスケジューリングを求める。

◆ロッキングによるトランザクションの実装/Implementing transactions by locking

もっとも単純な方法:

注意:プログラマは、ロックを意識しない。

制約が強すぎる。

読み取りロック:read lock と write lock を分ける。

ロックの粒度(granularity)が大事

小さくする
並列性が高まる。ロック自体のオーバヘッドが増える。 デッドロックが起こりやすくなる。
大きくする

◆2相ロック/Two phase locking

デッドロックが起きにくい、直列化可能な方法。
第1相(growing phase)
ロックの数が増える一方
第2相
ロックの数が減る一方

横軸、時刻、縦軸、ロックの数、第1相、増える、第2相、減る

図? 2相ロック/Two-phase locking

定理:トランザクションの実現で2相ロックを使うならば、インターリーブさ れることで作られるスケジュールは直列化可能である。

実際のシステムでは、Commit/Abort するまで、一度確保したロックをはなさない。 第2相で、まとめて全部ロックを解放する(strict two-phase locking)。

横軸、時刻、縦軸、ロックの数、第1相、増える、第2相、一発で減る

図? 2相ロック/Strict two-phase locking

利点

2相ロックでも、デッドロックは起きる。

注意:2相ロックと2相コミットは別。

◆楽観的並行性制御/Optimistic concurrency control

どんどんやって、後でまずかったことがわかった時点で abort する。 衝突が稀である時に有効。

実現(衝突時の対応):プライベート作業空間を使う実現が便利。 どんどんプライベート作業空間上のファイルを更新して、最後にコミットする か削除する。

性質

◆タイムスタンプによるトランザクションの実装/Implementing transactions with time stamps

操作にタイムスタンプを付けて、まずいものをアボートする。

アルゴリズム:

楽観的:同じファイルを独立したトランザクションで同時にアクセスすること は、あまりない。

Lamport のアルゴリズム等でクロックが同期されていれば、分散システムでも 使える。

◆分散システムにおける2相コミットによるトランザクションの実装/Implementing transactions with Two-phase commit in distributed sysems

2相コミット(two-phase commit)は、分散システムにおけるトランザクション の実装方法。(注意: 2相ロック(two-phase lock)ではない)。

2種類のプロセス

2つの相
第1相
全プロセスを Commit も Abort もできる状態にする。
  1. コーディネータは、ログに「準備」と書く。
  2. コーディネータは、サブオーディネートに「準備」メッセージを送る。
  3. サブオーディネートは、ログに「準備完了」と書く。
  4. サブオーディネートは、コーディネータに「準備完了」メッセージを送る。
  5. コーディネータは、全てのサブオーディネートからの応答を待つ。
第2相
実際に Commit する。
  1. コーディネータは、ログに「コミット」と書く。
  2. コーディネータは、サブオーディネートに「コミット」メッセージを送る。
  3. サブオーディネートは、ログに「コミット完了」と書く。
  4. サブオーディネートは、コーディネータに「コミット完了」メッセージを送る。
  5. コーディネータは、全てのサブオーディネートからの応答を待つ。
クラッシュした時には、ログから回復させる。

◆2相コミットの制約条件

https://www.slideshare.net/kumagi/ss-78765920,分散システムについて語らせてくれ by 熊崎宏樹

◆トランザクション分離レベルの例

ANSI/ISO SQL 標準で定義。Serializable は、重いので、多くの DBMS ではデ フォルトでは無効。
分離レベル ダーティーリード ノンリピータブル・リード ファントム・リード
Read Uncommitted
Read Committed
Repeatable Read
Serializable

■Argus

トランザクション機能を内部に含む言語。 発音は、英語読みでアーガス。ギリシャ神話読みでは、アルゴス。

Barbara Liskov: "Distributed programming in Argus", Communications of the ACM, Vol.31, No.3, pp.300-312, 1988. https://dl.acm.org/citation.cfm?id=42399

文法は、CLU 言語に似ている。

参考:

◆ガーディアン(guardian)

並行に動作するオブジェクト(現在の用語ではスレッド)を実現する。

◆安定な変数(Stable variable)

ガーディアンは、2種類の局所変数を持つ。
安定(stable)
クラッシュ(再起動)しても、生き残る。
揮発(volatile)
クラッシュ(再起動)すると、値が失われる。

◆アクション(action)

安定な変数に対するトランザクションを実現する。安定な変数を、整合性がと れた状態から、次の整合性がとれた状態へ遷移させる。( 途中でクラッシュしたら、元に戻す。)

トップアクション
トップレベルのトランザクションを実現する。commit するか abort するか。 内部にサブアクションを持つ。 abort したら、内部のサブアクションもすべて abort。
サブアクション
ネストしたトランザクションを実現する。
他のガーディアンのハンドラの呼出し(遠隔手続き呼び出し)は、 サブアクションになる。

◆Argusにおけるトランザクションの実装/Implementation of Transaction in Argus

◆ガーディアンの宣言/Declaration of guardians

  1. 名前 Name
  2. 生成ルーチン。引数の取得。Routines
  3. 安定な変数。Stable variables
  4. 揮発的な変数。Volatile variables
  5. ハンドラ手続き(外から呼ばれるエントリ)。Handlers
  6. バックグランド・ルーチン。ガーディアン自身のプログラム。 Backgroud routines.
  7. 復旧手続き。クラッシュ後に実行され、揮発的な変数を状態に戻す。 Recovery procedures.
安定な変数については、システムが自動的に整合性が取れた状態に復旧する。

◆銀行の支店/A bank branch in Argus

   1: branch = guardian is create handles total, open, close, deposit, withdraw
   2:   % type definitions
   3:   htable = atomic_array[bucket]
   4:   bucket = atomic_array[pair]
   5:   pair = atomic_record[num: account_number, acct: acct_info]
   6:   acct_info = atomic_record[bal: int]
   7:   account_number = atomic_record[code: string, num: int]
   8:   intcell = atomic_record[val: int]
   9: 
  10:   stable ht: htable    % the table of accounts
  11:   stable code: string  % the code for the branch
  12:   stable seed: intcell % the seed for generating new account numbers
  13: 
  14:   create = creator (c: string, size: int) returns (branch)
  15:     code := c
  16:     seed.val := 0
  17:     ht := htable$new()
  18:     for i: int in int$from_to(1, size) do
  19:       htable$addh(ht, bucket$new())
  20:     end
  21:     return (self)
  22:   end create
  23: 
  24:   total = handler () returns (int)
  25:     sum: int := 0
  26:     for b: bucket in htable$elements(ht) do
  27:       for p: pair in bucket$elements(b) do
  28:         sum := sum + p.acct.bal
  29:       end
  30:     end
  31:     return (sum)
  32:   end total
  33: 
  34:   open = handler () returns (account_number)
  35:     intcell$write_lock(seed) % get a write lock on the seed
  36:     a: account_number := account_number${code: code, num: seed.val}
  37:     seed.val := seed.val + 1
  38:     bucket$addh(ht[hash(a.num)], pair${num: a, acct: acct_info${bal: 0}})
  39:     return (a)
  40:   end open
  41: 
  42:   close = handler (a: account_number) signals (no_such_acct, positive_balance)
  43:     b: bucket := ht[hash(a.num)]
  44:     for i: int in bucket$indexes(b) do
  45:       if b[i].num != a then continue end
  46:       if b[i].acct.bal > 0 then signal positive-balance end
  47:       b[i] := bucket$top(b) % store topmost element in place of closed account
  48:       bucket$remh(b) % discard topmost element
  49:       return
  50:     end
  51:     signal no_such_acct
  52:   end close
  53: 
  54:   lookup = proc (a: account_number) returns (acct_info) signals (no_such__acct)
  55:     for p: pair in bucket$elements(ht[hash(a.num)]) do
  56:       if p.num = a then return (p.acct) end
  57:     end
  58:     signal no_such_acct
  59:     end lookup
  60: 
  61:   deposit = handler (a: account_number, amt: int) signals (no_such_acct, 
  62:                                                                 negativ_amount)
  63:     if amt < 0 then signal negative_amount end
  64:     ainfo: acct_info := lookup(a) resignal no_such_acct
  65:     ainfo.bal := ainfo.bal + amt
  66:   end deposit
  67: 
  68:   withdraw = handler (a: account_number, amt: int) signals (no_such_acct, 
  69:                                          negative_amount, insufficient_funds)
  70:     if amt < 0 then signal negative amount end
  71:     ainfo: acct_info := lookup(a) resignal no_such_acct
  72:     if ainfo.bal < amt then signal insufficient_funds end
  73:     ainfo.bal := ainfo.bal - amt
  74:   end withdraw
  75: end branch

■Etherium-Solidity

Etherium は、ブロックチェーン技術の一種。

◆銀行の口座/A bank account in Solidity

contract Bank {

    mapping(address => uint256) public accounts;


    function deposit() {
        accounts[msg.sender] += msg.value;
    }

    function withdraw(uint256 amount) {
        if(amount > accounts[msg.sender])
	    throw;
        accounts[msg.sender] -= amount;
        if(!msg.sender.send(amount))
	    throw;
    }

    function get_balance() {
      return accounts[msg.sender];
    }

}
deposit() は、送信元のアカウントから amount 分のether を受け取る。 withdraw() は、メッセージの送信元に、預かっている ether を amount 分だけ返す。 残高を確認し、先に accounts[msg.sender] を減らしてからトランザクション を行わないと、複数同時に withdraw() が呼ばれた時に、問題が生じる。

get_balance() は、残高照会。 状態を変えないので、トランザクションではなく call で実行できる。

■投機的実行/Speculative execution

投機的実行(speculative execution)、将来利用されるか利用されないか確定さ れる前に実行を開始してしまうこと。楽観的実行(optimistic execution)とも言う。

    if( a() ) {
        b();
    }
    else {
        c();
    }

if( a ) then b else c

図? 投機的実行 Speculative execution

この例では、a() が完了した時には、b()、c() が終わっていた時には、見かけ 上、即座に終わる。

◆HOPE

C. Cowan and H. L. Lutfiyya: "A wait-free algorithm for optimistic programming: Hope realized", In Proceedings of the 16th International Conference on Distributed Computing Systems(ICDCS), pages 484-493, 1996.

RPCの遅延を隠す。 This paper proposes hiding RPC delays by using optimistic execution.

◆世界OS/World OS

新城の研究成果。
  1. 根路銘, 當眞, 新城, 喜屋武, 翁長: "粗粒度投機的並列処理を支援 するオペレーティング・システムの構想", SWoPP'94, 情報処理学会研究会報 告94-ARC-107-12, Vol.94,No.66, pp.89-96 (1994年7月).
  2. Jun Sun, Yasushi Shinjo and Kozo Itano: "The Implementation of a Distributed File System Supporting the Parallel World Model", The Third International Workshop on Advanced Parallel Processing Technologies, pp.43-47 (Oct.19-21, 1999).
  3. 石井 孝衛, 新城 靖, 板野 肯三: "プロセストレース機能を用いた世界 OSの実現",情報処理学会論文誌, Vol.43, No.6, pp.1702-1714 (2002年6月).
  4. 今里邦夫, 鈴木真一, 新城靖, 板野肯三: "動的リンクとパケットフィル タを用いた世界OS のネットワーク機能の実現",日本ソフトウェア科学会第6回 プログラミングおよび応用のシステムに関するワークショップ(SPA 2004), ポ スターセッション (2004年3月1-3日).
  5. Yasushi Shinjo, Wataru Ishida and Jinpeng Wei: "Implementing a parallel world model using Linux containers for efficient system administration", IEEE Second International Workshop on Container Technologies and Container Clouds (WoC 2018), 7 pages (2018).

SF (Science Fiction) のパラレルワールド(parallel world, parallel universe)を、オペレーティング・システムのレベルで実現する。

サイコロをふる度に地球が6つに分裂する

図 SFのパラレルワールド

SFでは、時々別の世界にジャンプしたり人が入れ替わったりする。

◆Undo できるOS/Undoable OS

Undo とは、do の効果を打ち消して、もともと do しなかったことにする。 (do not とは違う。)

世界OSでは、ファイルの内容を変更すると、2つの世界ができる。

世界を作りファイルを書き換えうまくいけば融合、失敗すれば削除する。

図 世界OSで使える世界の操作

実際には、先に世界を作り、その中でファイルの内容を書き換える。うまくいっ たら、融合する。失敗すれば削除して、変更の結果を無効にする。

普通の仮想計算機では、融合はできない。継承のコストが大きい。

◆パラレルワールドの利用/Usage of parallel worlds

練習問題

以下の *全て* の問いについて答えなさい。 Answer *all* of the following questions.

次の内容を含む「テキスト」ファイルを作成し、 レポート提出ページ から提出しなさい。 締切りは、2019年8月13日、 23:59:59 とする。

★問題(1001) トランザクションによる銀行口座間の送金/Transferring money between two bank accounts by transaction

2つの銀行口座の間で送金するプログラムの「概略」を、トランザクションを使っ て簡単に書きなさい。基本となる言語としては、C言語、Java言語、Ruby言語、 または、それに類するものを使いなさい。トランザクションを実装するための ライブラリ関数が利用可能であるものとする。そのようなライブラリ関数には、 トランザクションを実現するための命令 と類似の名前をつけなさい。

なお、この問題では、概略を示せば十分であり、変数宣言の欠如や型の不一致 等のコンパイラが検出するような誤りは、減点しない。

Write a sketch of a program that transfers money between two bank accounts. You may use the syntax of the C, Java, or Ruby language. You can use the library functions that implement transactions. These library functions must have good names that are similar to the operations to realize transaction.

You do not have to write a runnable program in this question. You do not have to fix compilation errors, such as no variable declaration and type incompatibility.

★問題(1002) ロックとの比較/Comparisons with locking

問題(1001) で、ロックを使う方法と比較して、トラン ザクションを用いる方法の利点を示しなさい。

In 問題(1001) , write advantages of using transaction over using locking.

★問題(1003) Argus

Argus 言語のガーディアンと次の言語の要素のどれかと比較しなさい。 重要な類似点1つと重要なガーディアンの優位性1つを述べなさい。 Compare guardians in Argus language with elements in either of the following languages. Write an important similarity and an important advantage of guardians.
Last updated: 2019/08/14 10:40:50
Yasushi Shinjo / <yas@cs.tsukuba.ac.jp>