Shrinking segment cleaning algorithm in an object storage

Patent metadata

Field	Value
Publication number	US-11435935-B2
Application number	US-202017100663-A
Country	US
Kind code	B2
Filing date	Nov 20, 2020
Priority date	Nov 20, 2020
Publication date	Sep 6, 2022
Grant date	Sep 6, 2022

Abstract

A method for cleaning an object storage having a plurality of segments is provided. Each segment includes an identifier through which the segment is accessed. The method identifies a first segment in the plurality of segments. The first segment includes a first identifier and a first size. The method determines that a utilization ratio for the first segment is below a threshold. As a result, the method generates a second segment from the first segment, such that the second segment includes a second identifier that is the same as the first identifier and a second size that is smaller than the first size. The method then writes the second segment to the object storage.

First claim

We claim:

1. A method for cleaning an object storage having a plurality of segments, each segment having an identifier through which the segment is accessed, comprising:
identifying a first segment in the plurality of segments, the first segment having a first identifier and a first size wherein each segment of the plurality of segments comprises one or more data blocks that are either live or dead, wherein the first segment comprises at least one dead data block that is not included in a second segment;
determining that a utilization ratio for the first segment is below a threshold;
generating the second segment from the first segment, the second segment having a second identifier that is the same as the first identifier and a second size that is smaller than the first size; and
writing the second segment to the object storage where a table stores data that indicates a corresponding identifier, a corresponding number of live data blocks, and a corresponding size of each of the plurality of segments, the method further comprising updating the table to include the second size as a size of the first segment.

2. The method of claim 1 , wherein the utilization ratio for the first segment comprises a ratio between a number of live blocks of the first segment and the size of the first segment.

3. The method of claim 1 , further comprising:
receiving a first read instruction comprising the first identifier;
returning the first segment in response to receiving the first read instruction;
receiving a second read instruction comprising the first identifier; and
returning the second segment in response to receiving the second read instruction.

4. The method of claim 1 , wherein the object storage comprises an atomic update with eventual consistency data storage.

5. The method of claim 1 , wherein a table stores a plurality of key-value pairs, each key-value pair comprising a logical block address that is mapped to a segment identifier of a segment of the plurality of segments in the object storage, the method further comprising, after identifying the first segment:
identifying one or more logical blocks stored in the first segment by reading metadata associated with the first segment; and
determining which of the one or more logical blocks is a live block using the table, wherein the utilization ratio for the first segment is determined based on a number of live blocks in the first segment and the first size of the first segment.

6. The method of claim 5 , wherein the second segment comprises only live blocks of the first segment, wherein the table is not updated for the second segment after generating the second segment from the first segment.

7. 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 cleaning an object storage having a plurality of segments, each segment having an identifier through which the segment is accessed, the method comprising:
identifying a first segment in the plurality of segments, the first segment having a first identifier and a first size wherein each segment of the plurality of segments comprises one or more data blocks that are either live or dead, wherein the first segment comprises at least one dead data block that is not included in a second segment;
determining that a utilization ratio for the first segment is below a threshold;
generating the second segment from the first segment, the second segment having a second identifier that is the same as the first identifier and a second size that is smaller than the first size; and
writing the second segment to the object storage wherein a table stores data that indicates a corresponding identifier, a corresponding number of live data blocks, and a corresponding size of each of the plurality of segments, the method further comprising updating the table to include the second size as a size of the first segment.

8. The non-transitory computer readable medium of claim 7 , wherein the utilization ratio for the first segment comprises a ratio between a number of live blocks of the first segment and the size of the first segment.

9. The non-transitory computer readable medium of claim 7 , the method further comprising:
receiving a first read instruction comprising the first identifier;
returning the first segment in response to receiving the first read instruction;
receiving a second read instruction comprising the first identifier; and
returning the second segment in response to receiving the second read instruction.

10. The non-transitory computer readable medium of claim 7 , wherein a table stores a plurality of key-value pairs, each key-value pair comprising a logical block address that is mapped to a segment identifier of a segment of the plurality of segments in the object storage, the method further comprising, after identifying the first segment:
identifying one or more logical blocks stored in the first segment by reading metadata associated with the first segment; and
determining which of the one or more logical blocks is a live block using the table, wherein the utilization ratio for the first segment is determined based on a number of live blocks in the first segment and the first size of the first segment.

11. The non-transitory computer readable medium of claim 10 , wherein the second segment comprises only live blocks of the first segment, wherein the table is not updated for the second segment after generating the second segment from the first segment.

12. A computer system, comprising:
a memory; and
a processor coupled to the memory, the processor being configured to:
identify a first segment in a plurality of segments, the first segment having a first identifier and a first size wherein each segment of the plurality of segments comprises one or more data blocks that are either live or dead, wherein the first segment comprises at least one dead data block that is not included in a second segment;
determine that a utilization ratio for the first segment is below a threshold;
generate the second segment from the first segment, the second segment having a second identifier that is the same as the first identifier and a second size that is smaller than the first size; and
write the second segment to an object storage wherein a table stores data that indicates a corresponding identifier, a corresponding number of live data blocks, and a corresponding size of each of the plurality of segments, the processor being further configured to update the table to include the second size as a size of the first segment.

13. The computer system of claim 12 , wherein the utilization ratio for the first segment comprises a ratio between a number of live blocks of the first segment and the size of the first segment.

14. The computer system of claim 12 , wherein the processor is further configured to:
receive a first read instruction comprising the first identifier;
return the first segment in response to receiving the first read instruction;
receive a second read instruction comprising the first identifier; and
return the second segment in response to receiving the second read instruction.

Assignees

• Vmware Inc

Inventors

• Wang Wenguang
• Vandrovec Petr
• Negi Hardik Singh
• Gao Junlong
• Gunturu Vamsi

Classifications

• G06F3/0659

  Command handling arrangements, e.g. command buffers, queues, command scheduling · CPC title

• G06F3/0673

  Single storage device · CPC title

• G06F16/1727

  Details of free space management performed by the file system (saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064) · CPC title

• G06F2201/815

  Virtual · CPC title

• G06F3/067 Primary

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title