Writing data to an LSM tree file structure using consistent cache staging

Patent metadata

Field	Value
Publication number	US-11620261-B2
Application number	US-201816213815-A
Country	US
Kind code	B2
Filing date	Dec 7, 2018
Priority date	Dec 7, 2018
Publication date	Apr 4, 2023
Grant date	Apr 4, 2023

Abstract

The disclosure herein describes writing data to a log-structured merge (LSM) tree file system on an object storage platform. Write data instructions indicating data for writing to the LSM tree file system are received. Based on the received instructions, the data is written to the first data cache. Based on an instruction to transfer data in the live data cache to the LSM tree file system, the first data cache is converted to a stable cache. A second data cache configured as a live data cache is then generated based on cloning the first data cache. The data in the first data cache is then written to the LSM tree file system. Use of a stable cache and a cloned live data cache enables parallel writing data to the file system by the stable cache and handling write data instructions by the live data cache.

First claim

What is claimed is:

1. A computerized method for writing data to a log-structured merge (LSM) tree file system on an object storage platform, the method comprising:
receiving, by a processor, write data instructions indicating data for writing to the LSM tree file system;
based on the received write data instructions, writing, by the processor, the data to a first data cache, wherein the first data cache is configured as a live data cache to which write data instructions are directed and a second data cache has not been generated; and
based on an instruction to transfer data in the live data cache to the LSM tree file system:
converting, by the processor, the first data cache from the live data cache to a stable cache to which write data instructions are not directed;
generating, by the processor, the second data cache based on cloning the stable cache, wherein the second data cache is configured as a live data cache to which write data instructions are directed; and
writing, by the processor, the data in the stable cache to the LSM tree file system in parallel with the second data cache receiving write data instructions.

2. The computerized method of claim 1 , wherein the stable cache and the second data cache are installed on a client device and the LSM tree file system is installed on a server device connected to the client device by a network.

3. The computerized method of claim 1 , wherein the stable cache and second data cache include dirty bits associated with data blocks, the dirty bits indicating that associated data blocks are changed in an associated data cache; and
wherein generating the second data cache based on cloning the stable cache includes clearing all dirty bits of the second data cache.

4. The computerized method of claim 1 , wherein the stable cache and second data cache include respective sparse files representing a set of data blocks of the LSM tree file system, the respective sparse files including references to cached data blocks; and
wherein generating the second data cache based on cloning the stable cache includes copying cached data block references of a sparse file of the stable cache to the second data cache, whereby a sparse file of the second data cache includes references to the same cached data blocks as the sparse file of the stable cache.

5. The computerized method of claim 4 , further comprising:
receiving a write data instruction indicating a data change to be made to a target cached data block, wherein the write data instruction is directed to the second data cache;
writing a new data block based on the write data instruction, wherein the new data block is a copy of the target cached data block including the data change; and
replacing, in the sparse file of the second data cache, a reference to the target cached data block with a reference to the new data block.

6. The computerized method of claim 1 , wherein the instruction to transfer data in the live data cache to the LSM tree file system is based on at least one of an expiration of a data cache interval and a data cache capacity being exceeded by the first data cache.

7. The computerized method of claim 1 , wherein converting the first data cache from the live data cache to the stable cache comprises one or more of: renaming the first data cache and setting a flag associated with the first data cache indicating that the first data cache is stable, the method further comprising:
based on completion of writing the data in the stable cache to the LSM tree file system, deleting the stable cache.

8. A computer system comprising:
a processor;
a non-transitory computer readable medium having stored thereon program code for writing data to a log-structured merge (LSM) tree file system on an object storage platform, the program code causing the processor to:
receive write data instructions indicating data for writing to the LSM tree file system;
based on the received write data instructions, write the data to a first data cache, wherein the first data cache is configured as a live data cache to which write data instructions are directed;
based on an instruction to transfer data in the live data cache to the LSM tree file system, convert the first data cache from the live data cache to a stable cache to which write data instructions are not directed;
generate a second data cache based on cloning the stable cache, wherein the second data cache is configured as a live data cache to which write data instructions are directed; and
write the data in the stable cache to the LSM tree file system, whereby writing the data in the stable cache to the LSM tree file system is performed in parallel with the second data cache receiving write data instructions.

9. The computer system of claim 8 , wherein the stable cache and the second data cache are installed on a client device and the LSM tree file system is installed on a server device connected to the client device by a network.

10. The computer system of claim 8 , wherein the stable cache and second data cache include dirty bits associated with data blocks, the dirty bits indicating that associated data blocks are changed in an associated data cache; and
wherein generating the second data cache based on cloning the stable cache includes clearing all dirty bits of the second data cache.

11. The computer system of claim 8 , wherein the stable cache and second data cache include respective sparse files representing a set of data blocks of the LSM tree file system, the respective sparse files including references to cached data blocks; and
wherein generating the second data cache based on cloning the stable cache includes copying cached data block references of a sparse file of the stable cache to the second data cache, whereby a sparse file of the second data cache includes references to the same cached data blocks as the sparse file of the stable cache.

12. The computer system of claim 11 , the program code further causing the processor to:
receive a write data instruction indicating a data change to be made to a target cached data block, wherein the write data instruction is directed to the second data cache;
write a new data block based on the write data instruction, wherein the new data block is a copy of the target cached data block including the data change; and
replace, in the sparse file of the second data cache, a reference to the target cached data block with a reference to the new data block.

13. The computer system of claim 8 , wherein the instruction to transfer data in the live data cache to the LSM tree file system is based on at least one of an expiration of a data cache interval and a data cache capacity being exceeded by the first data cache.

14. The computer system of claim 8 , the program code further causing the processor to:
based on completion of writing the data in the stable cache to the LSM tree file system, deleting the stable cache.

15. A non-transitory computer readable storage medium having stored thereon program code executable by a first computer system at a first site, the program code embodying a method comprising:
receiving write data instructions indicating data for writing to a log-structured merge (LSM) tree file system;
based on the received write data instructions, writing the data to a first data cache, wherein the first data cache is configured as a live data cache to which write data instructions are directed;
based on an instruction to transfer data in the live data cache to the LSM tree file system, converting the first data cache from the live data cache to a stable cache to which write data instructions are not dir

Assignees

• Vmware Inc

Inventors

• Wang Wenguang
• Spillane Richard P
• Gao Junlong
• Johnson Robert T
• Karamanolis Christos
• Austruy Maxime

Classifications

• G06F16/172 Primary

  Caching, prefetching or hoarding of files · CPC title

• G06F16/9027

  Trees · CPC title

• G06F12/0891

  using clearing, invalidating or resetting means · CPC title

• G06F12/0875

  with dedicated cache, e.g. instruction or stack · CPC title

• G06F16/1744

  using compression, e.g. sparse files · CPC title