# US 2024/0256510 A1 · Distributed file system on top of a hybrid b-epsilon tree

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2024/0256510 A1
- Document ID: US20240256510A1
- Status: Published application
- Kind: A1
- Application number: 18/160,742
- Filed: 2023-01-27
- Published: 2024-08-01
- Earliest claimed: 2023-01-27
- Applicants: VMware, Inc.
- Inventors: Naama BEN DAVID; Aishwarya GANESAN; Jonathan HOWELL; Robert T. JOHNSON; Adriana SZEKERES
- Web page: https://patentgrep.com/patent/US20240256510A1

## CPC

- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/182: Distributed file systems
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A distributed file system operating over a plurality of hosts is built on top of a tree structure having a root node, internal nodes, and leaf nodes. Each host maintains at least one node and non-leaf nodes are allocated buffers according to a workload of the distributed file system. A write operation is performed by inserting write data into one of the nodes of the tree structure having a buffer. A read operation is performed by traversing the tree structure down to a leaf node that stores read target data, collecting updates to the read target data, which are stored in buffers of the traversed nodes, applying the updates to the read target data, and returning the updated read target data as read data.

## Claims

### Claim 1

A method for operating a distributed file system over a plurality of host computer systems, the method comprising:
forming a tree structure, the tree structure having a plurality of nodes including a root node at an uppermost level, internal nodes below the root node, and leaf nodes containing data items, each of the root node and the internal nodes including pivot keys and pointers to at least one child node or at least one leaf node, wherein each of the host computer systems maintains at least one of the nodes and non-leaf nodes are allocated buffers according to a workload of the distributed file system;
performing a write operation on a file in the distributed file system by inserting first data specified in the write operation as write data into one of the nodes of the tree structure having a buffer; and
performing a read operation on a file in the distributed file system by traversing the tree structure down to a leaf node that stores second data, collecting updates to the second data, which are stored in buffers of the nodes that are traversed, applying the collected updates to the second data, and returning the updated second data as read data.

### Claim 2 (depends on 1)

The method of claim 1, wherein the step of performing the write operation further includes:
traversing the tree structure using a key associated with a location in the distributed file system to which the first data is to be written; and
inserting a message that is associated with the key and contains the first data, into a highest node of the tree structure having a buffer that is traversed.

### Claim 3 (depends on 2)

The method of claim 2, wherein the tree structure is traversed according to a comparison of the key with pivot keys stored in each traversed node and the child pointers stored in each traversed node, each of the child pointers containing an identifier of one of the host computer systems.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
caching the traversed nodes locally in the host computer system that is performing the write operation.

### Claim 5 (depends on 2)

The method of claim 2, further comprising:
prior to inserting the message into a node that is the highest node of the tree structure having a buffer that is traversed, acquiring a lease to the node for the host computer system that is performing the write operation so that no other host computer system can access the node.

### Claim 6 (depends on 1)

The method of claim 1, wherein
the tree structure is traversed during the read operation using a key that is associated with a location in the distributed file system from which the read data is to be read, and
the tree structure is traversed according to a comparison of the key with pivot keys stored in each traversed node and the child pointers stored in each traversed node, each of the child pointers containing an identifier of one of the host computer systems.

### Claim 7 (depends on 6)

The method of claim 6, further comprising:
caching the traversed nodes locally in the host computer system that is performing the read operation.

### Claim 8 (depends on 1)

The method of claim 1, further comprising:
deallocating a buffer from a first non-leaf node of the tree structure and allocating a buffer to a second non-leaf node of the tree structure according to a policy that is based on workload behavior.

### Claim 9 (depends on 8)

The method of claim 8, wherein
the buffer previously allocated to the first non-leaf node is deallocated from the first non-leaf node in response to write contention on the first non-leaf node, and the second non-leaf node is one a plurality of non-leaf nodes that are allocated buffers in preparation for a bulk rename operation.

### Claim 10

A computer system comprising:
a plurality of host computer systems over which a distributed file system operates, the distributed file system including a file system in each of the host computer systems that coordinates with file systems of other host computer systems to maintain nodes of a tree structure, wherein the tree structure has a plurality of nodes including a root node at an uppermost level, internal nodes below the root node, and leaf nodes containing data items, each of the root node and the internal nodes including pivot keys and pointers to at least one child node or at least one leaf node, wherein non-leaf nodes are allocated buffers according to a workload of the distributed file system and each of the file systems is configured to:
perform a write operation on a file in the distributed file system by inserting first data specified in the write operation as write data into one of the nodes of the tree structure having a buffer; and
perform a read operation on a file in the distributed file system by traversing the tree structure down to a leaf node, collecting updates to the second data, which are stored in buffers of the nodes that are traversed, applying the collected updates to the second data, and returning the updated second data as read data.

### Claim 11 (depends on 10)

The computer system of claim 10, wherein each of the file systems is configured to perform the write operation by:
traversing the tree structure using a key associated with a location in the distributed file system to which the first data is to be written; and
inserting a message that is associated with the key and contains the first data, into a highest node of the tree structure having a buffer that is traversed.

### Claim 12 (depends on 11)

The computer system of claim 11, wherein the tree structure is traversed according to a comparison of the key with pivot keys stored in each traversed node and the child pointers stored in each traversed node, each of the child pointers containing an identifier of one of the host computer systems.

### Claim 13 (depends on 10)

The computer system of claim 10, wherein
the tree structure is traversed during the read operation using a key that is associated with a location in the distributed file system from which the read data is to be read, and
the tree structure is traversed according to a comparison of the key with pivot keys stored in each traversed node and the child pointers stored in each traversed node, each of the child pointers containing an identifier of one of the host computer systems.

### Claim 14 (depends on 10)

The computer system of claim 10, wherein
a buffer previously allocated to a first non-leaf node is deallocated from the first non-leaf node in response to write contention on the first non-leaf node, and a second non-leaf node is allocated a buffer in preparation for a bulk rename operation.

### Claim 15

A non-transitory computer readable medium comprising instructions executable in each of plurality of host computer systems, wherein the instructions, when executed in the host computer systems, cause the host computer systems to carry out a method of operating a distributed file system over the plurality of host computer systems, the method comprising:
forming a tree structure, the tree structure having a plurality of nodes including a root node at an uppermost level, internal nodes below the root node, and leaf nodes containing data items, each of the root node and the internal nodes including pivot keys and pointers to at least one child node or at least one leaf node, wherein each of the host computer systems maintains at least one of the nodes and non-leaf nodes are allocated buffers according to a workload of the distributed file system;
performing a write operation on a file in the distributed file system by inserting first data specified in the write operation as write data into one of the nodes of the tree structure having a buffer; and
performing a read operation on a file in the distributed file system by traversing the tree structure down to a leaf node that stores second data, collecting updates to the second data, which are stored in buffers of the nodes that are traversed, applying the collected updates to the second data, and returning the updated second data as read data.

### Claim 16 (depends on 15)

The non-transitory computer readable medium of claim 15, wherein the step of performing the write operation further includes:
traversing the tree structure using a key associated with a location in the distributed file system to which the first data is to be written; and
inserting a message that is associated with the key and contains the first data, into a highest node of the tree structure having a buffer that is traversed, wherein
the tree structure is traversed according to a comparison of the key with pivot keys stored in each traversed node and the child pointers stored in each traversed node, each of the child pointers containing an identifier of one of the host computer systems.

### Claim 17 (depends on 16)

The non-transitory computer readable medium of claim 16, wherein the method further comprises:
caching the traversed nodes locally in the host computer system that is performing the write operation.

### Claim 18 (depends on 15)

The non-transitory computer readable medium of claim 15, wherein
the tree structure is traversed during the read operation using a key that is associated with a location in the distributed file system from which the read data is to be read, and
the tree structure is traversed according to a comparison of the key with pivot keys stored in each traversed node and the child pointers stored in each traversed node, each of the child pointers containing an identifier of one of the host computer systems.

### Claim 19 (depends on 18)

The non-transitory computer readable medium of claim 18, wherein the method further comprises:
caching the traversed nodes locally in the host computer system that is performing the read operation.

### Claim 20 (depends on 16)

The non-transitory computer readable medium of claim 16, wherein
a buffer previously allocated to a first non-leaf node is deallocated from the first non-leaf node in response to write contention on the first non-leaf node, and a second non-leaf node is allocated a buffer in preparation for a bulk rename operation.
