順序付きキーバリューストア

順序付きキーバリューストア（OKVS）は、マルチモデルデータベースをサポートできるデータストレージパラダイムの一種です。OKVSは、バイトからバイトへの順序付きマッピングです。OKVSは、キーと値のペアをキーの辞書式順序でソートします。OKVSシステムは、異なる機能セットとパフォーマンスのトレードオフを提供します。それらのほとんどは、別のプロセスに組み込むために、ネットワークインターフェースのないライブラリとして出荷されます。ほとんどのOKVSはACID保証をサポートしています。一部のOKVSは分散データベースです。順序付きキーバリューストアは、 NewSQLデータベースシステム を含む多くの最新のデータベースシステムに採用されています

歴史

順序付きキーバリューストアの起源は、 1979年にケン・トンプソンがdbmで行った研究に遡ります。1991年後半には、キーのソート状態を維持できるBツリーバックエンドを備えたBerkeley DBがリリースされました。Berkeley DBは非常に高速であると言われ、様々な商用製品に採用されました。2.7までPythonの標準ライブラリに含まれていました。[ 1 ] 2009年には、トランザクションと順序付きキーの両方をサポートするKyoto Cabinet に置き換えられたTokyo Cabinetがリリースされました。2011年には、 OpenLDAPでBerkeley DBを置き換えるためにLMDBが作成されました。また、2012年にFacebookによってRocksDBとしてフォークされたGoogleのLevelDBもあります。2014年には、 Berkeley DBの後継であるWiredTigerがMongoDBに買収され、2019年からMongoDBデータベースの主要なバックエンドとなっています

OKVSパラダイムの他の注目すべき実装としては、Sophia [ 2 ]とSQLite3 LSM拡張が挙げられる。OKVSパラダイムのもう一つの注目すべき応用としては、RocksDBをベースにしたArangoDB [ 3 ]と呼ばれるマルチモデルデータベースシステムが挙げられる。

一部のNewSQLデータベースは、順序付きキーバリューストアによってサポートされています。プロパティグラフデータベースであるJanusGraphは、Berkeley DBバックエンドとFoundationDBバックエンドの両方を備えています。

主要な概念

辞書式符号化

基本データ型（ブール値、文字列、数値）とそれらのデータ型の組み合わせを、自然な順序を維持したソートされたコンテナ（タプル、リスト、ベクター）内に符号化するアルゴリズムがあります。バイトを直接操作することなく、順序付けされたキーバリューストアを操作することが可能です。FoundationDBでは、これはタプル層と呼ばれています。[ 4 ]

範囲クエリ

OKVS内ではキーは順序付けされているため、範囲クエリを実行できます。範囲クエリは、指定された2つのキーの間にあるすべてのキーを取得し、取得したキーがソートされた順序で返されることを保証します。

部分空間

キーの構成

より高レベルの抽象化を構築するために、キー空間を構築することができます。その考え方は、最上位レベルのキー空間の順序付けされた性質を利用してキーを構築することです。キー空間の順序付けされた性質を利用することで、特定のパターンを持つキーの範囲を照会することができます

非正規化

非正規化とは、同じデータを複数の部分空間で繰り返すことであり、一般的な手法です。これにより、インデックスとも呼ばれる二次表現を作成でき、クエリを高速化できます

高レベルの抽象化

以下の抽象化またはデータベースは、上位順序付けされたキーバリューストア上に構築されました

  • 時系列データベース
  • レコードデータベース[ 5 ]は行ストアデータベースとも呼ばれ、RDBMSと呼ばれるものと同様の動作をします
  • タプルストアはトリプルストアやクアッドストアとも呼ばれるが、ジェネリックタプルストアとも呼ばれる。[ 6 ] [ 7 ]
  • MongoDB APIを模倣したドキュメントデータベース[ 8 ]
  • 全文検索[ 9 ]
  • 地理情報システム[ 10 ]
  • プロパティグラフ[ 11 ]
  • バージョン管理されたデータ[ 12 ]
  • 近似最近傍法のベクトル空間データベース[ 13 ]

これらの抽象化はすべて同じ OKVS データベースと共存でき、ACID がサポートされている場合は、トランザクション システムによって提供される保証に基づいて操作が行われます。

特徴マトリックス

いくつかの順序付きキーバリューストアの比較
OKVS ライセンス トランザクション 分散 インメモリ 複数のスレッド 複数のプロセス ネストされたトランザクション
Berkeley DBAGPL はい いいえ いいえ はい はい はい
FoundationDBApache はい はい はい はい はい いいえ
京都キャビネットGPL はい いいえ いいえ ？ いいえ いいえ
LevelDBApache いいえ いいえ いいえ ？ いいえ いいえ
LMDBOpenLDAP はい いいえ いいえ はい はい はい
RocksDBApache はい いいえ いいえ はい いいえ いいえ
SQLite（LSM拡張） パブリックドメイン はい いいえ はい はい はい はい
TiKVApache はい はい いいえ はい はい いいえ
TkrzwApache はい いいえ ？ はい いいえ ？
東京内閣LGPL いくつかの いいえ ？ はい ？ ？
WiredTigerGPL はい いいえ はい はい いいえ いいえ

ユースケース

OKVSは、2つの戦略を実装するのに役立ちます。1つは小さな機能を最適化することで、例えば読み取りまたは書き込みのレイテンシを10%改善することです。もう1つの戦略は、FoundationDBとTiKVの分散特性を活用することです。これらの分散特性は、大規模な復元力において同等のものがないため、どちらのユーザーも必要な高レベルの抽象化を再実装する必要があります。複雑さ、保守性、微調整、すぐに利用できる機能のバランスが依然として複雑であり、専門家の選択に委ねられています。場合によっては、より特殊なデータ構造の方が、OKVS上の高レベルの抽象化よりも高速になることがあります

OKVS パラダイムのもう 1 つの魅力は、そのシンプルで多用途なインターフェースにあります。そのため、実験的なストレージ アルゴリズムやデータ構造の興味深いターゲットになります。

参照

参考文献

  1. ^ 「11.11. bsddb — Berkeley DBライブラリへのインターフェース — Python 2.7.17ドキュメント」 . docs.python.org . 2020年1月16日閲覧
  2. ^ 「sophia - 最新のトランザクション対応キー値/行ストレージライブラリ」 . sophia.systems . 2020年1月16日閲覧。
  3. ^ 「新しいRocksDBとMMFilesストレージエンジンの比較」 ArangoDB . 2020年1月16日閲覧。
  4. ^ 「Python API — FoundationDB 6.2」 . apple.github.io . 2020年1月19日閲覧。
  5. ^ FoundationDB上に構築されたレコード指向ストア。、FoundationDB、2020年1月16日、 2020年1月17日取得
  6. ^ 「Generic Tuple Store Database」 . srfi.schemers.org . 2020年1月17日閲覧。
  7. ^「汎用タプルストア」。GitHub 。
  8. ^ MongoDB®ワイヤプロトコルを実装したFoundationDB上のドキュメントデータモデル：FoundationDB/fdb-document-layer、FoundationDB、2019年12月9日、 2020年1月17日取得
  9. ^ meilisearch/MeiliSearch、MeiliSearch、2021年6月19日、 2021年6月19日閲覧
  10. ^ 「6.1. GeoMesa インデックス構造 — GeoMesa 1.3.1 マニュアル」 . www.geomesa.org . 2020年1月19日閲覧。
  11. ^ 「JanusGraph FoundationDBストレージアダプター - Ted Wilmes、Expero Inc」www.youtube.com . 2020年1月17日閲覧。
  12. ^ 「ライトニングトーク：エンティティストア：バージョン管理のためのFoundationDBレイヤー... - Stephen Pimentel、 - YouTube」。www.youtube.com。2020年1月17日閲覧。
  13. ^ meilisearch/arroy、Meilisearch、2024年8月5日、 2024年8月6日閲覧
「 https://en.wikipedia.org/w/index.php?title=Ordered_key–value_store&oldid=1334438801」より取得