CSR (Conflict Serializability)

背景

最近は、長期休暇を頂き、鬼怒川温泉に行っておりました。 旅館に来ると、学生の頃に旅館で合宿（仲良し研究室同士の研究会）がよくあったせいか、研究とか開発がしたくなります。

さて、前の記事でトランザクション理論を学習中と書きましたが、今回は、トランザクション理論に関するWebの記事で頻繁に見かけるCSR (Conflict Serializability)という基本概念について、覚え書きしておこうと思います。

トランザクション

トランザクションとは、DBのある値に対する一連のWriteまたはReadの操作です。 トランザクションは、ACID特性が満たされる事を期待されます。

一般的には、DDD (ドメイン駆動設計)の概念より、トランザクションは、あるドメイン内の一つの業務的な処理に相当するように設計されるのが良いでしょう。 ただ、DDDの話はまた別の機会に。

トランザクションの歴史は比較的古く、1960年初頭のSABREというメインフレームが始まりと言われています。 それ以来、いかに高速に、そして耐障害性が高くトランザクションを管理するか、常に検討されてきました。

トランザクション管理の困難な点

トランザクション管理は、以下のシチュエーションを想定したとき、一気に検討が難しくなります。

1. 1つのDBに対し、複数のトランザクションが同時に実行される場合
2. 複数のDBで、一つのトランザクションで操作されるデータが管理される場合
3. トランザクションの実行中にDBまたはトランザクションを処理するサーバーに障害が発生する場合

今回記載するCSRは、1.を検討する上で必須の概念になります。

トランザクションのスケジューリング

以下のように、Read, Writeの操作を複数含むトランザクションが、2種類以上ある場合を考えてみましょう。

Txは、Transactionの略で、一般的によく使われる略し方です。 Tx1は、xとyというデータをReadしてから、その情報を基に何らかの計算を行い、その結果をxにWriteします。 Tx2は、xとyというデータをReadしてから、その情報を基に何らかの計算を行い、その結果をyにWriteします。

もしこの二つのトランザクションが、下のように、トランザクション単位で確実に順番に行われるなら、ACID特性は容易に保てます。 一つのトランザクションの途中に別のトランザクションが割り込まないため、あるトランザクションは、別のトランザクションから隠蔽でき（Isolation性）、トランザクションの処理中に問題が発生しても他のトランザクションに影響を与えないため、Atomic性も満たせます。 また、Consistencyも、トランザクションの開始と終了毎に、他のトランザクションが存在しない状況で整合性検証が実行可能なので、容易に満たすことが出来ます。

このようにトランザクション単位で、トランザクションを順番に処理を行う事を、直列に実行する、と呼びます。

しかしながら、これでは一つのトランザクションの処理が終わるまで、別のトランザクションに関する処理が行えないため、複数コアを持つ計算機では、その利点を十分に活かすことが出来ず、効率がよくありません。

そこで、複数のトランザクションが同時に実行しましょう。 すなわち、異なるデータへのアクセスは並行して実行出来るように、ReadやWriteの操作単位で処理の順序を決めて実行していきます。 これの操作単位の処理順序を決める事をスケジューリングと呼びます。

CSR (Conflict Serializability)

Tx1とTx2では、「Tx1のR(y)、Tx2のR(y)、Tx2のW(y)」と「Tx1のR(x)、Tx1のW(x)、Tx2のR(x)」が、それぞれ競合関係(Conflict)にあります。 複数の操作が同一のデータにアクセスし、そのうち一つ以上の操作がWriteであるため、どちらが先に行われるかで、トランザクション内の処理結果が変わってしまうのです。

では、競合関係にある操作は、どの順番に行うべきでしょうか？

それは、競合関係にある操作が、直列的に処理した場合のスケジューリングと同じになるように操作の順序を決めます。 先ほど、トランザクション単位で直列して処理を行った場合、ACID特性が満たされると書きました。 競合していない操作は、どの操作を先に行おうと問題がないので、競合関係にある操作について順序の検討が必要で、そこだけ直列化と同じにすれば良いのです。

このように、競合の関係にある操作やその順番が、トランザクションを直列に逐次実行した時のスケジュールと同じであるスケジュールの事を、Conflict Serializable(以下CSR)であると言います。

スケジュールがCSRである事の確認

操作のスケジュールを考えたときに、それがCSRを満たしているかを確認する方法は、至って簡単です。

1. 二つのトランザクションの中で、競合する操作をピックアップ
2. トランザクションが直列に実行し、競合する操作が実行される順序を整理
3. スケジュールした操作の順序が2.と一致していたらCSR
4. 一致していない場合は、2.の直列化の順序を変えて3.4.を実行し、それでも一致しない場合はCSRではない

おわりに

今回は、トランザクション理論の基礎であるCSRについてまとめてみました。

ここでは、前提として、トランザクション内の操作が全て分かっている状況で、複数のトランザクションを安全かつ効率的に並行実行する事を考えてみました。 ただし実際、トランザクション内に、どんな操作がどの順番に存在するのかを認識し、スケジューリングを管理すること自体、誰が行うのでしょうか？

このあたりは、また今度まとめようと思います。