[論文まとめ] 「NewSQL」 の 「New」 の部分は一体何ですか

この記事は [DMM advent calendar 2020](https://qiita.com/advent-calendar/2020/dmm) 8日目の記事です。

NewSQL という言葉を聞いたことがある方がいらっしゃるでしょうか。「NewSQL」 の 「NEW」 の部分は一体何ですか等の疑問がありませんか？

筆者は最近 TiDB を勉強する時に、上記の疑問がよく頭に浮かび上がるので、調べてみました。そして、「[What’s Really New with NewSQL?](https://db.cs.cmu.edu/papers/2016/pavlo-newsql-sigmodrec2016.pdf)」 という論文を見つけた。 作者の Andrew Pavlo と Matthew Aslett は両方ともコンピュータサイエンスの専門家なので、この文章は非常に参考になれると思うため、概要をまとめました。自分は英語力が弱いので間違えたことろがあるかもしれませんが、深い興味があればリンクのPDFを読んでもいいと思う。


## 1. A Brief History of DBMSS

* 世界初のデータベース： IBM IMS (Information Management System) (1966年)
  * **アプリケーションロジックとデータ操作ロジックは分離すべきだ** という考え方がついに生まれた
* 70s
  * System R
  * INGRES
  * Oracle
* 80s
  * Sybase
  * Informix
  * DB2
  * オブジェクト指向言語が流行って、オブジェクト指向 DBMS 製品が誕生されたが、受けられなかった。
    * 伝統的なDBMS製品も影響され、 Object/XML/JSON 等のサポートが追加された
* 90s
  * Open Source 製品 MySQL と PostgreSQL が生まれた

2000 年以来、インタネットの発展で インターネットアプリケーション がたくさん生まれた。それらの特徴は、大量なユーザに並行でアクセスされることで、高可用性という要件は要求される。データベースがよくボトルネックになるので、色々方法が生まれた：

* ハードウェアのスペックアップ・垂直拡張
  * データ移行は難しい
  * パフォーマンス向上には限界ある
* データベースミドルウェア
  * applcation が ミドルウェア経由でデータベースにアクセスする
  * 単一レコードのRead/Writeなどの単純な操作に適している
  * 同じトランザクション内複数レコードの操作・Join等は難しい

結局各企業が ミドルウェアから離れて、分散データベースを開発し始めた。理由は

* 伝統的な DBMS は一貫性と正確性を重視していましたが、可用性とパフォーマンスは犠牲にしていた
  * この trade-off がインタネットアプリケーションの要件と逆している
* 豊富な、でもいらない機能が多い
* リレーショナルモデルはアプリケーションに最適な方法ではない
  * 単純な look-up 的なSQLが多く使われている

NoSQL が上記の問題を解決する理由で、発展されていた。 トランザクション、リレーショナルモデルを放棄して、最終的な一貫性と変更可能なデータモデル（例えば、キー/値、グラフ、ドキュメント）を採用していることである。 これで高可用性とスケールアウトをサポートできた。

一方で、NoSQL は 金融システムや注文処理システム等には適切されないので、一貫性と正確性がどう実現するか選択肢がない。そのため NewSQL が誕生された。


## 2. The Rise of NewSQL

NewSQLデータベースの定義:

* モダンなリレーショナル DBMS
* トランザクションの ACID 保証
* OLTP の Read/Write ワークロードが NoSQL と同じ拡張性なパフォーマンスを持つ

言い換えれば、各の特徴が両方持つ:
* 2000 年代の NoSQL DBMS と同じ拡張性
* 1970～80 年代のレガシー DBMS のリレーショナルモデル（SQL を使用）とトランザクション サポート

2000年代登場したオンライン分析処理(OLAP)用データウェアハウスDBMSと違って、NewSQL DBMS がアプリケーションに提供するクエリ処理の特徴は：

1. 短時間実行
2. インデックス検索でデータの一部だけを操作する(full table scan や 大規模分散式 join にならない)
3. 繰り返し使うクエリ（ SQL statement が固定で パラメーターが変わることを考えればいい  ）

他の学者が主張するもう一つのNewSQLの定義:

* ロックフリーの並行性制御技術を使う
* Shared-nothing 分散式アーキテクチャ

(Amazon Aurora は Shared-everthingじゃないじゃないと、個人的に思っています)

## 3. Categorization

本文が下記の３つの種類の NewSQL DBMS を調べた：

1. 新しいアーキテクチャを使用する革新的なシステム
2. Transparent Sharding Middleware
3. クラウドベンダーが提供している Data-as-a-service 製品

ちなみに、既存のシングルノードDBMSの代替ストレージエンジンをNewSQLシステムの分類に含まれない（例としては、MySQLのデフォルトのInnoDBストレージエンジンの代替の TokuDB、ScaleDB、Akiban、deepSQL 等）。
本文の作者の認識は、OLAPのため列指向のエンジン（e.g. Infobright、InfiniDB）に切り替えるメリットがあるが、OLTPのためMySQLのInnoDBエンジンを切り替えるメリットはほどんどない。

### 3.1 New Architectures

(ようやく重要な章に着いた)

ゼロから構築された新しい DBMS である。つまり、既存のシステムを拡張するのではなく、レガシーシステムのアーキテクチャ上の荷物を一切持たずに、新しいコードベースから設計されている。このカテゴリのDBMSはすべて、shared-nothing の分散式アーキテクチャに基づいており、下記のコンポーネントを持っている：

* マルチノード並行性制御 (multi-node concurrency control)
* レプリケーションによるフォールトトレランス (fault tolerance through replication)
* フロー制御(flow control)
* 分散クエリ処理(distributed query processing)

分散実行用に構築された新しいDBMSを使用する利点は、システムのすべての部分をマルチノード環境用に最適化できること。これには、query optimizer やノード間の通信プロトコルのようなものが含まれる。たとえば、ほとんどの NewSQL DBMS は、一部のミドルウェア システムのように中央の場所にデータをルーティングするのではなく、ノード間で直接クエリ内データを送信することができる。

このカテゴリの DBMS はすべて（Google Spanner を除く）、インメモリまたはディスク上の独自のプライマリ ストレージも管理している。つまり、DBMSは分散ファイルシステム(HDFSなど)やストレージファブリック(Apache Igniteなど)に頼るのではなく、カスタムエンジンを使ってリソース全体にデータベースを分散させる責任があるということ。これは、NewSQL DBMSが「 `bring the data to the query` 」 のではなく、「 `send the query to the data` 」ことで重要なポイントである。

*  `bring the data to the query` : データを転送する : ネットワークトラフィック量が多い
*  `send the query to the data` : クエリ自体を転送する : ネットワークトラフィック量が少ない

この種類のDB製品は欠点もある、多くの組織は：

* あまりにも新しすぎるテクノロジーを採用することを警戒しており
* 多くのインストールベースを持つ検証されていないテクノロジーを採用しているということ
* 人気のあるDBMSベンダーと比べて、システムの経験を積んでいる人の数がはるかに少ないこと

また、組織は既存の管理ツールやレポートツールへのアクセスを失う可能性があることを意味する。Clustrix や MemSQL や TiDB のようないくつかのDBMSは、MySQLのワイヤプロトコルとの互換性を維持することでこの問題を回避している。

例の製品

* Clustrix
* CockroachDB (postgresqlとの交換性)
* Google Spanner
* H-Store
* HyPer
* MemSQL
* NuoDB
* SAP HANA
* VoltDB
* TiDB (原論文に含まれない、 論文 2016 年に発表され、TiDB ver1.0 は 2017 年[リリース](https://github.com/pingcap/tidb/releases/tag/v1.0.0)された)

感想：
欠点の「新しすぎるテクノロジーを採用しない組織が多い」ことに対して、割と最近の４年間に、 TiDB は[大勢なユーザに積極的に使われている](https://pingcap.com/case-studies)。 あんまり 「 `新しい技術→使われない→経験が積まない→死ぬ ` 」 の無限ループになってなかったのは不思議ですね。

### 3.2 Transparent Sharding Middleware
ACID をサポートする Sharding Middleware のこと、集中型ミドルウェアコンポーネントとワークロードが構成するクラスターである。

ワークロードの特徴は：

1. 同じDBMSを実行し
2. データベース全体の一部しか持たず
3. 独立してアプリケーションからアクセスされない

集中型ミドルウェアコンポーネントの役割：

* クエリのルーティング
* トランザクションの調整
* ノード間のデータ配置
* レプリケーション、パーティショニングの管理

欠点：

* 伝統的な DBMS を使用することになる
  * 伝統的な DBMS は `disk-oriented` な設計であり
  * 新しいアーキテクチャで構築された NewSQL システムのように、 `memory-oriented` で最適化されたストレージ管理や並行性制御できない
  * これまでの研究では、 `disk-oriented` 設計は高いCPUコア数とより大きなメモリ容量を利用してスケールアップするのを妨げることが表れている。

例の製品：

* AgilData Scalable Cluster
* MariaDB MaxScale
* ScaleArc
* ScaleBase

### 3.3 Database-as-a-Service
この部分は皆さんが馴染まれている aws Aurora 的なサービスので、 skip しておく。


## 4. The State of the Art

では一緒に NewSQL 各コンポーネントの設計を確認し、革新するところがあるかどうか見る。

### 4.1 Main Memory Storage

伝統的な DBMS が `disk-oriented` の設計理念で、データを主にディスクに保存されて、ioスピードが遅いからバッファーをメモリで管理するので、コスト節約の目的が達成した。今の時代メモリの値段と容量が改善され、全てのデータをメモリに保存することも可能になった。それで、NewSQL DBMS は buffer pool manager や 重い並行性制御等のコンポーネントがいらなくなるため、パフォーマンス改善できた。

メインメモリストレージアーキテクチャをベースにしたNewSQL DBMS:

* 学術的なシステム（H-Store、HyPerなど）
* 商業的なシステム（MemSQL、SAP HANA、VoltDBなど）

#### 今まで存在する技術

* 80s 
  * Wisconsin-Madison 大学は にもうメモリデータベース領域にたくさん研究した
    * インデックス、クエリ処理、リカバリアルゴリズムなど
  * 最初の分散型メインメモリ DBMS であるPRISMA/DBも開発された
* 90s
  * 商用メインメモリ DBMS : Altibase 、OracleのTimesTen、AT&TのDataBlitz

#### NewSQL の革新

NewSQL の新しいところは、データベースにアクセスされないデータをメモリに削除して、メモリ使用量を削減することで、メモリサイズより大きいデータ量のデータベースを管理することが可能になること。

一般的なアプローチ： システム内部の内部追跡仕組みを使用して、アクセスされなくなったデータを識別し、削除のためにそれらを選択すること。

H-Store のやり方：  anti-caching コンポーネントが cold データをディスクに移動し、元のメモリの位置に `tombstone` リコードで表記し、トランザクションに使われる際に、それを中断し、別の thread で非同期にレコードをメモリに戻す。

VoltDB のやり方： OS の paging 機能を使う。

違う案の MemSQL： log-structured のデータ構造を使っているため、DBA がカラム形式で格納するテーブルを指定することができる。

### 4.2 Partitioning/Sharding

ほとんど分散式 NewSQL DBMS がスケールアウトする方法は、データベースをパーティションまたはシャードと呼ばれる不連続なサブセットに分割する。

#### 古い技術

実は パーティション化されたデータベース上での分散トランザクション処理は新しい技術ではない。

* 1970年代後半の SDD-1 プロジェクトで Phil Bernstein （および他の人たち） の研究
* 1980年代初頭 System R と INGRES の分散式版もある
* IBM の  R* は SDD-1 の share-nothing と disk-oriented の似ている設計を採用した
* INGRES の分散式版は分散クエリを再帰的に細かく分割する動的クエリ最適化アルゴリズムでよく知られている
* Wisconsin-Madison 大学的 GAMMA プロジェクトは 様々なパーティションストラテジを研究した

でも、これらの初期の分散型DBMSは、2つの理由で普及されなかった

* 20世紀のコンピューティングハードウェアが非常に高価だった
* 高性能な分散型DBMSに対するアプリケーションの需要が単に存在しなかった
  * その当時TPSの需要は数十から数百ぐらい

#### New

パーティション技術は、 Hash 関数で分割するか(sharding)、 range で分割するか、２種類分けられる。よく １つのノードが関係あるフラグメントのノードを管理責任を持つ設計になる。ただ DBaaS システムはこのタイプのパーティションストラテジをサポートしない。

##### ツリーの構造

多くの OLTP データベースは、ツリーのような構造に変換することができるので、root table のレコードと関係あるブランチテーブルを同じパーティションで格納する形で実現している。下記のような例で、１つの顧客のデータが同じパーティションにあるため、トランザクションが単一のパーティションでデータをアクセスするだけで済むので、2相コミット（Two-Phase Commit）を使用する必要がない。これでシステムの通信オーバーヘッドが削減される。

(Google Spanner はこのパターンですね)

 ![customer](https://user-images.githubusercontent.com/689799/101436207-0d1bec00-3951-11eb-8835-aba800a720ac.png "customer")

##### コンピューティングとストレージの分離設計

一部 NewSQL が異種なノードを持っている（NuoDBとMemSQL、TiDBも)。NuoDB のノードはコンピューティングとストレージの分離設計になっている：

* ストレージマネージャ（SM）
  * ストレージ ノード
  * それぞれがデータベースのパーティションを格納する
* トランザクションエンジン(TE)
  * コンピューティング ノード
  * クエリを処理するために、そのクエリに必要なすべてのデータを取得する（適切なSMまたは他のTEから）。
  * NuoDB の ロードバランシング トラテジで、一緒に使用されるデータが同じTEに存在することが多いことを保証している。
* この設計で、上記のツリー構造な設計はいらなくなる(アプリケーション側は汎用的DBを使うイメージができる)

MemSQL は NuoDB と似ているが、コンピューティング ノードにはデータをキャッシュしないため、 state-less な特徴がある。 (TiDB は MemSQL と似ているようなイメージですね)

##### Live migration と Rebalance
Live migration は NewSQL の重要な特性である。DBMS は物理リソース間でデータを移動してリバランスを取ったり、ホットスポットを緩和したり、サービスを中断することなく DBMS の容量を増減させたりすることができる。これは NoSQL と似ているが、  ACID 保証を維持しなければならないため、より困難である。実現するため、２つのアプローチ：

1. 物理ノード間に分散された多数の粗視化された「仮想」（すなわち論理）パーティションでデータベースを整理すること。DBMS が再バランスを取る必要があるときには、これらの仮想パーティションをノード間で移動させる。
2. より細かいリバランスを実行すること。(MongoDB、ScaleBase、H-Storeはこの案です)

### 4.3 Concurrency Control

並行性制御は、システム全体のほぼすべての側面に関与するため、データベースシステムのトランザクション処理の中で最も中心的で重要な部分である。 それは、異なるユーザーが別個に所有しているかのようにデータベースにアクセスすることを可能にし、トランザクションの原子性と分離を保証し、システムの全体的な動作に影響を与える。

#### トランザクション協調プロトコル

分散データベースのもう一つ重要な側面は、トランザクション協調プロトコル (transaction coordination protocol) は集中型 か 分散型 か、どちらに使用するかの問題。

* 集中型
  * すべてのトランザクションの操作はコーディネータ (coordinator) を経由しなければならない
  * 1970-1980年代のTPモニター(IBM CICS、Oracle Tuxedoなど)で使用されていた
* 分散型
  * 各ノードは、自分が管理するデータにアクセスするトランザクションの状態を維持する
  * 並行するトランザクションが競合するかどうかを判断するために、互いに調整しなければならない

分散型コーディネータはスケーラビリティの点では優れているが、トランザクションのグローバルな順序を生成するためには、各ノードが高度に時刻同期されている必要がある。（Google Spannerがこのパターンで、 原子時計とGPS受信機を備えて時刻同期しているようです ）

#### 2相ロッキング（2PL）

1970～80 年代の最初の分散型 DBMS は、2相ロッキング（2PL）方式を採用していた。

* SDD-1 : 集中型コーディネータ + 2相ロッキング（2PL）
* IBM の R* : 分散型コーディネータ + 2相ロッキング（2PL）
* INGRESの分散版 : 2相ロッキング（2PL）で、集中型コーディネータで デッドロック検出

#### TO と MVCC

新しいアーキテクチャに基づくNewSQLシステムのほとんどは、デッドロックの処理が複雑なため、2PLを避けている。代わりに、タイムスタンプ順序（TO）並行性制御の バリエーション を使用している。 これを使う前提は トランザクションがシリアル化順序 (serializable ordering) に違反するインターリーブされた操作を実行しないことである。

NewSQLシステムで最も広く使用されているプロトコルは分散型マルチバージョン並行性制御（MVCC）で、トランザクションによって更新されたときにDBMSがデータベース内のタプルの新しいバージョンを作成する。複数のバージョンを維持することで、別のトランザクションが同じタプルを更新した場合でもトランザクションを完了させることができる。また、長期的に実行される読み取り専用のトランザクションでも、 Write がブロックされないようにすることができる。 

分散型マルチバージョン並行性制御(MVCC) というものは、新しい技術ではない。 MVCC は 1979 年 MIT の PhD 論文にもう記述された。1980年代 Digital 社の VAX Rdb と InterBase が MVCC を使用した。（ InterBase のアーキテクチャを設計したのは Jim Starkey で、彼は NuoDB や Falcon MySQL ストレージエンジン の設計者である）

分散型マルチバージョン並行性制御（MVCC）を使う NewSQL 製品:

* MemSQL
* HyPer
* HANA
* CockroachDB
* TiDB

他のデータベース製品はほとんど2PL と MVCC を組み合わせて使用している。データベースの変更は  2PL でロックしないといけないが、読み取り専用のクエリは MVCC のおかげで ロックを取得する必要がない。最も有名な実装はMySQLのInnoDBだが、GoogleのSpanner、NuoDB、Clustrixでも採用されている。

すべての Transparent Sharding Middleware 種類の製品と DBaaS 製品は、 MySQL を使うため、2PL と MVCC の組み合わせ形になっている。

Spannerの並行性制御の実装は、NewSQLシステムの中で最も新しいものの1つと考えられている。2PLとMVCCの組み合わせに基づいているが、Spannerが異なるのは、専門なハードウェアデバイス（GPS、原子時計など）を使用して、高精度の時刻同期を保証すること。これらを使用してトランザクションにタイムスタンプを割り当て、広域ネットワーク上でのマルチバージョンデータベースの一貫性を保証する。

CockroachDB （TiDBも）似ている仕組みですが、専門なハードウェアデバイスがないため、クロックとカウンタを組み合わせて実現した。

結論を言うと、MVCC+2PL等は新しい技術ではなく、古い技術が新ハードウェア＋分散式環境でエンジニアリングされること。

### 4.4 Secondary Indexes

伝統的なデータベース製品として、全体が1つのノード上にあるため、セカンダリインデックスをサポートするのは簡単だが、分散型DBMSにおけるセカンダリインデックスの課題が難しい。

分散データベースがセカンダリインデックスをサポートするための 2 つの設計上の決定事項がある：

* セカンダリインデックス をどこに格納するか
* トランザクションの中で セカンダリインデックス をどのように維持するか

集中型コーディネータの案を採用した DBMS なら、コーディネータノード と シャードノードの両方に置くことができる。この案の利点は単一バージョンのセカンダリインデックスが実現できて、メンテナンスしやすい。

新しいアーキテクチャに基づくNewSQLシステムはすべて分散化されており、パーティショニングされたセカンダリインデックスを使用している。各ノードにインデックスが一部のデータを持つ状態で、パーティショニングの要素とレプリケーションの要素を合わせて見ると、選択肢は下記である：

* パーティショニングされたインデックス
  * インデックスを読み込む
    * 複数のノードに検索する
  * インデックスを書き込む
    * 一つのノードだけに書き込む
* レプリケーションされたインデックス
  * インデックスを読み込む
    * 一つのノードだけに検索する
  * インデックスを書き込む
    * 複数のノードに書き込む

Clustrix は上記の選択肢のいいところを結合した：

* Range で セカンダリインデックスを パーティショニング する
* ノードに Range と パーティションのマップを格納する
* 検索・更新のアクセスに対して、正しいノードにルーティングして、ノードがこのアクセスを応答する

### 4.5 Replication

データベースのレプリケーションに関しては、2つの設計上の決定：

#### ノード間でどのようにデータの一貫性を保つ
* 強く一貫性のあるDBMS
  * トランザクションの書き込む： すべてのレプリカで確認されないと行けない
  * 読み込むは一貫性がある
  * レプリカが１つ死んでも、他のレプリカにデータが格納されるので安全
  * 欠点： 二相コミット等の手法で、すべてのレプリカにコミット成功するまで、待たないと行けない。レイテンシが長い、また、１つのレプリカが障害なるときに、レイテンシが発生してしまう

#### どのようにデータを複数ノードに伝播する
* active-active レプリケーション
  * 各レプリカノードが同じリクエストを並行に同時に処理する
  * データが一致していなくなる可能性
* active-passive レプリケーション
  * １つのノードがリクエストを受けて処理し、この状態を他のレプリカノードに送る
  * 多くの NewSQL はこの案を採用している

#### 新しい・古い技術？

state machine replication 等の技術は 1970年代にもう研究されていた。
NewSQL が新しいところは、以前の時代にない 広域ネットワーク（WAN）上でのレプリケーションである。 
帯域とレイテンシによって、同期更新や非同期更新などのレプリケーション方法を提供している。
前文の通りに、Spanner と CockroachDB は時刻同期の手法で強く一貫性のあるレプリカを提供している。
（2020現在は TiDB も）


### 4.6 Crash Recovery

クラッシュ回復仕組みは NewSQL DBMSのもう一つの重要な機能である。

* 伝統的なDBMSの クラッシュ回復 の目標：データが失わない
* NewSQL の クラッシュ回復 の目標： データが失わない + ダウンタイムも最小化

伝統的なDBMSに使われる技術： 書込み先ログ(WAL)

* 障害後にシステムをリスタートし、 checkpoint をロードし、WALを再生して、障害前の正しい状態に戻す。
* この案の名称は ARIES で、 1990前後 IBM に発明され、多くの DBMS に使われている。

レプリカを持つ分散型DBMSには、この方法が利用できない。理由は master が障害になったら、他のレプリカが master になって、元 master が WAL で復活されても、新 master に新しい変更が既に発生したので、新しい master からすべての変更を同期しないと行けない。２つの案：

* checkpoint と WAL でローカルでデータを復元し、新しい master からログをプルする。障害時点以降のログでデータを復元する
* ローカルのデータを捨てて、新しい master からすべてのデータを取る。

新しいアーキテクチャに基づくNewSQLシステムは、既製のコンポーネント（ZooKeeper、Raftなど）と、既存のアルゴリズムの独自のカスタム実装（Paxosなど）を組み合わせて使用している。これらはすべて、1990年代以降の商用分散システムで利用可能な標準的な手順と技術である。

## 5. Future Trends

将来的にDBMSが分析的なクエリや機械学習アルゴリズムを実行する能力であると考えられている。このようなワークロードは「real-time analytics」 や 「hybrid transaction-analytical processing (HTAP)」に呼ばれる。

HTAP を実現する３つの方法

1. OLTP workload と OLAP workload を分けて構成する
2. lambda architecture。DBMS以外に別のバッチ処理システム（Hadoop、Spark等）

上記の２つの方法は、同じくデータを異質なシステムに導入しないと行けないため、問題が多い：

* 遅延
* デプロイ・メンテナンスのコスト
* それぞれのシステムに対して、クエリを書くのも面倒

それで３つ目の方法は

３.  HTAP データベース

下記の２つの要素を単一の DBMS の中に組み込んでいること：

* OLTP（インメモリストレージ、ロックフリー実行など）
* OLAP（カラム型ストレージ、ベクトル化実行など）

SAP HANAとMemSQLは、HTAPシステムとして売り出した最初のNewSQL DBMSでした。両方とも2つの異なるストレージマネージャ（1つは行用、もう1つは列用）を使用しているが、それらを1つの実行エンジンに混在させている。

(2020年現在は、TiDB 4.0 は HTAP データベースになっている)

## 6. Conclusion

結論として、NewSQLは既存のシステムアーキテクチャからの根本的な技術革新ではなく、むしろデータベース技術の継続的な開発におけるということである。

これらのシステムが採用している技術のほとんどは、学術界や産業界の以前のDBMSに存在していたが、全てをまとめて実装したことはなかった。NewSQL はすべてのアイデアを単一DBMSに組み込むことは、簡単なエンジニアリングではない。

自分の感想は、NewSQL は根本的な `New` ではない技術であっても、いい意味もあると思います。DB業界既に存在する技術を組み合わせて使うことで、**NewSQLの技術成熟度は低くない**ことじゃないかなと思います。