Mapper tree with super leaf nodes

Patent metadata

Field	Value
Publication number	US-11068455-B2
Application number	US-201916395887-A
Country	US
Kind code	B2
Filing date	Apr 26, 2019
Priority date	Apr 26, 2019
Publication date	Jul 20, 2021
Grant date	Jul 20, 2021

Abstract

A mapper tree for a logical volume is provided by storing, in each leaf node of the mapper tree, pointers to pages of non-volatile storage that store host data written to corresponding pages within a segment of the logical address space of the logical volume that corresponds to the leaf node. In response to receiving an initial write operation directed to a segment of the logical address space of the logical volume for which no leaf node currently exists in the mapper tree, a representation of a new leaf node is added to a super leaf node in the mapper tree that efficiently stores representations of multiple leaf nodes.

First claim

What is claimed is:

1. A method of providing a mapper tree for a logical volume, comprising:
storing, in each leaf node of the mapper tree, pointers to pages of non-volatile storage that store host data written to pages within a corresponding segment of a logical address space of the logical volume;
in response to receiving an initial write operation directed to a segment of the logical address space of the logical volume for which no corresponding leaf node exists in the mapper tree, adding a new leaf node corresponding to that segment of the logical address space to a super leaf node in the mapper tree that stores multiple leaf nodes; and
in response to detecting that an amount of available space within the super leaf node is less than a minimum threshold,
identifying a representation of a leaf node contained in the super leaf node that includes a larger number of pointers to pages of non-volatile storage than any other representation of a leaf node in the super leaf node, and
removing, from the super leaf node, the representation of the leaf node in the super leaf node that includes a larger number of pointers to pages of non-volatile storage than any other representation of a leaf node contained in the super leaf node.

2. The method of claim 1 , further comprising:
wherein the super leaf node includes multiple slots, each slot in the super leaf node containing a representation of a leaf node that is contained in the super leaf node; and
wherein adding the new leaf node to the super leaf node includes adding a representation of the new leaf node to the super leaf node.

3. The method of claim 2 , wherein adding the representation of the new leaf node to the super leaf node includes adding a pointer to a page of non-volatile storage to the representation of the new leaf node within the super leaf node, wherein the page of non-volatile storage is used to store host data indicated by the initial write operation.

4. The method of claim 3 , wherein adding the pointer to the page of non-volatile storage that stores the host data indicated by the initial write operation to the representation of the new leaf node within the super leaf node includes storing a tuple in the representation of the new leaf node, the tuple indicating both the pointer to the page of non-volatile storage used to store the host data indicated by the initial write operation and an offset of the page to which the initial write operation was directed within the segment of the logical address space of the logical volume corresponding to the new leaf node.

5. The method of claim 1 , wherein detecting that an amount of available space within the super leaf node is less than a minimum threshold is performed responsive to attempting to add a pointer to a page of non-volatile storage to the super leaf node.

6. The method of claim 1 , further comprising:
in response to detecting that a representation of a leaf node contained in the super leaf node includes a number of pointers to pages of non-volatile storage that exceeds a maximum threshold, removing, from the super leaf node, the representation of the leaf node in the super leaf node that includes a number of pointers to pages of non-volatile storage that exceeds the maximum threshold.

7. The method of claim 6 , wherein detecting that a representation of a leaf node contained in the super leaf node includes a number of pointers to pages of non-volatile storage that exceeds a maximum threshold comprises detecting that the representation of the leaf node in the super leaf node includes a number of pointers to pages of non-volatile storage that exceeds a predetermined maximum percentage of a maximum number of pointers to pages of non-volatile storage that can be contained in a leaf node.

8. The method of claim 1 , further comprising:
in response to detecting that no super leaf node exists in the mapper tree to store the new leaf node, adding a new super leaf node to the mapper tree prior to adding the new leaf node to the new super leaf node.

9. A data storage system, comprising:
processing circuitry and memory coupled to the processing circuitry, the memory storing instructions for providing a mapper tree for a logical volume, wherein the instructions, when executed by the processing circuitry, cause the processing circuitry to:
store, in each leaf node of the mapper tree, pointers to pages of non-volatile storage that store host data written to pages within a corresponding segment of a logical address space of the logical volume,
in response to receiving an initial write operation directed to a segment of the logical address space of the logical volume for which no corresponding leaf node exists in the mapper tree, add a new leaf node corresponding to that segment of the logical address space to a super leaf node in the mapper tree that stores multiple leaf nodes; and
in response to detecting that an amount of available space within the super leaf node is less than a minimum threshold,
identify a representation of a leaf node contained in the super leaf node that includes a larger number of pointers to pages of non-volatile storage than any other representation of a leaf node in the super leaf node, and
remove, from the super leaf node, the representation of the leaf node in the super leaf node that includes a larger number of pointers to pages of non-volatile storage than any other representation of a leaf node contained in the super leaf node.

10. The data storage system of claim 9 , further comprising:
wherein the super leaf node includes multiple slots, each slot in the super leaf node containing a representation of a leaf node that is contained in the super leaf node; and
wherein the instructions, when executed, cause the processing circuitry to add the new leaf node to the super leaf node at least in part by causing the processing circuitry to add a representation of the new leaf node to the super leaf node.

11. The data storage system of claim 10 , wherein the instructions, when executed, cause the processing circuitry to add the representation of the new leaf node to the super leaf node at least in part by causing the processing circuitry to add a pointer to a page of non-volatile storage to the representation of the new leaf node within the super leaf node, wherein the page of non-volatile storage is used to store host data indicated by the initial write operation.

12. The data storage system of claim 11 , wherein the instructions, when executed, cause the processing circuitry to add the pointer to the page of non-volatile storage that stores the host data indicated by the initial write operation to the representation of the new leaf node within the super leaf node at least in part by causing the processing circuitry to store a tuple in the representation of the new leaf node, the tuple indicating both the pointer to the page of non-volatile storage used to store the host data indicated by the initial write operation and an offset of the page to which the initial write operation was directed within the segment of the logical address space of the logical volume corresponding to the new leaf node.

13. The data storage system of claim 9 , wherein the instructions, when executed, further cause the processing circuitry to detect that the amount of available space within the super leaf node is less than the minimum threshold responsive to an attempt to add a pointer to a page of non-volatile storage to the super leaf node.

14. The data storage system of claim 9 , wherein the instructions, when executed, further cause the processing circuitry to:
detect that a representation of a leaf node contained in the super

Assignees

• Emc Ip Holding Co Llc

Inventors

• Shabi Uri
• Zalstein Dror
• Gazit Ronen
• Shveidel Vladimir

Classifications

• G06F16/2228

  Indexing structures · CPC title

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title