u-ar’s blog

研究や技術について。もろもろ。

【読書メモ5-1】Transactional Information Systemsを読んでいる

はじめに

修論なりで更新が滞っていたので、読み途中ではあるがTransactional Information Systemsの読書メモを書いておくことにする。

英語で700P超えの大著なので読むのには気力がいる。そしてkindle版でも1万超えという専門書の風格。

www.amazon.co.jp

日本語でまとめた資料をHackMDで作りながら読んでいるので、原著を読むのがしんどいという方に参照していただければ幸いである。

hackmd.io

全体的な感想

『データベース実践入門』でおすすめされていたので気になって読み始めたが、確かに面白い。

まず、この本はデータベース分野の中でもトランザクションについての話題だけを取り扱っている。いわゆるACID特性を満たすための、同時実行制御と障害回復アルゴリズムについて、それぞれ1部ずつ割いて丁寧に説明されている。

データベース分野で最も研究が進んできたトランザクションの概念を、データベースに限定しない一般的な概念として定義しなおしている。曰く、トランザクションとは本質的に、アプリケーションプログラムと複数のトランザクションサーバの間の契約で、複数のリクエストを単一の論理的な単位としてまとめて取り扱うためのもの、とのことである。また、最大の見どころは、複数のトランザクション逐次実行可能性(serializability)に対する数学的に厳密な特徴づけを与えているところである。

どうしても最重要の応用先がDBMSなので、実装の詳細に踏み込んで語っている部分もある(特に後半の障害回復)が、前半部の逐次実行可能性の定式化なんかはよく抽象化されていて一般的な議論になっている。同値類なんて言葉をここで見られるとは予期していなかったのでなんだかうれしい。

現在読み終わっている第2部まで、各章の概要と感想を述べていくことにする。詳細な定義や定理なんかはHackMDを参照。

章別感想

第1部

第1章 概要

トランザクションについて考えていくにあたり背景となる項目について述べている。トランザクションが満たさなければならないACID特性であったり、DBMSに求められる性能要件であったり、DBMSの基本的な実装についてであったりがさらっと。

第2章 計算モデル

トランザクションについての定義を明確に与え、また複数のトランザクションの集合体であるスケジュール(DBMSのスケジューラに順次与えられるリクエストの列を抽象化したもの)についても定義している。ここで、2種類の計算モデル、「ページモデル」と「オブジェクトモデル」が定義される。

  • ページモデル:ページのみが操作の対象となるデータであり、トランザクションが各ページpに対する読み込み r(p) と書き込み w(p) 、コミット c 、中断 a のみからなるモデル。最も単純化されているが、だからこそかえって本質を掴むのに役立つ。
  • オブジェクトモデル:ページに限らない、より抽象的なデータオブジェクトへの操作を許したモデル。あるデータオブジェクトへの操作が、実質的には複数のページへの操作を必要としたりするので、トランザクションは必然的に木構造をとることになる。トランザクションが単なる操作列であるページモデルと、そこが大きく異なる。

この本では基本的に、ページモデルについての性質を述べ、それをオブジェクトモデルに一般化する、という形で議論が進む。実際、オブジェクトモデルに一般化する際にそれほど苦労を伴っていないので、まずページモデルで本質的な議論をするという試みが成功していることが分かる。

第2部

第3章 同時実行制御:ページモデルにおける正当性の定義

まず、複数のトランザクションからリクエストが送られてきたとき、それを愚直に到着順のまま実行するといろいろな問題が起きる。例えば以下。

  • lost update
  • inconsistent read
  • dirty read

したがって、トランザクションを並列実行するにあたって、スケジュールをどの順番で実行するのか決定するアルゴリズムを備えたスケジューラが必要になるわけである。まずこの章では、スケジューラに生成させたいゴール地点として、ある意味で「正当」なスケジュールの集合を定義している。スケジューラの具体的なアルゴリズムは4章以降で導入される。

では、スケジュールの「正当性」とはどう定義されるのだろうか?

根底にあるアイディアはこの2つ。

  • 少なくとも、逐次実行するようなスケジュールは自明に正当といえる。例えば、トランザクションt1とt2とt3があったとして、t1を実行し、終わったらt2を実行、それが終わったら今度はt3、というように順番に行う場合、これは並列実行に起因する問題を一切引き起こさない。
  • そのような逐次実行スケジュールと、なんらかの意味で等価なスケジュールもまた、正当といえるのではないか。

そこで、数学は集合論における同値類の概念を用いることにする。スケジュール全体の集合を考え、スケジュール間の同値性を定義し、逐次的なスケジュールと同値なスケジュール全体の集合を「正当」なスケジュールの集合として定義するわけである。

ここで、定義する同値性の種類に応じて、複数の正当性基準が誕生することになる。

  • Final State Serializablity (FSR)
  • View Serializability (VSR)
  • Conflict Serializablity (CSR)

他にも細かく定義されているが、とりあえずこの三者が最も代表的。これらのスケジュール集合は CSR\subset VSR \subset FSR の関係を満たす。つまり、CSRが最も厳しい基準である。

lost updateもinconsistent readも防ぐにはCSRが必要(FSRやVSRでは力不足)で、またCSRは判定が容易という圧倒的な強みを持っているので、基本的にスケジューラはCSRを達成するように設計される。少し踏み込んで言うなら、スケジュールがFSR/VSRに属するかの判定はNP-hard、一方でCSRトランザクションをノードとして作ったConflict Graphなるグラフの閉路存在判定によって容易に確かめられる。

第4章 同時実行制御アルゴリズム

第3章で導入された正当なスケジュールについて、それを達成するようなアルゴリズムについて記述されている。

まずはロックを用いたスケジューラ。つまり、データを操作するときにはそのデータにread/writeロックをかけ、かかっている間は他のトランザクションからの操作が禁止されるような機構を用いて同時実行制御を行うアルゴリズムである。 ロックを使う、というだけだと何も保証されない。大事なのは二相ロック(2 Phase Locking, 2PL)、つまりトランザクションが2つのフェーズに分けられ、前半のフェーズではロックの取得のみが許され、後半のフェーズではロックの解放のみが許されるというような性質が満たされたときに限り、生成されるスケジュールがCSRに属することが保証される。実用的には、トランザクションが終了する直前に全ロックを解放すれば簡単に2PL性を満たせることになる。

次にロックを用いないスケジューラ。紹介されているのはTimestamp Ordering(TO)、Serialization Graph Testing(SGT)、Backward-oriented Optimistic Concurrency Control(BOCC)、Forward-oriented Optimistic Concurrency Control(FOCC)の4つ。TOはトランザクションのタイムスタンプに応じて実行の可否を決めるもの。SGTはConflict Graphを保持しながら、その閉路判定を踏まえてCSR性を保証するもの。BOCCとFOCCは楽観的なプロトコルという分類に属し、トランザクションの内容はとりあえず全部実行するが、コミットの段階になってそれがコミットされてもいいか検証を行う。

最後にこれらを組み合わせたハイブリッドなスケジューラについてもさらっと。

第5章 マルチバージョン同時実行制御(MVCC)

ここまでで述べられてきた計算モデルにおいて、各データは唯一のものしか許されていなかった。例えば、ある時点において、ページ  p の内容はどのトランザクションから見ても全く同じであり、他のバージョンが存在するなどということは考えなかった。ここで制限を緩め、複数のバージョンが存在してもよく、過去のバージョンを読み込むこともできる、と仮定すると、もっといろいろなスケジュールが逐次実行可能になってくる。

そのような、マルチバージョンという状況下での逐次実行可能性、および同時実行制御アルゴリズムについて述べられているのが本章。

マルチバージョン的な意味でのVSRとCSRに相当するMVSR、MCSRというクラスが定義されるのだが、こちらの同時実行制御アルゴリズムではMCSRでなくMVSR性が保証されることが少し不思議である。また、VSRとMVSRの関係や、バージョン数を制限した場合に生じるクラス間の関係なども生じてきて、その辺のベン図を眺めているのがとても面白い。

第6章 オブジェクトモデルにおける逐次実行可能性

第3章におけるページモデルの逐次実行可能性を拡張し、オブジェクトモデルにおける正当性が定義される。

CSRは複数のトランザクション間で「競合」する操作(同じデータに対するread/writeまたはwrite/write)を定義し、それらの実行順を変えないまま逐次実行順に並び替えられるスケジュールのクラスであった。

それを拡張して、いわばオブジェクトモデルにおけるConflict Serializabilityに相当するTree Reducibilityが定義される。まずオブジェクトモデルにおける操作間の可換性を与える(ページモデルにおけるread/writeと異なり、独自定義の操作が許されているために可換性も自分で与えなければならない)。可換な操作の間でのみ実行順を入れ替え、他のトランザクションと切り離すことのできた部分木の枝刈りを許して木を変形していき、最終的にトランザクション群が逐次的に並び替えられたら正当、といった具合になる。

この章あたりは、ページモデルから簡単に導けるという口実の下にかなり端折られているので少し戸惑う。あと、モデルが複雑なので仕方ないのだが、導入される定義が結構複雑な言葉からなっていて理解に苦労する。

第7章 オブジェクトモデルにおける同時実行制御

まず、オブジェクトモデルスケジュールの中でも特殊ケースである「平坦」なスケジュールから始まり、次に「階層的」なスケジュールに対して、最後に一般のスケジュールに対しての同時実行制御アルゴリズムが導入される。

まず平坦なスケジュールとは、各トランザクションがレコード操作からなり、レコード操作がページ操作からなる、というような2層構造をしており、これはそれぞれの層に別個に2PLなどのアルゴリズムを使えば簡単に制御できる。

次に、層が増やされた階層的なロックについても基本的に各層にページモデル用のを適用するだけ。

最後に一般のスケジュールについては、階層的なものと違って、全ての操作が全ての層を経由するわけではないため、そういった抜けを管理するためにretained lockなる層をまたぐロックの概念を必要とする。それを除けば階層的なロックと同様である。

retained lockが実用においては重いため、スケジュールが階層的であることを要求した上で各層にページモデルスケジューラを適用するのが、商用システムにおける基本となっているようだ。

第8章 RDBMSにおける同時実行制御

RDBMSという特定の応用下での同時実行制御の話題を述べているが、個人的にさして興味深くないので割愛。ただ述語指向のロック制御の話は割と重要だと思う。

第9章 インデックスにおける同時実行制御

こちらもDBMSにおけるインデックスという特定のデータ構造でのロック制御について記述されているが、アルゴリズミックなのでなかなか面白い。

インデックスはB+木という木構造をしており、その構造特有の性質を活かして2PLよりも少し緩いアクセス制御を行っても許される。レコードレベルとページレベルのそれぞれのレベルにおけるロック制御法を紹介した上で、最適化の話もちょろっとされている。

第10章 実装における諸問題

ロック管理機構の具体的な実装法であったり、マルチバージョン制御の実装であったり、SQL標準におけるserializabilityの取り扱われ方だったり、負荷制御だったりという実際的な問題に関する雑多な話題。

おわりに

そろそろまた読書を再開できそうなので、第3部・第4部もしっかり読み終えたいところ。終わったらそちらもまとめるつもり。