SQLite4の開発物語

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より高速になるための改良点はたくさんありました。ところがそこには盲点もあったのです。