High-Performance Distributed Data Storage System with Implicit Content Routing and Data Deduplication

• US 20150039645A1
• Filed: 08/02/2013
• Published: 02/05/2015
• Est. Priority Date: 08/02/2013
• Status: Abandoned Application

• Current Assignee: eBay Inc.
• Original Assignee: Formation Data Systems, Inc.
• Inventors: Lewis, Mark S.
• Application Number:
  US13/957,849
• Publication Number:
  US 20150039645A1
• Time in Patent Office: Days
• US Class Current: 707/769
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/9014 hash tables

Abstract

A write request that includes a data object is processed. A hash function is executed on the data object, thereby generating a hash value that includes a first portion and a second portion. A data location table is queried with the first portion, thereby obtaining a storage node identifier. The data object is sent to a storage node associated with the storage node identifier. A write request that includes a data object and a pending data object identification (DOID) is processed, wherein the pending DOID comprises a hash value of the data object. The pending DOID is finalized, thereby generating a finalized data object identification (DOID). The data object is stored at a storage location. A storage manager catalog is updated by adding an entry mapping the finalized DOID to the storage location. The finalized DOID is output.

Claims

1. A method for processing a write request that includes a data object, the method comprising:

executing a hash function on the data object, thereby generating a hash value that includes a first portion and a second portion;

querying a data location table with the first portion, thereby obtaining a storage node identifier; and

sending the data object to a storage node associated with the storage node identifier.

2. The method of claim 1, wherein querying the data location table with the first portion results in obtaining both the storage node identifier and a second storage node identifier, the method further comprising:

sending the data object to a storage node associated with the second storage node identifier.

3. The method of claim 1, wherein a length of the first portion is four bytes.

4. The method of claim 1, wherein the storage node identifier comprises an Internet Protocol (IP) address.

5. The method of claim 1, wherein the write request further includes an application data identifier, the method further comprising:

generating a pending data object identification (DOID) based on the data object;

sending the pending DOID to the storage node;

receiving, from the storage node, a finalized data object identification (DOID); and

updating a virtual volume catalog by adding an entry mapping the application data identifier to the finalized DOID.

6. The method of claim 5, wherein generating the pending DOID comprises concatenating the hash value and a conflict value.

7. The method of claim 5, wherein the application data identifier comprises a file name, an object name, or a range of blocks.

8. A method for processing a write request that includes a data object and a pending data object identification (DOID), wherein the pending DOID comprises a hash value of the data object, the method comprising:

finalizing the pending DOID, thereby generating a finalized data object identification (DOID);

storing the data object at a storage location;

updating a storage manager catalog by adding an entry mapping the finalized DOID to the storage location; and

outputting the finalized DOID.

9. The method of claim 8, wherein the pending DOID further comprises a conflict value, and wherein finalizing the pending DOID comprises:

determining whether a hash conflict exists;

responsive to determining that the hash conflict exists;

modifying the pending DOID by incrementing the pending DOID'"'"'s conflict value to a lowest non-conflicting value; and

setting the finalized DOID equal to the modified pending DOID; and

responsive to determining that the hash conflict does not exist;

setting the finalized DOID equal to the pending DOID.

10. The method of claim 9, wherein determining whether the hash conflict exists comprises determining whether the storage manager catalog includes an entry mapping a second data object'"'"'s data object identification (DOID), wherein the second data object'"'"'s DOID comprises a hash value identical to the pending DOID'"'"'s hash value, and wherein the second data object differs from the data object included in the write request.

11. The method of claim 10, wherein determining whether the storage manager catalog includes the entry mapping the second data object'"'"'s DOID comprises:

determining, based on a first hash function, whether the second data object matches the data object included in the write request; and

determining, based on a second hash function, whether the second data object matches the data object included in the write request.

12. A non-transitory computer-readable storage medium storing computer program modules for processing a read request that includes an application data identifier, the computer program modules executable to perform steps comprising:

querying a virtual volume catalog with the application data identifier, thereby obtaining a data object identification (DOID), wherein the DOID comprises a hash value of a data object, and wherein the hash value includes a first portion and a second portion;

querying a data location table with the first portion, thereby obtaining a storage node identifier; and

sending the DOID to a storage node associated with the storage node identifier.

13. The computer-readable storage medium of claim 12, wherein the steps further comprise receiving the data object.

14. The computer-readable storage medium of claim 12, wherein querying the data location table with the first portion results in obtaining both the storage node identifier and a second storage node identifier, and wherein the steps further comprise:

waiting for a response; and

responsive to no response being received within a specified time period, sending the DOID to a storage node associated with the second storage node identifier.

15. A system for processing a read request that includes a data object identification (DOID), wherein the DOID comprises a hash value of a data object, and wherein the hash value includes a first portion and a second portion, the system comprising:

a non-transitory computer-readable storage medium storing computer program modules executable to perform steps comprising;

querying a storage manager catalog with the first portion, thereby obtaining a storage location; and

retrieving the data object from the storage location; and

a computer processor for executing the computer program modules.

16. The system of claim 15, wherein the steps further comprise outputting the data object.