Partitioning mechanism for parallel processing in delta generation
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.
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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.
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.
9. 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.
10. 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.
11. 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.
12. 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.
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.
14. 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.
15. 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.
16. 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.
17. 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.