Transaction Anomalyの概念はデータベースの外で生き続ける（のかな？）

この記事は データベース・システム系 Advent Calendar 2023 (opens in a new tab) の16日目の記事です．

この記事はポエムです．また，Redbookの6章 (opens in a new tab) や Peter Bailis のブログ (opens in a new tab) がほぼ同じ話をしているので，この記事を読むよりこちらを読まれたほうがより深い理解が得られます．

TL;DR;

• Serializableという概念は便利．しかし，使われていない
• Serializableでなくとも要件が満たされるシステムが世の中には多い　
  • ワークロードによってはそもそも Weak Consistency でも Serializable と等価
• それでも，Weak Consistency と Serializable の差分の定式化（すなわち，Anomalyの定義）という概念自体は使いでがある
• 明日に続く

Anomalyとは． トランザクション処理を用いるミドルウェアではAnomaly¹ またはIsolation Bugsと呼ばれる現象が発生する．これは並行性に起因するバグで，以下のようなシナリオが現実に起こる．

• 「高負荷がかかったときだけデータベースの中身が壊れて，重複するIDが生まれた」
• 「夜間に流していたバッチと通常のクエリが衝突して，計算が狂った」

こういった並行性バグは基本的に予測不可能（ハイゼンバグ）とされることが多いが，データベースの中という閉じた世界ではトランザクションの理論によってAnomalyというラベル付けがされ，定式化がなされている． Anomalyはバグの中でも扱いやすい形態をしている．なぜ起きたのかグラフを描いて説明できるし，どうすれば防げるかも明らかにされていて，そのためのワークアラウンドも充実している (SELECT を SELECT FOR UPDATE に変えましょう，とか)．CIDR '23 の論文 [1] ではAnomalyというツールを使えばハイゼンバグを再現性の高いボーアバグに変換できて便利だ，というふうに説明されていて，なかなかわかりやすい．

Serializableと現実． Anomalyという概念は非常に強力なツールなのだが，バグの説明性と再現性が高まっているだけで，アプリケーションにバグが出てしまうことには変わりがない．そのため，トランザクション処理の文脈（特に研究レベル）では，「最も強い分離レベルである Serializable を提供するアルゴリズムなら，Anomalyは発生しない保証ができます．これを使いましょう」というのが通説だった． ところが，Serializableを躊躇なく使えるユーザはそれほど多くないのが現実である．

• SIGMOD'16 のKeynote [2] では，DBAに対してサーベイを行ったところ，「必ずSerializableで運用する」という回答はゼロだった．
  • 最も使われている Isolation Level は READ COMMITTED だった．これはかなり多様なAnomalyの発生を許容する．
• 機械学習に用いるパラメータサーバでは，一貫性を保証しない(Anomalyが発生する)ソフトウェアが多いことが指摘された [3]．

Anomalyは実際に起きるのか. Serializableが選ばれない理由はシンプルで，性能が低くなることと，多くの製品でデフォルトの設定ではないことの2点が大きい．さらには，そもそもAnomalyというのはたいして発生しないのではという説がある．この点はアプリケーションによるので一貫した答えはない・・・と思いきや，いくつか研究レベルでも話が出ている． [3] では，定理立てて以下のような話が証明されている．

we show that the weakest consistency level in transaction processing, such as NoCon, is equivalent to snapshot isolation (SI) if the BN3 is always true.

BN3とは Bad things doN't come into 3 という意味で，ざっくり言うと 「intersect/conflictしたトランザクションが二つ（エッジが一つ）以下なら，一切Concurrency ControlしなくてもSnapshot Isolationまでは保証される」ことを意味している²． そして，グラフ処理のワークロードでは，実際にクエリを流してみても99%以上の確率でBN3になることを確認している．この場合，どんな一貫性レベルでデータベースを運用してもANSIが定義したAnomalyはすべて防げることになる．

分散処理． 分散処理ともなるとオーバヘッドの問題はより深刻になり，一貫性を放棄するインセンティブがさらに高まる．Facebook が SOSP' 15 で発表した論文 [4] では，Facebookのソーシャルグラフを扱うシステムTAOにおいて Strong consistency がどれだけ違反されているかを調べている³． TAOは Eventual Consistency で動作しており（おそらく当時の中身はMySQLのレプリケーションクラスタだと思う），レプリケーション遅延があるのだが，この遅延を観測してしまうユーザがどれだけいたのかを実験によって調べている．結果として，0.0004% の読み取りのみがStrong consistencyに違反していることが明らかになった．この0.0004%の一貫性違反を防止するために，どれだけのコストを支払えるだろうか？

また，分散処理で実際にStrong Consistency + Serializableを実現しようとするとどれだけオーバヘッドが高くつくのか，というのは VLDB' 14 の Coordination Avoidance in Database Systems [5] という論文がマイクロベンチマークを行なっている．

対数軸なので桁違い，4桁くらいの性能劣化が起きてしまう．これほどの性能劣化を常に許容できるほどミッションクリティカルなアプリケーションは割合としては少ない．

予防かデバッグか． したがって，もはやSerializableでデータベースを運用するのは一般的なアプリケーションにとってのコスト最適からは遠くなっている．しかし，CIDR '23の発表 [6] では，93件のConcurrency系のIssueについて調査したところ，開発者はみな「事前に予防できるなら予防したい」と考えていることが示された．それは当たり前の話なのだが，そうできないのが現実になっている．

ツールになっていくAnomaly． では，Serializableでしかもゼロオーバヘッドという夢のようなデータベースが出てくるまで，トランザクション理論とConcurrency Controlは象牙の塔の産物になるのだろうか？ それがそうでもない．Anomalyという概念の有用性はまだ残っている．冒頭に述べたように，Anomalyはデータベースに関係するハイゼンバグをボーアバグに変えてくれる．これを活かした，「デバッグのためのAnomaly」という新たな研究領域が誕生している．具体的には，以下のような研究が花開いている/開きつつある．以下は論文のリファレンス紹介と夢の話：

• データベースの外側でAnomalyを検出する．．ログやクエリを入力として静的/動的に解析して，起こりうるAnomalyを特定し，開発者にデバッグのヒントを与える．Anomalyが実際に発生する前に検出・デバッグできれば価値が高い．
  • [1,7,8,10]
• Anomalyの説明． Anomalyを入力としてどのような脆弱性につながるのかを出力する．Anomalyはそれだけでは「トランザクションの世界ではこれは違反です」と言っているに過ぎず，アプリケーションから見て問題なのかはまた別の議論である（例えば，いいねボタンのインクリメントが並行実行されて数が過小に見える瞬間があったとしても，仕様としてユーザと合意することはできそうなもの）．Anomalyがどんな脆弱性につながるのかという説明を生成するツールの研究が求められている．
  • [9,11]
• Anomalyの不在保証． BN3で見たように，弱い一貫性の（あるいは一切なにも保証しない）システムを使っても，ワークロードによってはSerializableと等価な結果が得られることがある．ワークロードを入力として静的解析をすることで，何もしなくともSerializableが保証される一貫性レベルかどうかを判定する研究分野があり，ワークロードの 'Robustness' と呼ばれている．この分野の成果が普及し，高速かつ対話的に（たとえばエディタ上で）実行できるようになれば，クエリを書きながらそのクエリでAnomalyが発生するかどうかを判断することもできるかもしれない．ひいては，開発フェーズでAnomalyのない (<=> Robustな) アプリケーションが書けるようになるかもしれない．
  • [12,13,14,15]
• Anomalyの逆引き． これは既存研究を知らない，私の妄想なのだが，データベースが原因かどうかすらわからないバグレポートを入力として，「これはこういうAnomalyの産物です」という出力を返してくれるツールがあれば非常に有用だと思う．このツールの偽陰性をゼロにできれば，「これはデータベースには関係ないバグです」と切り分けをするツールにもなる．誰か既存研究やプロジェクトを知っていたら教えてください．

以上のように，論文だけを見ても多くの研究分野が誕生している．どれも，Anomalyという，Serializableの定義から生まれた概念をSerializableではない環境で使い倒しているのが面白い．

終わりに． Anomaly が便利な概念であること，しかし現実はSerializableで運用されAnomalyを予防しているシステムは少ないこと，そしてAnomalyはデバッグや開発のためのツールに変質していっていることをみた．

明日は，実際に実世界のアプリケーションでどんなAnomalyが起き，どのようにデバッグされているかを調べる．ちゃんと書けたらいいですね．

1. Qian Li, Peter Kraft, Michael J. Cafarella, Çagatay Demiralp, Goetz Graefe, Christos Kozyrakis, Michael Stonebraker, Lalith Suresh, Matei Zaharia: Transactions Make Debugging Easy. CIDR 2023
2. What Are We Doing With Our Lives?: Nobody Cares About Our Concurrency Control Research (SIGMOD'17, Keynote) (opens in a new tab)
3. My Weak Consistency is Strong: When Bad Things Do Not Come in Threes. Zechao Shang, Jeffrey Xu Yu. CIDR 2017
4. Haonan Lu, Kaushik Veeraraghavan, Philippe Ajoux, Jim Hunt, Yee Jiun Song, Wendy Tobagus, Sanjeev Kumar, and Wyatt Lloyd. 2015. Existential consistency: measuring and understanding consistency at Facebook. In Proceedings of the 25th Symposium on Operating Systems Principles (SOSP '15). Association for Computing Machinery, New York, NY, USA, 295–310. https://doi.org/10.1145/2815400.2815426 (opens in a new tab)
5. Peter Bailis, Alan Fekete, Michael J. Franklin, Ali Ghodsi, Joseph M. Hellerstein, and Ion Stoica. 2014. Coordination avoidance in database systems. Proc. VLDB Endow. 8, 3 (November 2014), 185–196. https://doi.org/10.14778/2735508.2735509 (opens in a new tab)
6. Chaoyi Cheng, Mingzhe Han, Nuo Xu, Spyros Blanas, Michael D. Bond, Yang Wang: Developer's Responsibility or Database's Responsibility? Rethinking Concurrency Control in Databases. CIDR 2023
7. Peter Alvaro, Kyle Kingsbury: Elle: Inferring Isolation Anomalies from Experimental Observations. Proc. VLDB Endow. 14(3): 268-280 (2020)
8. Yifan Gan, Xueyuan Ren, Drew Ripberger, Spyros Blanas, Yang Wang: IsoDiff: Debugging Anomalies Caused by Weak Isolation. Proc. VLDB Endow. 13(11): 2773-2786 (2020)
9. Drew Ripberger, Yifan Gan, Xueyuan Ren, Spyros Blanas, Yang Wang: IsoBugView: Interactively Debugging Isolation Bugs in Database Applications. Proc. VLDB Endow. 15(12): 3726-3729 (2022)
10. Wensheng Dou, Ziyu Cui, Qianwang Dai, Jiansen Song, Dong Wang, Yu Gao, Wei Wang, Jun Wei, Lei Chen, Hanmo Wang, Hua Zhong, Tao Huang: Detecting Isolation Bugs via Transaction Oracle Construction. ICSE 2023: 1123-1135
11. Todd Warszawski, Peter Bailis: ACIDRain: Concurrency-Related Attacks on Database-Backed Web Applications. SIGMOD Conference 2017: 5-20
12. Brecht Vandevoort, Bas Ketsman, Christoph Koch, Frank Neven: Detecting Robustness against MVRC for Transaction Programs with Predicate Reads. EDBT 2023: 565-577
13. Brecht Vandevoort, Bas Ketsman, Christoph Koch, Frank Neven: Robustness Against Read Committed: A Free Transactional Lunch. PODS 2022: 1-14
14. Brecht Vandevoort, Bas Ketsman, Christoph Koch, Frank Neven: Robustness against Read Committed for Transaction Templates. Proc. VLDB Endow. 14(11): 2141-2153 (2021)
15. Bas Ketsman, Christoph Koch, Frank Neven, Brecht Vandevoort: Deciding Robustness for Lower SQL Isolation Levels. PODS 2020: 315-330
16. Peter Kraft, Qian Li, Xinjing Zhou, Peter Bailis, Michael Stonebraker, Xiangyao Yu, Matei Zaharia: Epoxy: ACID Transactions Across Diverse Data Stores. Proc. VLDB Endow. 16(11): 2742-2754 (2023)