Write-optimized nested trees

Patent metadata

Field	Value
Publication number	US-10649959-B2
Application number	US-201715717613-A
Country	US
Kind code	B2
Filing date	Sep 27, 2017
Priority date	Sep 27, 2017
Publication date	May 12, 2020
Grant date	May 12, 2020

Abstract

A Bε-tree associated with a file system on a storage volume includes a hierarchy of nodes. Each node includes a buffer portion that can be characterized by a fixed maximum allowable size to store key-value pairs as messages in the buffer. Messages can be initially buffered in the root node of the Bε-tree, and flushed to descendent children from the root node. Messages stored in the buffers can be indexed using a B+-tree data structure. As the B+-tree data structure in a buffer grows (due to receiving flushed messages) and shrinks (due to messages being flushed), disk blocks can be allocated from the storage volume to increase the actual size of the buffer and deallocated from the buffer to reduce the actual size of the buffer.

First claim

The invention claimed is:

1. A method for a file system on a storage volume, the method comprising:
receiving an insert operation comprising a key and a value to be stored in a tree data structure of the file system, the tree data structure comprising a plurality of nodes organized in a hierarchy, each node having a buffer to store key-value pairs in a B + -tree data structure comprising disk blocks allocated from the storage volume and characterized by a predetermined maximum buffer size;
adding the received key and value as a key-value pair to the B + -tree in a root node of the tree data structure; and
moving one or more key-value pairs from the B + -tree in the root node to a B + -tree in a child node of the root node when an amount of data stored in the B + -tree of the root node is greater than the predetermined maximum buffer size, including allocating one or more disk blocks to the buffer of the child node as needed to store the one or more key-value pairs in the B + -tree of the child node,
wherein moving the one or more key-value pairs from the B + -tree in the root node to the B + -tree in the child node comprises:
producing a combined list of key-value pairs comprising the one or more key-value pairs from the B + -tree in the root node and key-value pairs in the B + -tree of the child node; and
rebuilding the B + -tree in the child node using the combined list of key-value pairs.

2. The method of claim 1 , further comprising:
moving one or more key-value pairs from the B + -tree in the child node to the B + -tree in a descendent child node when the amount of data stored in the buffer of the child node is greater than the predetermined maximum buffer size; and
deallocating any disk blocks comprising the buffer in the child node that become unused as a result of moving the one or more key-value pairs from the B + -tree in the child node to the B + -tree in the descendent child node.

3. The method of claim 1 , further comprising performing a sorting operation of the one or more key-value pairs from the B + -tree in the root node and the key-value pairs in the B + -tree of the child node to produce the combined list of key-value pairs.

4. The method of claim 3 , wherein the sorting operation is a merge sort operation.

5. The method of claim 1 , wherein rebuilding the B + -tree in the child node comprises bulk loading key-value pairs from the combined list of key-value pairs into the B + -tree.

6. The method of claim 1 , wherein rebuilding the B + -tree in the child node includes loading its leaf nodes with key-value pairs from the combined list of key-value pairs such that at least all the leaf nodes other than a last leaf node are completely filled with key-value pairs.

7. The method of claim 1 , wherein rebuilding the B + -tree in the child node includes re-using disk blocks already allocated to the B + -tree.

8. The method of claim 1 , further comprising deallocating any disk blocks comprising the buffer of the root node that become unused as a result of moving the one or more key-value pairs from the B+-tree in the root node to the B+-tree in the child node.

9. A non-transitory computer-readable storage medium having stored thereon computer executable instructions, which when executed by a processor, cause the processor to:
receive an insert operation comprising a key and a value to be stored in a tree data structure of the file system, the tree data structure comprising a plurality of nodes organized in a hierarchy, each node having a buffer to store key-value pairs in a B + -tree data structure comprising disk blocks allocated from the storage volume and characterized by a predetermined maximum buffer size;
add the received key and value as a key-value pair to the B + -tree in a root node of the tree data structure; and
move one or more key-value pairs from the B + -tree in the root node to a B + -tree in a child node of the root node when an amount of data stored in the B + -tree of the root node is greater than the predetermined maximum buffer size, including allocating one or more disk blocks to the buffer of the child node as needed to store the one or more key-value pairs in the B + -tree of the child node,
wherein moving the one or more key-value pairs from the B + -tree in the root node to the B + -tree in the child node comprises:
producing a combined list of key-value pairs comprising the one or more key-value pairs from the B + -tree in the root node and key-value pairs in the B + -tree of the child node; and
rebuilding the B + -tree in the child node using the combined list of key-value pairs.

10. The non-transitory computer-readable storage medium of claim 9 , wherein the computer executable instructions, which when executed by the processor, further cause the processor to:
move one or more key-value pairs from the B + -tree in the child node to the B + -tree in a descendent child node when the amount of data stored in the buffer of the child node is greater than the predetermined maximum buffer size; and
deallocate any disk blocks comprising the buffer in the child node that become unused as a result of moving the one or more key-value pairs from the B + -tree in the child node to the B + -tree in the descendent child node.

11. The non-transitory computer-readable storage medium of claim 10 , wherein the computer executable instructions, which when executed by the processor, further cause the processor to perform a merge sort of the one or more key-value pairs from the B + -tree in the root node and the key-value pairs in the B + -tree of the child node to produce the combined list of key-value pairs.

12. The non-transitory computer-readable storage medium of claim 10 , wherein rebuilding the B + -tree in the child node comprises bulk loading key-value pairs from the combined list of key-value pairs into the B + -tree.

13. An apparatus comprising:
one or more computer processors; and
a computer-readable storage medium comprising instructions for controlling the one or more computer processors to be operable to:
receive an insert operation comprising a key and a value to be stored in a tree data structure of the file system, the tree data structure comprising a plurality of nodes organized in a hierarchy, each node having a buffer to store key-value pairs in a B + -tree data structure comprising disk blocks allocated from the storage volume and characterized by a predetermined maximum buffer size;
add the received key and value as a key-value pair to the B + -tree in a root node of the tree data structure; and
move one or more key-value pairs from the B + -tree in the root node to a B + -tree in a child node of the root node when an amount of data stored in the B + -tree of the root node is greater than the predetermined maximum buffer size, including allocating one or more disk blocks to the buffer of the child node as needed to store the one or more key-value pairs in the B + -tree of the child node,
wherein moving the one or more key-value pairs from the B + -tree in the root node to the B + -tree in the child node comprises:
producing a combined list of key-value pairs comprising the one or more key-value pairs from the B + -tree in the root node and key-value pairs in the B + -tree of the child node; and
rebuilding the B + -tree in the child node using the combined list of key-value pairs.

14. The apparatus of claim 13 , wherein the tree data structure is a B ε -tree.

15. The apparatus of claim 13 , wherein the computer-readable storage medium further comprises instructions for controlling the one or more computer processors to be operable to:
move one or more k

Assignees

• Vmware Inc

Inventors

• Gupta Abhishek
• Spillane Richard P
• Chowksey Kapil
• Wang Wenguang
• Johnson Robert T

Classifications

• G06F16/185

  Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof (details of archiving G06F16/11) · CPC title

• G06F16/1727

  Details of free space management performed by the file system (saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064) · CPC title

• G06F16/2246

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

• G06F16/13 Primary

  File access structures, e.g. distributed indices (arrangements of input from, or output to, record carriers G06F3/06) · CPC title

• G06F7/16

  Combined merging and sorting · CPC title