Posts

ThriftはFacebookで開発されたRPCライブラリで、IDLからクライアントとサーバのコードを生成する。 Thrift自体は、大きくType, Transport, Protocol, Versioning, Processorの5つのコンポーネントからなる。

発表時期は2007年で、RDBMSの源流のSystem Rが開発された70年代と今日ではハードウェアの性能や価格が変わったことを背景に、RDMSの延長ではなく抜本から刷新し、いわゆるNoSQLを開発する必要性を主張している。 第一著者のMichael Stonebrakerは、後の2011年に今日全てのデータベースの要件をRDMSだけではまかなえないという旨の論文“One Size Fits All”を出している。 One Size Fits Allは以前本ページで紹介したことがある。 表題の論文では、OLTPに特化したデータベースH-Storeを実装し、TPC-Cをベンチマークとして商用データベースと比較したところ、H-Storeの方が82倍高速だった。

Burst trieは、trie木の一種で、2分木よりもメモリ効率がよく、trie木と同じくらい速い。 2種類のデータ構造からなり、trie木に加えて別のデータ構造も使う。 どのデータ構造を使うかは要件次第で、論文では、連結リスト、二分探索木、スプレー木を使った場合の実験がなされた。 Burst trie内の別のデータ構造の箇所はcontainerと呼ばれる。 初期状態のBurst trieは、1つのcontainerからなり、別のデータ構造そのものに等しい。 その後、コンテナ内の要素のアクセス頻度やヒット率にもとづくヒューリスティックな基準が満たされると、containerの要素をtrie木のノードにおきかえ、ノードに下に新しいcontainerをつくる。 新しくできたcontainerにも基準を適用し、適宜おきかえる。 これにより、与えられる文字列の頻度に合わせてtrie木と別のデータ構造を使い分けることができると同時に、性能はデータの歪度に依存する。

接尾辞配列 Suffix Arraysは、長さ\(P\)の文字列が長さ\(W\)の文字列のどこに出現するかを時間計算量\(\mathcal{O}(P + \log N)\)で判定できるデータ構造で、接尾辞木 suffix treeよりもメモリ効率が3-5倍よい。 一方で、検索の準備にかかる最悪時間計算量はsuffix treeよりも大きい。 suffix arrayの構築にかかる最悪時間計算量が\(\mathcal{O}(N\log N)\)に対して、suffix treeは\(\mathcal{O}(N)\)しかかからない。

HyperDexはキー以外の要素で値を検索できるキーバリューストアで、このキー以外の要素による検索速度がCassandraやMongoDBと比べて12-13倍速い。 キーバリューストアは、RDBMSとくらべて、処理速度は速く、検索条件の機能に乏しい。 HyperDexは、要素数と同数の次元からなるユークリッド空間を構成し、要素のハッシュ値で決まる座標に値をおくことで、キー以外でも高速に検索することを可能にする。 もとのドメインの順序関係を保持するハッシュ関数を使うため、範囲検索もあつかえる。

商用DBMS TransBaseのインデックスをB木からUB木に変え、 多次元アクセス（複数の列の範囲を指定するクエリ）を高速化した。 一見、商用DBMSのインデックスの拡張は複雑かつ高コストのように思える。 UB木は、B木をベースにしたインデックスで、B木のキーの生成とページ分割方法を細工し、範囲クエリを高速化できる。 範囲クエリに向きB木に似たUB木を使うことで、既存のDBMSの範囲クエリを人々の想定よりも簡単に高速化できることを例示した。 また、既存のインデックスの拡張用に提供されたインターフェースを使わず、インデックスを置き換えカーネルにUB木を密結合することで、クエリのオプティマイザを継続して利用できた。

データ構造は読み込み(Read, R), 更新(Update, U), 所要メモリ容量(Memory, M)にトリレンマを抱え、いかなるデータ構造でも、2つを最適化すると残る1つのオーバヘッドが悪化すると予想した。 Read, Update, Memoryの頭文字から、これをRUM Conjectureと名付けた。

Fractal Treeは、B+木のルートと節にバッファをもたせるデータ構造にあたる。 そのFractal TreeのamplificationをB+木やLSM Treeのそれと比較した。 議論になるamplificationは、write, read, spaceの3つで、write amplificationはアプリケーションが書き込むデータ量に対して実際にストレージに書き込まれたデータ量を表す。 read amplificationはクエリの実行に必要なI/Oの回数、space amplificationは仕組み上避けられない断片化や一時的なデータのコピーに該当する。

ソートされたシーケンスの直積を高速に求めるアルゴリズム Double Binary Searchを示した。 2つのシーケンス\(D\), \(Q\)があり、\(\mid D\mid=n\), \(\mid Q\mid=m\), \(n >= m\)であれば、平均と最悪時間計算量が、それぞれ、\(\mathcal{O}(m\log(n/m))\), \(m\)になる。 本アルゴリズムは、Web検索エンジンで大きなシーケンスの直積を高速に求めるために開発された。

LSM-Treeは、検索より挿入や削除が多い用途に向いたインデックス構造であり、例えば履歴テーブルやログの保存につかえる。 メモリにある1つ木とディスク上の1つ以上の木からなり、直近の挿入や削除をメモリの木で管理する。 メモリの木の大きさがしきい値を超えたとき、メモリの木の葉をディスクの木に移す。 移動時は、ディスク上の木の葉とメモリの葉をマージソートの要領でソートし、ソートした葉をディスクの新しい連続領域に書き込む。 連続領域に書き込み、アームの移動やディスクの回転を減らすことで、高速に挿入や削除ができる。 一方、検索速度は、複数の木を探索しなければならないために、1つの木でインデックスを構成するB木に劣る。