Reducing write amplification in buffer trees

Patent metadata

Field	Value
Publication number	US-10997144-B2
Application number	US-201816029463-A
Country	US
Kind code	B2
Filing date	Jul 6, 2018
Priority date	Jul 6, 2018
Publication date	May 4, 2021
Grant date	May 4, 2021

Abstract

A buffer tree structure includes, at each internal node, a buffer having a compacted portion and an uncompacted portion. Insertion of data elements to the buffer tree can occur units called packets. A packet is initially stored in the uncompacted portion of a receiving node's buffer. After a time, packets in the uncompacted portion of a buffer are combined into compacted packets in the compacted portion of the buffer. A buffer-emptying (flush) operation pushes the compacted packets to children nodes.

First claim

The invention claimed is:

1. A method comprising:
providing a buffer tree in a memory of a computer, the buffer tree comprising a plurality of nodes including a root node and a plurality of child nodes descending from the root node, wherein each of the plurality of nodes comprising a respective buffer, wherein the respective buffer comprising a respective compacted portion and a respective uncompacted portion, wherein the respective uncompacted portion having stored therein one or more respective pointers, wherein each pointer of the one or more respective pointers is pointing to a respective data;
receiving, by the computer, a pointer that points to a data;
adding, by the computer, the received pointer to the one more respective pointers in the uncompacted portion of the buffer of the root node to produce a plurality of pointers; and
when an amount of data pointed to by the plurality of pointers in the uncompacted portion of the buffer of the root node exceeds a predetermined limit, the computer:
accessing the data pointed to by the plurality of pointers in the uncompacted portion of the buffer of the root node;
combining the accessed data; and
storing the combined data among one or more compacted packets in the compacted portion of the buffer in the root node, including writing the one or more compacted packets to a data storage device separate from the memory of the computer.

2. The method of claim 1 , further comprising flushing at least one of the one or more compacted packets to a child node of the root node by storing a pointer to at least one of the one or more compacted packets in the root node into an uncompacted portion of a buffer of the child node.

3. The method of claim 2 , wherein storing a pointer to the compacted packet in an uncompacted portion of a buffer of the child node does not include writing data comprising the compacted packet to the data storage device.

4. The method of claim 1 , wherein the combining comprises:
producing a sorted list of the data pointed to by the plurality of pointers that is sorted according to keys associated with the data; and
dividing the sorted list into the one or more compacted packets according to key ranges associated with children of the root node.

5. The method of claim 1 , wherein the data pointed to by the received pointer comprises a plurality of data elements, wherein each data element comprises a value and an associated key that is used to index the value, wherein a key in a first data element in a first uncompacted packet and is also with a key in a second data element in a second uncompacted packet, wherein keys associated with data elements in a compacted packet are unique to that compacted packet.

6. The method of claim 1 , wherein the predetermined limit is a total size of the buffer of the root node.

7. A non-transitory computer-readable storage medium having stored thereon computer executable instructions, which when executed by a computer device, cause the computer device to:
provide a buffer tree in a memory of the computer device, the buffer tree comprising a plurality of nodes including a root node and a plurality of child nodes descending from the root node, wherein each of the plurality of nodes comprising a respective buffer, wherein the respective buffer comprising a respective compacted portion and a respective uncompacted portion, wherein the respective uncompacted portion having stored therein one or more respective pointers, wherein each pointer of the one or more respective pointers is pointing to a respective data;
receive a pointer that points to a data;
add the received pointer to the one or more respective pointers in the uncompacted portion of the buffer of the root node to produce a plurality of pointers; and
when an amount of data represented by the plurality of pointers in the uncompacted portion of the buffer of the root node exceeds a predetermined limit, then:
accessing the data pointed to by the plurality of pointers in the uncompacted portion of the buffer of the root node;
combining the accessed data; and
storing the combined data among one or more compacted packets in the compacted portion of the buffer in the root node, including writing the one or more compacted packets to a data storage device separate from the memory of the computer device.

8. The non-transitory computer-readable storage medium of claim 7 , wherein the computer executable instructions, which when executed by the computer device, further cause the computer device to flush at least one of the one or more compacted packets to a child node of the root node by storing a pointer to at least one of the one or more compacted packets in the root node into an uncompacted portion of a buffer of the child node.

9. The non-transitory computer-readable storage medium of claim 8 , wherein the computer device stores a pointer to the compacted packet in an uncompacted portion of a buffer of the child node without writing the data elements comprising the compacted packet to the data storage device.

10. The non-transitory computer-readable storage medium of claim 7 , wherein the computer executable instructions, which when executed by the computer device, further cause the computer device to:
produce a sorted list of the data pointed to by the plurality of pointers that is sorted according to keys associated with the data; and
divide the sorted list into the one or more compacted packets according to key ranges associated with children of the root node.

11. 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:
provide a buffer tree in a memory of the apparatus, the buffer tree comprising a plurality of nodes including a root node and a plurality of child nodes descending from the root node, wherein each of the plurality of nodes comprising a respective buffer, wherein the respective buffer comprising a respective compacted portion and a respective uncompacted portion, wherein the respective uncompacted portion having stored therein one or more respective pointers, wherein each pointer of the one or more respective pointers is pointing to a respective data;
receive a pointer that points to a data;
add the received pointer to the one or more respective pointers in the uncompacted portion of the buffer of the root node to produce a plurality of pointers; and
when an amount of data pointed to by the plurality of pointers in the uncompacted portion of the buffer of the root node exceeds a predetermined limit, then:
accessing the data pointed to by the plurality of pointers in the uncompacted portion of the buffer of the root node;
combining the accessed data; and
storing the combined data among one or more compacted packets in the compacted portion of the buffer in the root node, including writing the one or more compacted packets to a data storage device separate from the memory of the apparatus.

12. The apparatus of claim 11 , wherein the computer-readable storage medium further comprises instructions for controlling the one or more computer processors to be operable to flush at least one of the one or more compacted packets to a child node of the root node by storing a pointer to at least one of the one or more compacted packets in the root node into an uncompacted portion of a buffer of the child node.

13. The apparatus of claim 12 , wherein the one or more computer processors store a pointer to the at least one of the one or more compacted packet in an uncompacted portion of a buffer of the child node without writing the data comprising the compa

Assignees

• Vmware Inc

Inventors

• Johnson Robert T
• Abraham Ittai
• Gupta Abhishek
• Spillane Richard P
• Rangaswamy Sandeep
• Guerra Delgado Jorge
• Premachandran Srinath
• Chowksey Kapil

Classifications

• G06F16/24552

  Database cache management · CPC title

• G06F16/2282 Primary

  Tablespace storage structures; Management thereof · CPC title

• G06F16/2246 Primary

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

• G06F16/2379

  Updates performed during online database operations; commit processing · CPC title