Log-structured b-tree for handling random writes

Patent metadata

Field	Value
Publication number	US-2016378653-A1
Application number	US-201514750554-A
Country	US
Kind code	A1
Filing date	Jun 25, 2015
Priority date	Jun 25, 2015
Publication date	Dec 29, 2016
Grant date	—

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.

First claim

What is claimed is:

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; performing the file operation on the write-back cache maintained in memory; 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 based on 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; performing the file operation on the write-back cache maintained in memory; 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 based on 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;
performing the file operation on the write-back cache maintained in memory;
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; and
updating the B-tree data structure stored on the storage device based on 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 c

Assignees

• Vmware Inc

Inventors

• Lu Yunshan
• Wang Wenguang

Classifications

• G06F12/0806 Primary

  Multiuser, multiprocessor or multiprocessing cache systems · CPC title

• G06F12/0866 Primary

  for peripheral storage systems, e.g. disk cache · CPC title

• G06F2212/621

  Coherency control relating to peripheral accessing, e.g. from DMA or I/O device · CPC title

• G06F2212/463

  File · CPC title

• G06F12/0804

  with main memory updating (G06F12/0806 takes precedence) · CPC title