SHOEISHA iD

※旧SEメンバーシップ会員の方は、同じ登録情報(メールアドレス&パスワード)でログインいただけます

EnterpriseZine(エンタープライズジン)編集部では、情報システム担当、セキュリティ担当の方々向けに、EnterpriseZine Day、Security Online Day、DataTechという、3つのイベントを開催しております。それぞれ編集部独自の切り口で、業界トレンドや最新事例を網羅。最新の動向を知ることができる場として、好評を得ています。

直近開催のイベントはこちら!

Security Online Day 2022

2022年9月16日(金)10:00~17:10

EnterpriseZine(エンタープライズジン)編集部では、情報システム担当、セキュリティ担当の方々向けの講座「EnterpriseZine Academy」や、すべてのITパーソンに向けた「新エバンジェリスト養成講座」などの講座を企画しています。EnterpriseZine編集部ならではの切り口・企画・講師セレクトで、明日を担うIT人材の育成をミッションに展開しております。

お申し込み受付中!

DB Press

SQLite4の開発物語

db tech showcase2017 スペシャルセッション


 世界で一番使われているデータベース: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より高速になるための改良点はたくさんありました。ところがそこには盲点もあったのです。

次のページ
LSMの魅力blind write

この記事は参考になりましたか?

  • Facebook
  • Twitter
  • Pocket
  • note
DB Press連載記事一覧

もっと読む

この記事の著者

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

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

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

この記事は参考になりましたか?

この記事をシェア

EnterpriseZine(エンタープライズジン)
https://enterprisezine.jp/article/detail/9928 2017/10/20 10:31

Job Board

PR

おすすめ

アクセスランキング

アクセスランキング

イベント

EnterpriseZine(エンタープライズジン)編集部では、情報システム担当、セキュリティ担当の方々向けに、EnterpriseZine Day、Security Online Day、DataTechという、3つのイベントを開催しております。それぞれ編集部独自の切り口で、業界トレンドや最新事例を網羅。最新の動向を知ることができる場として、好評を得ています。

2022年9月16日(金)10:00~17:10

新規会員登録無料のご案内

  • ・全ての過去記事が閲覧できます
  • ・会員限定メルマガを受信できます

メールバックナンバー

アクセスランキング

アクセスランキング