Log-structured B-tree for handling random writes

• US 9,959,207 B2
• Filed: 06/25/2015
• Issued: 05/01/2018
• Est. Priority Date: 06/25/2015
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Lu, Yunshan, Wang, Wenguang
• Primary Examiner(s): Cygiel, Gary W.
• Application Number:
  US14/750,554
• Publication Number:
  US 20160378653A1
• Time in Patent Office: 1,041 Days
• Field of Search: None
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 2212/463 File
• CPC Class Codes: G06F 2212/466 Metadata, control data

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.

Claims

1. 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.

2. The method of claim 1, wherein the file operation comprises a write operation, and wherein performing the file operation on the write-back cache comprises generating modified blocks in the write-back cache.

3. The method of claim 1, wherein copying data blocks from the write-back cache into the physical log maintained in disk based on a state of the write-back cache is performed responsive to determining that the write-back cache has exceeded a threshold amount of modified blocks.

4. The method of claim 1, wherein copying data blocks from the write-back cache into the physical log maintained in disk based on a state of the write-back cache further comprises:

writing a first physical log entry comprising the modified blocks to the physical log; and

writing a second physical log entry indicating a commit operation to the physical log.

5. The method of claim 4, further comprising:

responsive to writing to second physical log entry indicating the commit operation to the physical log, updating a data block on disk using the first physical log entry in the physical log.

6. The method of claim 1, wherein the file operation comprises a read operation, and wherein performing the file operation on the write-back cache comprises retrieving data from the write-back cache and not from the disk.

7. The method of claim 1, further comprising:

performing a bootstrap procedure subsequent to a system failure, the bootstrap procedure comprising;

retrieving one or more un-played physical log entries from the physical log;

replaying the physical log entries into the write-back cache maintained in memory;

retrieving one or more un-replayed logical log entries from the logical log; and

replaying the logical log entries into the write-back cache maintained in memory.

8. 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.

9. The non-transitory computer-readable storage medium of claim 8, wherein the file operation comprises a write operation, and wherein performing the file operation on the write-back cache comprises generating modified blocks in the write-back cache.

10. The non-transitory computer-readable storage medium of claim 8, wherein copying data blocks from the write-back cache into the physical log maintained in disk based on a state of the write-back cache is performed responsive to determining that the write-back cache has exceeded a threshold amount of modified blocks.

11. The non-transitory computer-readable storage medium of claim 8, wherein copying data blocks from the write-back cache into the physical log maintained in disk based on a state of the write-back cache further comprises:

writing a first physical log entry comprising the modified blocks to the physical log; and

writing a second physical log entry indicating a commit operation to the physical log.

12. The non-transitory computer-readable storage medium of claim 11, wherein the steps further comprise:

responsive to writing to second physical log entry indicating the commit operation to the physical log, updating a data block on disk using the first physical log entry in the physical log.

13. The non-transitory computer-readable storage medium of claim 8, wherein the file operation comprises a read operation, and wherein performing the file operation on the write-back cache comprises retrieving data from the write-back cache and not from the disk.

14. The non-transitory computer-readable storage medium of claim 8, wherein the steps further comprise:

performing a bootstrap procedure subsequent to a system failure, the bootstrap procedure comprising;

retrieving one or more un-replayed logical log entries from the logical log; and

replaying the logical log entries into the write-back cache maintained in memory.

15. 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.

16. The computer system of claim 15, wherein the file operation comprises a write operation, and wherein performing the file operation on the write-back cache comprises generating modified blocks in the write-back cache;

and

wherein the file operation further comprises a read operation, and wherein performing the file operation on the write-back cache comprises retrieving data from the write-back cache and not from the storage device.

17. The computer system of claim 15, wherein copying data blocks from the write-back cache into the physical log maintained in the storage device based on a state of the write-back cache is performed responsive to determining that the write-back cache has exceeded a threshold amount of modified blocks.

18. The computer system of claim 15, wherein copying data blocks from the write-back cache into the physical log maintained in the storage device based on a state of the write-back cache further comprises:

writing a first physical log entry comprising the modified blocks to the physical log; and

writing a second physical log entry indicating a commit operation to the physical log.

19. The computer system of claim 18, further comprising:

responsive to writing to second physical log entry indicating the commit operation to the physical log, updating a data block on the storage device using the first physical log entry in the physical log.

20. The computer system of claim 15, further comprising:

performing a bootstrap procedure subsequent to a system failure, the bootstrap procedure comprising;

retrieving one or more un-played physical log entries from the physical log;

replaying the physical log entries into the write-back cache maintained in memory;

retrieving one or more un-replayed logical log entries from the logical log; and

replaying the logical log entries into the write-back cache maintained in memory.