公开(公告)号：US10909102B2

公开(公告)日：2021-02-02

申请号：US16212550

申请日：2018-12-06

Applicant: VMware, Inc.

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

IPC: G06F16/00 ,  G06F16/22 ,  H03M7/30

Abstract: Certain aspects provide systems and methods of compacting data within a log-structured merge tree (LSM tree) using sharding. In certain aspects, a method includes determining a size of the LSM tree, determining a compaction time for a compaction of the LSM tree based on the size, determining a number of compaction entities for performing the compaction in parallel based on the compaction time, determining a number of shards based on the number of compaction entities, and determining a key range associated with the LSM tree. The method further comprises dividing the key range by the number of shards into a number of sub key ranges, wherein each of the number of sub key ranges corresponds to a shard of the number of shards and assigning the number of shards to the number of compaction entities for compaction.

公开(公告)号：US20200183906A1

公开(公告)日：2020-06-11

申请号：US16213714

申请日：2018-12-07

Applicant: VMware, Inc.

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

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

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.

公开(公告)号：US20200183886A1

公开(公告)日：2020-06-11

申请号：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 ,  G06F16/174 ,  G06F16/901 ,  G06F12/0891

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.

公开(公告)号：US20200089788A1

公开(公告)日：2020-03-19

申请号：US16134564

申请日：2018-09-18

Applicant: VMware, Inc.

Inventor： Robert T. Johnson ,  Ittai Abraham ,  Abhishek Gupta ,  Richard P. Spillane ,  Srinath Premachandran ,  Jorge Guerra Delgado ,  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.