SQLite4の開発物語 (1/3):EnterpriseZine(エンタープライズジン)
Shoeisha Technology Media

EnterpriseZine(エンタープライズジン)

EnterpriseZine(エンタープライズジン)

テーマ別に探す

SQLite4の開発物語

2017/10/19 12:26

 世界で一番使われているデータベース:SQLite。その生みの親であるRichard Hipp氏がSQLiteリリース4の2年間の開発を通して学んだ新しい知見を語ってもらいました。最後に大どんでん返し。Sqlite3に戻ってきます!

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年 リリース3 バイナリデータのサポート

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され

 
    B-Treeが塊でディスクに

3回writeされたイメージがこうなります

 
    3回writeされたイメージ

そして次にバックグラウンドプロセスとかで溜まったb-treeをMergeします

 
    b-treeをMerge

このmergeで階層(Level)が作られていくわけです。そう、これが有名なLevelDBの語源です。


 
    b-treeをMerge

 SQLite4のLSM開発にはTokuDBの開発者でもあるDan Kennedyが参加しました。当然、SQLite3より高速にするのが目的です。確かにLevelDBより高速になるための改良点はたくさんありました。ところがそこには盲点もあったのです。

※この続きは、会員の方のみお読みいただけます(登録無料)。


著者プロフィール

  • 小幡一郎(オバタイチロウ)

    DBOnline特命記者  ユーザ企業としてPCやオフコンからコンピュータキャリアはスタートし、メインフレーム・パッケージベンダーそして日本オラクルを経て1995年インサイトテクノロジーを設立。2007年、インサイトテクノロジーから離れ、デンマークのMiracleグループに参加、ミラクル・アジアパ...

バックナンバー

連載:DB Press

もっと読む

All contents copyright © 2007-2017 Shoeisha Co., Ltd. All rights reserved. ver.1.5