US5774715A
Expired / Lapsed
US
⏱️ 0.0 years remaining
File system level compression using holes
Assignee: Oracle America Inc
•
Filing: 1996-03-27
•
Granted: 1998-06-30
•
Expires: 2016-03-27
Abstract
Abstract A method, apparatus, and computer-usable medium for compressing data in a file system utilizing the concept of "holes". A mapping table in a file system maps the logical blocks of a file to actual physical blocks on disk where the data is stored. Blocks may be arranged in units of a cluster, and the file may be compressed cluster-by-cluster. Holes are used within a cluster to indicate not only that a cluster has been compressed, but also the compression algorithm used. Different clusters within a file may be compressed with different compression algorithms. A unit of data is compressed, with the result that the file occupies fewer physical blocks than it has logical blocks. The mapping table is updated to indicate that for a given unit of data compressed, fewer physical blocks are needed. Certain logical blocks belonging to this unit of data are not mapped to physical blocks but are mapped to a hole. A hole indicates that the unit of data was compressed, and may also indicate the particular compression algorithm used to compress the unit of data. If a unit of data begins or ends within the middle of a cluster, to avoid overwriting the data not to be changed the whole cluster must first be read from disk. If a hole indicates the cluster had been compressed, the data must be expanded first. The cluster is read into a buffer and the portion to be changed is overwritten. The cluster is compressed and written back to disk. Those clusters within which the unit of data neither begins nor ends may be written to directly.
Inventors
- 👤 Peter W. Madany
- 👤 Thomas K. Wong
- 👤 Michael N. Nelson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 19:38
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/10; G06F16/17; G06F16/174; G06F16/1744; G06F3/00; G06F3/06; G06F3/0601; G06F3/0602; G06F3/0608; G06F3/0628; G06F3/0638; G06F3/0643; G06F3/0668; G06F3/0671; G06F3/0673; G06F3/0674; G06F3/0676; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
161 words
A computer-implemented method of storing data in a file system having a mapping table arranged to map logical memory blocks to physical memory blocks, the method comprising the steps of: requesting that a segment of data be written to physical memory, the segment of data being associated with selected logical memory blocks; compressing the segment of data into compressed data such that the compressed data occupies fewer blocks of memory than the segment of data; writing the compressed data to physical memory, the compressed data being written to at least one physical memory block; and updating the mapping table such that each physical memory block associated with the compressed data is mapped to by a mapping table entry corresponding to one of the selected logical memory blocks and each of the selected logical memory blocks that is not associated with any of the physical memory blocks is mapped to a hole identifier that does not correspond to any physical memory block.
Claim 2
Dependent Claim
161 words
A computer-implemented method of storing data in a file system having a mapping table arranged to map logical memory blocks to physical memory blocks, the method comprising the steps of: requesting that a segment of data be written to physical memory, the segment of data being associated with selected logical memory blocks; compressing the segment of data into compressed data such that the compressed data occupies fewer blocks of memory than the segment of data; writing the compressed data to physical memory, the compressed data being written to at least one physical memory block; and updating the mapping table such that each physical memory block associated with the compressed data is mapped to by a mapping table entry corresponding to one of the selected logical memory blocks and each of the selected logical memory blocks that is not associated with any of the physical memory blocks is mapped to a hole identifier that does not correspond to any physical memory block.
Claim 3
Dependent Claim
22 words
A method as recited in claim 1 wherein the hole identifier identifies the compression algorithm used to compress the segment of data.
Claim 4
Dependent Claim
52 words
A method as recited in claim 1 wherein: the segment of data may include a multiplicity of clusters, and the file system is arranged to process clusters, each cluster corresponding to a plurality of blocks of logical memory; and the compressing and writing steps are executed in a cluster by cluster manner.
Claim 5
Dependent Claim
41 words
A method as recited in claim 3 wherein: a plurality of hole identifiers are available for use; and the hole identifier selected for use in association with a particular cluster identifies the compression algorithm used to compress data in that cluster.
Claim 6
Dependent Claim
22 words
A method as recited in claim 4 wherein different compression algorithms are used to compress different clusters within the segment of data.
Claim 7
Dependent Claim
301 words
A computer-implemented method of storing data in a file system having a mapping table arranged to map logical memory blocks to physical memory blocks, the file system being arranged to process clusters, each cluster corresponding to a plurality of logical memory blocks, the method comprising the steps of: requesting that a segment of data be written to physical memory, the segment of data being associated with selected logical memory blocks, wherein the selected logical memory blocks may span a plurality of clusters; and determining whether the segment of data begins at an intermediate location within a first one of the clusters, wherein when it is determined that the segment of data begins at an intermediate location, the method further comprises the step of performing a partial cluster write operation utilizing the first cluster as a current cluster, the partial cluster write operation including the sub-steps of, a) reading data associated with the current cluster from physical memory into a read buffer, such current cluster data being stored in the read buffer in an expanded format, b) copying a portion of the segment of data associated with the current cluster into the read buffer after the reading step has been completed, c) compressing the data stored in the read buffer after the copying step, d) writing the compressed data to physical memory, and e) updating the mapping table such that each physical memory block associated with the compressed data is mapped to by a mapping table entry corresponding to one of the selected logical memory blocks that is associated with the current cluster and each of the selected logical memory blocks associated with the current cluster that is not associated with any of the physical memory blocks is mapped to a hole identifier that does not correspond to any physical memory block.
Claim 8
Dependent Claim
301 words
A computer-implemented method of storing data in a file system having a mapping table arranged to map logical memory blocks to physical memory blocks, the file system being arranged to process clusters, each cluster corresponding to a plurality of logical memory blocks, the method comprising the steps of: requesting that a segment of data be written to physical memory, the segment of data being associated with selected logical memory blocks, wherein the selected logical memory blocks may span a plurality of clusters; and determining whether the segment of data begins at an intermediate location within a first one of the clusters, wherein when it is determined that the segment of data begins at an intermediate location, the method further comprises the step of performing a partial cluster write operation utilizing the first cluster as a current cluster, the partial cluster write operation including the sub-steps of, a) reading data associated with the current cluster from physical memory into a read buffer, such current cluster data being stored in the read buffer in an expanded format, b) copying a portion of the segment of data associated with the current cluster into the read buffer after the reading step has been completed, c) compressing the data stored in the read buffer after the copying step, d) writing the compressed data to physical memory, and e) updating the mapping table such that each physical memory block associated with the compressed data is mapped to by a mapping table entry corresponding to one of the selected logical memory blocks that is associated with the current cluster and each of the selected logical memory blocks associated with the current cluster that is not associated with any of the physical memory blocks is mapped to a hole identifier that does not correspond to any physical memory block.
Claim 9
Dependent Claim
49 words
A method as recited in claim 6 further comprising the step of determining whether the current cluster is stored in a compressed format, and expanding the current cluster data for storage in the read buffer when it is determined that the current cluster is stored in a compressed format.
Claim 10
Dependent Claim
25 words
A method as recited in claim 6 wherein the hole identifier identifies the compression algorithm used to compress the data associated with the current cluster.
Claim 11
Dependent Claim
41 words
A method as recited in claim 8 wherein: a plurality of hole identifiers are available for use; and the hole identifier selected for use in association with a particular cluster identifies the compression algorithm used to compress data in that cluster.
Claim 12
Dependent Claim
22 words
A method as recited in claim 9 wherein different compression algorithms are used to compress different clusters within the segment of data.
Claim 13
Dependent Claim
66 words
A method as recited in claim 6 further comprising the steps of: determining whether the segment of data ends at an intermediate location within a second one of the clusters, wherein when it is determined that the segment of data ends at an intermediate location, the method further comprises the step of performing the partial cluster write operation utilizing the second cluster as a current cluster.
Claim 14
Dependent Claim
154 words
A method as recited in claim 11 further comprising the steps of: determining whether a selected cluster is a full cluster, a full cluster being one at which the segment of data being written neither begins nor ends in an intermediate location within the cluster, wherein when it is determined that a selected cluster is a full cluster, the method further comprises the steps of, f) compressing the data associated with the full cluster, g) writing the compressed data to physical memory, h) updating the mapping table such that each physical memory block associated with the compressed data is mapped to an associated logical memory block that is associated with the full cluster and each logical memory block associated with the full cluster that is not associated with any of the physical memory blocks is mapped to a hole identifier that does not correspond to any physical memory block associated with the compressed data.
Claim 15
Dependent Claim
164 words
A computer-implemented method of retrieving data in a file system having a mapping table arranged to map logical memory blocks to physical memory blocks, the method comprising the steps of: requesting that a segment of data be read from physical memory, the segment of data being associated with selected logical memory blocks; and determining by reference to the mapping table whether any of the selected logical memory blocks are mapped to a hole identifier that indicates that the segment of data is stored in compressed form in the physical memory, wherein when it is determined that the segment of data is stored in compressed form, performing the sub-steps of, a) reading from physical memory into a compression buffer all physical memory blocks that are associated with the selected logical memory blocks of the segment of data, and b) expanding the physical memory blocks stored in the compression buffer so that the segment of data is then stored in expanded form in the compression buffer.
Claim 16
Dependent Claim
164 words
A computer-implemented method of retrieving data in a file system having a mapping table arranged to map logical memory blocks to physical memory blocks, the method comprising the steps of: requesting that a segment of data be read from physical memory, the segment of data being associated with selected logical memory blocks; and determining by reference to the mapping table whether any of the selected logical memory blocks are mapped to a hole identifier that indicates that the segment of data is stored in compressed form in the physical memory, wherein when it is determined that the segment of data is stored in compressed form, performing the sub-steps of, a) reading from physical memory into a compression buffer all physical memory blocks that are associated with the selected logical memory blocks of the segment of data, and b) expanding the physical memory blocks stored in the compression buffer so that the segment of data is then stored in expanded form in the compression buffer.
Claim 17
Dependent Claim
22 words
A method as recited in claim 13 wherein the hole identifier identifies the compression algorithm used to compress the segment of data.
Claim 18
Dependent Claim
52 words
A method as recited in claim 13 wherein: the segment of data may include a multiplicity of clusters, and the file system is arranged to process clusters, each cluster corresponding to a plurality of blocks of logical memory; and the reading and expanding steps are executed in a cluster by cluster manner.
Claim 19
Dependent Claim
51 words
A method as recited in claim 15 wherein: a plurality of hole identifiers are available for use, and logical memory blocks in the mapping table corresponding to a particular cluster are mapped to at least one hole identifier that indicates the compression algorithm used to compress data in that particular cluster.
Claim 20
Dependent Claim
22 words
A method as recited in claim 16 wherein different compression algorithms are used to compress different clusters within the segment of data.
Claim 21
Dependent Claim
66 words
A method as recited in claim 13 wherein when it is determined that the segment of data is not stored in compressed form, reading from physical memory and into a read buffer all physical memory blocks that are associated with the selected logical memory blocks of the segment of data so that the segment of data is then stored in expanded form in the read buffer.
Claim 22
Dependent Claim
174 words
A computer apparatus for use in compressing and expanding a data segment in a file system, the data segment being associated with selected logical memory blocks, the computer apparatus comprising: a central processing unit; random access memory in communication with the central processing unit; a mass storage device in communication with the central processing unit; a mapping table arranged to map the selected logical memory blocks of the data segment to associated physical memory blocks of the mass storage device, such that when the data segment is stored in a compressed form on the mass storage device the compressed data segment occupies fewer physical memory blocks than the expanded data segment, and such that each physical memory block associated with the compressed data is mapped to by a mapping table entry corresponding to one of the selected logical memory blocks and each of the selected logical memory blocks that is not associated with any of the physical memory blocks is mapped to a hole identifier that does not correspond to any physical memory block.
Claim 23
Dependent Claim
174 words
A computer apparatus for use in compressing and expanding a data segment in a file system, the data segment being associated with selected logical memory blocks, the computer apparatus comprising: a central processing unit; random access memory in communication with the central processing unit; a mass storage device in communication with the central processing unit; a mapping table arranged to map the selected logical memory blocks of the data segment to associated physical memory blocks of the mass storage device, such that when the data segment is stored in a compressed form on the mass storage device the compressed data segment occupies fewer physical memory blocks than the expanded data segment, and such that each physical memory block associated with the compressed data is mapped to by a mapping table entry corresponding to one of the selected logical memory blocks and each of the selected logical memory blocks that is not associated with any of the physical memory blocks is mapped to a hole identifier that does not correspond to any physical memory block.
Claim 24
Dependent Claim
22 words
An apparatus as recited in claim 19 wherein the hole identifier identifies the compression algorithm used to compress the segment of data.
Claim 25
Dependent Claim
62 words
An apparatus as recited in claim 19 wherein: the segment of data may include a multiplicity of clusters, each cluster corresponding to a plurality of blocks of logical memory; a plurality of hole identifiers are available for use; and the hole identifier selected for use in association with a particular cluster identifies the compression algorithm used to compress data in that cluster.
Claim 26
Dependent Claim
22 words
An apparatus as recited in claim 21 wherein different compression algorithms are used to compress different clusters within the segment of data.
Claim 27
Dependent Claim
201 words
A computer program product comprising a computer-usable medium having computer-readable code embodied thereon for compressing and expanding data in a file system of a computer, the file system having a mapping table arranged to map logical memory blocks to physical memory blocks, the computer program product comprising the following computer-readable program code for effecting actions in the computer: program code for requesting that a segment of data be written to physical memory, the segment of data being associated with selected logical memory blocks; program code for compressing the segment of data into compressed data such that the compressed data occupies fewer blocks of memory than the segment of data; program code for writing the compressed data to physical memory, the compressed data being written to at least one physical memory block; and program code for updating the mapping table such that each physical memory block associated with the compressed data is mapped to by a mapping table entry corresponding to one of the selected logical memory blocks and each of the selected logical memory blocks that is not associated with any of the physical memory blocks is mapped to a hole identifier that does not correspond to any physical memory block.
Claim 28
Dependent Claim
201 words
A computer program product comprising a computer-usable medium having computer-readable code embodied thereon for compressing and expanding data in a file system of a computer, the file system having a mapping table arranged to map logical memory blocks to physical memory blocks, the computer program product comprising the following computer-readable program code for effecting actions in the computer: program code for requesting that a segment of data be written to physical memory, the segment of data being associated with selected logical memory blocks; program code for compressing the segment of data into compressed data such that the compressed data occupies fewer blocks of memory than the segment of data; program code for writing the compressed data to physical memory, the compressed data being written to at least one physical memory block; and program code for updating the mapping table such that each physical memory block associated with the compressed data is mapped to by a mapping table entry corresponding to one of the selected logical memory blocks and each of the selected logical memory blocks that is not associated with any of the physical memory blocks is mapped to a hole identifier that does not correspond to any physical memory block.
Claim 29
Dependent Claim
24 words
A computer program product as recited in claim 23 wherein the hole identifier identifies the compression algorithm used to compress the segment of data.
Claim 30
Dependent Claim
56 words
A computer program product as recited in claim 23 wherein: the segment of data may include a multiplicity of clusters, and the file system is arranged to process clusters, each cluster corresponding to a plurality of blocks of logical memory; and compressing and writing the segment of data is executed in a cluster by cluster manner.
Claim 31
Dependent Claim
43 words
A computer program product as recited in claim 25 wherein: a plurality of hole identifiers are available for use; and the hole identifier selected for use in association with a particular cluster identifies the compression algorithm used to compress data in that cluster.
Claim 32
Dependent Claim
24 words
A computer program product as recited in claim 26 wherein different compression algorithms are used to compress different clusters within the segment of data.
Claim 33
Dependent Claim
50 words
A computer-implemented method of transmitting the computer-readable program code as recited in claim 23, the method comprising the steps of: storing the program code onto a computer-usable medium; receiving a request for the transmission of the program code; and transmitting the program code over a network to a remote location.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-06-29 | 2001-12-29 | 2002-06-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-06-29 | 2005-12-29 | 2006-06-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-06-29 | 2009-12-29 | 2010-06-30 | $7700.00 | Window Closed / Lapsed |