Saving a snapshot of free space of a file system on persistent storage

A mechanism for saving a snapshot of free space of a file system on persistent storage is disclosed. A method of the invention includes determining whether generation numbers stored in each of a free space cache inode of an on-disk free space cache of a block group, a free space cache item, and a free space cache header are valid, determining whether a checksum generated for a first page of the free space cache matches a checksum stored in the file system and associated with the free space cache, and adding entries stored in the on-disk free space cache to an in-memory free space cache for the block group kept in volatile memory of a computing device, wherein the on-disk free space cache is stored in persistent data storage indexed by a file system of the computing device.

TECHNICAL FIELD

The embodiments of the invention relate generally to file systems and, more specifically, relate to a mechanism for saving a snapshot of free space of a file system on persistent storage.

BACKGROUND

Currently, a variety of file system structures exist in the computing environment. One such file system structure is the B-tree file system (BTRFS), which is a GPL-licensed copy-on-write (COW) file system for Linux™. In a BRTFS, everything in the file system, such as inodes, file data, directory entries, and so on, is an ‘item’ in a COW B+tree. BTRFS is structured as several layers of trees, all using the same b-tree implementation to store their various data types as generic ‘items’ sorted on a ‘key’ that specifies an object id and an item type, so that BTRFS is data agnostic. An ‘item’ is a data structure used in BTRFS which includes a combination of a ‘key’ data structure (where to find the item itself), a type of the item, and an offset where the data referenced by the item can be found. ‘Items’ are packed together (or pushed out to leaves) in arrangements that optimize both access time and disk space. In most cases in BTRFS, ‘items’ for the same object end up adjacent to each other in the tree, ordered by type.

Moreover, BTRFS provides extent-based file storage. An extent is a contiguous area of storage. In BTRFS, extents are zoned into block groups, which default to 4 KB in size and contain only file data. Each node and leaf of the BTRFS is an extent in the b-tree. Nodes are extents full of <key, block header> pairs, and leaves contain ‘items’. The extents for large file data are kept outside the BTRFS b-tree, with an extent ‘item’ in the leaf describing the extent where the large file data is kept. Small files that occupy less than one leaf block may be packed into the b-tree itself, inside of the extent ‘item.’

An extent allocation tree (also called an extent tree) is used to track space usage by extents and manage allocated space on the extent trees in the BTRFS. The space available can be divided between a number of extent trees and reduce lock contention and give different allocation policies to different block ranges.

When mounting a file system, such as a BTRFS, a free space cache is typically generated in memory to keep track of the free space available in the file system. When an application running on the computer system needs disk space, it requests a region of specified size from the file system included in the computer system. The file system manages unallocated storage space, and may use a data structure stored in primary memory (e.g., random access memory (RAM)) to determine what storage space to allocate to the application to satisfy the request. Various data structure may be used to represent the free space available in the file system. For instance, an extent may be used to represent the offset and the length of free space available in a block group. Additionally, a bitmap may also be used, which utilizes bits to represent whether particular page blocks are free or not.

However, in typical file systems, generating such a free space data structure in memory is a very intensive process. Typically, to generate a free space cache, the extent allocation tree is referenced to determine what is free in each block group of the file system. To do this, the extent allocation tree must be walked to read all of the extent block groups and determine what space is free in the block group. This means that many blocks (e.g., in the order of thousands) in the memory structure need to be searched, which can be time-consuming and inefficient, resulting in performance slowdowns.

DETAILED DESCRIPTION

Embodiments of the invention provide for a mechanism for saving a snapshot of free space of a file system on persistent storage. A method of embodiments of the invention includes determining whether generation numbers stored in each of a free space cache inode of an on-disk free space cache of a block group, a free space cache item, and a free space cache header are valid, determining whether a checksum generated for a first page of the free space cache matches a checksum stored in the file system and associated with the free space cache, and adding entries stored in the on-disk free space cache to an in-memory free space cache for the block group kept in volatile memory of a computing device, wherein the on-disk free space cache is stored in persistent data storage indexed by a file system of the computing device.

Embodiments of the invention provide a mechanism for saving a snapshot of free space of a file system on persistent storage. Specifically, in the file systems of various operating systems (OSs), structures are held in memory to keep track of free space. The generation process for this free space cache is very intensive, resulting in performance slow downs. Embodiments of the invention use a special inode in each block group, a free space item, and a free space cache header, so that only a few blocks need to be read to generate a complete free space cache, instead of searching thousands of blocks to generate the cache.

FIG. 1illustrates a diagrammatic representation of a machine in the exemplary form of a computer system100within which a set of instructions, for causing the machine to perform any one or more of the methodologies discussed herein below, may be executed. The machine may be a personal computer (PC), a tablet PC, a set-top box (STB), a Personal Digital Assistant (PDA), a cellular telephone, a web appliance, a server, a network router, switch or bridge, or any machine capable of executing a set of instructions (sequential or otherwise) that specify actions to be taken by that machine. Further, while only a single machine is illustrated, the term “machine” shall also be taken to include any collection of machines that individually or jointly execute a set (or multiple sets) of instructions to perform any one or more of the methodologies discussed herein.

The exemplary computer system100includes a processing device102, a main memory104(e.g., read-only memory (ROM), flash memory, dynamic random access memory (DRAM) such as synchronous DRAM (SDRAM) or Rambus DRAM (RDRAM), etc.), a static memory106(e.g., flash memory, static random access memory (SRAM), etc.), and a persistent data storage device118(e.g., hard disk drive, optical drive, etc.), which communicate with each other via a bus130.

The computer system100may further include a network interface device108. The computer system100also may include a video display unit110(e.g., a liquid crystal display (LCD) or a cathode ray tube (CRT)), an alphanumeric input device112(e.g., a keyboard), a cursor control device114(e.g., a mouse), and a signal generation device116(e.g., a speaker).

The persistent data storage device118may include a machine-accessible storage medium128on which is stored software124embodying any one or more of the methodologies or functions described herein. For example, software124may store instructions for a storage space manager180to perform saving a snapshot of free space of a file system on persistent data storage. The software124may also reside, completely or at least partially, within the main memory104and/or within the processing device102during execution thereof by the computer system100. In addition, the main memory104and the processing device102also constituting machine-accessible storage media. The machine-readable storage medium128may also be used to store instructions to perform saving a snapshot of free space of a file system on persistent data storage device118, and/or a software library containing methods that call the above applications.

In one embodiment of the present invention, at least a portion of the persistent data storage device118is managed memory. Managed memory is allocated and deallocated according to the needs of one or more applications (programs) and/or an operating system (OS). Means for managing portions of persistent data storage device118may be implemented in hardware, software, or a combination thereof. In one embodiment, the means for managing persistent data storage device118is a storage space manager (SSM)180that may be included in a file system. The storage space manager180may be responsible for assigning (allocating) and freeing (deallocating) portions of persistent data storage device118, and/or for making calls to the general purpose memory allocation library that do so. One embodiment of the storage space manager is discussed in more detail in conjunction withFIG. 2. The storage space manager180may be included in one or more of the processing logic126, main memory104, or persistent data storage device118.

While persistent data storage device118and main memory104are each shown in an exemplary embodiment to be single mediums, each should be taken to include a single medium or multiple media (e.g., a centralized or distributed database, and/or associated caches, registers, etc.) that store the one or more sets of instructions.

Each of the main memory104and the persistent data storage device118may include a machine accessible storage medium, which shall be taken to include any medium that is capable of storing or encoding a set of instructions122or software124for execution by the machine and that cause the machine to perform any one or more of the methodologies of the present invention. The term “machine-accessible storage medium” shall accordingly be taken to include, but not be limited to, solid-state memories and optical and magnetic media.

FIG. 2illustrates a block diagram of one embodiment of a file system environment200that performs saving a snapshot of free space of a file system on persistent data storage. More specifically,FIG. 2illustrates the major file system components implemented in an operating system (OS)210for use in saving a snapshot of free space of a file system on persistent data storage in embodiments of the invention. Note that though the following description refers to a file system, embodiments of the present invention can also be used to manage unallocated storage space in a database management system.

In one embodiment, file system environment200includes an OS210communicably coupled to one or more block devices250. In one embodiment, OS210is executing on processing device102described with respect toFIG. 1. Furthermore, in one embodiment, block devices250are the same as persistent data storage device118described with respect toFIG. 1.

As shown inFIG. 2, OS210is divided into user space220and kernel space230. User space220contains the applications225that provide the user interface for file system calls (e.g., open, read, write, close). Kernel space230contains the components that receive and implement the logic to response to the file system calls from the user space220.

In particular, kernel space230includes a system call interface232that acts as a switch to funnel file system calls from user space220to the appropriate endpoints in kernel space230. One such endpoint is the file system240, which implements an individual file system, such as BTRFS, ext3/4, JFS, and so on. The file system240manipulates the one or more block devices250with read and write requests and other administrative tasks. The device drivers234provide the interface between the kernel space230components and the one or more block devices250, allowing them to interact.

In embodiments of the invention, file system240includes a storage space manager242to perform saving a snapshot of free space of a file system on persistent data storage. The storage space manager210may be implemented in hardware, software, or a combination thereof. In one embodiment, storage space manager242is the same as storage space manager180described with respect toFIG. 1, and manages at least portions of the persistent data storage device118ofFIG. 1.

In one embodiment, storage space manager242includes an allocator244that is responsible for assigning (allocating) and freeing (deallocating) regions of storage space in block devices250, and/or for making calls to a general purpose memory allocation library that do so. The storage space manager210conceptually divides storage space in block devices250into multiple block groups, and generates a separate search tree for managing each block group. Each search tree may be maintained in main memory of the computing device implementing the OS210, such as main memory104described with respect toFIG. 1.

Storage space is typically divided into fixed size blocks, which are sequences of bytes or bits. A block may be the smallest unit of storage space that is allocated/managed. Typical block sizes include 1 kb, 2 kb, 4 kb and 8 kb. A block group is a sequence of blocks, and is also known as an extent. In some file systems, such as BTRFS, extents are zoned into block groups, which default to 4 KB in size and contain only file data.

Using the example of BTRFS, each node and leaf is an extent in a b-tree. Nodes are extents full of <key, block header> pairs, and leaves contain ‘items’. The extents for large file data are kept outside the BTRFS b-tree, with an extent ‘item’ in the leaf describing the extent where the large file data is kept. Small files that occupy less than one leaf block may be packed into the b-tree itself, inside of the extent ‘item.’

In some embodiments, allocator244may utilize an extent allocation tree (also called an extent tree) to track space usage by extents and manage allocated space on the extent trees. The space available can be divided between a number of extent trees and reduce lock contention and give different allocation policies to different block ranges.

In one embodiment, when the file system240is first mounted (i.e. associating the file system240to the storage device250), storage space manager242generates an in-memory free space cache246to keep track of the free space available in the file system. For example, the in-memory free space cache246may be stored in main memory104described with respect toFIG. 1. When an application running on OS210needs disk space, it requests a region of specified size from the file system240. The storage space manager242will then utilize the in-memory free space cache246to determine what storage space from block devices250to allocate to the application to satisfy the request.

Various data structure may be used to represent the free space available in the file system. For instance, an extent may be used to represent the offset and the length of free space available in a block group. Additionally, a bitmap may also be used, which utilizes bits to represent whether particular page blocks are free or not.

The typical way to generate the in-memory free space cache246can be a very intensive and time-consuming process because it requires the storage space manager242to perform a full walk of the extent allocation tree to read all of the extent block groups and determine what space is free in each block group. This means that many blocks (e.g., in the order of thousands) in the memory structure need to be searched, which can be time-consuming and inefficient, resulting in performance slowdowns.

Embodiments of the invention introduce an on-disk free space cache255to be stored in the persistent data storage of block devices250in order to speed up the generation process for the in-memory free space cache246. Using the on-disk free space cache255, storage space manager242will only have to read a few blocks from the on-disk free space cache255, instead of thousands of blocks from the extent allocation tree, in order to generate the in-memory free space cache.

In embodiments of the invention, three data structures are introduced for each block group of the file system in order to support the implementation of the on-disk free space cache255: (1) a special inode for the block group's free space cache, (2) a free space cache item for the block group, and (3) a header that begins the block group's free space cache. These items are described in further detail below while describing how the on-disk free space cache255is implemented by storage space manager242.

When a file system240is first mounted by operating system210, the on-disk free space cache255does not exist. However, it is at this time that the in-memory free space cache246is created by the storage space manager242in the memory space of the computing device (e.g., RAM, etc.). At the initial mounting time, the in-memory free space cache246is created using the current technique of walking the entirety of the extent allocation tree to determine free space in the storage of the file system.

In embodiments of the invention, the on-disk free space cache255is created/written out to disk (i.e. persistent data storage) upon each transaction commit operation by the file system240. The on-disk free space cache255is only written out to disk for those block groups that have modifications reflected in the transaction commit being written out.

In order to create the on-disk free space cache for a block group, a special free space cache inode is created by storage space manager242for the particular block group. In one embodiment, this free space cache inode may be kept in a root tree of the file system140. This free space cache inode will point to the space on-disk where the on-disk free space cache for the block group is stored. This free space cache inode will carry a generation number that will match the transaction that is being committed. This generation number is used for verification and validity purposes. The generation number is also stored in the file system's superblock for comparison purposes. In addition, the free space cache inode for a block group will contain a pointer to space on disk where the block group's free space cache is stored.

In addition, a free space cache ‘item’ is created by storage space manager242for the particular block group. The free space cache item holds the basic information about the block group's stored free space cache. In one embodiment, this free space cache item may be kept in a root tree of the file system140along with the free space cache inode. The free space cache item for the block group will hold the generation number of the transaction to make sure it matches the block group's free space cache inode. The free space cache item will also hold the number of entries that are contained within the free space cache and the number of bitmaps in the free space cache.

Lastly, at the front of the first page of the free space cache (on disk) for the block group is a header. The header includes a generation number of the transaction that is currently being written. In some embodiments, the header may also include a list of checksums for all of the pages in the free space cache on disk. However, in other embodiments, the checksums for the block group may be stored elsewhere, such as in an internal checksum saving infrastructure, and not necessarily in the header.

In one embodiment, when writing out the block group's on-disk free space cache, three things are written: (1) type of entry (i.e., whether it is an extent or a bitmap); (2) physical on-disk offset of the entry; and (3) physical on-disk size of the entry. If the entry is a bitmap, the bitmaps are written after all of the entries have been written, in the order they appear in the cache, so they can be read back in the proper order.

As a result, the on-disk free space cache255for a block group may look like the following:[ ]—Different blocks|—Logical SeparatorH—HeaderEE—Extent EntryBE—Bitmap EntryB—Bitmap[H|EE1|BE1] [EE2|EE3|BE2|EE4] [B1] [B2]
This on-disk free space cache255may be referenced by an associated free space cache inode and an associated free space cache item in the file system240.

In addition to writing out and creating the on-disk free space cache255for each block group, the in-memory free space cache246may also updated upon each transaction commit that writes out to the on-disk free space cache255. It is at this time that the changes being written out to the on-disk free space cache255may be reflected in the in-memory free space cache246.

In embodiments of the invention, the in-memory free space cache246essentially has the same structure that the new on-disk free space cache255has. The in memory free space cache246is a tree of entries of either extent type (offset and length) or a bitmap (a page of memory where every bit that is set to 1 represents one block of free space). As previously mentioned, when writing the on-disk free space cache255out to the block devices250, all of the entries are written out with a type and then at the end any bitmaps are written out. As a result, the in-memory free space cache246may look like this, for example:

and then the associated on-disk free space cache255would similarly look like this, for example:
|0,8192,extent|8192,4096,extent|12288,4096,bitmap|00100|

When the computing device implementing the file system240shuts down, the in-memory free space cache246may be cleared. This is when the on-disk free space cache255of embodiments of the invention can be used to speed up the in-memory free space cache generation246upon re-boot of the computing device. Upon re-start/re-boot of the computing device, any of the previously-created on-disk free space caches255can be read from to create the in-memory free space cache246. If a block group does not yet have an on-disk free space cache associated with it, then the in-memory free space cache246for that block group can be created using pervious techniques (e.g., walking the extent tree).

FIG. 3is a flow diagram illustrating a method300for creating an on-disk free space cache that is used for saving a snapshot of free space of a file system on persistent storage according to an embodiment of the invention. Method300may be performed by processing logic that may comprise hardware (e.g., circuitry, dedicated logic, programmable logic, microcode, etc.), software (such as instructions run on a processing device), firmware, or a combination thereof. In one embodiment, method300is performed by storage space manager180ofFIG. 1.

Method300begins at block310where changes are made to one or more block groups of a file system. In one embodiment, the changes may be made in response to application calls received at the file system. At decision block320, it is determined whether a transaction is to be committed to the persistent data storage device of the file system. In other words, based on protocols of the particular implemented file system it is determined whether any changes made to the block group should be written to the persistent data storage device indexed by the file system. If not, then method300returns to block310to continue making changes to one or more block groups.

If a transaction is to be committed at decision block310, then method300continues to block330where all block groups that have been changed are gathered and space in the persistent data storage device is pre-allocated for an on-disk free space cache for each block group with changes. If a free space cache for a block group already exists in on-disk, then space is not pre-allocated for that block group.

Then, at block330, for each block group to have an on-disk free space cache, a free space cache inode is created to store a generation number corresponding to the transaction id of the transaction being written. In addition, the free space cache inode for each block group includes a pointer to the space on disk (i.e., persistent data storage device) where the free space cache for the block group is held. In one embodiment, the free space cache inode for each block group is kept in the root tree (sometimes called the tree of tree roots) of the file system. If a free space cache inode already exists for a particular block group, then the generation number should just be updated.

Subsequently, at block340, for each block group to have an on-disk free space cache, a free space cache item is created to store the generation number, the number of entries in the free space cache, and the number of bitmaps in the free space cache. If a free space cache item already exists for a particular block group, then the generation number should be updated as well as the number of entries and bitmaps.

At block350, the allocated free space cache on-disk for each block group is written out. When writing out a free space cache for a block group, three things are included: (1) the type of entry (e.g., extent or bitmap), (2) the physical on-disk offset of the entry, and (3) the physical on-disk size of the entry. Once all the entries are written out, any bitmaps are written out in the order they appear in the entries in the free space cache. At block360, a header is created on the first page of each free space cache written to. The free space cache header lists checksums for all of the pages in the free space cache as well as the generation number. If a free space cache already exists, then in block350and360, the free space cache is updated with the new information accordingly with updated entries, new checksums, and a new generation number.

FIG. 4is a flow diagram illustrating a method400for creating an in-memory free space cache for a file system upon re-boot of a computer system by utilizing an on-disk free space cache on persistent storage indexed by the file system according to an embodiment of the invention. Method400may be performed by processing logic that may comprise hardware (e.g., circuitry, dedicated logic, programmable logic, microcode, etc.), software (such as instructions run on a processing device), firmware, or a combination thereof. In one embodiment, method400is performed by storage space manager180ofFIG. 1.

Method400begins at block405where it is determined by the file system, and in particular, the storage space manager, that the computing system of the file system is re-starting due to a re-boot. As a result, the storage space manager creates an in-memory free space cache from the corresponding on-disk free space cache in the persistent data storage device. The storage space manager starts by looking up all of the free space cache inodes in the root tree of the file system. For the following steps410through470, one skilled in the art will appreciate that the steps410-470may be run on a per block group basis, or can be run against all block groups at once (i.e., in series or in parallel).

At block410, a free space cache inode is examined and a generation number is pulled from the inode. At decision block415, it is determined whether the generation number is valid. In one embodiment, the generation number from the inode may be compared against a generation number in the superblock of the file system. If the generation number is not valid, then method400ends at block470where the on-disk free space cache is discarded due to inconsistency. On the other hand, if the generation number is valid, then method400continues to block420.

At block420, the free space cache item associated with the block group having the free space cache inode is looked up and a generation number is pulled from the item. At decision block425, it is determined whether the generation number is valid by comparing it against the generation number from the free space cache inode. If the generation number is not valid, then method400ends at block470where the on-disk free space cache is discarded due to inconsistency. On the other hand, if the generation number is valid, then method400continues to block430.

At block430, the header of the free space cache of the block group having the free space cache inode and item is read. At decision block435, a generation number from the header stored is compared to the free space cache item's generation number to determine if it is valid. If the generation number is not valid, then method400ends at block470where the on-disk free space cache is discarded due to inconsistency. On the other hand, if the generation number is valid, then method400continues to block440.

At block440, a checksum of the remainder of the first page (not including header) of the free space cache is generated. At decision block445, this checksum is compared to a checksum kept in the header of the free space cache for validity. If the checksum is not valid, then method400ends at block470where the on-disk free space cache is discarded due to inconsistency. On the other hand, if the checksum is valid, then method400continues to block450.

At block450, the free space cache is walked-through and all entries in the free space cache are added to an in-memory free space cache for the block group. In addition, any bitmap entries are noted in a separate list. Subsequently, at block460, once all of the entries are written to the in-memory free space cache, the bitmap pages at the end of the on-disk free space cache are cycled through and added to their corresponding bitmap entries in the in-memory free space cache. These steps are repeated for each block group in the file system having an on-disk free space cache. As a result, an in-memory free space cache can be created in a quicker and more efficient manner. Instead of reading thousands of blocks from an extent tree, just a few blocks need to be read from the on-disk free space cache.