Deduplication of regions with a storage system

• US 9,891,858 B1
• Filed: 01/26/2017
• Issued: 02/13/2018
• Est. Priority Date: 01/10/2013
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Colgrove, John, Miller, Ethan, Hayes, John, Sandvig, Cary, Golden, Christopher, Cao, Jianting
• Primary Examiner(s): Tsai, Henry
• Assistant Examiner(s): Bartels, Christopher
• Application Number:
  US15/416,665
• Time in Patent Office: 383 Days
• Field of Search: None
• 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/23 Updating
• CPC Class Codes: G06F 2212/1008 Correctness of operation, e.g. memory ordering
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: G06F 2212/163 Server or database system
• CPC Class Codes: G06F 2212/261 Storage comprising a plurality of storage devices
• CPC Class Codes: G06F 2212/263 Network storage, e.g. SAN or NAS
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0626 Reducing size or complexity of storage systems
• CPC Class Codes: G06F 3/0632 by initialisation or re-initialisation of 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/065 : Replication mechanisms
• CPC Class Codes: G06F 3/0652 : Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0655 : Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• CPC Class Codes: G06F 3/0664 : at device level, e.g. emulation of a storage device or system
• CPC Class Codes: G06F 3/0665 : at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/0667 : at data level, e.g. file, record or object virtualisation
• CPC Class Codes: G06F 3/067 : Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0671 : In-line storage system
• CPC Class Codes: G06F 3/0673 : Single storage device
• CPC Class Codes: G06F 3/0683 : Plurality of storage devices
• CPC Class Codes: G06F 3/0685 : Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays
• CPC Class Codes: G06F 3/0689 : Disk arrays, e.g. RAID, JBOD

Abstract

A system and method for performing coarse-grained deduplication of volume regions. A storage controller detects that a first region of a first volume is identical to a second region of a second volume, wherein the first volume points to a first medium and the second volume points to a second medium. In response to detecting the identical regions, the storage controller stores an indication that the first range of the first medium underlies the second range of the second medium. Also in response to detecting the identical regions, the mappings associated with the second range of the second medium are invalidated.

Claims

1. A computer system comprising:

a data storage subsystem comprising a plurality of data storage locations on a plurality of storage devices; and

a storage controller coupled to the plurality of storage devices, wherein the storage controller is configured to;

maintain a table to track mappings between logical groups of active data in the plurality of storage devices and logical groups of snapshot data in the plurality of storage devices;

determine that snapshot data within a first range of a first logical group of snapshot data is representative of active data within a second range of second logical group of active data;

in response to determining that snapshot data within the first range is representative of active data within the second range, indicate within the table, a mapping of the second range of the second logical group of active data to the first range of the first logical group of snapshot data; and

responsive to indicating with the table, the mapping of the second range to the first range, invalidate a plurality of entries corresponding to the second range in the table.

2. The computer system as recited in claim 1, wherein the first range of the first logical group and the second range of the second logical group are associated with a first volume.

3. The computer system as recited in claim 1, wherein the snapshot data of the first range of the first logical group is read-only.

4. The computer system as recited in claim 1, wherein the first range of snapshot data is located at a first offset within an address space of the first logical group, wherein the second range of active data is located at a second offset within an address space of the second logical group, and wherein the storage controller is configured to store an indication that the second logical group is aligned to the first logical group using a third offset, wherein the third offset is equal to a difference between the second offset and the first offset.

5. The computer system as recited in claim 1, wherein the second range is a portion of an address space of the second logical group, wherein the storage controller is further configured to:

create a new entry in the table for each additional range of the second logical group; and

copy a plurality of attributes from a second entry in the table to each new entry, wherein the second entry is assigned to the second logical group, and wherein the plurality of attributes include a specification of another logical group and an offset.

6. The computer system as recited in claim 1, wherein the indication is stored in a first entry in the table, and wherein the first entry is assigned to the second logical group.

7. A method for use in a storage system, the storage system including a plurality of storage devices, the method comprising:

maintaining a table to track mappings between logical groups of active data in the plurality of storage devices and logical groups of snapshot data in the plurality of storage devices;

determining that snapshot data within a first range of a first logical group of snapshot data is representative of active data within a second range of second logical group of active data;

in response to determining that snapshot data within the first range is representative of active data within the second range, indicating within the table, a mapping of the second range of the second logical group of active data to the first range of the first logical group of snapshot data; and

responsive to indicating with the table, the mapping of the second range to the first range, invalidating a plurality of entries corresponding to the second range in the table.

8. The method as recited in claim 7, wherein the first range of the first logical group and the second range of the second logical group are associated with a first volume.

9. The method as recited in claim 7, wherein the snapshot data of the first range of the first logical group is read-only.

10. The method as recited in claim 7, wherein the first range of snapshot data is located at a first offset within an address space of the first logical group, wherein the second range of active data is located at a second offset within an address space of the second logical group, and wherein the method further comprising storing an indication that the second logical group is aligned to the first logical group using a third offset, wherein the third offset is equal to a difference between the second offset and the first offset.

11. The method as recited in claim 7, wherein the second range is a portion of an address space of the second logical group, wherein the method further comprising:

creating a new entry in the table for each additional range of the second logical group; and

copying a plurality of attributes from a second entry in the table to each new entry, wherein the second entry is assigned to the second logical group, and wherein the plurality of attributes include a specification of another logical group and an offset.

12. The method as recited in claim 7, wherein the indication is stored in a first entry in the table, and wherein the first entry is assigned to the second logical group.

13. A non-transitory computer readable storage medium storing program instructions, wherein the program instructions are executable by a processor to:

maintain a table to track mappings between logical groups of active data in the plurality of storage devices and logical groups of snapshot data in the plurality of storage devices;

determine that snapshot data within a first range of a first logical group of snapshot data is representative of active data within a second range of second logical group of active data;

in response to determining that snapshot data within the first range is representative of active data within the second range, indicate within the table, a mapping of the second range of the second logical group of active data to the first range of the first logical group of snapshot data; and

responsive to indicating with the table, the mapping of the second range to the first range, invalidate a plurality of entries corresponding to the second range in the table.

14. The computer readable storage medium as recited in claim 13, wherein the first range of the first logical group and the second range of the second logical group are associated with a first volume.

15. The computer readable storage medium as recited in claim 13, wherein the snapshot data of the first range of the first logical group is read-only.

16. The computer readable storage medium as recited in claim 13, wherein the first range of snapshot data is located at a first offset within an address space of the first logical group, wherein the second range of active data is located at a second offset within an address space of the second logical group, and wherein the program instructions are executable by a processor to store an indication that the second logical group is aligned to the first logical group using a third offset, wherein the third offset is equal to a difference between the second offset and the first offset.

17. The computer readable storage medium as recited in claim 13, wherein the second range is a portion of an address space of the second logical group, and wherein the program instructions are further executable by a processor to:

create a new entry in the table for each additional range of the second logical group; and

copy a plurality of attributes from a second entry in the table to each new entry, wherein the second entry is assigned to the second logical group, and wherein the plurality of attributes include a specification of another logical group an underlying medium and an offset.