Update-correlations based overwrite mechanism

Patent metadata

Field	Value
Publication number	US-12182175-B2
Application number	US-202318181738-A
Country	US
Kind code	B2
Filing date	Mar 10, 2023
Priority date	Dec 21, 2022
Publication date	Dec 31, 2024
Grant date	Dec 31, 2024

Abstract

An information handling system acquires data chunks for a duration of at least one time slice, determines an overwrite frequency for the duration of the time slice of each of the data chunks, clusters the data chunks according to the overwrite frequency, and determines an overwrite frequency label for each cluster of the data chunks. The system may also determine a read frequency for the duration of the time slice of each of the data chunks, cluster the data chunks based on the read frequency, and determine a read frequency label for each of the cluster of the data chunks. The system may also construct a sorted tree based on the overwrite frequency label, the read frequency label, and a virtual logical block address of each of the data chunks.

First claim

What is claimed is:

1. A method comprising:
acquiring, by a processor, a plurality of data chunks with a duration of at least one time slice;
determining an overwrite frequency for the duration of the time slice of each of the data chunks, clustering the data chunks based on the overwrite frequency, and determining an overwrite frequency label for each cluster of the data chunks;
determining a read frequency for the duration of the time slice of each of the data chunks, clustering the data chunks based on the read frequency, and determining a read frequency label for each cluster of the data chunks; and

constructing a sorted tree based on the overwrite frequency label, the read frequency label, and a virtual logical block address of each of the data chunks, wherein a first index of a first parent node in a first level of the sorted tree is based on the overwrite frequency label, and wherein a second index of a second parent node in a second level of the sorted tree is based on the read frequency label.

2. The method of claim 1 , wherein the data chunks with same values for the overwrite frequency label and the read frequency label are included in one leaf node.

3. The method of claim 1 , wherein the data chunks with same values for the overwrite frequency label are included in neighbor leaf nodes.

4. The method of claim 1 , wherein the sorted tree is used to group the data chunks based on the overwrite frequency label and the read frequency label.

5. The method of claim 1 , wherein the overwrite frequency is a number of times that a data chunk has been overwritten for the duration of the time slice.

6. The method of claim 1 , wherein the read frequency is a number of times that a data chunk has been read for the duration of the time slice.

7. The method of claim 1 , wherein a leaf node of the sorted tree includes one or more data chunks that are sorted according to the virtual logical block address.

8. An information handling system, comprising:
a processor; and
a memory storing instructions that when executed cause the processor to perform operations including:
acquiring a plurality of data chunks for a duration of at least one time slice;
determining an overwrite frequency for the duration of the time slice of each of the data chunks, clustering the data chunks according to the overwrite frequency, and determining an overwrite frequency label for each cluster of the data chunks;
determining a read frequency for the duration of the time slice of each of the data chunks, clustering the data chunks based on the read frequency, and determining a read frequency label for each of the cluster of the data chunks; and

constructing a sorted tree based on the overwrite frequency label, the read frequency label, and a virtual logical block address of each of the data chunks, wherein a first index of a first parent node in a first level of the sorted tree is based on the overwrite frequency label, and wherein a second index of a second parent node in a second level of the sorted tree is based on the read frequency label.

9. The information handling system of claim 8 , wherein the data chunks with same values for the overwrite frequency label and the read frequency label are included in one leaf node.

10. The information handling system of claim 8 , wherein the data chunks with same values for the overwrite frequency label are included in neighbor leaf nodes.

11. The information handling system of claim 8 , wherein the sorted tree is used to group the data chunks based on the overwrite frequency label and the read frequency label.

12. The information handling system of claim 8 , wherein the overwrite frequency is a number of times that a data chunk has been overwritten for the duration of the time slice.

13. The information handling system of claim 8 , wherein the read frequency is a number of times that a data chunk has been read for the duration of the time slice.

14. The information handling system of claim 8 , wherein a leaf node of the sorted tree includes one or more data chunks that are sorted according to the virtual logical block address.

15. A non-transitory computer-readable medium to store instructions that are executable to perform operations comprising:
acquiring a plurality of data chunks for a duration of at least one time slice;
determining an overwrite frequency for the duration of the time slice of each of the data chunks, clustering the data chunks according to the overwrite frequency, and determining an overwrite frequency label for each cluster of the data chunks;
determining a read frequency for the duration of the time slice of each of the data chunks, clustering the data chunks based on the read frequency, and determining a read frequency label for each of the cluster of the data chunks; and

constructing a sorted tree based on the overwrite frequency label, the read frequency label, and a virtual logical block address of each of the data chunks, wherein a first index of a first parent node in a first level of the sorted tree is based on the overwrite frequency label, and wherein a second index of a second parent node in a second level of the sorted tree is based on the read frequency label.

16. The non-transitory computer-readable medium of claim 15 , wherein the virtual logical block address of each of the data chunks with same values for the overwrite frequency label and the read frequency label are included in one leaf node.

17. The non-transitory computer-readable medium of claim 15 , wherein the virtual logical block address of each of the data chunks with same values for the overwrite frequency label are included in neighbor leaf nodes.

18. The non-transitory computer-readable medium of claim 15 , wherein the sorted tree is used to group the data chunks based on the overwrite frequency label and the read frequency label.

19. The non-transitory computer-readable medium of claim 15 , wherein the overwrite frequency is a number of times that a data chunk has been overwritten for the duration of the time slice.

20. The non-transitory computer-readable medium of claim 15 , wherein the read frequency is a number of times that a data chunk has been read for the duration of the time slice.

Assignees

• Dell Products Lp

Inventors

• Pu Weilan
• Wang Jie
• Kang Jian

Classifications

• G06F16/2246

  Trees, e.g. B+trees · CPC title

• G06F16/285 Primary

  Clustering or classification · CPC title