公开(公告)号：US20190228096A1

公开(公告)日：2019-07-25

申请号：US15878341

申请日：2018-01-23

Applicant: VMware, Inc.

Inventor： Wenguang Wang ,  Abhishek Gupta ,  Kapil Chowksey ,  Richard P. Spillane ,  Rob Johnson

IPC: G06F17/30 ,  G06F11/14

Abstract: Data storage system and method for managing transaction requests in the data storage system utilizes prepare requests for a transaction request for multiple data storage operations. The prepare requests are sent to selected destination storage nodes of the data storage system to handle the multiple data storage operations. Each prepare request includes at least one of the multiple data storage operations to be handled by a particular destination data store node and a list of the destination storage nodes involved in the transaction request.

公开(公告)号：US20190188098A1

公开(公告)日：2019-06-20

申请号：US15844539

申请日：2017-12-16

Applicant: VMware, Inc.

Inventor： Abhishek Gupta ,  Jorge Guerra Delgado ,  Kapil Chowksey ,  Sandeep Rangaswamy ,  Srinath Premachandran

IPC: G06F11/20 ,  G06F3/06

CPC classification number: G06F11/2069 ,  G06F3/065 ,  G06F3/067 ,  G06F11/2082 ,  G06F2201/84

Abstract: The subject matter described herein is generally directed towards tracking and recovering a disk allocation state. An on-disk log of operations is maintained to describe operations performed to an in-memory partial reference count map. Upon a crash of a host computing device during a checkpoint operation to an on-disk complete reference count map, the on-disk log of operations is used to undo and then redo the operations, or just redo the operations. In this manner, a disk allocation state prior to the crash is recreated in the on-disk complete reference count map with atomicity and crash consistency.

公开(公告)号：US20190095457A1

公开(公告)日：2019-03-28

申请号：US15717613

申请日：2017-09-27

Applicant: VMware, Inc.

Inventor： Abhishek Gupta ,  Richard P Spillane ,  Kapil Chowksey ,  Wenguang Wang ,  Robert T Johnson

IPC: G06F17/30 ,  G06F7/16

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.

公开(公告)号：US11507553B2

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

申请号：US15927019

申请日：2018-03-20

Applicant: VMware, Inc.

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

IPC: G06F16/22 ,  G06F16/17 ,  G06F16/23 ,  G06F16/2453 ,  G06F16/2455

Abstract: Exemplary methods, apparatuses, and systems include a file system process inserting a first key/value pair and a second key/value pair into a first tree. The second key is a duplicate of the first key and the value of the second key/value pair is an operation changing the value. In response to a request for a range of key/value pairs, the process reads the second key/value pair and inserts it in a second tree. The process reads the first pair and determines, while inserting the first pair in the second tree, that the second key is a duplicate of the first key. The file system process determines an updated value of the first value by applying the operation in the second value to first value. The file system operation updates the second key/value pair in the second tree with the updated value and returns the requested range of key/value pairs.

公开(公告)号：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.

公开(公告)号：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.

公开(公告)号：US10824610B2

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

申请号：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: G06F16/30 ,  G06F16/22 ,  G06F16/23

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.

公开(公告)号：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.

公开(公告)号：US10452496B2

公开(公告)日：2019-10-22

申请号：US15727211

申请日：2017-10-06

Applicant: VMware, Inc.

Inventor： Abhishek Gupta ,  Richard P. Spillane ,  Kapil Chowksey ,  Rob Johnson ,  Wenguang Wang

IPC: G06F11/14 ,  G06F16/23

Abstract: Data storage system and method for managing transaction requests to the data storage system utilizes a write ahead log to write transaction requests received at the data storage system during a current checkpoint generation. After the transaction requests in the write ahead log are applied to a copy-on-write (COW) storage data structure stored in a storage system, one of first and second allocation bitmaps is updated to reflect changes in the COW storage data structure with respect to allocation of storage space in the storage system, and one of first and second super blocks is updated with references to central nodes of the COW storage data structure. After the allocation bitmap and the super block have been updated, an end indicator for the current checkpoint generation is written in the write ahead log to indicate that processing of the transaction requests for the current checkpoint generation has been completed.

公开(公告)号：US11720568B2

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

申请号：US15927016

申请日：2018-03-20

Applicant: VMware, Inc.

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

IPC: G06F16/17 ,  G06F16/2455 ,  G06F16/22 ,  G06F16/2453

CPC classification number: G06F16/24553 ,  G06F16/17 ,  G06F16/2246 ,  G06F16/24534

Abstract: Exemplary methods, apparatuses, and systems include a file system process reading a first node in a tree data structure from a first memory. The first node includes a first approximate membership query data structure (“AMQ”), a first plurality of child pointers, a first plurality of pivot values, and a first buffer. The file system process determines that the first plurality of child pointers exceeds a maximum size. Using a pivot value in the first plurality of pivot values, the file system process splits the first node into a second node and a third node. The file system process uses the pivot value to split the first buffer into a second buffer and a third buffer. Using the pivot value and the first AMQ, the file system process generates a second AMQ and a third AMQ.