これまでの私のお気に入りのトピックの2つは、SQLiteとキーバリューデータベースです。 そして今回は、両方について一度に書きます。この投稿は、SQLite 4で使用されるLSMベースのキー値ストレージのPythonラッパーに捧げられています。



私はSQLiteのリリースにあまり厳密には従いませんが、バージョン3.8.11が私の注意を引きました。その記述は3.8.0と比較してパフォーマンスが大幅に向上したと主張しているためです。 付随する情報で、フルテキスト検索のための新しい実験的な拡張機能についての言及に出くわしました（ これについてはかつて書きました ）。そのため、 SQLite 4の状況はどうなっているのでしょうか。



入手可能な情報を検討した結果、開発者のタスクの1つは、新しいバージョンのプラグインデータベースエンジンにインターフェイスを提供することであることに気付きました。 この投稿の執筆時点で、SQLite 4にはすでに2つの組み込みのバックエンドがあり、そのうちの1つはLSMベースのキーと値のストレージです。 過去2か月間、 UnQLiteとVedisの組み込み kvリポジトリ用のPythonラッパーを書いている間にCythonで遊んでいました 。 そして、Cythonを使用して、SQLite 4で使用されるLSMベースのデータベースエンジンインターフェイスを作成すると良いと思いました。



SQLite 4と小さなLSMヘッダーファイルのソースコードを理解したので、 python-lsm-db （ ドキュメント ）を書きました。

LSMツリーとは何ですか？

理論を理解している限り、LSMツリーは次のもので構成されています。

• バッファとして機能するメモリツリー
• ディスク上にある1つ以上の永続ツリー。

頭字語LSMの文字Mはマージを表します。これは、バッファリングされたレコードをディスク上のツリーと結合する操作です。 この手順により、ディスク上のシークのコストを大幅に削減できます。これは、高速記録という1つのことを意味します。 一方、システムは複数のツリーを検索するため、ランダム読み取りは遅くなる場合があります。 また、LSMツリーは、同等のBツリーよりも長くなる場合があります。 LSMツリーのもう1つの利点は、保存されたデータの断片化が少なくなり、キー範囲の読み取りが高速になることです。



もう一度強調します。これは理論に対する私の理解です。 何らかの方法で誤解されたり、重要なポイントを見逃したりする可能性があります。

プロパティ

SQLite 4のLSM実装には、非常に興味深いプロパティがいくつかあります。

• アプリケーションで使用される埋め込みDB。
• カーソルを使用してキーを表示する順序を設定します。
• トランザクション（ネストされたトランザクションを含む）。
• シングル書き込み/マルチ読み取りをサポートするMVCCベースのトランザクション並列化モデル。
• ディスク上に単一のファイルとして保存されているデータベース。
• アプリケーションまたは電源障害時のデータ復元力。
• ニーズに合わせて柔軟にカスタマイズする機能。

Pythonライブラリの作成

それでは始めましょう。 まず、virtualenvを作成し、pipを使用してCythonとlsm-dbをインストールします。

$ virtualenv test_lsm $ cd test_lsm $ source bin/activate (test_lsm) $ pip install Cython lsm-db
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

インストールを確認するには、次の行を実行できます。

 (test_lsm) $ python -c "import lsm, tempfile; lsm.LSM(tempfile.mktemp())"
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

すべてがインストールされ、正常に動作している場合、このコマンドの実行には何も伴いません。 しかし、LinuxのPython 2.7でのみテストしたことに留意してください。 したがって、WindowsでPython 3.4を使用している場合、このコードをデバッグする必要があります。

余談

以下は、lsm-dbライブラリの主な機能を反映する対話型コンソールセッションの例です。 APIドキュメントには、クラス、メソッド、およびパラメーターと戻り値の説明の完全なリストが含まれています。



まず、仮想環境でPythonインタープリターを起動し、データベースファイルへのパスを指定して、LSMオブジェクトのインスタンスを作成します。

 >>> from lsm import LSM >>> db = LSM('test.ldb')
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

LSMクラスには、ファイル名のほかに、設定可能なパラメーター （ブロックサイズ、ページサイズなど）がいくつかあります 。

キーバリュー機能

SQLite 4 LSMエンジンはキー/値ストアであり、Pythonのdictオブジェクトに多少似ています。 dict-like APIを使用します。

 >>> db['foo'] = 'bar' >>> print db['foo'] bar >>> for i in range(4): ... db['k%s' % i] = str(i) ... >>> 'k3' in db True >>> 'k4' in db False >>> del db['k3'] >>> db['k3'] Traceback (most recent call last): File "<stdin>", line 1, in <module> File "lsm.pyx", line 973, in lsm.LSM.__getitem__ (lsm.c:7142) File "lsm.pyx", line 777, in lsm.LSM.fetch (lsm.c:5756) File "lsm.pyx", line 778, in lsm.LSM.fetch (lsm.c:5679) File "lsm.pyx", line 1289, in lsm.Cursor.seek (lsm.c:12122) File "lsm.pyx", line 1311, in lsm.Cursor.seek (lsm.c:12008) KeyError: 'k3'
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

注：削除されたばかりのキーにアクセスしようとすると、KeyErrorがすぐにポップアップしました。 デフォルトでは、キーを検索するとき、ライブラリは最初に完全に一致するものを探します。 SQLite 4では、探している値が存在しない場合、LSMは最も近いキーを辞書的に検索することもできます。 一致する検索に加えて、次に近いキーを返す検索メソッドがさらに2つあります：SEEK_LEとSEEK_GE。 完全に一致するものが見つからない場合、SEEK_LEはキーの最上部（最高のキー）を返します。その値は検索より小さく、SEEK_GE-キーの最低（最低のキー）は値が検索よりも大きいです。 k1.5が存在しないと仮定します。

 >>> from lsm import SEEK_LE, SEEK_GE >>> #    "k1",    ,   k1.5 >>> db['k1.5', SEEK_LE] '1' >>> #    "k2",    ,   k1.5 >>> db['k1.5', SEEK_GE] '2'
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これらに加えて、LSMは、キー（）、値（）、および更新（）など、他の多くのメソッドもサポートしています。

スライスと反復

SQLite 4 LSMでは、データを直接反復処理するか、キーのサブセットを選択できます。 興味深い点は、キーの範囲を要求すると、その開始と終了が存在しない可能性があることです。 いくつかのキーが欠落している場合、データベースは次のクローズキー（next-closest key）を見つけるためにシークメソッドの1つを使用します。

 >>> [item for item in db] [('foo', 'bar'), ('k0', '0'), ('k1', '1'), ('k2', '2')] >>> db['k0':'k99'] <generator object at 0x7f2ae93072f8> >>> list(db['k0':'k99']) [('k0', '0'), ('k1', '1'), ('k2', '2')]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

特定の方向のすべてのキーを返すには、オープンエンドスライスを使用できます。

 >>> list(db['k0':]) [('k0', '0'), ('k1', '1'), ('k2', '2')] >>> list(db[:'k1']) [('foo', 'bar'), ('k0', '0'), ('k1', '1')]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

上限または下限がキーの範囲外の場合、空のリストが返されます。

 >>> list(db[:'aaa']) [] >>> list(db['z':]) []
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

キーを逆の順序で取得するには、スライスの最初のパラメーターとして一番上のキーを指定するだけです。 開いているスライスを抽出する場合は、ステップパラメーターとしてTrueを指定できます。

 >>> list(db['k1':'aaa']) #  'k1' > 'aaa',      : [('k1', '1'), ('k0', '0'), ('foo', 'bar')] >>> list(db['k1'::True]) #    True    step: [('k1', '1'), ('k0', '0'), ('foo', 'bar')]     <b></b> ,        : >>> del db['k0':'k99'] >>> list(db) # 'k0'   . [('foo', 'bar'), ('k0', '0')]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

シークメソッドの操作の詳細については、 LSM.fetch_range（）のドキュメントをご覧ください。

カーソル

ほとんどの場合、スライスで十分ですが、レコードを検索および表示するプロセスをより細かく制御する必要がある場合があります。

 >>> with db.cursor() as cursor: ... for key, value in cursor: ... print key, '=>', value ... foo => bar k0 => 0 >>> db.update({'k1': '1', 'k2': '2', 'k3': '3'}) >>> with db.cursor() as cursor: ... cursor.first() ... print cursor.key() ... cursor.last() ... print cursor.key() ... cursor.previous() ... print cursor.key() ... foo k3 k2 >>> with db.cursor() as cursor: ... cursor.seek('k0', SEEK_GE) ... print list(cursor.fetch_until('k99')) ... [('k0', '0'), ('k1', '1'), ('k2', '2'), ('k3', '3')]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

カーソルを使用するときは、開いたままにしないでください。 最初に、カーソルを閉じるのに役立つLSM.cursor（）コンテキストマネージャーを使用できます。

取引

SQLite 4 LSMデータベースは、ネストされたトランザクションをサポートします。 これらを使用する最も簡単な方法は、コンテキストマネージャーまたはデコレーターとしても機能するLSM.transaction（）メソッドを使用することです。

 >>> with db.transaction() as txn: ... db['k1'] = '1-mod' ... with db.transaction() as txn2: ... db['k2'] = '2-mod' ... txn2.rollback() ... True >>> print db['k1'], db['k2'] 1-mod 2
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ラップされたブロックを使用してトランザクションを部分的にコミットまたはロールバックすることができ、新しいトランザクションは古い場所から開始されます。

 >>> with db.transaction() as txn: ... db['k1'] = 'outer txn' ... txn.commit() #  . ... ... db['k1'] = 'outer txn-2' ... with db.transaction() as txn2: ... db['k1'] = 'inner-txn' #    . ... print db['k1'] #  "inner-txn". ... txn.rollback() #   txn2     . ... print db['k1'] ... 1 <- Return value from call to commit(). inner-txn <- Printed after end of txn2. True <- Return value of call to rollback(). outer txn <- Printed after rollback.
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

必要に応じて、LSM.begin（）、LSM.commit（）、LSM.rollback（）を明示的に呼び出すことができます。

 >>> db.begin() >>> db['foo'] = 'baze' >>> print db['foo'] baze >>> db.rollback() True >>> print db['foo'] bar
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

性能

これらすべてのベンチマークに耐えることはできませんが、LSMデータベースのパフォーマンスに非常に興味がありました。 したがって、 小さなベンチマークを使用して、SQLite 4 LSMとLevelDB、Berkeley DB、Kyoto Cabinet を比較しました。 良い方法では、Kyoto CabinetとBerkeley DBはビルトインBツリーであり、Kyoto CabinetとLevelDBはデータベースへのプロセスの複数アクセスをサポートしていないため、それらを比較できませんでした。 また、LevelDBにトランザクションサポートがあるかどうかもわかりません。 とりわけ、ベンチマークはデータベースライブラリを直接使用せず、利用可能なPythonドライバーを使用します。 そのため、結果はPythonライブラリのいくつかの制限と機能の影響を受ける可能性があります。



ベンチマーク結果（少ないほど良い）：

 Testing with N = 100000 ------------------------------------ BDBBTree ~~~~~~~~ Writes: 0.469 Reads: 0.479 Range (10%): 0.212 Range (20%): 0.192 Range (40%): 0.185 Range (80%): 0.186 KyotoBTree ~~~~~~~~~~ Writes: 0.208 Reads: 0.203 Range (10%): 0.219 Range (20%): 0.188 Range (40%): 0.188 Range (80%): 0.187 LevelDB ~~~~~~~ Writes: 0.227 Reads: 0.225 Range (10%): 0.031 Range (20%): 0.027 Range (40%): 0.028 Range (80%): 0.027 LSM ~~~ Writes: 0.282 Reads: 0.239 Range (10%): 0.059 Range (20%): 0.052 Range (40%): 0.052 Range (80%): 0.052
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このデータを次のように解釈します。キー範囲を取得する際のバークレーDBと京都内閣のパフォーマンスは、非常に期待されていることが判明しました。 また、LevelDBとLSMは、逆に、範囲を読み取るときにはるかに高速であることが判明し、非常に高速に書き込みます。



LevelDBはSQLite 4 LSMよりも優れていましたが、後者の読み取り範囲はBツリーよりもはるかに高速です。 彼の読書は執筆の4倍遅いことが判明したため、LSMベンチマークを販売する必要があります。 最初は読み取りに問題があると思っていましたが、すべてがフェッチごとにPythonカーソルラッパーにあることに気付きました（）。 PythonコードをC言語APIの直接呼び出しに置き換えた後、読み取り速度が大幅に向上しました。 Python LSMバインダーを試してみたい場合は、バージョン0.1.4以降を使用していることを確認してください。以前のバージョンではfetch（）の実装が非常に遅いためです。

SQLite 4に関する注意

SQLite 4を自分でビルドする場合は、古いリポジトリを複製してコンパイルできます。

 $ fossil clone http://www.sqlite.org/src4/ sqlite4.fossil $ mkdir sqlite4-build $ cd sqlite4-build $ fossil open ../sqlite4.fossil $ ln -s Makefile.linux-gcc Makefile $ export CFLAGS="$CFLAGS -DSQLITE_ENABLE_FTS3=1 -DSQLITE_ENABLE_COLUMN_METADATA=1 -DSQLITE_ENABLE_UNLOCK_NOTIFY -DSQLITE_SECURE_DELETE $ make
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

完了すると、バイナリファイルsqlite4、libsqlite4.aおよびsqlite4.hが作成されます。



また、埋め込みプロセスを簡素化するために、元の結合ファイルの独自のコピーを作成できます。

 make sqlite4.c
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

また、SQLite 4 ...の現在のステータスが不明であることにも注意する必要があります。 Hipp博士は、SQLite 3のサポートを継続する予定であると述べました。 しかし、エンドユーザーの代わりに、4番目のバージョンを試してみます。 おそらく未来は彼女にあるが、事実ではない。 たとえそうだとしても、それは現在の形ではないかもしれません。

追加資料

汚れた詳細が必要な場合、役立つリンクのリストを以下に示します。

• Python LSM-dbドキュメント
• SQLite4 LSMの概要
• 説明LSM C-API
• Quora：「LSMツリーはどのように機能しますか？」
• 私のベンチマークスクリプト

あなたが好きかもしれない私の他の投稿：

• PythonでSQLite JSON1およびFTS5拡張機能を使用する
• PythonでSQLite全文検索を使用する
• 高速で新しいUnQLiteバインディングの概要
• PythonおよびSQLiteリソースの私のリスト

他の組み込みNoSQLデータベースに興味がある場合は、 unqlite-pythonおよびvedis-pythonに注意してください 。 これらはそれぞれMongoDBとRedisに非常に似ており、ラッパー、Cの軽量拡張機能を使用し、Pythonプロジェクトに埋め込むことができます。