Generating new and unique distributed graph ID

Abstract

Techniques are provided for finding unused vertex and edge identifiers (IDs) in a distributed graph engine. A run-time data structure may be built during the loading of the graph. The data structure identifies unavailable IDs that are associated with graph entities of the graph. The data structure is traversed to determine one or more ranges of free IDs. Unused IDs are generated from the ranges.

What is claimed is: 
     
       1. A method comprising:
 during a loading of a graph that is distributed in a multi-node computing system into memory, determining a plurality of available IDs, each of which is unique, for a plurality of unidentified graph components of the graph; 
 wherein the graph comprises a plurality of existing graph components and is distributed in the multi-node computing system, wherein each vertex in the graph is in a node in the multi-node computing system and each edge in the graph connects a source vertex with a destination vertex in the graph; 
 wherein each of the plurality of unidentified graph components is a vertex or an edge, in the graph, that is not associated with a unique ID; 
 wherein determining the plurality of available IDs for the plurality of unidentified graph components comprises:
 at each node in the multi-node computing system:
 generating a local data structure comprising a plurality of arrays; 
 wherein each of the plurality of arrays comprises K slots, K being a whole number greater than one, wherein the K slots of a respective array representing a subdomain of identifiers associated with a domain of possible identifiers; 
 wherein the plurality of arrays includes a root array in a root layer associated with the domain, a plurality of parent arrays, and a plurality of child arrays, wherein each child array of the plurality of arrays is linked with a slot in a respective parent array; 
 wherein a property of each slot in each of the plurality of arrays indicates an availability of IDs, in the subdomain represented by a respective slot; and 
 wherein generating the local data structure comprises, for each of the plurality of existing graph components:
 inserting an ID of a respective existing graph component into a corresponding slot in the local data structure; and 
 deleting all sublayers of the corresponding slot responsive to determining the corresponding slot is full; 
 
 
 
 generating a merged data structure using data from the local data structure and data from local data structures associated with other nodes in the multi-node computing system; and 
 traversing the merged data structure to identify the plurality of available IDs based on the property of each slot in the merged data structure. 
 
     
     
       2. The method of  claim 1 , wherein each available ID is an integer ID, a string ID, or a composite ID. 
     
     
       3. The method of  claim 1 , wherein inserting the ID of the respective existing graph component into the corresponding slot in the local data structure comprises:
 responsive to determining the corresponding slot is empty:
 instantiating new sublayers until a maximum depth is reached; and 
 setting a count to one for all visited slots and setting the count to zero for all other slots; 
 
 responsive to determining the corresponding slot is not empty, recursively iterating the local data structure and updating the count of each visited slot. 
 
     
     
       4. The method of  claim 1 , wherein traversing the merged data structure comprises:
 for each leaf slot in the merged data structure, starting from the left-most slot of the merged data structure to the right-most slot of the merged data structure:
 iterating the merged data structure from a respective leaf slot until a visited slot is non-empty; and 
 identifying a subdomain of available IDs from the respective leaf slot to a slot prior to the non-empty slot. 
 
 
     
     
       5. The method of  claim 1 , wherein generating the local data structure comprises:
 creating the root array, wherein the root array is associated with a plurality of allowed characters; 
 for each of the plurality of existing graph components, inserting an ID of a respective existing graph component, character by character of the ID, into in the local data structure, wherein inserting the ID includes creating a new array for a particular character of the ID when a specific array for the particular character does not exist. 
 
     
     
       6. The method of  claim 5 , wherein a depth of the local data structure is a number of characters in a prefix. 
     
     
       7. The method of  claim 5 , wherein concatenation of each character in a plurality of slots that are linked forms a prefix. 
     
     
       8. The method of  claim 1 , wherein traversing the merged data structure comprises traversing the merged data structure in a breadth-first manner and identifying a subdomain of available IDs from array indices that have null pointers or Boolean set to false. 
     
     
       9. The method of  claim 1 , further comprising generating a particular available ID from the plurality of available IDs and assigning the particular available ID to a particular graph component of the plurality of unidentified graph components. 
     
     
       10. The method of  claim 9 , wherein the particular graph component is stored on a particular node that is associated with the particular available ID. 
     
     
       11. One or more non-transitory storage media storing sequences of instructions which, when executed by one or more processors, cause:
 during a loading of a graph that is distributed in a multi-node computing system into memory, determining a plurality of available IDs, each of which is unique, for a plurality of unidentified graph components of the graph; 
 wherein the graph comprises a plurality of existing graph components and is distributed in the multi-node computing system, wherein each vertex in the graph is in a node in the multi-node computing system and each edge in the graph connects a source vertex with a destination vertex in the graph; 
 wherein each of the plurality of unidentified graph components is a vertex or an edge, in the graph, that is not associated with a unique ID; 
 wherein determining the plurality of available IDs for the plurality of unidentified graph components comprises:
 at each node in the multi-node computing system:
 generating a local data structure comprising a plurality of arrays; 
 wherein each of the plurality of arrays comprises K slots, K being a whole number greater than one, wherein the K slots of a respective array representing a subdomain of identifiers associated with a domain of possible identifiers; 
 wherein the plurality of arrays includes a root array in a root layer associated with the domain, a plurality of parent arrays, and a plurality of child arrays, wherein each child array of the plurality of arrays is linked with a slot in a respective parent array; 
 wherein a property of each slot in each of the plurality of arrays indicates an availability of IDs, in the subdomain represented by a respective slot; and 
 wherein generating the local data structure comprises, for each of the plurality of existing graph components:
 inserting an ID of a respective existing graph component into a corresponding slot in the local data structure; and 
 deleting all sublayers of the corresponding slot responsive to determining the corresponding slot is full; 
 
 
 
 generating a merged data structure using data from the local data structure and data from local data structures associated with other nodes in the multi-node computing system; and 
 traversing the merged data structure to identify the plurality of available IDs based on the property of each slot in the merged data structure. 
 
     
     
       12. The one or more non-transitory storage media of  claim 11 , wherein each available ID is an integer ID, a string ID, or a composite ID. 
     
     
       13. The one or more non-transitory storage media of  claim 11 , wherein inserting the ID of the respective existing graph component into the corresponding slot in the local data structure comprises:
 responsive to determining the corresponding slot is empty:
 instantiating new sublayers until a maximum depth is reached; and 
 setting a count to one for all visited slots and setting the count to zero for all other slots; 
 
 responsive to determining the corresponding slot is not empty, recursively iterating the local data structure and updating the count of each visited slot. 
 
     
     
       14. The one or more non-transitory storage media of  claim 11 , wherein traversing the merged data structure comprises:
 for each leaf slot in the merged data structure, starting from the left-most slot of the merged data structure to the right-most slot of the merged data structure:
 iterating the merged data structure from a respective leaf slot until a visited slot is non-empty; and 
 identifying a subdomain of available IDs from the respective leaf slot to a slot prior to the non-empty slot. 
 
 
     
     
       15. The one or more non-transitory storage media of  claim 11 , wherein generating the local data structure comprises:
 creating the root array, wherein the root array is associated with a plurality of allowed characters; 
 for each of the plurality of existing graph components, inserting an ID of a respective existing graph component, character by character of the ID, into in the local data structure, wherein inserting the ID includes creating a new array for a particular character of the ID when a specific array for the particular character does not exist. 
 
     
     
       16. The one or more non-transitory storage media of  claim 15 , wherein a depth of the local data structure is a number of characters in a prefix. 
     
     
       17. The one or more non-transitory storage media of  claim 15 , wherein concatenation of each character in a plurality of slots that are linked forms a prefix. 
     
     
       18. The one or more non-transitory storage media of  claim 11 , wherein traversing the merged data structure comprises traversing the merged data structure in a breadth-first manner and identifying a subdomain of available IDs from array indices that have null pointers or Boolean set to false. 
     
     
       19. The one or more non-transitory storage media of  claim 11 , wherein the sequences of instructions which, when executed by the one or more processors, further cause generating a particular available ID from the plurality of available IDs and assigning the particular available ID to a particular graph component of the plurality of unidentified graph components. 
     
     
       20. The one or more non-transitory storage media of  claim 19 , wherein the particular graph component is stored on a particular node that is associated with the particular available ID.