[TinkerPop3] Lapin' up GraphComputer RFC

284 views
Skip to first unread message

Marko Rodriguez

unread,
Nov 13, 2013, 5:37:31 PM11/13/13
to gremli...@googlegroups.com
Hello,

We have finally converged on the OLAP system for TinkerPop3 -- GraphComputer. For those graph systems that implement the GraphComputer interfaces, they will be able to leverage:

1. Global graph algorithms provided by Gremlin (no more Furnace) -- e.g. PageRank, clustering, swarm computing, etc.
2. Gremlin OLAP (i.e. "Faunus" goes to TinkerPop and Titan takes over Faunus' Hadoop implementation).
3. Bulk parallel graph mutations -- update all vertices/edges in parallel.

To use GraphComputer, the underlying Graph must implement Graph.compute().
This returns a GraphComputer engine that can submitted VertexProgram.
A VertexProgram is a "program" that is executed at every vertex in the graph in parallel. When a vertex wants to communicate information to another vertex, it passes "messages" via the Messenger interface.
This interface is the key to our progress. Originally, there was no such interface and the semantics of a VertexProgram was that the current vertex could get the state of its neighbors and update it own state. This was Matthias Bröcheler's design and it is great for single machine systems (Fulgora) where you have shared memory and no locking as only the current vertex can update it state (much better than message passing queues for single machines). For systems like Faunus/Giraph/HAMA/etc, this becomes painful as you have to communicate all neighbor state to all adjacents regardless of their ultimate use or not. Moreover, all algorithms are written "in reverse." As such we were at an impasse for some time. With Messenger being the new intermediate interface, its up to the underlying Graph to decide to implement it as "message passing" or "shared state." This means now systems like Giraph (distributed  memory) and TinkerGraph (shared memory) can have the same VertexPrograms running over them!

For instance, see how TinkerGraph implements GraphComputer and Messenger.

Interested in how PageRank is implemented?
Looks a lot like "Pregel"-style system message passing. Again, TinkerGraph doesn't "message pass" (it shares state). Giraph can't "share state" cause its a distributed system so it will use message passing.

Please review and provide any questions or comments you may have.

Enjoy!,
Marko.

Marko Rodriguez

unread,
Dec 2, 2013, 6:29:02 PM12/2/13
to gremli...@googlegroups.com
Hello everyone,

Matthias and I just finished up a call on the OLAP aspects of Blueprints3. Beyond the notes from the previous RFC, we have some new additions:

1. MessageType.Local or MessageType.Global?

When you send a message, you know state whether the message is a global message (directed by a GraphQuery) or a local message (directed by VertexQuery). 


We had the notion of GraphQuery/VertexQuery as the message router previous, but needed a way to "label" (identify) the message type as well as provide auxiliary information such as a lambda to use on the edge propagating the message (e.g. modulate the message based upon properties of the edge that it is being propagated over). Now, looking at PageRankVertexProgram, we see it as:

- in short, a MessageType.Local is used to route "pageRank" messages around the graph with the edge modulator being the identity function (e,m) -> m.

If you want it to be weighted PageRank and thus module the <Double> message by the edge weight, you can do:
- in short, provide a BiFunction lambda.

2. So Many Features My Pinky Hurts!


We added the respective features that any GraphComputer implementation will need to specify. Note that for implementations like Faunus (Hadoop-based) you will be able to add/remove vertices/edges/properties. As it stands, this is how you use Faunus currently with linkOut(), linkIn(), linkBoth(), drop(), keep(), and respective set/removeProperties. I believe Giraph also supports runtime graph mutations as well. Moreover, TinkerGraphComputer allows such mutations as well. Systems like "Fulgora" (Titan's in-memory OLAP system) will not allow for such mutations and will be a read-only GraphComputer. Thus, making these explicit as Features is necessary so when a VertexProgram goes to execute, it can verify that the GraphComputer it is running on allows such behaviors.

Thoughts are more than welcome.

Marko.

Viktoras Veitas

unread,
Jan 3, 2014, 7:16:56 AM1/3/14
to gremli...@googlegroups.com
Hi Marko,

Reading interfaces is hard to me. Therefore I am trying to guess the general ideas and the process is probably influenced by my faculty of wishful thinking...  Anyway, could you comment on the following.

Recently I was trying to wrap my mind around the idea of merging an Actor model (say, implemented on Gpars) and Blueprints enabled distributed graph (say Titan on Cassandra) for implementing asynchronous message passing model with an explicit topology - something that I start to day dream about. Actors would be represented as vertexes in the graph; message passing - as vertex centric traversals. Now when I read your mails about TinkerPop3's VertexProgram, Messenger, MessageType.Local, etc, I cannot get rid of associations with the Actor model, which is a nice abstraction in my view.

So, the question: you talk of implementing 'Pregel' type graph computing with TinkerPop3 which follows the Bulk Synchronization Parallel model, which was tried out within Furnace project, I guess. What about completely asynchronous message passing as explained above? It seems close to my unexperienced eye..

Thanks a lot,
Viktoras


--
You received this message because you are subscribed to the Google Groups "Gremlin-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gremlin-user...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Marko Rodriguez

unread,
Jan 3, 2014, 10:54:33 AM1/3/14
to gremli...@googlegroups.com
Hello Viktoras,

GraphComputer supports both BSP and Dirty BSP, but NOT full asynchrony. Dirty BSP is a memory efficient BSP model where you don't keep two vectors around --- the properties in the previous BSP cycle and the properties in the current BSP cycle. Thus, you don't have full isolation between the two steps --- but the gain is you only have one vector of memory.

In terms of the actor model, you can think of GraphComputer as implementing the actor model where each vertex is a "thread/actor/agent" and you are propagating messages between them. The flow for a particular vertex is as such:

1. Read all incoming messages.
2. Do something with those messages.
3. Update your local state in some way (e.g. setProperty())
4. Send messages to other vertices (both adjacent and arbitrary recipients supported).

1-4 is repeated over and over and over until a termination point is reached. The model above is not new and has been around for some time with Pregel, HAMA, Giraph, and Faunus. There are various tweaks to the model that we think are neat:

1. If you are sending messages to neighbors in a single machine implementation, you can greatly reduce the amount of messages sent using a "blackboard" behind the scenes.
2. However, global message passing (arbitrary receivers) is possible like in the classic message passing systems.
2. While the vertex is the message's receiver, you can address a vertex, its properties, its edges, or its edge properties.
3. It uses a fluent interface to build VertexPrograms and will have a nice look and feel in the Gremlin3 REPL.

Finally, there are two ways to think of this as "the actor model." When you look at this pattern from the Gremlin perspective you start to see the messages as the actors and the graph as the communication substrate. In Gremlin OLAP, the messages (i.e. gremlins) are complex objects that store state and move about the graph according to the rule system dictated by the GremlinPipeline. In this way, you can decide where you want the computation to be represented --- in the vertex or in the message. The Gremlin perspective comes from "swarm computing" where you think of your messages as having the computing logic, not the VertexProgram. 

HTH,
Marko.

Viktoras Veitas

unread,
Jan 6, 2014, 2:05:36 PM1/6/14
to gremli...@googlegroups.com
Hello Marko,
Thanks for the explanation. It does help.

Couple of additional questions:

On Fri, Jan 3, 2014 at 4:54 PM, Marko Rodriguez <okram...@gmail.com> wrote:
GraphComputer supports both BSP and Dirty BSP, but NOT full asynchrony. Dirty BSP is a memory efficient BSP model where you don't keep two vectors around --- the properties in the previous BSP cycle and the properties in the current BSP cycle. Thus, you don't have full isolation between the two steps --- but the gain is you only have one vector of memory.
 
Do you by chance know any references where Dirty BSP is explained in more detail? I would like to understand it a little better...
 
In Gremlin OLAP, the messages (i.e. gremlins) are complex objects that store state and move about the graph according to the rule system dictated by the GremlinPipeline. In this way, you can decide where you want the computation to be represented --- in the vertex or in the message. The Gremlin perspective comes from "swarm computing" where you think of your messages as having the computing logic, not the VertexProgram. 


Not really related to the original question, but: is there chance that particles in the particle swarm could be connected with links (in a similar style as vertexes in a graph)? This sounds stupid maybe and does not make sense for things like metadata propagation explained in the second article, but it may make sense when thinking in terms of actor model.
 
Thank you,
Viktoras
Reply all
Reply to author
Forward
0 new messages