IP Library › Granted Patent US 8,949,199
Granted Patent B2
US 8,949,199 · App. 13/359,600 · Granted Feb 3, 2015

Systems and methods for de-duplication in storage systems

Inventors: Jacob Cherian (Austin, TX); Itay Dar (Rishon LeZion, IL)
Assignee: Dell Products L.P.
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 8,949,199
App. No.
13/359,600
Filed
Jan 27, 2012
Granted
Feb 3, 2015
Kind
B2
Art Unit
2162
USPC
707/692
Abstract

In accordance with embodiments of the present disclosure, a storage system may include a storage array comprising one or more storage resources, a processor communicatively coupled to the storage array, and a de-duplication module comprising instructions embodied on a computer-readable medium communicatively coupled to the processor. The de-duplication module may be configured to, when read and executed by the processor: generate a fingerprint for an item of data stored on the storage array; identify a partition for the fingerprint; associate the partition with a hardware instance selected from a plurality of hardware instances, wherein each particular hardware instance comprises one or more information handling resources; and query the selected hardware instance to determine if the fingerprint exists on the hardware instance.

Claims (31)

1. A storage system comprising:

a storage array comprising one or more storage resources;

a processor communicatively coupled to the storage array;

a de-duplication module comprising instructions embodied on a computer-readable medium communicatively coupled to the processor, the de-duplication module configured to, when read and executed by the processor:

generate a fingerprint for an item of data stored on the storage array;

identify a partition for the fingerprint by calculating a function to map the fingerprint to the partition;

associate the partition with a hardware instance selected from a plurality of hardware instances, wherein each particular hardware instance comprises one or more information handling resources; and

query the selected hardware instance to determine whether the fingerprint exists on the hardware instance.

2. The storage system according to claim 1 further comprising the plurality of hardware instances, each hardware instance configured to respond to the query with an indication of whether the fingerprint exists on the hardware instance.

3. The storage system according to claim 2 , at least one of the de-duplication module and the hardware instance further configured to add the fingerprint to the hardware instance if the fingerprint does not exist on the hardware instance.

4. The storage system according to claim 1 , the de-duplication module further configured to de-duplicate data associated with the fingerprint if the fingerprint exists on the hardware instance.

5. The storage system according to claim 1 , wherein one of the plurality of hardware instances comprises the processor.

6. The storage system according to claim 1 , the de-duplication module configured to generate fingerprints, identify partitions, and associate partitions with hardware instances in concert with one or more other de-duplication modules executing on one or more other processors.

7. The A storage system according to claim 1 , the de-duplication module configured to, in order to identify each partition, calculate a function y=F(x) to identify a partition y for each fingerprint x; wherein the number of partitions n comprise any suitable integer number, the value of y may comprise any integer number from 0 to n−1, and the function F(x) is operable to map all possible values of x to a corresponding value of y.

8. The A storage system according to claim 7 , the function F(x) operable to map fingerprints x into partitions y such that the number of fingerprints x associated with each partition y would approximately be equal.

9. The A storage system according to claim 1 , the de-duplication module configured to, in order to associate each partition with a hardware instance, calculate a function z=G(y) to assign each partition y to a hardware instance z; wherein the number m represents the number of hardware instances to which partitions may be assigned, the value of z may comprise any integer number from 0 to m−1, and the function G(y) is operable to map all possible values of y to a corresponding value of z.

10. The A storage system according to claim 9 , the function G(y) operable to map partitions y into hardware instances z such that the number of partitions y associated with each hardware instance z would approximately be equal.

11. The A storage system according to claim 1 , the de-duplication module configured to, in response to a change in the number of hardware instances, re-assign at least one partition to a different hardware instance selected from the plurality of hardware instances.

12. A method comprising:

generating a fingerprint for an item of data stored on the storage array;

identifying a partition for the fingerprint by calculating a function to map the fingerprint to the partition;

associating the partition with a hardware instance selected from a plurality of hardware instances, wherein each particular hardware instance comprises one or more information handling resources; and

querying the selected hardware instance to determine whether the fingerprint exists on the hardware instance.

13. The method according to claim 12 further comprising, responding, by each hardware instance, to the query with an indication of whether the fingerprint exists on the hardware instance.

14. The method according to claim 13 , further comprising adding the fingerprint to the hardware instance if the fingerprint does not exist on the hardware instance.

15. The method according to claim 12 , further comprising de-duplicating data associated with the fingerprint if the fingerprint exists on the hardware instance.

16. The A method according to claim 12 , further comprising, in order to identify each partition, calculating a function y=F(x) to identify a partition y for each fingerprint x; wherein the number of partitions n comprise any suitable integer number, the value of y may comprise any integer number from 0 to n−1, and the function F(x) is operable to map all possible values of x to a corresponding value of y.

17. The A method according to claim 16 , the function F(x) operable to map fingerprints x into partitions y such that the number of fingerprints x associated with each partition y would approximately be equal.

18. The A method according to claim 11 , in order to associate each partition with a hardware instance, calculating a function z=G(y) to assign each partition y to a hardware instance z; wherein the number m represents the number of hardware instances to which partitions may be assigned, the value of z may comprise any integer number from 0 to m−1, and the function G(y) is operable to map all possible values of y to a corresponding value of z.

19. The A method according to claim 18 , the function G(y) operable to map partitions y into hardware instances z such that the number of partitions y associated with each hardware instance z would approximately be equal.

20. The A method according to claim 11 , further comprising, in response to a change in the number of hardware instances, re-assigning at least one partition to a different hardware instance selected from the plurality of hardware instances.

Assignments (15)
RELEASE OF SECURITY INTEREST IN PATENTS PREVIOUSLY RECORDED AT REEL/FRAME (053546/0001) Recorded Jun 23, 2022
From: THE BANK OF NEW YORK MELLON TRUST COMPANY, N.A., AS NOTES COLLATERAL AGENT
To: DELL MARKETING L.P. (ON BEHALF OF ITSELF AND AS SUCCESSOR-IN-INTEREST TO CREDANT TECHNOLOGIES, INC.); DELL INTERNATIONAL L.L.C.; DELL PRODUCTS L.P.; DELL USA L.P.; EMC CORPORATION; DELL MARKETING CORPORATION (SUCCESSOR-IN-INTEREST TO FORCE10 NETWORKS, INC. AND WYSE TECHNOLOGY L.L.C.); EMC IP HOLDING COMPANY LLC
Reel/Frame 071642/0001 →
RELEASE OF SECURITY INTEREST IN PATENTS PREVIOUSLY RECORDED AT REEL/FRAME (045455/0001) Recorded May 20, 2022
From: THE BANK OF NEW YORK MELLON TRUST COMPANY, N.A., AS NOTES COLLATERAL AGENT
To: DELL MARKETING CORPORATION (SUCCESSOR-IN-INTEREST TO ASAP SOFTWARE EXPRESS, INC.); DELL MARKETING L.P. (ON BEHALF OF ITSELF AND AS SUCCESSOR-IN-INTEREST TO CREDANT TECHNOLOGIES, INC.); DELL USA L.P.; DELL INTERNATIONAL L.L.C.; DELL PRODUCTS L.P.; DELL MARKETING CORPORATION (SUCCESSOR-IN-INTEREST TO FORCE10 NETWORKS, INC. AND WYSE TECHNOLOGY L.L.C.); EMC CORPORATION (ON BEHALF OF ITSELF AND AS SUCCESSOR-IN-INTEREST TO MAGINATICS LLC); EMC IP HOLDING COMPANY LLC (ON BEHALF OF ITSELF AND AS SUCCESSOR-IN-INTEREST TO MOZY, INC.); SCALEIO LLC
Reel/Frame 061753/0001 →
RELEASE OF SECURITY INTEREST IN PATENTS PREVIOUSLY RECORDED AT REEL/FRAME (040136/0001) Recorded Apr 26, 2022
From: THE BANK OF NEW YORK MELLON TRUST COMPANY, N.A., AS NOTES COLLATERAL AGENT
To: DELL MARKETING CORPORATION (SUCCESSOR-IN-INTEREST TO ASAP SOFTWARE EXPRESS, INC.); DELL MARKETING L.P. (ON BEHALF OF ITSELF AND AS SUCCESSOR-IN-INTEREST TO CREDANT TECHNOLOGIES, INC.); DELL USA L.P.; DELL INTERNATIONAL L.L.C.; DELL PRODUCTS L.P.; DELL MARKETING CORPORATION (SUCCESSOR-IN-INTEREST TO FORCE10 NETWORKS, INC. AND WYSE TECHNOLOGY L.L.C.); EMC CORPORATION (ON BEHALF OF ITSELF AND AS SUCCESSOR-IN-INTEREST TO MAGINATICS LLC); EMC IP HOLDING COMPANY LLC (ON BEHALF OF ITSELF AND AS SUCCESSOR-IN-INTEREST TO MOZY, INC.); SCALEIO LLC
Reel/Frame 061324/0001 →
RELEASE OF SECURITY INTEREST Recorded Nov 3, 2021
From: CREDIT SUISSE AG, CAYMAN ISLANDS BRANCH
To: ASAP SOFTWARE EXPRESS, INC.; AVENTAIL LLC; CREDANT TECHNOLOGIES, INC.; DELL USA L.P.; DELL INTERNATIONAL, L.L.C.; DELL MARKETING L.P.; DELL PRODUCTS L.P.; DELL SOFTWARE INC.; DELL SYSTEMS CORPORATION; EMC CORPORATION; EMC IP HOLDING COMPANY LLC; FORCE10 NETWORKS, INC.; MAGINATICS LLC; MOZY, INC.; SCALEIO LLC; WYSE TECHNOLOGY L.L.C.
Reel/Frame 058216/0001 →
SECURITY AGREEMENT Recorded Apr 22, 2020
From: CREDANT TECHNOLOGIES INC.; DELL INTERNATIONAL L.L.C.; DELL MARKETING L.P.; DELL PRODUCTS L.P.; DELL USA L.P.; EMC CORPORATION; FORCE10 NETWORKS, INC.; WYSE TECHNOLOGY L.L.C.; EMC IP HOLDING COMPANY LLC
To: THE BANK OF NEW YORK MELLON TRUST COMPANY, N.A.
Reel/Frame 053546/0001 →
SECURITY AGREEMENT Recorded Mar 21, 2019
From: CREDANT TECHNOLOGIES, INC.; DELL INTERNATIONAL L.L.C.; DELL MARKETING L.P.; DELL PRODUCTS L.P.; DELL USA L.P.; EMC CORPORATION; FORCE10 NETWORKS, INC.; WYSE TECHNOLOGY L.L.C.; EMC IP HOLDING COMPANY LLC
To: THE BANK OF NEW YORK MELLON TRUST COMPANY, N.A.
Reel/Frame 049452/0223 →
SECURITY AGREEMENT Recorded Sep 21, 2016
From: ASAP SOFTWARE EXPRESS, INC.; AVENTAIL LLC; CREDANT TECHNOLOGIES, INC.; DELL USA L.P.; DELL INTERNATIONAL L.L.C.; DELL MARKETING L.P.; DELL PRODUCTS L.P.; DELL SOFTWARE INC.; DELL SYSTEMS CORPORATION; EMC CORPORATION; EMC IP HOLDING COMPANY LLC; FORCE10 NETWORKS, INC.; MAGINATICS LLC; MOZY, INC.; SCALEIO LLC; SPANNING CLOUD APPS LLC; WYSE TECHNOLOGY L.L.C.
To: CREDIT SUISSE AG, CAYMAN ISLANDS BRANCH, AS COLLATERAL AGENT
Reel/Frame 040134/0001 →
SECURITY AGREEMENT Recorded Sep 21, 2016
From: ASAP SOFTWARE EXPRESS, INC.; AVENTAIL LLC; CREDANT TECHNOLOGIES, INC.; DELL USA L.P.; DELL INTERNATIONAL L.L.C.; DELL MARKETING L.P.; DELL PRODUCTS L.P.; DELL SOFTWARE INC.; DELL SYSTEMS CORPORATION; EMC CORPORATION; EMC IP HOLDING COMPANY LLC; FORCE10 NETWORKS, INC.; MAGINATICS LLC; MOZY, INC.; SCALEIO LLC; SPANNING CLOUD APPS LLC; WYSE TECHNOLOGY L.L.C.
To: THE BANK OF NEW YORK MELLON TRUST COMPANY, N.A., AS NOTES COLLATERAL AGENT
Reel/Frame 040136/0001 →
RELEASE OF SECURITY INTEREST Recorded Sep 14, 2016
From: BANK OF AMERICA, N.A., AS COLLATERAL AGENT
To: DELL MARKETING L.P.; ASAP SOFTWARE EXPRESS, INC.; APPASSURE SOFTWARE, INC.; COMPELLENT TECHNOLOGIES, INC.; CREDANT TECHNOLOGIES, INC.; DELL INC.; DELL PRODUCTS L.P.; DELL USA L.P.; DELL SOFTWARE INC.; FORCE10 NETWORKS, INC.; PEROT SYSTEMS CORPORATION; SECUREWORKS, INC.; WYSE TECHNOLOGY L.L.C.
Reel/Frame 040040/0001 →
RELEASE OF SECURITY INTEREST Recorded Sep 14, 2016
From: BANK OF NEW YORK MELLON TRUST COMPANY, N.A., AS COLLATERAL AGENT
To: DELL MARKETING L.P.; ASAP SOFTWARE EXPRESS, INC.; APPASSURE SOFTWARE, INC.; COMPELLENT TECHNOLOGIES, INC.; CREDANT TECHNOLOGIES, INC.; DELL INC.; DELL PRODUCTS L.P.; DELL USA L.P.; DELL SOFTWARE INC.; FORCE10 NETWORKS, INC.; PEROT SYSTEMS CORPORATION; SECUREWORKS, INC.; WYSE TECHNOLOGY L.L.C.
Reel/Frame 040065/0618 →
RELEASE OF SECURITY INTEREST Recorded Sep 13, 2016
From: BANK OF AMERICA, N.A., AS ADMINISTRATIVE AGENT
To: DELL MARKETING L.P.; ASAP SOFTWARE EXPRESS, INC.; APPASSURE SOFTWARE, INC.; COMPELLANT TECHNOLOGIES, INC.; CREDANT TECHNOLOGIES, INC.; DELL INC.; DELL PRODUCTS L.P.; DELL USA L.P.; DELL SOFTWARE INC.; FORCE10 NETWORKS, INC.; PEROT SYSTEMS CORPORATION; SECUREWORKS, INC.; WYSE TECHNOLOGY L.L.C.
Reel/Frame 040065/0216 →
PATENT SECURITY AGREEMENT (NOTES) Recorded Jan 2, 2014
From: APPASSURE SOFTWARE, INC.; ASAP SOFTWARE EXPRESS, INC.; BOOMI, INC.; COMPELLENT TECHNOLOGIES, INC.; CREDANT TECHNOLOGIES, INC.; DELL INC.; DELL MARKETING L.P.; DELL PRODUCTS L.P.; DELL SOFTWARE INC.; DELL USA L.P.; FORCE10 NETWORKS, INC.; GALE TECHNOLOGIES, INC.; PEROT SYSTEMS CORPORATION; SECUREWORKS, INC.; WYSE TECHNOLOGY L.L.C.
To: BANK OF NEW YORK MELLON TRUST COMPANY, N.A., AS FIRST LIEN COLLATERAL AGENT
Reel/Frame 031897/0348 →
PATENT SECURITY AGREEMENT (TERM LOAN) Recorded Jan 2, 2014
From: DELL INC.; APPASSURE SOFTWARE, INC.; ASAP SOFTWARE EXPRESS, INC.; BOOMI, INC.; COMPELLENT TECHNOLOGIES, INC.; CREDANT TECHNOLOGIES, INC.; DELL MARKETING L.P.; DELL PRODUCTS L.P.; DELL SOFTWARE INC.; DELL USA L.P.; FORCE10 NETWORKS, INC.; GALE TECHNOLOGIES, INC.; PEROT SYSTEMS CORPORATION; SECUREWORKS, INC.; WYSE TECHNOLOGY L.L.C.
To: BANK OF AMERICA, N.A., AS COLLATERAL AGENT
Reel/Frame 031899/0261 →
PATENT SECURITY AGREEMENT (ABL) Recorded Jan 2, 2014
From: DELL INC.; APPASSURE SOFTWARE, INC.; ASAP SOFTWARE EXPRESS, INC.; BOOMI, INC.; COMPELLENT TECHNOLOGIES, INC.; CREDANT TECHNOLOGIES, INC.; DELL MARKETING L.P.; DELL PRODUCTS L.P.; DELL SOFTWARE INC.; DELL USA L.P.; FORCE10 NETWORKS, INC.; GALE TECHNOLOGIES, INC.; PEROT SYSTEMS CORPORATION; SECUREWORKS, INC.; WYSE TECHNOLOGY L.L.C.
To: BANK OF AMERICA, N.A., AS ADMINISTRATIVE AGENT
Reel/Frame 031898/0001 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jan 27, 2012
From: CHERIAN, JACOB; DAR, ITAY
To: DELL PRODUCTS L.P.
Reel/Frame 027605/0383 →
Continuity (2)
Provisional Application 61581439 · Dec 29, 2011
Related Publication 20130173561A1 · Jul 4, 2013