Vmware, Inc.

Sandeep Rangaswamy

Jorge Guerra Delgado

Srinath Premachandran

Abhishek Gupta

Kapil Chowksey

Richard Paul Spillane

Wenguang Wang

Robert T Johnson

Rob T Johnson

Kiran R Joshi

Ittai Abraham

Pascal Renauld

Edward Joseph Goggin

Gopala Suryanarayana

Venkata Ramanan

Christos Karamanolis

Eric Shannon Knauft

Enning Xiang

Jin Zhang

Yiqi Xu

Xin Liang Li

Radu Berinde

Radhika Vullikanti

Aditya Kotwal

Brian Caulfield

Exemplary methods, apparatuses, and systems include a file system process obtaining locks on a first node and a second node in a tree structure, with the second node being a child node of the first node. The file system process determines a quantity of child nodes of the second. While holding the locks on the first and second nodes, the file system determines whether to proactively split or merge the second node. In response to determining that the quantity of child nodes is within a first range, the file system process splits the second node. If the file system process determines that the quantity of child nodes is within a second range, the file system process merges the second node.

Proactive splitting and merging of nodes in a B-tree

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for executing concurrent writes to a data store. One of the systems includes a data store comprising a plurality of storage segments, wherein each storage segment comprises a plurality of blocks; and an allocator system comprising: a plurality of threads, and a plurality of bitmaps each corresponding to a respective storage segment of the data store, wherein the allocator system is configured to perform operations comprising: assigning a respective bitmap to each thread of the plurality of threads; and executing, by each thread of the plurality of threads, one or more write requests to one or more blocks of the storage segment corresponding to the thread using the bitmap assigned to the thread, wherein executing a write request by a thread includes updating the bitmap assigned to the thread.

Highly concurrent data store allocation

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.

Reduced bandwidth queries in B e-trees using approximate membership query data structures

The disclosure herein describes tracking changes to a stale component using a synchronization bitmap. A first component of a plurality of mirrored components of the distributed data object becomes available from an unavailable state, and a stale log sequence number (LSN) and a last committed LSN are identified. A synchronization bitmap of the first component associated with a range of LSNs (e.g., from the stale LSN to the last committed LSN) is created and configured to track changes to data blocks of the first component. A second component is identified based on the second component including a tracking bitmap associated with an LSN that matches the stale LSN of the first component. The first component is synchronized with data from the second component based on, wherein the synchronizing includes updating the synchronization bitmap to track changes made to data blocks of the first component.

Synchronizing changes to stale components of a distributed object using synchronization bitmaps

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.

Range lookup operations for B-trees using update messages

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.

Read iterator for pre-fetching nodes of a B-tree into memory

Techniques for enabling deduplication-aware load balancing in a distributed storage system are provided. In one set of embodiments, a node of the distributed storage system can receive an I/O (Input/Output) request pertaining to a data block of a storage object stored on a local storage component of the node. The node can further determine whether the I/O request requires insertion of a new entry into a deduplication hash table associated with the local storage component or deletion of an existing entry from the deduplication hash table. If the I/O request requires insertion of a new hash table entry, the node can add an identifier of the data block into a probabilistic data structure associated with the local storage component, where the probabilistic data structure is configured to maintain information regarding distinct data blocks that are likely present in the local storage component. Alternatively, if the I/O request requires deletion of an existing hash table entry, the node can remove the identifier of the data block from the probabilistic data structure.

Deduplication-aware load balancing in distributed storage systems

Exemplary methods, apparatuses, and systems include a destination node receiving, from a source node, a hash of data stored by the source node and designated for transfer from the source node to the destination node. In response to determining the hash received from the source node maps to data stored by the destination node, the destination node reads the data into a write buffer and transmits an indication to the source node that the data is present at the source node. The destination node reads the data from write buffer and, in response to determining the data read from the write buffer remains unchanged as stored by the destination node, increases a reference count for the data as stored by the destination node.

Hash-based data transfer in distributed deduplication storage systems

Exemplary methods, apparatuses, and systems include a file system process determining to a flush a node in a first tree. The first node includes a buffer structured as a second tree. The file system process generates an input/output instruction to load the buffer from a first memory to a second memory. The second tree is stored in two more non-contiguous locations in the first memory and the input/output operation includes a read operation corresponding to each of the two or more non-contiguous locations. The file system process causes the input/output instruction to be executed concurrently on the first memory.

Optimizing operations on b e-trees stored on solid state media

In accordance with the present disclosure, files may be deduplicated in a distributed storage system having a plurality of storage volumes. A uniqueness metric for each file may indicate a degree of deduplication of the respective data files in the given storage volume. The uniqueness metric may be used to identify files for rebalancing in the distributed storage system. The uniqueness metric may be efficiently calculated with enough accuracy using a sampling methodology.

File granular data de-duplication effectiveness metric for data de-duplication

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.

Large range lookups for B-tree

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.

Bounding cost of flushes in buffer trees

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.

Bulk-load for B-trees

Embodiments described herein involve improved management of snapshots of a file system. Embodiments include copying a first root node of a first snapshot to a second snapshot, the second snapshot referencing other nodes of the first snapshot. Embodiments further include incrementing reference counts of the other nodes of the first snapshot. Embodiments further include adding a storage address of the first root node to a list. Embodiments further include, each time that a copy on write operation is performed for a node of the other nodes, adding a storage address of the node to the list and decrementing the reference count of the node. Embodiments further include iterating through the list and, for each storage address in the list, decrementing the reference count of the node corresponding to the storage address and, if the reference count of the node reaches zero, freeing storage space at the storage address.

Optimal snapshot deletion

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.

Growing community of inventors

Mountain View, CA, United States of America

Sandeep Rangaswamy