Spannerの登場で急拡大したNewSQL
分散トランザクションの課題をどう解決したか

自己紹介とセッションのアジェンダ

小林隆浩氏（以下、小林）：では、さっそく本セッションに入っていきますが、まずは私のほうでイントロダクションをこのままやります。

イントロダクションのテーマは、「NewSQLへの誘い」というかたちで進めていきます。私は小林と言い、データベースに関する連載や、書籍の翻訳なんかをしているエンジニアです。

いろいろなデータベースをつまみ食いするのが好きで、評価したり検証したり。あとはその内容をいろいろなところで発表するようなことをやっています。

本日のイントロダクションのアジェンダは4つほどあります。まず、「そもそもNewSQLって何だっけ？」という話を簡単にしたいと思っています。これは個人の理解がいろいろあると思いますが、今までいろいろなベンダーさんとお話ししたりした、私なりのノウハウを共有したいと思っています。

2番目はストレージエンジンの観点ということで、NewSQLのデータを保存する部分について頭出しします。3番です。NewSQLというのはスケールアウト型で、ノードがたくさんあるようなデータベースクラスターになるので、その中で分散トランザクションをどういうふうにやっているか。今日のメイントピックです。そこについて簡単な頭出しをしたいと思っています。

NewSQL登場に至るまでの流れ

「そもそもNewSQLって何ですか？」というお話から入っていきます。このスライドでは2000年のはじめの頃から始めていますが、大きな流れとして、2000年のはじめの頃はデータベースは基本的にはお金を出して買うもので、ソースもクローズドでした。

Oracle DatabaseやSQL Server、DB2などのライセンスを購入して、ノードにインストールして使うものでした。その当時は、基本的には単一ノードのみで稼働していて、スケールアウトはできない。スケールアップのみの構成がメインでした。

そのあと2000年後半にかけて、NoSQLと言われるものが、データベースの拡張性や可用性を補うものとして出てくるわけです。けれども、これはリレーショナルなモデルではありませんし、ACIDトランザクションなど、RDBではサポートされていた多くのものも保証されなかったような時代になっています。

そういった背景を受けて、2011年に海外のレポートでNewSQLという用語が登場しました。NoSQLのような水平の拡張性と柔軟性を持ちながら、SQLも使えて、ACIDトランザクションがサポートできるような製品として登場してきます。

そこからさらに時代は流れ、2012年にGoogleがSpannerの論文を出しました。ここからNewSQLというような流れが一気に加速したのかなと、個人的には思っています。

スライドにあるとおり、Spannerの特徴はSQL文が使えて、我々がリレーショナルデータベースで想像するようなトランザクションが使えて、さらに、地理的にデータを分散できる大規模な分散SQLデータベースになっています。そのような構成を使い、従来のリレーショナルデータベースでは弱いとされていたWrite、書き込みのスケールアウトが可能になっています。

このSpannerの登場を受けて、NewSQLのマーケットは大きく転換、拡大をしてきているというのが個人的な概観になります。

先ほどのレポートが出た2011年頃は、例えばVoltDBだったり、NuoDBと言われるような、インメモリーを中心としたシェアード・ナッシングのデータベースクラスターがメインになっていました。しかし、Google Cloud Spannerが出てきて、それに類似したOSSがいろいろ出てきています。

その特徴は、強い整合性を持ち、トランザクションをサポートして、さらに先ほどSpannerで挙げていた地球規模。非常に大規模に展開が可能な、分散SQLデータベースというかたちになっています。

ストレージエンジンと分散トランザクション

では、ここからはストレージエンジンと分散トランザクションという観点で、簡単に見ていきます。まず、一般的なRDBMSのコンポーネントとして、ストレージエンジンがどこに位置するかという図がスライドにあります。パーサーというところでSQL文をデータベースは受け取って、それをオプティマイザで実行計画を作り、エグゼキューターで実行するかたちになるわけですが、その下で、実際に物理的なデータを取り出したりする部分をまとめて、ストレージエンジンという言い方をします。

ストレージエンジンも、時代とともに徐々に変わっていきます。これは今も使われているものですが、かつてはB+ Tree、RDBで長年使われてきたストレージ構造がメインでした。上書き型のデータ構造になっていて、読み込みがメインの場合はいいですが、書き込みであったり、たくさん書き込んだあとのSpaceの効率が悪かったりといった弱点がありました。

それに対して、その後にLSM-Treeというストレージエンジンが生まれてきて、現在ではNewSQLでもこちらが主流として使われるようになってきています。

ストレージエンジンの特性は何か

では、「その特性は何か？」をもうちょっと細かく見ていきます。ストレージエンジンを比較する際には、スライドの下の表にあるような、ReadとWrite、あとSpaceの効率などを見ていく必要があります。

1つのストレージエンジンですべてカバーするのが理想的なわけですが、それは技術的にかなり難しいので、どこかを伸ばしてどこかを妥協するような構成になってきます。

先ほど話したように、B+ TreeだとReadの効率は非常にいいですがWriteは悪いし、1ページ、1ブロックみたいなものを完全に埋められないので、Space効率も悪いと言われています。

それに対して、LSM-TreeはWriteの効率がよかったり、Spaceの効率がよかったりという特性を持っています。逆にReadは悪いということですね。TiDBであったり、CockroachDBについては、LSM-Treeを実装したRocksDBを利用しています。

今回の話には出てきませんが、YugaByteDBは、RocksDBをモデファイした独自開発のストレージエンジンを使っているし、CockroachDBについても、今独自のストレージエンジンを開発しています。NewSQLについては、このあたりの開発が非常に活発になっている分野になります。

では、このB+ TreeからLSM-Treeへの変化がどういうところから来たのかを考えると、実際はNoSQLです。「Cassandra」のデータ構造がまさにLSM-Treeです。これが今の流れに合っていて、Writeにも強いし、SSDとの相性もよいということで、NewSQLでも大規模に採用が進んでいます。

このあたりの話は、Cloud Native Database Meetupの別回でできればと思います。

分散データベースの課題

次が分散トランザクションの観点です。従来のRDBのように単一ノードで動いていたデータベースを複数ノードに分けた場合、そこから分散トランザクションとの戦いがもう始まってきます。

シングルノードの場合には、到着したリクエストを到着順にさばくことが簡単にできますが、スライドの下にあるようなマルチノードだと、到着順がそもそもよくわからない。ノード①に到着したものと、ノード②に到着したもの。どちらが早いのかよくわからないし、2台のノードの時刻同期も完全には一致しない問題があります。

こうした場合に、トランザクションの順序を正しく並び替えるためには、ほかのノードをブロックしたりすればいいわけです。しかし、それではスケールアウトしないことになるので、このあたりのさじ加減が難しい問題になってきます。

こちらは参考ですが、先ほどのトランザクションのケースでも、例えば書き込みを単一のノードで行う、読み込みは複数のノードで行うように決めてしまえば、実際は楽です。

そのような構成になっているのが、Amazon Auroraであったり、ポスグレのReplicationだったりします。プライマリーと言われる1台のサーバーで書き込みを行って、レプリカはデータの読み込みを行うような、責務が分かれている構成になります。

ただこれも当然プライマリーがボトルネックになってくるので、これまで問題になっていた、Writeのスケールアウトというような問題は解決できない構成になっています。

NewSQLの解決法

ではNewSQLでそのあたりをどう解決しているかです。まずスライドにある、Raftと単一パーティションのお話があります。NewSQLでは、特定のテーブルを複数のパーティション、シャードという言い方もしますが、それに分割をして、そのレプリカを複数のノードで持ち合うことで可用性を高めます。

単一のパーティションに対して、スライドの下の図のようにWriteがあるケースでは、Raftによってほかのノードにデータが複製される構成になります。実はこれ、そんなに難しくはありません。

Raft自体が非常に難しいと敬遠されがちですが、Writeはこの上のLeader1に行って、右側と下のノードにいるFollower1にそれぞれデータを複製する。Raftは多数決による合意プロトコルなので、Leader、Follower、Followerの3人の中から、2票の合意が得られれば先に進めるということで、Follower1から合意が1票返ってきた時点で、データをコミットして先に進めます。

Raft自体の仕組みとしては、読み込み（Read）もLeaderに行くのが原則になっているので、その図がRead Pathというかたちで表現されています。

では、単一パーティションではない場合。1トランザクションで1行ではなく、複数行を更新するような場合もありますが、それをアトミックにする時にはどうしたらいいんだという問題が次に出てきます。

突然難しそうな図になっていますが、マルチパーティションの更新そして2PC、Two-Phase Commitを使うような説明になります。

Two-Phase Commit自体は非常にシンプルで、スライドの図にあるようにProposeして、投票が得られればCommitをするようなプロトコルです。みなさんご存じのとおり、コーディネータの障害に非常に弱いプロトコルになっています。

上段右側の図のように、Proposeを投げてCommitを投げ、終わったタイミングでコーディネータが落ちてしまうと、cohortsと下に書いてありますが、ノードのデータを持っている側は、そのデータがCommitされたと見ていいのか、されていないと見るべきなのかわからなくなってしまう問題があります。Spannerでは、このあたりをPaxosグループを用いてTwo-Phase Commitを行うことで解決をしています。

問題はそれだけではなく、Two-Phase Commit自体がそれほど早くないなどの問題がありますが、それに対する最適化などもいろいろ行われていて、Spannerでは実用的なレベルに達していることになっています。

右下にいろいろ書いてありますが、SpannerとかCockroachDB、YugaByteDBなどは、プラットフォームは違うものの最適化のポイントも異なっていて。そのあたりを比較するのが非常におもしろい内容になっています。TiDBはSpannerとはまた違う、Percolatorという仕組みで分散トランザクションを実装しています。

突然宣伝になりますが、さらに詳しく知りたい方は、こういったNewSQLや分散システム、分散トランザクションを学ぶ本として、『詳説 データベース』が発売されました。

私が監訳を担当していて、第Ⅰ部がストレージエンジン、第Ⅱ部が分散システムと、非常に長い、ボリュームのある本になっています。こちらを読んでもらい、さらにこの中にある論文を深堀りしてもらえれば、このあたりについていろいろ学べるような内容になっています。