Back to results
US 9,959,207 B2Granted
Log-structured B-tree for handling random writes
AssigneeVMware, Inc.
InventorsYunshan Lu, Wenguang Wang
Life of this patent
Estimating the term…
Abstract
A sorted key-value store is implemented using a write-back cache maintained in memory, a B-tree data structured maintained in disk, and a logical and physical log for providing transactions. The logical log and write-back cache are used to answer client requests, while dirty blocks in the write-back cache are periodically flushed to disk using the physical log.
Claims20
A method, comprising:
- receiving a file operation for a file system comprising a sorted key-value store, wherein the sorted key-value store comprises a write-back cache maintained in memory, a logical log, and a physical log maintained in disk;
- inserting a log entry indicating the file operation into the logical log, the log entry comprising a value, an address in disk, and an identifier of the file operation to perform for the value at the address;
- performing the file operation on the write-back cache maintained in memory after inserting the log entry indicating the file operation into the logical log;
- copying data blocks from the write-back cache into the physical log maintained in disk based on a state of the write-back cache;
- and
- updating a B-tree data structure stored on the disk using the data blocks in the physical log.
3 more elements
A non-transitory computer-readable storage medium comprising instructions that, when executed in a computing device, perform the steps of:
- receiving a file operation for a file system comprising a sorted key-value store, wherein the sorted key-value store comprises a write-back cache maintained in memory, a logical log, and a physical log maintained in disk;
- inserting a log entry indicating the file operation into the logical log, the log entry comprising a value, an address in disk, and an identifier of the file operation to perform for the value at the address;
- performing the file operation on the write-back cache maintained in memory after inserting the log entry indicating the file operation into the logical log;
- copying data blocks from the write-back cache into the physical log maintained in disk based on a state of the write-back cache;
- and
- updating a B-tree data structure stored on the disk using the data blocks in the physical log.
3 more elements
A computer system for allocating storage space, the computer system comprising:
- a storage device comprising a logical log, a physical log, and a B-tree data structure;
- a memory comprising a write-back cache associated with the B-tree data structure;
- a processor (CPU) configured to perform the steps of:
- receiving a file operation for a file system comprising a sorted key-value store, wherein the sorted key-value store comprises the write-back cache maintained in the memory, the logical log, and the physical log maintained in the storage device;
- inserting a log entry indicating the file operation into the logical log, the log entry comprising a value, an address in disk, and an identifier of the file operation to perform for the value at the address;
- performing the file operation on the write-back cache maintained in memory after inserting the log entry indicating the file operation into the logical log;
- copying data blocks from the write-back cache into the physical log maintained in disk based on a state of the write-back cache;
- and
- updating a B-tree data structure stored on the disk using the data blocks in the physical log.
6 more elements
Dependencies are inferred from the claim text.