Storage Management And Index Method On Flash Memory Storage Systems

Flash memory is a non-volatile storage device, which has been widely used in storage systems because of its small size, shock resistance, low power consumption, lightweight and fast read performance. With recent technology breakthroughs, especially large increases in capacity, flash memory is considered as the best alternative for hard disk in many applications, such as embedded systems, mobile devices, and enterprise computing environments. Compared with disk, flash memory has many distinct characteristics:a flash block is the smallest unit of flash erases, all flash reads and writes are done at the page granularity, the cost of a flash write is much larger than a flash read, an erase operation must be done before rewriting the same place, and each block has a limited number of erasing. Due to these programming characteristics, the original data management designed for disk can not be used in the flash memory system directly, or the performance of flash memory storage system is rather poor. Therefore, many researches have been done over the flash memory systems, and gains great significance. Our paper mainly focuses on the management of flash memory storage system and the index structure over flash memory.The storage management of flash memory is the infrastructure of other applications and has a great impact on the performance of flash memory systems. Firstly, this paper proposes a novel implementation of flash memory storage systems (namely FMSS) with considerations of the programming restrictions and the poor reliability of the MLC flash memory. FMSS is a flexible flash memory management scheme with multiple granularities. Since NOR flash can be accessed in a word or byte, FMSS puts some critical data into NOR flash to increase the performance of flash memory storage system. Secondly, we propose a novel I/O scheduler (namely MBF) over flash memory system to increase the I/O performance and prolong the lifetime of flash memory. MBF scheduler reorders the pending requests and assigns a higher priority to read requests. A flexible bank assignment policy is proposed to assign write requests into proper banks according to the attributes of requests to provide rather uniform erase counts and capacity utilizations among different banks. An efficient index structure is critical to improve the performance of flash memory systems. The log implementation of B+ -tree over flash memory (BFTL) has a poor query performance. This paper proposes a method to adapt the node storage structure of BFTL dynamically to improve the overall performance of BFTL. At last, we propose a novel implementation of a multi-dimensional index strucuter (K-D-B-tree) over flash memory, namely F-KDB, which handles the fine-granularity updates efficiently. Then, an online algorithm is introduced to improve the query performance.