روشی کارآمد برای مدیریت سوابق در محیط حافظه فلش

Flash memory has its unique characteristics: the write operation is much more costly than the read operation, and in-place updating is not allowed. In this paper, we analyze how these characteristics affect the performance of clustering and non-clustering methods for record management, and show that non-clustering is more suitable in flash memory environment. Also, we identify the problems of the existing non-clustering method when applied to flash memory environment without any modification, and propose an effective method for record management in flash memory databases. This method, which is basically based on the non-clustering method, tries to store consecutively inserted records in the same page in order to make it possible to process them with only one write operation. In this paper, we call this method group write. Moreover, we propose two novel techniques for achieving efficient group writes: (1) dedicated buffers for group writes and (2) free space lists managed in main memory for maintaining only those pages having large free space. Our method greatly improves the write performance of database applications running in flash memory. For performance evaluation, we conduct a variety of experiments. The results show that our method achieves speed up by up to 1.67 times compared with the original non-clustering method.

Characterized by low power consumption, non-volatility, and high mobility, flash memory is widely used as storage media for mobile devices [7]. Unlike other storage media, flash memory has its unique characteristics: first, the difference between speeds of read and write operations is significant with flash memory [4] and [8]. Second, the physical characteristic of flash memory makes the in-place update impossible. To update data, its containing page1 has to be invalidated first, and then newly updated data is written onto a different physical page [28] and [30]. Third, flash memory requires the erase operation to resume the invalidated page. The erase operation requires a very high cost and occurs mainly due to frequent write operations, particularly when updating existing pages [14]. Therefore, it is very important to reduce the number of write operations in flash memory. Recently, as a capacity of flash memory grows rapidly, the application of flash memory as alternative storage media to disk is increasing. This naturally raised the necessity of studies for flash-based DBMSs to find out ways that allow to efficiently store and manage massive data directly on flash memory. With a proper software layer such as Flash Translation Layer (FTL), which makes flash memory behave as a block device like disk, we can employ the same methods used in conventional disk-based DBMSs without any modification [16]. However, conventional disk-based DBMSs do not consider the characteristics of flash memory at all, this approach fails to provide good performance. In order to overcome such limitations, researches on flash-based DBMSs have been performed. A typical storage system in a conventional DBMS consists of five layers: storage, buffer, index, record, and scan management layers [9]. Previous studies mainly focused on the prior three layers, i.e., flash-aware methods for storage [7] and [15], buffer [18], [19] and [20], and index [1] and [17] management. However, to the extent of our knowledge, there have been no previous studies on a record management method that handles the insertion, deletion, and placement of records, and significantly affects the overall performance of a DBMS. Two types of record management methods are widely used in disk-based DBMSs: clustering and non-clustering [9]. With the clustering method, records with similar key values are stored at physically adjacent pages. Whereas, with the non-clustering method, records are stored at pages having available space regardless of their key values. In disk-based DBMSs, the clustering method is more popular than the non-clustering one because the performance of range queries can be significantly improved if the records of similar key values are stored in the same or physical adjacent pages [9]. Since the location of a record in the clustering method is totally determined by its key value, the insertion of n records generally places them into n different pages, respectively, hence requiring n page accesses. As a result, it normally incurs n write operations. Such a task would not pose any problem in disk environment. However, it causes serious problems in flash memory environment due to the speed difference between read and write operations [2]. Furthermore, they incur frequent erase operations since most of write operations for record insertions are to update pages. On the other hand, in case of the non-clustering method, its inefficiency in range query processing would be compensated by the high speed of a read operation in flash memory. The non-clustering method is also expected to show superior performance of record insertions owing to the buffering effect that reduces the number of write operations and also the number of erase operations [2]. Through extensive preliminary experiments, this paper indeed shows the superiority of the non-clustering method over the clustering counterpart in overall performance in flash memory. However, there still arise several problems with the non-clustering method because it was not specifically designed to cater for the characteristics of flash memory. First, a number of write operations may be required in the same page, due to buffer replacement. Second, the free space list is frequently updated in case of the repetition of record insertions and deletions. The management of a free space list is used in both clustering and non-clustering methods for maintaining those pages that contain free space for future record insertions [9]. Since pointers to form a list are stored within pages in disk-based DBMSs [9], this makes any modification of the list necessitate write operations on pages, too. Thus, the management of a free space list could incur serious performance degradation in flash memory environment. In this paper, we propose an effective Flash-Aware Record Management (FARM) method. This method is basically based on the non-clustering method, and tries to store consecutively inserted records in the same page, thereby making it possible to store them with only one write operation. In this paper, we call this method as group write. For efficient support of group writes, we propose a dedicated buffer for group write and a free space list for maintaining in main memory only a small number of pages having large free space. To show the superiority of the proposed method, we conduct a variety of experiments for performance evaluation. The results show that our method achieves speed up by up to 67% compared with the original non-clustering method. This paper consists of the followings: in Section 2, characteristics of flash memory and related work on flash-based DBMSs are introduced. And the difference between related work and our proposed method is explained. In Section 3, as existing record management methods, clustering and non-clustering methods are explained and their new problems arising in flash memory environment are addressed. In Section 4, performance analysis on clustering and non-clustering methods in flash memory environment are presented. In Section 5, our new method is described in detail. In Section 6, performance analysis is conducted to verify the superiority of our proposed method. Finally, in Section 7, this paper is wrapped up with conclusions.

The processing speeds of read, write, and erase operations are quite different from one another in flash memory. The writing operation, in particular, subsequently requires the very costly erase operation and is also a major factor for shortening of service life of flash memory. This implies that the optimization of writing operations is crucial for performance improvement on flash memory environment. In this paper, we have evaluated the performance of clustering and non-clustering methods in flash memory environment, and proposed a novel flash-based method for record management. The contributions of this paper are as follows: • First, we analyzed how physical characteristics of flash memory affect the performance of clustering and non-clustering methods, and have shown the superiority of the non-clustering method through extensive experiments. The non-clustering method outperforms the clustering method in flash memory environment since performance improvement by reducing write and erase operations is greater than performance degradation in processing range queries. • Second, we discussed the problems of the non-clustering method newly arising in flash memory environment. In spite of the superiority of the non-clustering method in flash memory environment, there are some factors deteriorating performance. In the non-clustering method, the buffer replacement strategy may cause repetitive writing operations when multiple records are inserted. Also, the free space list has to be updated frequently by repetitive insertions and deletions. • Third, we proposed a novel record management method for flash memory called an FARM method. The FARM method tries to store consecutively inserted records in the same page in order to make it possible to store them with only one write operation. In this paper, we call this method group write. Also, we have proposed the dedicated buffer and the k-LASL to support efficient group writes. • Fourth, we verify the superiority of the FARM method by conducting extensive experiments. The results show that our method achieves speed up by up to 67% compared with the original non-clustering method.