IP Library › Granted Patent US 9,436,723
Granted Patent B2
US 9,436,723 · App. 14/271,246 · Granted Sep 6, 2016

Segment deduplication system with compression of segments

Inventor: Christopher R. Lumb (Mountain View, CA)
Assignee: EMC Corporation
G06F17/30371G06F3/0608G06F3/0641G06F3/0683G06F17/30067G06F17/30286H03M7/3064G06F11/1435G06F11/1453H03M7/30
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 9,436,723
App. No.
14/271,246
Filed
May 6, 2014
Granted
Sep 6, 2016
Kind
B2
Art Unit
2157
USPC
707/687
Abstract

A system for storing compressed data comprises a processor and a memory. The processor is configured to receive a compressed segment. The compressed segment is determined by breaking a data stream, a data block, or a data file into one or more segments and compressing each of the one or more segments. The processor is further configured to determine whether the compressed segment has been previously stored, and in the event that the compressed segment has not been previously stored, store the compressed segment. The memory is coupled to the processor and configured to provide the processor with instructions.

Claims (54)

1. A system for reading compressed data, comprising:

a deduplicated storage device;

a processor configured to:

receive a request for a data stream, a data block, or a data file to be retrieved;

retrieve one or more compressed segments and corresponding metadata information for each compressed segment,

wherein the corresponding metadata information comprises a compression type and a compression state from the deduplicated storage device using mapping information,

wherein the compression state comprises a state used for compressing the compressed segment, wherein the compression state comprises a 128 bit key, a 256 bit key, or an alphanumeric key,

wherein the one or more compressed segments were determined by breaking the data stream, the data block, or the data file into one or more segments and compressing each of the one or more segments,

wherein the deduplicated storage device stores compressed segments that have not been previously stored and references to compressed segments that have been determined to be identical to a previously stored compressed segment,

wherein the deduplicated storage device stores compressed segments that have not been previously stored with an index entry generated from the compressed segments,

wherein the index entry comprises one or more of the following: a digital fingerprint, SHA-1 hash, or Rabin Hash of each unique compressed segment,

wherein the deduplicated storage device further retrieves the one or more compressed segments indicated by the mapping information using index entries of compressed segments in the deduplicated storage;

decompress the one or more compressed segments using the segment compression information retrieved from the deduplicated storage device,

wherein the segment compression information comprises a segment identifier and a compression type; and

assemble the one or more compressed segments to reconstruct the data stream, the data block, or the data file using the mapping information,

wherein the mapping information comprises a mapping of segment identifiers and the data stream, the data block, or the data file; and

a memory coupled to the processor and configured to provide the processor with instructions.

2. A system as in claim 1 , wherein the breaking the data stream, the data block, or the data file is based at least in part on one of the following: a content-based technique or a non-content-based technique.

3. A system as in claim 1 , wherein the one or more compressed segments were compressed and decompressed with one of the following: a lossless compression system, a Huffman coding system, or a Lempel-Ziv Welch coding system.

4. A system as in claim 1 , wherein for a first compressed segment and a second compressed segment that is identical to the first compressed segment, a decompressed first compressed segment is identical to a decompressed second compressed segment.

5. A method for reading compressed data, comprising:

receiving a request for a data stream, a data block, or a data file to be retrieved;

retrieving one or more compressed segments and corresponding metadata information for each compressed segment,

wherein the corresponding metadata information comprises a compression type and a compression state from a deduplicated storage device using mapping information,

wherein the compression state comprises a state used for compressing the compressed segment, wherein the compression state comprises a 128 bit key, a 256 bit key, or an alphanumeric key,

wherein the one or more compressed segments were determined by breaking the data stream, the data block, or the data file into one or more segments and compressing each of the one or more segments,

wherein the deduplicated storage device stores compressed segments that have not been previously stored and references to compressed segments that have been determined to be identical to a previously stored compressed segment,

wherein the deduplicated storage device stores compressed segments that have not been previously stored with an index entry generated from the compressed segments,

wherein the index entry comprises one or more of the following: a digital fingerprint, SHA-1 hash, or Rabin Hash of each unique compressed segment,

wherein the deduplicated storage device further retrieves the one or more compressed segments indicated by the mapping information using index entries of compressed segments in the deduplicated storage;

decompressing, using a processor, the one or more compressed segments using the segment compression information retrieved from the deduplicated storage device,

wherein the segment compression information comprises a segment identifier and a compression type; and

assembling the one or more decompressed segments to reconstruct the data stream, the data block, or the data file using the mapping information,

wherein the mapping information comprises a mapping of segment identifiers and the data stream, the data block, or the data file.

6. A method as in claim 5 , wherein the breaking the data stream, the data block, or the data file is based at least in part on one of the following: a content-based technique or a non-content-based technique.

7. A method as in claim 5 , wherein the one or more compressed segments were compressed and decompressed with one of the following: a lossless compression system, a Huffman coding system, or a Lempel-Ziv Welch coding system.

8. A method as in claim 5 , wherein for a first compressed segment and a second compressed segment that is identical to the first compressed segment, a decompressed first compressed segment is identical to a decompressed second compressed segment.

9. A system as in claim 5 , wherein the deduplicating storage device stores metadata information associated with the segment.

10. A system as in claim 9 , wherein the metadata information comprises one or more of the following: the segment identifier, a source identifier, a user identifier, a host identifier, a session identifier, a format type, an associated file, an associated data stream, or an associated data block.

11. A system as in claim 5 , wherein the processor is further configured to provide the data stream, the data block, or the data file to a user.

12. A computer program product for reading compressed data, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:

receiving a request for a data stream, a data block, or a data file to be retrieved;

retrieving one or more compressed segments and corresponding metadata information for each compressed segment,

wherein the corresponding metadata information comprises a compression type and a compression state from a deduplicated storage device using mapping information,

wherein the compression state comprises a state used for compressing the compressed segment, wherein the compression state comprises a 128 bit key, a 256 bit key, or an alphanumeric key,

wherein the one or more compressed segments were determined by breaking the data stream, the data block, or the data file into one or more segments and compressing each of the one or more segments,

wherein the deduplicated storage device stores compressed segments that have not been previously stored and references to compressed segments that have been determined to be identical to a previously stored compressed segment,

wherein the deduplicated storage device stores compressed segments that have not been previously stored with an index entry generated from the compressed segments,

wherein the index entry comprises one or more of the following: a digital fingerprint, SHA-1 hash, or Rabin Hash of each unique compressed segment,

wherein the deduplicated storage device further retrieves the one or more compressed segments indicated by the mapping information using index entries of compressed segments in the deduplicated storage;

decompressing, using a processor, the one or more compressed segments using the segment compression information retrieved from the deduplicated storage device,

wherein the segment compression information comprises a segment identifier and a compression type; and

assembling the one or more decompressed segments to reconstruct the data stream, the data block, or the data file using the mapping information,

wherein the mapping information comprises a mapping of segment identifiers and the data stream, the data block, or the data file.

Assignments (13)
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 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Sep 29, 2016
From: EMC CORPORATION
To: EMC IP HOLDING COMPANY LLC
Reel/Frame 040203/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 →
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 →
CONVERSION Recorded Sep 15, 2014
From: DATA DOMAIN, INC.
To: DATA DOMAIN LLC
Reel/Frame 033745/0444 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Sep 15, 2014
From: DATA DOMAIN HOLDING, INC.
To: EMC CORPORATION
Reel/Frame 033743/0510 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Sep 15, 2014
From: DATA DOMAIN LLC
To: DATA DOMAIN HOLDING, INC.
Reel/Frame 033743/0508 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Sep 15, 2014
From: LUMB, CHRISTOPHER R.
To: DATA DOMAIN, INC.
Reel/Frame 033743/0506 →
Continuity (2)
Continuation 12455951 · Jun 9, 2009
Related Publication 20140330797A1 · Nov 6, 2014