Methods and systems for single instance storage of asset parts

• US 8,145,598 B2
• Filed: 02/23/2009
• Issued: 03/27/2012
• Est. Priority Date: 02/23/2009
• Status: Expired due to Fees

• Current Assignee: Autonomy Incorporated (HP Inc.)
• Original Assignee: Iron Mountain Incorporated
• Inventors: Tran, Tuyen M., Newson, Robert S., Beaman, Peter D.
• Primary Examiner(s): DANG, THANH HA T
• Application Number:
  US12/391,099
• Publication Number:
  US 20100228784A1
• Time in Patent Office: 1,128 Days
• Field of Search: 707/610, 707/615, 707/633, 707/634, 707/635, 707/640, 707/648, 707/812
• US Class Current: 707/610
• 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 comprising a plurality of storage nodes, 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;

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; and

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 asset part content and the stripe are replicated across at least two of the plurality of storage 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 the replicated journal.

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 atomically replacing the second generation number with the first generation number and causing the reference count associated with the asset part to be changed when the first generation number is larger than the second generation number.

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. A data storage system for maintaining single instance storage of a plurality of asset parts, the data storage system comprising:

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

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; and

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 asset part content and the stripe are replicated across at least two of the plurality of storage 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 the replicated journal.

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

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

10. The data storage system of claim 7, wherein the at least one processor is further configured 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 when the first generation number is larger than the second generation number.

11. The data storage system of claim 10, 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.

12. The data storage system of claim 7, 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.

13. A non-transitory computer readable medium comprising executable instructions maintaining single instance storage of a plurality of asset parts in a data storage system comprising a plurality of storage nodes, 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; and

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 asset part content and the stripe are replicated across at least two of the plurality of storage 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 the replicated journal.

14. The non-transitory computer readable medium of claim 13, wherein the instructions cause the computer to perform the confirmation cycle periodically.

15. The non-transitory computer readable medium of claim 13, wherein the second generation number is stored in metadata associated with the asset part.

16. The non-transitory computer readable medium of claim 13, 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.

17. The non-transitory computer readable medium of claim 16, 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.

18. The non-transitory computer readable medium of claim 13, 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.