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.
Type de document :
[Research Report] RR-6548, INRIA. 2008
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

Contributeur : Shaoyi Yin <>
Soumis le : mercredi 4 juin 2008 - 16:59:16
Dernière modification le : vendredi 25 mai 2018 - 12:02:04
Document(s) archivé(s) le : mardi 21 septembre 2010 - 16:41:53


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00284359, version 2



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



Consultations de la notice


Téléchargements de fichiers