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

山田 淳二  浅野 正一郎  

誌名
電子情報通信学会論文誌 D   Vol.J96-D   No.3   pp.519-530
発行日: 2013/03/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 特集論文 (学生論文特集)
専門分野: データ工学,Web情報システム
キーワード: 
SSD,  KVS (Key-Value Store),  Bloom Filter,  

本文: PDF(1.8MB)>>
論文を購入




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