Mapping in a storage system

• US 8,806,160 B2
• Filed: 08/16/2011
• Issued: 08/12/2014
• Est. Priority Date: 08/16/2011
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Colgrove, John, Hayes, John, Miller, Ethan, Sandvig, Cary
• Primary Examiner(s): RUTZ, JARED IAN
• Application Number:
  US13/211,288
• Publication Number:
  US 20130046949A1
• Time in Patent Office: 1,092 Days
• Field of Search: 711/162, 707/639
• US Class Current: 711/162
• 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/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• 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/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/0668 adopting a particular infrastructure
• 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

Abstract

A system and method for maintaining a mapping table in a data storage subsystem. A data storage subsystem supports multiple mapping tables. Records within a mapping table are arranged in multiple levels which may be logically ordered by time. Each level stores pairs of a key value and a pointer value. New records are inserted in a created new (youngest) level. All levels other than the youngest may be read only. In response to detecting a flattening condition, a data storage controller is configured to identify a group of two or more adjacent levels of the plurality of levels for flattening which are logically adjacent in time. A new level is created and one or more records stored within the group are stored in the new level, in response to detecting each of the one or more records stores a unique key among keys stored within the group.

Claims

1. A computer system comprising:

a data storage medium;

an overlay table;

a mapping table organized as a plurality of levels, each level of the plurality of levels comprising one or more mapping table entries, where each of the plurality of entries comprises a tuple including a key; and

a data storage controller coupled to the data storage medium;

wherein in response to detecting a flattening condition, the data storage controller is configured to;

identify a group of two or more levels of the plurality of levels which are logically adjacent in time;

create a new level in the plurality of levels;

insert one or more first records stored within the group into the new level, in response to detecting each of the one or more first records stores a unique key among keys stored within the group; and

utilize a filtering condition to determine which of the first records are inserted into the new level, wherein the filtering condition comprises a validity of a given record as determined by the overlay table.

2. The computer system as recited in claim 1, wherein the plurality of levels of the mapping table are organized as time ordered levels.

3. The computer system as recited in claim 1, wherein the data storage controller is further configured to sort records within the new level.

4. The computer system as recited in claim 1, wherein the mapping table entries within a level of the plurality of levels are sorted by key.

5. The computer system as recited in claim 1, wherein the data storage controller is configured to perform flattening operations on the mapping table asynchronously with respect to updates to the mapping table.

6. The computer system as recited in claim 1, wherein in response to detecting the flattening condition, the data storage controller is further configured to insert one or more second records stored within the group into the new level, in response to detecting each of the one or more second records:

corresponds to two or more records storing a same non-unique key within the group; and

is in a youngest level containing a record with the non-unique key of the group.

7. The computer system as recited in claim 6, wherein a single record within the mapping table corresponds to a range of key values.

8. The computer system as recited in claim 6, further comprising an overlay table, wherein at least some of the first and second records inserted into the new level are modified based on entries in the overlay table.

9. The computer system as recited in claim 6, further comprising an overlay table, wherein at least some records of the group are elided from the new level based on entries in the overlay table.

10. The computer system as recited in claim 7, wherein at least one record corresponding to a range of key values in the group is replaced in the new level by a plurality of records corresponding to subranges of the at least one record.

11. The computer system as recited in claim 7, further comprising an overlay table, wherein at least one record in the group is replaced by a new record in the new level with a range smaller than that of the one record based on one or more entries in the overlay table.

12. The computer system as recited in claim 7, wherein a given plurality of records in the group are replaced by a single record in the new level whose range covers all ranges covered by the given plurality of records.

13. The computer system as recited in claim 1, wherein the data storage controller is further configured to replace the group of two or more adjacent levels with the new level.

14. The computer system as recited in claim 1, wherein the data storage controller is further configured to create a new level from fewer than all of the records in the group of two or more adjacent levels.

15. The computer system as recited in claim 1, wherein the flattening condition is based on at least one of a current or predicted value of:

a number of levels in the mapping table, a number of entries in one or more levels of the plurality of levels, a number of mapping entries that would be elided or modified as part of a flattening operation, and a load on the system.

16. The computer system as recited in claim 1, wherein the filtering condition is based at least in part on a current or predicted number of entries in the new level.

17. A method for use in a storage system, the method comprising:

storing a mapping table organized as a plurality of levels, each level of the plurality of levels comprising one or more mapping table entries, where each of the plurality of entries comprises a tuple including a key; and

responsive to detecting a flattening condition;

identifying a group of two or more levels of the plurality of levels which are logically adjacent in time;

creating a new level in the plurality of levels; and

inserting one or more first records stored within the group into the new level, in response to detecting each of the one or more first records stores a unique key among keys stored within the group;

utilizing a filtering condition to determine which of the first records are inserted into the new level, wherein the filtering condition comprises a validity of a given record as determined by an overlay table.

18. The method as recited in claim 17, wherein only a youngest level of the plurality of levels may be updated with new mapping table entries.

19. The method as recited in claim 17, wherein the data storage controller is further configured to sort records within the new level.

20. The method as recited in claim 17, wherein the mapping table entries within a level of the plurality of levels are sorted by key.

21. The method as recited in claim 17, further comprising performing flattening operations on the mapping table asynchronously with respect to updates to the mapping table.

22. The method as recited in claim 17, wherein in response to detecting the flattening condition, the method further comprises inserting one or more second records stored within the group into the new level, in response to detecting each of the one or more second records:

corresponds to two or more records storing a same non-unique key within the group; and

is in a youngest level containing a record with the non-unique key of the group.

23. The method as recited in claim 17, wherein a single record within the mapping table corresponds to a range of key values.

24. The method as recited in claim 17, wherein at least some of the first and second records inserted into the new level are modified based on entries in the overlay table.

25. The method as recited in claim 17, wherein at least some records of the group are elided from the new level based on entries in the overlay table.

26. The method as recited in claim 23, wherein at least one record corresponding to a range of key values in the group is replaced in the new level by a plurality of records corresponding to subranges of the at least one record.

27. The method as recited in claim 23, wherein at least one record in the group is replaced by a new record in the new level with a range smaller than that of the one record based on one or more entries in the overlay table.

28. The method as recited in claim 23, wherein a given plurality of records in the group are replaced by a single record in the new level whose range covers all ranges covered by the given plurality of records.

29. A non-transitory computer readable storage medium storing program instruction executable by a processor to:

store a mapping table organized as a plurality of levels, each level of the plurality of levels comprising one or more mapping table entries, where each of the plurality of entries comprises a tuple including a key; and

responsive to detecting a flattening condition;

identify a group of two or more levels of the plurality of levels which are logically adjacent in time;

create a new level in the plurality of levels;

insert one or more first records stored within the group into the new level, in response to detecting each of the one or more first records stores a unique key among keys stored within the group; and

utilize a filtering condition to determine which of the first records are inserted into the new level, wherein the filtering condition comprises a validity of a given record as determined by an overlay table.

30. The computer readable storage medium as recited in claim 29, wherein in response to detecting the flattening condition, the program instructions are further executable by a processor to insert one or more second records stored within the group into the new level, in response to detecting each of the one or more second records:

corresponds to two or more records storing a same non-unique key within the group; and

is in a youngest level containing a record with the non-unique key of the group.

31. The computer readable storage medium as recited in claim 29, wherein the plurality of levels of the mapping table are organized as time ordered levels.

32. The computer readable storage medium as recited in claim 29, wherein only a youngest level of the plurality of levels may be updated with new mapping table entries.

33. A computer system comprising:

a data storage medium;

a mapping table organized as a plurality of levels, each level of the plurality of levels comprising one or more mapping table entries, where each of the plurality of entries comprises a tuple including a key; and

a data storage controller coupled to the data storage medium;

wherein in response to detecting a flattening condition, the data storage controller is configured to;

identify a group of two or more levels of the plurality of levels which are logically adjacent in time;

create a new level in the plurality of levels;

insert one or more first records stored within the group into the new level, in response to detecting each of the one or more first records stores a unique key among keys stored within the group; and

insert one or more second records stored within the group into the new level, in response to detecting each of the one or more second records;

corresponds to two or more records storing a same non-unique key within the group; and

is in a youngest level containing a record with the non-unique key of the group;

wherein at least some of the first and second records inserted into the new level are modified based on entries in an overlay table.

34. A computer system comprising:

a data storage medium;

a mapping table organized as a plurality of levels, each level of the plurality of levels comprising one or more mapping table entries, where each of the plurality of entries comprises a tuple including a key; and

a data storage controller coupled to the data storage medium;

wherein in response to detecting a flattening condition, the data storage controller is configured to;

identify a group of two or more levels of the plurality of levels which are logically adjacent in time;

create a new level in the plurality of levels;

insert one or more first records stored within the group into the new level, in response to detecting each of the one or more first records stores a unique key among keys stored within the group; and

insert one or more second records stored within the group into the new level, in response to detecting each of the one or more second records;

corresponds to two or more records storing a same non-unique key within the group; and

is in a youngest level containing a record with the non-unique key of the group;

wherein a single record within the mapping table corresponds to a range of key values;

wherein at least one record corresponding to a range of key values in the group is replaced in the new level by a plurality of records corresponding to subranges of the at least one record.

35. A computer system comprising:

a data storage medium;

a mapping table organized as a plurality of levels, each level of the plurality of levels comprising one or more mapping table entries, where each of the plurality of entries comprises a tuple including a key; and

a data storage controller coupled to the data storage medium;

wherein in response to detecting a flattening condition, the data storage controller is configured to;

identify a group of two or more levels of the plurality of levels which are logically adjacent in time;

create a new level in the plurality of levels;

insert one or more first records stored within the group into the new level, in response to detecting each of the one or more first records stores a unique key among keys stored within the group; and

insert one or more second records stored within the group into the new level, in response to detecting each of the one or more second records;

corresponds to two or more records storing a same non-unique key within the group; and

is in a youngest level containing a record with the non-unique key of the group;

wherein at least one record in the group is replaced by a new record in the new level with a range smaller than that of the one record based on one or more entries in an overlay table.

36. A computer system comprising:

a data storage medium;

a mapping table organized as a plurality of levels, each level of the plurality of levels comprising one or more mapping table entries, where each of the plurality of entries comprises a tuple including a key; and

a data storage controller coupled to the data storage medium;

wherein in response to detecting a flattening condition, the data storage controller is configured to;

identify a group of two or more levels of the plurality of levels which are logically adjacent in time;

create a new level in the plurality of levels;

insert one or more first records stored within the group into the new level, in response to detecting each of the one or more first records stores a unique key among keys stored within the group; and

insert one or more second records stored within the group into the new level, in response to detecting each of the one or more second records;

corresponds to two or more records storing a same non-unique key within the group; and

is in a youngest level containing a record with the non-unique key of the group;

wherein a given plurality of records in the group are replaced by a single record in the new level whose range covers all ranges covered by the given plurality of records.

37. A computer system comprising:

a data storage medium;

a mapping table organized as a plurality of levels, each level of the plurality of levels comprising one or more mapping table entries, where each of the plurality of entries comprises a tuple including a key; and

a data storage controller coupled to the data storage medium;

wherein in response to detecting a flattening condition, the data storage controller is configured to;

identify a group of two or more levels of the plurality of levels which are logically adjacent in time;

create a new level in the plurality of levels;

insert one or more first records stored within the group into the new level, in response to detecting each of the one or more first records stores a unique key among keys stored within the group;

utilize a filtering condition to determine which of the first records are inserted into the new level, wherein the filtering condition is based at least in part on a current or predicted number of entries in the new level.