野生のAnomalyを捕まえる旅（を読む）

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

TL;DR;

現実世界でトランザクションの Anomaly がどれだけ起きているかを調べる研究をいくつか紹介する．すべての論文で重大なバグが多く発見されているが，統一的なアンサーを与えることはできていない．トランザクションはアプリケーションのレベルで考えるのが当たり前になっている感すらある．今後のトランザクション研究の方向性を考えさせられる論文が多くあり，面白い．

背景

昨日の記事 (opens in a new tab) ではトランザクション処理におけるAnomalyを使った新たな研究分野が生まれてきていることをみた． この記事では，「じゃあAnomalyって実際どれくらい問題なの？」という興味を満たす論文をいくつか紹介する．これらの研究では，実運用されているアプリケーションで発生しているAnomalyをフィールドワーク的に調査することによって，どんなAnomalyが起こり，どのようなビジネス上の問題に発展し，どう対処されているかを調べている．

1. Feral Concurrency Control: An Empirical Investigation of Modern Application Integrity (SIGMOD '15)

要約: ORMのバリデーションだけで満足しているとAnomalyが起きる

この論文はRuby on Rails上で動くアプリケーションが Concurrency Control をあまり意識していないことを問題視している．より正確にいえば，「Ruby on Railsの層では Concurrency Control しているけど，データベースには何も設定していない」場合のことを Feral Concurrency Control と呼んでおり，これがもたらす問題や，どの程度発生していたかについて調査している．

たとえば，Feral CCの簡単な例は以下．

class Person < ApplicationRecord
  validates :email, uniqueness: true
end

これはActiveRecordのvalidationで，ユニーク制約をかけるものだ． このコードがアプリケーションのレベルに存在するけれど，スキーマには存在しない，という状況を著者らは "Feral CC" と呼んでいる．この場合，ユニーク制約は厳密には保証されない．

-- CREATE TABLE persons ( email text, UNIQUE KEY (email) ) -- こうではなく
CREATE TABLE persons ( email text ) -- こうなっている

ただし，Rails Guide (opens in a new tab) でも，以下のように説明されている．つまりこれは仕様上の欠陥ではなく，ユーザに与えられた選択肢である．

• Database constraints and/or stored procedures make the validation mechanisms database-dependent and can make testing and maintenance more difficult. However, if your database is used by other applications, it may be a good idea to use some constraints at the database level. Additionally, database-level validations can safely handle some things (such as uniqueness in heavily-used tables) that can be difficult to implement otherwise.
• Client-side validations can be useful, but are generally unreliable if used alone. ...
• Choose these in certain, specific cases. It's the opinion of the Rails team that model-level validations are the most appropriate in most circumstances.

この論文では，9950のこのようなFeral CCのサンプル(application-level validations)をOSSのWebアプリケーションから収集し，分析を行なっている．分析の方法として，この研究チームの持ちネタである Invariant-Confluece [2] という手法を使っている．ざっくり言うと，あるバリデーションがCoordination-freeで（すなわちアプリケーションレベルで実装されていて）も，保証したいInvariants (たとえばユニーク制約) に違反しないことを理論的に検証している．結果として，86.9%のバリデーションは検証にパスし，Coordination-freeでも（Feral CCでも）問題ないことが示された．たとえば ActiveRecordの validates_numericality_of などはどれだけ並行実行しても問題ない．一方で，validates_uniqueness_of とか，外部キー制約などは検証をパスしなかった．つまり，Feral CCではどうやってもAnomalyの危険が残り，制約を満たせない可能性がある．排除するためにはデータベースにユニーク制約をつけるしかない．

この論文では，さらに各アプリケーションのコードに踏み入って調べたところ，トランザクションで制約を記述していることはほとんどなく，ValidationsやAssociationsが広く使われていることが報告された．（Railsの書き方を考えたらそれは当然だろうという気もする）

この論文では，Feral CC をやめよう，という主張ではなく，より開発者に寄り添ったインタフェースをデータベース側が研究・提供・開発すべきである，といった主張が述べられている． 一貫性の保証は必要なときだけ行い，不要なオーバヘッドを生じさせず，アプリケーションが書きやすく，データベース側とも協調できる夢のようなORマッパーがあるといいよね，という話．

2. ACIDRain: Concurrency-Related Attacks on Database-Backed Web Applications (SIGMOD '17)

要約: APIの切り方を間違えるとAnomalyが起きる

ACIDRain [3] という研究は，Feral Concurrency Controlと同じ研究チームの論文で，また少し違ったポイントに注目している．この論文では，Webアプリケーションの開発の中で自然に起こってしまうようなAnomalyについて調べている．

普通なら (a) のケースは「トランザクションで囲め」で済む話なのだが，通信が挟まったり，APIが分かれていたり，別のストレージにリクエストする場合はそうもいかない．例えば「CRUDでAPIを切る」という基準だけでアプリを実装すると，本来アトミックに処理すべき二つのAPIでも分割してしまうことになり，トランザクション的な保護ができなくなる．データベースがSerializableであったとしてもトランザクションの使い方が正しくないのだからやっていることはRead Committedと同じになる．

この論文では，SQLのログをベースにこのような潜在的なAnomalyを検出する手法 Abstract Anomaly Detection (2AD) を提案している．2ADでは，各APIがどのカラムにアクセスしているかを調べ，同じカラムに対してアクセスするリクエストを集中実行させて並行実行パターンを生成することで，Anomalyを自動生成している．

しかし，同じカラムへの異なるAPIからの読み書きがすべて潜在的なAnomaly予備軍であるとみなされると考えると，検出されるAnomalyの量はとてつもない．開発者にとって真に重要なのはAnomalyではなくVulnerabilityなので，そこの橋渡しをする（Anomalyの重要性を説明する）こともまた必要である．この論文では，対象とするアプリケーションをe-commerceに限定することで，アプリケーションのInvariantsを3つのカテゴリ（ショッピングカート，在庫，金券）に分類して定義し，AnomalyがそのInvariantsに違反しているかどうかを調べている．¹

この論文では，調査の結果として，22件の新たなvulnerabilityが発見された．「世界中の5割のe-commerceサイトはクーポン券が無限に使いまわせる状態だった」とか「Issueで開発者に報告したらそんなこと起きるわけないだろと一蹴された」とか，目を引く面白い話が多い．

3. Ad Hoc Transactions in Web Applications: The Good, the Bad, and the Ugly. (SIGMOD '22)

要約: アプリケーションレベルでトランザクションぽいものを実装しているケースがたくさんある

少し時が経って発表されたこの論文はSIGMOD '22 のHonorable Mentionに選ばれた．この論文は，これまでの二つの論文(Feral CC, ACIDRain) とはまた異なる問題意識を持っていて，Ad-Hoc Transactionsという概念に着目している．これはデータベースの外，アプリケーションのレベルでトランザクションやConcurrency Controlを実装しているケースを指す．Feral CCとの差分は，Feral CCがORM（とくにActiveRecord）に着目していたのに対して，この論文はアプリケーションコード全体に着目している点でより補完的/包括的である． 具体的にAd-Hoc Transactionsとされているものの一例は以下．

• (a) アプリケーション側でロックを実装する (lock_map)
• (b) REDISをロックテーブルにしてDBのConcurrency Controlの補助輪にする
• (c) アプリケーション側でCompare-And-SwapやOCC相当のロジックを実装する

この論文では5年人月（！）の月日をかけて幅広いジャンルのOSSのWebアプリ（Redmine, Spree, Mastodonなど）を調査し，Ad-hoc transactionsの存在を手作業で（！）確認している． かなりの労力の結晶である．

we first search the keywords such as "lock," "concurrency," and "consistency" in the codebase, the commit histories, and the issue trackers. Then, we manually identify coordination code that isolates database operations and the purpose of those operations.

結果として，すべてのリポジトリでAd-hoc transactionsが使われていて，合計91件が確認された．ひとくちにAd-hocといっても，データベースとの調停を補助したり，並行する別のユーザからのリクエストをアプリ層で調停したり，複数のバックエンドに対する複数のリクエストの一貫性をXAの代わりに保証したり（このあたりはSagaパターンとも関連付けられている）と色々なやり方がされている．また，53件のAd-hoc transactionsにはバグがあるが，33件は開発者がすでにバグを認知していることも認められた．

それ以外にも，「アプリレベルのトランザクションではほぼ単一のロックしか使われない（デッドロック回避が鬼門だから？）」とか，「MastodonはRedisをロックに使っているがEXPIREによってアンロックしてしまうバグがほぼ全てのロックに存在する」とか，面白い話題が多く，さすが受賞論文という感じがある．

この論文もやはり「データベースは開発者にもっと歩み寄ったAPIやツールを提供すべき」という主張で締められる．たとえば SELECT FOR UPDATE はAd-hoc transactionsを実現するためのAPIとして考えられるが，こういうものの仕様がバラバラだったりするのがキツイ．例えば明示的なテーブルロックの取得などは各DBMSでシンタックスもセマンティクスも異なる．そしてそもそも SERIALIZABLE の意味も READ COMMITTED の意味もデータベースごとに異なる．このあたりがしんどいのも，アプリ側で実装したくなるインセンティブになっているのかもしれない．

終わりに（感想）

昨日から二日間かけて，Anomalyに関する論文をいくつか見た． OracleやSAP HANAといったデータベースがもとより厳密なSerializableを提供していないこともこれらの論文では指摘されている．つまり，Serializableで運用されているデータベースは少なく，世間のAnomalyは放置されているかアプリレベルの努力で回避されていることになる．困るのは放置するか努力するか，どちらの選択肢を取るべきかという指標すらないことだと思う．「あるAnomalyがどのような脆弱性を起こすのか」という問いへの一般化された回答がまだ無いため，リスク管理がしづらい（いっそ放置したくなる）．しかしアプリレベルの努力はerror-proneであるから精力的に活動しても負債が溜まっていくことになる． ましてや，近年のアプリケーションはデータベース一つで成立するものではないこともあるので，高速なデータベースを選定してSerializableで運用してもAd-Hoc Transactionsの問題が消えることはない．このあたりを包括的に考えて綺麗なアンサーを出すのが次の時代のトランザクション処理の研究なのだろうなと妄想している．

ともかく，今日紹介した論文はWebアプリケーションに携わったことがある人なら誰でも楽しく読めるものなので、おすすめです．

References

1. Peter Bailis, Alan D. Fekete, Michael J. Franklin, Ali Ghodsi, Joseph M. Hellerstein, Ion Stoica: Feral Concurrency Control: An Empirical Investigation of Modern Application Integrity. SIGMOD Conference 2015: 1327-1342
2. 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)
3. Todd Warszawski, Peter Bailis: ACIDRain: Concurrency-Related Attacks on Database-Backed Web Applications. SIGMOD Conference 2017: 5-20
4. Chuzhe Tang, Zhaoguo Wang, Xiaodong Zhang, Qianmian Yu, Binyu Zang, Haibing Guan, Haibo Chen: Ad Hoc Transactions in Web Applications: The Good, the Bad, and the Ugly. SIGMOD Conference 2022