Systems and methods of amortizing deletion processing of a log structured storage based volume virtualization

1. A method of amortizing metadata updates due to data delete operations in a data storage system, comprising:

writing a plurality of data chunks as log structured data onto at least one segment of a virtual volume;

storing information pertaining to the at least one segment as at least one entry of a segment database;

identifying at least one data chunk among the plurality of data chunks written as log structured data onto the at least one segment of the virtual volume, the identified at least one data chunk being a deleted data chunk on the at least one segment;

storing metadata pertaining to the deleted data chunk as at least one entry of a deleted chunk database configured as a log structured merge (LSM) tree;

performing an ordered traversal of entries in the segment database and entries in the deleted chunk database configured as the LSM-tree to identify a location of the deleted data chunk on the at least one segment; and

performing a segment clean operation to recover storage space on the at least one segment consumed by the deleted data chunk, the LSM-tree being a multi-level LSM-tree including a plurality of levels, and the data storage system including a memory,

wherein the storing of the metadata pertaining to the deleted data chunk includes:

inserting the metadata pertaining to the deleted data chunk into a first metadata tablet at a first respective level from among the plurality of levels of the multi-level LSM-tree within the memory;

upon the first metadata tablet at the first respective level of the multi-level LSM-tree reaching a predetermined size threshold, prohibiting insertion of additional metadata pertaining to one or more deleted data chunks into the first metadata tablet; and

inserting the additional metadata pertaining to the one or more deleted data chunks into a second metadata tablet at the first respective level of the multi-level LSM-tree within the memory, and

wherein the performing of the ordered traversal of the entries in the segment database and the entries in the deleted chunk database includes performing the ordered traversal at the first respective level of the multi-level LSM-tree where a first number of deleted data chunks in one of the first metadata tablet and the second metadata tablet relative to a total number of the entries in the segment database is greater than a predetermined value.

2. The method of claim 1 wherein the storing of the metadata pertaining to the deleted data chunk further includes, upon the second metadata tablet at the first respective level of the multi-level LSM-tree reaching the predetermined size threshold, performing a data merge operation on the first and second metadata tablets within the memory to form a third metadata tablet at a second respective level from among the plurality of levels of the multi-level LSM-tree.

3. The method of claim 2 further comprising:

performing a data flush operation on the third metadata tablet at the second respective level of the multi-level LSM-tree to migrate the third metadata tablet from the memory to persistent storage of the deleted chunk database.

4. The method of claim 2 wherein the deleted chunk database is a key/value store, wherein the at least one entry of the deleted chunk database has a key and a corresponding reference count that is initialized to one, and wherein the performing of the data merge operation on the first and second metadata tablets includes, in the event two or more entries of the deleted chunk database within the first and second metadata tablets have the same key, summing reference counts corresponding to the two or more entries of the deleted chunk database to obtain a reference count sum, and adding one of the two or more entries with the reference count sum to the third metadata tablet.

5. The method of claim 2 wherein the segment database is a key/value store, wherein the at least one entry of the segment database has a key and at least one corresponding value, wherein the at least one corresponding value includes a latest clean time of the at least one segment, wherein the third metadata tablet has an associated time stamp indicating a last add time when an entry of the deleted chunk database was last added to the third metadata tablet, and wherein the performing of the data merge operation on the first and second metadata tablets includes, in the event the latest clean time of the at least one segment is greater than the last add time of the third metadata tablet, omitting the entry of the deleted chunk database from the third metadata tablet.

6. The method of claim 2 wherein the performing of the ordered traversal of the entries in the segment database and the entries in the deleted chunk database includes performing the ordered traversal at the second respective level of the multi-level LSM-tree where a second number of deleted data chunks in the third metadata tablet relative to the total number of the entries in the segment database is greater than the predetermined value.

7. The method of claim 1 wherein the performing of the segment clean operation to recover the storage space on the at least one segment includes identifying the at least one segment based at least in part on an amount of storage space occupied by deleted data chunks.

8. The method of claim 7 wherein the data storage system includes a deleted chunk accounting database having a plurality of entries, each entry of the deleted chunk accounting database including a second number of deleted data chunks in a respective segment of the virtual volume, and wherein the identifying of the at least one segment based at least in part on the amount of storage space occupied by deleted data chunks includes identifying the at least one segment with a greatest number of deleted data chunks, as indicated by the plurality of entries of the deleted chunk accounting database.

9. The method of claim 7 wherein the performing of the segment clean operation to recover the storage space on the at least one segment further includes comparing the at least one entry of the segment database for the identified at least one segment against the at least one entry of the deleted chunk database configured as the LSM-tree.

10. The method of claim 9 wherein the comparing of the at least one entry of the segment database for the identified at least one segment against the at least one entry of the deleted chunk database includes performing ordered traversals of the deleted chunk database and the identified at least one segment to identify each data chunk on the identified at least one segment having a status of the deleted data chunk.

11. The method of claim 1 wherein the segment database is a first key/value store, wherein the at least one entry of the first key/value store has a key field and a value field, wherein the key field of the first key/value store includes a segment identifier of the at least one segment, and wherein the value field of the first key/value store includes a chunk map of the respective data chunks written to the at least one segment.

12. The method of claim 11 wherein the deleted chunk database is a second key/value store, wherein the at least one entry of the second key/value store has a first key field, a second key field, and a value field, wherein the first key field includes the segment identifier, wherein the second key field includes a chunk identifier of the at least one data chunk, and wherein the value field of the second key/value store includes a reference count of a total number of deleted data chunks on the at least one segment having the segment identifier.

13. The method of claim 12 wherein the performing of the ordered traversal of the entries in the segment database and the entries in the deleted chunk database includes performing the ordered traversal in the first key/value store and the second key/value store to identify a location of the deleted data chunk on the at least one segment based at least on the segment identifier, the chunk identifier, the chunk map, and the reference count.

14. A system for amortizing metadata updates due to data delete operations in a data storage system, comprising:

storage processing circuitry;

a memory;

a segment database;

a deleted chunk database configured as a log structured merge (LSM) tree; and

an array of storage devices configured for log structured data storage of virtual volumes,

wherein the storage processing circuitry is operative to execute a computer program out of the memory:

to write a plurality of data chunks as log structured data onto at least one segment of a virtual volume;

to store information pertaining to the at least one segment as at least one entry of the segment database;

to identify at least one data chunk among the plurality of data chunks written as log structured data onto the at least one segment of the virtual volume, the identified at least one data chunk being a deleted data chunk on the at least one segment;

to store metadata pertaining to the deleted data chunk as at least one entry of the deleted chunk database configured as the LSM-tree;

to perform an ordered traversal of entries in the segment database and entries in the deleted chunk database configured as the LSM-tree to identify a location of the deleted data chunk on the at least one segment; and

to perform a segment clean operation to recover storage space on the at least one segment consumed by the deleted data chunk,

wherein the LSM-tree is a multi-level LSM-tree including a plurality of levels, and

wherein the storage processing circuitry is further operative to execute the computer program out of the memory:

to insert the metadata pertaining to the deleted data chunk into a first metadata tablet at a first respective level from among the plurality of levels of the multi-level LSM-tree within the memory;

upon the first metadata tablet at the first respective level of the multi-level LSM-tree reaching a predetermined size threshold, to prohibit insertion of additional metadata pertaining to one or more deleted data chunks into the first metadata tablet; and

to insert the additional metadata pertaining to the one or more deleted data chunks into a second metadata tablet at the first respective level of the multi-level LSM-tree within the memory, and

wherein performing the ordered traversal of the entries in the segment database and the entries in the deleted chunk database includes performing the ordered traversal at the first respective level of the multi-level LSM-tree where a first number of deleted data chunks in one of the first metadata tablet and the second metadata tablet relative to a total number of the entries in the segment database is greater than a predetermined value.

15. The system of claim 14 wherein the storage processing circuitry is further operative to execute the computer program out of the memory, upon the second metadata tablet at the first respective level of the multi-level LSM-tree reaching the predetermined size threshold, to perform a data merge operation on the first and second metadata tablets within the memory to form a third metadata tablet at a second respective level from among the plurality of levels of the multi-level LSM-tree.

16. The system of claim 15 wherein the storage processing circuitry is further operative to execute the computer program out of the memory to perform a data flush operation on the third metadata tablet at the second respective level of the multi-level LSM-tree to migrate the third metadata tablet from the memory to persistent storage of the deleted chunk database.

17. The system of claim 14 wherein the data storage system further includes a deleted chunk accounting database having a plurality of entries, each entry of the deleted chunk accounting database including a second number of deleted data chunks in a respective segment of the virtual volume, and wherein the storage processing circuitry is further operative to execute the computer program out of the memory to identify the at least one segment with a greatest number of deleted data chunks, as indicated by the plurality of entries of the deleted chunk accounting database.

18. The system of claim 17 wherein the storage processing circuitry is further operative to execute the computer program out of the memory to compare the at least one entry of the segment database for the identified at least one segment against the at least one entry of the deleted chunk database configured as the LSM-tree.

19. The system of claim 18 wherein the storage processing circuitry is further operative to execute the computer program out of the memory perform ordered traversals of the deleted chunk database and the identified at least one segment to identify each data chunk on the identified at least one segment having a status of the deleted data chunk.

20. A computer program product having a non-transitory computer readable medium that stores a set of instructions to amortize metadata updates due to data delete operations in a data storage system, the set of instructions, when carried out by computerized circuitry, causing the computerized circuitry to perform a method of:

writing a plurality of data chunks as log structured data onto at least one segment of a virtual volume;

storing information pertaining to the at least one segment as at least one entry of a segment database;

identifying at least one data chunk among the plurality of data chunks written as log structured data onto the at least one segment of the virtual volume, the identified at least one data chunk being a deleted data chunk on the at least one segment;

storing metadata pertaining to the deleted data chunk as at least one entry of a deleted chunk database configured as a log structured merge (LSM) tree;

performing an ordered traversal of entries in the segment database and entries in the deleted chunk database configured as the LSM-tree to identify a location of the deleted data chunk on the at least one segment; and

performing a segment clean operation to recover storage space on the at least one segment consumed by the deleted data chunk, the LSM-tree being a multi-level LSM-tree including a plurality of levels, and the data storage system including a memory,

wherein the storing of the metadata pertaining to the deleted data chunk includes:

inserting the metadata pertaining to the deleted data chunk into a first metadata tablet at a first respective level from among the plurality of levels of the multi-level LSM-tree within the memory;

upon the first metadata tablet at the first respective level of the multi-level LSM-tree reaching a predetermined size threshold, prohibiting insertion of additional metadata pertaining to one or more deleted data chunks into the first metadata tablet; and

inserting the additional metadata pertaining to the one or more deleted data chunks into a second metadata tablet at the first respective level of the multi-level LSM-tree within the memory, and

wherein the performing of the ordered traversal of the entries in the segment database and the entries in the deleted chunk database includes performing the ordered traversal at the first respective level of the multi-level LSM-tree where a first number of deleted data chunks in one of the first metadata tablet and the second metadata tablet relative to a total number of the entries in the segment database is greater than a predetermined value.