US 8,930,307 B2Granted

Method for removing duplicate data from a storage array

AssigneePure Storage, Inc.

InventorsJohn Colgrove, John Hayes, Ethan Miller, Joseph S. Hasbani, Cary Sandvig

Life of this patent

Estimating the term…

Loading patent…

Abstract

A system and method for efficiently removing duplicate data blocks at a fine-granularity from a storage array. A data storage subsystem supports multiple deduplication tables. Table entries in one deduplication table have the highest associated probability of being deduplicated. Table entries may move from one deduplication table to another as the probabilities change. Additionally, a table entry may be evicted from all deduplication tables if a corresponding estimated probability falls below a given threshold. The probabilities are based on attributes associated with a data component and attributes associated with a virtual address corresponding to a received storage access request. A strategy for searches of the multiple deduplication tables may also be determined by the attributes associated with a given storage access request.

Claims19

Dependent claims

A computer system comprising:

a non-transitory data storage medium;
a first fingerprint table comprising a first plurality of entries and a second fingerprint table comprising a second plurality of entries, wherein each entry of the first and the second plurality of entries is configured to store a fingerprint corresponding to a data component already stored in the system, wherein the first fingerprint table has fewer entries than the second fingerprint table and wherein the second fingerprint table comprises a fingerprint for at least one deduplicated data components not included in the first fingerprint table;
and
a data storage controller comprising hardware;
wherein in response to receiving a write request, the data storage controller is configured to:
search the first fingerprint table during inline deduplication prior to the second fingerprint table based on a first fingerprint corresponding to the write request;
in response to detecting a hit on a matching entry in the first fingerprint table during said search:
write a reference to the data corresponding to the matching entry in the first table;
and
in response to detecting a miss in the first fingerprint table during said search:
postpone further deduplication to offline deduplication;
and
write data corresponding to the write request in the data storage medium.

10 more elements

A method comprising:

maintaining a first fingerprint table comprising a first plurality of entries and a second fingerprint table comprising a second plurality of entries in a computer system, wherein each entry of the first and the second plurality of entries is configured to store a fingerprint corresponding to a data component already stored in the system, wherein the first fingerprint table has fewer entries that the second fingerprint table and wherein the second fingerprint table comprises a fingerprint for at least one deduplicated data components not included in the first fingerprint table;
in response to receiving a storage access request:
searching the first fingerprint table during inline deduplication prior to the second fingerprint table based on a first fingerprint corresponding to the write request;
in response to detecting a hit on a matching entry in the first fingerprint table during said search:
write a reference to the data corresponding to the matching entry in the first table;
and
in response to detecting a miss in the first fingerprint table during said search:
postpone further deduplication to offline deduplication;
and
write data corresponding to the write request in the data storage medium.

7 more elements

A non-transitory computer readable storage medium comprising program instructions, wherein said program instructions are executable to:

maintain a first fingerprint table comprising a first plurality of entries and a second fingerprint table comprising a second plurality of entries in a computer system, wherein each entry of the first and the second plurality of entries is configured to store a fingerprint corresponding to a data component already stored in the system, wherein the first fingerprint table has fewer entries than the second fingerprint table and wherein the second fingerprint table comprises a fingerprint for at least one deduplicated data components not included in the first fingerprint table;
in response to receiving a storage access request:
search the first fingerprint table prior to the second fingerprint table based on a first fingerprint corresponding to the write request;
in response to detecting a hit on a matching entry in the first fingerprint table during said search:
write a reference to the data corresponding to the matching entry in the first table;
and
in response to detecting a miss in the first fingerprint table during said search:
postpone further deduplication to offline deduplication;
and
write data corresponding to the write request in the data storage medium.

7 more elements

Dependencies are inferred from the claim text.

Facts

Application: 13/250,570Filed 30 Sep 2011
Published: US 2013/0086006 A14 Apr 2013
Granted: 6 Jan 2015
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

G06F 3/0608
Specifically adapted to achieve a particular effect: saving storage space on storage systems
G06F 3/0641
Management of blocks: de-duplication techniques
G06F 3/0688
Plurality of storage devices: non-volatile semiconductor memory arrays
G06F 16/137
File access structures, e.g. distributed indices: hash-based