Storage of a data chunk with a colliding fingerprint

• US 10,241,708 B2
• Filed: 09/25/2014
• Issued: 03/26/2019
• Est. Priority Date: 09/25/2014
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Wang, Jin, Nazari, Siamak, Tamma, Roopesh Kumar, Murthy, Srinivasa D
• Primary Examiner(s): Lane, John A
• Application Number:
  US15/514,075
• Publication Number:
  US 20170300266A1
• Time in Patent Office: 1,643 Days
• Field of Search: None
• CPC Class Codes: G06F 11/08 Error detection or correction by redundancy in data representation, e.g. by using checking codes
• CPC Class Codes: G06F 11/14 Error detection or correction of the data by redundancy in operation G06F11/16 takes precedence
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• 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/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0673 Single storage device

Abstract

Example implementations relate to data chunk storage. For example, an implementation includes an apparatus that includes a processor. The processor is to receive a first data chunk from a source device and to generate a first fingerprint of the first data chunk. In response to a determination that the first fingerprint matches a second fingerprint of a second data chunk, the processor is to select a storage pool from a plurality of storage pools at a storage device to store the first data chunk based on the first data chunk and based on the second data chunk. The plurality of storage pools includes a first storage pool associated with first particular data chunks with non-colliding fingerprints and a second storage pool associated with second particular data chunks with colliding fingerprints.

Claims

1. An apparatus comprising:

a controller; and

a computer-readable storage medium comprising instructions that, when executed by the controller, cause the controller to;

receive a first data chunk from a source device;

generate a first fingerprint of the first data chunk;

in response to a determination that the first fingerprint does not match any of a plurality of fingerprints, including a second fingerprint of a second data chunk, store the first data chunk in a first storage pool associated with first particular data chunks having non-colliding fingerprints; and

in response to determinations that the first fingerprint matches the second fingerprint of the second data chunk and the first data chunk does not match the second data chunk, store the first data chunk in a second storage pool associated with second particular data chunks with colliding fingerprints.

2. The apparatus of claim 1, wherein the instructions, when executed by the controller, further cause the controller to:

when the first data chunk matches the second data chunk and the second data chunk is stored in the first storage pool, store a pointer to the second data chunk in the first storage pool.

3. The apparatus of claim 2, wherein the first storage pool is different from the second storage pool.

4. The apparatus of claim 1, wherein the instructions, when executed by the controller, further cause the controller to:

determine a location in the second storage pool to store the first data chunk based on a three level page table translation of an offset of the first data chunk.

5. The apparatus of claim 1, wherein the instructions, when executed by the controller, further cause the controller to:

in response to the determination that the first fingerprint does not match any of the plurality of fingerprints, store the first data chunk to a location of the first storage pool based on a three level page table translation of the first fingerprint.

6. A method comprising:

receiving, at a storage device, a first data chunk from a source device;

generating a first fingerprint of the first data chunk;

comparing the first fingerprint to a plurality of fingerprints, including a second fingerprint of a second data chunk;

when the first fingerprint does not match the second fingerprint, storing the first data chunk in a first storage pool of a plurality of storage pool associated with at least one storage device, the first storage pool associated with data chunks having non-colliding fingerprints;

when the first fingerprint matches the second fingerprint and the first data chunk does not match the second data chunk, storing the first data chunk in a second storage pool associated with data chunks having colliding fingerprints.

7. The method of claim 6, further comprising:

in response to determinations that the first fingerprint matches the second fingerprint and the first data chunk matches the second data chunk, storing a pointer to the second data chunk to the first storage pool for the first data chunk.

8. The method of claim 6, further comprising, when storing the first data chunk in the second storage pool, determining a location in the second storage pool to store the first data chunk based on a three level page table translation of an offset of the first data chunk.

9. The method of claim 6, further comprising, when the first fingerprint does not match any of the plurality of fingerprints, storing the first data chunk in a location of the first storage pool based on a three level page table translation of the first fingerprint.

10. The method of claim 6, wherein the first storage pool is different from the second storage pool.

11. A computer-readable storage medium comprising instructions that when executed cause a controller of a storage device to:

receive a first data chunk from a source device;

generate a first fingerprint of the first data chunk;

compare the first fingerprint to a plurality of fingerprints, including a second fingerprint of a second data chunk;

when the first fingerprint does not match any of the plurality of fingerprints, store the first data chunk in a first storage pool associated with non-colliding fingerprints;

when the first fingerprint matches the second fingerprint, compare the first data chunk to the second data chunk; and

when the first fingerprint matches the second fingerprint and the first data chunk does not match the second data chunk, store the first data chunk in a second storage pool associated with colliding fingerprints.

12. The computer-readable storage medium of claim 11, wherein the first data chunk is compared to the second data chunk via a byte by byte comparison.

13. The computer-readable storage medium of claim 11, further comprising instructions that when executed cause the controller of the storage device to:

when the first data chunk is to be stored in the first storage pool, store the first data chunk in a location of the first storage pool based on a three level page table translation of the first fingerprint.

14. The computer-readable storage medium of claim 11, further comprising instructions that when executed cause the controller of the storage device to:

when the first data chunk is to be stored in the second storage pool, store the first data chunk in a location of the second storage pool based on a three level page table translation of an offset of the first data chunk.

15. The computer-readable storage medium of claim 11, wherein the first storage pool is different from the second storage pool.

16. The computer-readable storage medium of claim 11 further comprising instructions that when executed cause the controller of the storage device to:

when the first fingerprint matches the second fingerprint and the first data chunk matches the second data chunk, for the first data chunk, store a pointer to the second chunk in the first storage pool associated with non-colliding fingerprints.