Graph database system

Patent metadata

Field	Value
Publication number	US-11442920-B2
Application number	US-201916457467-A
Country	US
Kind code	B2
Filing date	Jun 28, 2019
Priority date	Jun 28, 2019
Publication date	Sep 13, 2022
Grant date	Sep 13, 2022

Abstract

Systems and methods that describe a graph database system with an online component and an offline component, are provided. Write events that modify a first graph in a real-time graph database included in the online component are received. Graph logs that include changes to the first graph in the real-time graph database caused by the write events are generated. The graph logs are transmitted to an offline component of the graph database system in a chronological order. A second graph in the offline component is modified using the graph logs. The first graph and the second graph are instantiated using a graph schema.

First claim

What is claimed is:

1. A method comprising:
receiving, at a graph database system that includes a first graph in a real-time graph database included in an online component and a second graph in an offline graph database included in an offline component, at least one event that modifies the first graph, wherein the first graph and the second graph are based on a graph schema;
generating graph logs that include changes to the first graph in the real-time graph database caused by at least one transaction in the at least one event, wherein the changes include mutations to one or more vertices in a plurality of vertices in the first graph and to one or more edges in a plurality of edges in the first graph;
transmitting the graph logs to the offline component in a chronological order;
modifying the second graph in the offline graph database using the graph logs;
generating snapshots of the second graph at configurable time intervals;
determining that the first graph includes corrupted data in at least one vertex in the plurality of vertices at a first point in time;
identifying the snapshot from the snapshots of the second graph that was generated at a second point in time prior to the first point in time;
replaying a subset of graph logs from the graph logs on the snapshot from the snapshots, wherein the subset of graph logs from the graph logs is from the second point in time to the first point in time;
validating data in the second graph based on data generated using the subset of graph logs and the snapshot during the replaying;
transmitting the snapshot and the subset of graph logs from the offline component to the online component in the chronological order;
updating the first graph with the snapshot and the subset of graph logs used to validate the data in the second graph; and
recovering the first graph based on the updating.

2. The method of claim 1 , wherein the plurality of vertices are connected by the plurality of edges, a vertex in the plurality of vertices including metadata, a vertex identifier and at least one vertex property and an edge in the plurality of edges including a relationship between at least two vertices in the plurality of vertices, edge metadata, and at least one edge property.

3. The method of claim 2 , wherein a change in the changes is to the at least one vertex property in the vertex or to the at least one edge property in the edge.

4. The method of claim 1 , further comprising:
dividing the first graph into a first cluster and a second cluster, wherein dividing the first graph further comprises:
applying a hash function to the plurality of vertices;
generating a result based on the applying; and
including first vertices from the plurality of vertices in the first cluster when the result is a first result; or
including second vertices from the plurality of vertices in the second cluster when the result is a second result.

5. The method of claim 1 , wherein a vertex in the plurality of vertices in the first graph includes a vertex identifier that uniquely identifies the vertex from other vertices in the plurality of vertices.

6. The method of claim 1 , further comprising:
determining second corrupted data in the first graph; and
recovering data in the first graph using a second snapshot from the snapshots that was generated prior to a point in time that the corrupted data was determined and a graph log in the graph logs.

7. The method of claim 1 , further comprising:
determining a value in a vertex of the snapshot;
generating a graph log that includes the value and an operation that inserts the value into the first graph; and
updating the first graph with the value using the graph log.

8. The method of claim 1 , further comprising:
determining that the first graph includes second corrupted data in a second vertex in the plurality of vertices;
instantiating a new version of the first graph;
transmitting the graph logs from the offline component to the online component in the chronological order;
inserting data in the graph logs into the new version of the first graph using operations in the graph logs; and
recovering the first graph based on the inserting.

9. The method of claim 1 ,
wherein the method further comprises:
retrieving a vertex property of a vertex in the second graph at the first point in time; and
validating the vertex property.

10. A system comprising:
at least one memory configured to store a graph database system comprising a first graph in a real-time graph database included in an online component and a second graph in an offline graph database included in an offline component, wherein the first graph and the second graph are based on a graph schema; and
a processor coupled to the at least one memory and configured to perform operations that cause the graph database system to:
receive at least one event that modifies the first graph;
generate graph logs that include changes to the first graph in the real-time graph database caused by at least one transaction in the at least one event, wherein the changes include mutations to one or more vertices in a plurality of vertices in the first graph and to one or more edges in a plurality of edges in the first graph;
transmit the graph logs to the offline component in a chronological order;
modify the second graph in the offline graph database using the graph logs;
generate snapshots of the second graph at configurable time intervals;
determine that the first graph includes corrupted data in at least one vertex in the plurality of vertices at a first point in time;
identify a snapshot from the snapshots of the second graph that was generated at a second point in time prior to the first point in time;
replay a subset of graph logs from the graph logs on the snapshot from the snapshots, wherein the subset of graph logs from the graph logs is from the second point in time to the first point in time;
validate data in the second graph based on data generated using the subset of graph logs and the snapshot during the replaying;
transmit the snapshot and the subset of graph logs from the offline component to the online component in the chronological order;
update the first graph with the snapshot and the subset of graph logs used to validate the data in the second graph; and
recover the first graph based on the updating.

11. The system of claim 10 , wherein the plurality of vertices are connected by the plurality of edges, a vertex in the plurality of vertices including metadata, a vertex identifier and at least one vertex property and an edge in the plurality of edges including a relationship between at least two vertices in the plurality of vertices, edge metadata, and at least one edge property.

12. The system of claim 11 , wherein a change in the changes is to the at least one vertex property in the vertex or to the at least one edge property in the edge.

13. The system of claim 10 , wherein the processor is further configured to perform operations that cause the graph database system to divide the first graph into a first cluster and a second cluster by:
applying a hash function to the plurality of vertices;
generating a result based on the applying; and
including first vertices from the plurality of vertices in the first cluster when the result is a first result; or
including second vertices from the plurality of vertices in the second cluster when the result is a second result.

14. The system of claim 10 , wherein a vertex in the plurality of vertices in the first graph includes a vertex identifier that uniquely identifies the vertex from other vertices in the plurality of ver

Assignees

• Paypal Inc

Inventors

• Zang Meng
• Li Xin
• Yue Ying
• Wang Lei
• Zuo Quin
• Zhang Jun
• Jia Tingjie
• Zheng Ke
• Guo Junshi
• Chen Chaoyi
• Fu Qinghai
• Zhu Wenbing
• Zhang Haoran
• Huang Zhe
• Yu Yang
• Anand Siddarth
• Yun Xiaohan
• Kourjanski Mikhail
• Kutsyy Vadim
• Yang Zhenyin

Classifications

• G06F16/212

  with details for data modelling support · CPC title

• G06F16/9027

  Trees · CPC title

• G06F2201/84

  Using snapshots, i.e. a logical point-in-time copy of the data · CPC title

• G06F7/32 Primary

  Merging, i.e. combining data contained in ordered sequence on at least two record carriers to produce a single carrier or set of carriers having all the original data in the ordered sequence {merging methods in general}(G06F7/36 takes precedence) · CPC title

• G06F11/3476

  Data logging (G06F11/14, G06F11/2205 take precedence) · CPC title