Scalable I/O operations on a log-structured merge (LSM) tree

Patent metadata

Field	Value
Publication number	US-11675745-B2
Application number	US-202017097473-A
Country	US
Kind code	B2
Filing date	Nov 13, 2020
Priority date	Nov 13, 2020
Publication date	Jun 13, 2023
Grant date	Jun 13, 2023

Abstract

A method for managing data associated with objects stored in a cloud storage is provided. The method receives, at a first compute node, first data associated with an object stored in the cloud storage, the first compute node being one of a plurality of compute nodes that store data associated with different objects as storage objects in a log-structured merging (LSM) tree data structure. The method then assigns a first unique name to a first storage object associated with the first data, the first unique name comprising a combination of at least an identifier identifying the first compute node and a first incremental local value. The method stores the first storage object in a first level (L0) of the LSM tree data structure.

First claim

We claim:

1. A method for managing data associated with objects stored in a cloud storage, comprising:
receiving, at a first compute node, first data associated with an object stored in the cloud storage, the first compute node being one of a plurality of compute nodes that store data associated with different objects as storage objects in a log-structured merging (LSM) tree data structure;
assigning, by the first compute node, a first unique name to a first storage object associated with the first data, the first unique name comprising a combination of at least an identifier identifying the first compute node and a first incremental local value;
storing the first storage object in a first level (LO) of the LSM tree data structure;
receiving, at the first compute node, second data associated with the object;
assigning, by the first compute node, a second unique name to a second storage object associated with the second data, the second unique name comprising a combination of at least the identifier identifying the first compute node and a second incremental local value that is equal to the first incremental local value incremented; and
storing the second storage object in the LO of the LSM tree data structure.

2. The method of claim 1 , wherein a storage object comprises a sorted string table (SSTable) having at least one key that maps to a value, wherein each compute node in the plurality of compute nodes is assigned a different range of keys to store in SSTables of the LSM tree data structure.

3. The method of claim 1 , wherein a second compute node in the plurality of compute nodes stores a third storage object in the LSM tree data structure by:
assigning a third unique name to the third storage object, the third unique name comprising a combination of at least a second identifier identifying the second compute node and a third incremental local value; and
storing the third storage object in the L0 of the LSM tree data structure.

4. The method of claim 1 , wherein when a size of the LO reaches a threshold, a merging entity moves a plurality of storage objects stored in the LO, including the first and second storage objects, to a second level (L1) of the LSM tree data structure to make the LO available for storing additional data, the moving comprising:
determining that the first and second storage objects share the identifier indentifying the first compute node in their respective first and second unique names;
based on the determining, merging the first and second storage objects into a merged storage object; and
moving the merged storage object to the L1 of the LSM tree.

5. The method of claim 4 , wherein the plurality of storage objects in the L0 further comprises a third storage object and a fourth storage object,
wherein the first and second storage objects are within a first shard of a plurality of shards, and the third and fourth storage objects are within a second shard of the plurality of shards, and
wherein when the size of the L0 reaches the threshold, the merging entity merges and moves storage objects that are within the first shard to the L1, and a second merging entity merges and moves storage objects that are within the second shard to the L1.

6. The method of claim 5 , wherein the merging entity is assigned a first range of keys to merge and move to lower levels of the LSM tree data structure and the second merging entity is assigned a second range of keys to merge and move to the lower levels, and
wherein at least one of the first and second ranges of keys is readjusted when a total size of data storage objects within a corresponding shard exceeds a threshold.

7. The method of claim 1 , wherein the object comprises a virtual disk of a virtual machine and the first data associated with the object comprises metadata associated with the virtual disk, wherein the virtual disk is stored in the cloud storage in a log-structured file system (LFS) data structure, while the metadata is stored in the same or different cloud storage in the LSM tree data structure.

8. The method of claim 1 , wherein receiving the first data associated with the object comprises receiving the first data from an uploader agent residing in a host machine of a datacenter, wherein the object comprises a virtual disk of a virtual machine executing on the host machine.

9. The method of claim 8 , wherein a second datacenter retrieves data of the virtual disk from the cloud storage and the first storage object from the LSM tree data structure to recover and run the virtual machine in case of a failure in the datacenter.

10. A non-transitory computer readable medium comprising instructions that, when executed by one or more processors of a computing system, cause the computing system to perform a method for managing data associated with objects stored in a cloud storage, the method comprising:
receiving, at a first compute node, first data associated with an object stored in the cloud storage, the first compute node being one of a plurality of compute nodes that store data associated with different objects as storage objects in a log-structured merging (LSM) tree data structure;
assigning, by the first compute node, a first unique name to a first storage object associated with the first data, the first unique name comprising a combination of at least an identifier identifying the first compute node and a first incremental local value;
storing the first storage object in a first level (LO) of the LSM tree data structure;
receiving, at the first compute node, second data associated with the object;
assigning, by the first compute node, a second unique name to a second storage object associated with the second data, the second unique name comprising a combination of at least the identifier identifying the first compute node and a second incremental local value that is equal to the first incremental local value incremented; and
storing the second storage object in the LO of the LSM tree data structure.

11. The non-transitory computer readable medium of claim 10 , wherein a storage object comprises a sorted string table (SSTable) having at least one key that maps to a value, wherein each compute node in the plurality of compute nodes is assigned a different range of keys to store in SSTables of the LSM tree data structure.

12. The non-transitory computer readable medium of claim 10 , wherein when a size of the LO reaches a threshold, a merging entity moves a plurality of storage objects stored in the LO, including the first and second storage objects, to a second level (L1) of the LSM tree data structure to make the LO available for storing additional data, the moving comprising:
determining that the first and second storage objects share the identifier identifying the first compute node in their respective first and second unique names;
based on the determining, merging the first and second storage objects into a merged storage object; and
moving the merged storage object to the L1 of the LSM tree.

13. The non-transitory computer readable medium of claim 12 , wherein the plurality of storage objects in the L0 further comprises a third storage object and a fourth storage object,
wherein the first and second storage objects are within a first shard of a plurality of shards, and the third and fourth storage objects are within a second shard of the plurality of shards, and
wherein when the size of the L0 reaches the threshold, the merging entity merges and moves storage objects that are within the first shard to the L1, and a second merging entity merges and moves storage objects that are within the second shard to the L1.

14. A computer

Assignees

• Vmware Inc

Inventors

• Wang Wenguang
• Gao Junlong
• Gunturu Vamsi

Classifications

• G06F16/1824

  implemented using Network-attached Storage [NAS] architecture (distributed or networked storage systems G06F3/067; protocols for distributed storage of data in a network H04L67/1097) · CPC title

• G06F9/45558

  Hypervisor-specific management and integration aspects · CPC title

• G06F11/1484

  involving virtual machines · CPC title

• G06F11/1451

  by selection of backup contents · CPC title

• G06F16/1805 Primary

  Append-only file systems, e.g. using logs or journals to store data · CPC title