Fine-grained updates in database management systems for flash memory

The growing storage capacity of flash memory (up to 640 GB) and the proliferation of small mobile devices such as PDAs and mobile phones makes it attractive to build database management systems (DBMSs) on top of flash memory. However, most existing DBMSs are designed to run on hard disk drives. The unique characteristics of flash memory make the direct application of these existing DBMSs to flash memory very energy inefficient and slow. The relatively few DBMSs that are designed for flash suffer from two major short-comings. First, they do not take full advantage of the fact that updates to tuples usually only involve a small percentage of the attributes. A tuple refers to a row of a table in a database. Second, they do not cater for the asymmetry of write versus read costs of flash memory when designing the buffer replacement algorithm. In this paper, we have developed algorithms that address both of these short-comings. We overcome the first short-coming by partitioning tables into columns and then group the columns based on which columns are read or updated together. To this end, we developed an algorithm that uses a cost-based approach, which produces optimal column groupings for a given workload. We also propose a heuristic solution to the partitioning problem. The second short-coming is overcome by the design of the buffer replacement algorithm that automatically determines which page to evict from buffer based on a cost model that minimizes the expected read and write energy usage. Experiments using the TPC-C benchmark [S.T. Leutenegger, D. Dias, A modeling study of the TPC-C benchmark, in: Proceedings of ACM SIGMOD, 1993, pp. 22-31] show that our approach produces up to 40-fold in energy usage savings compared to the state-of-the-art in-page logging approach.     

闪存的数据库性能评测与优化研究

闪存是一种诞生于上世纪八十年代末的新型固态存储介质,与其他存储介质相比,具有一定的优越性,例如轻便、小巧、速度快、功耗小、抗震性能高,且不易丢失。正是由于闪存拥有诸多优点,使得其已经被逐渐运用到各种设备与系统当中。伴随着闪存存储技术的不断发展,进一步优化闪存数据库的性能,已经成为当前一项极为重要的问题。基于此,文章将对闪存及其特性加以介绍,并对闪存数据库的性能加以评测,且据此提出相应的优化措施,以进一步完善闪存数据库的性能,最后对闪存数据库的未来发展进行展望。     

FAST: Flash-aware external sorting for mobile database systems

Recently, flash memory has gained its popularity as storage on wide spectrum of computing devices such as cellular phones, digital cameras, digital audio players and PDAs. The integration of high-density flash memory has been accelerated twice every year for past few years. As flash memory’s capacity increases and its price drops, it is expected that flash memory will be more competitive with magnetic disk drives. Therefore, it is desirable to adapt disk-based algorithms to take advantage of the flash memory technology.In this paper, we propose a novel Flash-Aware external SorTing algorithm, FAST, that overcomes the limitation of larger writing cost for flash memory to improve both overall execution time and response time. In FAST, we reduce the write operations with additional read operations. We provide the analysis for both traditional and our flash-aware algorithms by comparing the detailed cost formulas. Experimental results with synthetic and real-life data sets show that FAST can result in faster execution time as well as smaller response time than traditional external sorting algorithms.     

FeGC: An efficient garbage collection scheme for flash memory based storage systems

NAND flash memory is a promising storage media that provides low-power consumption, high density, high performance, and shock resistance. Due to these versatile features, NAND flash memory is anticipated to be used as storage in enterprise-scale systems as well as small embedded devices. However, unlike traditional hard disks, flash memory should perform garbage collection that consists of a series of erase operations. The erase operation is time-consuming and it usually degrades the performance of storage systems seriously. Moreover, the number of erase operations allowed to each flash memory block is limited. This paper presents a new garbage collection scheme for flash memory based storage systems that focuses on reducing garbage collection overhead, and improving the endurance of flash memory. The scheme also reduces the energy consumption of storage systems significantly. Trace-driven simulations show that the proposed scheme performs better than various existing garbage collection schemes in terms of the garbage collection time, the number of erase operations, the energy consumption, and the endurance of flash memory.     

One-dimensional partitioning for heterogeneous systems: Theory and practice

We study the problem of one-dimensional partitioning of nonuniform workload arrays, with optimal load balancing for heterogeneous systems. We look at two cases: chain-on-chain partitioning, where the order of the processors is specified, and chain partitioning, where processor permutation is allowed. We present polynomial time algorithms to solve the chain-on-chain partitioning problem optimally, while we prove that the chain partitioning problem is NP-complete. Our empirical studies show that our proposed exact algorithms produce substantially better results than heuristics, while solution times remain comparable.     

Genetic algorithms based approach to database vertical partition

Vertical partition clusters attributes of a relation to generate fragments suitable for subsequent allocation over a distributed platform with the goal of improving performance. Vertical partition is an optimization problem that can resort to genetic algorithms (GA). However, the performance of the classical GA application to vertical partition as well as to similar problems such as clustering and grouping suffers from two major drawbacks—redundant encoding and non-group oriented genetic operations. This paper applies the restricted growth (RG) string Ruskey (1993) constraint to manipulate the chromosomes so that redundant chromosomes are excluded during the GA process. On RG string compliant chromosomes, the group oriented crossover and mutation become realizable. We thus propose a novel approach called Group oriented Restricted Growth String GA (GRGS-GA) which incorporates the two above features. Finally, we compare the proposed approach with a rudimental RG string based approach and a classical GA based approach. The conducted experiments demonstrate a significant improvement of GRGS-GA on partition speed and result, especially for large size vertical partition problems.     

Dynamic partitioning of multiprocessor systems

Partitioning of processors on a multiprocessor system involves logically dividing the system into processor partitions. Programs can be executed in the different partitions in parallel. Optimally setting the partition size can significantly improve the throughput of multiprocessor systems. The speedup characteristics of parallel programs can be defined by execution signatures. The execution signature of a parallel program on a multiprocessor system is the rate at which the program executes in the absence of other programs and depends upon the number of allocated processors, the specific architecture, and the specific program implementation. Based on the execution signatures, this paper analyzes simple Markovian models of dynamic partitioning. From the analysis, when there are at most two multiprocessor partitions, the optimal dynamic partition size can be found which maximizes throughput. Compared against other partitioning schemes, the dynamic partitioning scheme is shown to be the best in terms of throughput when thereconfiguration overhead is low. If the reconfiguration overhead is high, dynamic partitioning is to be avoided. An expression for the reconfiguration overhead threshold is derived. A general iterative partitioning technique is presented. It is shown that the technique gives maximum throughput forn partions.     

一种改进的闪存数据库Sort-Merge-Join算法*

在对传统的Sort-Merge-Join算法进一步研究的基础上,提出了一种改进的闪存数据库Sort-Merge-Join算法。该算法只对小关系进行外排序,避免了大关系的外排序,节省了大量时间,同时最小化了中间临时表,达到了少写闪存、减小擦除代价的目的。通过理论分析和与传统Sort-Merge-Join算法在闪存上的比较实验,证明了该算法的优越性。     

A hybrid flash translation layer design for SLC-MLC flash memory based multibank solid state disk

This paper presents the design of a NAND flash based solid state disk (SSD), which can support various storage access patterns commonly observed in a PC environment. It is based on a hybrid model of high-performance SLC (single-level cell) NAND and low cost MLC (multi-level cell) NAND flash memories. Typically, SLC NAND has a higher transfer rate and greater cell endurance than MLC NAND flash memory. MLC NAND, on the other hand, benefits from lower price and higher capacity. In order to achieve higher performance than traditional SSDs, an interleaving technique that places NAND flash chips in parallel is essential. However, using the traditional FTL (flash translation layer) on an SSD with only MLC NAND chips is inefficient because the size of a logical block becomes large as the mapping address unit grows. In this paper, we proposed a HFTL (hybrid flash translation layer) which makes use of chained-blocks, combining SLC NAND and MLC NAND flash memories in parallel. Experimental results show that for most of the traces studied, the HFTL in an SSD configuration composed of 80% MLC NAND and 20% SLC NAND memories can improve performance compared to other solid state disk configurations, composed of either SLC NAND or MLC NAND flash memory alone.     

Materialisation and data partitioning algorithms for distributed RDF systems

Many RDF systems support reasoning with Datalog rules via materialisation, where all conclusions of RDF data and the rules are precomputed and explicitly stored in a preprocessing step. As the amount of RDF data used in applications keeps increasing, processing large datasets often requires distributing the data in a cluster of shared-nothing servers. While numerous distributed query answering techniques are known, distributed materialisation is less well understood. In this paper, we present several techniques that facilitate scalable materialisation in distributed RDF systems. First, we present a new distributed materialisation algorithm that aims to minimise communication and synchronisation in the cluster. Second, we present two new algorithms for partitioning RDF data, both of which aim to produce tightly connected partitions, but without loading complete datasets into memory. We evaluate our materialisation algorithm against two state-of-the-art distributed Datalog systems and show that our technique offers competitive performance, particularly when the rules are complex. Moreover, we analyse in depth the effects of data partitioning on reasoning performance and show that our techniques offer performance comparable or superior to the state of the art min-cut partitioning, but computing the partitions requires considerably less time and memory.     

A familial specification language for database application systems

The Familial Specification Language is a set theoretic and functional language providing a unified approach to the less-procedural design of database application systems. The language is proposed to be both a database language and an application program specification language. The unique data structure employed, the family of sets, provides the designer with a unified framework, both to model and maintain data, and to algebraically specify the application programs without looping or branching, and with no side effects. Using the same data structure in both the data model and the problem specification creates a natural interface between the database and the application programs. Special emphasis is placed on aggregation and classification, the major problems is business data processing.     

PORCE: An efficient power off recovery scheme for flash memory

Flash memory is now replacing hard disk in many embedded applications including cellular phones, digital cameras, car navigation systems, and so on. However, because flash memory has its own characteristics such as “erase-before-write” and wear-leveling, a software layer called FTL (flash translation layer) should be provided. However, most FTL algorithms did not include the power off recovery module though it is very important in portable devices. In this paper, we suggest an efficient power off recovery scheme for flash memory called PORCE (Power Off Recovery sChEme for flash memory). PORCE is tightly coupled to FTL operations and minimizes performance degradation during normal operations by storing recovery information as small as possible. Additionally, PORCE provides cost-based reclamation protocols which include the wear-leveling module. Our empirical study shows that PORCE is an efficient recovery protocol.     

Four reference architectures for distributed database management systems

Five requirements for a centralized database management system and five additional requirements for a distributed database management system suggest definitions of software processors and schemas. These software processors and schemas can be organized into four reference architectures for distributed database management systems which permit comparisons of their advantages and disadvantages.     

A B-Tree index extension to enhance response time and the life cycle of flash memory

Flash memory has critical drawbacks such as long latency of its write operation and a short life cycle. In order to overcome these limitations, the number of write operations to flash memory devices needs to be minimized. The B-Tree index structure, which is a popular hard disk based index structure, requires an excessive number of write operations when updating it to flash memory. To address this, it was proposed that another layer that emulates a B-Tree be placed between the flash memory and B-Tree indexes. This approach succeeded in reducing the write operation count, but it greatly increased search time and main memory usage. This paper proposes a B-Tree index extension that reduces both the write count and search time with limited main memory usage. First, we designed a buffer that accumulates update requests per leaf node and then simultaneously processes the update requests of the leaf node carrying the largest number of requests. Second, a type of header information was written on each leaf node. Finally, we made the index automatically control each leaf node size. Through experiments, the proposed index structure resulted in a significantly lower write count and a greatly decreased search time with less main memory usage, than placing a layer that emulates a B-Tree.     

On a human-centred approach to database systems

It is often illuminating to view a technology or a methodology from a novel perspective, thereby assessing it with criteria which are likely to differ markedly from those used by its designers. In this paper we review current database design methodology and, implicitly, database technology. We attempt to show that both are founded on an information-centred philosophy, and that the consequences of this view are significant and unsatisfactory. We investigate an alternative, human-centred philosophy and relate this to the more limited scope of a user-centred view which evolves from our analysis.     

Parallel partitioning for distributed systems using sequential assignment

This paper introduces a method to combine the advantages of both task parallelism and fine-grained co-design specialisation to achieve faster execution times than either method alone on distributed heterogeneous architectures. The method uses a novel mixed integer linear programming formalisation to assign code sections from parallel tasks to share computational components with the optimal trade-off between acceleration from component specialism and serialisation delay. The paper provides results for software benchmarks partitioned using the method and formal implementations of previous alternatives to demonstrate both the practical tractability of the linear programming approach and the increase in program acceleration potential deliverable.     

Data loss recovery for power failure in flash memory storage systems

Due to the rapid development of flash memory technology, NAND flash has been widely used as a storage device in portable embedded systems, personal computers, and enterprise systems. However, flash memory is prone to performance degradation due to the long latency in flash program operations and flash erasure operations. One common technique for hiding long program latency is to use a temporal buffer to hold write data. Although DRAM is often used to implement the buffer because of its high performance and low bit cost, it is volatile; thus, that the data may be lost on power failure in the storage system. As a solution to this issue, recent operating systems frequently issue flush commands to force storage devices to permanently move data from the buffer into the non-volatile area. However, the excessive use of flush commands may worsen the write performance of the storage systems. In this paper, we propose two data loss recovery techniques that require fewer write operations to flash memory. These techniques remove unnecessary flash writes by storing storage metadata along with user data simultaneously by utilizing the spare area associated with each data page.     

Using database machines in embedded computer systems

A discussion whether or not present database machine technology addresses the needs of embedded computer systems is presented. The interface between the embedded system and its environment tends to be complex, asynchronous, highly parallel and sometimes distributed. In addition, embedded systems are likely to have stringent resource requirements, both physical and logical. An answer to both the complexity issue and the resource limitation can be potentially found in the database machine.Functions are identified for two applications that the embedded system in general and the database machine specifically are asked to perform. Given the requirements of such applications the current database machine technology is evaluated.Finally, given the primary requirements of data security and system throughput of tactical embedded computer systems, a database machine using distributed architecture is proposed. The system has the potential for connecting multiple database machines to each host or for connecting multiple hosts to one database machine.