Bloom Filterによる高速でコンパクトなインデックス構造: NAND FlashSSD上の高速データベースを対象とした

摘要

高速で大容量のNAND Flash SSD（Solid State Disk）について、大量のデータアクセスを伴うデータべ-ス分野での利用が研究されている。データの上書きに消去-モディファイ一再書込みが必要なNANDFlashの特性から，SSDへの書込みはシーケンシャルに行うことが望まれることから、SSD上にシーケンシャルにデータを書込み、Keyと書込み位置の対応を主記憶上のインデックスで保持する構造が、従来から提案されてきた。しかし、従来の構造では、主記憶上のインデックス構造の高速性とメモリ利用効率の両立が難しく、SSDの高速性能を十分に生かすことが出来なかった。本稿では、この点を解決する、Bloom Filterを利用した、メモリ利用効率が高く高速なインデックスのデータ構造を提案し、従来手法と比べて11.8倍の高速化を確認した。%Fast and large capacity SSD became a research target in the field of databases with large amounts of data access such as Key Value Store. From the nature of NAND Flash memories that need erase-modify-write operation to update data, data write into SSD should be sequential. Several data structures are known to keep relation table between key and stored location, on main memory, in order to realize sequential write into SSD. However, these methods have drawbacks on index structure, in fastness or memory efficiency, as well as premature realization of SSD performance. In this report, we propose an efficient and fast index structure using Bloom Filters to make possible of large database applications using SSDs. From the evaluation, the proposed index structure can 11.8 times faster compared to the conventional method based on a similar Bloom Filter.