File system level compression using holes

• US 5,774,715 A
• Filed: 03/27/1996
• Issued: 06/30/1998
• Est. Priority Date: 03/27/1996
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Wong, Thomas K., Madany, Peter W., Nelson, Michael N.
• Primary Examiner(s): Lintz, Paul R.
• Application Number:
  US08/623,907
• Time in Patent Office: 825 Days
• Field of Search: 395/611, 395/612, 395/440, 364/715.02
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0676 Magnetic disk device
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

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.

Claims

1. 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.

2. A method as recited in claim 1 wherein the hole identifier identifies the compression algorithm used to compress the segment of data.

3. 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.

4. 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.

5. A method as recited in claim 4 wherein different compression algorithms are used to compress different clusters within the segment of data.

6. 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.

7. 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.

8. 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.

9. 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.

10. A method as recited in claim 9 wherein different compression algorithms are used to compress different clusters within the segment of data.

11. 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.

12. 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.

13. 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.

14. A method as recited in claim 13 wherein the hole identifier identifies the compression algorithm used to compress the segment of data.

15. 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.

16. 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.

17. A method as recited in claim 16 wherein different compression algorithms are used to compress different clusters within the segment of data.

18. 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.

19. 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.

20. An apparatus as recited in claim 19 wherein the hole identifier identifies the compression algorithm used to compress the segment of data.

21. 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.

22. An apparatus as recited in claim 21 wherein different compression algorithms are used to compress different clusters within the segment of data.

23. 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.

24. A computer program product as recited in claim 23 wherein the hole identifier identifies the compression algorithm used to compress the segment of data.

25. 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.

26. 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.

27. A computer program product as recited in claim 26 wherein different compression algorithms are used to compress different clusters within the segment of data.

28. 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.