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 cross-region replication between a source file system in a source region and a target file system in a target region, the first cross-region replication being one of a plurality of parallel replications comprising i) a first-level operation comprising extracting deltas representing differences between a first snapshot and a second snapshot of the source file system and ii) a plurality of second-level operations comprising partitioning, in parallel, respective key-value pairs into key ranges, and a first result of the first-level operation corresponding to a second result of the plurality of second-level operations;
performing, by the computing system, the first-level operation by extracting the deltas representing the differences between the first snapshot and the second snapshot of the source file system, the deltas being stored in a tree structure associated with the source file system in the source region, the tree structure having multiple levels of hierarchy comprising more nodes in a lower hierarchal level than a higher hierarchal level, and the first snapshot and the second snapshot comprising the respective sets of key-value pairs;
partitioning, by the computing system, the respective sets of key-value pairs identified in the first-level operation into a first number of key partitions by traversing the tree structure from a top level of the tree structure downward, the first number being configured to be adjusted for each replication cycle; and
performing, by the computing system, the plurality of second-level operations on the first number of key partitions in parallel, each second-level operation of the plurality of second-level operations being performed on a key partition of the first number of key partitions.
2 . The method of claim 1 , wherein each key partition of the key partitions comprises at least one key-value pair stored in the tree structure associated with the source file system.
3 . The method of claim 1 , wherein the cross-region replication comprises encrypting the deltas in the source file system, transferring the encrypted deltas to the target file system, and decrypting the transferred deltas in the target file system.
4 . The method of claim 1 , wherein the second result comprises a combined result of the plurality of second-level operations, and the combined result is equivalent to the first result.
5 . The method of claim 1 , wherein each first-level operation extracts a portion of the deltas between the first snapshot and the second snapshot.
6 . The method of claim 1 , wherein each second-level operation of the plurality of second-level operations is performed by a processing thread of a plurality of processing threads.
7 . The method of claim 6 , further comprising coordinating the plurality of second-level operations by using a shared database, wherein the shared database is updated by the plurality of processing threads corresponding to the plurality of second-level operations independently.
8 . The method of claim 6 , wherein the first number is twice a total number of available processing threads for performing the second-level operations in the source file system.
9 . The method of claim 1 , wherein the traversal of the tree structure from the top level of the tree structure downward stops at a tree level containing at least the first number of the key-value pairs.
10 . The method of claim 9 , wherein the traversal of the tree structure is performed recursively.
11 . 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 cross-region replication between a source file system in a source region and a target file system in a target region, the first cross-region replication being one of a plurality of parallel replications comprising i) a first-level operation comprising extracting deltas representing differences between a first snapshot and a second snapshot of the source file system and ii) a plurality of second-level operations comprising partitioning, in parallel, respective key-value pairs into key ranges, and a first result of the first-level operation corresponding to a second result of the plurality of second-level operations;
performing, by the computing system, the first-level operation by extracting the deltas representing the differences between the first snapshot and the second snapshot of the source file system, the deltas being stored in a tree structure associated with the source file system in the source region, the tree structure having multiple levels of hierarchy comprising more nodes in a lower hierarchal level than a higher hierarchal level, and the first snapshot and the second snapshot comprising the respective sets of key-value pairs;
partitioning, by the computing system, the respective sets of key-value pairs identified in the first-level operation into a first number of key partitions by traversing the tree structure from a top level of the tree structure downward, the first number being configured to be adjusted for each replication cycle; and
performing, by the computing system, the plurality of second-level operations on the first number of key partitions in parallel, each second-level operation of the plurality of second-level operations being performed on a key partition of the first number of key partitions.
12 . The non-transitory computer-readable medium of claim 11 , wherein each key partition of the key partitions comprises at least one key-value pair stored in the tree structure associated with the source file system.
13 . The non-transitory computer-readable medium of claim 11 , wherein each first-level operation extracts a portion of the deltas between the first snapshot and the second snapshot, and wherein the second result comprises a combined result of the plurality of second-level operations, and the combined result is equivalent to the first result.
14 . The non-transitory computer-readable medium of claim 11 , wherein each second-level operation of the plurality of second-level operations is performed by a processing thread of a plurality of processing threads.
15 . The non-transitory computer-readable medium of claim 14 , the operations further comprising coordinating the plurality of second-level operations by using a shared database, wherein the shared database is updated by the plurality of processing threads corresponding to the plurality of second-level operations independently.
16 . A computing 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 cross-region replication between a source file system in a source region and a target file system in a target region, the first cross-region replication being one of a plurality of parallel replications comprising i) a first-level operation comprising extracting deltas representing differences between a first snapshot and a second snapshot of the source file system and ii) a plurality of second-level operations comprising partitioning, in parallel, respective key-value pairs into key ranges, and a first result of the first-level operation corresponding to a second result of the plurality of second-level operations;
perform the first-level operation by extracting the deltas representing the differences between the first snapshot and the second snapshot of the source file system, the deltas being stored in a tree structure associated with the source file system in the source region, the tree structure having multiple levels of hierarchy comprising more nodes in a lower hierarchal level than a higher hierarchal level, and the first snapshot and the second snapshot comprising the respective sets of key-value pairs;
partition the respective sets of key-value pairs identified in the first-level operation into a first number of key partitions by traversing the tree structure from a top level of the tree structure downward, the first number being configured to be adjusted for each replication cycle; and
perform the plurality of second-level operations on the first number of key partitions in parallel, each second-level operation of the plurality of second-level operations being performed on a key partition of the first number of key partitions.
17 . The computing system of claim 16 , wherein each first-level operation extracts a portion of the deltas between the first snapshot and the second snapshot, and wherein the second result comprises a combined result of the plurality of second-level operations, and the combined result is equivalent to the first result.
18 . The computing system of claim 16 , wherein each second-level operation of the plurality of second-level operations is performed by a processing thread of a plurality of processing threads.
19 . The computing system of claim 18 , wherein the computing system is further caused to coordinate the plurality of second-level operations by using a shared database, wherein the shared database is updated by the plurality of processing threads corresponding to the plurality of second-level operations independently.
20 . The computing system of claim 16 , wherein the traversal of the tree structure from the top level of the tree structure downward stops at a tree level containing at least the first number of the key-value pairs.