データベースの世界には The RedBook という本がある.

_

データベースの研究界において非常に重要な功績を果たした論文を紹介しながら,
M.Stonebraker氏やHellerstein氏といった業界の重鎮が,今後のデータベース界の動向と,必要とされる研究や開発の方向性を議論している本である.

このRedBookに入っている論文と,これまでの研究の流れの解説は特に素晴らしい.多少読むハードルは高いが,私のような初学者や入門者にこそオススメできる内容である.
実態としては本ではなく論文集にコメントが付記されているものに近い.論文はさすがにダウンロード出来ないが,付記されているほうのStonebraker御大らのコメントはWebでも読める.なかなか面白い.
私は4th Editionの冊子を持っているのと,5th EditionのWeb版のコメントを読んだ.

Stonebraker御大はもともと奔放な発言で有名な方(だそうだ)が,はじめから飛ばしているーはじめから,というより,4th Editionの頃も同じことを書いていたらしいが.

一例を挙げると,第1章 Background では,以下のように述べている.

My amazement about the data model paper is that nobody ever seems to learn anything from history.

10年前はデータベース業界ではXMLデータベースが盛り上がっていたのに,今ではそんな概念は消滅している.
その過去があるにも関わらず,今はJSONなどのフォーマットでデータモデリングをすることに誰もが躍起になっている.
そこにどんな違いがあるというのか?同じ過ちを繰り返しているだけではないのだろうか?

おそらくXMLもJSONも,超スパースでカーディナリティの高いデータに対しては有効な選択肢だが,
階層化されたデータ構造を表現するには問題がありすぎる.全てのデータモデリングを包摂できる銀の弾丸では無い,とStonebraker御大は語っている.

No doubt the next version of the Red Book will trash some new hierarchical format invented by people who stand on the toes of their predecessors, not on their shoulders.

巨人の肩の上ではなく,つま先の上にしか立たない人間たちがデータベース業界にいる ,という刺激的な批判が第一章から飛んでくる.面白い本だ.

だが,RDBのように正規化したデータモデリングを行わず,JSONのようなデータフォーマットでデータモデリングをしたい,という議論がたびたびされるというのは,むしろ 極めて重要な議論 であり,
界隈の愚かさの象徴ではなく,むしろ次なるデータベース研究開発のための大きなヒントであると私は思う.

勿論,柔軟にデータを表現したい,であるとか,開発効率を上げたい,ということもあるだろうが,それは本質では無いと私は思う.
JSONやXMLといったデータモデリングの再発明が繰り返されるその理由は, 性能の最適化と一貫性のため,すなわちトランザクションを自分でデザインできる ことにあると思う.
最近,論文紹介ブログをやっていて,そのあたりについて思うところがでてきた.

今日はこれについてポエムを書く.なお私は初心者なのでここに書かれていることは全てポエムの域を出ない.(保身)

同時実行制御のオーバーヘッド

太古の昔,1970年代から1980年代にかけての,同時実行制御(Concurrency Control) 研究の目的は,データベースの一貫性を守ることであった.
前に取り上げたBuilding on Quicksandで言われているように,CPUコア数やシステムの台数,OSのスケジューラの挙動などの外的要因がどのように変化しようとも,透過的に一貫性のあるデータ管理をすることが目標であった.

これをナイーブに行おうとすると,データベース全体にロックをかけて,同じ瞬間にはひとつの計算処理しか行えない(直列実行),という風に実装するのが手っ取り早い.手っ取り早いのだが,もちろんそれでは性能が出てこない.OSにスレッドを寝かされたら起きるまで待つとか,マルチコアならCPU一つしか動いていないとか,分散システムなら結局一台以外寝ている,とかいう話になる.

たとえば,昔,学校の集会があると,全校生徒が体育館に移動して,そこでクラス順,出席番号順に並び直すのに時間を取られていたことを思い出す.
教室の中では出席番号順に机が並んでいたから,体育館でも同じように並べばいいのだが,廊下という共有バスを通って移動している間にこんがらがってしまう.他の教室から出てくる人も間に挟まってくるので,体育館に着く頃には順番がまたバラバラになっている.結果として,並び直しという異常系の処理が走ることになる.

もし,生徒が一人しか居ない学校なら,どう移動しても確実にクラス順,出席番号順に並ぶという目的は自動的に達成される.が,人数が増えてくるとそうはいかない.
では,必ず,席を立って移動できる人間は全校で一人だけ,という制約をつけて,クラス順,出席番号順に移動させたらどうか?こうすれば,体育館ではきちんと整列された,並びに間違いのない集会が開かれることだろう.これはデータベース全体にロックをかけているのと同等である.もちろん途方もない時間がかかるだろうことが予想される.

これを出発点として,どうロックを細分化し,どうロックを扱っていくかということを突き詰めてきたのが同時実行制御の研究だった.

論文紹介ブログでも取り上げたOn Optimistic Methods for Concurrency Control では,過去の研究に対して,自身の立ち位置を

Research directed at finding deadlock-free locking protocols may be seen as an
attempt to lower the expense of concurrency control by eliminating transaction
backup as a control mechanism.
In this paper we consider the converse problem, that of eliminating locking.

と述べている.共有データにロックをかけることはそれ自体,オーバヘッドが存在する.ロックの扱い方を考えて,デッドロックを無くすことはアボート率を下げる上で有効であり,それは性能最適化に繋がる.が, ロックという概念自体が,全ノードに厳格に同時に通知されなければならない共有オブジェクトの存在を意味 していて,これはマルチコア/分散システムの時代にはどんどん苦しくなってくる,ということを1981年の時点で示唆している.

先ほどの例で言えば,各教室に「今は1クラスのAさんが移動している」という情報を常に共有しなければならないことになる.この情報は古くて(stale)はいけないし,間違っていてはいけない.必ず全教室に通知・更新していかなければならない.もし校舎が地理的に離れたロケーションにあっても,それをなんとか連絡しあって運行しないといけない.
この連絡コストをかけるよりも,楽観的に全校生徒全員を一斉に移動させて,うまく整列できないところの整合性を取っていく,という処理を行うほうが,エンジニアリングとして最適化しやすいのは自然な話だ.

不変条件

で,さらに最適化の議論を先に進めると,同時実行制御をどこまで厳格にやる必要があるのか というところが重要になってくる.
実は,全校集会というのは,生徒が全員同じところにそろっていて,なんとなく整列できていて,全員が同じ方向を向いていれば,それで問題が無かったりするものである.但し,抜けだされると面倒なので,相互監視の意味も兼ねて,出席番号順などの順序で並んでいて欲しいとかいう話が色々あるとする.

こういう条件は,整理すると以下の 不変条件 に整理できる.

1
2
3
1. 生徒全員が同じ場所に移動する
2. 全員が前を向く
3. 整列する(壇上から見て綺麗に見える)

この不変条件を満たす限りにおいては,何が起こっても良い,という考え方がある.特に代表的なのがPeter Bailis氏によるCoordination Avoidanceの思想である.氏はこの博士論文で2017年のSIGMODでJim Gray Awardを受賞しており,先に挙げたRedbook 5th Editionの編者陣にも加わっている気鋭の研究者である.

要するに,過去から現在に至るまで,データベースがノード数やコア数を増やしても透過的にデータに触れて,それによる副作用は一切ないことを保証するために,ロックをどう取って,どう生徒を整列させたら正しいのか,という 正しさ(correctness) を議論する必要があった.
このために生み出されたものが直列化可能性(Serializability)であった.これは,先に述べたような,「同時に実行できるのは一つの処理だけ,とした場合と同じ結果になるか」を検証するものだった.
すなわち,生徒を一人ずつ順番に移動させた時と,同じ順番になるように体育館に移動させる,ということだ.(微妙に違うか)

しかし実際のところ,データベースはそうでも,アプリケーション的には, 直列実行した際と同じ結果にならなくても別にいい こともある.
先の不変条件1~3を見てみると,実は全校集会を開くには,移動の経路や過程がどうでもいいことはもちろん,出席番号順とかクラス順とかいう話もどうでもよくて,このイベントを開催するアプリケーションはもっと柔軟に組み立てられそうであることが分かる.

もっとこの全校集会を考えてみると,実は以下の不変条件でよかったわ.とアプリケーションエンジニアはある日気付く.

1
2
1. 全校生徒が同じ話を聞く
2. 校長が全校生徒に同じ話を聞かせたというユーザエクスペリエンスを得る

こうなると実は,各生徒がAckさえ返せば,教室にいても全校集会は開催出来るのかもしれない.廊下という狭い帯域を逼迫させる必要はない.いや,自宅でもできるのかもしれない.もっと言うと時間も合わせなくてよかったのかもしれない.となるとN高校はなぜわざわざ全員集まる必要があったのだろうか.

https://nnn.ed.jp/news/index.html%3Fp=950.html

(閑話休題)

現代のアプリケーションの難しさ

このようにどんどんアプリケーションの不変条件は変化していく.一方でデータベースの側からはそれは見えない.
データベースはやはり,N人の生徒データを体育館に移動させるというアプリケーションがあったら,そこで厳格に直列化可能性のもとで動かざるを得ない.ただでさえこのように不変条件が変わっていく中で,データベースに与えられた述語は限られている.
以下はMySQLにおける制約の一覧だ.

1
2
3
4
1.8.3.1 PRIMARY KEY および UNIQUE インデックス制約
1.8.3.2 FOREIGN KEY の制約
1.8.3.3 無効データの制約
1.8.3.4 ENUM および SET の制約

これは滅茶苦茶厳しい.これの組み合わせとSQLで先ほどのアプリケーションの不変条件を表現することになるとなかなか難しい.
結果としてよくあるインピーダンスミスマッチが生まれて,バグが生まれる.

であればもう,データベースに「こうであるべき」という条件を教えるより,データベースがこうなってしまったら頑張ってリカバリする,というコードをアプリに異常系として実装したほうが 頑張るべきレイヤが一つになってわかりやすい.
結局,全校集会の例も,美しい移動手段を考えるより,移動した後に全員を整列させたほうが話が早かったし,直感的であった.
もしこれを,うまく教室を出る順番を考えれば全員が綺麗に整列できて,スピーディで,かつ廊下も混み合いません,というやり方があるのであれば,そうしたほうがいいのはわかるが,そんな方法はなかなか思いつかない.

Peter Bailis氏もこの傾向が特にWebの世界には顕著にあると述べていることを前にも紹介した

https://speakerdeck.com/futuredata/2017-jim-gray-award-talk-coordination-avoidance-in-distributed-databases

アプリケーションエンジニアは明確に何がアプリケーションの本質なのか,ユーザからの入出力は何かを語ることができる が,データベースは汎用的なソフトウェアなので,アプリケーションとのインタフェースが突き詰めると ReadWrite 命令,あるいはそれを複数束ねたトランザクションという単位しかない.
これでは踏み込んだ最適化はできないし,めまぐるしく変わるアプリケーションの不変条件に対応していくことも出来ない.いずれアプリの更新についていけないデータベースが性能のボトルネックになってくる.実はアプリのほうはもう完全リモートでVR全校集会を開いているのに,データベースは未だに全生徒の出席番号をわざわざ並べ替えて矛盾があるかチェックしている,ということが容易に起こりうる.

で,そうなると冒頭に挙げたJSONなんかのデータモデリングは実は悪くない選択肢となる.
どうせ厳密にRDBMSを運用すると,同時実行制御が存在する以上必ずスケールアップ/スケールアウトにかかるオーバヘッドがある.そのうえ同時実行制御は確かにデータの一貫性を保つが,実は瞬間的に壊れてもいい不変条件などの要件に対応することが難しい.じゃあ,アプリ側でうまくそれを作りこんで,データが壊れたら補償で対応すればいいじゃんというのが現代の設計になっている
となると結局,正しさ(Correctness)に関してはアプリエンジニアがデータベースの責務まで実装することになる わけだから,別に厳密に正規化したリレーショナルモデリングを扱う必要はなくて,JSONでも何でも別に構わないという話になる.バックエンドがREST APIのような設計をしている場合,ユーザとシステムとの間をやりとりするデータのフォーマットもやはりJSONであることが多いわけだし...

ここではアプリケーションエンジニアは,データベーストランザクションを手放した代償として,Memories, Guesses, and Apologies を合言葉にシステムを実装する必要がある.

  • Memories: データが必ず記憶されること.データベースにおけるDurability
  • Guesses: 記憶されたデータは間違っているかもしれないこと.
  • Apologies: データが間違っていたらユーザにどうごめんなさいするか考えること.補償.

これを,常に意識して開発を行い,システムの台数が増減したり構成が変化するたびに潜在的だったバグとご対面する,というのが今Webのエンジニアが置かれている状況である.厳格なトランザクションのあるRDBMSの世界に比べると,とても難しい世界だ.

データベースが提供すべきインタフェースとは

しかし,ムーアの法則は限界を迎えたと言われて久しい.分散システム化/マルチコア化の流れは避けられない.古典的なトランザクションを支える同時実行制御は原理的にオーバーヘッドがある.じゃあどうするか.というところで,Peter Bailisが提案しているのは, 不変条件の記述をデータモデリングのベースにしたデータベースとトランザクション である.そこでは,必ず満たすべき不変条件の記述 だけでアプリケーションとデータベースを接続する,という,リレーショナルモデリングやJSON/XMLより一歩先行く世界の夢が描かれている(なお実装はない).
具体的にはDBとアプリとの繋ぎこみを担当するO/Rマッパーをベースにして新しく研究をしていけばいいんじゃないかと論文では語っている.

確かに,上に挙げたような不変条件をベースにアプリケーションとデータベースを組み立てられたら凄く楽だ.

1
2
3
* 日本で行ったツイートがブラジルのフォロワーのタイムラインに表示されるのは別に後でもいい
* Web銀行の残高照会は必ず最新の値を返す
* ショッピングカートの在庫数は古くてもいい.過剰注文したらごめんなさいするから

このような不変条件はアプリケーションエンジニアからするとSQLやUNIQUE制約やトランザクションよりずっと簡単に表現できる.
また,このようなセマンティクスから染み出てくる最適化プランは,今までのデータベースのモデリングよりずっと具体的になる.既存のシステムより大幅な性能向上が見込めるはずである.

実際に,Peter Bailisの論文では,TPC-Cのクエリに対して不変条件の分析を行い,並列実行可能なクエリを可能な限り並列化し,ロックを取り払った実装を行っている.その結果は素晴らしい性能だ.

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.

私はこの夢のような世界観が好きだ.もともとデータベースというのは DataBase Management System であり,共有データをどう管理するかということが主目的のソフトウェアだ.そこで一貫性や分離性,永続性といった議論が生まれた.突き詰めればユニケージ開発手法なんかでやられているように,テキストファイルをデータベースとみなしても何ら問題は無い.データベースの果たすべき制約はアプリケーションとは結局のところ切っても切り離せないものだ.そこを汎用的なソフトウェアとするために生まれたのがACID制約であり,これはデータベースの責務を一般化するための手段だったと思う.

終わりに

お盆なのでつい無駄に筆を進めてしまったが,ここまでの話は実は全てPeter Bailis氏のスライドを読めばすぐにわかる話である.実際こちらのほうがわかりやすい.

データベースがどのようなデータモデリングを提供し,どのようなインタフェースを提供するかというのは,性能最適化ももちろんだが,突き詰めるとユーザにどこまでの抽象化を見せるかという点で,アプリケーションとレジスタの間の界面のデザインである.そういう意味で,私はこのような話が面白いと思う.スケールの大きいインタフェースの研究だと感じている.

The Redbookの6th Editionでは,Stonebraker御大が新しいデータモデリング手法に舌を巻いて,リレーショナルモデリングを過去の産物と切って捨てる姿が見たいものである.