Intra-disk swapping of data storage volumes

Details Intra-disk swapping of data storage volumes Intra-disk swapping of data storage volumes

2000-03-31

2003-12-16

Kim, Matthew (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C711S004000, C711S114000, C711S154000, C711S167000, C709S241000, C710S018000, C714S006130, C714S006130

Reexamination Certificate

active

06665771

ABSTRACT:

TECHNICAL FIELD
This invention relates to data storage systems.
BACKGROUND
An access to a data storage disk proceeds via a sequence of acts that additively contribute to the time needed to complete the access. The sequence includes acts that physically align a disk's read-write head with the physical storage volume being accessed and acts that actually transfer data to or from the physically aligned storage volume.
The physical alignment typically involves two movements. One movement is a radial travel of the read-write head that aligns the head with a start track of the storage volume to be accessed. The average time for the head travel is referred to as the seek time. The other movement is a rotation of the disk that aligns the read-write head with a start sector of the storage volume to be accessed. The average time for the disk rotational movement is referred to as the rotational latency time.
The total access time for a storage disk is the total time needed to complete the acts of the access. Thus, the total access time is a sum of the seek time, the rotational latency time, and the actual time to transfer data. The seek time can however, provide the dominant contribution to the total access time for many storage disks. Each contribution to the total access time is dynamical and can depend on the state of both the disk and the applications using the disk.
The dynamical nature of the contributions to the total access time is illustrated by the seek time. The seek time depends on access patterns for individual storage volumes of the disk. If the access pattern includes many consecutive accesses to the same physical storage volume, the seek time will be small. If the access pattern includes many consecutive accesses to new physical storage volumes, the seek time will be large. Determining the seek time usually requires measurements of access activity data for the physical storage volumes of the disk.
SUMMARY
In a first aspect, the invention features a process for performing an intra-disk swap. The process includes finding a set of values indicative of access loads of new states of a disk. Each new state is produced from a current state of the disk by hypothetically swapping a pair of physical storage volumes of the disk. The process also includes swapping a pair of physical storage volumes based on the value of the access load of the new state produced by hypothetically swapping the pair.
In some embodiments, each value of the access load is either a seek time or a total access time. The act of swapping may be responsive to the swap of the associated pair of volumes producing the new state with the lowest value of the set.
In some embodiments, each value of the access time is either a seek time or a reduction to a seek time of the current state. The act of finding may perform a number of arithmetic operations to obtain the set of values, the number being of order of a number of values in the set.
The act of finding may also include finding a set of numerical objects from activity data for the current state and determining the seek time or reduction to seek time for each new state by evaluating a formula based on the found set of numerical objects. The set has of order N members with N being the number of storage volumes. The formula has less than of order N terms.
In these embodiments, the act of finding a set of numerical objects may include evaluating a set of equations {R
j+1
=(R
j
+a
j
)t
Ref
p+1,p
} for components of a vector object R. The “t
Ref
p+1,p
” is a number, and each a
j
is an activity of the storage volume with index “j” in the current state. Each act of determining may include evaluating [−(a
p
−a
q
)[R
p
+R
p
*−R
q
−R
q
*]+(a
p
−a
q
)
2
(t
Ref
pp
+t
Ref
qq
−2t
Ref
pq
)]/F with F being the total activity of the current state.
In some embodiments, each act of finding a value includes performing a sum over component seek times to obtain a seek time for an associated new state. Each component seek time is a seek time associated with a reference head travel time function. For storage disks one form for the head travel time function is given by:
t
kj
=x
j
, for
j=k
, and
t
kj
=&agr;
|j−k|
for
j≠k.
For a selected value of &agr;, this form is referred to as a reference travel time function, t
kj
Ref
. The number &agr; defines the particular reference travel time function, t
kj
Ref
, and may be a real or a complex number. For &agr;=1, the associated reference travel time function is independent of distance between the storage volumes “j” and “k”. For a set of values of &agr;, the reference travel time functions, t
kj
Ref
(n), can provide a series approximation to other head travel functions. Each term of each sum may be weighted by expansion coefficients of a head travel time function of the disk with respect to the reference travel time functions.
In a second aspect, the invention features a process for determining seek times. The process includes collecting activity data on a current state of a disk, finding a plurality of numerical objects from the activity data, and then, determining a plurality of seek times for new states from the found numerical objects. Each new state is related to the current state by a hypothetical swap of a pair of storage volumes of the disk. The seek times correspond to a preselected reference head travel time function.
In some embodiments, each act of determining a seek time includes performing a set of simple arithmetic operations less numerous than the physical storage volumes of the disk.
In some embodiments, the act of finding a plurality of numerical objects includes performing a set of simple arithmetic operations whose number is smaller than a square of the number of physical storage volumes on the disk.
In some embodiments, the reference head travel time function between a pair of the storage volumes is a weighted sum of numbers to powers of a distance between the pair of storage volumes.
In some embodiments, the act of finding a plurality of numerical objects includes evaluating a set of equations {R
j+1=(R
j
+a
j
)t
Ref
p+1,p
} for a vector object R. Here, the “t
Ref
p+1,p
” is a number, and each a
j
is an activity of the storage volume with index “j” in the current state. The act of determining the seek time of the new state produced by hypothetically swapping may also include evaluating [−(a
p
−a
q
)[R
p
+R
p
*−R
q
−R
q
*]+(a
p
−a
q
)
2
(t
Ref
pp
+t
Ref
qq
−2t
Ref
pq
)]/F with F being a total activity of the current state.
In a third aspect, the invention features a program storage media storing a computer executable program of instructions. The instructions cause a computer to perform one of the above-described processes.
In a fourth aspect, the invention features a system for performing an intra-disk swap. The system includes means for finding a set of values indicative of access loads of new states of a disk. Each new state is produced from a current state of the disk by hypothetically swapping a pair of physical storage volumes of the disk.
In some embodiments, the system further includes means for swapping one of the pairs of physical storage volumes based on the value of the access load of the new state produced by hypothetically swapping the one of the pairs. The access load may be a seek time or a total access time.
In some embodiments, the means for finding performs a number of arithmetic operations to obtain the set of values. The number is of order of the number of values in the set.
Other features and advantages of the invention will be apparent from the detailed description and claims.


REFERENCES:
patent: 4638424 (1987-01-01), Beglin et al.
patent: 6061761 (2000-05-01), Bachmat
patent: 6088766 (2000-07-01), Bachmat et al.
patent: 6189071 (2001-02-01), Bachmat
patent: 6237063 (2001-05-01), Bachmat et al.
patent: 6341333 (2002-01-01), Sch

Affiliated with

Also associated with

Rating

Intra-disk swapping of data storage volumes does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Intra-disk swapping of data storage volumes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Intra-disk swapping of data storage volumes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3129486