Slate: Stratified Hash Tree
There is an AI-translated English version.
前書き
現実の階層記憶構造に対して追記とアクセス効率が良く、累積的な構造変化の履歴をすべて保持するハッシュツリー構造である Slate, Stratified Hash Tree を提案します。このデータ構造の設計における核心的要件は以下の 3 点です:
時間的局所性の原理に基づき、最近アクセスされたデータに対する I/O 操作を効率化する構造を持つ。
分散環境におけるトランザクションログのような複数のデータ列を比較し、その差異や分岐位置を高速に特定できる。
永続的データ構造として過去のすべてのバージョンを維持する。
この構造の本質はデータの追加が可能なハッシュツリー (Merkle ツリー) であり、一般的なハッシュツリーと同様に小さなデータ片を用いてデータの破損や改ざんを検証することができます。
この文書の内容は、該当するアルゴリズムに関する論文や書籍が見つけられなかったため、今のところ個人的な研究です。要素の追加によりノードの積層が成長してゆく構造的特徴から、この構造を Stratified Hash Tree (層様のハッシュツリー) と名付けています。
具体的な実装は https://github.com/torao/stratified-hash-tree を参照してください。
Table of Contents
- 前書き
- 概要
- 1. 導入
- 2. 関連研究
- 3. 予備知識と定義
- 4. Slate データ構造
- 5. 操作とアルゴリズム
- 6. 複雑性の解析
- 7. 実装上の考慮
- 8. アプリケーション
- 9. 実験的評価
- 10. 議論
- 11. 結論
- References
概要
1. 導入
Stratified Hash Tree (層様ハッシュツリー) または Slate は追記効率の良い構造を持つ部分的永続性データ構造 (partial persistent data structure) のハッシュツリー (Merkle ツリー) である。トランザクションログやブロックチェーンのようにインクリメンタルに増加する一つの数値 \(i\) によって特定される、改ざん検出や分岐検出といった検証可能なデータを連結するリスト構造に向いている。このデータ構造の直列化形式は非常にシンプルであり、SSD のような二次記憶装置上のファイル (ブロックデバイス) で効率的に表現することができる。データの追加操作はファイルの追記のみで完結するため非常に高速である。
Slate は本質的に完全二分木ではないが、葉ノードの追加により Slate が内包する完全二分木の部分構造を成長させ連結することによって、木構造全体の大半のノードが完全二分木の特性を持っている。Figure 1 に示す図は Slate に 1 から 16 までのデータを追加するときの概念上の木構造の成長と、その直列化された形式を示している。
Figure 1 が示すように、Slate の直列化表現は追加のみの操作であることからファイル操作に対して高速である。また、任意の時点の木構造を完全な履歴として保持していることから、過去のある時点を基準としたデータ要求であっても正しいハッシュツリーで応答することができ、またロールバック操作と末尾置換操作も容易である。これらの操作をサポートする場合、Slate は純粋な append-only ではなくなるが、操作の大部分が追記であることを前提に設計されている。この意味で「追記最適化」という表現を用いる。
Slate は以下の特徴を持つ。
Persistent append-based growth list with verifiable hash tree. Slate はハッシュツリーによって管理されるデータ構造である。時系列データのように高頻度の追加が行われる用途に最適化されており、データ構造レベルで部分的永続性 (partial persistent) である。通常のハッシュツリーと同様に、データの差異や破損、改ざんの有無を検出したり、またその位置を特定するために使用できる。
Append-optimized serialization with history revision support. ファイルのようなブロックデバイスに対する直列化形式をサポートし、特に追記に最適化されている。また、あるバージョンへのロールバック (切り詰め; truncate) と、それ以降を新しく追加する後方置換 (suffix replacement) 操作をサポートする (データ構造は永続的だが直列化形式はこのような変更の可能性がある点に注意)。
Multi-versioned data structure. この木構造は永続的であり、過去の構造の完全な履歴が保存されている。このためデータの追加によってツリーが成長したとしても過去の任意の時点の木構造を再現することができる。必要に応じて過去の特定のバージョンへの巻き戻し、そこから再開することができる。
Assign efficiency to more recent data. Slate の直列化形式は、より最近追加されたデータのアクセス効率が高くなるような局所性を持つように設計されている。最も最新のデータは \(O(1)\) の I/O 操作 (seek + read) でアクセスでき、最も古いデータ、つまり最悪ケースであっても \(O(\log n)\) の I/O 操作でアクセスできる。これは、最近追加されたデータの方が古いデータより頻繁にアクセスされるという現実的な特性に適合している。
Strength of safety over time. 認証パスのレベル (ルートノードからの距離) を安全性の強度と考えたとき、ハッシュツリーとしての安全性は長期間存在する要素と新しく追加された要素とで非対称的である。ある要素の強度は、別の要素が追加されるたびに対数で増加し、全体が完全二分木となったときすべての要素が通常のハッシュ木と同等の信頼性を持る。これはブロックの追加によって過去のブロックの信頼性 (確定性) が増すブロックチェーンと類似した特性である。
Slate の基本的な操作は追加 (append) と取得 (get) である。拡張として範囲取得 (scan) がある。これらの操作のみに限り直列化形式も永続的で並行読み取りが容易に実装できる。オプションとして truncate と suffix replacement が可能である。delete はハッシュ値のみを残して論理削除を行うことができるが、そのハッシュ値の信憑を検証する手段が失われる。
2. 関連研究
Stratified Hash Tree は複数の確立された研究領域の概念を統合した新しいデータ構造である。これは、基盤領域として、永続データ構造、ハッシュベースの完全性検証、層様データの局所性を引用し、その応用領域として分散バージョン管理システムは実用的な同期要件と解決手法を明らかにしている。
本セクションでは、これらの各研究領域における Stratified Hash Tree の理論的位置付けを明確にし、既存手法との比較を通じて本研究の独自性と貢献を示す。
2.1. 永続性とバージョン付けされたデータ構造
永続データ構造の理論は、データの複数バージョンへの効率的なアクセスを可能にする。永続的データ構造は Driscoll ら [5] によって体系的に研究された。この論文では、変更時に履歴を失う一過性 (ephemeral) 構造と、その後のアクセスのために維持される永続的 (persistent) 構造を区別している。彼らの研究は、任意のデータ構造に対する汎用的な永続化手法に焦点を当てたもので、ファットノード方式とノードコピー方式の 2 つの基本的な手法を導入した。一方で、我々の Stratified Hash Tree は、部分的永続性の特徴を提供する木構造上の追記にのみ注目している。また、バージョンスタンプや複数のポインタを注意深く管理する必要がある一般的なノードコピー方式とは異なり、Stratified Hash Tree は各エントリ \(e_i\) が更新操作 \(i\) の間に作成されたすべてのノードを含む階層構造によってシンプルに永続性を実現する。この設計上の選択により、我々の Slate からは複雑なポインタ管理の必要性が排除される。さらに、Slate の追記のみという特性は、分散トラザクションログやブロックチェーンのような不変性と効率的な検証が重要となる最近のアプリケーションによく適合している。Driscoll らの手法のように明示的なバージョンポインタを保持するのではなく、Stratified Hash Tree はその層様構造によってバージョン情報を暗黙的にエンコードし、時間的局所性が空間的局所性として自然に保持される。
2.2. ハッシュベースの完全性と時間的構造
ハッシュ関数を用いたデータの完全性の保証は Merkle [6] によって公開鍵暗号システムのプロトコルとして最初に提案された。これは Merkle ツリーと呼ばれ、葉ノードにデータのハッシュ値を配置し、中間ノードに子ノードのハッシュ値を再帰的に格納することで、効率的な完全性検証を可能にする。この基本構造は、後にデジタル署名システム [7] や様々な分散システムで広く採用されることとなった。
時間的要素をハッシュベース構造に組み込む研究は Haber と Stornetta [2] のデジタル文書タイムスタンプに研究まで遡る。彼らは文書のハッシュ値を時系列で連鎖させることで、文書の存在時刻を証明可能にした。この手法は Bayer ら [8] によってハッシュツリーベースの改良が加えられ、複数文書の効率的なタイムスタンプが実現された。
より厳密な理論的基盤は Buldas と Saarepera [8] によって確立された。彼らはハッシュカレンダーの概念を提案し、append-only データベースに 1 秒ごとに 1 つのハッシュ値を追加することで時間の経過を測定する手法を開発した。この構造は特殊な Merkle ツリーと位置づけられ、任意の時点でツリーが 1970 年 1 月 1 日からの各秒に対応するリーフノードを含むという性質を持つ。Buldas ら [9] はこの手法を Universally Composable タイムスタンプスキームとして実用化し、信頼できる第三者への依存を最小化したシステムを構築した。
これらの既存手法は、いずれもハッシュベースの完全性保証と時間的要素の組み合わせという重要な基盤を提供している。しかし、分散トランザクションログの効率的な同期という観点では以下の限界がある。
Merkle ツリーは優れた完全性検証機能を提供するが、時間的局所性を考慮した構造最適化は行われていない。すべてのリーフノードが等価に扱われるため、最近追加されたデータへの高頻度なアクセスパターンを活用できない。また、新しいデータの追加時にはツリー全体の再バランスが必要になる場合があり、append-only 環境での効率性に課題がある。特にデータ個数が \(2^i\) でない場合には空欄ノードや特別な埋め込み値を持つ葉ノードを作成する必要があり、これが実装の複雑さを増すとともにストレージ効率の低下を招く。
ハッシュカレンダーは時間的順序付けされた append-only 木構造として優れており、実際、本文書で提案する Stratified Hash Tree と最も類似したデータ構造である。両者は左から右へ葉ノードを順次追加し、一過性ノードによる完全二分木の連結を通じて上位レベルのノードを段階的に構築するという共通の木成長パターンを採用している。しかし、ハッシュカレンダーがタイムスタンプと時間的完全性の検証に焦点を当てているのに対し、本文書の Stratified Hash Tree は分散システムにおける効率的な差分検出という異なる問題に取り組んでいる。具体的には、ハッシュカレンダーの各秒に固定的に 1 つのハッシュ値を配置する設計は、不規則な更新頻度を持つトランザクションログには適さない。さらに、異なる更新頻度を持つ複数のデータ列間での効率的な差分検出や、ツリーの直列化表現とデータ局所性、時間的最適化については議論されていない。
これに対して本文書で提案する Stratified Hash Tree は、これらの既存手法の利点を継承しつつ、分散トランザクションログ同期に有利な最適化を導入している。具体的には、時間的局所性を活用した階層構造により最近のデータへの高速アクセスを実現し、append-only 特性を保持しながら効率的な差分検出を可能にしている。また、不規則な更新パターンに対応するために適応的な階層管理機能を提供し、既存の Merkle ツリーやハッシュカレンダーでは実現困難であった実用的な分散同期性能を達成している。
2.3. 層様データ構造
層化 (stratification) による最適化は、データの特性や使用パターンに応じて複数の階層を設けることで、全体的な性能向上を図る設計手法である。この概念は、メモリ階層の原理に基づき、アクセス頻度や時間的局所性の違いを活用してシステム効率を改善する。
Stratified B-Tree は 2011 年に Twigg らによって提案された、バージョン付けされた辞書のためのデータ構造である [Twigg et al., 2011]。これは Copy-on-Write B-Tree の非効率性を解決することを目的として開発された。Stratified B-Tree は Key-Value ペアを配列の層に配置することで、更新と範囲クエリー時のシーケンシャル I/O を可能にし、同時に不要な重複を避けるための密度を維持する。積層するデータ構造という意味で本文書の Stratified Hash Table と類似しているが、両者は層化の軸が根本的に異なる。Stratified B-Tree が独立して管理されるバージョン空間として層を使用するのに対し、我々の Stratified Hash Tree は時間的順序を分離し、時間的局所性を持つ単位として層を使用する。ただし、Stratified Hash Tree においても層はバージョンとして利用できる点で概念的類似性がある。
LSM-Tree (Log-Structured Merge Tree) [1] は、書き込み集約的なワークロードに最適化された層様データ構造である。LSM-Tree は、メモリ上の構造 (memtable) とディスク上の複数のレベルの構造 (SSTable) を組み合わせて書き込み操作を効率化する。新しいデータは最初メモリ内構造に追加され、一定のサイズに達するとディスク上の下位レベルにフラッシュされる。定期的なコンパクション処理により、複数のレベル間でデータがマージされ、重複の除去と空間効率の最適化が行われる。この階層化アプローチは、Cassandra, HBase, RocksDB などの現代の NoSQL データベースで広く採用されている。LSM-Tree の層の概念は、本文書の Stratified Hash Tree とは書き込み最適化と層管理という点で共通するが、LSM-Tree が主にストレージ効率と書き込み性能に焦点を当てているのに対し、Stratified Hash Tree は差分検出と同期効率に最適化されている。
階層型ストレージ管理 (hierarchical storage management) の概念は、ストレージシステムにおいてデータのアクセス頻度や重要度に応じて異なる性能特性を持つストレージ階層にデータを配置する手法である。高速だが高コストで容量の小さい SSD から、低速だが低コストで大容量の HDD やテープストレージまで、複数の階層を組み合わせてコスト効率と才能のバランスを最適化する。この階層化の原理は、時間的局所性と空間的局所性を活用し、頻繁にアクセスされるデータを高速階層に、アーカイブデータを低速階層に配置することで全体効率を向上させる。
これらの既存の層様データ構造は、いずれも階層化による効率化という共通の設計思想を持つが、それぞれ異なる問題領域に特化している。Stratified B-Tree はバージョン管理辞書、LSM-Tree は書き込み集約型ストレージ、階層型ストレージはコスト効率的な大容量ストレージを主な対象とする。本文書の Stratified Hash Tree は、これらの階層化概念を時間的局所性が空間的局所性となるように転換し、append-only 環境で最近のデータのアクセス効率を向上する最適化を提供している。
2.4. トランザクションログと分散バージョン管理の同期
分散環境における効率的なデータ同期と一貫性保証は、現代の分散システムにおける根本的な課題である。この分野では、コンセンサスアルゴリズム、分散バージョン管理、差分同期技術、そして分散台帳技術が相互に関連し合いながら発展してきた。
Raft は分散システムにおけるコンセンサスをを実現するためのアルゴリズムとして Paxos アルゴリズムの代替として設計された [Ongaro & Ousterhout, 2014]。これは複雑性の排除によって Paxos より理解しやすく設計されており、形式的に安全性が証明されている。Raft はリーダーアプローチによってコンセンサスを実装し、クラスタで選出された唯一のリーダーが他のサーバとのログレプリケーションを管理する責任を負っている。TiDB や YugabyteDB のような現代的な分散 SQL データベースでは、各データ単位は Raft を使用して他のノードにレプリケートされる。リーダー選出、ログレプリケーション、コミット処理という一連のプロセスにより、ノード障害やネットワーク分断下でもデータの一貫性が保証される。
Raft でリーダー交替が起きたとき、フォロワーのログが新しいリーダーのログとどこまで同期しているかを知るために、ログの末尾から 1 つずつ比較する。この手法は簡単だが、最悪ケースで \(O(n)\) となるログ全体の線形操作が必要となる場合があり、大規模なログでは性能の問題となる可能性がある。
Git は分散バージョン管理システムの実用的な実装例である。Git では、リポジトリの履歴が DAG (Directed Acyclic Graph) 構造として表現され、各コミットが親子ミットへのポインタを持つ。ブランチの分岐点検出は git merge-base アルゴリズムによって実現されていて、2 つのブランチの共通祖先 (最低共通祖先: LCA) を特定する。rebase 操作時には、Git は DAG 内で 2 つのブランチの共通祖先を見つけ、一方のブランチの各コミットからの変更をもう一方のブランチの上に適用する。しかし、この手法はブランチ後方からの線形探索で分岐点を検出する。
差分同期 (Delta Synchronization) の代表例である rsync アルゴリズムは効率的な差分転送の基盤技術である [Tridgell, 1999]。rsync はファイル内で変更された部分のみを同期することでネットワーク帯域幅の占有を最小化する。これは、クライアントとリモートサーバの両方でファイルをチャンクに分割し、それらのチェックサム交換することで差分のみの転送を行うことができる。このアプローチは効率的だが、ファイル単位での処理に限定され、構造化されたデータの階層的な差分検出には適していない。
ブロックチェーンの軽量クライアントはハッシュベース検証がもたらす軽量化の重要な例である。Bitcoin の Simplified Payment Verification (SPV) では、クライアントはすべてのブロックではなくブロックヘッダのみをダウンロードし、Merkle 証明に依存してトランザクションを検証する。SPV クライアントがトランザクションを必要としたとき、フルノードから取得した特定のトランザクションがブロックに含まれていることを証明するために Merkle 証明を要求ル。これらの値をハッシュ化し、ブロックヘッダ内の Merkle ルートと比較することでトランザクションがブロックの一部であることを確認でキス。しかし、SPV は主に包含の証明に特化しており、複数のノード間での効率的な差分同期機能は提供されていない。
これらの既存手法は、それぞれ特定の同期要件や検証要件に対して解決策を提供しているが、分散トランザクションログの効率的な差分検出という共通の観点を持ちながら限界がある。Raft や Git の線形探索は直感的だが、大きな履歴に対して非効率になる可能性がある。rsync のファイルレベル同期はブロックデバイスに特化されており構造化データには適していない。ブロックチェーンの軽量クライアントの検証は単発的で、継続的な差分追跡には最適化されていない。
本文書で提案する Stratified Hash Tree はこれらの制約を解決する可能性を持っている。時間的局所性を活用した階層構造により、Raft のログ同期や Git の分岐点検出では最悪ケースで \(O(\log n)\) の効率化が期待できる。また rsync では階層的差分検出により従来のブロックレベル同期を超えた精度を実現し、ブロックチェーン環境では連続的なブロック検証における計算量の削減が見込まれる。これらの改善により、既存手法と比較した性能向上が期待される。
トランザクションログやコミットグラフ上の分岐点検出は、表面的には最小共通祖先 (LCA) 問題と類似している。しかし、従来の LCA アルゴリズム [Harel & Tarjan 1984, Schieber & Vishkin 1988, Binary Lifting] はグラフ構造が明らな状況でインデックスを構築し、各ノードの構造的関係を高速に検索することを目的としている。一方で、分散システムにおける実際の問題は、異なるマシン上で作成したデータ系列の整合性を検証しながら双方の分岐点を遠隔で特定することである。Slate は、このような分散かつ動的特性を持つ環境に特化して設計されている。これは、従来の LCA 研究が扱う共通祖先問題とは根本的に異なる問題設定であるため、本文書では追記最適化ハッシュツリーとしての独自の貢献に焦点を当てる。
3. 予備知識と定義
4. Slate データ構造
Stratified Hash Tree はその多くの領域を完全二分木が占める二分木である。本文書では \(n\) 個のユーザデータ (葉ノード) を含む Slate の木構造全体を \(T_n\)、あるノード \(b\) が木構造 \(T\) に含まれていることを便宜的に \(b \in T\)、\(T_1\) が \(T_2\) の部分木であることを \(T_1 \subseteq T_2\) と表記する。また、特に \(T_n\) の成長過程に注目するとき \(n\)-th 世代と表現する。
Slate は部分構造として含まれている一つ以上の完全二分木を統合しながら成長する。また木構造の大半が完全二分木であることから、完全二分木に近い特性を持つ。したがって Slate の特徴を活用するには木構造全体から完全二分木を判定する方法が重要である。ここでは Slate 構造の現実的な操作に必要な数学的背景を記述する。
4.1. ノード
ユーザデータは Slate の葉ノードに格納される。ここで \(i \in \{1,2,\ldots\}\) をユーザデータのインデックスとし、Slate に \(i\) 番目に追加された葉ノードを \(b_i\) と表す (またはより一般化して \(b_{i,0}\) と表記することもできる)。
既存の木構造 \(T_{i-1}\) に \(i\) 番目の葉ノード \(b_i\) を追加するときに発生する中間ノードを \(b_{i,j}\) と表記する。ここで \(j \in \{1,2,\ldots\}\) は \(b_{i,j}\) をルートノードとする部分木を考えたときに最も遠い葉ノードまでの距離 (高さまたは深さ) を表している。したがって木構造全体で最も大きい \(j\) を持つノードはそのルートノードである。また、任意の \(b_{i,j}\) をルートノードとする部分木において \(j\) が最も大きくなるケースはその部分木が完全二分木のときであることから、ルートノードの取る \(j\) の最大値は \(\lceil \log_2 i \rceil\) である。ここで \(j=0\) を持つ単一の葉ノードも部分木とみなすことに注意。\[ \begin{equation} i \in \{1,2,\ldots\}: 0 \le j \le \lceil \log_2 i \rceil \label{ij} \end{equation} \]
式 (\(\ref{ij}\)) は、現実的な実装において \(i\) の定義域を 64-bit 整数としても \(j\) の取りうる最大値は高々 64 であることを意味している。
Figure 1 ですみれ色と薄いグレーで示しているように、中間ノードには 2 つの種類がある。一つはその中間ノードをルートとする部分木が完全二分木のケースで、これは永続性 (persistent) を持ち \(i\)-th 世代以降のすべての木構造でも顕在する。もう一つは完全二分木でないケースで、これは他の完全二分木の部分木を接続するために設置された \(i\)-th 世代でのみ現れる一過性 (ephemeral) の中間ノードである。一過性の中間ノードは、説明を簡略化するために Figure 1 では消去しているが、直列化形式の中では常に存在しており、その木構造はいつでも復元することができる。
ある中間ノード \(b_{i,j}\) が左枝に \(b_{i_\ell,j_\ell}\)、右枝に \(b_{i_r,j_r}\) を接続していることを示すために \(\underset{(i_\ell,j_\ell)(i_r,j_r)}{b_{i,j}}\) と表記する。
4.2. 完全二分木の判定
木構造 \(T_n\) に含まれるあるノード \(b_{i,j}\) をルートとする (葉ノードまでを含む) 部分木を \(T_{i,j} \subseteq T_n\) とする。\(i,j\) に対して式 (\(\ref{pbt}\)) が成り立つような整数 \(\alpha\) が存在するならば、この部分木構造 \(T_{i,j}\) は完全二分木 (perfect binary tree) である。\[ \begin{equation} i = \alpha \times 2^j \label{pbt} \end{equation} \] ここで \(\alpha \ge 1\) は同一の高さ \(j\) を持つ完全二分木 \(T_{*,j} \subseteq T_n\) の中で先頭から何番目の部分木かを意味している。\(T_{i,j}\) が完全二分木であることを意図しているとき \('\) (prime) を付けて \(T'_{i,j}\) と表記し、同様に完全二分木となる部分木のルートノードを意図しているとき \(b'_{i,j}\) と表記する。また式中では完全二分木となる部分木を \({\rm PBST}\) (perfect binary subtree) と表記する。
実装では式 (\(\ref{pbt}\)) から導かれる式 (\(\ref{pbst}\)) を使って添字のビット演算のみで \(T_{i,j}\) が完全二分木かを判断することができる。\[ \begin{equation} \begin{cases} i \equiv 0 \pmod{2^j} & \quad \text{If $T_{i,j}$ is a PBST} \\ i \not\equiv 0 \pmod{2^j} & \quad \text{Otherwise} \end{cases} \label{pbst} \end{equation} \] ここで整数 \(x\), \(y\) に対する \(x \bmod 2^y\) はビット演算子を用いて x & ((1 << y) - 1) と表現することができる。また \(j=0\) であれば式 (\(\ref{pbst}\)) は必ず true となることは明らかであるから任意の葉ノード \(b_i = b_{i,0}\) は完全二分木と等価である。
4.3. 独立した完全二分木の列挙
\(n\) 個の葉ノードを含む (\(n\)-th 世代の) 木構造 \(T_n\) が内包する、独立した (互いに部分構造ではない) 完全二分木を列挙する方法について考える。
このような完全二分木は左から順に、その位置から右に位置する葉ノードを使って構築できる最大の完全二分木となるように並んでいる (余った葉ノードは次の完全二分木の「材料」になる)。そして、\(x\) 個の葉ノードを使って構築できる最大の完全二分木は高さ \(j=\max\{j\in\mathbb{Z}\mid 2^j\le x\}\) で \(2^j\) 個の葉ノードを持つことから、以下のようなアルゴリズムで求めることができる。ここで \(\mathcal{B}'_n\) を \(T_n\) に含まれる独立した完全二分木のルートノードの集合とする。
| 1. | \( {\bf function} \ {\rm pbst\_roots}(n:{\it Int}) \to {\it Sequence}[{\it Node}] \) | |
| 2. | \( \hspace{12pt}x := n \) | |
| 3. | \( \hspace{12pt}\mathcal{B}'_n := \emptyset \) | |
| 4. | \( \hspace{12pt}{\bf while} \ x \ne 0 \) | |
| 5. | \( \hspace{24pt}j = \max \{j \in \mathbb{Z} \mid 2^j \le x\} \) | |
| 6. | \( \hspace{24pt}\mathcal{B}'_n := \mathcal{B}'_n \mid\mid b'_{n-x+2^j,j} \) | // \(b'_{n-x+2^j,j}\) は完全二分木となる部分構造のルート |
| 7. | \( \hspace{24pt}x := x - 2^j \) | |
| 8. | \( \hspace{12pt}{\bf return} \ \mathcal{B}'_n \) | |
ここで \(\mid\mid\) を順序集合 (リスト構造) を連結する演算子とする。Algorithm 1 から得られる \(m\) 個の完全二分木のルートノード集合を \(\mathcal{B}'_n=(b'_{i_1,j_1},\ldots,b'_{i_m,j_m})\) とする。これらは配置上の左から順序付けられているため \(i_1 \lt \ldots \lt i_m\) である。また左に位置する完全二分木がより高いという性質を持つことから \(j_1 \gt \ldots \gt j_m\) である。
4.4. 一過性ノードの列挙
Slate における一過性の中間ノードは、\(T_n\) の部分木である独立した完全二分木のルートノードを右から接続したものである。したがって独立した完全二分木を列挙することで一過性の中間ノードも列挙することができる。
Algorithm 1 より得られる \(m\) 個の完全二分木のルートノード集合 \(\mathcal{B}'_n\) に対して、それらを接続する一過性の中間ノードは \(\mathcal{B}_n=(b_{n,j_1+1},\ldots,b_{n,j_{m-1}+1})\) となる。ここで、左から \(k\) 番目に位置する任意の一過性中間ノードは式 (\(\ref{ephemeral_node}\)) のように表される。\[ \begin{equation} \left\{ \begin{array}{ll} \underset{(i_k,j_k)(n,j_{k+1}+1)}{b_{n,j_k+1}} \ \ & (k \lt m - 1) \\ \underset{(i_k,j_k)(i_m,j_m)}{b_{n,j_k+1}} \ \ & (k = m - 1) \end{array} \right. \label{ephemeral_node} \end{equation} \] 式 (\(\ref{ephemeral_node}\)) で表される一過性中間ノードは、左枝に完全二分木の \(b'_{i_k,j_k}\)、右枝に一過性ノード \(b_{n,j_{k+1}+1}\) または右端の完全二分木 \(b'_{i_m,j_m}\) を接続し、\(n\)-th 世代で一過性の中間ノードであるため \(i=n\)、右枝に接続する二分木より左枝に接続する二分木の方が必ず高いため \(j=j_k+1\) となることを意味している。Algorithm 2 は一過性の中間ノードを生成するアルゴリズムである。
| 1. | \( {\bf function} \ {\rm ephemeral\_nodes}(n:{\it Int}) \to {\it Sequence}[{\it Node}] \) | |
| 2. | \( \hspace{12pt}\mathcal{B}'_n := {\rm pbst\_roots}(n) \) | // Algorithm 1 |
| 3. | \( \hspace{12pt}\mathcal{B}_n := \emptyset \) | |
| 4. | \( \hspace{12pt}{\bf for} \ x := {\rm size}(\mathcal{B}'_n)-1 \ {\bf to} \ 1 \) | |
| 5. | \( \hspace{24pt}i = n, \) | |
| 6. | \( \hspace{24pt}j = \mathcal{B}'_n[x].j+1 \) | |
| 7. | \( \hspace{24pt}left = \mathcal{B}'_n[x-1] \) | |
| 8. | \( \hspace{24pt}right = \mathcal{B}_n[0] \ {\bf if} \ x \ne {\rm size}(\mathcal{B}'_n)-1 \ {\bf else} \ \mathcal{B}'_n[x] \) | |
| 9. | \( \hspace{24pt}\mathcal{B}_n := b \{i, j, left, right\} \ \mid\mid \ \mathcal{B}_n \) | |
| 10. | \( \hspace{12pt}{\bf return} \ \mathcal{B}_n \) | |
この木構造の構築手順から、任意のノード \(b_{i,j} \in T_n\) の左右の枝に接続されているノード \(b_{i_l,j_l}\) と \(b_{i_r,j_r}\) について考えたとき、Slate のノードは以下の自明な性質を持っている。
性質 1: 任意のノード \(b_{i,j} \in T_n\) の左枝に接続されているノード \(b'_{i_l,j_l}\) を頂点とする部分木は完全二分木である。また、右枝に接続されているノード \(b_{i_r,j_r}\) を頂点とする部分木は完全二分木の可能性がある。
性質 2: 任意のノード \(b_{i,j} \in T_n\) の左枝に接続されているノード \(b_{i_l,j_l}\) の高さは \(j_l = j - 1\) である。
性質 3: 任意のノード \(b_{i,j} \in T_n\) の右枝に節即されているノード \(b_{i_r,j_r}\) のインデックスは \(i_r = i\) である。またこの性質を再帰的に考慮すると、任意のノードの右枝を葉ノードまでたどる一連のノードは同じ \(i\) の値を持つ。
また Algorithm 1 と Algorithm 2 に基づいて \(n\) から集合 \(\mathcal{B}'_n\) と \(\mathcal{B}_n\) を求めるスクリプトを以下に示す。
\(n\)-th 世代の \(T_n\) に対して行う操作は \(\mathcal{B}'_n\) と \(\mathcal{B}_n\) に含まれるノードを頻繁に参照するためこれらはメモリ上にキャッシュしておくと良いだろう。
4.5. インデックス
Slate はデータを \(2^j\) ずつのグループに分割する階層構造の性質がある。世代 \(n\) において完全に埋まっているグループは、対応する部分木が完全二分木であることを意味する。例えば、高さ \(j=2\) では容量 4 のグループとなり、\(n=11\) に対して 2 つのグループが完全に埋まり 1 つのグループが埋まっていない。\[ \begin{array}{lll} {\rm Group}_1 & = & (1, 2, 3, 4) & \quad \text{completely filled (PBST)} \\ {\rm Group}_2 & = & (5, 6, 7, 8) & \quad \text{completely filled (PBST)} \\ {\rm Group}_3 & = & (9, 10, 11, \_) & \quad \text{not completely filled (not PBST)} \end{array} \] これを木構造で表すと Figure 2 のようになる。
4.5.1 任意の部分木に含まれる葉ノード数
任意のノード \(b_{i,j}\) を頂点とする部分木 \(T_{i,j}\) に含まれる葉ノードの数 \(r_{i,j}\) を求める。まず、部分木 \(T'_{i,j}\) が完全二分木の場合 (\(i \equiv 0\pmod{2^j}\))、\(T_{i,j}\) に対応する \(\frac{i}{2^j}\) 番目のグループが満杯であり、各グループは容量 \(2^j\) を持つことから \(r'_{i,j}=2^j\) である。
次に部分木 \(T_{i,j}\) が完全二分木ではない場合 (\(i \not\equiv 0 \pmod{2^j}\))、つまり一過性ノード \(b_{i,j}\) をルートとしている場合、木は \(\lfloor \frac{i}{2^j}\rfloor\) 番目のグループに対応しており、その前には \(\lfloor\frac{i}{2^j}\rfloor\) 個の満杯のグループが存在している。したがって \(r_{i,j}=i-\lfloor\frac{i}{2^j}\rfloor\times 2^j\) となる。\[ \begin{equation} \begin{cases} r'_{i,j} & = & 2^j & \quad i \equiv 0 \pmod{2^j} \\ r_{i,j} & = & i - \left\lfloor\frac{i}{2^j}\right\rfloor \times 2^j & \quad i \not\equiv 0 \pmod{2^j} \end{cases} \label{r_cases} \end{equation} \]
完全二分木のケースにおいて、\(i \equiv 0 \pmod{2^j}\) は \(i = q \times 2^j\) となるような整数 \(q \ge 1\) が存在することを意味している。また \(q-1\) は一つ前のグループの番号を表しているため \(q-1=\lfloor \frac{i-1}{2^j} \rfloor\) である。したがって \(r'_{i,j}\) は式 (\(\ref{r_pbst}\)) のように変形できる。\[ \begin{eqnarray} r'_{i,j} & = & 2^j = q \times 2^j - (q - 1) \times 2^j \nonumber \\ & = & i - \left\lfloor\frac{i-1}{2^j}\right\rfloor \times 2^j \label{r_pbst} \end{eqnarray} \] また \(i \not\equiv 0 \pmod{2^j}\) では \(\lfloor\frac{i}{2^j}\rfloor = \lfloor\frac{i-1}{2^j}\rfloor\) であるため、\(r_{i,j}\) も式 (\(\ref{r_ephemeral}\)) のように変形できる。\[ \begin{eqnarray} r_{i,j} & = & i - \left\lfloor \frac{i}{2^j} \right\rfloor \times 2^j \nonumber \\ & = & i - \left\lfloor \frac{i-1}{2^j} \right\rfloor \times 2^j \label{r_ephemeral} \end{eqnarray} \] これにより、式 (\(\ref{r_cases}\)) におけるケース分岐は式 (\(\ref{r_pbst}\), \(\ref{r_ephemeral}\)) に統合することができる。ここで \(\lfloor\frac{i-1}{2^j}\rfloor\) は \(T_{i,j}\) より前に存在するグループの個数を表している。
一般に、任意の整数 \(a\), \(b\) (\(b\gt 0\)) に対して \(a = \lfloor\frac{a}{b}\rfloor \times b + (a \bmod b)\) であることから、\(a=(i-1)\) を適用すると式 (\(\ref{r}\)) が得られる。\[ \begin{eqnarray} r_{i,j} & = & i - \left\lfloor \frac{i-1}{2^j} \right\rfloor \times 2^j \nonumber \\ & = & ((i - 1) \bmod 2^j) + 1 \label{r} \end{eqnarray} \] この式 (\(\ref{r}\)) により、任意のノード \(b_{i,j}\) に含まれる葉ノードの数 \(r_{i,j}\) は、完全二分木か一過性ノードかにかかわらず統一的に計算できる。
4.5.2. 部分木のカバー範囲
任意の部分木 \(T_{i,j} \subseteq T_n\) に含まれている葉ノードのインデックス範囲 \([i_{\rm min}, i_{\rm max}]\) について考える。性質 3 より、最大のインデックスが \(i_{\rm max} = i\) であることは明らかであるため、最小のインデックス \(i_{\rm min}\) に注目する。
高さ \(j\) を持つ部分木 \(T_{i,j}\) より前には、\(T_{i,j}\) が完全二分木かどうかにかかわらず、同じ高さ \(j\) を持つ部分木 (完全二分木) \(T'_{i',j}\)、\(i' \lt i\) が \(\lfloor\frac{i-1}{2^j}\rfloor\) 個存在する。高さ \(j\) の完全二分木は \(2^j\) 個の葉ノードを含んでいることから、\(T_{i,j}\) の最小のインデックス \(i_{\rm min}\) は \(T_{i,j}\) より前に存在する葉ノードの総数 + 1 と考えることができる。\[ \begin{equation} \left\{ \begin{array}{lcl} i_{\rm min} & = & \left\lfloor \frac{i-1}{2^j} \right\rfloor \times 2^j + 1 = i - ((i-1)\bmod 2^j) \\ i_{\rm max} & = & i \end{array} \right. \label{subtree_range} \end{equation} \] 式 (\(\ref{subtree_range}\)) より、\(T_{i,j}\) に含まれる葉ノードの数は \(i_{\rm max}-i_{\rm min}+1=r\) で式 (\(\ref{r}\)) と一致する。また \(T_{i,j}\) に隣接する「左隣りの部分木の最大の葉ノード」と「右隣りの部分木の最小の葉ノード」も算出することができる。この考え方は中間ノードの接続の説明で使用する。
ここで整数 \(x\), \(y\) に対する \(\lfloor\frac{x}{2^y}\rfloor\) はビット演算子を用いて x >> y と、同様に \(x \times 2^y\) は x << y と表現することができる。
4.5.3. 左右のノードのインデックス
任意のノード \(b_{i,j} \in T_n\) の左右の枝に接続されているノード \(b_{i_l,j_l}\) と \(b_{i_r,j_r}\) について考える。性質 2 と性質 3 から \(j_l = j-1\) と \(i_r=i\) は明らかであるため、残りの \(i_l\) と \(j_r\) を求める。
まず \(i_l\) を求める。
\(T_{i_l,j-1}\) は \(T_{i,j}\) と最も左側の葉ノードを共有している。つまり、\(T_{i_l,j-1}\) より前にある葉ノード数は \(T_{i,j}\) より前にある葉ノード数と同じであり、その個数は式 (\(\ref{subtree_range}\)) より \(i_{\rm min}-1=\lfloor\frac{i-1}{2^j}\times 2^j\) である。
性質 1 より、\(T_{i_l,j-1}\) は高さ \(j-1\) の完全二分木である。したがって、\(T_{i_l,j-1}\) は \(2^{j-1}\) 個の葉ノードを内包している。
したがって、\(T_{i_l,j-1}\) の最も右側に位置する葉ノードは \(i_l = \lfloor\frac{i-1}{2^j}\rfloor\times 2^j + 2^{j-1}\) を持つ。
次に、\(T_{i,j_r}\) に含まれる葉ノードの数が \(i-i_l\) であることから、\(T_{i,j_r}\) の高さは \(j_r=\lceil\log_2(i-i_l)\rceil\) と算出できる。まとめると、任意のノード \(b_{i,j} \in T_n\) における左右のノード \(b_{i_l,j_l}\), \(b_{i_r,j_r}\) は式 (\(\ref{lr_index}\)) のように表すことができる。\[ \begin{equation} \begin{cases} (i_l, j_l) & = & \left(\left\lfloor \frac{i-1}{2^n} \right\rfloor \times 2^j + 2^{j-1}, j-1\right) \\ & = & (i-((i-1)\bmod 2^j)+2^{j-1}-1, j-1) \\ (i_r, j_r) & = & (i, \left\lceil \log_2(i-i_l) \right\rceil) \end{cases} \label{lr_index} \end{equation} \]
4.6. 中間ノードの高さ
Slate において部分木構造 \(T_{i,j}\) が完全二分木とならないケースは 2 つある。一つは \(b_{i,j}\) が高さの異なる 2 つの完全二分木を左右の枝に接続するケースであり、もう一つは \(b_{i,j}\) の右枝 (より大きい \(i\) を含む方の辺) が完全二分木でないケースである。ここでどのような中間ノードも左枝と接続している部分木が完全二分木であることに注意。すなはち、任意の \(b_{i,j}\) が接続してる 2 つの部分木はレベルが等しいか (\(T_{i,j}\) が完全二分木の場合)、または左枝に接続している部分技のほうが大きい (\(T_{i,j}\) が完全二分木でない場合)。したがって新しい中間ノード \(b_{i,j}\) の左枝に接続する部分技を \(T'_{k,\ell}\) とすると \(j=\ell+1\) となる。
4.7. 直列化表現
Slate に \(i\) 番目の値 \(b_i\) を追加するとき、一つの葉ノード \(b_i\) と 0 以上の中間ノード \(b_{i,j}\) が発生する。これらのノード情報をまとめ、Slate の直列化表現 \(S\) に \(i\) 番目に追加される要素をエントリ \(e_i\) と表す。これらは Figure 1 の Serialized Layout のように配置される。ここで、\(S\) の最も右に配置されているノードは常に Slate のルートノードである。
エントリ \(e_i\) には同一の世代を持つ全てのノード \(b_{i,*}\) が含まれている。加えて、中間ノードの右枝に接続しているノードは同一の世代であることから、ノードを右枝側に探索するケースは一回のエントリ読み込みで完了することができる。言い換えると、Slate はより最近のユーザデータへのアクセスがより効率的となる特性を持つ。
4.8. 検索効率
前述のように Slate の直列化形式においてはある世代で追加されるすべてのノードが同一のエントリに含まれている。言い換えると、任意の中間ノード \(b_{i,x}\) の右枝側のノード \(b_{i,y}\) は \(b_{i,x}\) と同じエントリに含まれており、従って右枝側への探索はストレージ上の 1 回の seek + read で済むことを意味している。従って最悪ケースはルートノードを起点にすべての移動が左枝側となるようなケース、つまり最も古いデータを検索する場合である。このような最悪ケースで最古のエントリを読み出すための seek + read 回数は \(O(log_2 N)\) となる。
具体例を挙げると、最新のエントリのみをメモリ上にキャッシュしている場合、\(T_{16}\) の木構造に含まれている各ノードに到達するまでの seek + read 回数は Figure 3 のようになる。
5. 操作とアルゴリズム
Slate の直列化表現であるリスト構造を \(S\) とし、\(S[x]\) を \(S\) の \(x\) 番目に格納されているノードとする。特に \(S[{\rm last}]\) という表記は \(S\) の最末尾のノードを表している。
5.1 追加操作
\(S\) に新しい葉ノード \(b_i\) を追加する操作は Algorithm 1 と Algorithm 2 を用いてエントリ \(e_i\) を構築し \(S\) に連結する。
- 以下のノード集合を用いて \(e_i\) を構築する。ここですべてのノードは \(j\) で降順ソートされるものとする。
- 葉ノード \(b_i\)
- Algorithm 1 で得た順序集合 \(\mathcal{B}'_i\) に含まれる \(b'_{i,*}\) である中間ノード
- Algorithm 2 で得た順序集合 \(\mathcal{B}_i\) のすべての中間ノード
- \(e_i\) を \(S\) に連結する。
この手順により作成される \(e_i\) は、先頭のノードに葉ノード \(b_i\)、末尾のノードに木構造のルートノードを配置している。
Figure 4 は \(T_{13}\) に \(b_{14}\) を追加するために上記の操作を行った結果として構築される木構造である。「新しく追加された \(b_i\) を含む最大の部分木」と「その部分木の左隣りに位置する最も大きな完全二分木」とを中間ノードが接続し木構造全体が接続されることが分かる。
5.1.1. \({\rm append}(e:{\it Node})\) 関数
Algorithm 3 は既存の木構造の直列化表現に新しい葉ノード \(b_n\) を追加する操作を表している。
| 1. | \( {\bf function} \ {\rm append}(b_n:Node) \) | |
| 2. | \( \hspace{12pt}\mathcal{B}'_n = {\rm pbst\_roots}(n) \) | // Algorithm 1 |
| 3. | \( \hspace{12pt}\mathcal{B}_n = {\rm ephemeral\_nodes}(n) \) | // Algorithm 2 |
| 4. | \( \hspace{12pt}e_n = {\rm sort} \ (\{b_n\} \cup \{b_{i,*} \in \mathcal{B}'_n \mid i=n\} \cup \mathcal{B}_n) \ {\rm by} \ j \) | // \(j\) で降順ソートされた順序集合となるように |
| 5. | \( \hspace{12pt}S := S \mid\mid e_i \) | |
5.2. 検索操作
Slate の検索は通常の二分木検索と同じである。木構造全体が完全二分木となる特殊なケースではすべての葉ノードへは \(O(\log_2 N)\) で均等に到達できるが、そうでない場合、最近追加された葉ノードが比較的レベルの低い部分木に属するという偏りを持つことから、最新のデータがより速く検索できる特徴を持つ。ただしその場合、一過性の中間ノードが存在することにより +1 ステップの操作が必要であるため、検索に対する一般化した計算複雑性は \(O(\lceil \log_2 N \rceil)\) である。
5.2.1. 単一検索操作
5.2.1.1. \({\rm contains}(b_{i,j}:{\it Node},k:{\it Int})\) 関数
二分木の探索で左右の枝のどちらに検索対象の葉ノードが含まれているかは式 (\(\ref{subtree_range}\)) を使用することができる。あるノード \(b_{i,j}\) をルートとする部分木に葉ノード \(b_k\) が含まれるかを判定することで中間ノードの左右の枝のどちらに検索対象の葉ノードが含まれているかを判断することができる。
| 1. | // \(b_{i,j}\) をルートとする部分木構造に葉ノード \(b_k\) が含まれているかを判定 | |
| 2. | \( {\bf function} \ {\rm contains}(b_{i,j}:{\it Node}, k:{\it Int}) \to {\it Boolean} \) | |
| 3. | \( \hspace{12pt}i_{\rm min}, i_{\rm max} = {\rm range}(b_{i,j}) \) | |
| 4. | \( \hspace{12pt}{\bf return} \ i_{\rm min} \le k \ {\bf and} \ k \le i_{\rm max} \) | |
5.2.1.2. \({\rm retrieve}(e:{\it Node},i:{\it Int})\) 関数
マルチスレッド/マルチプロセス環境で追加と検索の操作を並行処理で行っている場合、追加操作の途中で実行されると \(S[{\rm last}]\) が Slate のルートノードでない可能性があることに注意。
| 1. | \( b_i := {\rm retrieve}(S[{\rm last}], i) \) | |
| 2. | \( {\bf function} \ {\rm retrieve}(b_{i,j}:{\it Node}, k:{\it Int}) \to {\it Node} \) | |
| 3. | \( \hspace{12pt}{\bf if} \ j = 0 \ {\bf then} \) | |
| 4. | \( \hspace{24pt}{\bf return} \ {\bf if} \ i = k \ {\bf then} \ b_{i,j} \ {\bf else} \ {\it None} \) | |
| 5. | \( \hspace{12pt}{\bf else \ if} \ {\rm contains}(b_{i,j}.{\rm left}, k) \ {\bf then} \) | |
| 6. | \( \hspace{24pt}{\bf return} \ {\rm retrieve}(b_{i,j}.{\rm left}, k) \) | |
| 7. | \( \hspace{12pt}{\bf else} \) | |
| 8. | \( \hspace{24pt}{\bf return} \ {\rm retrieve}(b_{i,j}.{\rm right}, k) \) | |
5.2.2. 範囲検索操作
すべての要素は \(S\) 上で直列化されているため範囲検索は容易である。\(t_0\) から \(t_1\) までの要素を取得するには、まず \(S\) 上の \(b_{t_0}\) の位置を検索し、そこから \(S\) を右方向に \(b_{t_1}\) を検出するまで読み込むだけで良い。
読み込み位置を \(i\) とすると 1 要素あたり 1 から \(\log_2 i\) 個の中間ノードの読み込みまたはスキップ (seek) が発生するが、中間ノード自体はそれほど大きくなく、連続した領域であることから I/O バッファが有効に機能して大きな影響はないと考えられる。
| 1. | \( {\bf function} \ {\rm range\_scan}(b_{i,j}:{\it Node}, i_{\rm min}:{\it Int}, i_{\rm max}:{\it Int}) \to \) | |
5.2.2.1. \({\rm range}(b_{i,j}:{\it Node})\) 関数
| 1. | \( {\bf function} \ {\rm range}(b_{i,j}:{\it Node}) \to ({\it Int}, {\it Int}) \) | |
| 2. | \( \hspace{12pt}i_{\rm max} = i \) | |
| 3. | \( \hspace{12pt}i_{\rm min} = (\lfloor 1/2^j \rfloor - (1 \ {\bf if} \ i \bmod 2^j = 0 \ {\bf else} \ 0)) \times 2^j + 1 \) | |
| 4. | \( \hspace{12pt}{\bf return} \ (i_{\rm min}, i_{\rm max}) \) | |
\(j\) の範囲が \(0..\lceil \log_2 i \rceil\) であることから、\(i\) の定義域を 64-bit とすると \(2^j\) は 65-bit の値域を取りうることに注意。
5.2.3. ハッシュ付き検索操作
ハッシュツリーとして要素を検索する場合、要素そのものだけではなく経路から分岐する中間ノードのハッシュ値も取得しなければならない。\(T_n\) を \(b_{n,\ell}\) をルートとする木構造とし、任意のノード \(b_{i,j} \in T_n\) に属するすべての葉ノード (ユーザデータ) を取得するときに必要となる中間ノードついて考える。
5.2.3.1. \({\rm level}(b_{n,\ell}:{\it Node}, b_{i,j}:{\it Node})\) 関数
ハッシュ付き検索の結果に必要な中間ノードの個数は \(b_{i,j}\) のレベル (\(b_{i,j}\) から目的のルートノード \(b_{n,\ell}\) までの祖先の数) に等しい。もし \(T_n\) が完全二分木であれば \(\ell - j\) であることは明らかだが、そうでない場合、\(b_{i,j}\) を含む完全二分木までの距離をヒューリスティックに求める必要がある。
| 1. | \( {\bf function} \ {\rm level}(b_{n,\ell}:{\it Node}, b_{i,j}:{\it Node}) \to Int \) | |
| 2. | \( \hspace{12pt}{\bf if} \ {\bf not} \ {\rm contains}(b_{n,\ell}, i) \ {\bf then} \) | |
| 3. | \( \hspace{24pt}{\bf return} \ {\it None} \) | |
| 4. | \( \hspace{12pt}b := b_{n,\ell} \) | |
| 5. | \( \hspace{12pt}{\rm step} := 0 \) | |
| 6. | \( \hspace{12pt}{\bf while} \ b \ne b_{i,j} \ {\bf and} \ b.i \bmod 2^{b.j} \ne 0 \) | |
| 7. | \( \hspace{24pt}b := b.{\rm left} \ {\bf if} \ {\rm contains}(b.{\rm left}, i) \ {\bf else} \ b.{\rm right} \) | |
| 8. | \( \hspace{24pt}{\rm step} = {\rm step} + 1 \) | |
| 9. | \( \hspace{12pt}{\bf return} \ b.j - j + {\rm step} \) | |
この関数はサーバ応答に正しい数の中間ノード (ハッシュ値) が含まれていることをクライアント側で検証するために使うことができる。
5.2.3.2. \({\rm retrieve\_with\_hashes}()\) 関数
| 1. | \( {\bf function} \ {\rm retrieve\_with\_hashes}(b_{n,\ell}:{\it Node}, b_{i,j}:{\it Node}) \to ({\it Set}[{\it Node}], {\it Sequence}[{\it Node}]) \) | |
| 2. | \( \hspace{12pt}{\bf if} \ {\bf not} \ {\rm contains}(b_{n,\ell}, i) \ {\bf then} \) | |
| 3. | \( \hspace{24pt}{\bf return} \ {\it None} \) | |
| 4. | \( \hspace{12pt}b := b_{n,\ell} \) | |
| 5. | \( \hspace{12pt}{\rm branches} := \emptyset \) | |
| 6. | \( \hspace{12pt}{\bf while} \ b \ne b_{i,j} \) | |
| 7. | \( \hspace{24pt}{\bf if} \ {\rm contains}(b.{\rm left}, i) \ {\bf then} \) | |
| 8. | \( \hspace{36pt}b := b.{\rm left} \) | |
| 9. | \( \hspace{36pt}{\rm branches} := {\rm branches} \mid\mid b.{\rm right} \) | |
| 10. | \( \hspace{24pt}{\bf else} \) | |
| 11. | \( \hspace{36pt}b := b.{\rm right} \) | |
| 12. | \( \hspace{36pt}{\rm branches} := {\rm branches} \mid\mid b.{\rm left} \) | |
| 13. | \( \hspace{12pt}i_{\rm min}, i_{\rm max} = {\rm range}(b) \) | |
| 14. | \( \hspace{12pt}{\rm values} := {\rm range\_scan}(b, i_{\rm min}, i_{\rm max}) \) | |
| 15. | \( \hspace{12pt}{\bf return} \ ({\rm branches}, {\rm values}) \) | |
5.2.4. 分岐ノードの算出
ある \(T_n\) のルートノードから任意の \(b_{i,j} \in T_n\) までを結ぶ距離を求める。Algorithm 1 によって求めた完全二分木の部分構造のルートノードの中で \(b_{i,j}\) を含む部分木を \(b'_{i',\log_2 i'}\) とする。
- 対象のノード \(b_{i,j}\) を含む完全二分木のルートノードを取得し、\(T_n\) のルートノードからの距離を得る。
- 完全二分木のルートノードを \(b'_{i',j'}\) としたとき、\(b'_{i',j'}\) からの距離 \(j' - j\) を計算する。
| 1. | \( {\bf function} \ {\rm nodes\_at\_branches}(n:{\it Int}, i:{\it Int}, j:{\it Int}) \to {\it Int} \) | |
| 2. | \( \hspace{12pt}\mathcal{B}'_n = {\rm Algorithm1}(n) \) | |
| 3. | \( \hspace{12pt}b := {\rm root \ of \ } T_n \) | |
| 4. | \( \hspace{12pt}{\bf for} \ b'_{i',j'} \ {\bf in} \ \mathcal{B}'_n \) | |
| 5. | \( \hspace{24pt}{\bf if} \ {\rm contains}(b'_{i',j'}, i, j) \) | |
5.3 補助的操作
5.3.5. 起動時の初期動作
すべての操作は木構造のルートノードを含むエントリ \(S[{\rm last}]\) に頻繁にアクセスするため、起動時に \(S[{\rm last}]\) の内容を読み込んでメモリ上で保持することで効率的に動作できるだろう。しかし、先頭の \(S[1]\) から逐次読み込んでいては \(S\) が大きくなったときに時間がかかることから、ファイルの末尾から \(S[{\rm last}]\) を取得できるようにすべきである。これは次のように実装できるだろう:
ファイルの末尾から固定長の seek で \(S[{\rm last}]\) の先頭位置が分かる情報を入れておく。
\(S[{\rm last}]\) からその情報までが正しい情報であることを確認するためのチェックサムを入れておく。
ノードとしては正しいがすべての中間ノードが書き込まれていない状況を検知するため、読み込んだ \(S[{\rm last}]\) が木構造全体を表していることを確認する。
\(S[{\rm last}]\) の破損を検出した場合、\(S[1]\) から最後に正しく読み込みができた要素 \(b_i\) を \(S[{\rm last}]\) として
5.3.6. ロールバックと末尾置換操作
ロールバック操作は直列化されたストレージをある世代の位置まで truncate するだけである。
6. 複雑性の解析
7. 実装上の考慮
7.1. キャッシュ設計
Slate での追加操作と検索操作を効率的に実行するためには、木構造の特定のノードを戦略的にキャッシュする必要がある。このセクションでは Slate の構造的特徴を考慮したキャッシュ設計について記述する。
7.1.1. キャッシュ忘却特性
Slate が厳密な意味でのキャッシュ忘却アルゴリズム (Cache-Oblivious Algorithm) とは断言できないが、以下の特性からキャッシュ忘却に近い特性を持つと予想する。
直列化レイアウトでの局所性: 同一世代のノード \(b_{i,*}\) がすべて同一エントリ \(e_i\) に格納され、右枝方向への探索が単一のメモリブロック内で完結する。この特性は、キャッシュラインサイズやページサイズに依存せずに局所性の恩恵を受ける。
再帰的な完全二分木構造: Slate が内包する完全二分木 \(T'_{i,j}\) はそれぞれ独立した部分構造として扱うことができる。これは van Emde Boas layout に類似した階層的アクセスパターンと言える。これにより、キャッシュ階層の深さにかかわらず、自然に階層的な局所性を活用できる。
アクセスパターンの偏り: Slate は新しいデータほど浅い位置に配置される構造的特徴を持つ。これは、時系列データの「最近のデータほどアクセス頻度が高い」という性質と整合する。この偏りはキャッシュサイズにかかわらず有効に機能する。
Slate が内包する完全二分木では標準的な二分探索木と同等のキャッシュ忘却性を持ち、最悪ケース (最古のデータへのアクセス) であっても、各レベルでたかだか 1 回のキャッシュに抑えられることから、次の予想が成り立つと考える。
予想: メモリ階層のパラメータ (キャッシュサイズ \(M\)、ブロックサイズ \(B\)) を知らない状態であっても、\(n\) 個の要素を持つ Slate における検索操作のキャッシュミス回数は \(O(\log_B n)\) となる。
このようなキャッシュ忘却の特性により、Slate は様々なハードウェア環境において明示的なキャッシュ管理を実装しなくても効率的な性能を発揮することが期待される。ただし、この特性は理論上の予測であり、厳密な証明は今後の課題である。
7.1.2. 段階的なキャッシュ戦略
Slate におけるキャッシュ忘却特性は主にデータの局所性に由来する特徴で、ディスク I/O の削減や CPU キャッシュの有効活用に関連している。一方で、現実の実装では計算の削減を目的として明示的なキャッシュが推奨される。
Slate の優れた構造設計により、最新エントリ \(e_n\) には木構造の操作を開始するために必要な以下の情報がすべて含まれている。
現世代のルートノード \(b_{n,\lceil \log n \rceil}\): これはすべての操作の起点となる。
完全二分木のルートノードへの参照: 追加操作において新しく発生するノードとの接続先として (実データではなく位置のみが) 参照される。また検索操作では I/O なしに完全二分木のルートの位置を特定できる。
一過性ノード集合 \(\mathcal{B}_n\): 現世代の木構造を形成する。
この特性により、キャッシュを全く使用しない場合であっても、直列化表現 \(S_n\) の末尾のエントリ \(e_n\) の 1 回の読み込みで木構造の操作を開始できる。
言い換えると、最新のエントリ \(e_n\) をメモリ上にキャッシュするだけでも、すべての主要な操作において最初の 1 回の読み込みを削減できる。\(e_n\) のキャッシュに必要な空間計算量は \(O(\log n)\) と極めて小さく、その効果はあらゆる操作で一律 1 回の I/O 削減として現われる。この費用対効果の高さから、最新エントリのキャッシュは強く推奨される。
加えて、読み込み中心のワークロードでは、キャッシュの範囲を木構造の下に向かって段階的に拡張することでさらなる性能向上が可能である。ここで、上で述べた最新エントリ \(e_n\) のキャッシュをレベル 0 (基本キャッシュ) とする。レベル \(k\) のキャッシュは完全二分木のルートから深さ \(k\) までのノードを含むエントリをキャッシュする。空間計算量は \(O(2^k \times (\log n)^2)\) となるが、\(k\) の上限は木の高さ \(\log_2 n\) に制限される。
例えば、レベル 1 は \(T_n\) が内包する各完全二分木のルートノード \(b'_{i,j} \in \mathcal{B}'_n\) を含んでいる各エントリ \(e_i\) をキャッシュする。これにより、完全二分木の探索を I/O なしに開始することが可能となり、追加で 1 回の READ が削減される。空間計算量は \(O((\log n)^2)\) となる。さらにレベル 2 では、各完全二分木のルートノードの左枝の子ノードを含む各エントリをキャッシュする。完全二分木内の最初の分岐までがカーバされるようになり、さらに 1 回の READ が削減される。このようにして、検索のワークロードに対して適応的に段階化されたキャッシュを使用することができる。
7.1.3. 実装上の推奨事項
多くのアプリケーションではレベル 0 の基本キャッシュのみで十分な効果が得られる。特に、追記中心のワークロードや、最近のデータへのアクセスが多い時系列データ処理では、それ以上のレベルのキャッシュは有効な効果をもたらさないかもしれない。
一方、全データ範囲にわたる均等なアクセスパターンを持つアプリケーションでは、レベル 1 キャッシュの採用により古いデータへのアクセスも高速化できる。レベル 2 以上は、極めて低レイテンシーが要求される特別な用途に限定すべきである。
このように、Slate のキャッシュ設計は、最小限のメモリ使用量で効果を得られる基本戦略と、アクセスパターンに応じた段階的な拡張オプションを提供する。構造自体が局所性を持つことにより、キャッシュなしでも実用的な性能を持ちながら、単純なキャッシュ戦略で有効な性能向上を実現できる。
追加の選択肢として、最近アクセスしたエントリ (LRU などで) や頻繁にアクセスのあることが分っている世代のノード集合をヒューリスティックにキャッシュすることが考えられるが、その有効性はアプリーションのアクセスパターンに依存するためここでは省略する。
7.2. 並行処理
実用的なシステムでは複数のプロセスやスレッドからの並行したアクセスが前提となる。特にトランザクションログやブロックチェーンの用途では並行性が必須となる。Slate の構造的特性は並行処理の環境で特に有利に機能する。確定済みとなり、書き込まれたすべてのノードとその関連する木構造が永続的となった部分木には、複数のプロセスが並行してデータにアクセスできる。
7.2.1. 読み取りの安全性
\(n\) 世代までが確定している (truncate や replace が起きない) のであれば、木構造 \(T_n\) も直列化表現 \(S_n\) も値や構造が変わることはない。したがって、追記操作とは完全に独立して読み取り操作が可能である。
確定済みエントリの安定性: 一度書き込まれたエントリは変更されない。
Slate に書き込まれた要素および関連するツリー構造が永続的であることは並行処理に有利に機能する。直列化表現 \(S\) への要素や中間ノードの追加は単一プロセスで行う必要があるが、検索については検索開始時点の確定済み木構造を基準に行うことで、追加処理や他の検索処理が進行中であっても安全に行うことができる。
7.2.2. 書き込み競合の回避
Slate への新しい世代の追加は、木構造の一貫性とファイルの整合性を保つために単一のプロセスまたはスレッドで行う必要がある。これは、新しいエントリの構築と直列化表現の書き込みが青とミックに行われることを保証するためである。
複数のプロセスまたはスレッドが Slate を共有するケースにおいて、整合性を保証する最も簡単な方法は、書き込み操作に対して排他制御を適用することである。追加操作を実行するプロセスは、まず書き込みロックを獲得し、新しいエントリの構築とファイルへの書き込みを完了した後、ロックを解放する。この方法は単純で確実だが、書き込み頻度が高い場合にはロック競合により各プロセスのスループットが低下する可能性がある。
より高度な設計として、書き込み操作を専用のプロセスまたはスレッドに委譲する方法がある。この設計では、追加要求をジョブキューに投入し、専用の書き込みプロセスがそれを逐次処理する。これにより書き込み操作の直列化が自然に実現され、ロック機構が不要になる。ただし、キューの管理やプロセス間通信 (終了の通知など) のオーバーヘッドが発生することからシステム全体の構造が複雑化する。
追加操作の頻度がそれほど高くないシステムでは、楽観的ロックを使用することで CPU リソースの効率的な利用が期待できる。この方式では、各プロセスは以下の手順で追加を試みる:
まず、現在の確定済み世代 \(x\) のエントリを参照し、それに基づいてメモリ上で新しい世代 \(x+1\) のエントリを作成する。世代 \(x\) のエントリは immutable であり、エントリの構築はローカルな操作であるため、他に同じ処理を行おうとしているプロセスと競合することなく実行できる。
次に Compare-and-Swap (CAS) 操作を用いて世代番号の更新を試みる。世代 \(x\) から \(x+1\) への更新に成功した場合、現在のルートを新しいエントリのルートに更新し、ファイルへの追記を実行する。もし他のプロセスが先に世代を更新していた場合、構築したエントリを破棄し、最新の状態を参照して最初からやり直す。
7.2.3. 楽観的ロックを使った並行書き込み
要素の追加頻度がそれほど高くないシステムにおいては、追記操作において楽観的ロックを使うことで CPU リソースの効率化を期待することができる。
一つの方法は、確定済みの高さを表すアトミック更新が可能な変数 \(x_1\) と、追加処理が進行中の高さを表す CAS (Compare and Swap) が可能な変数 \(x_2\) を使用する。追加処理を開始したプロセス \(P\) はまず \(x_1\) から最新の確定済み高さを参照し (仮にその値を \(n\) とする) 木構造 \(T_n\) に基づいて要素や中間ノードの直列化表現をメモリ上で準備する。次に、実際に書き込みを行う直前に \(x_2\) に対して \(n \to n+1\) の更新を試みる。\(x_2\) の更新に成功した場合、実際に書き込みを行い、最後に \(x_1\) を \(n+1\) に更新する。\(x_2\) の更新に失敗した場合は自身が基準にした木構造 \(T_n\) が最新ではないため最初からやり直す。ただし、この方法は \(x_2\) の更新に成功したプロセスが \(x_1\) を更新する前に (外部からのシグナルや disk full などで) 停止してしまうケースである。この場合、ある一定期間 \(x_1 \ne x_2\) かつ書き込みが進行していなければ、書き込み中のプロセスが使用している I/O リソースをクローズし、書き込み位置を \(x_1\) の最後まで戻し、最後に \(x_2\) を \(x_1\) と等しくなるように戻すといったタイマー監視の処理が必要になるかもしれない。
7.3. 障害耐性と回復
Slate では直列化された個々のノードが (ハッシュツリーのハッシュ値はと別に) チェックサムを持つことでデータの破損を検出可能にしている。
要素の追加操作中にシステムが異常終了した場合、次に起動したときに \(S[{\rm last}]\) が破損している可能性がある。それぞれのノードはチェックサムを追加することによって破損を検出できるようにしている。
最後のエントリがすべてのデータとツリー構造を要約していることから、完成した Slate の最後のエントリに対する署名を追加することで、第三者が検証可能なように "封印" することができるだろう。
8. アプリケーション
8.1. 分散トランザクションログの修復と一貫性の維持
分散コンセンサスアルゴリズムの Raft においてリーダーが交代したとき、新しいリーダーと各フォロワー間でログの一貫性を保証するプロセスがある。これは、双方のログ (トランザクションログ) がどこまで一致しているかを検出して、それ以降のログをリーダーのログで上書きする。このプロセスにおいて、Raft ではリーダーのログを後方から送信する。
8.2. ハッシュグラフとバージョン管理システム
分散バージョン管理システムの git における merge-base コマンドでは、2 つのブランチの分岐点を見つけるために、双方のコミットを起点に親を遡って共通の祖先を探すアルゴリズムを使用している。これは平均ケースで \(O(\log n)\)、最悪ケースで \(O(n)\) の計算量となる。
木構造の特定の世代を基準に別のハッシュ木を枝として分岐させることができるだろう。これは git のブランチシステムに似ている。
8.3. ブロックチェーンシステム
ブロックチェーンのチェーン状の連鎖を Slate に置き換えることで、概念が簡素化され、light client での利用も自然に統合できる。
ブロックチェーンは、追記型のチェーン状のデータ構造を持ち、特に Bitcoin などのフォークが発生するタイプについては一貫性を維持するために修復機構を備えている。つまり、ブロックチェーンはビザンチン障害耐性を持つ分散トランザクションログと見なすことができる。このため、ブロックチェーンにおいてもブロックの検証や、効率的な分岐点の検出のために Slate を使用することができる。
一般的なブロックチェーンは、あるブロックに前のブロックのハッシュ値を埋め込むことで概念的にチェーン状のデータ構造を構築する。ただし、この構造は、あるブロックの正当性を確認するために、その直前の検証済みブロックを持っていなければならない。これは、帰納的に、あるブロックのみを入手しても、その検証のために、それより前のすべてのブロックを入手する必要があることを意味する。
ブロックチェーンには、light client と呼ばれる、自身が必要な一部のデータのみを追跡するノードが存在する。このノードは、自身が持っていないブロックが必要になったときに、それを full node に問い合わせて入手するが、そのブロックが改ざんされていないことを確認するために、一般にハッシュツリーを使用する。
light client はブロックチェーンネットワークから最新のブロックを取得してハッシュツリーを計算し、そのルートハッシュを追跡する。light client は、あるブロックが必要になったとき、full node にそのブロックを問い合わせ、ブロックをハッシュツリーの最小限の枝も含めて取得する。light client は、ブロックのハッシュ値から枝を遡って算出したルートハッシュが、自身の追跡しているルートハッシュと一致していれば、そのブロックが改ざんされていないことを保証できる (暗号論的ハッシュ関数を使用していれば意図したハッシュ値に衝突させるような改ざんを行うことは不可能である)。
つまり、light client を想定するブロックチェーンはすでにハッシュツリーを計算する実装を行っている。あるブロックに前のブロックのハッシュ値を埋め込む代わりに、Slate 構造化したルートハッシュを埋め込むことができる。つまり、ブロックチェーンの現状は「チェーン状に連結されたブロック」と「ハッシュツリー状に連結されたブロック」の 2 つの観点を持ち、局面によって概念を切り替えている状態である。これは実装面で余分な複雑さをもたらしている。Slate の構造に基づく概念に統一することで観点が簡素化される。
ブロックチェーンには、あるブロックが追加されて世代が進むにつれてそのブロックの改ざん耐性が高くなるという特性がある。これは、ハッシュの衝突を想定したとしても、チェーンが長くなるにつれて過去のブロックを遡って改ざんするすることが難しくなることを意味している。Slate でも古いデータはルートノードからの深さが高くなるため、オーダーは異なるものの同様の性質を考慮できる。
9. 実験的評価
10. 議論
10.1. トレードオフ
10.2. セキュリティ考察
10.3. 将来的な拡張
11. 結論
References
- O’Neil, P., Cheng, E., Gawlick, D. et al. The log-structured merge-tree (LSM-tree). Acta Informatica 33, 351–385 (1996). https://doi.org/10.1007/s002360050048
- Haber, S., Stornetta, W.S. How to time-stamp a digital document. J. Cryptology 3, 99–111 (1991). https://doi.org/10.1007/BF00196791
- Buldas, A., Saarepera, M. (2004). On Provably Secure Time-Stamping Schemes. In: Lee, P.J. (eds) Advances in Cryptology - ASIACRYPT 2004. ASIACRYPT 2004. Lecture Notes in Computer Science, vol 3329. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30539-2_35
- Hash Calendar実装の特許： US Patent 8,719,576 B2: "Document verification with distributed calendar infrastructure" (2014). Inventors: Ahto Buldas, Märt Saarepera
- Driscoll, J. R., Sarnak, N., Sleator, D. D., Tarjan, R. E.: Making data structures persistent. In J. Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 109–121. ACM, (1986)
- R. C. Merkle. Protocols for public key cryptosystems, in Secure communications and asymmetric cryptosystems, pp. 73–104, Routledge, 2019.
- Merkle, R.C. (1987) A Digital Signature Based on a Conventional Encryption Function. Conference on the Theory and Application of Cryptographic Techniques, Santa Barbara, 16-20 August 1987, 369-378. https://doi.org/10.1007/3-540-48184-2_32
