IP Library › Granted Patent US 11,281,657

Granted Patent B2

US 11,281,657 · App. 16/777,692 · Granted Mar 22, 2022

Event-driven identity graph conflation

Inventors: Deepak Goyal (Chandigarh, IN); Giridhar Addepalli (Bangaluru, IN); Sebastien Jean-Maurice Olivier Pehu (Novato, CA); Saigopal Thota (Fremont, CA); Mridul Jain (Cupertino, CA); Navinder Pal Singh Brar (Abohar, IN)

Assignee: WALMART APOLLO, LLC

G06F16/2365 G06F16/215 G06F16/27

View Patent ↗

Loading inventors, assignments & file history…

Monitor This Case

Get email alerts when status or documents change.

Order Certified Copies

Most orders are placed with the USPTO same day — all within 24 business hours.

Order via The Patent Place →

Pre-filled with this patent's details

Quick Facts

Patent No.: US 11,281,657
App. No.: 16/777,692
Granted: Mar 22, 2022
Kind: B2

External Links

USPTO Patent Center↗ Full Patent PDF↗

Abstract

A distributed system including multiple processing nodes. The distributed system can perform certain acts. The acts can include receiving a first conflation event identifying a first node and a second node. The first node can be part of a first set. The first set can include a sole parent node stored at a first processing node of the multiple processing nodes. The second node can be part of a second set. The second set can include a sole parent node stored at a second processing node of the multiple processing nodes. The first and second sets can be disjoint sets. The first conflation event can be received at an event-driven stream application at one of the multiple processing nodes. The acts also can include conflating the first set and the second set into a conflated set. The conflated set can include the first and second nodes. The conflated set can include a sole parent node. Data for each node of the conflated set can be stored at the sole parent node of the conflated set at a processing node of the multiple processing nodes. Other embodiments are disclosed.

Claims (223)

1. A distributed system comprising:

one or more processors;

multiple processing nodes running on the one or more processors,

wherein the one or more processors are configured to perform:

receiving a first conflation event identifying a first node and a second node, wherein the first node is part of a first set, the first set comprises a sole parent node stored at a first processing node of the multiple processing nodes, the second node is part of a second set, the second set comprises a sole parent node stored at a second processing node of the multiple processing nodes, the first and second sets are disjoint sets, and the first conflation event is received at an event-driven stream application at one of the multiple processing nodes; and

conflating the first set and the second set into a conflated set, wherein the conflated set comprises the first and second nodes, wherein the conflated set comprises a sole parent node, and data for each node of the conflated set is stored at the sole parent node of the conflated set at a processing node of the multiple processing nodes,

wherein:

the first set, the second set, and the conflated set are each a respective graph;

the sole parent node of the conflated set is a first one of the sole parent node of the first set or the sole parent node of the second set;

a second one of the sole parent node of the first set or the sole parent node of the second set is a child node of the first one in the conflated set;

the first one is lexicographically smaller than the second one; and

the first set, the second set, and the conflated set correspond to an identity of a user.

2. The distributed system of claim 1 , wherein:

the first node is the sole parent node of the first set;

the second node is the sole parent node of the second set;

the first node is lexicographically smaller than the second node;

data for the first node are stored at the first node;

the second set further comprises a third node that is a child node mapped to the second node;

the third node is stored at a third processing node of the multiple processing nodes; and

data for the second node and data for the third node are stored at the second node.

3. The distributed system of claim 2 , wherein:

the first conflation event is received at the first processing node; and

conflating the first set and the second set into the conflated set further comprises:

changing a state of the first node to a conflating state;

sending, from the first node to the second node, a root event identifying the first node;

determining, at the second node, that the first node is lexicographically smaller than the second node;

changing a state of the second node to a packed state;

sending, from the second node to the first node, a data event comprising the data for the second node and the data for the third node;

storing the data for the second node and the data for the third node at the first node;

changing the state of the first node to a normal state;

sending, from the first node to each of the second node and the third node, a change-root event identifying the first node;

deleting the data for the second node and the data for the third node from the second node;

setting the second node to be a child node mapped to the first node;

changing the state of the second node to a normal state; and

setting the third node to be a child node mapped to the first node.

4. The distributed system of claim 2 , wherein:

the first conflation event is received at the second processing node; and

conflating the first set and the second set into the conflated set further comprises:

changing a state of the second node to a conflating state;

sending, from the second node to the first node, a first root event identifying the second node;

determining, at the first node, that the first node is lexicographically smaller than the second node;

changing a state of the first node to the conflating state;

sending, from the first node to the second node, a second root event identifying the first node;

changing the state of the second node to a packed state;

sending, from the second node to the first node, a data event comprising the data for the second node and the data for the third node;

storing the data for the second node and the data for the third node at the first node;

changing the state of the first node to a normal state;

sending, from the first node to each of the second node and the third node, a change-root event identifying the first node;

deleting the data for the second node and the data for the third node from the second node;

setting the second node to be a child node mapped to the first node;

changing the state of the second node to a normal state; and

setting the third node to be a child node mapped to the first node.

5. The distributed system of claim 2 , wherein:

the first set further comprises a fourth node that is a child node mapped to the first node;

the fourth node is stored at a fourth processing node of the multiple processing nodes; and

data for the fourth node are stored at the first node.

6. The distributed system of claim 1 , wherein:

the first conflation event is received at the first processing node; and

conflating the first set and the second set into the conflated set further comprises:

changing a state of the first node to a conflating state based on the first conflation event;

receiving, while the state of the first node is the conflating state, a second conflation event at the first processing node identifying the first node and a third node;

adding the second conflation event to a to-be-conflated queue at the first node; and

when the state of the first node changes to a normal state, changing a state of the first node to the conflating state based on the second conflation event.

7. The distributed system of claim 1 , wherein:

the first node is the sole parent node of the first set;

the second node is the sole parent node of the second set;

the first conflation event is received at the first processing node; and

conflating the first set and the second set into the conflated set further comprises:

changing a state of the first node to a conflating state based on the first conflation event;

determining, at the first node, a first conflation hash identifier for the first conflation event;

receiving, while the state of the first node is the conflating state, a second conflation event at a third processing node identifying the second node and a third node, wherein the third node is stored at the third processing node, the third node is a sole parent node of a third set, and the first set, the second set, and the third set are disjoint sets;

changing a state of the third node to the conflating state based on the second conflation event;

determining, at the third node, a second conflation hash identifier for the second conflation event;

sending, from the first node to the second node, a first root event identifying the first node and the first conflation hash identifier;

determining, at the second node, that the first node is lexicographically smaller than the second node;

changing a state of the second node to a packed state;

sending, from the third node to the second node, a second root event identifying the third node and the second conflation hash identifier;

sending, from the second node to the first node, a data event comprising the data for the second node;

sending, from the second node to the third node, a concurrent conflation event comprising the second conflation hash identifier;

sending one or more retries up to a retry limit, from the third node to the second node, for the second root event; and

when the state of the second node changes to a normal state and one of the one or more retries is received at the second node, changing a state of the second node to the conflating state based on the second conflation event.

8. The distributed system of claim 7 , wherein:

the retry limit is randomized to overcome cyclic deadlocks.

9. The distributed system of claim 1 , wherein:

the first set further comprises a third node;

the third node is stored at a third processing node of the multiple processing nodes;

the third node is the sole parent node of the first set;

the second set further comprises a fourth node;

the fourth node is stored at a fourth processing node of the multiple processing nodes;

the fourth node is the sole parent node of the second set;

the first node is a child node mapped to the third node;

the second node is a child node mapped to the fourth node;

data for the first node and data for the third node are stored at the third node; and

data for the second node and data for the fourth node are stored at the fourth node.

10. The distributed system of claim 9 , wherein:

the first conflation event is received at the first processing node; and

conflating the first set and the second set into the conflated set further comprises:

determining, at the first node, that a parent of the first node is the third node;

sending, from the first node to the third node, a second conflation event identifying the third node and the second node;

changing a state of the third node to a conflating state;

sending, from the third node to the second node, a first root event identifying the third node;

determining, at the second node, that a parent of the second node is the fourth node;

sending, from the second node to the fourth node, a second root event identifying the third node;

determining, at the fourth node, that the third node is lexicographically smaller than the fourth node;

changing a state of the fourth node to a packed state;

sending, from the fourth node to the third node, a data event comprising the data for the second node and the data for the fourth node;

storing the data for the second node and the data for the fourth node at the third node;

changing the state of the third node to a normal state;

sending, from the third node to each of the second node and the fourth node, a change-root event identifying the third node;

deleting the data for the second node and the data for the fourth node from the fourth node;

setting the fourth node to be a child node mapped to the third node;

changing the state of the fourth node to a normal state; and

setting the second node to be a child node mapped to the third node.

11. A method comprising:

receiving a first conflation event identifying a first node and a second node, wherein the first node is part of a first set, the first set comprises a sole parent node stored at a first processing node of multiple processing nodes of a distributed system, the second node is part of a second set, the second set comprises a sole parent node stored at a second processing node of the multiple processing nodes, the first and second sets are disjoint sets, and the first conflation event is received at an event-driven stream application at one of the multiple processing nodes; and

wherein:

the first set, the second set, and the conflated set are each a respective graph;

the sole parent node of the conflated set is a first one of the sole parent node of the first set or the sole parent node of the second set;

a second one of the sole parent node of the first set or the sole parent node of the second set is a child node of the first one in the conflated set;

the first one is lexicographically smaller than the second one; and

the first set, the second set, and the conflated set correspond to an identity of a user.

12. The method of claim 11 , wherein:

the first node is the sole parent node of the first set;

the second node is the sole parent node of the second set;

the first node is lexicographically smaller than the second node;

data for the first node are stored at the first node;

the second set further comprises a third node that is a child node mapped to the second node;

the third node is stored at a third processing node of the multiple processing nodes; and

data for the second node and data for the third node are stored at the second node.

13. The method of claim 12 , wherein:

the first conflation event is received at the first processing node; and

conflating the first set and the second set into the conflated set further comprises:

changing a state of the first node to a conflating state;

sending, from the first node to the second node, a root event identifying the first node;

determining, at the second node, that the first node is lexicographically smaller than the second node;

changing a state of the second node to a packed state;

sending, from the second node to the first node, a data event comprising the data for the second node and the data for the third node;

storing the data for the second node and the data for the third node at the first node;

changing the state of the first node to a normal state;

sending, from the first node to each of the second node and the third node, a change-root event identifying the first node;

deleting the data for the second node and the data for the third node from the second node;

setting the second node to be a child node mapped to the first node;

changing the state of the second node to a normal state; and

setting the third node to be a child node mapped to the first node.

14. The method of claim 12 , wherein:

the first conflation event is received at the second processing node; and

conflating the first set and the second set into the conflated set further comprises:

changing a state of the second node to a conflating state;

sending, from the second node to the first node, a first root event identifying the second node;

determining, at the first node, that the first node is lexicographically smaller than the second node;

changing a state of the first node to the conflating state;

sending, from the first node to the second node, a second root event identifying the first node;

changing the state of the second node to a packed state;

sending, from the second node to the first node, a data event comprising the data for the second node and the data for the third node;

storing the data for the second node and the data for the third node at the first node;

changing the state of the first node to a normal state;

sending, from the first node to each of the second node and the third node, a change-root event identifying the first node;

deleting the data for the second node and the data for the third node from the second node;

setting the second node to be a child node mapped to the first node;

changing the state of the second node to a normal state; and

setting the third node to be a child node mapped to the first node.

15. The method of claim 12 , wherein:

the first set further comprises a fourth node that is a child node mapped to the first node;

the fourth node is stored at a fourth processing node of the multiple processing nodes; and

data for fourth node are stored at the first node.

16. The method of claim 11 , wherein:

the first conflation event is received at the first processing node; and

conflating the first set and the second set into the conflated set further comprises:

changing a state of the first node to a conflating state based on the first conflation event;

receiving, while the state of the first node is the conflating state, a second conflation event at the first processing node identifying the first node and a third node;

adding the second conflation event to a to-be-conflated queue at the first node; and

when the state of the first node changes to a normal state, changing a state of the first node to the conflating state based on the second conflation event.

17. The method of claim 11 , wherein: