Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2000-07-18
2004-12-07
Peikari, B. James (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S004000
Reexamination Certificate
active
06829678
ABSTRACT:
TECHNICAL FIELD
This invention relates, in general, to allocating space on data storage devices, and in particular, to using weights to determine the order and frequency in which space is allocated on individual storage devices.
BACKGROUND ART
Many computing environments include file systems, which enable other application programs to store data on and retrieve data from storage devices. In particular, a file system allows application programs to create files and to give them names (a file is a named data object of arbitrary size), to store (or write) data into files, to read data from files, to delete files, and perform other operations on files.
A file structure is the organization of data on the storage devices. In addition to the file data itself, the file structure contains meta data, which includes, for instance, the following: a directory that maps file names to the corresponding files; file meta data that contains information about the file, including the location of the file data on the storage device (i.e., which device blocks hold the file data); an allocation map that records which device blocks are currently in use to store meta data and file data; and a superblock that includes overall information about the file structure (e.g., the locations of the directory, allocation map, and other meta data structures).
In order to store successive data blocks of a file to distinct devices, such as disks or other storage devices, a technique known as data striping is used. Data striping may also be used to store the file system's meta data. The advantages of striping include high performance and load balancing. In data striping, the file system writes successive blocks of a file, or the file's meta data, to distinct devices in a defined order. For example, the file system may use a round-robin allocation, in which successive blocks are placed according to a cyclic permutation of the devices. This permutation is called the data stripe order. The stripe order defines the order and frequency of allocations (and thus, writes) to each device in the file system. For example, a system with four disks using a simple round-robin allocation scheme would allocate space on each disk in consecutive order, namely: 1, 2, 3, 4, 1, 2, 3, 4 . . . Hereinafter, “data stripe” and “stripe,” as well as “data striping” and “striping” are used interchangeably.
This simple round-robin allocation is used by most striped file systems for allocation. Although, round-robin allocations may be sufficient in some circumstances for a system that includes homogeneous devices, it proves to be inadequate for a system with heterogeneous devices, and it proves to be inadequate for various circumstances in which homogeneous devices are used.
As one example, a round-robin allocation is inadequate for devices of different storage capacities or throughput. Under round-robin allocation, all devices are allocated equally. Consequently, subsequent access to the data is typically spread equally across the devices as well. For systems that include devices with different storage capacities, the small devices fill before the larger devices and then, must be excluded from the stripe order, thus reducing the parallelism and performance for all subsequent writes. Furthermore, the data striped across the reduced set of devices has reduced performance for all subsequent accesses.
Likewise, for systems that include devices with different throughput, round-robin allocation fails to maximize the throughput for allocation and all subsequent accesses to the data. Additionally, round-robin allocation has no capability for rebalancing a system that begins in an unbalanced state. An unbalanced state can occur for a variety of reasons including, for instance, when devices are partitioned between file or operating systems; when empty devices are added to an existing file system; or when the allocation policy changes. To rebalance such a system, extraordinary measures are required by the user, such as restriping of all the data in the file system.
Thus, a need still exists for an allocation technique that is general enough to be used in a wide variety of circumstances. Further, a need exists for a capability that enables rebalancing of the allocations to better match the current conditions and requirements of the system and/or devices.
SUMMARY OF THE INVENTION
The shortcomings of the prior art are overcome and additional advantages are provided through the provision of a method of managing the allocation of space on storage devices. The method includes, for instance, obtaining weights for at least a subset of a plurality of storage devices, the subset comprising at least two storage devices; and allocating space on multiple storage devices of the at least a subset of storage devices in proportion to weights obtained for the multiple storage devices, wherein the allocating is independent of access patterns of data to be accommodated by the allocated space in that the allocating lacks apriori knowledge of the access patterns.
In a further embodiment of the invention, a method of managing the allocation of space on storage devices is provided. The method includes, for instance, obtaining weights for at least a subset of a plurality of storage devices; and generating a stripe order using one or more of the weights, the stripe order indicating an order and frequency of allocating space on multiple storage devices of the plurality of storage devices, and wherein the generating is independent of a weighting assignment used in obtaining the weights.
System and computer program products corresponding to the above-summarized methods are also described and claimed herein.
The capabilities of one or more aspects of the present invention advantageously provide for the allocation of space across a plurality of storage devices, such that the space on each device is allocated and thus, consumed in proportion to some weight assigned to that device. The weight assigned to each device determines the allocation policy and allows the file system to balance the allocation across the devices. The weights and the allocation policy are independent of the technique used for allocation. This allows the policy to be changed dynamically to better match the current conditions and requirements.
Additional features and advantages are realized through the techniques of the present invention. Other embodiments and aspects of the invention are described in detail herein and are considered a part of the claimed invention.
REFERENCES:
patent: 4467421 (1984-08-01), White
patent: 5423046 (1995-06-01), Nunnelley et al.
patent: 5583995 (1996-12-01), Gardner et al.
patent: 5600820 (1997-02-01), Johnston
patent: 5659704 (1997-08-01), Burkes et al.
patent: 5708660 (1998-01-01), Riedel
patent: 5724539 (1998-03-01), Riggle et al.
patent: 5732239 (1998-03-01), Tobagi et al.
patent: 5754756 (1998-05-01), Watanabe et al.
patent: 5774643 (1998-06-01), Lubbers et al.
patent: 5845319 (1998-12-01), Yorimitsu
patent: 5937428 (1999-08-01), Jantz
patent: 5943690 (1999-08-01), Dorricott et al.
patent: 5960446 (1999-09-01), Schmuck et al.
patent: 5963963 (1999-10-01), Schmuck et al.
patent: 6016552 (2000-01-01), Lee et al.
patent: 6023706 (2000-02-01), Schmuck et al.
patent: 6055354 (2000-04-01), Bopardikar
patent: 6275917 (2001-08-01), Okada
patent: 6279052 (2001-08-01), Upadrastra
patent: 6327638 (2001-12-01), Kirby
patent: 6425052 (2002-07-01), Hashemi
patent: 6629201 (2003-09-01), Dempsey et al.
patent: 2312316 (1997-10-01), None
patent: 411203055 (1999-07-01), None
IEEE 100: The Authoritative Dictionary of IEEE Standards Terms, 7thed. IEEE Press, 2000, p. 1277.
Haskin Roger L.
Sawdon Wayne A.
Schmuck Frank B.
Wyllie James C.
Cutter, Esq. Lawrence D.
Heslin Rothenberg Farley & & Mesiti P.C.
Peikari B. James
Schiller, Esq. Blanche E.
LandOfFree
System for determining the order and frequency in which... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for determining the order and frequency in which..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for determining the order and frequency in which... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3301926