Fast querying of social network data

• US 10,037,388 B2
• Filed: 04/27/2015
• Issued: 07/31/2018
• Est. Priority Date: 04/27/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Sachdev, Sanjay, Jan, Jane Alam, Cho, SungJu
• Primary Examiner(s): Le, Miranda
• Application Number:
  US14/696,821
• Publication Number:
  US 20160314220A1
• Time in Patent Office: 1,191 Days
• Field of Search: 707798
• CPC Class Codes: G06F 16/86 Mapping to a database
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9038 Presentation of query results

Abstract

The disclosed embodiments provide a system for processing data. During operation, the system obtains a graph of a social network, wherein the graph includes a set of nodes representing users in the social network and a set of edges representing relationships between pairs of the users. Next, the system stores, on a single computer system, a static representation of the graph, wherein the static representation includes a first set of fixed-size blocks representing the nodes and the edges and a first index that maps a set of identifiers for the nodes and the edges to offsets of the first set of fixed-size blocks. The system then uses the static representation of the graph to process, by the single computer system, one or more queries of the graph.

Claims

1. A method for processing data, comprising:

obtaining a graph of a social network, wherein the graph comprises;

a set of nodes representing users in the social network; and

a set of edges representing relationships between pairs of the users;

storing, on a single computer system instead of a cluster-based query-processing system that includes multiple computers, a static representation of the graph, wherein the static representation comprises;

a first set of fixed-size blocks representing the nodes and the edges; and

a first index that maps a set of identifiers for the nodes and the edges to offsets of the first set of fixed-size blocks;

identifying, from a stream of events associated with activity in the social network, updates to the graph that occurred subsequent to creation of the static representation;

storing, in a memory of the single computer system, a dynamic representation of the identified changes to the graph, wherein the dynamic representation comprises;

a second set of fixed-size blocks representing changes to the nodes and edges caused by the updates to the graph; and

a second index that maps a subset of the identifiers for the nodes and the edges to offsets of the second set of fixed-size blocks; and

using the dynamic representation and the static representation of the graph to process, by the single computer system, one or more queries of the graph by, for each of one or more identifiers in the query;

using the second index to match the identifier to an offset to one or more blocks in the second set of fixed-size blocks that match the query; and

when the second index does not contain the identifier, using the first index to match the identifier to an offset to one or more blocks in the first set of fixed-size blocks that match the query.

2. The method of claim 1, further comprising:

storing the dynamic representation in one or more files on the single computer system prior to a restart of the single computer system; and

after the restart, loading the dynamic representation from the one or more files into the memory.

3. The method of claim 1, further comprising:

periodically merging the dynamic representation into the static representation.

4. The method of claim 3, wherein merging the dynamic representation into the static representation comprises:

for each block in the second set of fixed-size blocks;

identifying a block in the first set of fixed-size blocks that corresponds to the block in the second set of fixed-size blocks; and

replacing the block in the first set of fixed-size blocks with the block in the second set of fixed-size blocks; and

discarding the dynamic representation.

5. The method of claim 3, wherein said periodically merging the dynamic representation into the static representation of the graph enables the single computer system to be used as a primary data store instead of as a mechanism for serving data duplicated from the primary data store.

6. The method of claim 1, further comprising:

obtaining a new version of the graph;

updating the static representation of the graph with the new version; and

discarding the dynamic representation after the static representation is updated.

7. The method of claim 1, wherein the first set of fixed-size blocks comprises a contiguous subset of fixed-size blocks corresponding to active users in the social network.

8. The method of claim 1, wherein the graph is obtained as a snapshot from a primary data store.

9. The method of claim 1, wherein at least a portion of the static representation of the graph is stored in one or more solid-state drives (SSDs) in the single computer system.

10. The method of claim 1, wherein a fixed-size block in the first set of fixed-size blocks comprises:

an adjacency list of a set of edges from a node to other nodes in the graph; and

one or more attributes associated with the set of edges.

11. An apparatus, comprising:

a single computer system having one or more processors; and

memory storing instructions that, when executed by the one or more processors, cause the apparatus to;

obtain a graph of a social network, wherein the graph comprises;

a set of nodes representing users in the social network; and

a set of edges representing relationships between pairs of the users;

store a static representation of the graph, wherein the static representation comprises;

a first set of fixed-size blocks representing the nodes and the edges; and

a first index that maps a first set of identifiers for the nodes and the edges to offsets of the first set of fixed-size blocks;

identify, from a stream of events associated with activity in the social network, updates to the graph that occurred subsequent to creation of the static representation;

store, in the memory, a dynamic representation of the identified changes to the graph, wherein the dynamic representation comprises;

a second set of fixed-size blocks representing changes to the nodes and edges caused by the updates to the graph; and

a second index that maps a subset of the identifiers for the nodes and the edges to offsets of the second set of fixed-size blocks; and

use the dynamic representation and the static representation of the graph to process one or more queries of the graph by, for each of one or more identifiers in the query;

using the second index to match the identifier to an offset to one or more blocks in the second set of fixed-size blocks that match the query; and

when the second index does not contain the identifier, using the first index to match the identifier to an offset to one or more blocks in the first set of fixed-size blocks that match the query.

12. The apparatus of claim 11, wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:

store the dynamic representation in one or more files on the single computer system prior to restarting the apparatus; and

after the apparatus has restarted, load the dynamic representation from the one or more files into the memory.

13. The apparatus of claim 11, wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:

periodically merge the dynamic representation into the static representation;

wherein said periodically merging the dynamic representation into the static representation of the graph enables the single computer system to be used as a primary data store instead of as a mechanism for serving data duplicated from the primary data store.

14. The apparatus of claim 11, wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:

obtain a new version of the graph;

update the static representation of the graph with the new version; and

discard the dynamic representation after the static representation is updated.

15. The apparatus of claim 11, wherein the first set of fixed-size blocks comprises a contiguous subset of fixed-size blocks corresponding to active users in the social network.

16. A system, comprising:

a management non-transitory computer-readable medium comprising instructions that, when executed by one or more processors, cause the system to;

obtain a graph of a social network, wherein the graph comprises;

a set of nodes representing users in the social network; and

a set of edges representing relationships between pairs of the users; and

store a static representation of the graph, wherein the static representation comprises;

a first set of fixed-size blocks representing the nodes and the edges; and

a first index that maps a set of identifiers for the nodes and the edges to offsets of the first set of fixed-size blocks;

identify, from a stream of events associated with activity in the social network, updates to the graph that occurred subsequent to creation of the static representation;

maintain a dynamic representation of the identified changes to the graph, wherein the dynamic representation comprises;

a second set of fixed-size blocks representing changes to the nodes and edges caused by the updates to the graph; and

a second index that maps a subset of the identifiers for the nodes and the edges to offsets of the second set of fixed-size blocks; and

a query-processing non-transitory computer-readable medium comprising instructions that, when executed by one or more processors, cause the system to use the dynamic representation and the static representation of the graph to process one or more queries of the graph by, for each of one or more identifiers in the query;

using the second index to match the identifier to an offset to one or more blocks in the second set of fixed-size blocks that match the query; and

when the second index does not contain the identifier, using the first index to match the identifier to an offset to one or more blocks in the first set of fixed-size blocks that match the query.

17. The system of claim 16, wherein a fixed-size block in the first set of fixed-size blocks comprises:

an adjacency list of a set of edges from a node to other nodes in the graph; and

one or more attributes associated with the set of edges.

18. The system of claim 16, wherein one or both of the first set of fixed-size blocks and second set of fixed-size blocks comprise a contiguous subset of blocks corresponding to active users in the social network.

19. The system of claim 16, wherein the management non-transitory computer-readable medium further comprises instructions that, when executed by one or more processors, cause the system to:

periodically merge the dynamic representation into the static representation;

wherein said periodic merging of the dynamic representation into the static representation enables the single computer system to be used as a primary data store instead of as a mechanism for serving data duplicated from the primary data store.

20. The system of claim 19, wherein merging the dynamic representation into the static representation comprises:

for each block in the second set of fixed-size blocks;

identifying a block in the first set of fixed-size blocks that corresponds to the block in the second set of fixed-size blocks; and

replacing the block in the first set of fixed-size blocks with the block in the second set of fixed-size blocks; and

discarding the dynamic representation.