NAND flash-based SSDs have become attractive alternatives to hard disk drivers due to their high random read performances and low power consumptions. However, the poor random write performances highly limit their popularization in commercial applications. In this paper, we propose a novel mapping scheme called hybrid mapping unsorted block images (hUBI). hUBI aims for (1) optimized random write performances, (2) low write laten- cies, and (3) low space consumptions. It optimizes traditional hybrid mapping schemes to achieve (1). In hUBI, the merge operation involves only a single block. So, (2) is guaranteed. To avoid introducing a high space cost maintaining the metadata, hUBI puts its metadata into out-of-band (OOB) areas of SSD pages, which obtains (3). Our experimental results show that hUBI provides a considerable random write performance and holds low write latencies at the same time.

Major web search engines answer thousands of queries per second requesting information about billions of web pages. The data sizes and query loads are growing at an exponential rate. To manage the heavy workload, we consider techniques for utilizing a Graphics Processing Unit (GPU). We investigate new approaches to improve two important operations of search engines -- lists intersection and index compression. For lists intersection, we develop techniques for efficient implementation of the binary search algorithm for parallel computation. We inspect some representative real-world datasets and find that a sufficiently long inverted list has an overall linear rate of increase. Based on this observation, we propose Linear Regression and Hash Segmentation techniques for contracting the search range. For index compression, the traditional d-gap based compression schemata are not well-suited for parallel computation, so we propose a Linear Regression Compression schema which has an inherent parallel structure. We further discuss how to efficiently intersect the compressed lists on a GPU. Our experimental results show significant improvements in the query processing throughput on several datasets.

In this paper, we study longest lowest-density MDS codes, a simple kind of multi-erasure array code with optimal redundancy and minimum update penalty. We prove some basic structure properties for longest lowest-density MDS codes. We define a "perfect" property for near-resolvable block designs (NRBs) and establish a bijection between 3-erasure longest lowest-density MDS codes (T-Codes) and perfect NRB(3¿ + 1, 3, 2)s. We present a class of NRB(3¿+1, 3, 2)s, and prove that it produces a family of T-Codes. This family is infinite assuming Artin¿s Conjecture. We also test some other NRBs and find some T-Code instances outside of this family.

Peer-to-peer distributed storage systems aggregate the storage space of many peers spread over the Internet. Due to the dynamic and scalable nature of these systems, it is a challenging issue to access data in an available and reliable way through redundancy. Following the modeling methodology presented, we present the stochastic model to analyze redundancy evolution of these systems under churn. Different from the previous work based on the average peer availability, the stochastic model can be applied into the practice based on both conditional probabilities (alpha, theta) which can be obtained from network probing easily. First, we apply the model to characterize the redundancy evolution of a fragment system with temporary churn. Then, we use an empirical trace and a synthetic trace to validate the model. Second, based on the characteristics of different churn from the both probabilities, we propose the redundancy maintenance strategy assisted by network sampling. Our simulations evaluate the performance of the strategy driven by empirical and synthetic traces.

X-code is an important 2-erasure correcting vertical array code. In this paper, we present a combinatorial representation for X-code. It is based on graph representation of binary linear/array codes. We represent X-code by Cayley tables of the cyclic groups of prime order - a special column-Hamiltonian Latin squares (CHLS). This representation is helpful to comprehend X-code's 2-erasure correcting ability. We also show the inner relationship between X-code and the liberation codes though the former is a vertical code and the latter is a horizontal code. A possible way to construct the 2-erasure vertical codes like X-code using common CHLS is also proposed.

An object-oriented storage system NLOV (network logical object volume) based on BerkeleyDB is implemented. It provides a block level object-oriented storage interface. It uses NBD and AOE as transport protocols and supports interoperation between the two protocols. Compared with other object-oriented storage system, such as Lustre and Ceph, NLOV has good simplicity, better flexibility and applicability. Some experiments are also done to examine the performance of NLOV.

Deep reactive ion etching (DRIE) technique is a new and powerful tool in micro-electro-mechanical systems (MEMS) fabrication. A 3-D DRIE simulation can help researcher understand the time-evolution of Bosch process used in DRIE. Due to the high complexity of the algorithm used in the simulation, it is necessary to develop an algorithm that can speedup the simulation. This paper presents a parallel implementation of the 3-D DRIE simulation based on multi-core processor. The algorithm is based on data partition. We examine four different data partition strategies and find two-dimensional block-cyclic distribution can obtain perfect load balance. The experimental results show that the parallel algorithm obtains a substantial speedup over the serial algorithm on an Intel quad-core computer.

Storage applications are in urgent need of multi-erasure codes. But there is no consensus on the best coding technique. Hafner has presented a class of multi-erasure codes named HoVer codes [1]. This kind of codes has a unique data/parity layout which provides a range of implementation options that cover a large portion of the performance/efficiency trade-off space. Thus it can be applied to many scenarios by simple tuning. In this paper, we give a combinatorial representation of a family of double-erasure HoVer codes - create a mapping between this family of codes and Latin squares. We also present two families of double-erasure HoVer codes respectively based on the column-Hamiltonian Latin squares (of odd order) and a family of Latin squares of even order. Compared with the double-erasure HoVer codes presented in [1], the new codes enable greater flexibility in performance and efficiency trade-off.

In this paper, we present PDH Latin - a new class of 2-erasure horizontal codes with dependent parity symbols based on column-Hamiltonian Latin squares (CHLS). We prove that PDH Latin codes are MDS codes. We also present a new class of 2-erasure parity independent mixed codes based on CHLS - PIMLatin. We show that the performance of the new codes is comparable to or better than other codes of this kind. They have perfect parameter flexibility and structure variety that benefit performance. We also discuss code shortening technologies that can improve parameter flexibility, structure variety and reliability. Borrowing ideas from vertical shortening, we develop a 2-erasure array code construction method using non-Hamiltonian Latin squares.

In recent years, multi-erasure correcting coding systems have become more pervasive. RAID6 is an important 2-erasure correcting code specification. But there is no consensus on the best concrete RAID6 coding scheme. Plank developed a brand new class of RAID6 codes called the Liberation codes that achieves good encoding, updating and decoding performance. In this paper, we present a chained decoding algorithm for the Liberation codes. Its performance is comparable with the bit matrix scheduling algorithm developed by Plank, but is more intuitive and reveals the essence better. In the process, we present a new class of Liberation codes called the Latin Liberation codes. These codes are based on column-hamiltonian Latin squares, hence the name. They are superior to the Liberation codes in parameter flexibility and structure flexibility. Finally, we analyze the performance of several XOR-based RAID6 codes and give some suggestion on their application.

This paper analyzes churn impact on replicated data duration with different node lifetime distributions. In structured overlay networks, churn includes node-join churn and node-failure churn, caused by the arrival and departure of nodes separately. The paper introduces a duration model of replicated data under node-failure churn for node failure directly leads to data loss. Furthermore, it investigates the impact of node-join churn on the duration of replicated data for different node-lifetime distributions. The paper presents that node-churn will negatively impact on replicated data duration for heavy-tailed distribution and Weibull distribution except exponential distribution. Then we evaluate the impact on replicated data duration with two real-world trace datasets. The experimental results show the negative impact of node-join churn for different node-join churn degrees. Finally, the paper discusses an enhancement by setting a trial period for every fresh node. By experiment, it is an effective way to reduce the negative impact of node-join churn due to the memory property of node lifetime distributions.

In this paper, we propose an innovative debugging tool called MKtrace to help programmers identify bugs in multi-threaded programs on multiprocessor systems with little overhead. Unlike the traditional debugging tools, we use the trace log to analyze the cause of a crash or any abnormal behaviour. Bugs can be identified within the log file, not directly at run time. Also, a key advantage of MKtrace is its insignificant overhead. The main idea of MKtrace is to monitor all the processes or threads from a program when they switch out in the kernel. We log the call stack of each thread, and then we analyze the log in the user space. We implemented MKtrace on Linux AS3 with two processors and achieved promising results during our experiments.

HTC (high throughput computing) is a environment that can provide large amounts of processing capacity over long periods of time. To HTC, users are more concerned about how many jobs can be completed in a long period, but not how fast can a single job be finished. Condor, an implementation of HTC, is constructed by commodity CPUs and memory. As long as the Condor nodes are controlled by the Central Management Node, its reliability and scalability had been restricted. Based on the concept of DHT (distributed hash table), this paper presents a new distributed HTC architecture, named CrossTree, which has no central parts, and its metadata is distributed across all nodes in the system. Theoretical analysis and the simulation results proved CrossTree to be an efficient architecture with high scalability and reliability.

With the rapid progress of the capacity and slow pace of the speed/MTTF of hard disks, and increasing size of storage systems, the reliability and availability of storage systems become more and more serious. This paper discusses the method of constructing double- and triple-erasure-correcting codes via combining mirroring and parity approaches in details, and presents a double-erasure code MPDC and a triple-erasure code MPPDC based on one-factorizations of complete graphs. The two codes are simple, easy to implement, and have no disk number limitation. They achieve perfect fault-free load balance and approximately optimal reconstruction load balance. The simulation results show that, compared with other double- and triple-erasure codes, MPDC and MPPDC have comparative light-load and moderate-load performance and better heavy-load performance in fault-free mode. Because parity declustering is used, the two codes are far superior to the other double- and triple-erasure codes in degraded- and reconstruction-mode performance.

In this paper, we present a new class of t-erasure horizontal codes with independent parity symbols based on Column-Hamiltonian Latin squares (CHLS). We call the codes PIHLatin (parity independent horizontal Latin) codes. We prove the necessary and sufficient condition of the existence of PIHLatin codes for t=2. For tges3, we prove some necessary conditions of the existence of PIHLatin codes. We also prove the bijection between 2-erasure PIHLatin-like codes and CHLSs and prove the mapping from t-erasure PIHLatin-like codes to t-1 mutually orthogonal CHLSs for t>2. The performance analysis shows that PIHLatin codes are superior to other multi-erasure array codes in flexibility and variety. Moreover, PIHLatin codes are suitable for both traditional disk arrays and distributed storage systems.

For practical deployment of peer-to-peer (P2P) systems, it is one of the most important and challengeable aspects to achieve high data availability in structured P2P systems since the environment is much scalable and dynamic. The paper utilizes the hybrid of two data redundancy schemes, namely replication and erasure coding, to improve system availability. To mask or hide the high churn from the short-lived but churn-frequent peers and permanent failure peers, we use replication among the nodes in a certain interval of the identifier space that can be considered as a virtual node. Then with an erasure-coded redundancy scheme, we consider that a set of virtual nodes that cooperatively provide guaranteed over the networks. The paper presents the hybrid redundancy prototype and protocol. The evaluation shows that the approach is effective with an empirical trace by setting different system parameters.

Previous work on performance of network storage system has been mostly qualitative. This work proposes a quantitative analytical method based on closed queueing networks in order to analyze the performance bounds of IP-SWAN (storage wide area network) based on distributed network software RAID (NS-RAID). Experimental results show that testing results are within the bounds predicted by the performance analysis model and the bounds reflect the dynamic trend of the actual testing performance. Furthermore, the bottleneck and the potential bottleneck that affect the IP-SWAN performance can be derived from the performance analysis model. Meanwhile the model provides us with the criteria for distinguishing the key performance factors and non-key performance factors.