Network-wide, location-independent object identifiers for high-performance distributed graph databases

• US 10,585,943 B2
• Filed: 10/07/2016
• Issued: 03/10/2020
• Est. Priority Date: 11/24/2015
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Kizhakkel, Vinit Rajan, Lo, Jeffrey Y. D, Pereira, Pratap
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Bogacki, Michal
• Application Number:
  US15/288,282
• Publication Number:
  US 20170147448A1
• Time in Patent Office: 1,250 Days
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

In one embodiment, an operating system (on a computer device in a network of computer devices) interfaces with a distributed graph database that is distributed across the network of computer devices, and executes an application that has one or more parent data constructs that reference one or more child objects within the distributed graph database. Specifically, the one or more child objects each have a location-independent object identifier (OID) having at least: a) an OID-identifier (OID-ID) assigned upon creation to each particular child object by a data source of the location-independent OID; b) an OID-source structure that uniquely identifies the data source of the location-independent OID within the network of computer devices; and c) an OID-pointer indicative of a relative location of the particular child object in a memory mapped region. Accordingly, the operating system accesses the child objects (e.g., for an application) based on the location-independent OID.

Claims

1. A method, comprising:

interfacing, by an operating system on a computer device in a network of computer devices, with a distributed graph database that is distributed across the network of computer devices;

executing, by the operating system, an application that has one or more parent data constructs that reference one or more child objects within the distributed graph database, wherein the one or more child objects each have a location-independent object identifier (OID) that models hierarchical relationships between nodes in the distributed graph database on a plurality of networking devices interconnected by the computer devices in the network, the OID including;

an OID-identifier (OID-ID) assigned to each particular child object by a data source of the location-independent OID,

an OID-source tupled to the OID-ID, the OID-source a pointer to a structure that uniquely identifies the data source of the location-independent OID within the network of computer devices, wherein the OID source identifies an exact location of origin of the one or more child objects in the distributed graph database, and

an OID-pointer indicative of a relative location of the particular child object in a memory mapped region, wherein lookup trees provide bidirectional mapping from OID-ID and OID-source tuples to OID-pointer values, and wherein the OID-pointer for a particular child object is cached within a particular parent data construct referencing a relative address of that particular child object; and

accessing, by the operating system, the one or more child objects based on the location-independent OID.

2. The method as in claim 1, wherein the lookup trees comprise one of either red-black trees or generalized balanced trees.

3. The method as in claim 1, further comprising:

generating, as a particular data source, a particular location-independent OID for a newly referenced child object, wherein generating comprises assigning a particular OID-ID to the newly referenced child object and combining the particular OID-ID with an OID-source that uniquely identifies the particular data source as an OID-ID and OID-source tuple;

caching the OID-ID and OID-source tuple within the newly referenced child object;

determining a particular OID-pointer value for the newly referenced child object based on a particular relative location of the newly referenced child object in a particular memory mapped region;

establishing lookup trees that provide a bidirectional mapping from the OID-ID and OID-source tuple to the particular OID-pointer value; and

caching the particular OID-pointer value for the newly referenced child object within a corresponding parent data construct referencing the newly referenced child object.

4. The method as in claim 3, further comprising:

generating the particular location-independent OID only in response to a particular application requesting reference to the newly referenced child object.

5. The method as in claim 1, further comprising:

replicating a plurality of child objects and associated location-independent OIDs across device boundaries to a replicating device using the same OID-ID and OID-source tuple for each of the plurality of replicated child objects, wherein one or more new OID-pointers are established that are specific to the replicating device.

6. The method as in claim 5, further comprising:

establishing a table of contents for the replication of child objects, wherein replicating is performed based on the table of contents.

7. The method as in claim 5, further comprising:

creating a placeholder OID-pointer within a particular parent data construct in response to the particular parent data construct being replicated before a corresponding child object; and

resolving the placeholder OID-pointer in response to the corresponding child object being replicated.

8. The method as in claim 1, wherein the OID-source comprises one or more identifications selected from a group consisting of:

a system identifier of a multi-chassis stack;

a chassis identifier for an associated chassis within a multi-chassis stack;

a unit identifier for a computing unit within a chassis;

a slot identifier for a physical slot on a chassis; and

a bay identifier for a physical bay on a chassis.

9. The method as in claim 8, wherein the group from which the identifications are selected from further consists of:

a logical unit identifier to identify a type of a corresponding child object.

10. The method as in claim 1, wherein each location-independent OID further has an OID-attribute that defines whether the particular child object is an object or a set of objects.

11. The method as in claim 1, wherein the operating system is a network device operating system, and wherein the computer device is a computer networking device.

12. The method as in claim 1, wherein the network of computer devices is an enterprise network.

13. A tangible, non-transitory, computer-readable media having software encoded thereon, the software, when executed by a processor on a computer device in a network of computer devices, operable to:

interface with a distributed graph database that is distributed across the network of computer devices;

execute an application that has one or more parent data constructs that reference one or more child objects within the distributed graph database, wherein the one or more child objects each have a location-independent object identifier (OID) that models hierarchical relationships between nodes in the distributed graph database interconnected by the computer devices in the network, the OID including;

an OID-identifier (OID-ID) assigned to each particular child object by a data source of the location-independent OID,

an OID-source tupled to the OID-ID, the OID-source a pointer to a structure that uniquely identifies the data source of the location-independent OID within the network of computer devices, wherein the OID source structure identifies an exact location of origin of the one or more child objects in the distributed graph database, and

an OID-pointer indicative of a relative location of the particular child object in a memory mapped region, wherein lookup trees provide bidirectional mapping from OID-ID and OID-source tuples to OID-pointer values, and wherein the OID-pointer for a particular child object is cached within a particular parent data construct referencing a relative address of that particular child object; and

access the one or more child objects based on the location-independent OID.

14. The computer-readable media as in claim 13, wherein the software, when executed, is further operable to:

generate, as a particular data source, a particular location-independent OID for a newly referenced child object, wherein generating comprises assigning a particular OID-ID to the newly referenced child object and combining the particular OID-ID with an OID-source that uniquely identifies the particular data source as an OID-ID and OID-source tuple;

cache the OID-ID and OID-source tuple within the newly referenced child object;

determine a particular OID-pointer value for the newly referenced child object based on a particular relative location of the newly referenced child object in a particular memory mapped region;

establish lookup trees that provide a bidirectional mapping from the OID-ID and OID-source tuple to the particular OID-pointer value; and

cache the particular OID-pointer value the newly referenced child object within a corresponding parent data construct referencing the newly referenced child object.

15. The computer-readable media as in claim 13, wherein the software, when executed, is further operable to:

replicate a plurality of child objects and associated location-independent OIDs across device boundaries to a replicating device using the same OID-ID and OID-source tuple for each of the plurality of replicated child objects, wherein one or more new OID-pointers are established that are specific to the replicating device.

16. The computer-readable media as in claim 13, wherein the OID-source comprises one or more identifications selected from a group consisting of:

a system identifier of a multi-chassis stack;

a chassis identifier for an associated chassis within a multi-chassis stack;

a unit identifier for a computing unit within a chassis;

a slot identifier for a physical slot on a chassis; and

a bay identifier for a physical bay on a chassis.

17. The computer-readable media as in claim 13, wherein the software is executed by a network device operating system on a computer networking device.

18. An apparatus, comprising:

one or more network interfaces configured to communicate in a network of computer devices;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

interface with a distributed graph database that is distributed across the network of computer devices;

execute an application that has one or more parent data constructs that reference one or more child objects within the distributed graph database, wherein the one or more child objects each have a location-independent object identifier (OID) that models hierarchical relationships between nodes in the distributed graph database interconnected by the computer devices in the network, the OID including;

an OID-identifier (OID-ID) assigned to each particular child object by a data source of the location-independent OID,

an OID-source tupled to the OID-ID, the OID-source a pointer to a structure that uniquely identifies the data source of the location-independent OID within the network of computer devices, wherein the OID source structure identifies an exact location of origin of the one or more child objects in the distributed graph database, and

an OID-pointer indicative of a relative location of the particular child object in a memory mapped region, wherein lookup trees provide bidirectional mapping from OID-ID and OID-source tuples to OID-pointer values, and wherein the OID-pointer for a particular child object is cached within a particular parent data construct referencing a relative address of that particular child object; and

access the one or more child objects based on the location-independent OID.

19. The apparatus as in claim 18, wherein the OID-source comprises one or more identifications selected from a group consisting of:

a system identifier of a multi-chassis stack;

a chassis identifier for an associated chassis within a multi-chassis stack;

a unit identifier for a computing unit within a chassis;

a slot identifier for a physical slot on a chassis; and

a bay identifier for a physical bay on a chassis.

20. The apparatus as in claim 18, the process when executed further operable to:

generate, as a particular data source, a particular location-independent OID for a newly referenced child object, wherein generating comprises assigning a particular OID-ID to the newly referenced child object and combining the particular OID-ID with an OID-source that uniquely identifies the particular data source as an OID-ID and OID-source tuple;

cache the OID-ID and OID-source tuple within the newly referenced child object;

determine a particular OID-pointer value for the newly referenced child object based on a particular relative location of the newly referenced child object in a particular memory mapped region;

establish lookup trees that provide a bidirectional mapping from the OID-ID and OID-source tuple to the particular OID-pointer value; and

cache the particular OID-pointer value for the newly referenced child object within a corresponding parent data construct referencing the newly referenced child object.