Skip to content
This repository was archived by the owner on Dec 19, 2025. It is now read-only.

Usage

Jump to bottom
liqweed edited this page Jan 26, 2014 · 9 revisions

Graph Lifecycle

Use of the NetflixGraph library is expected to generally follow a lifecycle:

  1. Define an NFGraphSpec, which serves as the schema for the graph data.
  2. Instantiate an NFBuildGraph, then populate it with connections.
  3. Compress the NFBuildGraph, which will return a representation of the data as an NFCompressedGraph.
  4. Serialize the NFCompressedGraph to a stream. Netflix, for example, has a use case which streams this graph to Amazon Web Service’s S3.
  5. Deserialize the stream where the compact in-memory representation of the graph data is necessary.

Your code to create the graph will resemble the following:

NFGraphSpec spec = new NFGraphSpec( ... );

NFBuildGraph buildGraph = new NFBuildGraph(spec);

for( ... each connection between nodes ... ) {
    graph.addConnection( ... );
}

NFCompressedGraph compressedGraph = buildGraph.compress();

OutputStream os = ... stream to where you want the serialized data ...;

compressedGraph.writeTo(os);

And your code to read the graph back into memory will resemble:

InputStream is = ... stream from where the serialized data was written ...;

NFGraph graph = NFCompressedGraph.readFrom(is);

Defining a Schema

Before creating a graph, you will need to create an NFGraphSpec, which serves as a schema for your graph. The schema defines the types of nodes in your graph, and the properties which are available for each type of node.

For example, you may have a node type “Actor” and a node type “Movie”. “Actor” may point to “Movie” by some property “starredIn”. If this is a sufficient description of your data, you might define the following schema:

import static com.netflix.nfgraph.spec.NFPropertySpec.MULTIPLE;
import static com.netflix.nfgraph.spec.NFPropertySpec.COMPACT;

NFGraphSpec spec = new NFGraphSpec(
	new NFNodeSpec(
		"Actor",
		new NFPropertySpec("starredIn", "Movie", MULTIPLE | COMPACT)
	),
	new NFNodeSpec("Movie")
);

Notice the final parameter in the NFPropertySpec constructor. Each property is configured with options described using constants from the class NFPropertySpec. These properties can be mixed and matched using a bitwise OR (“|” as above) to describe a property specification. One property from each of the following groups may be chosen:

SINGLE or MULTIPLE
COMPACT or HASH
GLOBAL or MODEL_SPECIFIC

SINGLE properties will allow zero or one connection per node. MULTIPLE properties will allow zero to many connections.

COMPACT properties will be represented in an NFCompressedGraph as variable-byte deltas. HASH properties will be represented as variable-byte hashed arrays. See Compact Representations for more details.

GLOBAL properties will not segregate connections into connection models. MODEL_SPECIFIC properties will. See Connection Models for more details.

If options from each group are not chosen, the defaults are MULTIPLE | COMPACT | GLOBAL.

A graph specification contains multiple node specification, and each node specification contains multiple property specifications:

import static com.netflix.nfgraph.spec.NFPropertySpec.MULTIPLE;
import static com.netflix.nfgraph.spec.NFPropertySpec.SINGLE;
import static com.netflix.nfgraph.spec.NFPropertySpec.COMPACT;
import static com.netflix.nfgraph.spec.NFPropertySpec.HASH;

NFGraphSpec movieSchema = new NFGraphSpec(
	new NFNodeSpec(
		"Actor",
		new NFPropertySpec("starredIn", "Movie", MULTIPLE | COMPACT),
		new NFPropertySpec("costarredWith", "Actor", MULTIPLE | HASH),
		new NFPropertySpec("premieredIn", "Movie", SINGLE)
	),
	new NFNodeSpec(
		"Movie",
		new NFPropertySpec("rated", "Rating", SINGLE),
		new NFPropertySpec("starring", "Actor", MULTIPLE | HASH)
	),
        new NFNodeSpec("Rating")
);

Building the Graph

Now that you’ve defined the schema for the graph, you’ll need to populate it with some actual data. The first step is to instantiate an NFBuildGraph with your schema. You can use the schema from above:

NFBuildGraph buildGraph = new NFBuildGraph(movieSchema);

Now you want to add a movie “The Matrix”, starring “Keanu Reeves” and “Laurence Fishburne”, which is rated “R”.

In the NetflixGraph library, each node in your graph is expected to be uniquely represented as a “type” and “ordinal”. Each “type” will be referred to as a String; in our example, we have three types “Actor”, “Movie”, and “Rating”. An “ordinal” is an integer that uniquely defines the node given its type. If there are n objects of a given type, then those objects should each be assigned a unique ordinal value from 0 through (n-1). NetflixGraph provides an efficient and simple mechanism for creating and maintaining ordinal assignment with the class OrdinalMap.

Let’s say you want to refer to your nodes by their String representations. You’ll need some mechanism for translation between Strings and ordinals to use our NFBuildGraph. You can use the OrdinalMap to assign ordinals as follows:

OrdinalMap<String> movieOrdinals = new OrdinalMap<String>();
OrdinalMap<String> actorOrdinals = new OrdinalMap<String>();
OrdinalMap<String> ratingOrdinals = new OrdinalMap<String>();

int matrixOrdinal = movieOrdinals.add("The Matrix");

int keanuOrdinal = actorOrdinals.add("Keanu Reeves");
int laurenceOrdinal = actorOrdinals.add("Laurence Fishburn");

int ratedROrdinal = ratingOrdinals.add("R");

Now this mapping will be maintained so long as you have a handle to the movieOrdinals, actorOrdinals, and ratingOrdinals maps. You can add some relationships between these nodes using:

buildGraph.addConnection("Actor", keanuOrdinal, "starredIn", matrixOrdinal);
buildGraph.addConnection("Actor", laurenceOrdinal, "starredIn", matrixOrdinal);
buildGraph.addConnection("Movie", matrixOrdinal, "starring", keanuOrdinal);
buildGraph.addConnection("Movie", matrixOrdinal, "starring", laurenceOrdinal);
buildGraph.addConnection("Movie", matrixOrdinal, "rated", ratedROrdinal);

Your graph now has four connections populated. Now, since you’ve added all of your connections to the graph, you can compress to obtain a read-only, memory-efficient representation of the connections you’ve added:

NFCompressedGraph compressedGraph = buildGraph.compress();

Using the Graph

Once you have your compressed graph, you can discard the build graph. You will no longer need it.

You can use the compressed graph to find out who starred in The Matrix:

int matrixOrdinal = movieOrdinals.get("The Matrix");

OrdinalIterator iter = compressedGraph.getConnectionIterator("Movie", matrixOrdinal, "starring");

int currentOrdinal = iter.nextOrdinal();

while(currentOrdinal != OrdinalIterator.NO_MORE_ORDINALS) {
	System.out.println(actorOrdinals.get(currentOrdinal) + " starred in The Matrix!");
	currentOrdinal = iter.nextOrdinal();
}

Notice the use of an OrdinalIterator above. You can also choose to retrieve these connections as an OrdinalSet, which will allow you to determine the membership of a given node via the contains() operation. In the case of single connections, you can also retrieve values as a single int:

int ratedOrdinal = compressedGraph.getConnection("Movie", matrixOrdinal, "rating");
System.out.println("The Matrix is rated " + ratingOrdinals.get(ratedOrdinal);

Moving the Data

NetflixGraph is designed to be moved around your application infrastructure. You may want to build the graph on one machine, then move the compact serialized representation to another or many other machines. The NFCompressedGraph class defines methods to serialize and deserialize this data to a stream. For example, you could serialize this data to some file on the hard disk:

OutputStream os = new FileOutputStream("/tmp/some-file");
compressedGraph.writeTo(os);

And then deserialize it later:

InputStream is = new FileInputStream("/tmp/some-file");
NFCompressedGraph sameCompressedGraph = NFCompressedGraph.readFrom(is);

You’ll want to decide where this OutputStream writes to, and the details about how this data ends up on the right machine is up to you. In addition, this data will not automatically include the details about your nodes, so you will likely want to include this in your serialized representation. In the example above, you might include these mappings as follows:

DataOutputStream out = new DataOutputStream(someOutputStream);
serializeNodeDetails(movieOrdinals, out);
serializeNodeDetails(actorOrdinals, out);
serializeNodeDetails(ratingOrdinals, out);
compressedGraph.writeTo(out);
out.close();

... 

public void serializeNodeDetails(OrdinalMap<String> nodeMap, DataOutputStream out) {
	out.writeInt(nodeMap.size());
	for(String node : nodeMap) {
		out.writeUTF(node);
	}
}

And then when deserializing:

DataInputStream is = new DataInputStream(someInputStream);
OrdinalMap<String> movieOrdinals = deserializeNodeDetails(is);
OrdinalMap<String> actorOrdinals = deserializeNodeDetails(is);
OrdinalMap<String> ratingOrdinals = deserializeNodeDetails(is);
NFGraph graph = NFCompressedGraph.readFrom(is);
is.close();

...

public OrdinalMap<String> deserializeNodeDetails(DataInputStream is) {
        int size = is.readInt();
	OrdinalMap<String> map = new OrdinalMap<String>(size);
	for(int i=0;i<size;i++) {
		map.add(is.readUTF());
	}
	return map;
}

Of course, this is just a helpful example. The serialized representation of your node objects is entirely up to you. The NetflixGraph library only provides functionality to generate a serialized representation of the NFCompressedGraph itself.

Thread safety: Please note that currently, adding connections to the NFBuildGraph is not a thread-safe operation. Accessing data from the compressed graph is read-only, and therefore thread-safe.

Clone this wiki locally