# US 12,182,078 B2 · Partitioning mechanism for parallel processing in delta generation

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

- Number: US 12,182,078 B2
- Document ID: US12182078B2
- Status: Granted
- Kind: B2
- Application number: 18/181,414
- Filed: 2023-03-09
- Published: 2023-12-21
- Granted: 2024-12-31
- Earliest claimed: 2022-06-16
- Assignees: Oracle International Corporation
- Applicants: Oracle International Corporation
- Inventors: Satish Kumar Kashi Visvanathan; Vikram Singh Bisht; Viggnesh Venugopal; Ravi Lingappa Shamanna
- Web page: https://patentgrep.com/patent/US12182078B2

## CPC

- G06F 16/178: Techniques for file synchronisation in file systems
- G06F 9/505: {considering the load}
- G06F 11/1417: {Boot up procedures}
- G06F 11/1451: {by selection of backup contents}
- G06F 11/1464: {for networked environments}
- G06F 11/2023: {Failover techniques}
- G06F 11/2028: {eliminating a faulty processor or activating a spare}
- G06F 11/2038: {with a single idle spare processing component}
- G06F 11/2094: {Redundant storage or storage space (G06F11/2056 takes precedence)}
- G06F 11/2097: {maintaining the standby controller/processing unit updated (initialisation or re-synchronisation thereof G06F11/1658 and subgroups)}
- G06F 16/11: File system administration, e.g. details of archiving or snapshots (error detection or correction of the data by redundancy in operations G06F11/14)
- G06F 16/119: {Details of migration of file systems (migration mechanisms in storage systems G06F3/0647)}
- G06F 16/128: {Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion (error detection or correction of the data by redundancy in operations or in hardware G06F11/14, G06F11/16)}
- G06F 16/1756: {based on delta files}
- G06F 16/1844: {Management specifically adapted to replicated file systems}
- G06F 16/185: Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof (details of archiving G06F16/11)
- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 16/27: Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
- G06F 21/602: {Providing cryptographic facilities or services}
- G06F 21/6218: {to a system of files or objects, e.g. local or distributed file system or database}
- H04L 9/0819: {Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s) (network architectures or network communication protocols for key distribution in a packet data network H04L63/062)}
- H04L 9/0836: {using tree structure or hierarchical structure}
- H04L 9/0891: {Revocation or update of secret information, e.g. encryption key update or rekeying}
- H04L 9/0894: {Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage}
- H04L 9/14: using a plurality of keys or algorithms
- H04L 9/3228: {One-time or temporary data, i.e. information which is sent for every authentication or authorization, e.g. one-time-password, one-time-token or one-time-key}
- G06F 11/2048: {where the redundant components share neither address space nor persistent storage}
- G06F 16/1774: {Locking methods, e.g. locking methods for file systems allowing shared and concurrent access to files}
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 2201/84: Using snapshots, i.e. a logical point-in-time copy of the data
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Techniques are described for partitioning B-tree keys of file systems into key ranges for parallel processing in delta generation during file storage replications between file systems in different cloud infrastructure regions. In certain embodiments, a delta generation processing for cross-region replication may utilize a key-range splitting mechanism involving a recursive algorithm that partitions B-tree keys of a source file system into roughly equal-size key ranges. All the partitioned key ranges may be processed in parallel and concurrently by different processing threads, one thread per key range, to improve the performance of the delta generation and achieve scalability.

## Claims

### Claim 1

A method, comprising:
receiving, by a computing system, a request to perform a first replication between a source file system in a source region and a target file system in a target region, the first replication being one of a plurality of parallel replications, the source region and the target region being in different regions;
storing, by the computing system, a first snapshot and a second snapshot of the source file system in nodes of a tree structure, each node of the tree structure comprising one or more key-value pairs representing the first snapshot and the second snapshot of the source file system; and
performing, by the computing system, a first-level operation within the first replication, the first-level operation comprising generating deltas between a first snapshot and a second snapshot in a tree structure associated with the source file system, the first snapshot being a base snapshot, the second snapshot being a snapshot being replicated, and the tree structure having multiple levels of hierarchy comprising more nodes in a lower hierarchical level than a higher hierarchical level, the generating deltas comprising:
sorting, by the computing system, keys in nodes of the tree structure, at a current tree level, into an ascending order;
identifying, by the computing system, the sorted keys in the nodes of the tree structure, at the current tree level, belonging to the first snapshot and the second snapshot of the source file system;
recursively traversing, by the computing system, from top of the tree hierarchy to a tree level containing the number of the identified keys enough for partitioning the identified keys by determining whether the number of the identified keys is greater than or equal to a first number, wherein the first number is adjusted for each replication cycle; and
partitioning, by the computing system, the identified keys into a plurality of key ranges being equal to the first number, in accordance with the number of the identified keys being determined to be greater than or equal to the first number, each key range having one or more identified keys, and wherein a second-level operation is performed on each key range of the plurality of key ranges in parallel, the second-level operation corresponding to a partial delta generation.

### Claim 2 (depends on 1)

The method of claim 1, further comprising keeping the identified keys in a single key range if the current tree level is the bottom tree level and the number of the identified keys is determined to be smaller than the first number.

### Claim 3 (depends on 1)

The method of claim 1, wherein the partial delta generation comprises processing the identified keys in a first key range of the plurality of key ranges by a first parallel-running processing thread in the source file system.

### Claim 4 (depends on 3)

The method of claim 3, wherein processing the identified keys comprises collecting delta keys in each key range, the delta keys being identified to be keys that are different between the first snapshot and the second snapshot in the tree structure.

### Claim 5 (depends on 1)

The method of claim 1, wherein the first number is determined based at least in part on considering one or more file system factors and is larger than the number of available processing threads of the source file system.

### Claim 6 (depends on 5)

The method of claim 5, wherein the one or more file system factors comprise bandwidth, throughput, number of keys to partition, thread counts available to process keys, and size of the source file system.

### Claim 7 (depends on 1)

The method of claim 1, wherein the second-level operation is one of a plurality of second-level operations, wherein the plurality of second-level operations are created by:
partitioning the first-level operation into the plurality of second-level operations running in parallel;
wherein each second-level operation is performed on the one or more identified keys in each key range of the plurality of key ranges,
wherein each second-level operation comprises a partial delta generation between the first snapshot and the second snapshot, and
wherein combined results of the second-level operations equal to a result of the first-level operation.

### Claim 8

A non-transitory computer-readable medium storing computer-executable instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:
receiving, by a computing system, a request to perform a first replication between a source file system in a source region and a target file system in a target region, the first replication being one of a plurality of parallel replications, the source region and the target region being in different regions;
storing, by the computing system, a first snapshot and a second snapshot of the source file system in nodes of a tree structure, each node of the tree structure comprising one or more key-value pairs representing the first snapshot and the second snapshot of the source file system; and
performing, by the computing system, a first-level operation within the first replication, the first-level operation comprising generating deltas between a first snapshot and a second snapshot in a tree structure associated with the source file system, the first snapshot being a base snapshot, the second snapshot being a snapshot being replicated, and the tree structure having multiple levels of hierarchy comprising more nodes in a lower hierarchical level than a higher hierarchical level, the generating deltas comprising:
sorting, by the computing system, keys in nodes of the tree structure, at a current tree level, into an ascending order;
identifying, by the computing system, the sorted keys in the nodes of the tree structure, at the current tree level, belonging to the first snapshot and the second snapshot of the source file system;
recursively traversing, by the computing system, from top of the tree hierarchy to a tree level containing the number of the identified keys enough for partitioning the identified keys by determining whether the number of the identified keys is greater than or equal to a first number, wherein the first number is adjusted for each replication cycle; and
partitioning, by the computing system, the identified keys into a plurality of key ranges being equal to the first number, in accordance with the number of the identified keys being determined to be greater than or equal to the first number, each key range having one or more identified keys, and wherein a second-level operation is performed on each key range of the plurality of key ranges in parallel, the second-level operation corresponding to a partial delta generation.

### Claim 9 (depends on 8)

The non-transitory computer-readable medium of claim 8, the operations further comprising keeping the identified keys in a single key range if the current tree level is the bottom tree level and the number of the identified keys is determined to be smaller than the first number.

### Claim 10 (depends on 8)

The non-transitory computer-readable medium of claim 8, wherein the partial delta generation comprises processing the identified keys in a first key range of the plurality of key ranges by a first parallel-running processing thread in the source file system, wherein the processing the identified keys comprises collecting delta keys in each key range, the delta keys being identified to be keys that are different between the first snapshot and the second snapshot in the tree structure.

### Claim 11 (depends on 8)

The non-transitory computer-readable medium of claim 8, wherein the first number is determined based at least in part on considering one or more file system factors and is larger than the number of available processing threads of the source file system, wherein the one or more file system factors comprise bandwidth, throughput, number of keys to partition, thread counts available to process keys, and size of the source file system.

### Claim 12 (depends on 8)

The non-transitory computer-readable medium of claim 8, wherein the second-level operation is one of a plurality of second-level operations, wherein the plurality of second-level operations are created by:
partitioning the first-level operation into the plurality of second-level operations running in parallel;
wherein each second-level operation is performed on the one or more identified keys in each key range of the plurality of key ranges,
wherein each second-level operation comprises a partial delta generation between the first snapshot and the second snapshot, and
wherein combined results of the second-level operations equal to a result of the first-level operation.

### Claim 13

A system, comprising:
one or more processors; and
one or more computer readable media storing computer-executable instructions that, when executed by the one or more processors, cause the system to:
receive a request to perform a first replication between a source file system in a source region and a target file system in a target region, the first replication being one of a plurality of parallel replications, the source region and the target region being in different regions;
store a first snapshot and a second snapshot of the source file system in nodes of a tree structure, each node of the tree structure comprising one or more key-value pairs representing the first snapshot and the second snapshot of the source file system; and
perform a first-level operation within the first replication, the first-level operation comprising generating deltas between a first snapshot and a second snapshot in a tree structure associated with the source file system, the first snapshot being a base snapshot, the second snapshot being a snapshot being replicated, and the tree structure having multiple levels of hierarchy comprising more nodes in a lower hierarchical level than a higher hierarchical level, the generating deltas comprising:
sort keys in nodes of the tree structure, at a current tree level, into an ascending order;
identify the sorted keys in the nodes of the tree structure, at the current tree level, belonging to the first snapshot and the second snapshot of the source file system;
recursively traverse from top of the tree hierarchy to a tree level containing the number of the identified keys enough for partitioning the identified keys by determining whether the number of the identified keys is greater than or equal to a first number, wherein the first number is adjusted for each replication cycle; and
partition the identified keys into a plurality of key ranges being equal to the first number, in accordance with the number of the identified keys being determined to be greater than or equal to the first number, each key range having one or more identified keys, and wherein a second-level operation is performed on each key range of the plurality of key ranges in parallel, the second-level operation corresponding to a partial delta generation.

### Claim 14 (depends on 13)

The system of claim 13, wherein the system is further caused to keep the identified keys in a single key range if the current tree level is the bottom tree level and the number of the identified keys is determined to be smaller than the first number.

### Claim 15 (depends on 13)

The system of claim 13, wherein the partial delta generation comprises processing the identified keys in a first key range of the plurality of key ranges by a first parallel-running processing thread in the source file system, wherein processing the identified keys comprises collecting delta keys in each key range, the delta keys being identified to be keys that are different between the first snapshot and the second snapshot in the tree structure.

### Claim 16 (depends on 13)

The system of claim 13, wherein the first number is determined based at least in part on considering one or more file system factors and is larger than the number of available processing threads of the source file system, wherein the one or more file system factors comprise bandwidth, throughput, number of keys to partition, thread counts available to process keys, and size of the source file system.

### Claim 17 (depends on 13)

The system of claim 13, wherein the second-level operation is one of a plurality of second-level operations, wherein the plurality of second-level operations are created by:
partitioning the first-level operation into the plurality of second-level operations running in parallel;
wherein each second-level operation is performed on the one or more identified keys in each key range of the plurality of key ranges,
wherein each second-level operation comprises a partial delta generation between the first snapshot and the second snapshot, and
wherein combined results of the second-level operations equal to a result of the first-level operation.