Research On Buffer Management Algorithms For Flash Memory

As a novel solid-state storage medium, flash memory has been widely used as storage medium for embedded systems and portable devices in recent years, due to its small size, lightweight, non-volatile, high speed, shock-resistance, and less energy consumption. New challenges are posed by the distinct physical characteristics of flash memory to the data management technology, such as flash-based storage management, flash-aware index management and flash-aware buffer management. Among them, buffer manager has been the research focus for the field of flash-based database in recent years,which is an important and very effective method for improving the access performance of flash memory,.However, current available buffer replacement policies are most based on the traditional magnetic disk, they do not consider the characteristics of flash memory which are different from magnetic disk, and only focus on improving the hit ratio, if they are directly applied to flash memory, the total costs for accessing flash memory may be very high. So, researches on effective and flash-aware buffer replacement policy have important significance for reducing the costs for accessing flash memory.First, the dissertation summarized the existing buffer manager algorithms for flash memory, then analyzed the key issues of flash-aware buffer management, and mainly studied the buffer replacement policy, finally given some means to solve relevant problems. Concretely speaking, the main research works of this dissertation can be summarized as follows:1. The dissertation proposes a novel buffer replacement algorithm for flash-memory-based systems, called CCF-LRU. The new algorithm uses two LRU lists to maintain the buffer pages, where a cold-clean LRU list stores the cold clean pages, and a mixed LRU list places dirty pages and hot clean pages. When the buffer space is insufficient, it first evicts the LRU page in the cold clean list, or in case that the cold clean list is empty, it evicts the cold dirty page in the mixed LRU list. Using this strategy, replacement algorithm CCF-LRU can effectively prevent clean page accessed only once recently from polluting the buffer, and thus reduces the number of flash write operation; moreover, it reduces the number of flash write operations as well as holds higher hit ratio, and thus improves the access performance of flash memory.2. In order to solve the 0-1 jump problem in the replacement algorithm CCF-LRU, we improve on the replacement algorithm CCF-LRU and propose a new replacement algorithm called controllable cold clean first replacement policy, CCCF-LRU for short. Unlike replacement algorithm CCF-LRU, replacement algorithm CCCF-LRU limits the length of cold clean LRU list in the buffer, and stipulates that its length is not less than minCCL, otherwise it selects the cold dirty pages from the mixed LRU list as victim. Compared with CCF-LRU, replacement algorithm CCCF-LRU can prevent the clean pages which are initially loaded into buffer and will be frequently accessed from being evicted quickly, it increases a little amount of flash write operations but significantly improves the hit ratio, and thus improves the access performance of flash memory.