US5604902A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Hole plugging garbage collection for a data storage system
Assignee: Hewlett Packard Development Co LP
•
Filing: 1995-02-16
•
Granted: 1997-02-18
•
Expires: 2015-02-16
Abstract
Abstract A data storage management system performs garbage collection to reduce fragmentation in storage by moving data from source fragmented areas to holes (unused storage space) in target fragmented areas, rather than copying data to the end of an extending target area. New areas are not consumed. Preferably, source areas are emptier (i.e., more fragmented) relative to the whole set of areas in the storage system, and target areas are fuller (i.e., less fragmented) relative to the whole set of areas in the storage system. The goal of freeing (defragmenting) an area is realized with fewer I/O moves, if most areas are lightly fragmented, because fragmentation is reduced in more than one area substantially concurrently. Namely, fragmentation is eliminated in a source area by continuing to empty the area (i.e., by moving the data from the source area) and, substantially concurrently, fragmentation is reduced in a target area by continuing to fill the area (i.e., by moving/plugging the data into holes in the target area). In a lightly fragmented storage, this reduction in moves outweighs the increased cost incurred for read-modify-write in parity storage, thereby providing better overall garbage collection efficiency and performance.
Inventors
- 👤 Theresa A. Burkes
- 👤 Carl Staelin
- 👤 Timothy T. Sullivan
- 👤 Douglas L. Voigt
- 👤 John Wilkes
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 00:15
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1076; G06F16/00; G06F16/20; G06F16/22; G06F16/221; G06F3/00; G06F3/06; G06F3/0601; G06F3/0602; G06F3/0608; G06F3/0628; G06F3/0646; G06F3/0652; G06F3/0668; G06F3/0671; G06F3/0683; G06F3/0689; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99956; Y10S707/99957
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
97 words
A storage management system for defragmenting storage space in a data storage system, comprising: (a) selection means for selecting from the storage space at least one source fragmented area-having first blocks of data therein, and at least one target fragmented area having second blocks of data therein and holes of unused storage space, and wherein the source and target fragmented areas are separate areas in the storage space; and, (b) means for moving the first blocks of data into the holes to fill the holes, whereby the source and target fragmented areas are each defragmented substantially concurrently.
Claim 2
Dependent Claim
97 words
A storage management system for defragmenting storage space in a data storage system, comprising: (a) selection means for selecting from the storage space at least one source fragmented area-having first blocks of data therein, and at least one target fragmented area having second blocks of data therein and holes of unused storage space, and wherein the source and target fragmented areas are separate areas in the storage space; and, (b) means for moving the first blocks of data into the holes to fill the holes, whereby the source and target fragmented areas are each defragmented substantially concurrently.
Claim 3
Dependent Claim
24 words
The storage management system of claim 1 wherein each area is at least one stripe set in a Redundant Array of Independent Disks (RAID).
Claim 4
Dependent Claim
42 words
The storage management system of claim 1 wherein the source area is one of the most fragmented within a set of all areas in the storage space, and the target area is one of the least fragmented of the set of areas.
Claim 5
Dependent Claim
47 words
The storage management system of claim 1 wherein the selection means includes a frequency distribution table for characterizing the storage space according to a predetermined distribution criteria and for selecting storage space for defragmentation purposes, whereby scanning and sorting overhead for storage space selection purposes is reduced.
Claim 6
Dependent Claim
73 words
The storage management system of claim 4 wherein the frequency distribution table comprises a set of interval elements for identifying subsets for a total number of areas of storage space in the data storage system, and wherein the subsets of areas are identified by selection criteria, and wherein the selection criteria are selected from the group consisting of block use counts, hole counts, fragmentation percentages, and values that are functions of fragmentation percentages.
Claim 7
Dependent Claim
24 words
The storage management system of claim 1 wherein all the first blocks in the source fragmented area are moved to the target fragmented area.
Claim 8
Dependent Claim
31 words
The storage management system of claim 1 wherein all the first blocks are moved from at least one of the source fragmented areas to at least one of the target areas.
Claim 9
Dependent Claim
39 words
The storage management system of claim 1 wherein the data storage system includes a memory hierarchy system selected from the group consisting of (i) multiple data redundancy schemes, including parity storage redundancy, and (ii) multiple physical media storage types.
Claim 10
Independent Claim
99 words
A method for defragmenting storage space in a data storage system, comprising the steps of: (a) selecting from the storage space at least one source fragmented area having first blocks of data therein; (b) selecting from the storage space at least one target fragmented area having second blocks of data therein and holes of unused storage space, and wherein the source and target fragmented areas are separate areas in the storage space; and, (c) moving the first blocks of data into the holes to fill the holes, whereby the source and target fragmented areas are each defragmented substantially concurrently.
Claim 11
Independent Claim
99 words
A method for defragmenting storage space in a data storage system, comprising the steps of: (a) selecting from the storage space at least one source fragmented area having first blocks of data therein; (b) selecting from the storage space at least one target fragmented area having second blocks of data therein and holes of unused storage space, and wherein the source and target fragmented areas are separate areas in the storage space; and, (c) moving the first blocks of data into the holes to fill the holes, whereby the source and target fragmented areas are each defragmented substantially concurrently.
Claim 12
Dependent Claim
22 words
The method of claim 9 wherein each area is at least one stripe set in a Redundant Array of Independent Disks (RAID).
Claim 13
Dependent Claim
40 words
The method of claim 9 wherein the source area is one of the most fragmented within a set of all areas of the storage space and the target area is one of the least fragmented of the set of areas.
Claim 14
Dependent Claim
49 words
The method of claim 9 wherein the source and target areas are selected using a frequency distribution table for characterizing the storage space according to a predetermined distribution criteria and for selecting storage space for defragmentation purposes whereby scanning and sorting overhead for storage space selection purposes is reduced.
Claim 15
Dependent Claim
73 words
The method of claim 12 wherein the frequency distribution table comprises a set of interval elements for identifying subsets for a total number of areas of storage space in the data storage system, and wherein the subsets of areas are identified by selection criteria, and wherein the selection criteria are selected from the group consisting of block use counts, hole counts, fragmentation percentages, and any value that is a function of fragmentation percentages.
Claim 16
Dependent Claim
22 words
The method of claim 9 wherein all the first blocks in the source fragmented area are moved to the target fragmented area.
Claim 17
Dependent Claim
29 words
The method of claim 9 wherein all the first blocks are moved from at least one of the source fragmented areas to at least one of the target areas.
Claim 18
Dependent Claim
37 words
The method of claim 9 wherein the data storage system includes a memory hierarchy system selected from the group consisting of (i) multiple data redundancy schemes, including parity storage redundancy, and (ii) multiple physical media storage types.
Claim 19
Independent Claim
124 words
A method for defragmenting storage space in a storage system having a memory hierarchy, comprising the steps of: (a) selecting from the storage space at least one source fragmented area having first blocks of data therein; (b) selecting from the storage space at least one target fragmented area having second blocks of data therein and holes of unused storage space, and wherein the source area is one of the most fragmented within a set of all areas in the storage space and the target area is one of the least fragmented of the set of areas; and, (c) moving all the first blocks of data into the holes to fill the holes, whereby fragmentation is reduced in the source and target areas substantially concurrently.
Claim 20
Independent Claim
124 words
A method for defragmenting storage space in a storage system having a memory hierarchy, comprising the steps of: (a) selecting from the storage space at least one source fragmented area having first blocks of data therein; (b) selecting from the storage space at least one target fragmented area having second blocks of data therein and holes of unused storage space, and wherein the source area is one of the most fragmented within a set of all areas in the storage space and the target area is one of the least fragmented of the set of areas; and, (c) moving all the first blocks of data into the holes to fill the holes, whereby fragmentation is reduced in the source and target areas substantially concurrently.
Claim 21
Dependent Claim
29 words
The method of claim 17 wherein all the first blocks are moved from at least one of the source fragmented areas to at least one of the target areas.
Claim 22
Dependent Claim
49 words
The method of claim 17 wherein the source and target areas are selected using a frequency distribution table for characterizing the storage space according to a predetermined distribution criteria and for selecting storage space for defragmentation purposes, whereby scanning and sorting overhead for storage space selection purposes is reduced.
Claim 23
Dependent Claim
71 words
The method of claim 19 wherein the frequency distribution table comprises a set of interval elements for identifying subsets for a total number of areas of storage space in the data storage system, and wherein the subsets of areas are identified by selection criteria, and wherein the selection criteria are selected from the group consisting of block use counts, hole counts, fragmentation percentages, and values that are functions of fragmentation percentages.
References Cited (Backward Citations)
US4775932A
Cited
US4924435A
Cited
US5025367A
Cited
US4797810A
Cited
US4996663A
Cited
US4907151A
Cited
US5088036A
Cited
US5109336A
Cited
US5398142A
Cited
US5398142B1
Cited
US5195100A
Cited
US5247634A
Cited
US5241673A
Cited
US5155835A
Cited
US5339411A
Cited
US5278838A
Cited
US5237658A
Cited
US5297258A
Cited
US5287462A
Cited
US5289418A
Cited
US5416915A
Cited
US5551003A
Cited
US5560003A
Cited
US5555405A
Cited
US5392244A
Cited
US5463776A
Cited
US5488701A
Cited
US5542065A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-02-18 | 2000-08-19 | 2001-02-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-02-18 | 2004-08-19 | 2005-02-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-02-18 | 2008-08-19 | 2009-02-18 | $7700.00 | Window Closed / Lapsed |