Optimizing a storage system to support short data lifetimes

A system and method for optimizing a storage system to support short data object lifetimes and highly utilized storage space are provided. With the system and method, data objects are clustered based on when they are anticipated to be deleted. When an application stores data, the application provides an indicator of the expected lifetime of the data, which may be a retention value, a relative priority of the data object, or the like. Data objects having similar expected lifetimes are clustered together in common data structures so that clusters of objects may be deleted efficiently in a single operation. Expected lifetimes may be changed by applications automatically. The system automatically determines how to handle these changes in expected lifetime using one or more of copying the data object, reclassifying the container in which the data object is held, and ignoring the change in expected lifetime for a time to investigate further changes in expected lifetime of other data objects.

RELATED APPLICATION

This application is related to commonly assigned and co-pending U.S. patent application Ser. No. 10/943,397 entitled “System and Method for Optimizing a Storage System to Support Full Utilization of Storage Space,” filed on even data herewith and hereby incorporated by reference.

BACKGROUND OF THE INVENTION

1. Technical Field

The present invention is generally directed to an improved data processing system. More specifically, one aspect of the present invention is directed to a system and method for optimizing a storage system, such as a file system, to support short data lifetimes, e.g., short file lifetimes or short object lifetimes. A second aspect of the present invention is directed to a system and method for optimizing a storage system, such as a file system, using priority based retention of data objects, e.g., files, so as to support full utilization of storage space.

2. Description of Related Art

Early file systems were designed with the expectation that data would typically be read from disk many times before being deleted. Therefore, on-disk data structures were optimized for reading of data. However, as main memory sizes increased, more read requests could be satisfied from data cached in memory. This motivated file system designs that optimized write performance rather than read performance. However, the performance of such system tends to suffer from overhead due to the need to garbage collect current, i.e. “live,” data while making room for areas where new data can be written.

New types of systems are evolving in which, in addition to reading and writing of data, creation and deletion of data are important factors in the performance of the system. These systems tend to be systems in which data is quickly created, used and discarded. These systems also tend to be systems in which the available storage system resources are generally fully utilized. In such systems, the creation of data and deletion of this data is an important factor in the overall performance of the system.

However, known file systems, which are optimized for data reads or, alternatively, data writes, do not provide an adequate performance optimization for this new breed of systems. Therefore, it would be advantageous to have a system and method that optimizes, in addition to data reads and writes, the creation and deletion of data.

All file systems have the capability for the explicit deletion of files by a program or user. Some file systems have provision for a timed delete of a file, previously scheduled by a user or program. If more files are created than deleted, eventually the system will fill, and writing new files is no longer possible. The current state of the art is tools that an administrator can use to explicitly delete files. The implication is that an administrator is forced to make decisions about the value of objects, and instigate deletion of lower value files. Therefore, it would be advantageous to have a system and method that automatically selects data to delete, retaining the most highly valued data that can fit into a file system at any given time.

SUMMARY OF THE INVENTION

The present invention provides a system and method for optimizing a storage system, such as a file system, to support short file lifetimes and highly utilized storage space. With a preferred embodiment of the system and method of the present invention, data objects may be clustered based on when they are anticipated to be deleted. That is, when an application stores data to a particular location, the application provides an indication of the useful life of the data, e.g., a relative priority or retention value (or value function) of the data object. Data objects having similar relative priorities may be clustered together in a common data structure so that clusters of objects may be deleted efficiently in a single operation. The use of these relative priorities, rather than merely waiting for data to be explicitly deleted, enables a storage system to adapt to changing priorities of different data objects, even when the storage space is fully utilized. In addition, bulk deletion allows storage space to be reclaimed efficiently and in a scalable manner.

Relative priorities may be changed by applications explicitly or implicitly. The system automatically determines how to handle these changes in relative priority using a plurality of mechanisms. These mechanisms may include, for example, copying the data object, reclassifying the container in which the data object is held, ignoring the change in relative priority for a time to investigate further changes in relative priority of other data objects, and ignoring the change indefinitely.

Moreover, the retention values of the data objects may be utilized with or without grouping of the data objects into common data structures, i.e. containers, so as to achieve a fully utilized storage system. That is, the retention values may be used such that when a fully utilized storage system needs to store new data objects/containers of data objects, data objects/containers are deleted based on the retention values so as to provide sufficient storage space for the new data objects/containers. This deletion may be performed based on a delete threshold, a sorted list of retention values for data objects/containers, or the like.

Thus, the present invention provides a first aspect of grouping data objects based on expected lifetimes of the data objects so that data objects having similar lifetimes may be deleted in bulk when necessary. In addition, the present invention provides a second aspect of the present invention that permits prioritization of data objects/containers based on their relative retention values such that data objects/containers are deleted in accordance with their relative retention values when necessary to ensure a fully utilized storage system. These aspects may be used separately or in combination to achieve a storage system that is optimized for short lifetime data objects and a continually full storage system.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

The present invention provides a system and method for optimizing a storage system under high loads. A first aspect of the present invention optimizes a storage system, such as a file system, to support short data lifetimes, e.g., short file lifetimes in a file system or short object lifetimes in an object storage system. A second aspect of the present invention provides a system and method for optimizing a storage system, such as a file system, using priority based retention of data objects so as to support a highly utilized storage system. The present invention may be implemented in a distributed data processing system, such as the Internet, a local area network, a wide area network, storage area network, or the like. In addition, the present invention may be implemented in a stand-alone computing system. In order to provide a context with regard to the types of computing devices in which the aspects of the present invention may be implemented,FIGS. 1-3are described hereafter as example computing environments and computing devices in which aspects of the present invention may be implemented. It should be appreciated thatFIGS. 1-3are only exemplary and are not intended to state or imply any limitation with regard to the types of computing environments and/or computing devices in which the present invention may be implemented.

As another example, data processing system300may be a stand-alone system configured to be bootable without relying on some type of network communication interfaces. As a further example, data processing system300may be a personal digital assistant (PDA) device, which is configured with ROM and/or flash ROM in order to provide non-volatile memory for storing operating system files and/or user-generated data.

The depicted example inFIG. 3and above-described examples are not meant to imply architectural limitations. For example, data processing system300also may be a notebook computer or hand held computer in addition to taking the form of a PDA. Data processing system300also may be a kiosk or a Web appliance. The present invention provides a system and method for optimizing a storage system, such as a file system, for short data object lifetimes and high storage utilization. In one aspect of the present invention, data is stored in association with other data having similar expected lifetimes to effectuate bulk deletions and to optimize the creation/deletion of data in the storage system. In one exemplary embodiment, data that is stored in association with each other may be deleted in bulk when predetermined criteria are met, e.g., a delete threshold is met. In other exemplary embodiments, mechanisms are provided for modifying the association of data based on changes to the expected lifetimes of the data.

In a second aspect of the present invention a system and method for optimizing a storage system, such as a file system, to run at close to 100% storage utilization are provided. In one exemplary embodiment of the present invention, portions of data having associated expected retention lifetimes are used along with a measure of storage system usage to determine when to delete data from the storage system. In another exemplary embodiment, a sorted list of retention values of portions of data, e.g., data objects or files, or containers of data is used to determine which portions of data to delete to make available storage space to store new portions of data. These and other aspects of the present invention will be described in detail in the description hereafter.

The present invention may be implemented in a distributed data processing environment or in a stand-alone computing system. For example, the present invention may be implemented in a server, such as server104, or client computing device, such as clients108-112. Moreover, aspects of the present invention may be implemented using storage device106in accordance with the present invention as described hereafter. The configuration of the present invention is based upon a number of observations made of log-structured file systems. Therefore, a brief explanation of a log-structure file system will first be made. In its earliest incarnation, the log-structured file system was envisioned as a single contiguous log in which data was written at one end of a wrap-around log and free space was created at the other end by copying “live” files to the first end. This had the disadvantage that long-lived data would be continually garbage collected, resulting in high overhead. The problem of long-lived data was solved by segmenting the log into many fixed-size units, which were large enough to amortize the overhead of a disk seek relative to writing an entire unit contiguously. These units, called “segments,” were cleaned in the background by copying live data from segments with low utilization (i.e., most of the segment already consists of deleted data) to new segments of entirely live data. See “The Design and Implementation of a Log-Structured File System,” by Rosenblum and Ousterhout, ACM Transactions on Computer Systems, 1991, which is hereby incorporated by reference.

One of the basic embodiments of the present invention is based on treating an entire file system as a wrap-around log, in which data objects are written once, then overwritten when the log wraps. Useful data may be copied to a more permanent storage location before the log wraps. The present invention does not entail any garbage collection and there are no specific guarantees that data will be retained. Files are deleted after some interval, the duration of which may be estimated in advance but may be determined in practice by the rate at which new data is written, for example.

The present invention is further expanded by observing that there may in fact be many logs, with potentially different storage allocations, thereby wrapping at different rates. A data object may be written to a particular log, resulting in it being overwritten when that log wraps. One log may wrap approximately every hour while another may wrap once per day, for example.

The present invention is further based on the observation that it is possible to use multiple segments to place data together that are expected to be deleted together. For instance, if an application knows that everything it creates in the next 5 minutes is likely to be deleted within 6 hours, then by placing all that data in one log-file system container, e.g., a segment, regardless of what else is being written, the entire container may be reclaimed in 6 hours without any cleaning overhead.

As a further enhancement made by the present invention, improved performance may be obtained by allowing for best-effort retention of data objects. This best-effort retention may be performed with regard to individual objects, containers of objects, or a combination of individual objects and containers of objects. With this further enhancement, the system can choose to delete objects, rather than copy them to new containers or segments, based on a priority that has been specified for retaining the data objects. In one exemplary embodiment of this type, containers or segments have a priority that is tied to the priority of the objects they contain. When an object's priority changes, the system makes a determination whether to leave the container alone, change the priority of the container, or copy the object to a new container. This determination may be deferred until any time before the container is actually permitted to be overwritten. Priorities can vary over time, but they can also be determined by other criteria such as access patterns.

In an alternative embodiment, rather than prioritizing data objects based on containers, a plurality of data objects may be provided that are each associated with a respective retention value that identifies a relative importance for storing the data object in the storage system as compared to other data objects having different retention values. These data objects are stored in the storage system in association with their respective retention values. The retention values provide a mechanism by which a relative priority for retention of data objects may be determined based on the associated retention values of the data objects. Based on this relative priority of retention of data objects, when it is necessary to free storage space for new objects, existing data objects may be deleted in accordance with the determined relative priority for retention of the data objects until a sufficient amount of storage space for the new objects has been freed.

With these observations in mind,FIG. 4illustrates a method by which data may be stored in a data storage system in accordance with one exemplary embodiment of the present invention. As shown inFIG. 4, a host system410includes one or more applications420which may store and retrieve data from storage system430. The host system410may be separated from the storage system430and in communication with the storage system430via communication links, such as via a local area network, a wide area network, the Internet, or the like. Alternatively, the storage system430may be integrated with the host system410in the same computing system.

As illustrated inFIG. 4, the application420may store data objects440in the storage system430. The data objects440may be of arbitrary size. Many data objects440will be just a few bytes in size. While some data objects440may be discarded immediately and never make it to secondary storage, e.g., physical storage device450, a substantial amount of data objects440will be written to physical storage device450, e.g., hard disk, magnetic tape, etc., read once or a small number of times, and then quickly deleted. Depending on system load and priorities, some data objects440may be deleted before ever being read. A relatively small fraction of the data objects440will be retained for a long time and read repeatedly. In this environment, it is observed that as data object lifetimes become short, and all other things are equal, Little's Law requires that a fixed-size storage system will have increasing create/delete rates, i.e. rates at which data objects440are created in physical storage system450and deleted from physical storage system450. Since creates/deletes may involve random disk I/O, and disk technology is progressing faster in density than access rate, this will become increasingly important in the performance optimization of future storage systems.

Two key notions in the design of the storage system of the present invention, i.e. characteristics of data storage that are sought to be supported by the present invention, are immutability and relative valuation. First, data objects440are immutable once created. Thus, the only operations on data objects that involve their data are to write them initially, read them, or delete them.

Second, there are additional operations to affect the metadata of a data object, particularly its retention value (RV). When a data object440is created, it is given a current retention value (CRV) that indicates the relative importance of keeping the data object440, and a function defining how the CRV changes over time, e.g., either decaying or increasing over time. The terms “current retention value” (CRV) and simply “retention value” (RV) are used interchangeably herein. For purposes of the present description it is assumed that the function defines a decay of the CRV, i.e. that the function is a decay function, since this is the most probable implementation for ensuring that a storage system does not become over utilized. However, it should be appreciated that an increasing CRV function may be used without departing from the spirit and scope of the present invention. Thus, objects440may naturally age out of the storage system430over time based on their initial retention value, i.e. the CRV of the objects440when they are first stored in the storage system430, and the decay function associated with the data object440.

In one exemplary embodiment, data objects440themselves may not be assigned the function but rather the container460to which the data objects440are assigned has the associated function and a container460retention value that is determined based on the current retention values of the data objects440within the container460. That is, for example, when an application wishes to write a data object440to the data storage system430, the application420initiates storage of the data object440by instructing the data storage system430to prepare for receipt of a data object440having a particular retention value and decay function. In actuality, the application420will typically initiate a stream of data objects440that are destined for a container460in the storage system430. In response, the storage system430initiates a data container460in which the data objects420having a same or similar retention value are maintained. A plurality of containers460may be established for data objects having different retention values and/or decay functions. The way in which these containers460, their retention values, and decay functions, are used to manage storage of data objects in a prioritized manner and perform bulk deletions will be described in greater detail hereafter.

Another aspect of the storage system430is that there may exist some applications420that are designed to take data objects along a pipeline, often in an arbitrary order. Rather than an application420requesting a specific data object440and suffering the latency of retrieving that data object440, through use of the present invention, applications may be designed to receive a stream of data objects, the order of which is dictated by a resource manager. For example, a web crawler that processes retrieved pages may not be concerned with pages it processes first, only that it processes all recently crawled pages in some order.

The retention values (RVs) and current retention values (CRVs) and their associated decay functions may be absolute terms for identifying how long a data object440is to be retained in the storage system430or may be regarded as only hints or suggestions about how long to retain a data object440in the storage system430. In other words, there are no absolute guarantees as to how long data objects will be retained in the storage system430. Thus, unlike traditional file systems that write a file and then ensure the availability of that file until it is deleted or overwritten, the storage system430of the present invention writes a data object440to physical storage device450, maintains a metadata entry for the data object and its associated container460in either memory or other data storage, e.g., disk, and then makes a good-faith effort to retain the data object440in the physical storage device450in accordance with its specified RV. As data objects are processed, their processing can affect the RV of various data objects (themselves or others), causing them to be retained for longer or shorter periods. However, the storage system430is designed with the expectation that explicit updates to existing RVs are relatively uncommon. In a steady state, most data objects will not explicitly change their RV before deletion. For example, in some implementations of the present invention, only approximately 10-20% of data objects will explicitly change their RV before deletion. Most data objects will have their RV changed implicitly through the use of a decay function, but all objects within a container will have similar decay, thus there will be no relative change between two objects in a single container.

The large number of small data objects typically encountered requires some form of aggregation to amortize I/O overheads. Clustering objects into collections of data, all written contiguously, makes sense from the standpoint of write performance. However, units such as the segments used in log-structured file systems can suffer from high overheads from garbage collection when the overall storage utilization is moderately high. If there are no segments without any “live” data, the system must garbage-collect to coalesce live data into fewer segments and create entirely empty segments to be reused. In contrast, deleting an entire empty segment at once, without the need to copy “live” data to a new segment, can improve performance dramatically.

The key to such performance gains is the ability for applications420to predict, at object creation time, which data objects440are likely to be deleted together, i.e. have the same expected life time. By clustering data objects440into different groups that depend on their anticipated lifetime, the system can create segments that can be reclaimed in their entirety at an appropriate time without the need for cleaning. These groups or collections are the storage containers460previously mentioned above.

As data objects440are created by applications420, they are annotated with an initial retention value, e.g., a value between 0 and 1, with 1 referring to data objects that should be retained if at all possible. The data objects440are also annotated with a decay function that specifies the anticipated retention decay of the object's data. As mentioned above, rather than associating the decay function with the data objects, however, in another alternative embodiment, the decay function may be associated with the data container460in which the data object440is stored.

FIG. 5provides examples of decay curves that may be used with data objects in accordance with an exemplary embodiment of the present invention.FIG. 5shows curves510,520,530,540, and550, which represent different retention values as a function of time. Curves510,520, and530represent decay curves that transition from a high value to a low value in the space of a small number of time units (for example 10-30 minutes), while curves540and550are “long-term” decay curves that cause retention values to stay high for a prolonged period (for example, days) before falling. These curves are merely illustrative and many other possible decay curves are possible.

A decay function, in the present storage system430, may either provide an indication of the actual time that the data object will be retained or may be just a statistical formulation that is not a guarantee of retention time of the data object. That is, in one exemplary embodiment, since retention values may be modified by applications outside the operation of the decay function, and dynamic utilization of the storage system may be used to determine what data objects should be deleted, some data objects may be deleted long before they are anticipated to be deleted as the retention value would suggest. Similarly, some data objects may survive well past the expected point of deletion.

Current retention values (CRVs) and anticipated retention decays (ARDs) may be changed at any time by an application420. The ARD is a value that indicates the expected lifetime of the data objects440as determined from the current retention values and the decay function. A container may have an associated ARD based on the ARD of the data objects that are, or are to be, stored in the container. A data object440whose retention value increases should be expected to survive longer in the data storage system430. Similarly, a data object440whose retention value is decreased is expected to survive a shorter amount of time in the data storage system430.

The pressure on the storage system430to store data objects is expected to vary over time. When the rate of data object writes surpasses the rate of data object deletions, the total storage utilization increases. Over short times, discrepancies between data object reads and writes are expected, but eventually they must be synchronized. This is accomplished by having a high water mark or threshold that defines a current retention level. Those data objects, or containers of data objects, that have retention values that are equal to or below the high water mark or threshold will be reclaimed, i.e. deleted. Those data objects, or containers of data objects, that have retention values that are above the high water mark or threshold will be retained in the storage system430. As available storage space in the storage system430, i.e. available storage space in the physical storage device450, decreases below a predetermined minimum amount, the high water mark or threshold is increased. As the available storage space increases past this predetermined minimum amount, the high water mark or threshold may be reduced.

Thus, in summary, with a preferred embodiment of the present invention, applications420predict the useful life of data objects being generated by the applications420at data object creation time and associate a retention value and decay function with these data objects. The data objects are sent to the storage system430where the retention value and decay function are used to create a container460for the data objects440. The container460contains data objects440having similar initial retention values and, optionally, decay functions. It should be noted that in an embodiment in which the decay functions are associated with the individual objects, each data object440may have its own decay function and thus, its retention value may decay at a different rate than other data objects within the same container460.

The data objects440are first stored in the container460. When either the container460is full, after a predetermined delay, or when the container460is manually flushed (i.e. written to disk or other “permanent” storage), the data objects in the container460are written to one or more segments in the physical storage device450to ensure integrity. Metadata referencing the container460, and the data objects440in the container460, is maintained within the memory470or may itself be stored in secondary storage. The retention values of the data objects440stored in the storage system430may be modified by the applications420and by application of the decay functions associated with the data objects. In addition, a delete threshold is established for determining which data objects to delete, e.g., mark for deletion or mark as available to be overwritten, from the physical storage device450. This delete threshold may be dynamically increased or decreased as available storage space in the physical storage device450increases or decreases. Data objects440or containers460that have retention values that are below or equal to the delete threshold are marked for deletion while those that have retention values above the delete threshold are retained in the storage system430.

As an alternative to using the delete threshold, in another embodiment of the present invention, a sorted list of stored object retention values may be maintained. When it is necessary to create additional room for new objects, this sorted list may be used to identify objects/containers that have a lowest retention value so that these data objects/containers may be deleted first until a required amount of storage space is freed. The sorted list may be updated dynamically as data objects are created/deleted. The sorted list may include an identifier of the data object/container and its retention value and may be sorted based on the retention value. Thus, rather than using a dynamically determined delete threshold, when the amount of storage space usage increases above a predetermined amount, the sorted list is provided as a mechanism for prioritizing or ranking which data objects/containers are to be deleted first prior to other data objects/containers.

With regard to the containers460referenced above, these containers take advantage of the combination of high data rates, rapid data object deletion, and predictable relative retention values. Any given combination of initial CRV and ARD is extremely likely to have a steady stream of new data objects being sent to the storage system430. In such cases, these data objects are written to a storage container460that holds data objects having a particular retention value and optionally, a particular decay function. Thus, in some embodiments, the containers460specify a retention value that the data objects must initially have, in other embodiments, all of the data objects must have not only the same initial retention value but also the same decay function. For example, in one embodiment of the present invention, the container460stores data objects having a particular initial retention value and which were created within a predetermined time interval of each other. When the storage container460is full, or after an appropriate delay, it is written to disk in a single high-bandwidth operation with metadata for the container460and data objects440within the container460remaining in memory470.

Grouping data objects by retention value and writing large containers460contiguously to the physical storage450in one high-bandwidth operation makes writing of data objects more efficient. Similarly, because the data objects are written predominantly in a contiguous manner in the physical storage450, sequential reading of data objects is also made more efficient. That is, since many related data objects are stored in close proximity to one another in the physical storage450, they will tend to be read together in a single large I/O operation at a later point.

As mentioned above, the applications420may be optimized to accept data that is provided with some ordering or may often be provided in an arbitrary order. There are two primary ways in which this ability is supported in the applications420. First, applications420may be designed to have data objects pushed to them rather than having to request the data from the storage system430. Rather than deciding what data objects to read, the applications420are designed to permit an external optimizer480to read the data objects that are the “best” available, e.g., due to the a combination of factors that include their expected time to live, the performance of reading particular objects, and inter-object dependencies. Even applications that decide on specific data objects to read can improve performance substantially by specifying a long list of data objects prior to actually accessing them and allowing the underlying storage system430to prefetch data as efficiently as possible. See “Informed Prefetching and Caching,” by Patterson, et al., Proceedings of the 15th ACM Symposium on Operating System Principles, 1995, which is hereby incorporated by reference.

Second, in some embodiments] the host system410will always have more work to do than available resources. Therefore, its scheduler490can run those applications that have their data immediately available. With rare exceptions for high priority analysis, should an application need a specific data object read from physical storage450, the added latency for that application is unimportant as long as the system as a whole consistently makes progress.

As discussed previously, with the present invention, retention values are permitted to change, either by explicit changing of the retention value by an application or by virtue of the decay function associated with a data object. In a preferred embodiment of the present invention, retention values are set as values between 0 and 1 with 1 denoting data objects that are not to be deleted until specifically deleted by an application. If applications420choose to set too many data objects to an absolute current retention value of 1, such that the storage system430runs out of storage space in physical storage device450, an exception is triggered. An application420that wishes to increase the relative value of a data object can modify it to have a higher retention value, and the storage system430endeavors to keep the data object an appropriately longer interval, although as mentioned above, the retention value is only a suggestion as to how long to keep the data object and is not absolute.

With the present invention, there are basically three approaches to handling changes in retention values of data objects in containers. These three approaches are illustrated with reference toFIGS. 6-8.FIG. 6illustrates a storage system in which there are three containers610,620and630. Container610stores data objects612having a first retention value RV1 and a decay function that is equivalent to retaining the data objects612for approximately 1 hour in physical storage, i.e. the container610has an ARD of 1 hour. Container620stores data objects622having a second initial retention value RV2 and a decay function that is equivalent to retaining the data objects622for approximately 2 hours in physical storage, i.e. the container620has an ARD of 2 hours. Container630stores data objects632having a third initial retention value RV3 and a decay function that is equivalent to retaining the data objects632for approximately 1 day in physical storage, i.e. the container630has an ARD of 1 day or 24 hours.

It is assumed now that the retention values of objects within the containers610-630are modified, either directly by an application or through application of a decay function, associated with the data object, to the retention values. Most commonly, a decay function is applied to each object in a container, and the retention value of the container is adjusted accordingly. If not all objects are updated simultaneously, the system must address any discrepancies among the retention values of objects in the container. A first option for handling the change in retention value is to move any data object that has its retention value change such that it is inserted into a new storage container with an appropriate overall retention value. A consideration here is that occasional changes to retention values may not have the same steady-state behavior as a constant stream of external inputs, leading to a storage container being written when it is largely empty or, conversely, being kept in memory while the system attempts to fill it.

A variant of this first option is to write the changed object into an existing container. This can be done if an appropriate container has space, either because other objects have been deleted or moved, the container otherwise has not been completely filled, or because some space has been reserved in the first place for such move operations. Writing objects in an existing container is analogous to “hole-plugging” in a log-structured file system, as described in “The HP AutoRAID hierarchical storage system,” by Wilkes, et al., ACM Transactions on Computer Systems, 1996, which is hereby incorporated by reference.

A second option is to ignore the change to the retention value of the data object entirely or to note the change and await a large enough aggregate change. Since all retention values are merely hints or suggests as to how long a data object will be retained in physical storage, it is acceptable to delete something “prematurely” if keeping it longer would present a hardship to the storage system as a whole. Thus, for example, as single data object with a retention value of 0.7 and an ARD of one day might be kept in a container having a retention value of 0.6 and an ARD of 12 hours. However, changing a second data object to a retention value of 0.7 may trigger copying the two objects to another container having an appropriate retention value and ARD or adjusting the entire container as described hereafter.

A third option is to affect the entire container in which the object resides. That is, for example, when a sufficient number of data objects within the container have their retention values modified such that the retention value of the container no longer accurately reflects the retention values of the data objects within the container, the retention value of the container may be modified. For example, the average retention value of the data objects within the container may be calculated and a determination may be made as to whether this average is significantly different from a current retention value of the container, e.g., an absolute value of the difference between the average retention value and the current retention value of the container is greater than a predetermined threshold. If the average retention value is significantly different from the current retention value, then the current retention value of the container may be modified to be the average (or other function, e.g., maximum) retention value of the data objects within the container.

These three options are implemented in the storage system as container policies that are applied during the management of containers in the storage system. The container policies determine when to move data objects from one container to another, when to keep data objects in the same container even though the retention value of the data objects have changed, when to modify the retention value and ARD of the container as whole based on changes to data objects within the container, and when to delete data objects/containers from the storage system. The application of these policies is illustrated with reference toFIGS. 7 and 8.

As shown inFIG. 7, data objects12,19,21and22have had their retention values changed such that the data objects are to be deleted from the storage system earlier. However, these data objects are kept in container620in accordance with the container policies. For example, the container policy may take an average of the retention values of data objects within container620and determine whether the absolute value of the average retention value is more than a threshold amount from the current retention value of the container620.

If the absolute value of the average retention value is not more than a threshold amount from the current retention value of the container620, a determination may be made as to whether there is space in another container having an appropriate retention value for the data objects that have had their retention values modified. If so, then the data objects that have had their retention values modified may be moved to this other container. This is illustrated inFIG. 7with regard to data objects4and25. As shown inFIG. 7, data object25is deleted from the storage system. This deletion may be an explicit deletion by an application or based on a comparison of data object25's retention value and the current delete threshold for the storage system. For example, the retention value of data object25may be less than the current delete threshold and, as a result, data object25may be deleted from the storage system, e.g., marked as available to be overwritten. More likely, the deletion of data object25is an explicit deletion of the data object by an application rather than being based on a retention value falling below the delete threshold since all of the objects in container630have the same retention value and as such, the container630as a whole would have been deleted if the retention value fell below the delete threshold.

The deletion of data object25provides available storage space in container630. Data object4has had its retention value modified to a higher retention value, such as by an application, so that it now corresponds with the retention value of container630. Since there is available storage space in container630for data object4, the application of the container policies to the management of the containers may result in data object4being copied into container630and deleted from container610, as shown.

If the difference between the average retention value of the data objects and the retention value of the container is greater than the predetermined threshold, then the retention value of the container may be modified. This is shown inFIG. 8where a majority of the data objects622in the container620have had their retention values modified. As a result, it is determined that the retention value of the container620should be modified to RV4 with a resulting ARD of 1 hour. It should be noted that the measurement of the “1 hour” ARD is based on the storage of the initial data object in the container620. Thus, although the retention value, and thus, the resulting ARD, have changed, this does not mean that the data objects in the container are necessarily retained for a longer period of time, i.e. the time period for retention of the data objects is not restarted. Furthermore, it should be kept in mind that the retention values are only hints or suggestions and deletion of objects is based on a comparison of the dynamically updated delete threshold to the retention values of the data objects/containers.

As mentioned above, the delete threshold is a dynamically updated threshold that is tied to the current level of usage of the storage system. That is, as the level of usage of the storage system increases, the delete threshold, or high water mark, is updated so that more data objects/containers are likely to be reclaimed by the storage system, i.e. marked for deletion. As the level of usage of the storage system decreases, the delete threshold is updated so that less data objects/containers are likely to be reclaimed by the storage system. This updating of the delete threshold may be done on a continual basis, a periodic basis, or in response to the occurrence of a particular event or events. For example, in one embodiment of the present invention, the updating of the delete threshold may occur when data objects are added to containers, when data objects' retention values are modified, when container retention values are modified, or when data objects are moved from one container to another. In other exemplary embodiments, the delete threshold is performed periodically as retention values for the data objects and containers are updated based on application of decay functions to these retention values.

Moreover, in still other exemplary embodiments of the present invention, as described previously, rather than using a delete threshold, the present invention may make use of a sorted list of retention values for data objects and/or containers or data objects that prioritizes these data objects and/or containers based on their respective retention values. In this way, when new data objects and/or containers of data objects need to be stored in the storage system, other existing data objects and/or containers or data objects may be deleted from the storage system in accordance with the sorted list of retention values. In other words, those data objects/containers that have a lowest retention value may be deleted first until an appropriate amount of storage space is freed for the storing of the new data objects/containers. In this way, the system of the present invention permits the storage system to remain fully utilized while still permitting the storage of new data objects/containers in the storage system.

The above embodiments of the present invention assume that most retention values will exist between the values of 0 and 1, i.e. between a value indicating that the data object/container is not to be retained (e.g., 0) and a value indicating that the data object/container is never to be deleted (e.g., 1). In instances of the present invention in which the retention value indicates that the data object/container is not to be deleted, the mechanisms of the present invention are implemented. However, the mechanisms of the present invention may be modified so that data objects/containers that are identified as “permanent,” i.e. never to be automatically deleted by operation of the present invention but must be expressly deleted, are written to physical storage in a portion of the physical storage reserved for “permanent” data objects/containers. Alternatively, this reserved portion of physical storage for “permanent” data objects/containers may be present on a separate physical storage from that used for storing other data objects/containers. That is, “permanent” data objects/containers may be moved from one storage system or storage device to another storage system or storage device.

Moreover, as mentioned above, the retention values of data objects/containers may be modified by application of the decay functions and/or explicitly modified by applications. This gives rise to the possibility that the retention value of a data object/container may be modified more often than desirable, e.g., retention value “thrashing.” Such “thrashing” tends to increase the overhead of managing data objects/containers and thereby reduces the efficiency of the overall system.

Thresholds may be provided for identifying a maximum number of changes to a retention value within a period of time. When it is determined that a retention value of a data object/container has been modified more than a predetermined number of times within a predetermined period of time, the present invention may perform functions to minimize the affect of this “thrashing” on the operation of the present invention. These functions may include, for example, moving the data object/container to a different storage system or physical storage medium such that the data object/container is treated as a “permanent” data object/container. In this way, the data object/container is no longer subject to the management mechanisms of the present invention and instead must be specifically deleted by an application as in the conventional storage systems. In this way, data objects/containers that experience retention value “thrashing” are isolated from the remaining data objects/containers that do not experience this “thrashing.”

Thus, the present invention provides a mechanism by which data objects are assigned a retention value, and optionally a decay function, that provides an indication of the life of the data object in the storage system. The retention value and decay function may be used to group the data object with other data objects having a similar retention value, and optionally decay function, in containers prior to writing the data objects to physical storage. The retention value may be modified by an application directly or by applying the decay function to the retention value of the data object. Data objects may be moved from one container to another based on a change in their retention value. Containers may have their retention values updated based on the changes to retention values of data objects in the container. Data objects/containers may be deleted when they have a predetermined relationship to a dynamically updated delete threshold that is tied to the current level of usage of the storage system. Alternatively, data objects/containers may be deleted in accordance with a sorted list of retention values. In this way, the present invention provides an improved data storage system in which data objects are written and deleted in bulk and data objects/containers are deleted without requiring explicit deletion commands from applications.

FIGS. 9-12are flowcharts outlining various processes implemented by aspects of the present invention. It will be understood that each block of the flowchart illustrations, and combinations of blocks in the flowchart illustrations, can be implemented by computer program instructions. These computer program instructions may be provided to a processor or other programmable data processing apparatus to produce a machine, such that the instructions which execute on the processor or other programmable data processing apparatus create means for implementing the functions specified in the flowchart block or blocks. These computer program instructions may also be stored in a computer-readable memory or storage medium that can direct a processor or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory or storage medium produce an article of manufacture including instruction means which implement the functions specified in the flowchart block or blocks.

FIG. 9is a flowchart outlining an exemplary process for storing a data object in a container in a storage system in accordance with one exemplary embodiment of the present invention. As shown inFIG. 9, the operation starts by receiving a data object from an application (step910). As described previously above, the application, at data object creation time, associates the data object with a retention value and a decay function that are indicative of the expected lifetime of the data object within the data storage system. Upon receipt of the data object, the retention value of the data object is identified (step920) and a determination is made as to whether an appropriate container having a similar retention value is available for the data object (step930). If a container is not available in memory for the data object, based on the retention value of the data object, a new container is generated in memory for the specified data object retention value (step950). This may involve generating a metadata file in memory for storing attributes of the container including the container's retention value, identifiers of data objects stored in the container, retention values of the data objects in the container, decay functions of the data objects in the container, and the like.

Alternatively, if an appropriate container is available in memory, a determination is made as to whether the container has sufficient storage space for the data object (step940). If not, again a new container may be generated in memory for the specified data object retention value (step950). If an appropriate container is available and has sufficient space for the data object (steps930and940), or if a new container is created for storing the data object (step950), the data object is stored in the identified container in memory (step960). Container metadata is updated with the metadata for the data object (step970).

A determination is then made as to whether the container is full, a predetermined amount of time has expired since creation of the container, or the container is explicitly flushed (step980). That is, a determination is made as to whether the addition of the data object to the container results in a full container that should be written to physical storage or if some other event has occurred requiring writing of the container to physical storage. If the container is not full, the operation terminates. If the container is full, the container, i.e. the data objects within the container, are written to one or more segments of physical storage in a single high-bandwidth operation (step990). The metadata for the container is maintained in memory and may be updated with pointers to the physical storage locations of the data objects. In addition, the container data structure may be deleted from memory so that the memory is freed for reuse or may be cached for some time to allow the system to avoid disk accesses. The operation then terminates.

FIG. 10is a flowchart outlining an exemplary process for handling a modification of a retention value of a data object in accordance with one exemplary embodiment of the present invention. As shown inFIG. 10, a modification to a data object retention value is received (step1010). This may be an explicit modification by an application or may be the result of an application of a decay function associated with the data object to the retention value of the data object, for example. Thereafter, container policies for handling modifications to attributes of data objects in containers are applied to the modified data object retention value (step1020). Based on the application of these container policies, a determination is made as to whether the data object is to be moved to another container (step1030).

If the data object is to be moved to another container, the data object is copied to a new physical storage location and the data object at the new physical location is associated with the other container having a retention value that is similar to the modified retention value of the data object (step1050). In addition, the original copy of the data object may be marked for deletion. Metadata associated with the object may be updated to allow future accesses to the object to use the new copy.

If, by application of the container policies, it is determined that the data object is not to be moved to another container, a determination is made as to whether to modify the retention value of the container (step1040). If the retention value of the container is to be modified, the retention value associated with the container is updated based on the retention values for the data objects in the container (step1060). Thereafter, after the data object has been moved to another container, or if the change in the retention value of the data object is to be ignored, the metadata for the container(s) is updated in memory based on the particular change in retention value of the data object and any resulting changes to containers as a consequence of the change to the retention value of the data object (step1070). The operation then terminates.

FIG. 11is a flowchart outlining an exemplary process for deleting data objects/containers from a storage system in accordance with one exemplary embodiment of the present invention. As shown inFIG. 11, the operation starts by detecting a delete threshold update event (step1110). This event may be a periodic event (e.g., every 5 minutes), may be a continuous event, or may be a specific event (e.g., creation of a new data object) in a set of one or more specific events that trigger updating of the delete threshold.

A level of storage system utilization is then determined (step1120). For example, the storage system may determine a ratio of used to available storage space as an indication of storage system utilization. Based on this level of storage system utilization, the delete threshold may be either increased or decreased (step1130). In a preferred embodiment, as described previously, as storage system utilization increases, the delete threshold is increased between the values of 0 and 1. As a result, with increased delete threshold, there will be more containers and data objects that have retention values that are less than the delete threshold.

The retention value information for a next data object/container in the storage system is obtained (step1140) and a determination is made as to whether the retention value of the data object/container is less than or equal to the delete threshold (step1150). If so, the data object/container is marked for deletion (step1160). If the retention value of the data object/container is greater than the delete threshold, then the data object/container is not marked for deletion. A determination is then made as to whether there are additional data objects/containers to evaluate (step1170). If so, the operation returns to step1140where the next data object/container retention value information is obtained and the process is repeated. Otherwise, if there are no further data objects/containers to process, the operation terminates.

Thus, the present invention provides a mechanism by which data objects are assigned a retention value and decay function that provides an indication of the life of the data object in the storage system and which is used along with a dynamically updated deletion threshold to automatically control the storage system utilization. With the present invention, the retention value and delete threshold provide a mechanism for identifying data objects/containers that should be deleted from the storage system because they have outlived their useful life. Containers provide a mechanism to delete objects in large contiguous units, permitting later large contiguous writes that improve system efficiency. The decay function provides a mechanism for gradually removing data objects from a storage system by reducing the data object's retention value over time. In this way, the present invention provides an improved data storage system in which data objects are written and deleted in bulk and data objects/containers are deleted without requiring explicit deletion commands from applications.

As mentioned above, in a second aspect of the present invention, data objects and/or containers of data objects may be prioritized by their respective retention values. This prioritization may be used to determine which data objects/containers to delete when storage space needs to be freed for storing new data objects/containers of data objects. This deletion may be performed based on a delete threshold, a sorted list of retention values for data objects/containers, or the like. Furthermore, this prioritization may be used in conjunction with or separate from the other aspects of the present invention described above.

FIG. 12is a flowchart outlining an exemplary operation of the present invention when prioritizing data objects/containers of data objects in order to maintain a fully utilized storage system. Although the steps shown inFIG. 12are illustrated in a serial manner for clarity, many of the operations shown inFIG. 12may be performed in parallel without departing from the spirit and scope of the present invention. For example, typically the deleting of existing data objects/containers will be performed in parallel with the writing of new data objects/containers to the storage system.

As shown inFIG. 12, the operation starts when a request to store a new data object/container to the storage system is received (step1210). A determination is made as to whether there is available storage space to store the new data object/container (step1220). If there is available storage space, the data object/container is stored to the storage system and appropriate data structures for managing the new data object/container in the storage system are updated (step1260).

If there is not sufficient storage space for storing the data object/container, the retention values for the existing data objects/containers in the storage system are retrieved (step1230). A determination is made, based on these retention values, as to which existing data objects/containers may be deleted in order to make available storage space for the new data objects/containers (step1240). This determination may be made based on a delete threshold, a sorted list of retention values, or the like.

The identified data objects/containers that may be deleted are then deleted in order of their retention values, e.g., lowest relative retention value being deleted first, until a sufficient amount of storage space for the new data object/container is made available (step1250). The new data object/container is then stored in the storage system and data structures, e.g., the sorted list of retention values, for managing the new data object/container in the storage system are updated (step1260). The operation then ends but may be repeated for subsequent storage requests in order to maintain a fully utilized storage system that permits storage of new data objects/containers of data objects.