Software Transactional Memo

STM関係のことをメモっていこうと思います。

『夢のデータベース?「Cloud Spanner」の実力は?』について

こんな記事が目に入った。

www.itmedia.co.jp

大雑把に完全に間違ったことを言っているわけでもないが、読んでいくといろいろ鼻につくところがあり、どのあたりから間違っているのかと自分に問いただすのは現時点での自分の知識を棚卸しするためにも有用かも知れないと思ったので一言一句漏らさず思うところを書いていこうと思う。

中には枝葉末節な難癖もあるので全部を真に受けない感じで読んで欲しい。

 

Cloud Spannerの特徴は、これまでリレーショナルデータベースで不可能とされていた「トランザクション処理の大規模分散処理」を実現したところにあります。

単一のトランザクション処理を分散して実行しているかというと、Spannerはトランザクションごとに担当のトランザクションマネージャがそのトランザクション処理全体を取り仕切って行う仕組みになっている。なので「トランザクション処理の大規模分散処理」を実現しているかというと違う、一つのトランザクション処理そのものは集中処理なのである。複数のトランザクションを別個のトランザクションマネージャがそれぞれ並列に分散処理を行いはするが、その状況を表現するために「トランザクション処理の大規模分散処理」という言い方をするのは少し違うと思う。

なので「大規模分散環境でのマルチマスターなトランザクション処理」という言い方の方が正確な気がするが、マルチマスターと言っても今度は正確に意味が理解できる人がいないかも知れない。
なお、ここでは取り上げないがマルチマスターなトランザクション処理エンジンそのものはSpanner登場以前でも探すと結構でてくる。

 

しかし、分散データベースには乗り越えられない「CAP定理」というのがあり、そんな理想的なDBは実現できないといわれてきました。

CAP定理を使って分散システムの問題を定義しようとするとロクな事にならないから止めて欲しい。詳細は後で。

 

トランザクション処理というのは、金融システムや生産管理などのミッションクリティカルな業務で必要となる処理で、「間違いや不整合が起こらない」ことが絶対の要件です。

金融の世界でトランザクションを使わないパターンも一応あるだろという反論もあるが、それ以上に「トランザクションなら間違いが起こらない」という表現は誤解を招く。

「間違い」をそれとして定義できるのは一般にアプリケーションのレイヤーの都合であってトランザクショントランザクションのルールを逸脱しないというだけに過ぎない。なので「トランザクションを使えばアプリケーションが間違えない」というのは誤解である。もちろん誤った分離レベルを設定すればバグるというのは明らかだが、最強の分離レベル(=Serializable)でトランザクションを使ってもアプリがバグるぜというのはDB研究の世界ではいずれ解かれるべき課題の一つとして認識されている。

http://www.bailis.org/papers/acidrain-sigmod2017.pdf

この論文では、トランザクションを使っていてもアプリケーションがバグる状況に付いて調査し論じている。端的に言えばユーザからのHTTPリクエスト1回に対して内部で2回以上トランザクションを発行していたらさもありなんという話ではある。

 

ネット上のデータが爆発的に増える中、画像や動画、音声など、RDBMSでは扱いにくいデータが増えてきました。

RDBMSは会計データのような、数値や文字で桁数もある程度決まっているような「お行儀の良い」データを扱うのは得意ですが、大きさの予想がつかないようなデータは扱いにくい(扱えないわけではないが、効率が悪くなる)のです。

僕の知る限りSpannerはデータの多様性に対応するために作られたものでもないし、 バイナリデータを放り込むために作ったものでもないので、Spannerの紹介の中でデータの多様性の話をするのは論点がぼやけて良くないと思う。

 

処理能力を上げるための方法としては、前述の「大型のサーバにアップグレードする」方法(スケールアップ)と、「小型のサーバを大量に並べて分散処理する」方法(スケールアウト)がありますが、RDBMSは「スケールアウトしづらい」とされてきました。

理由は、トランザクション処理では「間違ってはいけない」という目的を達成するために、ACIDという特性を備えることが求められるからです。

RDBMSの中でも分析用の物はあり、分析いわゆるOLAPの処理は比較的スケールアウトしやすい。Redshiftの分析力はスケールするし、RedshiftはRDBMSの一種である。

また、「トランザクション処理はACID特性のためにスケールアウトしづらい」という表現もやはり的確な表現ではない。なぜならトランザクション処理の中で SELECT COUNT(*)みたいなクエリが含まれていたとして、その処理そのものはスケールアウトしやすい。スケールアウトしやすさの軸で語るのであれば的確な差分はACIDそのものではなく「データ並列性」の有無である。

トランザクションの高スループット化のために利用される並列性はスレッド並列性であり、データ並列性が無い処理をスケールアウトするのはそもそも自明ではない。ソフトウェアパイプラインのような形で並列性を引き出す事はありうる。そういえばAuroraがやっている事は100mぐらい離れて見ればログからのページ生成を遅延評価するというソフトウェアパイプラインによる高速化という見方はできるかも知れない。詳細はここを読んでいただければ。

データ並列性という観点でいえばトランザクションの世界ではデーブルを分割統治すべきか否かは現在も完全な答えが出ているとは言いがたい。分割統治すればロックなどでの衝突が減りキャッシュヒット率も上がりデータ並列な処理の性能が上がるのだが、分割されたデータを触れるスレッド数に限りが出るので性能の上限にぶち当たりやすいという欠点がある。例えば

http://www.vldb.org/pvldb/vol8/p1190-faleiro.pdf

この論文で提案されている方法は、トランザクション処理からアクセスすべきデータを洗い出してデータの範囲ごとに個別のスレッドに分配させてデータ並列性を引き出している。性能は必ずしも出ているとは言いがたいが…。

ともかく「トランザクション処理はスケールアウトしにくい」は必ずしも適切な言い方とは言えず「データ並列性が自明でない処理を並列処理するのは自明でない」という表現の方が適切だと思う。

RDBMSの進化の歴史は、ACIDを追究する歴史でもありました。

RDBMSの進化よりも前からACIDを追求する歴史というのはあって(IMSなど)、強いてRDBとしての歴史で言うならば、登場した当初は遅すぎて使い物にならないと言われた関係代数の実行を現在使われる程度まで高速化したオプティマイザやオペレータの発展の歴史の方が「RDBMS」の歴史と呼ぶに相応しいと思う。

また、個人的にはACIDという言葉はRDBMSを指すために適切とは思わない。Consistencyは本来アプリの側からしか注入出来ない概念であり、世に出ている一般的なRDBMSはその概念を守るために充分なセマンティクスを用意しているように見えない(Unique制約やForeignKey制約で世の中の問題が片付いているならWebアプリエンジニアは今ほどせっせとValidationロジックを書く必要性が無いのでは?)。更にはIsolationなんてデフォルトでReadCommitedが多いなんて時点で「ACIDです」とは言いがたい。もっというと世の中に出回ってる代表的なRDBMSは結構平気でDurabilityに違反している事も指摘されている。

https://www.usenix.org/system/files/conference/osdi14/osdi14-paper-zheng_mai.pdf

CAP定理同様、ACIDというスローガンに過ぎない言葉を使って現在のRDBMSの実装を語るのは論点がぼやけると考えている。

 

ところがこのACIDを満足させるために、分散処理に制限が出てしまうのです。そのCAP定理は、分散型のデータベースでは、C(Consistency:一貫性)、A(Availability:可用性)、P(Partition-tolerance:ネットワーク分断への耐性)の3つを同時に保証することはできない、という定理です。

ACIDを満足させるためにCAP定理が立ちはだかるという構図はレイヤーが異なる議論を混同している為、勘違いを招きやすいと思う。

そもそもCAP定理はネットワーク分断時のシステムの挙動に関して論じているが、例えばみんな大好きなPaxosは「ネットワークが分断しようがクラスタの中の多数派の合意が取れていれば進行する」という方針で動いている。その特性はつまり

「ネットワークが分断しても一貫性が常に保たれている、つまりC」であり

「多数派は通信できる限り応答して可用性を保証する、つまりA」であり

「多数派はネットワークの分断に耐えている、つまりP」である。

なのでPaxosはCAPを3つ全部実現してしまっている事になる。だが分断された側の少数派は「多数派が応答してくれないから一切の合意が取れない、Pとは言えない」「合意が取れないから返事が出来ないので可用性を保証できない、Aとは言えない」という感じで使い物にならない。そんな感じで、システムの特性を表すための条件としては議論を簡略化し過ぎており、EventualConsistent教とQuorum教の宗教戦争の中で生まれた一過性の風説に見える。システムの特性を短い表現で表せられるという点では価値があったかも知れないが詳細な議論をするほどに乖離して結局CAPとは全く別の地平で論じる羽目になるので、猫も杓子もCAPとドヤ顔で語るのは大事な議論を見えなくしてしまうなぁと考えている。

 

その中で開発されたのが「BigTable」などのデータベースで、RDBMSとは全く違ったデータ構造、仕組みを持ちます。これらは「RDBMSではない(=SQLを使わない)」ことを示すために「NoSQL」という呼称で呼ばれるようになります。NoSQLは、ACID特性(CA)を諦めることによって、CPあるいはAPを実現し、分散処理を可能にしているといえます。

BigTableはLSM-treeのようなデータ構造(Tablet) を使っているが、LSM-TreeはMySQLInnoDBのストレージを置き換えたMyRocksの中で使われているので「RDBMSと全く違ったデータ構造」という呼び方は引っ掛かりを覚える。

また、RDBMSは関係モデルを扱うデータベースである一方で関係モデルで表現されたデータにアクセスするために使う言語は必ずしもSQLとは限らない(関係モデルでデータベースを表現する一方、その中身にアクセスするためにC言語でループを書かねばならない商用データベースを僕は知っている)。なので、SQLを使わない事は必ずしもRDBMSではない事を意味しない。そして当然のようにACID特性の事をかっこでくくってCAと書かれることには納得が行かない、なぜならトランザクションは必ずしもNetwork Partitionに耐えれないわけではなく、Paxosの上で決定的にトランザクションを行うなどの方法はSpanner登場以前から提案されていたので、Spannerがそれを実現した最初のシステムのように書かれるのは違和感がある。そのような雑な解像度の議論でBigTableとACIDの特性の違いを論じるのは良くない。

 

それを調べるために、仕組みがどうなっているのか調べようとしているのですが、これがなかなか難しいのです。このような記事もあるのですが……。「SpannerはDatastoreに似ている」ということですが、DatastoreってNoSQLですし。「Paxos」というのがキーワードのようですが、これも難しそうです。こちらの記事(Googleの論文の翻訳)によると、原子時計まで使っているようです。

分からないなら無理に書かないほうが…。

手前味噌だけれど、Spannerの仕組みについては

qiita.com

www.slideshare.net

あたりを眺めて欲しい(正確にはMV2PLじゃなくてROMVだったりと細かい突っ込みどころはあるにせよ)

 

分断が起きるとSpannerはCを選択し、Aを犠牲にします。つまり技術的に見ると、SpannerはCPシステムなのです。

 と記載されていました。やはり、CAP定理を乗り越えたわけではないのですね。

 Paxosで分断された少数派側は応答を返さなくなるので、Aを犠牲にする。Availabilityがない時点で分断に耐えたと呼べないわけで、CPと呼ぶのは今ひとつ納得が行かない。

 

まあ、この可用性でも十分、という業務もあるのでしょうが、金融トランザクションにはまだまだ使えなさそうです。

 金融トランザクションの全てが99.9999%の可用性を要求してるかというと一概には言えない。もちろん要求しているところもあるけれどお金を扱うトランザクションクラウド上のMySQLPostgreSQLでやってるベンチャー企業はいくつも実在する。

 

結構長文になってしまったが、違和感を棚卸しすると自分の理解度を再確認することができて良かった。他の人も同様の事を書いてワイワイと答え合わせができればなお好ましいと思っている。