In-memory shared data reuse replacement and caching

• US 10,372,677 B2
• Filed: 01/11/2017
• Issued: 08/06/2019
• Est. Priority Date: 09/06/2016
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd. (Samsung Group)
• Original Assignee: Samsung Electronics Co. Ltd. (Samsung Group)
• Inventors: Yang, Zhengyu, Wang, Jiayin, Evans, Thomas David
• Primary Examiner(s): Bragdon, Reginald G
• Assistant Examiner(s): Knight, Paul M
• Application Number:
  US15/404,121
• Publication Number:
  US 20180067869A1
• Time in Patent Office: 937 Days
• Field of Search: None
• CPC Class Codes: G06F 12/0808 with cache invalidating means G06F12/0815 takes precedence
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/124 being minimized, e.g. non MRU
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files
• CPC Class Codes: G06F 16/188 Virtual file systems
• CPC Class Codes: G06F 2009/4557 Distribution of virtual machine instances; Migration and load balancing
• CPC Class Codes: G06F 2009/45579 I/O management, e.g. providing access to device drivers or storage
• CPC Class Codes: G06F 2009/45583 Memory management, e.g. access or allocation
• CPC Class Codes: G06F 2212/1021 Hit rate improvement
• CPC Class Codes: G06F 2212/602 Details relating to cache prefetching
• CPC Class Codes: G06F 2212/6024 History based prefetching
• CPC Class Codes: G06F 2212/62 Details of cache specific to multiprocessor cache arrangements
• CPC Class Codes: G06F 3/06 Digital input from, or digital output to, record carriers , e.g. RAID, emulated record carriers or networked record carriers
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0634 by changing the state or mode of one or more devices
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays
• CPC Class Codes: G06F 9/45558 : Hypervisor-specific management and integration aspects

Abstract

A cache management system for managing a plurality of intermediate data includes a processor and a memory having stored thereon instructions that cause the processor to perform identifying a new intermediate data to be accessed, loading the intermediate data from the memory in response to identifying the new intermediate data as one of the plurality of intermediate data, in response to not identifying the new intermediate data as one of the plurality of intermediate data, selecting a set of victim intermediate data to evict from the memory based on a plurality of scores associated with respective ones of the plurality of intermediate data, the scores being based on a score table, evicting the set of victim intermediate data from the memory, updating the score table based on the set of victim intermediate data, and adding the new intermediate data to the plurality of intermediate data stored in the memory.

Claims

1. A cache management system for managing a plurality of intermediate data, the cache management system comprising:

a processor; and

a memory having stored thereon the plurality of intermediate data and instructions that when executed by the processor, cause the processor to perform;

identifying a new intermediate data to be accessed;

loading the intermediate data from the memory in response to identifying the new intermediate data as one of the plurality of intermediate data;

in response to not identifying the new intermediate data as one of the plurality of intermediate data;

selecting a set of victim intermediate data from the plurality of intermediate data to evict from the memory based on a plurality of scores associated with respective ones of the plurality of intermediate data, the plurality of scores being based on a score table stored in the memory;

evicting the set of victim intermediate data from the memory;

updating the score table based on the set of victim intermediate data; and

adding the new intermediate data to the plurality of intermediate data stored in the memory,

wherein the score table comprises, for each intermediate data of the plurality of intermediate data, a number of children of the intermediate data, a size of the intermediate data, a re-compute time of the intermediate data.

2. The cache management system of claim 1, wherein the score table further comprises, for each intermediate data of the plurality of intermediate data, a generating logic chain of the intermediate data.

3. The cache management system of claim 1, wherein each one of the plurality of intermediate data is a resilient distributed data (RDD), and

wherein the cache management system operates under a Spark framework.

4. The cache management system of claim 1, wherein the selecting of the set of victim intermediate data comprises:

identifying a first set of intermediate data of the plurality of intermediate data, each one of the first set of intermediate data having a size less than that of the new intermediate data.

5. The cache management system of claim 4, wherein the selecting of the set of victim intermediate data further comprises:

sorting the first set of intermediate data in a sorted order based on first scores associated with respective ones of the first set of intermediate data; and

adding ones of the first set of intermediate data to the set of victim intermediate data to be evicted, based on the sorted order, while a cumulative size of the set of victim intermediate data is less than the new intermediate data.

6. The cache management system of claim 5, wherein the order is an ascending order.

7. The cache management system of claim 5, wherein the generating of each one of the first scores comprises:

calculating a product of a re-compute time and a number of children of an associated one of the first set of intermediate data; and

dividing the calculated product by a size of the associated one of the first set of intermediate data to calculate the one of the first scores.

8. The cache management system of claim 4, wherein the selecting of the set of victim intermediate data comprises:

in response to a size of the first set of intermediate data being smaller than the new intermediate data;

emptying the set of victim intermediate data;

identifying a second set of intermediate data of the plurality of intermediate data, each one of the second set of intermediate data having a size greater than or equal to that of the new intermediate data;

generating second scores associated with respective ones of the plurality of intermediate data based on the score table; and

selecting one intermediate data, as the set of victim intermediate data, from a second set of intermediate data having a lowest associated score among the second scores.

9. The cache management system of claim 8, wherein the generating of the second scores comprises:

generating each one of the second scores based on a re-compute time of, a number of children of, and a size of an associated one of the second set of intermediate data stored at the score table.

10. The cache management system of claim 1, wherein the updating of the score table comprises:

for each one of the set of victim intermediate data;

identifying a child intermediate data of the one of the set of victim intermediate data;

calculating a re-compute time of the child intermediate data based on a re-compute time of the one of the set of victim intermediate data; and

updating the score table based on the calculated re-compute time of the child intermediate data.

11. A cache management system for managing a plurality of intermediate data, the cache management system comprising:

a processor; and

a memory having stored thereon a plurality of intermediate data and instructions that when executed by the processor, cause the processor to perform;

identifying a new intermediate data to be accessed;

loading the intermediate data from the memory in response to identifying the new intermediate data as one of the plurality of intermediate data;

in response to not identifying the new intermediate data as one of the plurality of intermediate data;

generating a plurality of scores associated with respective ones of the plurality of intermediate data, each of the plurality of scores being based on a re-compute time of, a number of children of, and a size of an associated one of the plurality of intermediate data stored at a score table in the memory;

selecting a set of victim intermediate data from the plurality of intermediate data to evict from the memory based on a plurality of scores associated with respective ones of the plurality of intermediate data;

evicting the set of victim intermediate data from the memory;

updating the score table based on the set of victim intermediate data; and

adding the new intermediate data to the plurality of intermediate data stored in the memory.

12. A method of managing a plurality of intermediate data stored in a memory, the method comprising:

identifying, by a processor, a new intermediate data to be accessed;

loading, by the processor, the intermediate data from the memory in response to identifying the new intermediate data as one of the plurality of intermediate data;

in response to not identifying the new intermediate data as one of the plurality of intermediate data;

selecting, by the processor, a set of victim intermediate data from the plurality of intermediate data to evict from the memory based on a plurality of scores associated with respective ones of the plurality of intermediate data, the plurality of scores being based on a score table stored in the memory;

evicting, by the processor, the set of victim intermediate data from the memory;

updating, by the processor, the score table based on the set of victim intermediate data; and

adding, by the processor, the new intermediate data to the plurality of intermediate data stored in the memory,

wherein the score table comprises, for each intermediate data of the plurality of intermediate data, a number of children of the intermediate data, a size of the intermediate data, a re-compute time of the intermediate data.

13. The method of claim 12, wherein the score table further comprises, for each intermediate data of the plurality of intermediate data, a generating logic chain of the intermediate data.

14. The method of claim 12, wherein the selecting of the set of victim intermediate data comprises:

identifying a first set of intermediate data of the plurality of intermediate data, each one of the first set of intermediate data having a size less than that of the new intermediate data.

15. The method of claim 14, wherein the selecting of the set of victim intermediate data comprises:

sorting the first set of intermediate data in a sorted order based on first scores associated with respective ones of the first set of intermediate data; and

adding ones of the first set of intermediate data to the set of victim intermediate data to be evicted, based on the sorted order, while a cumulative size of the set of victim intermediate data is less than or equal to the new intermediate data,

wherein the order is an ascending order.

16. The method of claim 15, wherein the selecting of the set of victim intermediate data further comprises:

generating each one of the first scores based on a re-compute time of, a number of children of, and a size of an associated one of the first set of intermediate data stored at the score table.

17. The method of claim 14, wherein the selecting of the set of victim intermediate data comprises:

in response to a size of the first set of intermediate data being smaller than the new intermediate data;

emptying the set of victim intermediate data;

identifying a second set of intermediate data of the plurality of intermediate data, each one of the second set of intermediate data having a size greater than or equal to that of the new intermediate data;

generating second scores associated with respective ones of the plurality of intermediate data based on the score table; and

selecting one intermediate data, as the set of victim intermediate data, from a second set of intermediate data having a lowest associated score among the second scores.

18. The method of claim 17, wherein the generating of the second scores comprises:

generating each one of the second scores based on a re-compute time of, a number of children of, and a size of an associated one of the second set of intermediate data stored at the score table.

19. The method of claim 12, wherein the updating of the score table comprises:

for each one of the set of victim intermediate data;

identifying a child intermediate data of the one of the set of victim intermediate data;

calculating a re-compute time of the child intermediate data based on a re-compute time of the one of the set of victim intermediate data; and

updating the score table based on the calculated re-compute time of the child intermediate data.

20. A cache management system for managing a plurality of intermediate data, the cache management system comprising:

a processor; and

a memory having stored thereon the plurality of intermediate data and instructions that when executed by the processor, cause the processor to perform;

identifying a new intermediate data to be accessed;

loading the intermediate data from the memory in response to identifying the new intermediate data as one of the plurality of intermediate data;

in response to not identifying the new intermediate data as one of the plurality of intermediate data;

selecting a set of victim intermediate data from the plurality of intermediate data to evict from the memory based on a plurality of scores associated with respective ones of the plurality of intermediate data, the plurality of scores being based on a score table stored in the memory;

evicting the set of victim intermediate data from the memory;

updating the score table based on the set of victim intermediate data; and

adding the new intermediate data to the plurality of intermediate data stored in the memory,

wherein the selecting of the set of victim intermediate data comprises;

identifying a first set of intermediate data of the plurality of intermediate data, each one of the first set of intermediate data having a size less than that of the new intermediate data; and

in response to the first set of intermediate data not being empty;

sorting the first set of intermediate data in a sorted order based on first scores associated with respective ones of the first set of intermediate data;

adding ones of the first set of intermediate data to the set of victim intermediate data to be evicted, based on the sorted order, while a cumulative size of the set of victim intermediate data is less than the new intermediate data; and

generating each one of the first scores based on a re-compute time of, a number of children of, and a size of an associated one of the first set of intermediate data stored at the score table.