2019-05-12

トランザクションとXのきもち

ポエム

（このポストはトランザクションとは関係ありません）

トランザクションをTXと略すことがある。

これはtransactionを、同じ発音で読めるtranxtion（またはtranxaction）と書いたときの音節ごとの先頭文字をとってきたものである。

一方、トランザクションをXと略すことがある*1。

これはtransactionをxactionと書いた時の先頭文字をとってきたものである。

ここでxはtrans-という接頭辞に対応していることになる。

同様の省略のされ方は他にもあり、例えば

今流行りのDXはDigital Transformationの略（Transformation → Xformation）
昔のPCのキーボードにあったxferキーは、おそらくtransferの略
C言語の標準ライブラリ関数のstrxfrmは、おそらくstring transformの略（transform → xform → xfrm）

なぜtrans-接頭辞をxと書くのかについて昔疑問に思ったときは、それを説明するサイトを見つけられなかった。

trans-という接頭辞の意味は、weblioによると、

「越えて」「横切って」の意、「貫いて」「通って」「完全に」の意、「他の側へ」「別の状態へ」の意、「超越して」、「…の向こう側の」の意

とのことだったので、当時は、彼我の位置を入れ替えるときの軌跡がXを描くからだ、と解釈した。以下の図のイメージ。

f:id:dev_supisula:20190512010730p:plain

いまぐぐってみたところ、英語学習者向けのQAサイト？でHow did “trans-” become “x-”?という投稿を見つけた。

最初の回答に、「xはcrossのgraphical representation」とあるので、もっと単純に境界を超える、越境のイメージのようだ。

f:id:dev_supisula:20190512011312p:plain

おしまい

*1:PostgreSQLのXIDとか

2019-05-12

NP完全性のメモ（１）

0. まとめ

0.1 P, NP, NP完全

計算複雑度のクラスP (complexity class P)とは、多項式時間で解ける問題の集合である。

計算複雑度のクラスNP (complexity class NP)とは、多項式時間で検証可能な問題の集合である。問題を解くより検証の方が簡単なので、 $P \subset NP$ まはた $P = NP$ のどちらかである（が多くの研究者は $P \ne NP$ だと信じている）。

問題が以下の全てを満たすならば、NP完全 (NP-complete)であるという。

その問題がNPに属する。かつ、
NPに属するすべての問題に対し、多項式時間でその問題に帰着可能である場合。

NPに属する問題の中で、最も難しい問題からなる集合(NPの部分集合) がNP完全な問題である。

NP完全な問題はNPに属する他のどの問題よりも同じかより難しいので、もしもNP完全な問題の一つについて多項式時間で解ける（クラスPに属する）ことが証明できれば、NPに属するすべての問題が多項式時間で解ける ( $P=NP$ である) ことが証明されるという強力なものである（だからこそ、 $P \ne NP$ であると信じられている）。

0.2 NP完全性の証明

すでにNP完全であることが証明された問題があるので、それを利用して以下の2つを確かめることにより行う。

問題がNPに属することを証明する。
NP完全であることが証明されている問題から（from）、対象の問題へ（to）多項式時間で帰着可能であることを証明する。

一つ目は対象の問題の難しさの上限を確認するもの（少なくとも検証は多項式時間でできる）、二つ目は対象の問題の難しさの下限を確認するもの（少なくともNP完全な問題よりは同じか難しい）である。

1. はじめに

NP完全性についての理解が怪しかったので、学生時代の教科書を（年末年始休暇に）引っ張り出して読み直しました。以下の本「アルゴリズムイントロダクション第3巻精選トピックス」の第36章がNP完全性の章です。

上記の本は分冊版（全3巻）ですが、現在は原著第3版の翻訳（統合版）が出ており、こちらの第34章が該当の内容のようです（未確認）。

以降は主に本の説明の流れに沿って用語の定義などをまとめています。見出しのタイトルは私がつけたものです。元の第36章の各節のタイトルは以下です。

多項式時間
多項式時間の検証
NP完全性と帰着
NP完全性の証明
NP完全問題

修正中…

2019-04-19

トランザクションの参照透過性&副作用およびHerbrand Semanticsについて

TX ポエム

トランザクションの参照透過性と副作用

前回のポストでは、関数の参照透過性と副作用について書きました。

本ポストでは、（データベースにおける）トランザクションの参照透過性を以下のように定義する。

トランザクションのすべての作用が、トランザクションがデータベースからreadした情報だけに依存するとき、そのトランザクションには参照透過性があると定義する。
トランザクションの作用とは、データベースのdata itemへのwriteである。
つまりトランザクションがデータベースへwriteする内容が、そのトランザクションがデータベースからreadした情報だけに依存して決まるとき、そのトランザクションには参照透過性がある。

また本ポストでは、（データベースにおける）トランザクションの副作用を以下のように定義する。

トランザクションの実行によって影響を及ぼす範囲が、データベースのdata itemだけに閉じているとき、そのトランザクションには副作用がないと定義する。

この定義によると、トランザクションとデータベースの間の界面がトランザクションの主たる界面（副ではないという意味で）となる。

Herbrand Semanticsとは

Herbrand Semanticsとは、トランザクションが何を引き起こすか、トランザクションのその意味をモデル化する方法である。

TIS（Weikum本）のDefinition 3.3では、ステップについてのHerbrand Semanticsが次のように定義されている。

DEFINITION 3.3 Herbrand Semantics of Steps

Let s be a schedule. The Herbrand semantics H_s of steps r_i(x), w_i(x) ∈ op(s) is recursively defined as follows:

H_s(r_i(x)) := H_s(w_j(x)), where w_j(x), j ≠ i, is the last write operation on x in s before r_i(x).

H_s(w_i(x)) := f_ix(H_s(r_i(y₁)),..., H_s(r_i(y_m))), where the r_i(y_j), 1 ≤ j ≤ m, represent all read operations of t_i that occur in s before w_i(x), and where f_ix is an uninterpreted m-ary function symbol.

Weikum, Gerhard; Vossen, Gottfried. Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems) （ページ74). Elsevier Science. Kindle 版.

これは以下のように解釈できる。

トランザクションt_iがdata item xにwriteする値は、そのトランザクションt_iが（そのwrite step以前に）readしたすべてのdata itemの値と、そのトランザクションt_iのそのwrite step固有の関数f_ix のみに依存して決まるとする考え方。

Definition 3.3に続く文章では、スケジュール内の全てのトランザクションに先行する（各data itemの初期値をwriteだけする）特別なトランザクションt₀によって書かれたという考え方を取り入れている。これによりf_ixを展開していくと、各data itemの値は最終的には、関数f_ixの組み合わせだけに還元できる。

Herbrand Senanticsにつては以下も参考になります。

Herbrand Senanticsと参照透過性

TISのDefinition 3.3 Herbrand Senantics of Steps を見る限り、この定義におけるトランザクションには参照透過性がある。言い換えると、参照透過性があるトランザクションを一見、前提にしているように見える。

Herbrand Senanticsにおける副入力の解釈

例えば銀行口座間の送金トランザクションを考えると、２つの口座番号と送金金額はプログラム上はパラメタライズされており、外部から与えられた情報をもとにして初めて実体化される。

この外部からの入力は、参照透過性の観点における副入力に他ならないのではないかという疑問が湧く。しかしこれは以下のように解釈できる。

トランザクションは（トランザクションの識別性は）、そのロジックとパラメタを組み合わせたものである。パラメタが異なる（例: 口座番号や金額が異なる）トランザクションは別のトランザクションである。

このように考えると、すべての副入力はトランザクションのロジックと区別がつかなくなり、トランザクションに副入力は存在しないことになる。

トランザクションの副作用

トランザクションの作用はdata itemへのwriteであり、それ以外は副作用と見なすと定義した。

データベース管理システムで実行されるトランザクションは応答を返す。応答が観測されるなら、これは副作用になり得る。

トランザクションの実行モデル

トランザクションが実行されるモデルとして以下の３つを考える。

すべてのトランザクションが投入され終わらない限り、いずれのトランザクションの応答も返ってこないモデル。
- すべてのトランザクションが投入されてから初めて、実行がスケジューリングされるモデルと見なせる
１つのトランザクションがまとめて一度だけシステムに渡され、一度だけ応答を返すモデル。
- One-shotモデル？
１つのトランザクションにつき複数回のやり取りを許すモデル。
- SQLのステートメントごとに要求と応答を繰り返すような対話型モデル

これらのうち１つ目のモデルでは、あるトランザクションの応答を別のトランザクションが参照することがないため、副作用はないものと見なせる。

一方残りの２つのモデルでは、他のトランザクションの応答を観測しうるので、このモデルにはトランザクションの副作用が存在し得る。

異なるトランザクションの間に外部の依存関係があった場合

あるトランザクションXの（完了）応答が、別トランザクションYの振る舞いに影響を与えている場合を考える。

例えば、ある送金トランザクションXの実行結果によって、別の送金トランザクションYの金額や送金差先が変更されるような状況である。

このときXの応答は別のトランザクションの振る舞いに影響を与えている（観測された）ので、これは明らかに副作用である。（一方、先の議論で、トランザクションの参照透過性を脅かす副入力は存在しないことになっている。）

このようなトランザクション間の外部の依存関係はトランザクションマネージャには捕捉されないので、トランザクションマネージャは、Y→Xというような順序付けを行う可能性がある。

これは外部の依存関係を知る者にとっては明らかに誤りだが、トランザクションマネージャは何らかのserial scheduleとequivalentだと判断したはずである。

Herbrand Semanticsにおける副入力の扱いを踏まえると、以下のような状況である。

まずトランザクションXのテンプレートX<T>とトランザクションYのテンプレートY<S>があった。
（X<T>から実体化された）トランザクションX<A>の応答をもとに、テンプレートY<S>のパラメタSがBと決定された。
トランザクションY<B>が実行された。
実際の依存関係はX<T>→Y<S>であったが、トランザクションマネージャはY<S>→X<T>と順序付けた。

もし実際の順序がY<S>→X<T>であったなら、パラメタSはBにはなりえなかった。つまりこの順序の場合、Y<B'>→X<A>である。一方、実際はX<A>→Y<B>である。

まとめると以下のような状況になる。

trans() ＼順序	X→Y	Y→X
`{X<A>,Y<B>}`	①あり得る	②あり得ない
`{X<A>,Y<B'>}`	③あり得ない	④あり得る

トランザクションマネージャは②を選択したが、①と比較すれば順序付けが誤っていたと見えるし、④と比較するとequivalentだと思ったスケジュールのトランザクション集合が実は異なっていたと見える。

外部の依存関係を許すか

上記のような外部の依存関係を許さないシステムが多かったのではないかと想像します。

一方で、DBMSがUDFに対して参照透過性や副作用が無いことを要求するのとおなじように、アプリケーション/トランザクションにそれを要求できるかというと難しいと思われる。

なぜなら、通常UDFが触れている世界とDBMSの世界ではDBMSの扱う範囲の方が広く、だからDBMSはUDFに「必要なものはすべて私が与えるからそれ以外の界面でやりとりするな」という主張に納得できる部分もあるが、DBMSの世界よりアプリケーションが触れる世界の方が大きいから、DBMSがアプリケーションに「必要なものはすべて与える」という主張は滑稽に見える。

しかしこれも、データベースの性質によっては言えるかもしれない。例えば以下のご本尊系データベースの場合。

データベースには二種類ある。ひとつは実世界の状態の複製であるところのデータベースで、もうひとつはデータベース自体が本体、マスタ、オリジナル、ご本尊であるところのデータベースだ。
— デヴすぴスラ (@dev_supisula) 2019年2月14日

トランザクションの単位

上記のような依存関係があるなら、別のトランザクションにするのではなく、１つのトランザクションにすべきだ、という主張が考えられる。

しかし一般にトランザクションの単位とはなにか、というとそれは永続化のatomicity、および分離のatomicityの単位と認識されているのではないか。依存関係のスコープを表す手段としてのトランザクション、という考え方は一般的ではないのではないか。

この問題の回避

外部の依存関係は実時間の流れる方向にしか発生しないはずだ。

だから、one-shotモデルの場合は既存のプロコトルに以下の制約を付け加えればよい。

ｰ Tx < Ty | cx < by の場合。ここでcxはトランザクションTxの完了応答時刻で、byはトランザクションTyの到着時刻

この制約は、トランザクションに（分散処理の文脈における）consistencyを導入することに対応するはずだ。

再びHerbrand Senantics

TISのp.73のIdea of Herbrand Senanticsは次のように書かれている。

a step wi(x) ∈ s writes a new value that potentially depends on the Idea of Herbrand semantics values of all data items that ti has read from the database or from other transactions in active(s) ∪ commit(s) prior to wi(x).

強調部分を読むと、副入力を想定しているようにも見える。しかしこれがdefinition 3.3になると、データベースとの入出力だけに限定されているように読める。

その他

トランザクションの副作用を考えたとき、対話型モデルではステートメント毎の応答が他のトランザクションに影響を（isolationを無視して）及ぼしうる。

またone-shotモデルでも、abort応答が他のトランザクションの振舞いに影響を与えるかもしれない。

これらはどう扱えばよいのか…。

2019-04-17

関数の参照透過性と副作用についてのメモ

ポエム

概要

プログラミング言語やUDF機能を提供するシステムにおいて関数が持っていると嬉しい性質として以下の2つがある。

関数の返す値は、関数の引数に与えた値だけに依存して決まる（参照透過性がある）。
関数は、値を返す以外の作用（副作用）を行わない（副作用がない）。

上記の2つの性質を持つ関数は、関数の処理系のコンパイラやオプティマイザによって最適化することができる。例えば、

関数の引数が定数の場合、その関数の値（計算結果）をコンパイル時に決定できるので、実行コードにおける関数の呼び出しをなくすことができる。
同じ関数に同じ引数を与えている箇所があれば、2回目以降の関数の呼び出しをなくし、1回目の関数の計算結果に置き換えることができる。

関数に参照透過性がない場合

同じ関数に同じ引数を与えたとしても同じ結果を返すとは限らないため、コンパイラ／オプティマイザはその結果を事前計算orキャッシュすることができない。

参照透過性がない関数とは例えば、システム時刻を返す関数であったり、乱数によって振舞いを変えたり、通信やIO等の外部からの入力を利用したりするものである。

関数に副作用がある場合

副作用がある関数とは、例えば関数の実装の中でログに出力するような関数である。

そのため最適化によって関数呼び出しが削除されてしまうと、残るべきログが残らないという事態が起こる。

参照透過性と副作用のイメージ

関数の引数（INPUT）と、関数の計算結果（OUTPUT）による界面（インターフェイス）を通常と考えると、それ以外の界面からの入力があると参照透過性を脅かし、それ以外の界面への出力があると副作用となりうる。

参照透過性と副作用の関係

両者は独立して存在しうる。

参照透過性があるが副作用を持つ関数も存在するし、副作用はないが参照透過性がない関数もありうる。

参照透過性と副作用は本当に独立か？

副作用がない関数がありうると書いたが、実際には何を副作用とみなすかは程度問題である。

ログ出力は典型的な副作用であるが、ログが最適化で省略されても問題ないのであれば、その副作用は無視できる。

また世の中にはサイドチャネル攻撃というものが存在するので、ふつうに考えて副作用がないような関数も、同じコアで同時実行される別のスレッドのスケジューリングやCPUの電力消費や電波の輻射等の形で外部に影響を与えるため、これを副作用とみなすこともできる。

その意味で副作用とは、その副作用を観測するものの存在ぬきでは語れない。

参照透過性のない関数は、そのような副作用を観測するものの一つである。

2018-09-27

辞書式順序とユーザ定義型

ポエムトライ木

トライ木（Trie）というデータ構造がある。トライ木についてはWikipedia (ja)、Wikipedia (en)を参照。

2018-09-27

dbts2018 A13/C33（トランザクション関係）聴講メモ

ポエム TX

db tech showcase 2018 Tokyoの以下のセッションを聴講したメモです。

A13 今後のDBのトランザクション処理のあり方について徹底討議する～"InvisibleWriteRule: トランザクションの書込み最適化" を中心に
C33 MVCCにおけるw-w/w-r/r-wのあり方とcommit orderのあり方の再検討～Sundial: Harmonizing Concurrency Control and Caching in a Distributed OLTP Database Management Systemを題材に

2016-02-23

SSI論文のメモ

Making Snapshot Isolation Serializable 再考 - 急がば回れ、選ぶなら近道

で紹介されている2つの論文を読んだのでメモ。

Making Snapshot Isolation Serializable

Alan Feketeの論文。

okachimachiorzさんが詳しく書いているので引っ掛かったところだけメモ。

用語について

Predicate Read
名前（Identifier）によって特定された対象に対するReadではなくて、比較演算等の述語が真かどうかを評価、選択してReadする操作を特別にPredicate Readと呼んでいる。
こちらが普通だと思っていた。通常はIndexによって一本釣りできることが前提になるから述語の評価による選択に敢えて名前がついているのかな。
First Commiter Winルール
同じ対象をWrite使用とするとき最初にCommitしたトランザクションが有効になるルール。First Updater Winルールも出てくる。
Write Skew
Anomalyの1つ。Snapshot Isolationで除去できない。2つのrw-dependencyによって起こる。
Lost Update
Anomalyのひとつ。メジャなやつ。
Phantom Read
Anomalyのひとつ。ANSIにも出てくる。PostgreSQLの実装が頭にあるとNon-repeatable Readとの違いがわからなくて困った。

Typo/誤り

Example 2.1
H1:W1(X1) W1(Y1) W1(Z1) C1 W3(X3) R2(X1) W2(Y2) C2 R3(Y1) C3

上記のヒストリはSerializableである（T1→T2→T3の順）と書いてあるが、Serializableではない。T2⇒T3のrw-dependencyとT3⇒T2のrw-dependencyが存在し、サイクルになってしまう。
この例のままではアイテムZが出てくる意味がないので、正しくは恐らく以下のヒストリ。

H1:W1(X1) W1(Y1) W1(Z1) C1 W3(X3) R2(X1) W2(Y2) C2 R3(Z1) C3

ざっと検索したところ、以下の論文で上記とほぼ同じ例がZ1に変えて載っていたので誤りでよいと思う。

Nonserializable executionを引き起こすためには依存関係のサイクルが必要だが、サイクルに2つの連続したrw-dependencyが必要、の直感的な解釈

依存関係でサイクルを作るためには、どこかで時間を逆行するような依存関係が必要
Snapshot Isolation下では、トランザクションbegin時のバージョンをRead/Writeするので、Read/Writeが起こった時刻より前のバージョン（時刻）に対して依存関係の時刻の起点がある。Snapshot Isolationに潜在的に時間の逆行がある。
ただしWriteが有効になるのはトランザクションのcommit時なので、Writeを起点とする依存関係はWriteの後にしか起こらない（逆行しない）。
よって時間を逆行するのはReadを起点とする依存関係でそれは、Read-Write dependencyのみ。
1つのrw-dependencyを含みサイクルを作ろうとすると、もう1つの依存関係が必要だが、時刻の関係から、この依存関係に関わるトランザクションはconcurrentであることがわかる。
Concurrentなトランザクション間の依存関係はrw-dependencyにしかならないので、結果的に2つのrw-dependencyがいることになる。

Serializable Isolation for Snapshot Databases

Michael Cahillの論文

内容について

Non-serializable executionの検出をDBMSの内部でやろうとする話。
ただし依存関係のサイクルの完全な検出ではなく、連続した2つのrw-dependencyを検出する（そしていずれかのトランザクションをabortする）ことでnon-serializable executionを排除する。
そのため、偽陽性（False Positive）、サイクルになってないのにabortすることがある。
それを改善したアルゴリズムを提示されている。
2つの方法でrw-dependencyを検出している。
2つある理由は、rw-dependencyを構成するRead,Write処理が、1）ReadがWriteに先行する（ReadしたVersionをWriteする）場合と、2）ReadがWriteの後に起こる（ReadするVersionをWriteする）場合があるため。
Read先行に対しては、Rowロックに新たなロックモードSIREADを追加する方法をとる。
ロックモードであるがSIREADは他のどのロックモードとも競合しない。
SIREADとEXCLUSIVEが同じRowに対して為されたことは、rw-dependencyの存在を表す。
Write先行に対しては、Read時に、ReadしたVersionより新しいVersionが存在するかどうかをチェックすることで行う。
基本的なアルゴリズムは上記の通りだが、このままではPhantomに伴うrw-dependencyが検出できない。
InnoDBに対するプロトタイプ実装では、InnoDBに（Phantom Read対策のために？）実装済である、gapロック、next-keyロックに、同様にSIREADロックモードを追加することで行う。