Heuristic journal reservations

Patent metadata

Field	Value
Publication number	US-9483356-B2
Application number	US-201313787456-A
Country	US
Kind code	B2
Filing date	Mar 6, 2013
Priority date	Mar 6, 2013
Publication date	Nov 1, 2016
Grant date	Nov 1, 2016

Abstract

Example apparatus and methods reserve space in a journal using an observation based approach instead of a fixed sized approach or a worst case scenario approach. One example method receives a request to allocate space in a journal to support a file system transaction. The example method reserves an amount of space in the journal based on a pre-existing reservation size estimate. Unlike conventional systems, the estimate is not based on a worst-case scenario. The example method observes the actual amount of storage used in the journal by the file system transaction and then selectively automatically adjusts the pre-existing reservation size estimate. The estimate may slowly shrink if no overflows are encountered but may quickly grow if an overflow is detected.

First claim

What is claimed is:

1. A non-transitory computer-readable medium storing computer-executable instructions that when executed by a computer cause the computer to perform a method, the method comprising:
receiving a request to allocate space in a journal, the request being associated with a file system transaction;
accessing a pre-determined estimated reservation size for the file system transaction;
reserving an amount of storage in the journal for the file system transaction, where the amount of storage reserved is a function of the pre-determined estimated reservation size;
determining an actual amount of storage used in the journal by the file system transaction; and
selectively automatically adjusting the pre-determined estimated reservation size as a function of the actual amount of storage used, where adjusting the pre-determined estimated reservation size as a function of the actual amount of storage used includes reducing the pre-determined estimated reservation size at a first rate upon determining that the actual amount of storage used was less than the pre-determined estimated reservation size, or increasing the pre-determined estimated reservation size at a second rate upon determining that the actual amount of storage used was greater than the pre-determined estimated reservation size, where the second rate is at least twice the first rate.

2. The non-transitory computer-readable medium of claim 1 , the journal being a circular buffer.

3. The non-transitory computer-readable medium of claim 2 , the pre-determined estimated reservation size being stored in a table, where the table stores pre-determined estimated reservation sizes for different file system transaction types on a per transaction type basis.

4. The non-transitory computer-readable medium of claim 1 , where reserving the amount of storage includes reserving an additional amount of storage in the journal, where the additional amount of storage is configured to operate as an overflow buffer.

5. The non-transitory computer-readable medium of claim 4 , comprising:
upon determining that the transaction is going to cause an overflow, using the additional amount of storage to handle the overflow.

6. The non-transitory computer-readable medium of claim 1 , where reserving the amount of storage includes computing a derived estimate as a function of the pre-determined estimated reservation size and a weighting factor.

7. The non-transitory computer-readable medium of claim 1 , where reserving the amount of storage includes computing a derived estimate as a function of the pre-determined estimated reservation size and a number of files to which the file system transaction is to be applied.

8. The non-transitory computer-readable medium of claim 1 , where reducing the pre-determined estimated reservation size is a function of a rolling average of observed storage usage, a decaying rolling average of observed storage usage, a weighted rolling average of observed storage usage, a pre-determined reduction amount, a pre-determined reduction factor, a dynamic reduction amount, or a dynamic reduction factor, where a change in observed storage usage that is more than one standard deviation from the rolling average of observed storage usage reduces the pre-determined estimate reservation size less than a change in observed storage usage that is less than one standard deviation from the rolling average of observed storage usage.

9. The non-transitory computer-readable medium claim 1 , where increasing the pre-determined estimated reservation size is a function of a rolling average of observed storage usage, and a weighted rolling average of observed storage usage, a pre-determined increase amount, a pre-determined increase factor, a dynamic increase amount, or a dynamic increase factor.

10. The non-transitory computer-readable medium of claim 1 , where increasing the pre-determined estimated reservation size is a function of a number of overflows or a number of near-overflows experienced during a threshold number of observed preceding transactions.

11. The non-transitory computer-readable medium of claim 1 , where reserving the amount of storage in the journal includes computing a derived estimate by multiplying the pre-determined estimated reservation size by a multiple, and
where adjusting the pre-determined estimated reservation size as a function of the actual amount of storage used includes adjusting the multiple.

12. An apparatus, comprising:
a processor;
a memory that stores a journal impact estimate for a file system transaction;
a set of logics; and
an interface that connects the processor, the memory, and the set of logics;
the set of logics including:
a first logic that determines a predicted journal usage for the file system transaction as a function of the journal impact estimate;
a second logic that controls allocating storage in a journal as a function of the predicted journal usage, and
a third logic that selectively automatically adjusts the journal impact estimate as a function of a variance between an observed journal usage and the predicted journal usage, where the third logic adjusts the journal impact estimate down at a rate determined as a function of observations of N previous file system transactions, N being an integer greater than one, where the third logic adjusts the journal impact estimate down upon determining that the observed journal usage was less than the predicted journal usage by a first threshold amount, where the first threshold amount is less than one standard deviation from the predicted journal usage and where the third logic adjusts the journal impact estimate up at a pre-determined rate upon determining that the observed journal usage was greater than the predicted journal usage by a second threshold amount, where the pre-determined rate is at least double the rate produced as a function of the observations of the N previous file system transactions, and where the second threshold amount is less than one standard deviation from the predicted journal usage.

13. The apparatus of claim 12 , where the second logic controls allocating storage as a function of the predicted journal usage and of the number of files associated with the file system transaction.

14. The apparatus of claim 12 , the set of logics including a fourth logic that allocates an overflow buffer in the journal for the transaction and, upon determining that the file system transaction will produce journal usage greater than the predicted journal usage, uses the overflow buffer to accommodate the file system transaction.

15. A system, comprising:
means for reserving storage in a journal, where the storage is configured to accommodate a plurality of atomic operations associated with completing a file system transaction of a first type, where the amount of storage reserved is a function of an existing reservation size associated with the first type;
means for reserving additional storage in the journal, the additional storage being configured to accommodate an overflow of the journal, and
means for updating the existing reservation size as a function of observing an actual amount of storage used in the journal by transactions of the type of the file system transaction,
where the means for updating the existing reservation size is configured to reduce the existing reservation size upon determining that the actual amount of storage used in the journal by the file system transaction was less than the amount of storage reserved, where the existing reservation size is reduced at a first rate, where the first rate is a function of a decaying rolling average

Assignees

• Lord Stephen P
• Quantum Corp

Inventors

• Lord Stephen P

Classifications

• G06F12/023 Primary

  Free address space management · CPC title

• G06F2212/463

  File · CPC title

• G06F16/1815

  Journaling file systems · CPC title

• G06F11/1471

  involving logging of persistent data for recovery · CPC title

• G06F11/1448 Primary

  Management of the data involved in backup or backup restore · CPC title