公开(公告)号：US11893273B2

公开(公告)日：2024-02-06

申请号：US17580154

申请日：2022-01-20

Applicant: VMware, Inc.

Inventor： Robert T. Johnson ,  Alexander John Horton Conway ,  Yi Xu ,  Aishwarya Ganesan ,  Ramnatthan Alagappan

IPC: G06F3/06

CPC classification number: G06F3/0656 ,  G06F3/0619 ,  G06F3/0679

Abstract: A method of writing to a tiered memory system of a computing device, the tiered memory system including volatile memory and persistent memory (PMEM), includes the steps of: in response to a first write request including first data to write to a first page of the tiered memory system, copying contents of the first page to a second page located in the PMEM; after copying the contents of the first page to the second page, writing the first data to the second page; and after writing the first data to the second page, updating a first mapping of the tiered memory system to reference the second page instead of the first page.

公开(公告)号：US11620261B2

公开(公告)日：2023-04-04

申请号：US16213815

申请日：2018-12-07

Applicant: VMware, Inc.

Inventor： Wenguang Wang ,  Richard P. Spillane ,  Junlong Gao ,  Robert T. Johnson ,  Christos Karamanolis ,  Maxime Austruy

IPC: G06F16/172 ,  G06F12/0891 ,  G06F16/901 ,  G06F16/174

Abstract: The disclosure herein describes writing data to a log-structured merge (LSM) tree file system on an object storage platform. Write data instructions indicating data for writing to the LSM tree file system are received. Based on the received instructions, the data is written to the first data cache. Based on an instruction to transfer data in the live data cache to the LSM tree file system, the first data cache is converted to a stable cache. A second data cache configured as a live data cache is then generated based on cloning the first data cache. The data in the first data cache is then written to the LSM tree file system. Use of a stable cache and a cloned live data cache enables parallel writing data to the file system by the stable cache and handling write data instructions by the live data cache.

公开(公告)号：US11093472B2

公开(公告)日：2021-08-17

申请号：US16213714

申请日：2018-12-07

Applicant: VMware, Inc.

Inventor： Richard P. Spillane ,  Wenguang Wang ,  Junlong Gao ,  Robert T. Johnson ,  Christos Karamanolis ,  Maxime Austruy

IPC: G06F16/00 ,  G06F16/22 ,  G06F16/84 ,  G06F16/13 ,  G06F16/2455

Abstract: The disclosure herein describes providing and accessing data on an object storage platform using a log-structured merge (LSM) tree file system. The LSM tree file system on the object storage platform includes sorted data tables, each sorted data table including a payload portion and an index portion. Data is written to the LSM tree file system in at least one new sorted data table. Data is ready by identifying a data location of the data based on index portions of the sorted data tables and reading the data from a sorted data table associated with the identified data location. The use of the LSM tree file system on the object storage platform provides an efficient means for interacting with the data stored thereon.

公开(公告)号：US11093471B2

公开(公告)日：2021-08-17

申请号：US16000142

申请日：2018-06-05

Applicant: VMware, Inc.

Inventor： Abhishek Gupta ,  Richard P. Spillane ,  Robert T. Johnson ,  Wenguang Wang ,  Kapil Chowksey ,  Jorge Guerra Delgado ,  Sandeep Rangaswamy ,  Srinath Premachandran

IPC: G06F17/00 ,  G06F16/22 ,  G06F7/16

Abstract: Embodiments herein are directed towards systems and methods for performing range lookups in Bε-trees. One example method involves receiving a request to return key-value pairs within a range of keys from the Bε-tree. The Bε-tree includes a plurality of nodes, each node being associated with a buffer that stores key-value pairs. The method further involves determining a fractional size of the range of keys. The method further involves, for each level of the Bε-tree, obtaining from within one or more buffers of one or more nodes of the level, a set of key-value pairs within the range of keys up to a size equal to the fractional size and transferring the set of key-value pairs to a result data structure. The method further involves sorting and merging all key-value pairs in the result data structure and returning the result data structure in response to the request.

公开(公告)号：US20200151268A1

公开(公告)日：2020-05-14

申请号：US16184861

申请日：2018-11-08

Applicant: VMware, Inc.

Inventor： Robert T. Johnson ,  Abhishek Gupta ,  Jorge Guerra Delgado ,  Ittai Abraham ,  Richard P. Spillane ,  Srinath Premachandran ,  Sandeep Rangaswamy ,  Kapil Chowksey

IPC: G06F17/30

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. When a compaction trigger condition exists, packet compaction is performed including a data element compaction operation. A buffer-emptying (flush) operation pushes the compacted packets to children nodes.

公开(公告)号：US11048678B2

公开(公告)日：2021-06-29

申请号：US16353535

申请日：2019-03-14

Applicant: VMware, Inc.

Inventor： Abhishek Gupta ,  Robert T. Johnson ,  Richard P. Spillane ,  Sandeep Rangaswamy ,  Jorge Guerra Delgado ,  Srinath Premachandran ,  Kapil Chowksey

IPC: G06F16/22 ,  G06F7/08 ,  G06F16/2455

Abstract: Embodiments described herein are related to bulk loading data into a B-tree. Embodiments include generating a first leaf node of a B-tree by allocating a first page for the first leaf node from a leaf page queue comprising a first plurality of sequential pages; and writing one or more tuples to the first page allocated for the first leaf node. Embodiments further include generating an parent node for the first leaf node and a second leaf node of the B-tree by allocating a third page for the parent node from an parent page queue comprising a second plurality of sequential pages, the parent node comprising a first indication of the first leaf node and a second indication of the second leaf node, the first indication and the second indication stored in the third page allocated for the parent.

公开(公告)号：US11487731B2

公开(公告)日：2022-11-01

申请号：US16931219

申请日：2020-07-16

Applicant: VMware, Inc.

Inventor： Abhishek Gupta ,  Richard P. Spillane ,  Robert T. Johnson ,  Srinath Premachandran ,  Jorge Guerra Delgado ,  Kapil Chowksey ,  Sandeep Rangaswamy

IPC: G06F15/16 ,  G06F16/22 ,  G06F16/23 ,  G06F9/54 ,  G06F9/50

Abstract: Embodiments described herein are related to a method of scanning a B-tree. For example, a method comprises receiving a scan request to scan a B-tree having a plurality of levels, each level comprising one or more nodes, wherein for each of one or more levels of the plurality of levels, nodes are grouped into groups, where nodes of any given group are stored across sequential disk blocks. The method further comprises generating a queue for each level of the B-tree. For each queue, the method further comprises loading into memory a next group of nodes based upon determining a storage location of a node of the next group of nodes.

公开(公告)号：US11176099B2

公开(公告)日：2021-11-16

申请号：US16231300

申请日：2018-12-21

Applicant: VMware, Inc.

Inventor： Wenguang Wang ,  Junlong Gao ,  Richard P. Spillane ,  Robert T. Johnson ,  Christos Karamanolis ,  Maxime Austruy

IPC: G06F16/178 ,  G06F16/18

Abstract: The disclosure herein describes synchronizing a data cache and an LSM tree file system on an object storage platform. Instructions to send a cached data set from the data cache to the LSM tree file system are received. An updated metadata catalog is generated. If the LSM tree structure is out of shape, compaction is performed on the LSM tree file system which may be on a different system or server. When an unmerged compacted metadata catalog is identified, a merged metadata catalog is generated, based on the compacted metadata catalog and the cached data set, and associated with the cached data set. The cached data set and the associated metadata catalog are sent to the LSM tree file system, whereby the data cache and the LSM tree file system are synchronized. Synchronization is enabled without the data cache or file system being locked and/or waiting for the other entity.

公开(公告)号：US11074225B2

公开(公告)日：2021-07-27

申请号：US16231246

申请日：2018-12-21

Applicant: VMware, Inc.

Inventor： Wenguang Wang ,  Richard P. Spillane ,  Junlong Gao ,  Robert T. Johnson ,  Christos Karamanolis ,  Maxime Austruy

IPC: G06F7/00 ,  G06F16/178 ,  G06F16/13 ,  G06F16/172 ,  G06F16/185

Abstract: The disclosure herein describes synchronizing cached index copies at a first site with indexes of a log-structured merge (LSM) tree file system on an object storage platform at a second site. An indication that the LSM tree file system has been compacted based on a compaction process is received. A cached metadata catalog of the included parent catalog version at the first site is accessed. A set of cached index copies is identified at the first site based on the metadata of the cached metadata catalog. The compaction process is applied to the identified set of cached index copies and a compacted set of cached index copies is generated at the first site, whereby the compacted set of cached index copies is synchronized with a respective set of indexes of the plurality of sorted data tables of the LSM tree file system at the second site.

公开(公告)号：US10983909B2

公开(公告)日：2021-04-20

申请号：US16252488

申请日：2019-01-18

Applicant: VMware, Inc.

Inventor： Abhishek Gupta ,  Robert T. Johnson ,  Richard P. Spillane ,  Sandeep Rangaswamy ,  Jorge Guerra Delgado ,  Kapil Chowksey ,  Srinath Premachandran

IPC: G06F12/0804 ,  G06F16/22 ,  G06F7/16 ,  G06F16/2455

Abstract: Certain aspects provide systems and methods for performing an operation on a Bε-tree. A method comprises writing a message associated with the operation to a first slot in a first buffer of a first non-leaf node of the Bε-tree in an append-only manner, wherein a first filter associated with the first slot is used for query operations associated with the first slot. The method further comprises determining that the first buffer is full and, upon determining to flush the message to a non-leaf child node, flushing the message in an append-only manner to a second slot in a second buffer of the non-leaf child node, wherein a second filter associated with the second slot is used for query operations associated with the second slot. The method further comprises, upon determining to flush the message to a leaf node, flushing the message to the leaf node in a sorted manner.