Method and apparatus for data access

Patent metadata

Field	Value
Publication number	US-10698831-B2
Application number	US-201715848451-A
Country	US
Kind code	B2
Filing date	Dec 20, 2017
Priority date	Dec 21, 2016
Publication date	Jun 30, 2020
Grant date	Jun 30, 2020

Abstract

Embodiments of the present disclosure relates to a method and device of data access. The method comprises determining whether target data stored in a non-volatile storage device is cached in a memory. The target data is organized in a first level of a multi-way tree in the storage device. The method further comprises, in response to determining that the target data is missing in the memory, moving the target data from the storage device into the memory. Besides, the method comprises, in response to the target data being accessed from the memory, adding a reference to the target data to a first list, the first list recording a sequence for accessing data in the first level.

First claim

We claim:

1. A method for data access, comprising:
determining whether target data stored in a non-volatile storage device is cached in a memory, the target data being organized in a first level of a multi-way tree in the storage device;
in response to determining that the target data is missing in the memory, moving the target data from the storage device into the memory; and
in response to the target data being accessed from the memory, adding a reference to the target data to a first list, the first list recording a sequence for accessing data in the first level,
wherein the multi-way tree has a second level having a lower priority than the first level, and wherein the method further comprises moving data out of the memory in inverse relation to priority, such that a greater proportion of data organized in the second level of the multi-way tree is moved out of memory than is moved out of memory from the first level of the multi-way tree.

2. The method according to claim 1 , wherein the determining whether target data stored in a non-volatile storage device is cached in a memory comprises:
determining, by searching a hash table, whether the target data is cached in the memory; and
wherein the moving the target data from the storage device into the memory comprises:
adding, to the hash table, a data entry indicating that the target data is cached in the memory.

3. The method according to claim 1 , further comprising:
in response to determining that the target data has been cached in the memory, causing the target data to be accessed from the memory; and
in response to the target data being accessed from the memory and the reference being added to the first list, updating a position of the reference in the first list.

4. The method according to claim 1 , further comprising:
in response to determining that usage of the memory exceeds a predetermined threshold, determining, based on the first list, a recent access condition of data in the first level; and
moving, based on the recent access condition, a part of the data in the first level out of the memory.

5. The method according to claim 1 , further comprising:
in response to determining usage of the memory exceeds a predetermined threshold,
determining, based on the first list, a first recent access condition of data in the first level;
moving, based on the first recent access condition, a first amount of data in the first level out of the memory;
determining, based on a second list, a second recent access condition of data in the second level of the multi-way tree, and the second list recording a sequence for accessing the data in the second level; and
moving, based on the second access condition, a second amount of data in the second level out of the memory, the first amount being less than the second amount.

6. The method according to claim 5 , wherein a depth of the second level in the multi-way tree is greater than that of the first level in the multi-way tree.

7. The method according to claim 1 , further comprising:
in response to determining that the target data is being accessed and the reference has been added to the first list, removing the reference from the first list.

8. The method of claim 1 , further comprising accessing the target data in the multi-way tree by searching at least one address of one or more nodes of the multi-way tree.

9. The method of claim 1 , wherein the first level of the multi-way tree comprises a root node, and further comprising accessing the target data in the multi-way tree by searching from the root node.

10. An electronic device, comprising:
at least one processing unit;
at least one memory coupled to the at least one processing unit and storing instructions for execution by the at least one processing unit, the instructions, when executed by the at least one processing unit, causing the device to:
determine whether target data stored in a non-volatile storage device is cached in a memory, the target data being organized in a first level of a multi-way tree in the storage device;
in response to determining that the target data is missing in the memory, move the target data from the storage device into the memory; and
in response to the target data being accessed from the memory, add a reference to the target data to a first list, the first list recording a sequence for accessing data in the first level,
wherein the multi-way tree has a second level having a lower priority than the first level, and wherein the instructions further cause the device to move data out of the memory in inverse relation to priority, such that a greater proportion of data organized in the second level of the multi-way tree is moved out of memory than is moved out of memory from the first level of the multi-way tree.

11. The device according to claim 10 , wherein the determining whether target data stored in a non-volatile storage device is cached in a memory comprises:
determining, by searching a hash table, whether the target data is cached in the memory; and
wherein the moving the target data from the storage device into the memory comprises:
adding, to the hash table, a data entry indicating that the target data is cached in the memory.

12. The device according to claim 10 , wherein the instructions, when executed by the at least one processing unit, further cause the device to:
in response to determining that the target data has been cached in the memory, cause the target data to be accessed from the memory; and
in response to the target data being accessed from the memory and the reference being added to the first list, update a position of the reference in the first list.

13. The device according to claim 10 , wherein the instructions, when executed by the at least one processing unit, further cause the device to:
in response to determining that usage of the memory exceeds a predetermined threshold, determine, based on the first list, a recent access condition of data in the first level; and
move, based on the recent access condition, a part of the data in the first level out of the memory.

14. The device according to claim 10 , wherein the instructions, when executed by the at least one processing unit, further cause the device to:
in response to determining usage of the memory exceeds a predetermined threshold,
determine, based on the first list, a first recent access condition of data in the first level;
move, based on the first recent access condition, a first amount of data in the first level out of the memory;
determine, based on a second list, a second recent access condition of data in the second level of the multi-way tree, and the second list recording a sequence for accessing the data in the second level; and
move, based on the second access condition, a second amount of data in the second level out of the memory, the first amount being less than the second amount.

15. The device according to claim 14 , wherein a depth of the second level in the multi-way tree is greater than that of the first level in the multi-way tree.

16. The device according to claim 10 , wherein the instructions, when executed by the at least one processing unit, further cause the device to:
in response to determining that the target data is being accessed and the reference has been added to the first list, remove the reference from the first list.

17. A computer program product for data access, the computer program product comprising:
a non-transitory computer readable medium encoded with computer-executable program code, the code configured to enable the execution

Assignees

• Emc Ip Holding Co Llc

Inventors

• Zhou Qiaosheng
• Zhao Junping
• Xu Xinlei
• Hu Wilson
• Wu Jun

Classifications

• G06F12/123 Primary

  with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list · CPC title

• G06F12/128

  adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel · CPC title

• G06F12/126

  with special data handling, e.g. priority of data or instructions, handling errors or pinning · CPC title

• G06F16/00

  Information retrieval; Database structures therefor; File system structures therefor · CPC title

• G06F12/0891 Primary

  using clearing, invalidating or resetting means · CPC title