flink-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Vasiliki Kalavri <vasilikikala...@gmail.com>
Subject Re: [gelly] Spargel model rework
Date Tue, 27 Oct 2015 18:10:43 GMT
@Martin: thanks for your input! If you ran into any other issues that I
didn't mention, please let us know. Obviously, even with my proposal, there
are still features we cannot support, e.g. updating edge values and graph
mutations. We'll need to re-think the underlying iteration and/or graph
representation for those.

@Fabian: thanks a lot, no rush :)
Let me give you some more information that might make it easier to reason
about performance:

Currently, in Spargel the SolutionSet (SS) keeps the vertex state and the
workset (WS) keeps the active vertices. The iteration is composed of 2
coGroups. The first one takes the WS and the edges and produces messages.
The second one takes the messages and the SS and produced the new WS and
the SS-delta.

In my proposal, the SS has the vertex state and the WS has <vertexId,
MessageIterator> pairs, i.e. the inbox of each vertex. The plan is more
complicated because compute() needs to have two iterators: over the edges
and over the messages.
First, I join SS and WS to get the active vertices (have received a msg)
and their current state. Then I coGroup the result with the edges to access
the neighbors. Now the main problem is that this coGroup needs to have 2
outputs: the new messages and the new vertex value. I couldn't really find
a nice way to do this, so I'm emitting a Tuple that contains both types and
I have a flag to separate them later with 2 flatMaps. From the vertex
flatMap, I crete the SS-delta and from the messaged flatMap I apply a
reduce to group the messages by vertex and send them to the new WS. One
optimization would be to expose a combiner here to reduce message size.

tl;dr:
1. 2 coGroups vs. Join + coGroup + flatMap + reduce
2. how can we efficiently emit 2 different types of records from a coGroup?
3. does it make any difference if we group/combine the messages before
updating the workset or after?

Cheers,
-Vasia.


On 27 October 2015 at 18:39, Fabian Hueske <fhueske@gmail.com> wrote:

> I'll try to have a look at the proposal from a performance point of view in
> the next days.
> Please ping me, if I don't follow up this thread.
>
> Cheers, Fabian
>
> 2015-10-27 18:28 GMT+01:00 Martin Junghanns <m.junghanns@mailbox.org>:
>
> > Hi,
> >
> > At our group, we also moved several algorithms from Giraph to Gelly and
> > ran into some confusing issues (first in understanding, second during
> > implementation) caused by the conceptional differences you described.
> >
> > If there are no concrete advantages (performance mainly) in the Spargel
> > implementation, we would be very happy to see the Gelly API be aligned to
> > Pregel-like systems.
> >
> > Your SSSP example speaks for itself. Straightforward, if the reader is
> > familiar with Pregel/Giraph/...
> >
> > Best,
> > Martin
> >
> >
> > On 27.10.2015 17:40, Vasiliki Kalavri wrote:
> >
> >> Hello squirrels,
> >>
> >> I want to discuss with you a few concerns I have about our current
> >> vertex-centric model implementation, Spargel, now fully subsumed by
> Gelly.
> >>
> >> Spargel is our implementation of Pregel [1], but it violates some
> >> fundamental properties of the model, as described in the paper and as
> >> implemented in e.g. Giraph, GPS, Hama. I often find myself confused both
> >> when trying to explain it to current Giraph users and when porting my
> >> Giraph algorithms to it.
> >>
> >> More specifically:
> >> - in the Pregel model, messages produced in superstep n, are received in
> >> superstep n+1. In Spargel, they are produced and consumed in the same
> >> iteration.
> >> - in Pregel, vertices are active during a superstep, if they have
> received
> >> a message in the previous superstep. In Spargel, a vertex is active
> during
> >> a superstep if it has changed its value.
> >>
> >> These two differences require a lot of rethinking when porting
> >> applications
> >> and can easily cause bugs.
> >>
> >> The most important problem however is that we require the user to split
> >> the
> >> computation in 2 phases (2 UDFs):
> >> - messaging: has access to the vertex state and can produce messages
> >> - update: has access to incoming messages and can update the vertex
> value
> >>
> >> Pregel/Giraph only expose one UDF to the user:
> >> - compute: has access to both the vertex state and the incoming
> messages,
> >> can produce messages and update the vertex value.
> >>
> >> This might not seem like a big deal, but except from forcing the user to
> >> split their program logic into 2 phases, Spargel also makes some common
> >> computation patterns non-intuitive or impossible to write. A very simple
> >> example is propagating a message based on its value or sender ID. To do
> >> this with Spargel, one has to store all the incoming messages in the
> >> vertex
> >> value (might be of different type btw) during the messaging phase, so
> that
> >> they can be accessed during the update phase.
> >>
> >> So, my first question is, when implementing Spargel, were other
> >> alternatives considered and maybe rejected in favor of performance or
> >> because of some other reason? If someone knows, I would love to hear
> about
> >> them!
> >>
> >> Second, I wrote a prototype implementation [2] that only exposes one
> UDF,
> >> compute(), by keeping the vertex state in the solution set and the
> >> messages
> >> in the workset. This way all previously mentioned limitations go away
> and
> >> the API (see "SSSPComputeFunction" in the example [3]) looks a lot more
> >> like Giraph (see [4]).
> >>
> >> I have not run any experiments yet and the prototype has some ugly
> hacks,
> >> but if you think any of this makes sense, then I'd be willing to follow
> up
> >> and try to optimize it. If we see that it performs well, we can consider
> >> either replacing Spargel or adding it as an alternative.
> >>
> >> Thanks for reading this long e-mail and looking forward to your input!
> >>
> >> Cheers,
> >> -Vasia.
> >>
> >> [1]: https://kowshik.github.io/JPregel/pregel_paper.pdf
> >> [2]:
> >>
> >>
> https://github.com/vasia/flink/tree/spargel-2/flink-libraries/flink-gelly/src/main/java/org/apache/flink/graph/spargelnew
> >> [3]:
> >>
> >>
> https://github.com/vasia/flink/blob/spargel-2/flink-libraries/flink-gelly/src/main/java/org/apache/flink/graph/spargelnew/example/SSSPCompute.java
> >> [4]:
> >>
> >>
> https://github.com/grafos-ml/okapi/blob/master/src/main/java/ml/grafos/okapi/graphs/SingleSourceShortestPaths.java
> >>
> >>
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message