(cache)RDBの限界とNoSQLの登場

こんにちは、Stamp Incの村本です。
NoSQLの過去と未来についてまとめます。
普段はFirebaseの技術コンサルティングをやってます。

RDBの歴史

NoSQLの必要性を語るためにまず、RDBの登場の経緯、歴史から見ていこうと思う。RDBの登場は1970年代まで遡る。

RDBの登場

RDB(リレーショナルデータベース)が登場する以前のデータベース市場では、階層型と呼ばれるモデルに基づいた製品が主流だった。当時はIBMが開発したInformation Management System(IMS)が利用されていた。

IMSが使われた最も有名なシステムが、1961年から始まったNASAのアポロ計画です。最終製品を構成する部品の階層関係を表したリストをBOM（Bill of Materials）と呼び、製造業ではどのような製品を作るかを問わず、このBOMが設計図と並ぶ重要な情報です（BOMは日本語では「部品表」と呼びます）。IMSはロケットの膨大な部品群を管理するという難解な課題に優れた解を与えたデータベースでした。

RDBを生み出したのはIBMのエンジニア

40代半ばのエンジニアE.F.コッドが書いた「A Relational Model of Data for Large Shared Data Banks」

リレーショナルデータベースの考案者 E. F. CODD

A Relational Model of Data for Large Shared Data Banks

[論文] https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf
[参考] エドガー・コッドの「リレーショナル・データ・モデル論」
[参考] https://www.cc.u-tokai.ac.jp/text/2005/Access-intro.pdf

その後、外部のエンジニアたちによって多くのRDBが開発される。

年代	DB	主要な開発元
1974年	Ingres	カリフォルニア大学
1979年	Oracle Database	Oracle
1983年	DB2	IBM
1987年	Sybase SQL Server	Sybase
1989年	MS SQL Server	Microsoft
1989年	PostgreSQL	カリフォルニア大学
1995年	MySQL	MySQL AB

RDBよりも先に生まれたACIDの概念

ACIDは1983年にアンドレアス・ロイターとテオ・ヘルダーによって提唱されが、この概念はジム・グレイよって1970年代後半に定義された。また、1973年にIMSはACID トランザクションをサポートしている。

年代	できごと
1973年	IMSはACID トランザクションをサポート
1979年	ジム・グレイがACIDの概念を定義
1983年	アンドレアス・ロイターとテオ・ヘルダーがACIDを提唱

データの整合性を重要視してきた歴史

RDBがトランザクションを重要視しているのには理由がある。開発当初は世界中の人間がアクセスするインターネットはなく、マシンの性能もムーアの法則の初期で限界を意識してなかったはずだ。
システムがデータベースに求めたのはスケール性能ではなく、厳密な一貫性だったと言える。

年代	できごと
1961年	最初のパケット通信の論文
1969年	ARPANETで初のパケット送信
1980年	イーサネットの規格公開
1982年	TCP/IP標準化
1982年	Simple Mail Transfer Protocol (SMTP)
1983年	Domain Name System (DNS)

事実世界のインターネット人口が増えたのは1990年代からだ。

[引用] http://www.soumu.go.jp/johotsusintokei/whitepaper/ja/h10/html/98wp2-3-1f.html

[引用] http://www.soumu.go.jp/johotsusintokei/whitepaper/ja/h29/html/nc144210.html

NoSQLの登場

1990年に入るとインターネットの利用人口が急激に増加することになる。
この頃からトランザクションに最適化されて設計されたDBでは性能劣化が始まり、システムはデータベースに対しスケール性能を必要とし始める。

多くの開発者は、単一の強力なサーバーでリレーショナル・データベースを実行するのではなく、リレーショナル・データベース管理システム (RDBMS) のパーティショニング (シャーディング) を試み、(サーバーの「クラスター」内で) 分散システムとして実行しました。しかし、リレーショナル・データベースには 1 次書き込みサーバー・ノードと読み取り専用のレプリカとの間のデータの平行性に問題があり、アクセス・スピードに悩まされ、異なるノードに格納されているテーブル間の結合操作を効果的に実行できないことがわかりました。

1998年Carlo StrozziによってSQLのない軽量なDBを推進する運動として"NOSQL"という言葉が使われる。

NotOnlySQL

2000年代半ばに2つの企業がデータの保管と検索のための新たなモデルを相次いで発表する。
Googleは2006年「A Distributed Storage System for Structured Data」でカラム指向データベース・システムである「BigTable」の妥当性を示し、Amazonは2007年「Dynamo」で分散キーバリュー・ストレージ・システムを提示した。

そして、2009年にサンフランシスコで開かれたミートアップで「NoSQL」がハッシュタグとして使われ、次々生まれることになるRDBでないデータベースは「NoSQL」と呼ばれることになる。

Bigtable: A Distributed Storage System for Structured Data
Dynamo: Amazon’s Highly Available Key-value Store

NoSQLを次のレベルに引き上げたCassandra（カサンドラ）

Facebookによって開発されたNoSQLのデータベースCassandra。
Facebookは2008年7月にCassandraをオープンソースソフトウェアとして公開し、2009年3月からApache Incubatorプロジェクトとなる。DynamoDBのような高い可用性とスケーラビリティを保持している。

Facebookのデータチームを率いるJeff HammerbacherはCassandraをAmazon DynamoDBのようなインフラストラクチャ上で動作するBigTableデータモデルであると表現している。

調節可能な整合性レベルと結果整合性

CassandraはDynamoと同じく、基本的には結果整合性を前提としているが整合性レベルの調節が可能だ。これにより開発者はスケーラビリティとのトレードオフを実現できるようになっている。

書き込み性能に最適化

AmazonのDynamoがB-treeを採用しているのに対し、CassandraはGoogleのBigTableをモデルとして作られたHBaseと同じくLSM Treeを採用している。

Cassandraが採用したCAP定理はAP

HBaseはCAP定理のCPを採用し、CassandraはAPを採用している。
一貫性を強く意識して作られてきたデータベースの歴史の中で一貫性を捨てたことには大きな意味がある。正確には捨てた訳でなくEventual Consistency（結果整合性）の概念を取り入れている。

Eventual Consistencyまでの一貫性図解大全

分散合意プロトコルPaxos

インターネット人口の増加に伴い世界的にデータベースを分散化させるニーズが出始める。そこで重要になったのが地理的に分散化したデータベースでも一貫性を保つ手法だ。Paxosプロトコルは1990年に登場し命名されたが、論文として出版されたのは1998年。

[参考] https://ja.wikipedia.org/wiki/Paxos%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

次々とNoSQLを発表するGoogle

2011年スケーラビリティと一貫性を両立した分散データストアMegastoreを発表。
Google Cloud Platform（GCP）では、Cloud Datastoreというデータストアを利用することができ、Cloud Datastoreは、内部的にMegastoreを用いて実装されている。

Megastore: Providing Scalable, Highly Available Storage for Interactive Services

2012年に設計が論文として公開されたSpanner。2017年からはGoogle Cloud Platform上で提供されている。
トランザクションに対する最も厳格な同時実行制御（外部整合）をクライアントに保証している。

Spanner: Google's Globally Distributed Database
[参考] Spanner, TrueTime & The CAP Theorem

データベースにおける整合性の定義

用語	定義
整合性	データベースシステムにおける整合性は、あらゆるデータベーストランザクションが、影響されるデータを、許可された方法でのみ変更しなければならないという要件を指します。データベースに書き込まれるデータは、定義されたすべてのルールに従って有効でなければなりません。
直列化可能性	直列化可能性は、異なるトランザクションの一部が並列に複数のオブジェクトを読み書きする可能性がある、トランザクション分離プロパティです。トランザクションの挙動が、トランザクションが順次実行された場合と同じになることを保証します。ただし、その順序は、トランザクションが実際に実行された順序と違っても問題ないとされます。
線形化可能性	線形化可能性は、レジスタ（個々のオブジェクト）の読み書きの順序を保証します。オペレーションをトランザクションとしてグループ化しないので、競合のマテリアライズのような対策を講じなければ、書き込みスキューのような問題を防げません。
強整合性	すべてのアクセスがすべての並列プロセス（またはノード、プロセッサなど）によって、同じ順序で（順次実行されるように）見えます。レプリケートされたオブジェクトが線形化可能である場合、レプリケーションプロトコルは強整合性を示すという定義もあります。
結果整合性	結果整合性は、データベースへの書き込みを停止してしばらく待つと、最終的に、すべての読み取り要求に対して同じ値が返されることを意味します。
外部整合性	トランザクションの commit が認識される順序は順次実行順序と整合します。外部整合性は、線形化可能性と直列化可能性のどちらよりも強いプロパティです。

[参考] https://cloud.google.com/blog/ja/products/gcp/why-you-should-pick-strong-consistency-whenever-possible

NoSQLが解決したRDBの特性

RDBのボトルネックは二つ

一貫性を担保するためストレージを共有する構成を取る必要があること
SQLが強力で柔軟なため複雑な処理を実行できてしまうこと

データモデルの限界

RDBは構造化データを表現しにくい

RDBは静的なテーブルの構造で、システムを運用する中で動的に変更することは想定していないことが一般的。
テーブル定義やテーブル間のリレーションを変更することは大規模なマイグレーションが必要になる。

RDBの限界とNoSQLの登場