Merging sorted runs using large main memory

Summary External sorting is usually accomplished by first creating sorted runs, then merging the runs. In the merge phase, writing and calculating can be overlapped by reading if two input buffers are used for each sorted run. If the memory is very large, the input buffers will be large and using two input buffers per sorted run will be more efficient than using only one input buffer per run and risking reduced overlap of reading and writing. In many cases, merging time can be cut in half. We derive a formula for estimating the total time for merging for a given memory size, file size, number of merging passes and for a given disk drive. We present an extreme example where in spite of having two buffers per run, significant non-overlap occurs. However, in realistic problems, we show that making one merge pass with two input buffers per run is near optimal. This contradicts earlier results on merging which do not take large memory into account.     

A Simple and Efficient Parallel Disk Mergesort

External sorting—the process of sorting a file that is too large to fit into the computer's internal memory and must be stored externally on disks—is a fundamental subroutine in database systems[G], [IBM]. Of prime importance are techniques that use multiple disks in parallel in order to speed up the performance of external sorting. The simple randomized merging (SRM ) mergesort algorithm proposed by Barve et al. [BGV] is the first parallel disk sorting algorithm that requires a provably optimal number of passes and that is fast in practice. Knuth [K,Section 5.4.9] recently identified SRM (which he calls ``randomized striping') as the method of choice for sorting with parallel disks. In this paper we present an efficient implementation of SRM, based upon novel and elegant data structures. We give a new implementation for SRM's lookahead forecasting technique for parallel prefetching and its forecast and flush technique for buffer management. Our techniques amount to a significant improvement in the way SRM carries out the parallel, independent disk accesses necessary to read blocks of input runs efficiently during external merging. Our implementation is based on synchronous parallel I/O primitives provided by the TPIE programming environment[TPI]; whenever our program issues an I/O read (write) operation, one block of data is synchronously read from (written to) each disk in parallel. We compare the performance of SRM over a wide range of input sizes with that of disk-striped mergesort (DSM ), which is widely used in practice. DSM consists of a standard mergesort in conjunction with striped I/O for parallel disk access. SRM merges together significantly more runs at a time compared with DSM, and thus it requires fewer merge passes. We demonstrate in practical scenarios that even though the streaming speeds for merging with DSM are a little higher than those for SRM (since DSM merges fewer runs at a time), sorting using SRM is often significantly faster than with DSM (since SRM requires fewer passes). The techniques in this paper can be generalized to meet the load-balancing requirements of other applications using parallel disks, including distribution sort and multiway partitioning of a file into several other files. Since both parallel disk merging and multimedia processing deal with streams that get ``consumed' at nonuniform and partially predictable rates, our techniques for lookahead based upon forecasting data may have relevance in video server applications. Received June 28, 2000, and in revised form June 5, 2001. Online publication April 8, 2002.     

External sorting: run formation revisited

External mergesort begins with a run formation phase creating the initial sorted runs. Run formation can be done by a load-sort-store algorithm or by replacement selection. A load-sort-store algorithm repeatedly fills available memory with input records, sorts them, and writes the result to a run file. Replacement selection produces longer runs than load-sort-store algorithms and completely overlaps sorting and I/O, but it has poor locality of reference resulting in frequent cache misses and the classical algorithm works only for fixed-length records. This paper introduces batched replacement selection: a cache-conscious version of replacement selection that works also for variable-length records. The new algorithm resembles AlphaSort in the sense that it creates small in-memory runs and merges them to form the output runs. Its performance is experimentally compared with three other run formation algorithms: classical replacement selection, Quicksort, and AlphaSort. The experiments show that batched replacement selection is considerably faster than classic replacement selection. For small records (average 100 bytes), CPU time was reduced by about 50 percent and elapsed time by 47-63 percent. It was also consistently faster than Quicksort, but it did not always outperform AlphaSort. Replacement selection produces fewer runs than Quicksort and AlphaSort. The experiments confirmed that this reduces the merge time whereas the effect on the overall sort time depends on the number of disks available.     

A performance model for preplanned disk sorting

The idea of preplanning strings on disks which are merged together is investigated from a performance point of view. Schemes of internal buffer allocation, initial string creation by an internal sort, and string distribution on disks are evaluated. An algorithm is given for the construction of suboptimal merge trees called plannable merge trees. A cost model is presented for accurate preplanning which consists of detailed assumptions on disk allocation fork input disks andr-way merge planning. Timing considerations for sort and merge including hardware characteristics of moveable head disks show a significant gain of time compared to widely used sort/merge applications.     

Tight bounds for prefetching and buffer management algorithms forparallel I/O systems

The I/O performance of applications in multiple-disk systems can be improved by overlapping disk accesses. This requires the use of appropriate prefetching and buffer management algorithms that ensure the most useful blocks are accessed and retained in the buffer. In this paper, we answer several fundamental questions on prefetching and buffer management for distributed-buffer parallel I/O systems. First, we derive and prove the optimality of an algorithm, P-min, that minimizes the number of parallel I/Os. Second, we analyze P-con, an algorithm that always matches its replacement decisions with those of the well-known demand-paged MIN algorithm. We show that P-con can become fully sequential in the worst case. Third, we investigate the behavior of on-line algorithms for multiple-disk prefetching and buffer management. We define and analyze P-Iru, a parallel version of the traditional LRU buffer management algorithm. Unexpectedly, we find that the competitive ratio of P-Iru is independent of the number of disks. Finally, we present the practical performance of these algorithms on randomly generated reference strings. These results confirm the conclusions derived from the analysis on worst case inputs     

Practical prefetching techniques for multiprocessor file systems

Improvements in the processing speed of multiprocessors are outpacing improvements in the speed of disk hardware. Parallel disk I/O subsystems have been proposed as one way to close the gap between processor and disk speeds. In a previous paper we showed that prefetching and caching have thepotential to deliver the performance benefits of parallel file systems to parallel applications. In this paper we describe experiments withpractical prefetching policies that base decisions only on on-line reference history, and that can be implemented efficiently. We also test the ability of those policies across a range of architectural parameters.     

Issues in the design of a storage server for video-on-demand

We examine issues related to the design of a storage server for video-on-demand (VOD) applications. The storage medium considered is magnetic disks or arrays of disks. We investigate disk scheduling policies, buffer management policies and I/O bus protocol issues. We derive the number of sessions that can be supported from a single disk or an array of disks and determine the amount of buffering required to support a given number of users. Furthermore, we propose a scheduling mechanism for disk accesses that significantly lowers the buffer-size requirements in the case of disk arrays. The buffer size required under the proposed scheme is independent of the number of disks in the array. This property allows for striping video content over a large number of disks to achieve higher concurrency in access to a particular video object. This enables the server to satisfy hundreds of independent requests to the same video object or to hundreds of different objects while storing only one copy of each video object. The reliability implications of striping content over a large number of disks are addressed and two solutions are proposed. Finally, we examine various policies for dealing with disk thermal calibration and the placement of videos on disks and disk arrays.     

Strip-oriented asynchronous prefetching for parallel disk systems

Sequential prefetching schemes are widely employed in storage servers to mask disk latency and improve system throughput. However, existing schemes cannot benefit parallel disk systems as expected due to the fact that they ignore the distinct internal characteristics of the parallel disk system, in particular, data striping. Moreover, their aggressive prefetching pattern suffers from premature evictions and prolonged request latencies. In this paper, we propose a strip-oriented asynchronous prefetching (SoAP) technique, which is dedicated to the parallel disk system. It settles the above-mentioned problems by providing multiple novel features, e.g., enhanced prediction accuracy, adaptive prefetching strength, physical data layout awareness, and timely prefetching. To validate SoAP, we implement a prototype by modifying the software redundant arrays of inexpensive disks (RAID) under Linux. Experimental results demonstrate that SoAP can consistently offer improved average response time and throughput to the parallel disk system under non-random workloads compared with STEP, SP, ASP, and Linux-like SEQPs.     

Alphasort: A cache-sensitive parallel external sort

A new sort algorithm, called AlphaSort, demonstrates that commodity processors and disks can handle commercial batch workloads. Using commodity processors, memory, and arrays of SCSI disks, AlphaSort runs the industrystandard sort benchmark in seven seconds. This beats the best published record on a 32-CPU 32-disk Hypercube by 8:1. On another benchmark, AlphaSort sorted more than a gigabyte in one minute. AlphaSort is a cache-sensitive, memoryintensive sort algorithm. We argue that modern architectures require algorithm designers to re-examine their use of the memory hierarchy. AlphaSort uses clustered data structures to get good cache locality, file striping to get high disk bandwidth, QuickSort to generate runs, and replacement-selection to merge the runs. It uses shared memory multiprocessors to break the sort into subsort chores. Because startup times are becoming a significant part of the total time, we propose two new benchmarks: (1) MinuteSort: how much can you sort in one minute, and (2) PennySort: how much can you sort for one penny.     

一种面向视频播放系统的RAID并行预取技术及实现

随着视频数字化技术的广泛应用，视频播放系统中的存在“瓶颈”也日益突出，在分析视频存储系统磁盘阵列的I／O调度算法和在实际应用中视频数据的特点的基础上，提出一种面向视频媒体服务的RAID并行预取实时调度算法，它利用未来数据的可行预测性，预先将其从磁盘取入缓冲区，同时优化任务调度，使主机数据的回送和从磁盘预取数据同步执行，进一步提高了阵列的I／O吞吐率，用I／Ometer测试结果证明，新算法具有很好的性能。     

Web object-based storage management in proxy caches

Proxy caches are essential to improve the performance of the World Wide Web and to enhance user perceived latency. Appropriate cache management strategies are crucial to achieve these goals. In our previous work, we have introduced Web object-based caching policies. A Web object consists of the main HTML page and all of its constituent embedded files. Our studies have shown that these policies improve proxy cache performance substantially.In this paper, we propose a new Web object-based policy to manage the storage system of a proxy cache. We propose two techniques to improve the storage system performance. The first technique is concerned with prefetching the related files belonging to a Web object, from the disk to main memory. This prefetching improves performance as most of the files can be provided from the main memory rather than from the proxy disk. The second technique stores the Web object members in contiguous disk blocks in order to reduce the disk access time. We used trace-driven simulations to study the performance improvements one can obtain with these two techniques. Our results show that the first technique by itself provides up to 50% reduction in hit latency, which is the delay involved in providing a hit document by the proxy. An additional 5% improvement can be obtained by incorporating the second technique.     

THSORT:单机并行排序算法

排序是计算机事务处理的重要操作之一.前人已经就内部排序、外部排序和并行排序提出各种方法.从一种全新的视角研究了排序算法,提出一种在单机上实现的并行排序算法THSORT(Tsinghua SORT).它用多个进程分别控制不同的硬件部件,使输入、排序和输出能够同时进行,从而大大提高了硬件部件的并行性和运行效率.在带有双磁盘阵列的硬件平台上进行的测试表明,THSORT的性能达到了NTSORT(new technology SORT)的1倍左右,并成为2002年PennySort(Daytona类)世界排序纪录的保持者.     

Storage System for Supporting More Video Streams in Video Server

Video server needs a storage system with large bandwidth in order to provide concurrently more users with the real time retrieval requests for video streams. So, the storage system generally has the structure of disk array, which consists of multiple disks. When the storage system serves multiple video stream requests, it's bottlenecks come from the seeking delay caused by the random movement of disk head and from unbalanced disk access due to disk load unbalance among multiple disks.This paper presents a novel placement and retrieval policy. The new policy retrieves the requested data through sequential movement of disk heads and maintaining disk load balance so that it can diminish the bottlenecks on retrieving and can provide the concurrent real time retrieval services for more users simultaneously. In addition, the novel policy reduces the startup latency for the requests. The correctness of the novel placement and retrieval policy is analyzed with theoretical views. Performance analysis of the novel placement and retrieval policy is provided with simulations.     

Prefetching in file systems for MIMD multiprocessors

The question of whether prefetching blocks on the file into the block cache can effectively reduce overall execution time of a parallel computation, even under favorable assumptions, is considered. Experiments have been conducted with an interleaved file system testbed on the Butterfly Plus multiprocessor. Results of these experiments suggest that (1) the hit ratio, the accepted measure in traditional caching studies, may not be an adequate measure of performance when the workload consists of parallel computations and parallel file access patterns, (2) caching with prefetching can significantly improve the hit ratio and the average time to perform an I/O (input/output) operation, and (3) an improvement in overall execution time has been observed in most cases. In spite of these gains, prefetching sometimes results in increased execution times (a negative result, given the optimistic nature of the study). The authors explore why it is not trivial to translate savings on individual I/O requests into consistently better overall performance and identify the key problems that need to be addressed in order to improve the potential of prefetching techniques in the environment     

Speeding up external mergesort

External mergesort is normally implemented so that each run is stored continuously on disk and blocks of data are read exactly in the order they are needed during merging. We investigate two ideas for improving the performance of external mergesort: interleaved layout and a new reading strategy. Interleaved layout places blocks from different runs in consecutive disk addresses. This is done in the hope that interleaving will reduce seek overhead during merging. The new reading strategy precomputes the order in which data blocks are to be read according to where they are located on disk and when they are needed for merging. Extra buffer space makes it possible to read blocks in an order that reduces seek overhead, instead of reading them exactly in the order they are needed for merging. A detailed simulation model was used to compare the two layout strategies and three reading strategies. The effects of using multiple work disks were also investigated. We found that, in most cases, interleaved layout does not improve performance, but that the new reading strategy consistently performs better than double buffering and forecasting     

面向虚拟机的远程磁盘缓存

在虚拟机(virtual machine)系统中,随着虚拟机数量和应用程序需求的不断增长,内存容量已经成为应用程序性能的主要瓶颈。为了提升内存密集型和I/O密集型程序的页面交换性能,提出了虚拟机的远程磁盘缓存机制REMOCA,它允许运行在一台物理主机上的虚拟机将其他物理主机的内存作为其二级磁盘缓存。由于网络传输延迟远远小于磁盘访问,用网络传输代替磁盘访问就能够有效地降低虚拟机的平均磁盘访问延迟。REMOCA的目标就要尽可能地减少磁盘访问。REMOCA运行在虚拟机管理器中,其基本工作原理是截获并处理虚拟机的页面淘汰、磁盘访问等事件。REMOCA能够与现有的虚拟机内存管理机制(如气球技术、影子缓存)相结合,从而提供更加灵活的内存资源管理策略。实验数据表明,REMOCA能有效地降低页面抖动对虚拟机性能的影响,并在很大程度上提升虚拟机中I/O密集型应用的性能。     

Perfectly Overlapped Generation of Long Runs for Sorting Large Files

A parallel algorithm is presented for quick generation of long sorted runs as the first phase of sorting a large file. It can generate runs of length about 2(m + 2)p on a linear array of p processors each with a heap of size m. Internal computations can be completely overlapped with I/O, and only n + (m + 2)p steps are required to generate the runs from a file of n items. Experiments with the algorithm show that it can give highly satisfactory results in a real environment. A variant of the algorithm is also presented. It is possible that no merge phase is required for sorting a file occupying a whole disk.     

Balancing disk energy against reliability in video playback

Video files contain large amount of data, which can be stored cost-effectively on a hard disk drive, but this consumes a significant energy when it is spinning and ready to read data. The energy used by a disk can be reduced by prefetching video frames into buffer to allow the disk to spin down. But frequent spindowns compromise disk life, so it is desirable to limit the number of times that the disk spins down. We propose a method of data prefetching that fully utilizes the available buffer while providing continuous video playback. We analyze the effect of the amount of data comprising the frames in the buffer on disk power consumption and formulate algorithms that determine when the disk should enter standby mode and the optimal number of disk spindowns. We implemented our scheme in the Linux 2.6 MPlayer and find that a portable 1.8-inch disk uses between 10 and 37 % less energy than it does with the existing MPlayer.     

动态虚拟盘阵数据分布算法

尽管当今的磁盘等外存储设备容量增加得很快,但还是无法满足用户应用程序的需要;在性能上,外存储设备已经成为计算机系统的瓶颈;为此,在集群环境下,将分布式的外设构成动态虚拟盘阵系统是一种较好的解决方案,而数据分布算法是动态虚拟研究的一项重要内容。也就是说,采用优化的数据分布算法,使得盘阵的性能和容量随盘阵的扩展而扩展。研究的主要工作是综述以往对动态盘阵数据分布算法,并对以往SCADDAR算法进行了扩充,提出了D／H(Double／Halve)数据分布算法。     

面向多应用环境RAID系统的智能预取和缓存调度

本文分析了RAID系统的多应用环境数据请求的存储模式的特点，提出了能根据应用环境的不同而自动改变预取策略的智能预取算法以及缓存调度算法。实践证明，本算法使得RAID系统的预取和缓存调度摆脱了盲目性，保证了预取策略和缓存调度的最优性。