Fan-out control in scalable distributed data stores

Abstract

The disclosed embodiments provide a system for processing data. During operation, the system identifies a query type of a query of a graph database storing a graph, wherein the graph comprises nodes, edges between pairs of nodes, and predicates. Next, the system determines, based on the query type, a number of clusters on which the graph database is replicated for fanning out of the query. The system then selects a set of storage nodes in the determined number of clusters for processing of the query. Finally, the system generates a fan-out of the query to the selected storage nodes.

Description

RELATED APPLICATIONS[0001]This application claims the benefit of U.S. Provisional Application No. 62 / 307,025, Attorney Docket Number LI-P1890.LNK.PROV, entitled “Partitioning and Replicating Data in Scalable Distributed Data Stores,” by inventors SungJu Cho, Andrew J. Carter, Joshua D. Ehrlich and Jane Alam Jan, filed 11 Mar. 2016, which is incorporated herein by reference.[0002]The subject matter of this application is related to the subject matter in a co-pending non-provisional application by inventors SungJu Cho, Qingpeng Niu, Andrew Carter and Sanjay Sachdev, entitled “Partial Graph Incremental Update in a Social Network,” having Ser. No. 14 / 546,790, and filing date 18 Nov. 2014 (Attorney Docket No. P1384.LNK.US; 3080.C63US1).[0003]The subject matter of this application is also related to the subject matter in a co-pending non-provisional application by the same inventors as the instant application and filed on the same day as the instant application, entitled “Partitioning and...

AI Technical Summary

Benefits of technology

The patent text describes a system for improving the performance and scalability of complex queries of social and online professional network data. The system uses fan-out control and throughput-based fan-out control to optimize the processing of queries and reduce the time and resource-intensive process of searching and connecting data. This system can be used in social networks and online professional networks to leverage the data and improve business activities.

Problems solved by technology

However, complex querying of social and / or online professional network data may be time- and / or resource-intensive.

Moreover, a subset of the individuals and / or organizations may have a significantly larger than average number of links to other individuals and / or organizations, resulting in the added consumption of computational resources and / or time during execution of the query if the individuals and / or organizations are included in the search space of the query.

In turn, an uneven distribution of graph database data and queries among multiple storage and / or query nodes may result in issues such as tail latency, network congestion, and / or CPU-bounding.

Images