Synchronization of index copies in an LSM tree file system

Patent metadata

Field	Value
Publication number	US-11074225-B2
Application number	US-201816231246-A
Country	US
Kind code	B2
Filing date	Dec 21, 2018
Priority date	Dec 21, 2018
Publication date	Jul 27, 2021
Grant date	Jul 27, 2021

Abstract

The disclosure herein describes synchronizing cached index copies at a first site with indexes of a log-structured merge (LSM) tree file system on an object storage platform at a second site. An indication that the LSM tree file system has been compacted based on a compaction process is received. A cached metadata catalog of the included parent catalog version at the first site is accessed. A set of cached index copies is identified at the first site based on the metadata of the cached metadata catalog. The compaction process is applied to the identified set of cached index copies and a compacted set of cached index copies is generated at the first site, whereby the compacted set of cached index copies is synchronized with a respective set of indexes of the plurality of sorted data tables of the LSM tree file system at the second site.

First claim

What is claimed is:

1. A computerized method for synchronizing cached index copies at a first site with indexes of a log-structured merge (LSM) tree file system on an object storage platform at a second site, the method comprising:
receiving, by a processor at the first site, an indication that the LSM tree file system has been compacted based on a compaction process, the indication including a parent catalog version associated with a compacted metadata catalog generated at the second site during the compaction process;
accessing, by the processor, a cached metadata catalog of the included parent catalog version at the first site, the cached metadata catalog including metadata associated with a plurality of sorted data tables of the LSM tree file system;
identifying, by the processor, a set of cached index copies at the first site associated with the plurality of sorted data table based on the metadata of the cached metadata catalog;
applying, by the processor, the compaction process to the identified set of cached index copies based on the metadata of the cached metadata catalog; and
based on the application of the compaction process to the set of cached index copies, generating, by the processor, a compacted set of cached index copies at the first site, whereby the compacted set of cached index copies is synchronized with a respective set of indexes of the plurality of sorted data tables of the LSM tree file system at the second site, wherein the first site includes a client, the second site includes a server, and the client and server are in communication via a network.

2. The computerized method of claim 1 , wherein generating the compacted set of cached index copies includes generating, by the processor, at least one compacted index copy that includes index metadata over a key range based on at least one cached index copy of the identified set of cached index copies that includes metadata over at least a portion of the key range;
flagging, by the processor, the at least one cached index copy of the identified set of cached index copies for garbage collection; and
performing, by the processor, a garbage collection process on the flagged at least one cached index copy, whereby memory associated with the flagged at least one cached index copy is reclaimed.

3. The computerized method of claim 1 , wherein generating the compacted set of cached index copies includes merging key-value tuples of a plurality of cached index copies of the identified set of cached index copies into a single compacted index copy of the compacted set of cached index copies in a sorted order.

4. The computerized method of claim 1 , further comprising:
based on receiving a read data instruction associated with a requested data set, identifying, by the processor, a data location associated with the requested data set based on the compacted set of cached index copies and sending a request to the LSM tree file system at the second site including the identified data location.

5. The computerized method of claim 1 , wherein applying the compaction process to the identified set of cached index copies includes identifying at least one tree level of the LSM tree file system that exceeds an associated tree level capacity based on the metadata of the cached metadata catalog and flagging the at least one tree level for compaction.

6. The computerized method of claim 5 , wherein applying the compaction process to the identified set of cached index copies further includes performing the compaction process over a key range of cached index copies of the identified set of cached index copies associated with the identified at least one tree level.

7. The computerized method of claim 1 , wherein receiving an indication that the LSM tree file system has been compacted based on a compaction process includes receiving the indication from the second site over a network connection.

8. A computer system comprising:
a processor at a first site;
a non-transitory computer readable medium having stored thereon program code for synchronizing cached index copies at the first site with indexes of a log-structured merge (LSM) tree file system on an object storage platform at a second site, the program code causing the processor to:
receive an indication that the LSM tree file system has been compacted based on a compaction process, the indication including a parent catalog version associated with a compacted metadata catalog generated at the second site during the compaction process;
access a cached metadata catalog of the included parent catalog version at the first site, the cached metadata catalog including metadata associated with a plurality of sorted data tables of the LSM tree file system;
identify a set of cached index copies at the first site associated with the plurality of sorted data table based on the metadata of the cached metadata catalog;
apply the compaction process to the identified set of cached index copies based on the metadata of the cached metadata catalog; and
based on the application of the compaction process to the set of cached index copies, generate a compacted set of cached index copies at the first site, whereby the compacted set of cached index copies is synchronized with a respective set of indexes of the plurality of sorted data tables of the LSM tree file system at the second site, wherein the first site includes a client, the second site includes a server, and the client and server are in communication via a network.

9. The system of claim 8 , wherein generating the compacted set of cached index copies includes generating, by the processor, at least one compacted index copy that includes index metadata over a key range based on at least one cached index copy of the identified set of cached index copies that includes metadata over at least a portion of the key range;
flagging, by the processor, the at least one cached index copy of the identified set of cached index copies for garbage collection; and
performing, by the processor, a garbage collection process on the flagged at least one cached index copy, whereby memory associated with the flagged at least one cached index copy is reclaimed.

10. The system of claim 8 , wherein generating the compacted set of cached index copies includes merging key-value tuples of a plurality of cached index copies of the identified set of cached index copies into a single compacted index copy of the compacted set of cached index copies in a sorted order.

11. The system of claim 8 , the program code further causing the processor to:
based on receiving a read data instruction associated with a requested data set, identify a data location associated with the requested data set based on the compacted set of cached index copies and sending a request to the LSM tree file system at the second site including the identified data location.

12. The system of claim 8 , wherein applying the compaction process to the identified set of cached index copies includes identifying at least one tree level of the LSM tree file system that exceeds an associated tree level capacity based on the metadata of the cached metadata catalog and flagging the at least one tree level for compaction.

13. The system of claim 12 , wherein applying the compaction process to the identified set of cached index copies further includes performing the compaction process over a key range of cached index copies of the identified set of cached index copies associated with the identified at least one tree level.

14. The system of claim 8 , wherein receiving an indication that the LSM tree file system has been compacted based on a compaction process includes receiv

Assignees

• Vmware Inc

Inventors

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

Classifications

• G06F16/172

  Caching, prefetching or hoarding of files · CPC title

• G06F16/13 Primary

  File access structures, e.g. distributed indices (arrangements of input from, or output to, record carriers G06F3/06) · CPC title

• G06F16/185

  Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof (details of archiving G06F16/11) · CPC title

• G06F16/178 Primary

  Techniques for file synchronisation in file systems · CPC title