Methods and Systems for Single Instance Storage of Asset Parts

• US 20100228784A1
• Filed: 02/23/2009
• Published: 09/09/2010
• Est. Priority Date: 02/23/2009
• Status: Active Grant

• Current Assignee: Autonomy Incorporated (HP Inc.)
• Original Assignee: Iron Mountain Incorporated
• Inventors: Newson, Robert S., Beaman, Peter D., Tran, Tuyen M.
• Granted Patent: US 8,145,598 B2
• Time in Patent Office: Days
• US Class Current: 707/802
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 16/1815 Journaling file systems

Abstract

Methods and systems are disclosed that relate to single instance storage of asset parts utilizing a back reference count associated with each asset part. Entries in a journal associated with the asset parts reflect the intention to increment or decrement an asset part'"'"'s back reference count. The journal may be used to maintain an accurate and reliable reference count for asset parts replicated across multiple disk drives in a distributed storage system, where the replication is structured to reduce the risk of data loss in the event of a disk drive failure. The journal entries may comprise generation numbers used to maintain a back reference count associated with an asset part and to verify a back reference count associated with an asset part.

Claims

1. A method for maintaining single instance storage of a plurality of asset parts in a data storage system, the method comprising:

using at least one processor for;

maintaining a journal associated with the plurality of the asset parts, the journal comprising entries having generation numbers that are larger than generation numbers of previous entries;

creating a first entry to the journal corresponding to a request to add or remove a reference from an asset to an asset part, the first entry further comprising a first generation number assigned thereto; and

performing a confirmation cycle, wherein the confirmation cycle comprises

comparing the first generation number to a second generation number that is associated with the asset part, and

when the first generation number is larger than the second generation number, causing a reference count associated with the asset part to be changed.

2. The method of claim 1, wherein the confirmation cycle is performed periodically.

3. The method of claim 1, wherein the second generation number is stored in metadata associated with the asset part.

4. The method of claim 1, further comprising performing atomically the steps of replacing the second generation number with the first generation number and causing the reference count associated with the asset part to be changed.

5. The method of claim 4, wherein the first generation number comprises a numerical value selected from the group consisting of an address of the first entry, a count of entries in the journal from a beginning entry to the first entry, a byte offset of the first entry from a beginning memory location of the journal, and a first time stamp reflecting a creation time of the first entry.

6. The method of claim 1, wherein the first entry comprises an identifier of the asset, and wherein performing the confirmation cycle further comprises:

prior to causing the reference count associated with the asset part to be changed, checking a status associated with the asset;

when the status indicates that the asset is eligible for change, causing the reference count associated with the asset part to be changed; and

when the status indicates that the asset is ineligible for change, not causing the reference count associated with the asset part to be changed.

7. The method of claim 1, wherein the data storage system comprises a plurality of storage nodes,

wherein each of the plurality of asset parts comprises asset part content and asset part metadata, the asset part metadata being associated with a stripe;

wherein the journal is associated with the stripe;

wherein the asset part content and the stripe are replicated across at least two of the plurality of nodes, forming at least one replicated asset part content and at least one replicated stripe having a replicated journal; and

wherein creating the first entry further comprises creating the first entry in each replicated journal.

8. A data storage system for maintaining single instance storage of a plurality of asset parts, the system comprising:

a plurality of disk drives storing assets and a plurality of asset parts; and

at least one processor configured to

maintain a journal associated with the plurality of the asset parts, the journal comprising entries having generation numbers that are larger than generation numbers of previous entries;

create a first entry to the journal corresponding to a request to add or remove a reference from an asset to an asset part, the first entry further comprising a first generation number assigned thereto; and

perform a confirmation cycle, wherein the confirmation cycle comprises

comparing the first generation number to a second generation number that is associated with the asset part, and,

when the first generation number is larger than the second generation number, causing a reference count associated with the asset part to be changed.

9. The data storage system of claim 8, wherein the at least one processor is configured to perform the confirmation cycle periodically.

10. The data storage system of claim 8, wherein the second generation number is stored in metadata associated with the asset part.

11. The data storage system of claim 8,

wherein the at least one processor is further configured to atomically perform the steps of replacing the second generation number with the first generation number and causing the reference count associated with the asset part to be changed.

12. The data storage system of claim 11, wherein the first generation number comprises a numerical value selected from the group consisting of an address of the first entry, a count of entries in the journal from a beginning entry to the first entry, a byte offset of the first entry from a beginning memory location of the journal, and a first time stamp reflecting a creation time of the first entry.

13. The data storage system of claim 8, wherein the first entry comprises an identifier of the asset, and wherein performing the confirmation cycle further comprises:

prior to causing the reference count associated with the asset part to be changed, checking a status associated with the asset;

when the status indicates that the asset is eligible for change, causing the reference count associated with the asset part to be changed; and

when the status indicates that the asset is ineligible for change, not causing the reference count associated with the asset part to be changed.

14. A computer readable medium comprising executable instructions maintaining single instance storage of a plurality of asset parts in a data storage system, the instructions, when executed by a computer system, causing the computer system to:

maintain a journal associated with the plurality of asset parts, the journal comprising entries having generation numbers that are larger than generation numbers of previous entries;

create a first entry to the journal corresponding to a request to add or remove a reference from an asset to an asset part, the first entry further comprising a first generation number assigned thereto; and

perform a confirmation cycle, wherein the confirmation cycle comprises

comparing the first generation number to a second generation number that is associated with the asset part, and

when the first generation number is larger than the second generation number, causing a reference count associated with the asset part to be changed.

15. The computer readable medium of claim 14, wherein the instructions cause the computer to perform the confirmation cycle periodically.

16. The computer readable medium of claim 14, wherein the second generation number is stored in metadata associated with the asset part.

17. The computer readable medium of claim 14,

wherein the instructions cause the computer to atomically replace the second generation number with the first generation number and cause the reference count associated with the asset part to be changed.

18. The computer readable medium of claim 17, wherein the first generation number comprises a numerical value selected from the group consisting of an address of the first entry, a count of entries in the journal from a beginning entry to the first entry, a byte offset of the first entry from a beginning memory location of the journal, and a first time stamp reflecting a creation time of the first entry.

19. The computer readable medium of claim 14, wherein the first entry comprises an identifier of the asset, and wherein the instructions further cause the computer to:

prior to causing the reference count associated with the asset part to be changed, check a status associated with the asset;

when the status indicates that the asset is eligible for change, cause the reference count associated with the asset part to be changed; and

when the status indicates that the asset is ineligible for change, not cause the reference count associated with the asset part to be changed.