Skip to Main content Skip to Navigation
Reports

PBFilter: Indexing Flash-Resident Data through Partitioned Summaries

Shaoyi Yin 1 Philippe Pucheral 1 Xiaofeng Meng 1
1 SMIS - Secured and Mobile Information Systems
PRISM - Parallélisme, Réseaux, Systèmes, Modélisation, UVSQ - Université de Versailles Saint-Quentin-en-Yvelines, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8144
Abstract : NAND Flash has become the most popular persistent data storage medium for mobile and embedded devices and is even being considered as a credible competitor for traditional disks. The hardware characteristics of NAND Flash (e.g. page granularity for read/write with a block-erase-before-rewrite constraint, limited number of erase cycles) preclude in-place updates. Previous works adapted traditional indexing methods to cope with these constraints mainly by deferring index updates thanks to a log and batching them to decrease the number of rewrite operations in Flash. These methods introduce a complex trade-off between read and write performance and neglect negative side-effects on the RAM consumption, Flash consumption and garbage collection cost. In this paper, we propose a new alternative for indexing Flash-resident data, designed from the outset to exploit the peculiarities of NAND Flash. This ap-proach, called PBFilter, organizes the index structure in a pure sequential way to avoid the side-effects mentioned above. Key lookups are sped up thanks to two principles called Summariza-tion and Partitioning. We instantiate these principles by data structures and algorithms based on Bloom Filters and show the effectiveness of this approach through a comprehensive perform-ance analysis. PBFilter can be instantiated with different Summarization and Partitioning algo-rithms opening up a new way to think about indexing Flash-resident data.
Document type :
Reports
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/inria-00284359
Contributor : Shaoyi Yin <>
Submitted on : Wednesday, June 4, 2008 - 4:59:16 PM
Last modification on : Tuesday, May 19, 2020 - 2:36:14 PM
Long-term archiving on: : Tuesday, September 21, 2010 - 4:41:53 PM

File

RR-6548.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00284359, version 2

Collections

Citation

Shaoyi Yin, Philippe Pucheral, Xiaofeng Meng. PBFilter: Indexing Flash-Resident Data through Partitioned Summaries. [Research Report] RR-6548, INRIA. 2008. ⟨inria-00284359v2⟩

Share

Metrics

Record views

212

Files downloads

514