FlashDB: Dynamic Self-tuning Database for NAND Flash

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 that their access costs are not identical. Further, databases may be subject to different workloads with varying read to write ratios and data patterns. 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 practical systems. FlashDB uses a novel self-tuning index that dynamically adapts its storage structure to the workload and underlying storage device. We formalize the self-tuning nature of the 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. Our current prototype, in compact .NET framework, can run on sensor network cluster heads or gateways. We compare different indexing schemes on multiple flash devices and workloads, and show that our indexing scheme outperforms existing schemes under any workload and flash device.