トランザクション

並行システム

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

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

■連絡事項

■今日の重要な話

■トランザクション

相互排除、デッドロックより高いレベルの抽象が欲しい。

ロックよりも楽にプログラムを作りたい。

特に分散では。集中でも、フォールト・トレランスの実現では必要。

◆トランザクションの意味

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

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

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

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

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

◆特性(ACID)

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

◆直列化可能(serializable)

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

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

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

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

図? トランザクションの処理(並行実行)

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

図? トランザクションの処理(直列化の例その1)

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

図? トランザクションの処理(直列化の例その2)

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

図? トランザクションの処理(直列化の例その3)

◆例

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

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

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

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

◆トランザクションの実装(集中)

◆プライベート作業空間

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

ファイルのコピー、インデックス、ブロック、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))、他のディスクからコピーして回復する。

◆並行性制御

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

◆ロッキングによるトランザクションの実装

もっとも単純な方法: Begin Transaction で、ファイルをロックする。 Commit/Abort でアンロックする。

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

制約が強すぎる。

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

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

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

◆2相ロック

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

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

図? 2相ロック)

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

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

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

図? 2相ロック)

利点

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

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

◆楽観的並行性制御

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

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

性質

◆タイムスタンプによるトランザクションの実装

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

アルゴリズム:

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

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

◆2相コミットによるトランザクションの実装

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. コーディネータは、全てのサブオーディネートからの応答を待つ。
クラッシュした時には、ログから回復させる。

■Argus

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

Barbara Liskov: "Distributed programming in Argus", Communications of the ACM, Vol.31, No.3, pp.300-312, 1988.

◆ガーディアン(guardian)

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

◆安定な変数

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

◆アクション(action)

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

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

◆トランザクションの実装

◆ガーディアンの宣言

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

◆銀行の支店

   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

■投機的実行

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

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

if( a ) then b else c

図? 投機的実行

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

◆世界OS

新城の研究成果。
  1. 根路銘, 當眞, 新城, 喜屋武, 翁長: "粗粒度投機的並列処理を支援 するオペレーティング・システムの構想", SWoPP'94, 情報処理学会研究会報 告94-ARC-107-12, Vol.94,No.66, pp.89-96 (1994年7月).
  2. 石井 孝衛, 新城 靖, 板野 肯三: "プロセストレース機能を用いた世界 OSの実現",情報処理学会論文誌, Vol.43, No.6, pp.1702-1714 (2002年6月).
  3. 今里邦夫, 鈴木真一, 新城靖, 板野肯三: "動的リンクとパケットフィル タを用いた世界OS のネットワーク機能の実現",日本ソフトウェア科学会第6回 プログラミングおよび応用のシステムに関するワークショップ(SPA 2004), ポ スターセッション (2004年3月1-3日).

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

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

図 SFのパラレルワールド

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

◆Undo できるOS

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

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

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

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

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

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

◆パラレルワールドの利用

◆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の遅延を隠す。

練習問題

★問題(1001) トランザクションによる送金

2つの銀行口座の間で送金するプログラムの「概略」を、トランザクションを使っ て簡単に書きなさい。基本となる言語としては、C言語、Java言語、Ruby言語、 または、それに類するものを使いなさい。トランザクションを実装するための ライブラリ関数が利用可能であるものとする。そのようなライブラリ関数には、 トランザクションを実現するための命令 のどれに相当するのかが簡単にわかるような名前をつけなさい。 なお、この問題では、概略を示せば十分であり、変数宣言の欠如や型の不一致 等のコンパイラが検出するような誤りは、減点しない。

★問題(1002) ロックとの比較

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

★問題(1003) Argus

Argus 言語のガーディアンと次のどれかと対比しなさい。類似点と相違点を述 べなさい。
Last updated: 2012/02/23 08:23:13
Yasushi Shinjo / <yas@cs.tsukuba.ac.jp>