Set partitioning for encoding file system allocation metadata

Patent metadata

Field	Value
Publication number	US-9678879-B2
Application number	US-12950508-A
Country	US
Kind code	B2
Filing date	May 29, 2008
Priority date	May 29, 2008
Publication date	Jun 13, 2017
Grant date	Jun 13, 2017

Abstract

Methods for encoding file system metadata are described herein. According to one embodiment, a file system cache is maintained including information representing relationships between inodes and disk blocks of a disk having disk sections. Each disk section includes a data segment and a header encoding metadata for describing the data section of each disk section. The metadata is encoded using a set partitioning algorithm and each set represents a set of disk blocks. In response to a file system request for reading a disk section, metadata associated with the disk section is retrieved and decoded to extract information representing a relationship between inodes and disk blocks associated with the requested disk section. The file system request is then serviced using the decoded metadata and the associated data segment and one or more entries of the file system cache are updated using the decoded metadata.

First claim

What is claimed is:

1. A method, comprising:
maintaining, by a processor, a file system stored on a disk, wherein the disk comprises a disk section, and wherein the disk section comprises a data segment and a variable-sized metadata segment, and wherein the variable-sized metadata segment comprises:
(1) an encoding of an allocation map of a plurality of disk blocks of the disk section, wherein the encoding of the allocation map is generated via hierarchical set-partitioning compression,
(2) a state of a first inode of the file system, and
(3) an extent of disk blocks allocated to the first inode;

maintaining a file system cache associated with the file system, wherein the file system cache comprises a cache entry corresponding to the first inode, and wherein the cache entry specifies:
a starting physical block number of the extent of disk blocks allocated to the first inode,
a starting logical block number relative to the first inode, and
a length of the extent;

maintaining an index of the file system cache, the index comprising an index entry that maps at least one of an ending physical block number of the extent or an ending logical block number of the extent to the first inode;
receiving a first file system request with respect to the disk section;
in response to the first file system request, retrieving and decoding, by the processor, the variable-sized metadata segment;
servicing the first file system request using the decoded variable-sized metadata segment;
updating the cache entry using the decoded variable-sized metadata segment and the index of the file system cache;
receiving a second file system request; and
servicing the second file system request in view of the updated file system cache.

2. The method of claim 1 , wherein the first file system request is a request for block allocation, and wherein the method further comprises:
examining an extent allocated to inode zero in an attempt to locate a closest extent of an inode in view of an extent requested in the block allocation;
modifying a record of inode zero to a new inode and updating indices of the file system cache when the extent of inode zero equals to the requested extent;
reducing the extent of inode zero and creating a new record in the file system cache for blocks allocated for the request when the extent of inode zero is larger than the requested extent.

3. The method of claim 1 , wherein the file system request is a request for block deallocation, and wherein the method further comprises:
looking up extents in the file system cache using the index of the file system cache to locate a record associated with a block being deallocated; and
transferring or merging the located record with a record associated with inode zero.

4. The method of claim 1 , wherein the file system request is a request for disk defragmentation, and wherein the method further comprises:
for each inode having multiple extents, summing a total size required for the multiple extents and generating a list of extents in a predetermined order;
invoking a copy process to relocate blocks on disk to generate a new layout of the disk having fewer fragmentation; and
synchronizing the file system cache with metadata stored in disk sections of the disk in the new layout, including encoding metadata from the file system cache and storing the encoded metadata in headers of the disk sections.

5. The method of claim 1 , wherein the generating of the encoding of the allocation map comprises:
initializing a data structure representing a list of inode numbers (LIN) and a data structure representing a list of block sets (LBS);
for each entry of the LBS, generating and outputting a first code when a respective set represents only one inode and the represented inode is the same inode as a previous extent;
generating and outputting a second code when the respective set represents only one inode and the represented set is not included in the LIN;
generating and outputting a third code when the respective set represents only one inode and the represented set is included in the LIN; and
generating and outputting a fourth code when the respective set represents a plurality of inodes.

6. The method of claim 5 , wherein the generating of the encoding of the allocation map comprises:
encoding a bit to indicate whether the represented inode includes any uncoded extents in a current disk section; and
removing a file system cache entry associated with the represented inode from the LIN if when the represented inode does not include any uncoded extents in the current disk section.

7. A non-transitory machine-readable medium having instructions stored therein, the instructions to cause a processor to:
maintain, by the processor, a file system stored on a disk, wherein the disk comprises a disk section, and wherein the disk section comprises a data segment and a variable-sized metadata segment, and wherein the variable-sized metadata segment comprises:
(1) an encoding of an allocation map of a plurality of disk blocks of the disk section, wherein the encoding of the allocation map is generated via hierarchical set-partitioning compression,
(2) a state of a first inode of the file system, and
(3) an extent of disk blocks allocated to the first inode;

maintain, by the processor, a file system cache associated with the file system, wherein the file system cache comprises a cache entry corresponding to the first inode, and wherein the cache entry specifies:
a starting physical block number of the extent of disk blocks allocated to the first inode,
a starting logical block number relative to the first inode, and
a length of the extent;

maintain, by the processor, an index of the file system cache, the index comprising an index entry that maps at least one of an ending physical block number of the extent or an ending logical block number of the extent to the first inode;
receive a first file system request with respect to the disk section;
in response to the first file system request, retrieve and decode the variable-sized metadata segment;
service the first file system request using the decoded variable-sized metadata segment;
update, by the processor, the cache entry using the decoded variable-sized metadata segment and the index of the file system cache;
receive a second file system request; and
service the second file system request in view of the updated file system cache.

8. The non-transitory machine-readable medium of claim 7 , further comprising executable instructions causing the processor to:
examine an extent allocated to inode zero in an attempt to locate a closest extent of an inode in view of an extent requested in the block allocation;
modify, by the processor, a record of inode zero to a new inode and updating indices of the file system cache when the extent of inode zero equals to the requested extent; and
reduce the extent of inode zero and creating a new record in the file system cache for blocks allocated for the request when the extent of inode zero is larger than the requested extent.

9. The non-transitory machine-readable medium of claim 7 , further comprising executable instructions causing the processor to:
look up, by the processor, extents in the file system cache using the index of the file system cache to locate a record associated with a block being deallocated; and
transfer or merge the located record with a record associated with inode zero.

10. The non-transitory machine-readable medium of claim 7 , further comprising executable instructions causing the processor to:
for each inode having multiple extents, sum, by the processor, a total size required for the multiple extents and generate, by the proce

Assignees

• Whitehouse Steven
• Red Hat Inc

Inventors

• Whitehouse Steven

Classifications

• G06F16/13

  File access structures, e.g. distributed indices (arrangements of input from, or output to, record carriers G06F3/06) · CPC title

• G06F16/172

  Caching, prefetching or hoarding of files · CPC title

• G06F2212/466

  Metadata, control data · CPC title

• G06F12/0866 Primary

  for peripheral storage systems, e.g. disk cache · CPC title

• G06F17/30132

  Physics · mapped topic