# US 10,311,025 B2 · Duplicate in-memory shared-intermediate data detection and reuse module in spark framework

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,311,025 B2
- Document ID: US10311025B2
- Status: Granted
- Kind: B2
- Application number: 15/404,100
- Filed: 2017-01-11
- Published: 2018-03-08
- Granted: 2019-06-04
- Earliest claimed: 2016-09-06
- Assignees: Samsung Electronics Co., Ltd.
- Applicants: Samsung Electronics Co., Ltd.
- Inventors: Zhengyu Yang; Jiayin Wang; Thomas David Evans
- Web page: https://patentgrep.com/patent/US10311025B2

## CPC

- G06F 16/172: Caching, prefetching or hoarding of files
- G06F 3/06: Digital input from, or digital output to, record carriers {, e.g. RAID, emulated record carriers or networked record carriers}
- G06F 3/061: {Improving I/O performance}
- G06F 3/0634: {by changing the state or mode of one or more devices}
- G06F 3/0685: {Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays}
- G06F 9/45558: {Hypervisor-specific management and integration aspects}
- G06F 12/0808: with cache invalidating means (G06F12/0815 takes precedence)
- G06F 12/0811: with multilevel cache hierarchies
- G06F 12/0842: for multiprocessing or multitasking
- G06F 12/0862: with prefetch
- G06F 12/124: {being minimized, e.g. non MRU}
- G06F 12/126: with special data handling, e.g. priority of data or instructions, handling errors or pinning
- G06F 16/188: Virtual file systems
- G06F 12/0868: Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
- G06F 2009/4557: {Distribution of virtual machine instances; Migration and load balancing}
- G06F 2009/45579: {I/O management, e.g. providing access to device drivers or storage}
- G06F 2009/45583: {Memory management, e.g. access or allocation}
- G06F 2212/1021: Hit rate improvement
- G06F 2212/602: Details relating to cache prefetching
- G06F 2212/6024: History based prefetching
- G06F 2212/62: Details of cache specific to multiprocessor cache arrangements
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A cache management system for managing a plurality of intermediate data includes 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, and in response to not identifying the new intermediate data as one of the plurality of intermediate data identifying a reusable intermediate data having a longest duplicate generating logic chain that is at least in part the same as a generating logic chain of the new intermediate data, and generating the new intermediate data from the reusable intermediate data and a portion of the generating logic chain of the new intermediate data not in common with the reusable intermediate data.

## Claims

### Claim 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; and
in response to not identifying the new intermediate data as one of the plurality of intermediate data:
identifying a reusable intermediate data having a longest duplicate generating logic chain that is at least in part the same as a generating logic chain of the new intermediate data, each generating logic chain comprising a chain of functions applied to a corresponding intermediate data source, a first function of the chain of functions operating on the corresponding intermediate data source and each subsequent function of the chain of functions operating on an output of a previous function of the chain of functions; and
generating the new intermediate data from the reusable intermediate data and a portion of the generating logic chain of the new intermediate data not in common with the reusable intermediate data,
wherein the identifying of the reusable intermediate data comprises:
identifying a subset of intermediate data, each one of the subset of intermediate data having a same intermediate data source as the new intermediate data and a generating logic chain that is not longer than that of the new intermediate data; and
comparing functions of the generating logic chain of each one of the subset of intermediate data to those of the new intermediate data, in a sequence, to identify the reusable intermediate data as one of the subset of intermediate data having a longest sequence of matching functions with the new intermediate data.

### Claim 2 (depends on 1)

The cache management system of claim 1, wherein the instructions further cause the processor to perform:
in response to a lack of sufficient space within the memory to store the new intermediate data:
selecting a set of victim intermediate data from the plurality of intermediate data to evict from the memory; and
evicting the set of victim intermediate data from the memory.

### Claim 3 (depends on 1)

The cache management system of claim 1, wherein the sequence is an order of functions from the intermediate data source to the each one of the subset of intermediate data.

### Claim 4 (depends on 1)

The cache management system of claim 1, wherein the intermediate data source of each of the subset of intermediate data has a same size as, and a same data structure as, that of the new intermediate data.

### Claim 5 (depends on 1)

The cache management system of claim 1, wherein the identifying of the subset of intermediate data comprises:
comparing, byte-to-byte, the intermediate data source of each one of the subset of intermediate data with the new intermediate data.

### Claim 6 (depends on 1)

The cache management system of claim 1, wherein the comparing of the functions of the generating logic chain of each one of the subset of intermediate data to those of the new intermediate data comprises:
determining that the functions of the generating logic chain of each one of the subset of intermediate data and those of the new intermediate data are deterministic; and
in response, determining that types of the functions of the generating logic chain of each one of the subset of intermediate data are the same as those of the new intermediate data.

### Claim 7 (depends on 6)

The cache management system of claim 6, wherein the determining that the functions are deterministic comprises:
matching each of the functions with one of a preset list of deterministic functions.

### Claim 8 (depends on 1)

The cache management system of claim 1, wherein the generating of the new intermediate data from the reusable intermediate data comprises:
successively applying, to the reusable intermediate data, functions of the generating logic chain of the new intermediate data not in common with the reusable intermediate data to generate the new intermediate data.

### Claim 9 (depends on 1)

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

### Claim 10

A method of managing a plurality of intermediate data stored in 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; and
in response to not identifying the new intermediate data as one of the plurality of intermediate data:
identifying, by the processor, a reusable intermediate data having a longest duplicate generating logic chain that is at least in part the same as a generating logic chain of the new intermediate data, each generating logic chain comprising a chain of functions applied to a corresponding intermediate data source, a first function of the chain of functions operating on the corresponding intermediate data source and each subsequent function of the chain of functions operating on an output of a previous function of the chain of functions; and
generating, by the processor, the new intermediate data from the reusable intermediate data and a portion of the generating logic chain of the new intermediate data not in common with the reusable intermediate data,
wherein the identifying of the reusable intermediate data comprises:
identifying, by the processor, a subset of intermediate data, each one of the subset of intermediate data having a same intermediate data source as the new intermediate data and a generating logic chain that is not longer than that of the new intermediate data; and
comparing, by the processor, functions of the generating logic chain of each one of the subset of intermediate data to those of the new intermediate data, in a sequence, to identify the reusable intermediate data as one of the subset of intermediate data having a longest sequence of matching functions with the new intermediate data.

### Claim 11 (depends on 10)

The method of claim 10, further comprising:
in response to a lack of sufficient space within the memory to store the new intermediate data:
selecting, by the processor, a set of victim intermediate data from the plurality of intermediate data to evict from the memory; and
evicting, by the processor, the set of victim intermediate data from the memory.

### Claim 12 (depends on 10)

The method of claim 10, wherein the sequence is an order of functions from the intermediate data source to the each one of the subset of intermediate data.

### Claim 13 (depends on 10)

The method of claim 10, wherein the intermediate data source of each of the subset of intermediate data has a same size as, and a same data structure as, that of the new intermediate data.

### Claim 14 (depends on 10)

The method of claim 10, wherein the identifying of the subset of intermediate data comprises:
comparing, byte-to-byte, by the processor, the intermediate data source of each one of the subset of intermediate data with the new intermediate data.

### Claim 15 (depends on 10)

The method of claim 10, wherein the comparing of the functions of the generating logic chain of each one of the subset of intermediate data to those of the new intermediate data comprises:
determining, by the processor, that the functions of the generating logic chain of each one of the subset of intermediate data and those of the new intermediate data are deterministic; and
in response, determining, by the processor, that types of the functions of the generating logic chain of each one of the subset of intermediate data are the same as those of the new intermediate data.

### Claim 16 (depends on 15)

The method of claim 15, wherein the determining that the functions are deterministic comprises:
matching, by the processor, each of the functions with one of a preset list of deterministic functions.

### Claim 17 (depends on 10)

The method of claim 10, wherein the generating of the new intermediate data from the reusable intermediate data comprises:
successively applying, to the reusable intermediate data, by the processor, functions of the generating logic chain of the new intermediate data not in common with the reusable intermediate data to generate the new intermediate data.

### Claim 18 (depends on 10)

The method of claim 10, wherein each one of the plurality of intermediate data is a resilient distributed data (RDD).