Granted Patent B2

US 12,645,644 · App. 18/583,335 · Granted Jun 2, 2026

Inventors: Hui Qi (Suwon-si, KR); Peng Yun (Suwon-si, KR)

Assignee: SAMSUNG ELECTRONICS CO., LTD.

G06F16/1744G06F16/2246

Abstract

Claims (55)

1 . A compaction method for sorted string table (SST) files stored in zones of a zoned namespace solid state drive (ZNS SSD), comprising:

determining, based on a compaction operation for a first level of a Log Structure Merge Tree (LSM-Tree), a plurality of first SST files in the first level and a plurality of second SST files in a second level, wherein at least one key range among key ranges of the plurality of first SST files at least partially overlaps with key ranges of the plurality of second SST files in the second level, and at least one key range among the key ranges of the plurality of second SST files at least partially overlaps with the key ranges of the plurality of first SST files, wherein the second level is a level of the LSM-Tree that is adjacent to the first level and higher than the first level;

obtaining a key overlapping ratio for each of the plurality of first SST files based on a size of the key range of each of the plurality of first SST files and one or more second SST files, among the plurality of second SST files, the one or more second SST files comprising a key range at least partially overlapping with a key range of each of the plurality of first SST files;

obtaining compaction priority scores, each corresponding to one of the plurality of first SST files based on a plurality of factor values, each of the plurality of factor values obtained based on a product of attribute information of each of a plurality of zones corresponding to each of the respective one of the plurality of first SST files and a weight respectively associated with each of the zones corresponding to each of the respective one of the plurality of first SST files;

obtaining priority information of each of the plurality of first SST files based on the key overlapping ratio of each of the plurality of first SST files and the compaction priority score of each of the plurality of first SST files; and

performing compaction on a first SST file having a highest compaction priority among the plurality of first SST files based on the priority information by deleting the first SST file in the respective zone and reclaiming the respective zone for storing a new SST file,

wherein the obtaining the compaction priority score of each of the plurality of first SST files further comprises determining a maximum value among the plurality of factor values, and

wherein the performing the compaction on the first SST file having the highest compaction priority among the plurality of first SST files based on the compaction priority score of each of the plurality of first SST files.

2 . The method of claim 1 , wherein the obtaining the priority information further comprises:

determining one or more types of the attribute information of each of the plurality of zones corresponding to the each of the plurality of first SST files and the one or more second SST files;

determining each of the plurality of factor values based on the one or more types of the attribute information of each of the plurality of zones according to a preset rule;

determining the compaction priority score of each of the plurality of first SST files based on the plurality of factor values corresponding to the plurality of zones and the key overlapping ratio; and

determining the priority information based on the compaction priority scores of the plurality of first SST files.

3 . The method of claim 2 , wherein the one or more types of the attribute information comprises at least one of a ratio of a size of invalid files in each of the plurality of zones to a capacity of the respective zone, a usage duration of each of the plurality of zones, and a reciprocal of a number of accesses to each of the plurality of zones.

4 . The method of claim 3 , wherein the invalid files comprise an SST file that is capable of being deleted through a compaction operation on the each of the plurality of first SST files and the one or more second SST files or the usage duration of the each zone indicates an interval between time the each zone was last opened and current time.

5 . The method of claim 2 , wherein the determining of the factor values respectively corresponding to each of the plurality of zones comprises:

performing weighted summation on the one or more types of the attribute information of each of the plurality of zones.

6 . The method of claim 2 , wherein the determining of the compaction priority score of each of the plurality of first SST files further comprises:

determining the compaction priority score of each of the plurality of first SST files based on the key overlapping ratio and the maximum value.

7 . The method of claim 6 , wherein the determining of the compaction priority score of the each of the plurality of first SST files based on the key overlapping ratio and the maximum value comprises:

using a ratio of the maximum value plus 1 to the key overlapping ratio as the compaction priority score of the each of the plurality of first SST files.

8 . The method of claim 2 , wherein the determining of the priority information comprises:

determining an SST file, among two of the plurality of first SST files, having a greater compaction priority score as having a higher compaction priority, and

wherein the performing of the compaction on the SST file having the higher compaction priority among the two of the plurality of first SST files comprises:

selecting the SST file having the higher compaction priority among the two of the plurality of first SST files and performing the compaction on the selected SST file having the higher compaction priority and SST files each of which has a key range at least partially overlapping with a key range of the selected SST file having the higher compaction priority among the plurality of second SST files.

9 . An electronic device comprising:

a processor; and

a memory configured to store instructions that when executed by the processor cause the processor to:

identify one or more first SST files and one or more second SST files, wherein at least one key range among key ranges of the one or more first SST files at least partially overlaps at least one key range among key ranges of the one or more second SST files;

obtain a key overlapping ratio for each of the one or more first SST files based on a size of the key range of each of the one or more first SST files and the one or more second SST files, the one or more second SST files comprising a key range at least partially overlapping with a key range of each of the one or more first SST files;

obtain compaction priority scores, each corresponding to one of the one or more first SST files based on a plurality of factor values, each of the plurality of factor values obtained based on a product of attribute information of each of a plurality of zones corresponding to each of the respective one of the one or more first SST files and a weight respectively associated with each of the zones corresponding to each of the respective one of the one or more first SST files;

obtain priority information each of the one or more first SST files based on the key overlapping ratio of each of the one or more first SST files and the compaction priority score of each of the plurality of first SST files;

perform compaction on a first SST file, among the one or more first SST files based on the priority information by deleting the first SST file in the respective zone and reclaiming the respective zone for storing a new SST file,

wherein the obtaining the compaction priority score of for each of the one or more first SST files further comprises determining a maximum value among the plurality of factor values, and

wherein the performing the compaction on the first SST file having a highest compaction priority among the one or more first SST files based on the compaction priority score of each of the plurality of first SST files.

10 . A compaction method for sorted string table (SST) files stored in zones of a zoned namespace solid state drive (ZNS SSD), comprising:

determining, based on a compaction operation for a first level of a Log Structure Merge Tree (LSM-Tree), a plurality of first SST files in the first level and a plurality of second SST files in a second level, wherein at least one key range among key ranges of the plurality of first SST files at least partially overlaps with key ranges of the plurality of second SST files in the second level, and at least one key range among the key ranges of the plurality of second SST files at least partially overlaps with the key ranges of the plurality of first SST files, wherein the second level is a level of the LSM-Tree that is adjacent to the first level and higher than the first level;

obtaining a key overlapping ratio for each of the plurality of first SST files based on a size of the key range of each of the plurality of first SST files and one or more second SST files, among the plurality of second SST files, the one or more second SST files comprising a key range at least partially overlapping with a key range of each of the plurality of first SST files;

determining one or more types of the attribute information of each of a plurality of zones corresponding to the each of the plurality of first SST files and the one or more second SST files;

obtaining compaction priority scores, each corresponding to one of the plurality of first SST files based on a plurality of factor values, each of the plurality of factor values corresponding to each of the plurality of zones based on the one or more types of the attribute information of each of the plurality of zones according to a preset rule;

obtaining priority information of each of the plurality of first SST files based on the key overlapping ratio of each of the plurality of first SST files and the compaction priority score of each of the plurality of first SST files; and

performing compaction on a first SST file having a highest compaction priority among the plurality of first SST files based on the priority information by deleting the first SST file in the respective zone and reclaiming the respective zone for storing a new SST file.

11 . The method of claim 10 , the one or more types of the attribute information comprises at least one of a ratio of a size of invalid files in each of the plurality of zones to a capacity of the respective zone, a usage duration of each of the plurality of zones, and a reciprocal of a number of accesses to each of the plurality of zones.

12 . The method of claim 11 , wherein the invalid files comprise an SST file that is capable of being deleted through a compaction operation on the each of the plurality of first SST files and the one or more second SST files or the usage duration of the each zone indicates an interval between time the each zone was last opened and current time.

13 . The method of claim 10 , wherein the determining of a factor value, among the plurality of factor values, corresponding to each of the plurality of zones comprises:

performing weighted summation on the one or more types of the attribute information of each of the plurality of zones.

14 . The method of claim 10 , wherein the determining of the compaction priority score of each of the plurality of first SST files comprises:

determining a maximum value among the plurality of factor values corresponding to the plurality of zones; and

determining the compaction priority score of each of the plurality of first SST files based on the key overlapping ratio and the maximum value.

15 . The method of claim 14 , wherein the determining of the compaction priority score of the each of the plurality of first SST files based on the key overlapping ratio and the maximum value comprises:

using a ratio of the maximum value plus 1 to the key overlapping ratio as the compaction priority score of the each of the plurality of first SST files.

16 . The method of claim 10 , wherein the determining of the priority information comprises:

determining an SST file, among two of the plurality of first SST files, having a greater compaction priority score as having a higher compaction priority, and

wherein the performing of the compaction on the SST file having the higher compaction priority among the two of the plurality of first SST files comprises:

selecting the SST file having the higher compaction priority among the two of the plurality of first SST files and performing the compaction on the selected SST file having the higher compaction priority and SST files each of which has a key range at least partially overlapping with a key range of the selected SST file having the higher compaction priority among the plurality of second SST files.

Assignments (1)

Priority Claims (1)

Continuity (1)

References Cited (16)