# US 11,442,920 B2 · Graph database system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,442,920 B2
- Document ID: US11442920B2
- Status: Granted
- Kind: B2
- Application number: 16/457,467
- Filed: 2019-06-28
- Published: 2020-12-31
- Granted: 2022-09-13
- Earliest claimed: 2019-06-28
- Assignees: Paypal, Inc.
- Applicants: Paypal, Inc.
- Inventors: Meng Zang; Xin Li; Ying Yue; Lei Wang; Quin Zuo; Jun Zhang; Tingjie Jia; Ke Zheng; Junshi Guo; Chaoyi Chen; Qinghai Fu; Wenbing Zhu; Haoran Zhang; Zhe Huang; Yang Yu; Siddarth Anand; Xiaohan Yun; Mikhail Kourjanski; Vadim Kutsyy; Zhenyin Yang
- Web page: https://patentgrep.com/patent/US11442920B2

## CPC

- G06F 7/32: 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)
- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 7/14: Merging, i.e. combining at least two sets of record carriers each arranged in the same ordered sequence to produce a single set having the same ordered sequence
- G06F 11/1469: {Backup restoration techniques}
- G06F 11/1471: involving logging of persistent data for recovery
- G06F 11/3476: {Data logging (G06F11/14, G06F11/2205 take precedence)}
- G06F 16/212: {with details for data modelling support}
- G06F 16/9014: {hash tables}
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 16/9027: {Trees}
- G06F 2201/80: Database-specific techniques
- G06F 2201/805: Real-time
- G06F 2201/84: Using snapshots, i.e. a logical point-in-time copy of the data
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 1)

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.

### Claim 9 (depends on 1)

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.

### Claim 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.

### Claim 11 (depends on 10)

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.

### Claim 12 (depends on 11)

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.

### Claim 13 (depends on 10)

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.

### Claim 14 (depends on 10)

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 vertices.

### Claim 15 (depends on 10)

The system of claim 10, wherein the processor is further configured to perform operations that cause the graph database system to:
determine second corrupted data in the first graph; and
recover 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.

### Claim 16 (depends on 10)

The system of claim 10, wherein the processor is further configured to perform operations that cause the graph database system to:
determine a value in a vertex of the snapshot;
generate a graph log that includes the value and an operation that inserts the value into the first graph; and
update the first graph with the value using the graph log.

### Claim 17 (depends on 10)

The system of claim 10, wherein the processor is further configured to perform operations that cause the graph database system to:
determine that the first graph includes second corrupted data in a second vertex in the plurality of vertices;
instantiate a new version of the first graph;
transmit the graph logs from the offline component to the online component in the chronological order;
insert data in the graph logs into the new version of the first graph; and
recover the first graph based on the inserting.

### Claim 18

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;
replaying a subset of graph logs from the graph logs on a snapshot from the snapshots;
validating data in the second graph based on data generated using the subset of graph logs and the snapshot during the replaying;
determining that the first graph includes corrupted data in at least one 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.

### Claim 19 (depends on 18)

The method of claim 18, 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.

### Claim 20 (depends on 19)

The method of claim 19, 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.