Optimizing storage allocation in a storage system

• US 10,114,574 B1
• Filed: 10/31/2016
• Issued: 10/30/2018
• Est. Priority Date: 10/07/2014
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Golden, Christopher, Colgrove, John, Miller, Ethan L., Sharpe, Malcolm, Hodgson, Steve
• Primary Examiner(s): Tsui, Daniel D
• Application Number:
  US15/339,524
• Time in Patent Office: 729 Days
• Field of Search: None
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 2212/1056 Simplification
• CPC Class Codes: G06F 2212/214 Solid state disk
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

A system and method for utilizing unmapped and unknown states in a storage system. When a first portion of a first medium is determined to be unreachable from any other mediums, the first portion of the first medium may be put into an unmapped state, and its data may be discarded and the corresponding storage locations may be freed. During replication of the first medium to a replica storage array, the state of the first portion of the first medium may be translated from the unmapped state into an unknown state on the replica storage array. If another storage array has the data of the first portion of the first medium, this data may be used to overwrite the first portion of the first medium on the replica storage array, converting the first portion of the first medium from the unknown state into the mapped state.

Claims

1. A method comprising:

performing one or more write operations to a first portion of a first logical grouping of data;

in response to performing one or more write operations to the first portion, recording that a second portion of a second logical grouping of data no longer underlies the first portion of the first logical grouping of data;

determining whether any other logical groupings of data are mapped to the second portion of the second logical grouping of data; and

allocating storage locations associated with the second portion of the second logical grouping of data based on the determination of whether any other logical groupings of data are mapped to the second portion of the second logical grouping of data.

2. The method of claim 1 wherein allocating storage locations includes:

in response to determining that one or more other logical groupings of data are mapped to the second portion of the second logical grouping of data, maintaining the second portion of the second logical grouping of data in a mapped state.

3. The method of claim 1 wherein allocating storage locations includes:

in response to determining that no other logical groupings are mapped to the second portion of the second logical grouping of data;

changing the state of the second portion of the second logical grouping of data to an unmapped state;

discarding data of the second portion of the second logical grouping of data; and

freeing storage locations corresponding to the discarded data.

4. The method of claim 3 wherein the unmapped state indicates that the contents of the portion has been forgotten by a host subsystem.

5. The method of claim 3 wherein freeing storage locations corresponding to the discarded data includes performing garbage collection operations on the storage locations.

6. The method of claim 3 further comprising reusing the freed storage locations.

7. The method of claim 1 wherein, prior to performing one or more write operations to a first portion of a first logical grouping of data, the first portion of the first logical grouping of data is mapped to the second portion of the second logical grouping of data.

8. An apparatus comprising a computer processor and a computer readable storage medium, wherein the computer readable storage medium includes computer program instructions that when executed by the computer processor cause the apparatus to carry out the steps of:

performing one or more write operations to a first portion of a first logical grouping of data;

in response to performing one or more write operations to the first portion, recording that a second portion of a second logical grouping of data no longer underlies the first portion of the first logical grouping of data;

determining whether any other logical groupings of data are mapped to the second portion of the second logical grouping of data; and

allocating storage locations associated with the second portion of the second logical grouping of data based on the determination of whether any other logical groupings of data are mapped to the second portion of the second logical grouping of data.

9. The apparatus of claim 8 wherein allocating storage locations includes:

in response to determining that one or more other logical groupings of data are mapped to the second portion of the second logical grouping of data, maintaining the second portion of the second logical grouping of data in a mapped state.

10. The apparatus of claim 8 wherein allocating storage locations includes:

in response to determining that no other logical groupings are mapped to the second portion of the second logical grouping of data;

changing the state of the second portion of the second logical grouping of data to an unmapped state;

discarding data of the second portion of the second logical grouping of data; and

freeing storage locations corresponding to the discarded data.

11. The apparatus of claim 10 wherein the unmapped state indicates that the contents of the portion has been forgotten by a host subsystem.

12. The apparatus of claim 10 wherein freeing storage locations corresponding to the discarded data includes performing garbage collection operations on the storage locations.

13. The apparatus of claim 10 wherein the computer readable storage medium includes computer program instructions that when executed by the computer processor cause the apparatus to carry out the steps of reusing the freed storage locations.

14. The apparatus of claim 8 wherein, prior to performing one or more write operations to a first portion of a first logical grouping of data, the first portion of the first logical grouping of data is mapped to the second portion of the second logical grouping of data.

15. A computer readable storage medium, the computer readable storage medium including computer program instructions that when executed by a computer cause the computer to carry out the steps of:

performing one or more write operations to a first portion of a first logical grouping of data;

in response to performing one or more write operations to the first portion, recording that a second portion of a second logical grouping of data no longer underlies the first portion of the first logical grouping of data;

determining whether any other logical groupings of data are mapped to the second portion of the second logical grouping of data; and

allocating storage locations associated with the second portion of the second logical grouping of data based on the determination of whether any other logical groupings of data are mapped to the second portion of the second logical grouping of data.

16. The computer program product of claim 15 wherein allocating storage locations includes:

in response to determining that one or more other logical groupings of data are mapped to the second portion of the second logical grouping of data, maintaining the second portion of the second logical grouping of data in a mapped state.

17. The computer program product of claim 15 wherein allocating storage locations includes:

in response to determining that no other logical groupings are mapped to the second portion of the second logical grouping of data;

changing the state of the second portion of the second logical grouping of data to an unmapped state;

discarding data of the second portion of the second logical grouping of data; and

freeing storage locations corresponding to the discarded data.

18. The computer program product of claim 17 wherein the unmapped state indicates that the contents of the portion has been forgotten by a host subsystem.

19. The computer program product of claim 17 wherein freeing storage locations corresponding to the discarded data includes performing garbage collection operations on the storage locations.

20. The computer program product of claim 17 wherein the computer readable storage medium includes computer program instructions that when executed by a computer cause the computer to carry out the steps of reusing the freed storage locations.