Method and system for distributed processing in a messaging platform

Patent metadata

Field	Value
Publication number	US-10324776-B2
Application number	US-201715859220-A
Country	US
Kind code	B2
Filing date	Dec 29, 2017
Priority date	Sep 26, 2013
Publication date	Jun 18, 2019
Grant date	Jun 18, 2019

Abstract

A method for distributed processing involves receiving a graph (G) of targets and of influencers, with each influencer related to at least one target, receiving an action graph of actions performed by one or more of the influencers, and key partitioning G across shards. The method further involves transposing the first graph (G) to obtain a first transposed graph (G T ), valuing partitioning G T across the shards, storing the action graph on multiple shards, issuing, to a shard, a request specifying an influencer, to perform an intersection, receiving a response to the request of a set of influencers each of which is related to a target, and determining whether to send a recommendation to the target based on the response.

First claim

What is claimed is:

1. A method comprising:
receiving a graph (G) comprising a plurality of nodes that each represent a respective account of a messaging system and a plurality of edges that each represent a relationship between a pair of accounts, wherein each account is either a target of other accounts, an influencer of other accounts, or both a target and an influencer, wherein G represents a plurality of targets and a plurality of influencers, and wherein each directed edge from one node to another node in the graph indicates that the account represented by the other node is an influencer of the account represented by the one node and that the account represented by the one node is a target of the account represented by the other node;
value partitioning G across multiple physical shards, wherein the value partitioning of G comprises, for each influencer, applying a hash function to the influencer of the graph to generate a hash result and distributing the in-edges to each influencer to a physical shard identified by the hash result for the influencer;
transposing G to obtain a transposed graph (G T ), wherein the transposed graph G T transposes the relationships between the nodes of G;
value partitioning G T across the multiple physical shards, wherein each partition of G T in each shard of the multiple physical shards has the same edges as a corresponding partition of G in the shard;
in response to a request to determine all accounts represented in G that are influencers of a first account and that are also targets of a second account:
issuing to each physical shard a request for an intersection of (i) values found on a lookup of the value partition of G on the shard using the first account as key and (ii) values found on a lookup of the value partition of G T on the shard using the second account as key, and receiving from each shard the respective intersection of values, and
performing a union of the intersections of values received from the shards, wherein the results of the union correspond to accounts represented by nodes of G that are influencers of the first account and that are also targets of the second account;

determining to send a recommendation to one or more of the accounts of the messaging system identified in the results of the union; and
in response to a determination to send the recommendation to one or more of the accounts, sending the recommendation to the determined one or more accounts.

2. The method of claim 1 , wherein each directed edge from one node to another node in the graph indicates that the account represented by the one node is a follower of the account represented by the other node.

3. The method of claim 1 , wherein the multiple physical shards each have one or more data processing nodes and partitioning G and G T across the shards comprises partitioning G and G T across the data processing nodes of the multiple physical shards.

4. A method comprising:
receiving a graph (G) comprising a plurality of nodes that each represent a respective account of a messaging system and a plurality of edges that each represent a relationship between a pair of accounts, wherein each account is either a target of other accounts, an influencer of other accounts, or both a target and an influencer, wherein G represents a plurality of targets and a plurality of influencers, and wherein each directed edge from one node to another node in the graph indicates that the account represented by the other node is an influencer of the account represented by the one node and that the account represented by the one node is a target of the account represented by the other node;
key partitioning G across a first physical shard and a second multiple physical shards, wherein the key partitioning of G comprises, for each influencer, applying a hash function to the influencer of the graph to generate a hash result and distributing the in-edges to each influencer to a physical shard identified by the hash result for the influencer;
transposing G to obtain a first transposed graph (G T ), wherein the first transposed graph G T transposes the relationships between the nodes of G;
key partitioning G T across the multiple physical shards, wherein each partition of G T in each shard of the multiple physical shards has the same edges as a corresponding partition of G in the shard;
in response to a request to determine all accounts represented in G that are targets of a first account and also targets of a second account:
issuing to each physical shard a request for an intersection of (i) values found in a look-up of key partition G T on the shard using the first account as key and (ii) values found in a look-up of key partition G on the shard using the second account as key, and receiving from each shard the respective intersection of values, and
performing a union of the intersections of values received from the shards, wherein the results of the union correspond to accounts represented by nodes of G that are targets of the first account and also targets of the second account;

determining to send a recommendation to one or more of the accounts of the messaging system identified in the results of the union; and
in response to a determination to send the recommendation to one or more of the accounts, sending the recommendation to the determined one or more accounts.

5. The method of claim 4 , wherein each directed edge from one node to another node in the graph indicates that the account represented by the one node is a follower of the account represented by the other node.

6. The method of claim 4 , wherein the multiple physical shards each have one or more data processing nodes and partitioning G and G T across the shards comprises partitioning G and G T across the data processing nodes of the multiple physical shards.

7. A system comprising:
one or more computers and one or more storage devices on which are stored instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:
receiving a graph (G) comprising a plurality of nodes that each represent a respective account of a messaging system and a plurality of edges that each represent a relationship between a pair of accounts, wherein each account is either a target of other accounts, an influencer of other accounts, or both a target and an influencer, wherein G represents a plurality of targets and a plurality of influences, and wherein each directed edge from one node to another node in the graph indicates that the account represented by the other node is an influencer of the account represented by the one node and that the account represented by the one node is a target of the account represented by the other node;
value partitioning G across multiple physical shards, wherein the value partitioning of G comprises, for each influencer, applying a hash function to the influencer of the graph to generate a hash result and distributing the in-edges to each influencer to a physical shard identified by the hash result for the influencer;
transposing G to obtain a transposed graph (G T ), wherein the first transposed graph Gt transposes the relationships between the nodes of G;
value partitioning G T across the multiple physical shards, wherein each partition of GT in each shard of the multiple physical shards has the same edges as a corresponding partition of G in the shard;
in response to a request to determine all accounts represented in G that are influences of a first account and that are also targets of a second account:
issuing to each physical shard a first request for an intersection of (i) values found on a lookup of the value partition of G on the shard using the first account as key and (ii) values found on a look

Assignees

• Twitter Inc

Inventors

• Grewal Ajeet
• Gurumurthy Siva
• Satuluri Venumadhav
• Gupta Pankaj
• Larson Brian
• Zhabuik Volodymyr
• Sharma Aneesh
• Goel Ashish

Classifications

• G06F16/245

  Query processing · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F9/546 Primary

  Message passing systems or structures, e.g. queues · CPC title

• G06F9/46 Primary

  Multiprogramming arrangements · CPC title