Method for processing duplicated data

• US 8,983,968 B2
• Filed: 09/22/2011
• Issued: 03/17/2015
• Est. Priority Date: 06/01/2011
• Status: Active Grant

• Current Assignee: Inventec Corporation
• Original Assignee: Inventec Corporation
• Inventors: Zhu, Ming-Sheng, Chen, Chih-Feng
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): MINA, FATIMA P
• Application Number:
  US13/240,154
• Publication Number:
  US 20120310974A1
• Time in Patent Office: 1,272 Days
• Field of Search: 707/791, 707/752, 707/715, 707/718, 707/728, 707/779
• US Class Current: 707/747
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/152 using file content signatures, e.g. hash values
• CPC Class Codes: G06F 16/174 Redundancy elimination performed by the file system management of the data involved in backup or backup restore using de-duplication of the data G06F11/14
• CPC Class Codes: G06F 2201/83 the solution involving signatures

Abstract

A processing method for duplicated data includes the following steps. A query request is received from a client, in which the query request includes a requested fingerprint value. A hash tank corresponding to the requested fingerprint value in a memory is searched for the requested fingerprint value. When the requested fingerprint value does not exist in the hash tank corresponding to the requested fingerprint value, the following steps are executed. An addition table in the memory is searched for the requested fingerprint value; and when the requested fingerprint value exists in the addition table, an invalid duplicate message is sent to the client.

Claims

1. A method for processing duplicated data, comprising:

receiving a query request from a client, wherein the query request comprises a requested fingerprint value;

searching a hash tank corresponding to the requested fingerprint value in a memory for the requested fingerprint value, comprising;

executing a hash procedure on the requested fingerprint value and obtaining a tank index value;

searching the memory for the hash tank corresponding to the requested fingerprint value according to the tank index value;

when the hash tank corresponding to the requested fingerprint value exists in the memory, searching the hash tank corresponding to the requested fingerprint value for the requested fingerprint value; and

when the hash tank corresponding to the requested fingerprint value does not exist in the memory, executing the following steps;

loading the hash tank corresponding to the requested fingerprint value into the memory from a disk;

searching a storage complete table in the memory with the loaded hash tank for the requested fingerprint value; and

updating a write status value of the hash tank, deleting the requested fingerprint value in the storage complete table, and then searching the hash tank corresponding to the requested fingerprint value for the requested fingerprint value, when the requested fingerprint value exists in the storage complete table; and

executing the following steps, when the requested fingerprint value does not exist in the hash tank corresponding to the requested fingerprint value;

searching an addition table in the memory for the requested fingerprint value; and

sending an invalid duplicate message to the client, when the requested fingerprint value exists in the addition table.

2. The method for processing the duplicated data according to claim 1, further comprising:

sending a valid duplicate message to the client, when the requested fingerprint value exists in the hash tank.

3. The method for processing the duplicated data according to claim 1, further comprising:

executing an addition procedure, when requested fingerprint value does not exist in the addition table.

4. The method for processing the duplicated data according to claim 3, wherein the addition procedure comprises:

adding the requested fingerprint value into the addition table; and

sending a new data message to the client.

5. The method for processing the duplicated data according to claim 4, wherein the addition procedure further comprises:

receiving a data tank represented by the requested fingerprint value from the client and storing the data tank;

searching the memory for the hash tank corresponding to the requested fingerprint value;

updating the write status value of the hash tank, and deleting the requested fingerprint value in the addition table, when the hash tank corresponding to the requested fingerprint value exists in the memory; and

writing the requested fingerprint value into a storage complete table, and deleting the requested fingerprint value in the addition table, when the hash tank corresponding to the requested fingerprint value does not exist in the memory.

6. A method for processing duplicated data, comprising:

receiving a query request from a client, wherein the query request comprises a requested fingerprint value;

processing the requested fingerprint value by employing a Bloom filter and obtaining a return value; and

executing the following steps, when the return value is hit;

searching a hash tank corresponding to the requested fingerprint value in a memory for the requested fingerprint value, comprising;

executing a hash procedure on the requested fingerprint value and obtaining a tank index value;

searching the memory for the hash tank corresponding to the requested fingerprint value according to the tank index value;

when the hash tank corresponding to the requested fingerprint value exists in the memory, searching the hash tank corresponding to the requested fingerprint value for the requested fingerprint value; and

when the hash tank corresponding to the requested fingerprint value does not exist in the memory, executing the following steps;

loading the hash tank corresponding to the requested fingerprint value into the memory from a disk;

searching a storage complete table in the memory with the loaded hash tank for the requested fingerprint value; and

updating a write status value of the hash tank, deleting the requested fingerprint value in the storage complete table, and then searching the hash tank corresponding to the requested fingerprint value for the requested fingerprint value, when the requested fingerprint value exists in the storage complete table; and

executing the following steps, when the requested fingerprint value does not exist in the hash tank corresponding to the requested fingerprint value;

searching an addition table in the memory for the requested fingerprint value; and

sending an invalid duplicate message to the client, when the requested fingerprint value exists in the addition table.

7. The method for processing the duplicated data according to claim 6, further comprising:

executing an addition procedure, when the return value is miss.