Graph-based system and method of information storage and retrieval

Structure of a resultant Every Document as a Graph (EVG) graph may be outlined using an EVG query. First metadata for a first data source may be retrieved. At least one entity key may be determined for a first entity, the entity key coming directly from the EVG query or from an entity on a preceding level of the EVG graph. Based on the first metadata and entity key, an edge may be created in the EVG graph beginning at the first entity, wherein the edge contains information retrieved from the first data source. Second metadata for a second data source may be retrieved. Based on the second metadata and information contained in the edge retrieved from first data source, a second entity may be created in the EVG graph, wherein the edge connects to the second entity, wherein the second entity contains information retrieved from the second data source.

TECHNICAL FIELD

This application relates to the technical fields of software and/or hardware technology and, in one example embodiment, to a graph-based system and method of information storage and retrieval.

BACKGROUND

Storing large numbers of documents in an efficient and quick-to-retrieve manner is a common problem with databases. A number of different solutions have been provided in the database arena, where data is stored in a single database in a single domain. However, recently web sites such as social networks have attempted to gather and access documents from different domains and combine them to satisfy a particular business case. A number of problems have been encountered in such situations, including having to deal with redundant data stores for relationships, duplication of operation and maintenance effort, and significant scalability issues that need to be addressed frequently.

DETAILED DESCRIPTION

In an example embodiment, a uniform, generic system for user case-specific relationships is provided. A graph-based model may be provided to allow for simpler and consistent mental models. Users are able to define domain models and perform queries in an efficient and easy-to-understand manner. Furthermore, the system simplifies scaling and operations by leveraging a small number of relatively generic systems and an open multi-tenant architecture for features of appropriate scale. Data sources are abstracted, and the system is able to store and retrieve metadata about the data sources and is able to efficiently use this metadata to gather desired data from the data sources. In this way, a service provider such as a social networking website may accelerate time-to-market of new features and services and reduce cost by enabling reuse and abstraction of existing data objects, which has the effect of reducing duplicate effort.

As used herein, the term “or” may be construed in either an inclusive or exclusive sense. Similarly, the term “exemplary” merely means an example of something or an exemplar and not necessarily a preferred or ideal means of accomplishing a goal. For the purposes of this description, the phrase “an on-line social networking application” may be referred to as and used interchangeably with the phrase “an on-line social network” or merely “a social network.” It will also be noted that an on-line social network may be any type of an on-line social network such as, for example, a professional network, an interest-based network, or any on-line networking system that permits users to join as registered members. For the purposes of this description, registered members of an on-line social network may be referred to as simply members.

Each member of an on-line social network is represented by a member profile (also referred to as a profile of a member or simply a profile). A member profile may be associated with social links that indicate that member's connection to other members of the social network. A member profile may also include or be associated with comments or endorsements from other members of the on-line social network, with links to other network resources such as, for example, publications, etc. As mentioned above, an on-line social networking system may be designed to allow registered members to establish and document networks of people they know and trust professionally. Any two members of a social network may indicate their mutual willingness to be “connected” in the context of the social network, in that they can view each other's profiles, profile recommendations and endorsements for each other and otherwise be in touch via the social network. Reputation scores may be computed based on information obtained from trusted sources, such as patent databases, publications databases, skills, endorsement of skills, or even enterprise contracts.

In addition to member profiles, there may be a number of different types of data stored by the social network site. Additionally, data from other data sources, such as audio and video content, email and business documents, calendars, text messages, etc. may also be accessed by the social network site. It would be helpful if all this data can be accessed in an efficient manner and that whatever features the social network site is attempting to set up to access new data types or new data sources can be set up in an efficient manner.

In an example embodiment, a concept known as Every Document as a graph (EVG) is introduced. EVG is a shared, multi-tenant service for supporting entity persistence and discovery, managing relationships, and integrating social gestures. It is a layer on top of data store implementations such as Espresso, Voldemort, Oracle, etc. and acts as a proxy to these data stores.

In an example embodiment, EVG also acts to assemble complex documents and display them as a simple query, offer strongly-typed representations of data to use case-specific clients, and use metadata to function when new types of edges and entities are introduced, without having to rebuild, redeploy, or disrupt existing clients.

In an example embodiment, EVG breaks down rich domain objects that are often represented as hierarchical documents into a graph where individual entities are tied together via directional associations or edges. In EVG, every relationship is represented as an edge and every rich object or document is a graph.

FIG. 1is a graph100for a document in accordance with an example embodiment. Here, a member node102is linked to a treasuryMedia node104via an edge106, representing the relationship between the member node102and the treasuryMedia node104. To get to a member's media content stored in a treasuryMedia entity, the member2Media edge106may be used.

The generic framework of EVG makes it easy for the user to assemble a graph from distinct data stores. In an example embodiment, from a database perspective, EVG follows a normalized approach where entities and edges are stored in separate tables, making it easy to recombine these elements to satisfy different use cases. In an example embodiment, EVG is metadata-driven to distinguish stored edges from entities. The metadata also may map entities to physical data stores. EVG can then handle the assembly of these data objects based on an intuitive query language expression.

For purposes of this disclosure, a document may be considered to be a rich data object combining elements of different domains. An element may be considered a generic term for a data envelope, and can either be an entity or an edge. An entity or vertex may be considered a material part of a domain model carrying attributes. An association or relationship may be considered to be a direct connection between two entities. An edge may be considered to be a meaning attached to an association. A gesture may be considered a sum of social interactions with entities (e.g., comments, likes, feeds, etc.). A feed may be considered to be an activity stream for a given number of entities.

FIG. 2is a block diagram illustrating a system200of implementing EVG in accordance with an example embodiment. A client application202may contain an EVG client library204, which may perform validation206and stencilization208activities. A server application210may perform assembly212of each EVG graph. A metadata store214may store and serve mappings, queries, association constraints, registries of virtual associations, and other metadata related to the graphs. An entity store216may store and serve entity data. The metadata store214may be partitioned by entity. An edge store218may store associative links/edges. In an example embodiment, all edges are stored in the same partition/database/table, with distinction between adjacency list and “row-per-edge’ storage format.

The assembly212may construct the graphs by accessing one or more external data stores220A,220B, and storing the corresponding graph information in the metadata store214, entity store216, and edge store218. A search service222may be used to find relationships spanning several degrees of separation, and traverse bidirectional relationships. The search service222may also extend an EVG query to support the indexing of metadata.

In an example embodiment, at least one of the external data sources220A,220B is a key-value store system, such as Espresso. Key-value store systems lose the ability to perform traditional JOIN operations common to relational databases. In light of this, the system may be designed with query parameters and features designed to maintain edges in a manner that helps make up for the loss of such traditional JOIN operations.

FIG. 3is a block diagram illustrating various layers of a server application210in accordance with an example embodiment. A business layer300may allow assembly of data per the client's specification via EVG graphs, and may manage mapping of entity types to uniform resource names (URN) and uniform resource identifiers (URI). A domain layer302may define and publish schemas, formulate queries and invocations, take on the responsibility of reconstituting foreign domain objects, and use visibility constraints to filter obscure pieces of data that are restricted based on domain logic, such as privacy settings, subscription status, etc. In an example embodiment, the domain layer302may be implemented using a domain-specific REST.LI service. REST.LI is a Java framework that allows users to create clients and servers using a Representational State Transfer (REST) style.

The domain layer302may also, via the EVG client library204, perform validations driven by schemas and provide strongly typed interfaces proxying data maps (stencils).

A presentation layer304may then emit flattened, simplified Javascript Object Notation (JSON) for consumption by clients, and take user input to be persisted and send it to the business layer300to be stored in an EVG graph.

In an example embodiment, data sources are abstracted to provide a single interface for multiple data sources. The EVG graphs stich together heterogeneous data and a query engine is then able to access multiple data stores in parallel. By partitioning data, the EVG graphs also become extremely scalable. Related entities may be clustered and parallel queries may be executed for additional scalability.

Data structures used by the EVG graphs in one example embodiment are described herein. One of ordinary skill in the art will recognize that these are merely examples, and that other data structures may be utilized in some embodiments.

URNs may be represented as a sequence of variables including scheme, entity type, partition key, and entity key. For example, the URN “urn:li:media:(urn:li:member:123,456)” may indicate a scheme of “urn:li”, an entity type of “media”, a partition key of “member:123” and an entity key of “456”.

Entities may be represented as strongly-typed Java objects having sub-entities and lists. They may contain properties such as URN and type.

Edges may be represented as strongly-typed Java objects having various properties, such as URNs, from entity URNs, to entity URNs, edge types, and various attributes.

Adjacency lists may contain properties such as from entity URN, edge type, and an ordered list of edges.

In an example embodiment, associations can be modeled in two ways: sub-entities and entities+edges. Composition (“part of”) relations, such as where the member has a list of positions he has worked at, may be modeled as sub-entities, while non-composition relations, such as which companies the member has worked for, may be modeled as entities+edges.

The following is example code illustrating setting up an ECG client in accordance with an example embodiment.

FIG. 4is a block diagram illustrating an EVG graph400in accordance with an example embodiment. The EVG graph400contains two member nodes402A,402B. Member node402A corresponds to member “123” while member node402B corresponds to member “234”. These nodes are each linked to a position node404A,404B and an education node406A,406B. Each position node404A,404B is linked to a company node408A,408B and a seniority node410A,410B. Each education node406A,406B is linked to a school node412A,412B. The edges414,416,418,420,422,424,426,428,430, and432are all named so that they can easily identify to a user what sort of information is stored on the node following the edge. This allows the user to easily specify a query using a query language. For example, the user may write the following in the query language:

from {‘urn:member:123’,‘urn:member:234’} get entity

over memberEducation get entity over educationSchool get entity;}

which indicates to the system that the user wishes to get all the company nodes408A,408B, seniority nodes410A,410B, and school nodes412A,412B.

FIG. 5is a block diagram illustrating an EVG graph500in accordance with another example embodiment. Here, rather than a working history use case such as inFIG. 4, the EVG graph500represents admission decisions in higher education (e.g., college admissions). A memberboard node502may identify a member of an admissions board of the university, and member data may be stored in a first data store504having a first data store type, such as Espresso. The URN for the memberboard node502may point to the first data store504, where entity data506is stored. Another URN may point to another data store508, where edge data510is stored. This additional data store508is depicted as another Espresso database, and in some embodiments may be the same data store as the first data store504. In other embodiments, this additional data store508may be a completely different type than the first data store504.

Here, the edge data510indicates two edges512A,512B, each to a decision card node514A,514B defined by entity data506. Each decision card node514A,514B then contains a URN pointing to a second data store516having a second data store type, such as Oracle. The second data store516then contains entity data518indicating comment nodes520A,502B,520C,520D. Another URN may point to another data store522, where edge data524is stored. This additional data store508is depicted as another Oracle database, and in some embodiments may be the same data store as the second data store516. In other embodiments, this additional data store522may be a completely different type than the second data store516.

Here, edge data524indicating edges526A,526B,526C,526D, which are edges to comment nodes520A,520B,520C,520D.

If a user wishes to perform a query, such as “get all decision cards from a member board and get all the comments on the decision cards,” the user can create a query language query as follows:

from {‘urn:memberBoard:(urn:li:member:123,42)’} get urn

In an example embodiment, a Java-based client may be provided for programmatic access to the EVG graphs. The client utilizes a common builder pattern for constructing requests and responses. It may provide a layer of abstraction above the REST layer and may be capable of producing and consuming objects typed to client-specific domain classes.

The client may be used to construct basic requests and responses. The following is sample code for creating an entity in accordance with an example embodiment:

The following is sample code for retrieving an entity in accordance with an example embodiment:

The following is sample code for updating an entity in accordance with an example embodiment:

The following is sample code for deleting an entity in accordance with an example embodiment:

The following is sample code for adding an edge in accordance with an example embodiment:

The following is sample code for deleting an edge in accordance with an example embodiment:

The following is sample code for querying in accordance with an example embodiment:

In an example embodiment, the system may support metadata and index metadata for entities and edges. Metadata may be used to define each entity and edge type for a particular use case, and index metadata may be used to access entity data through a data source's secondary index.

In an example embodiment, a number of different attributes are available for a user to create metadata for a new entity or edge, including entityType, urnResolver, urnResolverConfig, edge, rowPerEdge, edgeMultiTenant, and reducedEdge.

The entityType attribute supports entities and edges and specifies the name of the entity or edge.

The urnResolver attribute specifies the data store.

The urnResolverConfig attribute is a map with attributes specific to the resolver (data store). The map may include database and table information for the entity, and the URN pattern which will specify the URN to database translation.

The edge attribute specifies whether the entity type is an entity or an edge.

The rowPerEdge attribute indicates whether each edge is stored in one separate row or several edges can be aggregated into one row.

The edgeMultiTenant attribute specifies whether multiple edge types can be stored in the table.

The reducedEdge attribute specifies whether the edge can be stored in a reduced format.

Referring back to the example inFIG. 1having a member entity102with an edge106to an entity for treasuryMedia104, various metadata for each of these elements may be provided. For example, the following is sample metadata for the entity treasuryMedia104in accordance with an example embodiment:

//Metadata if the entity treasuryMedia is stored in Oracle

//Metadata if the entity treasuryMedia is stored in Espresso

The following is sample metadata for the edge member2Media106in accordance with an example embodiment:

//Metadata if the edge member2Media is stored in Oracle

//Metadata if the edge member2Media is stored in Espresso

In an example embodiment, a number of different attributes are available for a user to create index metadata for a new entity or edge, including indexName, urnResolveer, urnResolverConfig, edge, toIndexField, indexFields, and supportedEdges.

The indexName attribute specifies the name of the entity or edge.

The urnResolver attribute defines the data store.

The urnResolverConfig attribute is a map with attributes specific to the resolver (data store). The map includes database and table information for the entity and the URN pattern which specifies the URN to database translation.

The edge attribute specifies whether the entity type is an entity or an edge.

The toIndexField attribute is used if the entity is an edge and specifies a full valid URN. The system then retrieves and returns the data defined in this URN.

The supportedEdges attribute specifies the edges in an EVG graph query supported by the index.

In an example embodiment, entities are stored in a table per per-domain object. In an alternative embodiment, a completely opaque binary envelope is used. In the table per per-domain object case, this means that users create a table for their objects. In order to allow the data to be partitioned, all keys, for both entities and edges, begin with a partition key. In an example embodiment, this may be a member identification. Consequently, since the URN needs to carry enough information to fill in the parameters of the request to perform any of the operations on the underlying data store, it also needs to have the identification of the domain specific object along the way.

Table 1 depicts example URNs in accordance with an example embodiment:

TABLE 1EntityURNNotesmembers'surn:li:member:1profileposition #123urn:li:position:Although position is an(urn:li:member:1,123)integral part of a profile, itcan also be served up as anentity of its own, whileacting as a sub-entity of amember's profilememberurn:li:profileSection:An object with this addressprofile's(urn:li:member:does not exist nor is eversection1,RECOMMENDATIONS)materialized outside of amembers profile; thiseffectively refers to an areaon the screen wherecorresponding data isrendered.treasuryurn:li:treasuryMedia:media #456(urn:li:member:1,456)

The results of using an EVG graph is that data from multiple data sources may be abstracted and queries for data from these multiple data sources can be sent to a single destination: the EVG system. The EVG system maintains the edges for the data in these multiple data sources. Each entity itself may be unaware that another entity exists, even if an edge is present between the two entities, because the EVG system maintains the edges separately from the entities.

The EVG system is also able to retrieve all pieces of data in parallel, despite the fact that they may be disparate pieces of data in disparate data sources, as opposed to prior art techniques where the system retrieves at least some data in series, necessitating a waiting period until the final piece of data is retrieved, prior to loading. Additionally, the EVG system is also intelligent enough such that if one of the disparate pieces of data being retrieved has an edge to another piece of data (e.g., a sub-entity), it can immediately retrieve that other piece of data. Thus, for example, if there are two entities, labeled media1 and media2, each having an edge to sub-entities, labeled group1 and group2, the system, upon retrieving media1, can immediately begin retrieving group1, without waiting for media2 to be completely retrieved. Thus, the EVG system is designed to accept queries that specify edges, rather than goal entities, to retrieve. The EVG system then uses these specified edges to return “whatever” entities reside on the other ends of these edges.

FIG. 6is a block diagram illustrating an EVG system600in accordance with an example embodiment. A query (written in a query language) is received at a query parser602, which generates an abstract syntax tree (AST) representation of the query. This is then passed to a query engine604. The query engine604may then start an assembly task606, an entity request task608, an edge request task610, an entity result task612, and an edge result task614. The entity result task612may require that the entity request task608complete before launching, and the edge result task614may require that the entity result task612complete before launching. However, the entity result task612and the edge result task614may each launch additional tasks dynamically as needed. For example, if one of these tasks612,614determine that there is, in fact, an additional group element under the currently retrieved element, it may launch an additional entity request task to retrieve this additional group element. Each request task608-610may contain a pointer to where it is located in the AST in order to make this possible.

A result context616gathers URNs generated by the tasks608-610and retrieves corresponding data from the data sources for these URNs. This helps eliminate duplicate requests. For example, if two different entities are linked to the same media file, the media file, while referenced by two different tasks, will only be retrieved once as the result context616is intelligent enough to recognize duplicate URNs and only retrieve one piece of data.

The assembly task606then forms the response to the query based on the data from the result context616.

Notably, the request tasks608-610look up in the resolver618to determine how to actually retrieve the corresponding data. The resolver618provides this information based on the metadata, allowing the request tasks608to schedule actual data retrieval calls via URNs. Communication flows620and622indicate how the edgeResult task614can actually cause a loop or cycle by then initiating calls to entityRequest608and/or edgeRequest610.

FIG. 7is a block diagram illustrating a task chain700in accordance with an example embodiment. The task chain700includes an entity get702, which then uses an xfetcher task704which, when the result comes back, gets turned into xnormalize706, which then results in entitydone708. The xfetcher task704and the xnomalize706task may be collectively known as a resolver710, which may be plug-and-play, meaning that the resolver710for one type of data source can be switched out with the resolver710. The task chain700may be defined by metadata. Additionally, the resolver710can be designed as a dual fetcher, performing similar tasks on different data sources simultaneously, which makes it easier for users to migrate data from one data source to another.

FIG. 8is a sequence diagram illustrating a method800in accordance with an example embodiment. The method800involves a number of different entities, including a user802, front-end804, middle tier806, EVG engine808, AST query engine810, Assembler812, Metadata source814, 1st data source816, and 2nd data source818. At operation820, the user (through, for example, a browser) may send an HTTP request to the front-end804. At operation822, the front-end804sends a request to the middle tier806. At operation824, the middle tier806sends a query via REST to the EVG engine808. At operation826, the EVG engine808sends a query to the AST query engine810.

At operation828, the AST query engine810sends an AST message for content to the assembler812. At operation830, the assembler812sends a get request to the metadata source814, which returns the metadata at operation832. At operation834, the assembler812then creates the tasks. At operation836, the assembler812sends a get request to the 1st data source816, which returns content at operation838. At operation840, the assembler812populates the content in a data structure. At operation842, the assembler812sends a get request to the 2nd data source818, which returns content at operation844. At operation846, the assembler812populates the content in a data structure.

At operation848, the assembler812sends the content to the EVG engine808, which at operation850forms a response from the content. This response is sent to the middle tier806at operation852. The middle tier806then returns a model to the front-end804at operation854. The front-end then returns an HTML page at856based on the model.

FIG. 9is a flow diagram illustrating a method900in accordance with an example embodiment. At operation902, structure of a resultant Every Document as a Graph (EVG) graph may be outlined using an EVG query. At operation904, first metadata for a first data source may be retrieved. At operation906, at least one entity key for a first entity is determined, wherein the entity key comes directly from the EVG query or from an entity on a preceding level of the EVG graph. Then, at operation908, based on the first metadata and entity key, an edge may be created in the EVG graph beginning at the first entity, wherein the edge contains information retrieved from the first data source. At operation910, second metadata for a second data source is retrieved, the second data source being of a different data source type than the first data source such that accessing data from the first data source is performed differently than accessing data from the second data source. Then, based on the second metadata and information contained in the edge retrieved from first data source, a second entity may be created in the EVG graph, wherein the edge connects to the second entity, wherein the second entity contains information retrieved from the second data source.

The example computer system1000includes a processor1002(e.g., a central processing unit (CPU), a graphics processing unit (GPU) or both), a main memory1004and a static memory1006, which communicate with each other via a bus1008. The computer system1000may further include a video display unit1010(e.g., a liquid crystal display (LCD) or a cathode ray tube (CRT)). The computer system1000also includes an alphanumeric input device1012(e.g., a keyboard), a user interface (UI) navigation device1014(e.g., a cursor control device), a storage device1016, a signal generation device1018(e.g., a speaker) and a network interface device1020.

The storage device1016includes a machine-readable medium1022on which is stored one or more sets of instructions and data structures (e.g., instructions1024) embodying or utilized by any one or more of the methodologies or functions described herein. The instructions1024may also reside, completely or at least partially, within the main memory1004and/or within the processor1002during execution thereof by the computer system1000, with the main memory1004and the processor1002also constituting machine-readable media1022.

The instructions1024may further be transmitted or received over a network1026via the network interface device1020utilizing any one of a number of well-known transfer protocols (e.g., Hyper Text Transfer Protocol (HTTP)).

While the machine-readable medium1022is shown in an example embodiment to be a single medium, the term “machine-readable medium” should be taken to include a single medium or multiple media (e.g., a centralized or distributed database, and/or associated caches and servers) that store the one or more sets of instructions e.g.,1024. The term “machine-readable medium” shall also be taken to include any medium that is capable of storing and encoding a set of instructions e.g.,1024for execution by the machine and that cause the machine to perform any one or more of the methodologies of embodiments of the present disclosure, or that is capable of storing and encoding data structures utilized by or associated with such a set of instructions e.g.,1024. The term “machine-readable medium” shall accordingly be taken to include, but not be limited to, solid-state memories, optical and magnetic media. Such media may, without limitation, also include hard disks, floppy disks, flash memory cards, digital video disks, random access memory (RAMs), read only memory (ROMs), and the like.

The embodiments described herein may be implemented in an operating environment comprising software installed on a computer, in hardware, or in a combination of software and hardware. Such embodiments of the inventive subject matter may be referred to herein, individually or collectively, by the term “disclosure” merely for convenience and without intending to voluntarily limit the scope of this application to any single embodiment if more than one is, in fact, disclosed.

Modules, Components and Logic

Similarly, the methods described herein may be at least partially processor-implemented. For example, at least some of the operations of a method may be performed by one or more processors1002or processor-implemented modules. The performance of certain of the operations may be distributed among the one or more processors1002, not only residing within a single machine, but deployed across a number of machines. In some example embodiments, the processor or processors1002may be located in a single location (e.g., within a home environment, an office environment or as a server farm), while in other embodiments the processors1002may be distributed across a number of locations.

Although embodiments have been described with reference to specific example embodiments, it will be evident that various modifications and changes may be made to these embodiments without departing from the broader spirit and scope of the inventive subject matter. Accordingly, the specification and drawings are to be regarded in an illustrative rather than a restrictive sense.