File removal with no available disk blocks in redirect-on-write file systems

Embodiments include a method for removing a file within a redirect-on-write file system. In some embodiments, a file removal operation is detected in a file management unit, which resides in a memory unit. It is then determined that the number of free data blocks in the persistent storage is below a minimum threshold. The file removal operation is written to a log used for storing system operations. A file management unit is notified of the successful write of the file removal operation to the log used for storing system operations. The data blocks are moved from the file selected for removal to a list of free data blocks. The indirect blocks from the file selected for removal are moved to a data block removal list.

TECHNICAL FIELD

Embodiments of the inventive subject matter generally relate to the field of operating systems and, more particularly, to removing files in redirect-on-write file systems.

BACKGROUND

Operating systems are a basic component in most computer systems. Operating systems include file systems, which organize and store data within main memory and on disk (or other persistent storage). An operating system manages data in the file system with various system operations, such as operations which read and write the data in the file system. In many operating systems, storage space in the file system can be made available by removing files or data, whenever necessary. However, redirect-on-write file systems remove data differently, as they perform special operations for freeing data when free memory and disk space is limited. Without the ability to remove files or data from a file system, some computer systems may be unable to process incoming file system operations or store more data or files persistently on disk.

SUMMARY

Embodiments include a method for removing a file within a redirect-on-write file system. In some embodiments, a file removal operation is detected in a file management unit, which resides in a memory unit. It is then determined that the number of free data blocks in the persistent storage is below a minimum threshold. The file removal operation is written to a log used for storing system operations. A file management unit is notified of the successful write of the file removal operation to the log used for storing system operations. The data blocks are moved from the file selected for removal to a list of free data blocks. The indirect blocks from the file selected for removal are moved to a data block removal list.

DESCRIPTION OF EMBODIMENT(S)

The description that follows includes exemplary systems, methods, techniques, instruction sequences and computer program products that embody techniques of the present inventive subject matter. However, the embodiments may be practiced without these specific details. For instance, although examples refer to removing files in an IBM® Advanced Interactive Executive (AIX®) operating system, in other embodiments, operations described herein can also be implemented for removing files in any suitable operating system. In other implementations, well-known instruction instances, protocols, structures and techniques have not been shown in detail in order to avoid obfuscating the description.

Introduction

This section provides an introduction to concepts utilized in some embodiments of the inventive subject matter.

Some operating systems store and organize their data in file systems. These file systems may store and organize data and files using different methods and data structures. The data in the file systems can be stored in persistent storage (e.g., on magnetic disk). Data in persistent storage can be referred to as an original volume.

Some operating systems ensure data redundancy and minimize the impact of system crashes by utilizing certain data consistency methods in their file systems. Data consistency is the concept that data should be valid and accurate. If a computer system loses power, crashes, or fails, data consistency prevents the data from becoming unrecoverable or corrupted.

Operating systems can maintain data consistency using consistency snapshots. A consistency snapshot (also referred to herein as a “snapshot”) is a record of a file system's state at a given moment in time. Upon creation, snapshots are stored in main memory, but later, they are written to persistent storage. Because snapshots are eventually stored in persistent storage (e.g., on magnetic disk), operating system components can use snapshots as a guide for restoring file systems after components fail (e.g., a loss of power).

Some embodiments of the inventive subject matter include operating systems that employ redirect-on-write file systems. In some embodiments, the redirect-on-write file system's original volume contains data present when a snapshot is taken. The file system can also store, in a snapshot storage area in main memory, modifications to the original volume, where the modifications occurred since the snapshot was taken. Consequently, in some embodiments, redirect-on-write file systems redirect new write operations affecting the original volume to the snapshot's storage area in main memory. For example, if an application program wants to modify an existing file by writing new data to the file, the file system records the new data in the snapshot's storage area in main memory.

In some embodiments, the redirect-on-write file system includes a file management unit that manages the flow of data between the snapshot storage area of main memory and persistent storage. Periodically, the file management unit can determine that the data from the snapshot storage should be reconciled back into the original volume (this process is also referred to herein as “flushing the snapshot” to persistent storage). After reconciling the snapshot back into the original volume, the original volume is up-to-date, and the file management unit can then create another snapshot. As successive snapshots are created, access to the original data, tracking of the data in the snapshots and the original volume, and reconciliation upon snapshot deletion are further complicated. As these issues grow in complexity with each successive snapshot, the file management unit can track and reconcile the data modifications in the snapshot and the original volume.

There are relationships between consecutive snapshots in redirect-on-write file systems. As discussed above, a new snapshot is captured in main memory after the previous snapshot is written to persistent storage. At this point in time, the original volume is up-to-date, so the data in the original volume represents the current state of the file system.

The persistent storage area can store data in data blocks. These data blocks can be connected in structures called i-nodes, which can store basic information about files and directories. The data blocks can be connected in a tree structure, with the top data block referred to as a disk i-node block. The disk i-node block can be connected with up to sixteen indirect blocks below. The indirect blocks can also be connected with up to sixteen indirect blocks below or up to sixteen data blocks. The data blocks can store data, while the indirect blocks provide access to the data blocks. The hierarchical structure of the indirect blocks and data blocks form files and directories. The file structure is further described inFIG. 2. After the file management unit reconciles the current snapshot into the original volume (in persistent storage), data blocks that are freed after writing the consistency snapshot become available, so the next snapshot can utilize the free data blocks in persistent storage.

In some instances, removing data or files operates differently in redirect-on-write file systems than with other file systems. With other file systems, data or files can typically be removed freely without regard for remaining disk space in storage. However, with redirect-on-write file systems, a limited amount of free data blocks in persistent storage can be problematic (e.g., because file removal operations consume free data blocks in persistent storage). When the persistent storage does not have enough free data blocks to complete system calls, such as file removal or write operations, the system calls will fail. In order to avoid this situation, the system can provide an indicator when there are no free data blocks in persistent storage or when the number of free data blocks in the persistent storage is low. If such an indicator is detected, some embodiments can take measures to free-up data block in persistent storage, so file operations can execute without failure and without delay.

Handling File Removal Operations

FIG. 1is a conceptual diagram illustrating example operations for removing a file in a redirect-on-write operating system, according to some embodiments.FIG. 1depicts a computer system100, which includes persistent storage118and main memory116. In some embodiments, main memory116includes a consistency snapshot106and an operating system102. The consistency snapshot106can include a portion of the data for a file108located in persistent storage118. However, the file108can have data in both persistent storage118and the consistency snapshot106. The operating system102includes a file management unit104. The operating system102includes a file management unit104, which in some embodiments manages both data and file removal. Although the operating system102appears in the main memory116, portions of the operating system102can reside in the persistent storage118. Similarly, in some embodiments, components depicted in the persistent storage118may reside in main memory (all, in part, or as a copy).

The persistent storage118includes a data block removal list114(also referred to herein as a “tlist”), an intent log110, a free data block list112, and either all or a portion of the data in a file108. The data blocks in the free data blocks list112can be utilized for data storage during the current snapshot. However, the data blocks within the data block removal list114cannot be utilized for data storage until the current snapshot is flushed to persistent storage.

The intent log110can store system operations, such as file removal or write operations, that the file management unit104receives after the previous snapshot is flushed to persistent storage. Flushing the snapshot to the original volume (persistent storage) occurs frequently, which allows for relatively short intent logs. In the event of a system crash, the intent log can replicate the system calls that occurred after the last snapshot was flushed to persistent storage.

FIG. 1shows file removal operations in stages A-E. During stage A, the file management unit104detects a file removal operation and searches for a file108. The file's data108could be located in the consistency snapshot106, or the persistent storage118. The file management unit104may detect a file removal operation from an application or command line operation. Next (stage B), the file management unit104retrieves portions of the file from the persistent storage118.FIGS. 2A & 2Bshow an example of the state of various memory components before the file removal operation is executed. In turn (stage C), the file management unit104sends the file removal operation to the intent log110. In some implementations, the file management unit104then receives notification of a successful write of the file removal operation in the intent log110(stage D). If the number of available free data blocks in the persistent storage118is below a minimum threshold and the file removal operation was successfully written to the intent log110, then the file management unit can move data blocks within the file (i.e., the file selected for removal) to the free block list112and the indirect blocks within the file to the tlist114.FIGS. 2A & 2Bshow an example state of the memory components after a file removal operation is executed.

FIG. 2Aincludes a state diagram which illustrates an examples file system state. InFIG. 2A, an i-node includes a series of indirect blocks210and data blocks204connected to a disk i-node block202in a hierarchical manner. The disk i-node block202is the head of data tree200, which stores all of the data. In some embodiments, the disk i-node block contains up to sixteen pointers to indirect blocks210below. Each indirect block210can also contain up to sixteen pointers to data blocks204below. All of the data can be stored in data blocks204at the bottom level of the data tree, while the in data blocks210can contain the pathway information necessary to access the data blocks204. In some instances, there are indirect blocks210in the i-node which connect to other indirect blocks210. This allows for the file structure to contain more data blocks, thereby increasing the amount of data which can be stored within a single file structure.

The free data blocks list208contains all available data blocks that can be used for data storage by any application or file within the current snapshot. The tlist206contains a list of data blocks, which will become free data blocks after the current snapshot is flushed to persistent storage.

The state of the file system before a file removal operation is illustrated inFIG. 2A. The i-node can include a disk i-node block202, indirect blocks210, and data blocks204. In some embodiments, the tlist206includes a list of data blocks that have been freed in the current snapshot, but cannot be used again for data storage until the current snapshot is flushed to persistent storage. The free data blocks list208includes a list of data blocks, some of which have been freed in the current snapshot. Blocks in the free data blocks list208can be used for data storage in the current snapshot.

FIG. 2Billustrates an instance in which a file removal operation has occurred, according to some embodiments. The data blocks204and indirect blocks210have been removed from the i-node202and placed in either the free data blocks list216or the tlist218. In some embodiments, for file removal operations occurring while the persistent storage contains a number of free data blocks below a minimum threshold (e.g., there are no free data blocks), the file management unit places the “removed” file's data blocks204in the free data blocks list216—before flushing the current consistency snapshot to persistent storage. Data blocks do not store data that may be needed to reconstruct files if the system were to unexpectedly crash. Instead, data blocks store data for application programs and other processes in the computer system. Because the file management unit places the data blocks on the free data blocks list216before flushing the consistency snapshot, those blocks can be used immediately for storing data associated with file operations (e.g., file removal operations). Thus, the operating system may avoid file-removal-related stalls arising from low free space in persistent storage. The file management unit can also place the indirect blocks in the tlist218whenever the file removal operation occurs, regardless of the number of free data blocks available in the persistent storage. All of the data blocks in the tlist will be considered free data blocks after the file management unit flushes the current consistency snapshot to persistent storage.

This discussion continues with more operations for removing files in a redirect-on-write file system.

FIG. 3depicts a flow diagram illustrating example operations for removing files or directories, according to some embodiments. The flow begins at block302inFIG. 3.

The file management unit detects a removal operation (302). The file management unit may detect a removal operation from an application or command line operation. The file management unit can then determine if the removal operation targets a file or a directory (304). If the file management unit determines that the removal operation targets a directory, then the data blocks and indirect blocks associated with the directory can be moved from the directory location to the tlist (308).

If the file management unit determines that the removal operation targets a file (at304), then the file management unit can determine whether the number of available data blocks in the persistent storage is below a minimum threshold (306). If the number of available data blocks is greater than the minimum threshold (at306), then the file management unit places data blocks and indirect blocks from the file selected for removal in the tlist (308). As described above, data blocks on the tlist will not be added back to the free list of data blocks until the current snapshot is flushed to persistent storage. Thus, those tlist blocks will not be available for use in servicing other file operating occurring during the current snapshot cycle.

If the number of available data blocks in persistent storage is less than a minimum threshold (at304), then the file management unit determines whether there is available disk space in persistent storage to write the file removal operation to the intent log (310). If there is not sufficient free disk space in persistent storage to write the file removal operation to the intent log, then the file removal fails (i.e., the file management unit does not remove the file) (312). If there is adequate free space in persistent storage to write the file removal operation to the intent log (at310), then the file management unit writes the file removal operation to the intent log (314). The file management unit can then move the data blocks within the file selected for removal to the free data blocks list (316). The file management unit can also move the indirect blocks to the tlist316. In the example shown inFIG. 2B, at this point in time, the file structure will be empty.

It should be understood thatFIGS. 1-4are examples meant to aid in understanding embodiments and should not be used to limit embodiments or limit scope of the claims. Embodiments may perform additional operations, fewer operations, operations in a different order, operations in parallel, and some operations differently. For instance, according toFIG. 3, the file management unit determines whether a removal operation targets a directory or file304before determining whether the persistent storage has a number of free data blocks which is below a minimum threshold306. Some embodiments may determine whether the persistent storage has a number of free data blocks which is below a minimum threshold306before the file management unit determines whether a removal operation targets a directory or file304.

FIG. 4depicts an example computer system. A computer system includes a processor unit416(possibly including multiple processors, multiple cores, multiple nodes, and/or implementing multi-threading, etc.). The computer system also includes a memory unit404. The memory unit404may be system memory (e.g., one or more of cache, SRAM, DRAM, zero capacitor RAM, Twin Transistor RAM, eDRAM, EDO RAM, DDR RAM, EEPROM, NRAM, RRAM, SONOS, PRAM, etc.) or any one or more of the above already described possible realizations of machine-readable media. The computer system also includes a bus414(e.g., PCI, ISA, PCI-Express, HyperTransport®, InfiniBand®, NuBus, etc.), a communication interface410(e.g., an ATM interface, an Ethernet interface, a Frame Relay interface, SONET interface, wireless interface, etc.), and an I/O (input/output) interface412. The communication interface allows the computer400to communicate (e.g., send and receive data) with other computers402. Input/output interface adapters in computers can implement user-oriented input/output through, for example, software drivers and computer hardware. The I/O interface may utilize various display devices420, such as computer display screens, and various user input devices418, such as keyboards and mice.

In some embodiments, the memory unit404includes main memory424, which can include a consistency snapshot426. As discussed above, in some embodiments, the consistency snapshot426includes data for files located in persistent storage422. The memory unit404also includes an operating system. In some embodiments, there is a file management unit408included in the operating system406. The file management unit408embodies functionality to implement the operations described above. The file management unit408may include one or more functionalities that facilitate the removal of files in redirect-on-write file systems. In some embodiments, the file management unit408detects a file removal operation. Then, the file management unit408can determine that the number of available data blocks in persistent storage422is below a minimum threshold. As discussed above, the file management unit408can then remove the file.

Any one of these functionalities may be partially (or entirely) implemented in hardware and/or on the processing unit416. For example, the functionality may be implemented with an application specific integrated circuit, in logic implemented in the processing unit416, in a co-processor on a peripheral device or card, etc. Further, realizations may include fewer or additional components not illustrated inFIG. 4(e.g., video cards, audio cards, additional network interfaces, peripheral devices, etc.). The processor unit416, the I/O interface412, and the communication interface410are coupled to the system bus414. Although illustrated as being coupled to the system bus414, the memory unit404may be coupled to the processor unit416.

While the embodiments are described with reference to various implementations and exploitations, it will be understood that these embodiments are illustrative and that the scope of the inventive subject matter is not limited to them. In general, techniques for removing files in a redirect-on-write file system as described herein may be implemented with facilities consistent with any hardware system or hardware systems. Many variations, modifications, additions, and improvements are possible.