SSDを対象としたKey-Value Storeのデータ構造に関する研究

摘要

データベース分野では，シーケンシャルライトが高速な従来のSSD (Solid State Drive）の特性を生かすために，SSD上にシーケンシャルにデータを書き込み，Keyと書込み位置の対応を主記憶上のインデックスで保持するKVS (Key Value Store）が提案されている。特に，要素をSSD上でブロック単位に分割し，各ブロックに対応する主記憶上のインデックスとしてBloom Filterを用いる方式は，少ない主記憶容量で大量の要素を管理できることから有望と考えられる。しかし，従来の構造では，Bloom Filterの偽陽性に伴うブロックの読出しにより速度が低下するという課題があった。本論文では，この点について定量的な検討を行い，アクセス速度を高速化するために，ブロック内探索を融化する複数のデータ構造を提案した。その結果，市販の一般消費者向けSSDを使用して，1ms以下のアクセス時間を実現可能であることを確認した。