EFFICIENTLY COMMITTING LARGE TRANSACTIONS IN A GRAPH DATABASE

• US 20170228418A1
• Filed: 09/14/2016
• Published: 08/10/2017
• Est. Priority Date: 02/04/2016
• Status: Active Grant

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Levin, Roy, Roitman, Haggai
• Granted Patent: US 10,061,799 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A computer-implemented method includes receiving a transaction, where the transaction includes a plurality of operations and is applicable to a graph database. The transaction is represented by a transaction graph, which is a dependency graph representing dependencies among the plurality of operations of the transaction. The transaction graph is partitioned, by a computer processor, into two or more transaction subgraphs. Each of the two or more transaction subgraphs includes two or more operations of the transaction, and each of the two or more transaction subgraphs is a dependency graph representing dependencies among the two or more operations of the transaction subgraph. The two or more transaction subgraphs are independent of one another. The two or more transaction subgraphs are applied to the graph database in parallel, where applying each transaction subgraph to the graph database includes applying the two or more operations of the transaction subgraph to the graph database.

Claims

1. A computer-implemented method, comprising:

receiving a transaction comprising a plurality of operations, the transaction applicable to a graph database;

representing the transaction by a transaction graph, the transaction graph being a dependency graph representing dependencies among the plurality of operations of the transaction;

partitioning, by a computer processor, the transaction graph into two or more transaction subgraphs, each of the two or more transaction subgraphs comprising two or more operations of the transaction, each of the two or more transaction subgraphs being a dependency graph representing dependencies among the two or more operations of the transaction subgraph, and the two or more transaction subgraphs being independent of one another; and

applying the two or more transaction subgraphs to the graph database in parallel, wherein applying each transaction subgraph to the graph database comprises applying the two or more operations of the transaction subgraph to the graph database.

2. The computer-implemented method of claim 1, wherein the partitioning the transaction graph into two or more transaction subgraphs comprises:

partitioning the transaction graph into two or more intermediate transaction subgraphs;

identifying one or more crossover edges crossing between a first intermediate transaction subgraph and a second intermediate transaction subgraph, the first and second intermediate transaction subgraphs being distinct and belonging to the two or more intermediate transaction subgraphs;

extracting from the first and second intermediate transaction subgraphs each vertex at which at least one of the one or more crossover edges terminates; and

inserting each extracted vertex into a residual subgraph.

3. The computer-implemented method of claim 2, further comprising synchronously applying the residual subgraph to the graph database.

4. The computer-implemented method of claim 1, wherein the partitioning the transaction graph into two or more transaction subgraphs comprises applying a balanced partitioning algorithm to the transaction graph.

5. The computer-implemented method of claim 4, wherein the applying the balanced partitioning algorithm comprises executing one or more normalized cuts on the transaction graph.

6. The computer-implemented method of claim 1, further comprising:

determining that the transaction exceeds a threshold size; and

performing the partitioning and the applying based on the transaction exceeding the threshold size.

7. The computer-implemented method of claim 1, wherein the graph database represents a social network.

8. A system comprising:

a memory having computer readable instructions; and

one or more processors for executing the computer readable instructions, the computer readable instructions comprising;

receiving a transaction comprising a plurality of operations, the transaction applicable to a graph database;

representing the transaction by a transaction graph, the transaction graph being a dependency graph representing dependencies among the plurality of operations of the transaction;

partitioning the transaction graph into two or more transaction subgraphs, each of the two or more transaction subgraphs comprising two or more operations of the transaction, each of the two or more transaction subgraphs being a dependency graph representing dependencies among the two or more operations of the transaction subgraph, and the two or more transaction subgraphs being independent of one another; and

applying the two or more transaction subgraphs to the graph database in parallel, wherein applying each transaction subgraph to the graph database comprises applying the two or more operations of the transaction subgraph to the graph database.

9. The system of claim 8, wherein the partitioning the transaction graph into two or more transaction subgraphs comprises:

partitioning the transaction graph into two or more intermediate transaction subgraphs;

identifying one or more crossover edges crossing between a first intermediate transaction subgraph and a second intermediate transaction subgraph, the first and second intermediate transaction subgraphs being distinct and belonging to the two or more intermediate transaction subgraphs;

extracting from the first and second intermediate transaction subgraphs each vertex at which at least one of the one or more crossover edges terminates; and

inserting each extracted vertex into a residual subgraph.

10. The system of claim 9, the computer readable instructions further comprising synchronously applying the residual subgraph to the graph database.

11. The system of claim 8, wherein the partitioning the transaction graph into two or more transaction subgraphs comprises applying a balanced partitioning algorithm to the transaction graph.

12. The system of claim 11, wherein the applying the balanced partitioning algorithm comprises executing one or more normalized cuts on the transaction graph.

13. The system of claim 8, the computer readable instructions further comprising:

determining that the transaction exceeds a threshold size; and

performing the partitioning and the applying based on the transaction exceeding the threshold size.

14. The system of claim 8, wherein the graph database represents a social network.

15. A computer program product for applying a transaction to a graph database, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform a method comprising:

receiving a transaction comprising a plurality of operations, the transaction applicable to a graph database;

representing the transaction by a transaction graph, the transaction graph being a dependency graph representing dependencies among the plurality of operations of the transaction;

partitioning the transaction graph into two or more transaction subgraphs, each of the two or more transaction subgraphs comprising two or more operations of the transaction, each of the two or more transaction subgraphs being a dependency graph representing dependencies among the two or more operations of the transaction subgraph, and the two or more transaction subgraphs being independent of one another; and

applying the two or more transaction subgraphs to the graph database in parallel, wherein applying each transaction subgraph to the graph database comprises applying the two or more operations of the transaction subgraph to the graph database.

16. The computer program product of claim 15, wherein the partitioning the transaction graph into two or more transaction subgraphs comprises:

partitioning the transaction graph into two or more intermediate transaction subgraphs;

identifying one or more crossover edges crossing between a first intermediate transaction subgraph and a second intermediate transaction subgraph, the first and second intermediate transaction subgraphs being distinct and belonging to the two or more intermediate transaction subgraphs;

extracting from the first and second intermediate transaction subgraphs each vertex at which at least one of the one or more crossover edges terminates; and

inserting each extracted vertex into a residual subgraph.

17. The computer program product of claim 16, the method further comprising synchronously applying the residual subgraph to the graph database.

18. The computer program product of claim 15, wherein the partitioning the transaction graph into two or more transaction subgraphs comprises applying a balanced partitioning algorithm to the transaction graph.

19. The computer program product of claim 18, wherein the applying the balanced partitioning algorithm comprises executing one or more normalized cuts on the transaction graph.

20. The computer program product of claim 15, wherein the graph database represents a social network.