Efficient memory utilization in a dispersed storage system

• US 9,489,533 B2
• Filed: 06/23/2014
• Issued: 11/08/2016
• Est. Priority Date: 12/29/2009
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Grube, Gary W., Markison, Timothy W., Gladwin, S. Christopher, Resch, Jason K., Leggette, Wesley, Baptist, Andrew
• Primary Examiner(s): Pham, Khanh
• Application Number:
  US14/312,550
• Publication Number:
  US 20140304527A1
• Time in Patent Office: 869 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 2209/603 Digital right managament [DRM]
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions

Abstract

A method for improving memory utilization in a dispersed storage network (DSN). After a data object is received for storage in the DSN, it is determined whether a substantially identical data portion of the data object has previously been encrypted and stored. The determination may be made, for example, by comparing a portion reference value relating to the data object to portion reference information stored in DSN memory. If not detected, the data object is encrypted using an encryption pattern sequence and encryption key, at least one of which substantially identical to at least a portion of the data portion. The encrypted data object is then compressed using a pattern based data compression function, and the compressed data object is stored. The portion reference value is also stored in DSN memory.

Claims

1. A data deduplication method for execution by a computing device, wherein the method comprises:

receiving a storage request regarding storing a data object in dispersed storage network (DSN) memory;

determining a data portion of the data object;

determining that a substantially identical data portion is stored in the DSN memory;

obtaining an encryption pattern sequence for the substantially identical data portion;

retrieving an encryption key of the substantially identical data portion from the DSN memory, wherein, based on the encryption pattern sequence, a first portion of the encryption key is identical to a first portion of the substantially identical data portion and a second portion of the encryption key is identical to an inverted second portion of the substantially identical data portion;

encrypting the data portion using the encryption key and the encryption pattern sequence to produce an encrypted data portion that includes a plurality of encrypted data segments;

compressing the encrypted data portion using a pattern based data compression function to produce a compressed data portion; and

facilitating storage of the compressed data portion and the encryption pattern sequence in response to the storage request.

2. The method of claim 1 further comprises:

compressing the encryption pattern sequence to produce a compressed encryption pattern sequence; and

sending the compressed encryption pattern sequence to the DSN memory for storage therein.

3. The method of claim 2, wherein the step of determining that a substantially identical data portion is stored in the DSN memory includes:

determining a portion reference for the data portion;

retrieving stored portion reference information from the DSN memory; and

comparing the portion reference to the stored portion reference information to determine that the stored portion reference information includes substantially the same portion reference.

4. The method of claim 3 further comprises:

sending the portion reference to the DSN memory for storage therein in combination with the compressed encryption pattern sequence.

5. The method of claim 3, wherein the portion reference for the data portion is based on at least one of:

a portion of the data portion;

a hash algorithm;

a calculated hash of the data portion;

an encryption algorithm;

operational parameters;

or

content of a store data object message relating to the data object.

6. The method of claim 1, wherein the compressed data portion includes a plurality of compressed data segments, and wherein compressing the encrypted data portion comprises:

compressing a first data segment of the compressed data portion using a using a first portion of the encryption pattern sequence and a first compression function of the pattern based data compression function; and

compressing a second data segment of the compressed data portion using a second portion of the encryption pattern sequence and a second compression function of the pattern based data compression function.

7. The method of claim 1, wherein storing the compressed data portion comprises:

storing the compressed data portion in local memory of the computing device.

8. The method of claim 1, wherein the encryption key comprises at least one of:

a substantially identical version of the data portion;

a substantially identical portion of the data portion;

or

an inversion of a substantially identical version of the data portion.

9. The method of claim 1, wherein encrypting the data portion using the encryption key and the encryption pattern sequence comprises:

encrypting the first portion of the data portion using a first encrypting function; and

encrypting a second portion of the data portion using a second encrypting function.

10. The method of claim 9, wherein encrypting the data portion using the encryption key and the encryption pattern sequence includes:

subtracting the first portion of the encryption key from the first portion of the data portion to produce a first encrypted data segment of the plurality of encrypted data segments; and

exclusive ORing a second portion of the encryption key with the second portion of the data portion to produce a second encrypted data segment of the plurality of encrypted data segments.

11. A non-transitory computer readable storage medium having accessible therefrom a set of instructions interpretable by a processing module, the set of instructions being configured to cause the processing module to carry out operations for:

receiving a storage request regarding storing a data object in dispersed storage network (DSN) memory;

determining a data portion of the data object;

determining that a substantially identical data portion is stored in the DSN memory;

obtaining an encryption pattern sequence for the substantially identical data portion;

retrieving an encryption key of the substantially identical data portion from the DSN memory, wherein, based on the encryption pattern sequence, a first portion of the encryption key is identical to a first portion of the substantially identical data portion and a second portion of the encryption key is identical to an inverted second portion of the substantially identical data portion;

encrypting the data portion using the encryption key and the encryption pattern sequence to produce an encrypted data portion that includes a plurality of encrypted data segments;

compressing the encrypted data portion using a pattern based data compression function to produce a compressed data portion; and

facilitating storage of the compressed data portion and the encryption pattern sequence in response to the storage request.

12. The non-transitory computer readable storage medium of claim 11, wherein the set of instructions further causes the processing module to carry out operations for:

compressing the encryption pattern sequence to produce a compressed encryption pattern sequence; and

sending the compressed encryption pattern sequence to the DSN memory for storage therein.

13. The non-transitory computer readable storage medium of claim 12, wherein the set of instructions further causes the processing module to carry out operations for determining that a substantially identical data portion is stored in the DSN memory by:

determining a portion reference for the data portion;

retrieving stored portion reference information from the DSN memory; and

comparing the portion reference to the stored portion reference information to determine that the stored portion reference information includes substantially the same portion reference.

14. The non-transitory computer readable storage medium of claim 13, wherein the set of instructions further being configured to cause the processing module to carry out operations for:

sending the portion reference to the DSN memory for storage therein in combination with the compressed encryption pattern sequence.

15. The non-transitory computer readable storage medium of claim 13, wherein the set of instructions further being configured to cause the processing module to carry out operations for:

encrypting the first portion of the data portion using a first encrypting function; and

encrypting a second portion of the data portion using a second encrypting function.

16. The non-transitory computer readable storage medium of claim 13, wherein the set of instructions further being configured to cause the processing module to carry out operations for:

subtracting the first portion of the encryption key from the first portion of the data portion to produce a first encrypted data segment of the plurality of encrypted data segments; and

exclusive ORing a second portion of the encryption key with the second portion of the data portion to produce a second encrypted data segment of the plurality of encrypted data segments.

17. The non-transitory computer readable storage medium of claim 11, wherein the set of instructions further causes the processing module to carry out operations for the storing of the compressed data portion by:

dispersed storage error encoding the compressed data portion to produce one or more sets of encoded data slices; and

sending the one or more sets of encoded data slices to the DSN memory for storage therein.