Constraint Allocation on Disks

Abstract

Most existing storage servers store data stripes on magnetic hard disks. These magnetic hard disks are accessed by moving the disk heads to random disk tracks. A significant amount of overhead is spent in moving the disk heads across the disk tracks. The access time of a request would be significantly reduced if the seek time is reduced. In the normal placement of data stripes on disks being described in the two previous chapters, data stripes can be placed on any tracks with free space. There is not much consideration on the distance among data stripes of concurrent streams. Separation distances between data stripes of an object are not sufficiently constrained. Thus, the only guarantee on the upper bounds of access times is very high. Constraint allocation methods limit the available locations to store the data stripes. This helps to control the access time within media playback requirements. The data stripes are also evenly spread across the surface of the storage media. This reduces the overheads of serving concurrent streams from the same storage device. Therefore, the maximum overheads in accessing data from the storage devices, such as seek time, become lowered. In this chapter, we shall describe two constraint allocation methods that are designed for magnetic hard disks. These methods may also be applicable to other storage media that use the disk format. When many streams access the same hot object, the phase based constraint allocation supports more streams with less seek actions. We shall describe the phase based constraint allocation method in the next section. The region based allocation limits the longest seek distance among requests. After that, we describe the region based allocation method.