FlashDB
Suman Nath, Aman Kansal · 2007
FlashDB is a self-tuning database optimized for sensor networks using NAND flash storage. In practical systems flash is used in different packages such as on-board flash chips, compact flash cards, secure digital cards and related formats. Our experiments reveal non-trivial differences in their access costs. Furthermore, databases may be subject to different types of workloads. We show that existing databases for flash are not optimized for all types of flash devices or for all workloads and their performance is thus suboptimal in many practical systems. FlashDB uses a novel self-tuning index that dynamically adapts its storage structure to workload and underlying storage device. We formalize the self-tuning nature of an index as a two-state task system and propose a 3-competitive online algorithm that achieves the theoretical optimum. We also provide a framework to determine the optimal size of an index node that minimizes energy and latency for a given device. Finally, we propose optimizations to further improve the performance of our index. We prototype and compare different indexing schemes on multiple flash devices and workloads, and show that our indexing scheme outperforms existing schemes under all workloads and flash devices we consider.
Cited by 199 works. doi:10.1145/1236360.1236412
Authors
References
- The design and implementation of a log-structured file system
- CarTel
- An optimal online algorithm for metrical task systems
- Hardware design experiences in ZebraNet
- Database Systems Concepts
- An Efficient B-Tree Layer for Flash-Memory Storage Systems
- ELF
- Competitive algorithms for replication and migration problems
- XYZ: a motion-enabled, power aware sensor node platform for distributed sensor network applications
- Microhash: an efficient index structure for fash-based sensor devices