SQLiteの歴史
2000年 リリース1 HashベースのGDBMストレージエンジン
SQLite1はGPLのGDBM(GNU Database Manager)エンジンを使ったので、その流れからライセンスはGPLで始まります(現在はパブリックドメイン)。この時からServerlessとSinglefile databaseがSQLiteの基本方針です。しかし、元となったGDBMはHashテーブルでありレンジスキャンができないので、Berkeley DBのドキュメントを2日ほど読んでからB-Treeストレージエンジンの開発を始めました。
2001年 リリース2 B-Treeストレージエンジン
SQLiteが携帯電話や自動車、冷蔵庫などに搭載され広がり始めたのです。今はもうなくなりましたが携帯大手のモトローラから「バイナリーデータをサポートしてほしい」と言われてSQLite3の開発が始まりました。
2004年 リリース３ バイナリデータのサポート
LSMへの挑戦
まず初めに、データベースとストレージエンジンを混同しないでください。MySQLやPostgresと言ったらデータベースです。そして以下は有名なストレージエンジンの一部です：
Berkeley DB GDBM LevelDB LMDB RocksDB Kyoto Cabinet
データベースはSQLを解析してエンジンの実行バイトコードにします。対してストレージエンジンはバイトコードを解析しファイルにアクセスします。
B-TreeとLSM(Log Structured Merge)
現在の二大ストレージエンジンと言えばB-TreeとLSMです。LSMが新しくて良いという風潮 もありますが、果たして本当にそうなのでしょうか?
- B-tree = slow and bad
- LSM = fast and good
B-Treeの問題はWrite Amplification（書き込み増幅）
たった20バイトのInsertでも「ページ単位で書き込まなければいけない」のを表しているのが以下の図です。隣り合うデータは物理的に書き戻されていることになります。これは無駄だしSSDなんかには最適とは言えません。新しい波はLSMをベースにしています。
LSMの魅力は”blind” write
NoSQLのHBaseやBigTableなんかがB-Treeのように隣り合う値をページ単位でReadしてからWriteするなんて無駄なI/Oは、扱うデータ量を考えると致命的ですよね？ blind writeは「無条件にWriteする」という点で優れているのです。
まずメモリ上で作られたB-Treeが塊でディスクにwriteされ
３回writeされたイメージがこうなります
そして次にバックグラウンドプロセスとかで溜まったb-treeをMergeします
このmergeで階層(Level)が作られていくわけです。そう、これが有名なLevelDBの語源です。
SQLite4のLSM開発にはTokuDBの開発者でもあるDan Kennedyが参加しました。当然、SQLite3より高速にするのが目的です。確かにLevelDBより高速になるための改良点はたくさんありました。ところがそこには盲点もあったのです。
