Transaction Processing Method and Apparatus

• US 20190324760A1
• Filed: 06/28/2019
• Published: 10/24/2019
• Est. Priority Date: 12/30/2016
• Status: Active Grant

• Current Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: Hou, Jie, Lin, Chengyong, Li, Yan, Dai, Longfei, Dong, Wenxia, Song, Yuezhong
• Granted Patent: US 11,176,086 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 9/28 Enhancement of operational speed, e.g. by using several microcontrol devices operating in parallel
• CPC Class Codes: G06F 9/30145 Instruction analysis, e.g. decoding, instruction word fields
• CPC Class Codes: G06F 9/3822 Parallel decoding, e.g. parallel decode units
• CPC Class Codes: G06F 9/3887 controlled by a single instruction for multiple data lanes [SIMD]

Abstract

A network device obtains, from a transaction queue, a plurality of transactions that do not conflict with each other, and performs reverse shallow copying in parallel for the transactions that do not conflict, to generate a plurality of temporary trees corresponding to the plurality of transactions. Because the plurality of transactions does not conflict with each other, processing the transactions in parallel can ensure accurate and proper transaction processing. In addition, generating the temporary trees in a reverse shallow copying manner can effectively reduce consumption of time and memory. Further, processing of the plurality of transactions is implemented by merging the plurality of temporary trees.

Claims

1. A transaction processing method implemented by a network device, wherein a transaction comprises a series of operations on a tree data structure, wherein the tree data structure comprises a base tree, and wherein the transaction processing method comprises:

obtaining M transactions from a transaction queue, wherein the M transactions are transactions that perform an update on a same base tree, wherein a first transaction and a second transaction are any two transactions in the M transactions that do not conflict wherein a conflict occurs when a common subtree of the first transaction is either a father or a child of a common subtree of the second transaction, wherein a common part of subtrees formed by operations performed on the base tree in any transaction constitutes a common subtree of the transaction, and wherein M is an integer greater than or equal to two;

performing reverse shallow copying in parallel for the M transactions to generate M temporary trees corresponding to the M transactions, wherein a temporary tree corresponding to each transaction comprises a tree that is formed after the transaction performs an update on the base tree;

merging M temporary trees; and

replacing the base tree with a merged temporary tree.

2. The transaction processing method of claim 1, wherein merging the M temporary trees comprises:

using a first temporary tree as a first merged tree in the M temporary tree;

merging an i^th temporary tree into an (i−

1)^th merged tree to obtain an i^th merged tree in the M temporary trees wherein the (i-1)^th merged tree is obtained by merging the first temporary tree to an (i−

1)^th temporary tree, wherein i is an integer, and wherein i is greater than or equal to two and is less than or equal to M; and

using an M^th merged tree as the merged temporary tree.

3. The transaction processing method of claim 2, wherein merging the i^th temporary tree into the (i−

1)^th merged tree to obtain the i^th merged tree comprises;

comparing

a path of a common subtree of a transaction corresponding to each temporary tree with a path of a common subtree of a transaction corresponding to the i^th temporary tree to obtain an initial to-be-merged path of the i^th temporary tree relative to the temporary tree each temporary tree in the first temporary tree to the (i−

1)^th temporary tree;

determining;

a shortest initial to-be-merged path as a to-be-merged path of the i^th temporary tree relative to the (i−

1)^th merged tree; and

merging the to-be-merged path into the (i−

1)^th merged tree to obtain the i^th merged tree.

4. The transaction processing method of claim 1, wherein obtaining the M transactions from the transaction queue comprises obtaining, using a head of the transaction queue as a start point, a first transaction to the M^th transaction successively from the transaction queue.

5. The transaction processing method of claim 4, wherein after the network device obtains a (k−

1)^th transaction from the transaction queue and before the network device obtains a k^th transaction, the transaction processing method further comprises determining that the k^th transaction does not conflict with any transaction in the first transaction to the (k−

1)^th transaction, wherein k is an integer and wherein k is greater than or equal to two and is less than or equal to M.

16. The transaction processing method of claim 1, wherein the transaction comprises a read operation on the base tree in the tree data structure.

17. The transaction processing method of claim 1, wherein the transaction comprises a write operation on the base tree in the tree data structure.

18. The transaction processing method of claim 1, wherein the transaction comprises a group of update operations on different subtrees in the base tree.

6. A network device comprising;

a non transitory computer-readable memory comprising an instruction and

a processor coupled to the non-transitory computer-readable memory and configured to execute the instruction to configure the network device to;

obtain M transactions from a transaction queue, wherein the M transactions are transactions that perform an update on a same base tree, wherein a first transaction and a second transaction are any two transactions in the M transactions that do not conflict, wherein a conflict occurs when a common subtree of the first transaction is either a father or a child of a common subtree of the second transaction, wherein a common part of subtrees formed by operations performed on the base tree in any transaction constitutes a common subtree of the transaction, and wherein M is an integer greater than or equal to two;

perform reverse shallow copying in parallel for the M transactions to generate M temporary trees corresponding to the M transactions, wherein a temporary tree corresponding to each transaction comprises a tree that is formed after the transaction performs an update on the base tree;

merge the M temporary trees; and

replace the base tree with a merged temporary tree.

7. The network device of claim 6, wherein the processor is further configured to execute the instruction to configure the network device to;

use a first temporary tree as a first merged tree in the M temporary trees;

merge an i^th temporary tree into an (i−

1)^th merged tree to obtain an i^th merged tree, wherein the (i−

1)^th merged tree is obtained by merging the first temporary tree to an (i−

1)^th temporary tree, wherein i is an integer, and wherein i is greater than or equal to two and is less than or equal to M; and

use an M^th merged tree as the merged temporary tree.

8. The network device of claim 7, wherein the processor is further configured to execute the instruction to configure the network device to;

compare a path of a common subtree of a transaction corresponding to each temporary tree with a path of a common subtree of a transaction corresponding to the i^th temporary tree to obtain an initial to-be-merged path of the i^th temporary tree relative to each temporary tree for each temporary tree in the first temporary tree to the (i−

1)^th temporary tree;

determine a shortest initial to-be-merged path as a to-be-merged path of the i^th temporary tree relative to the (i−

1)^th merged tree; and

merge the to-be-merged path into the (i−

1)^th merged tree to obtain the i^th merged tree.

9. The network device of claim 6, wherein the processor is further configured to execute the instruction to configure the network device to obtain, by using a head of the transaction queue as a start point, the first transaction to an M^th transaction successively from the transaction queue.

10. The network device of claim 9, wherein after the network device is configured to obtain a (k−

1)^th transaction from the transaction queue and before the network device is configured to obtain a k^th transaction, the network device is further configured to determine that the k^th transaction does not conflict with any transaction in the first transaction to the (k−

1)^th transaction, wherein k is an integer, and wherein k is greater than or equal to two and is less than or equal to M.

19. The network device of claim 6, wherein the M transactions comprise a read operation and a write operation.

11. A network device, comprising;

a memory configured to store a transaction queue;

a scheduler configured to obtain M transactions from the transaction queue, wherein the M transactions are transactions that perform an update on a same base tree, wherein a first transaction and a second transaction are any two transactions in the M transactions that do not conflict, wherein a conflict occurs when common subtree of the first transaction is either a father or a child of a common subtree of the second transaction, wherein a common part of subtrees form formed by operations performed on the base tree in any transaction constitutes a common subtree of the transaction, and wherein M is an integer greater than or equal to two; and

a processor that comprises at least M processor cores and that has a multi-task parallel processing capability, wherein the processor is configured to;

perform reverse shallow copying in parallel for the M transactions to generate M temporary trees corresponding to the M transactions, wherein a temporary tree corresponding to each transaction comprises a tree that is formed after each transaction performs an update on the base tree;

merge the M temporary trees; and

replace the base tree with a merged temporary tree.

12. The network device of claim 11, wherein the processor is further configured to:

use a first temporary tree as a first merged tree in the M temporary trees;

merge an i^th temporary tree into an (i−

1)^th to obtain an i^th merged tree in the M temporary trees, wherein the (i−

1)^th merged tree is obtained by merging the first temporary tree to the (i−

1)^th temporary tree, wherein i is an integer, and wherein i is greater than or equal to two and is less than or equal to M; and

use an M^th merged tree as the merged temporary tree.

13. The network device of claim 12, wherein the processor is further configured to:

compare a path of a common subtree of a transaction corresponding to each temporary tree with a path of a common subtree of a transaction corresponding to the i^th temporary tree to obtain an initial to-be-merged path of the i^th temporary tree relative to each temporary tree for each temporary tree in the first temporary tree to the (i−

1)^th temporary tree;

determine a shortest initial to-be-merged path as a to-be-merged path of the i^th temporary tree relative to the (i−

1)^th merged tree; and

merge the to-be-merged path into the (i−

1)^th merged tree to obtain an i^th merged tree.

14. The network device of claim 11, wherein the scheduler is further configured to obtain, by using a head of the transaction queue as a start point, the first transaction to an M^th transaction successively from the transaction queue.

15. The network device of claim 14, wherein after the scheduler is configured to obtain a (k−

1)^th transaction from the transaction queue and before the scheduler is configured to obtain a k^th transaction, the scheduler is further configured to determine that the k^th transaction does not conflict with any transaction in the first transaction to the (k−

1)^th transaction, wherein k is an integer, and wherein k is greater than or equal to two and is less than or equal to M.

20. The network device of claim 11, wherein the M transactions comprise a read operation and a write operation.