Override Pages for Efficient Log-Structured Index

本論文では，後乗せページという新しい構造を導入することによって，ログ構造化データ構造における木構造インデックスの取り扱いを改善できることを示す．ログ構造化データ構造における更新は，新しいデータを含むページ (ログ構造の構成単位) をログ状の構造の末尾に追記することによって行う．今までのログ構造化データ構造では，古いページを参照していたページが存在していた場合，それらも新しいページを参照するように再帰的にログ構造に書き出される必要があった．この更新プロセスでは，階層的な参照関係を持つ木構造のインデックスを使用した際に，木のルートまで参照更新の伝搬処理が発生してしまい，大量のページが参照の更新のために再度書き出されることになってしまう．今回，この問題に対し，後乗せページという特殊なページを導入することによって，更新伝搬を抑制することに成功した．後乗せページには，通常のページとは違い，更新元への参照が含まれている．更新元ページと後乗せページの関係を変換表を用いて管理することにより，古いページに対する参照を，適宜更新データを持つ後乗せページへの参照と読み替えることができる．以上の後乗せページを用いた更新を用いることで，木構造インデックスを取り扱った際に発生する参照更新の伝搬を遅延することができる．本論文では，提案手法であるログ構造化データ構造への後乗せページの導入，及びこれを扱う実装について詳しく述べる．さらに，提案手法を導入することで，木構造インデックスを扱う際に性能向上が得られることを評価により示す．

In this paper, we introduce override pages, a simple expansion to log-structured data structures which greatly improves efficiency of tree indices. In log-structured data structures, updates are performed by appending a page, an element that composes log structure containing update data, to tail of the log. In previous methods, all references to the page that contained old data had to be also recursively updated and rewritten to tail of the log. However, in this process, an single update of indices with hierarchical references would result in massive rewrite of pages, caused by reference updates propagating to the tree root. We have relieved this issue by introducing override pages, special pages specifying update while retaining old references. Override pages, unlike ordinary pages, contain a reference to the page containing old data. By keeping track of these relations between the old page and a new override page, it is possible to redirect references to old pages to the override pages containing new version of the data. By updating indices with override pages, we could delay the reference update propagation, and therefore greatly reduce the number of written pages in a single update. In this paper, we first describe our model of override pages, and design and implementation when incorporating it to log-structured data structures. Furthermore, we evaluate performance improvement in tree indices achieved by override pages.