You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@tinkerpop.apache.org by Marko Rodriguez <ok...@gmail.com> on 2019/05/14 00:08:13 UTC

N-Tuple Transactions?

Hello Josh (others),

You mentioned a week or so ago that the n-tuple model should be able to capture both indices and transactions.

At the time, I scoffed at the notion. However, as you know, I have been recently enlightened to how n-tuples can model indices and am using it extensively in the spec. What I would like to contemplate now is how you figure transactions being modeled?

Thanks,
Marko.

http://rredux.com <http://rredux.com/>





Re: N-Tuple Transactions?

Posted by Stephen Mallette <sp...@gmail.com>.
> without it, the same programs may have different results when executed on
different databases.

It would be nice if we could make it so that TinkerPop-level transactions
allowed for more control over the expectations of a traversal. There are
many instances where mutation oriented traversals have different results
depending on the backend and what it does from a transactional standpoint
in relation not only to the mutations but also to how it handles read
operations that might follow later in that same traversal. If we could
always assure the same result no matter what the backend was, that would be
huge. I imagine though that this "tuple-transactions" don't have any magic
to them and that building a unified transaction system in TinkerPop will
still be "hard".

On Wed, May 15, 2019 at 12:34 PM Joshua Shinavier <jo...@fortytwo.net> wrote:

> Tough question, since I have not used Akka or the actor model, but here are
> some first thoughts. From what I am reading, the trick would be to
> implement the transaction log as a CRDT
> <https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type>.
> Operation-based CRDTs -- which propagate individual mutations as opposed to
> local state -- appear to be preferable if mutations are commutative. So are
> they commutative? In the "imperative" scenario I described to Stephen, no.
> In the "functional" scenario, yes, they have to be. Suppose you insert a
> vertex and also delete that vertex. The eventually consistent result of the
> transaction must be a no-op; if the vertex already exists, leave it alone.
> If it does not exist, do not create it. However, it does not matter in what
> order you perform the insert and delete -- once all operations are
> accounted for, you arrive at the correct state.
>
> Just from what I glean from Wikipedia, there appear to be a handful of
> well-known strategies for operation-based and state-based CRDTs. I do not
> know how hard it would be to support multiple strategies in the same VM,
> but in the Akka world, that seems to be the way in which you would choose
> your operational semantics.
>
> Josh
>
>
>
>
> On Wed, May 15, 2019 at 8:00 AM Marko Rodriguez <ok...@gmail.com>
> wrote:
>
> > Wow. I totally understood what you wrote.
> >
> > Question: What is the TransactionLog in a distributed environment?
> >                         e.g. Akka-driven traversers spawned from the same
> > query migrating around the cluster mutating stuff.
> >
> > Thanks for the lesson,
> > Marko.
> >
> > http://rredux.com <http://rredux.com/>
> >
> >
> >
> >
> > > On May 15, 2019, at 8:58 AM, Joshua Shinavier <jo...@fortytwo.net>
> wrote:
> > >
> > > Hi Stephen,
> > >
> > > More the latter. TinkerPop transactions would be layered on top of the
> > > native transactions of the database (if any), which gives the VM more
> > > control over the operational semantics of a computation in between
> > database
> > > commits. For example, in many scenarios it would be desirable not to
> > mutate
> > > the graph at all until a traversal has completed, so that the result
> does
> > > not depend on the order of evaluation. Consider a traversal which adds
> or
> > > deletes elements as it goes. In some cases, you want writes and reads
> to
> > > build on each other, so that what you wrote in one step is accessible
> for
> > > reading in the next step. This is a very imperative style of traversal
> > for
> > > which you need to understand how the VM builds a query plan in order to
> > > predict the result. In many other cases, you might prefer a more
> > functional
> > > approach, for which you can forget about the query plan. Without
> VM-level
> > > transactions, you don't have this choice; you are at the mercy of the
> > > underlying database. The extra level of control will be useful for
> > > concurrency and parallelism, as well -- without it, the same programs
> may
> > > have different results when executed on different databases.
> > >
> > > Josh
> > >
> > >
> > >
> > >
> > > On Wed, May 15, 2019 at 6:47 AM Stephen Mallette <spmallette@gmail.com
> >
> > > wrote:
> > >
> > >> Hi Josh, interesting... we have graphs with everything from no
> > transactions
> > >> like TinkerGraph to more acid transactional systems and everything in
> > >> between - will transaction support as you describe it cover all the
> > >> different transactional semantics of the underlying graphs which we
> > might
> > >> encounter? or is this an approach that helps unify those different
> > >> transactional semantics under TinkerPop's definition of a transaction?
> > >>
> > >> On Wed, May 15, 2019 at 9:23 AM Joshua Shinavier <jo...@fortytwo.net>
> > >> wrote:
> > >> [...]
> >
> >
>

Re: N-Tuple Transactions?

Posted by Joshua Shinavier <jo...@fortytwo.net>.
Tough question, since I have not used Akka or the actor model, but here are
some first thoughts. From what I am reading, the trick would be to
implement the transaction log as a CRDT
<https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type>.
Operation-based CRDTs -- which propagate individual mutations as opposed to
local state -- appear to be preferable if mutations are commutative. So are
they commutative? In the "imperative" scenario I described to Stephen, no.
In the "functional" scenario, yes, they have to be. Suppose you insert a
vertex and also delete that vertex. The eventually consistent result of the
transaction must be a no-op; if the vertex already exists, leave it alone.
If it does not exist, do not create it. However, it does not matter in what
order you perform the insert and delete -- once all operations are
accounted for, you arrive at the correct state.

Just from what I glean from Wikipedia, there appear to be a handful of
well-known strategies for operation-based and state-based CRDTs. I do not
know how hard it would be to support multiple strategies in the same VM,
but in the Akka world, that seems to be the way in which you would choose
your operational semantics.

Josh




On Wed, May 15, 2019 at 8:00 AM Marko Rodriguez <ok...@gmail.com>
wrote:

> Wow. I totally understood what you wrote.
>
> Question: What is the TransactionLog in a distributed environment?
>                         e.g. Akka-driven traversers spawned from the same
> query migrating around the cluster mutating stuff.
>
> Thanks for the lesson,
> Marko.
>
> http://rredux.com <http://rredux.com/>
>
>
>
>
> > On May 15, 2019, at 8:58 AM, Joshua Shinavier <jo...@fortytwo.net> wrote:
> >
> > Hi Stephen,
> >
> > More the latter. TinkerPop transactions would be layered on top of the
> > native transactions of the database (if any), which gives the VM more
> > control over the operational semantics of a computation in between
> database
> > commits. For example, in many scenarios it would be desirable not to
> mutate
> > the graph at all until a traversal has completed, so that the result does
> > not depend on the order of evaluation. Consider a traversal which adds or
> > deletes elements as it goes. In some cases, you want writes and reads to
> > build on each other, so that what you wrote in one step is accessible for
> > reading in the next step. This is a very imperative style of traversal
> for
> > which you need to understand how the VM builds a query plan in order to
> > predict the result. In many other cases, you might prefer a more
> functional
> > approach, for which you can forget about the query plan. Without VM-level
> > transactions, you don't have this choice; you are at the mercy of the
> > underlying database. The extra level of control will be useful for
> > concurrency and parallelism, as well -- without it, the same programs may
> > have different results when executed on different databases.
> >
> > Josh
> >
> >
> >
> >
> > On Wed, May 15, 2019 at 6:47 AM Stephen Mallette <sp...@gmail.com>
> > wrote:
> >
> >> Hi Josh, interesting... we have graphs with everything from no
> transactions
> >> like TinkerGraph to more acid transactional systems and everything in
> >> between - will transaction support as you describe it cover all the
> >> different transactional semantics of the underlying graphs which we
> might
> >> encounter? or is this an approach that helps unify those different
> >> transactional semantics under TinkerPop's definition of a transaction?
> >>
> >> On Wed, May 15, 2019 at 9:23 AM Joshua Shinavier <jo...@fortytwo.net>
> >> wrote:
> >> [...]
>
>

Re: N-Tuple Transactions?

Posted by Marko Rodriguez <ok...@gmail.com>.
Wow. I totally understood what you wrote.

Question: What is the TransactionLog in a distributed environment?
			e.g. Akka-driven traversers spawned from the same query migrating around the cluster mutating stuff.

Thanks for the lesson,
Marko.

http://rredux.com <http://rredux.com/>




> On May 15, 2019, at 8:58 AM, Joshua Shinavier <jo...@fortytwo.net> wrote:
> 
> Hi Stephen,
> 
> More the latter. TinkerPop transactions would be layered on top of the
> native transactions of the database (if any), which gives the VM more
> control over the operational semantics of a computation in between database
> commits. For example, in many scenarios it would be desirable not to mutate
> the graph at all until a traversal has completed, so that the result does
> not depend on the order of evaluation. Consider a traversal which adds or
> deletes elements as it goes. In some cases, you want writes and reads to
> build on each other, so that what you wrote in one step is accessible for
> reading in the next step. This is a very imperative style of traversal for
> which you need to understand how the VM builds a query plan in order to
> predict the result. In many other cases, you might prefer a more functional
> approach, for which you can forget about the query plan. Without VM-level
> transactions, you don't have this choice; you are at the mercy of the
> underlying database. The extra level of control will be useful for
> concurrency and parallelism, as well -- without it, the same programs may
> have different results when executed on different databases.
> 
> Josh
> 
> 
> 
> 
> On Wed, May 15, 2019 at 6:47 AM Stephen Mallette <sp...@gmail.com>
> wrote:
> 
>> Hi Josh, interesting... we have graphs with everything from no transactions
>> like TinkerGraph to more acid transactional systems and everything in
>> between - will transaction support as you describe it cover all the
>> different transactional semantics of the underlying graphs which we might
>> encounter? or is this an approach that helps unify those different
>> transactional semantics under TinkerPop's definition of a transaction?
>> 
>> On Wed, May 15, 2019 at 9:23 AM Joshua Shinavier <jo...@fortytwo.net>
>> wrote:
>> [...]


Re: N-Tuple Transactions?

Posted by Joshua Shinavier <jo...@fortytwo.net>.
Hi Stephen,

More the latter. TinkerPop transactions would be layered on top of the
native transactions of the database (if any), which gives the VM more
control over the operational semantics of a computation in between database
commits. For example, in many scenarios it would be desirable not to mutate
the graph at all until a traversal has completed, so that the result does
not depend on the order of evaluation. Consider a traversal which adds or
deletes elements as it goes. In some cases, you want writes and reads to
build on each other, so that what you wrote in one step is accessible for
reading in the next step. This is a very imperative style of traversal for
which you need to understand how the VM builds a query plan in order to
predict the result. In many other cases, you might prefer a more functional
approach, for which you can forget about the query plan. Without VM-level
transactions, you don't have this choice; you are at the mercy of the
underlying database. The extra level of control will be useful for
concurrency and parallelism, as well -- without it, the same programs may
have different results when executed on different databases.

Josh




On Wed, May 15, 2019 at 6:47 AM Stephen Mallette <sp...@gmail.com>
wrote:

> Hi Josh, interesting... we have graphs with everything from no transactions
> like TinkerGraph to more acid transactional systems and everything in
> between - will transaction support as you describe it cover all the
> different transactional semantics of the underlying graphs which we might
> encounter? or is this an approach that helps unify those different
> transactional semantics under TinkerPop's definition of a transaction?
>
> On Wed, May 15, 2019 at 9:23 AM Joshua Shinavier <jo...@fortytwo.net>
> wrote:
> [...]

Re: N-Tuple Transactions?

Posted by Stephen Mallette <sp...@gmail.com>.
Hi Josh, interesting... we have graphs with everything from no transactions
like TinkerGraph to more acid transactional systems and everything in
between - will transaction support as you describe it cover all the
different transactional semantics of the underlying graphs which we might
encounter? or is this an approach that helps unify those different
transactional semantics under TinkerPop's definition of a transaction?

On Wed, May 15, 2019 at 9:23 AM Joshua Shinavier <jo...@fortytwo.net> wrote:

> Hi Marko,
>
> Get ready for monads
> <https://en.wikipedia.org/wiki/Monad_(functional_programming)>. I
> mentioned
> them in my post
> <https://groups.google.com/d/msg/gremlin-users/MPNdNOAnYbs/sbowvioiDgAJ>
> on
> algebraic property graphs. In functional programming, monads are a typical
> way of composing chains of stateful operations together in such that they
> do not violate functional purity. For example, an operation which adds a
> vertex to a graph can be thought of as a function f : Graph -> Graph that
> takes a graph as its input, adds a vertex, and returns the resulting graph
> as its output. The function f doesn't actually mutate the graph on disk,
> but it gives you an in-memory representation of the mutated graph, which
> can then be persisted to disk. Some things you need in order to make this
> work:
>
> 1) a snapshot of the state of the graph / database as it existed when the
> transaction was started
> 2) a transaction log, within the TinkerPop VM, containing all atomic
> changes that were made to the graph since the transaction was started
> 3) a view of the graph overlaid with the contents of the transaction log
> 4) the ability to persist the transaction log to the database
>
> Items (1) and (4) are pretty trivial if the underlying database itself
> supports transactions. Item (2) is easy if we use a basic state monad. More
> on that below. Item (3) requires some insight into how graphs and other
> data structures are represented in TinkerPop4, and this is where the
> interaction between the basic data model and the VM comes in. In terms of
> what I called the APG data model, there are three basic changes of state:
>
> 1) add an element of a given type. E.g. the edge with label knows and id 42
> didn't exist before, and now it does.
> 2) remove an element of a given type. E.g. the edge with label knows and id
> 42 existed before, but now it doesn't.
> 3) mutate an existing element of a given type. E.g. the element with label
> knows and id 42 used to have Person vertex 1 as its out-element and Person
> vertex 4 as its in-element, but now it has Person vertex 6 as its
> in-element.
>
> In other words, we support *create*, *update*, and *delete* operations for
> typed elements. *Read* operations do not require appending to the
> transaction log. Now, given that we have mutated the graph in our
> transaction, but the graph on disk has not changed, how do we deliver a
> consistent view of the mutated graph to subsequent read operations in the
> same transaction? If we think of the graph as a set of relations (tables,
> indexes), then we just need to wrap each read operation, from each table,
> in such a way that the read operation respects the transaction log.
>
> For example, if we have a relation like V() that represents all vertices in
> the graph, and we have added a vertex, then the iterator for V() should be
> the raw V() iterator for the unmodified graph -- filtered to exclude all
> *delete* elements in the transaction log which are vertices -- concatenated
> with a filtered iterator over all *create* elements which are vertices.
> Once you have committed your transaction, the transaction log is empty, so
> these wrapped iterators provide exactly the same elements as the raw
> iterators.
>
> How do you build a transaction log within a traversal? With a state monad
> <https://en.wikipedia.org/wiki/Monad_(functional_programming)#State_monads
> >.
> A state monad will allow you to execute any basic VM instruction and carry
> the transaction log along with the computation. Most instructions are a
> no-op with respect to state, but those few instructions which do affect
> state must append to the transaction log. For example, a V() operation
> doesn't just give you an iterator over vertices; it gives you a pair of
> objects: the iterator over vertices, and also the transaction log . A
> create-vertex operation also gives you a pair of objects: the newly-created
> vertex, and also the state, in which we have appended a *create* element to
> the transaction log.
>
> In terms of language support, Java 8+ supports some things
> <https://dzone.com/articles/whats-wrong-java-8-part-iv> that happen to be
> monads, where the flatMap method is equivalent to the monadic bind
> operator. Of course, you can also implement your own monads in Java. Scala
> does not have a built-in monad concept or syntactic sugar either, although
> it does have better support for higher-kinded types in general. In any
> case, we only really need to implement one monad for the sake of
> transactions: call it State or Transaction. In plain old Java, this would
> look something like the following (ignoring applicative functors, which are
> awkward in Java):
>
> public class TransactionLog {
>     private Iterable<Element> created;
>     private Iterable<Element> updated;
>     private Iterable<Element> deleted;
>
>     public TransactionLog append(TransactionLog other) {
>         ...
>     }
> }
>
> public class State<A> {
>     private TransactionLog log;
>     private A object;
>
>     public State(A object, TransactionLog log) {
>         this.object = object;
>         this.log = log;
>     }
>
>     public TransactionLog getLog() {
>         return log;
>     }
>
>     public A getObject() {
>         return object;
>     }
>
>     public <B> State<B> map(Function<A, B> mapper) {
>         return new State(mapper.apply(object), log);
>     }
>
>     public <B> State<B> flatMap(Function<A, State<B>> mapper) {
>         State<B> other = mapper.apply(object);
>         return new State(other.object, log.append(other.log));
>     }
> }
>
>
> Btw. a type-friendly definition of Element would look something like this:
>
>
> public abstract class Type {
>     public String name;
> }
>
> public class PrimitiveType extends Type {
>     public Class valueClass;
> }
>
> public class TupleType extends Type {
>     public List<Field> fields;
> }
>
> public class UnionType extends Type {
>     public List<Field> alternatives;
> }
>
> public class Field {
>     public String name;
>     public Type type;
> }
>
> public class Element {
>     public String id;
>     public Type type;
>     public Value value;
> }
>
> public abstract class Value {
> }
>
> public class PrimitiveValue<V> extends Value {
>     public V value;
> }
>
> public class TupleValue extends Value {
>     public List<Value> values;
> }
>
> public class UnionValue extends Value {
>     public String fieldName;
>     public Value value;
> }
>
>
>
> Josh
>
>
>
>
>
> On Mon, May 13, 2019 at 5:08 PM Marko Rodriguez <ok...@gmail.com>
> wrote:
>
> > Hello Josh (others),
> >
> > You mentioned a week or so ago that the n-tuple model should be able to
> > capture both indices and transactions.
> >
> > At the time, I scoffed at the notion. However, as you know, I have been
> > recently enlightened to how n-tuples can model indices and am using it
> > extensively in the spec. What I would like to contemplate now is how you
> > figure transactions being modeled?
> >
> > Thanks,
> > Marko.
> >
> > http://rredux.com <http://rredux.com/>
> >
> >
> >
> >
> >
>

Re: N-Tuple Transactions?

Posted by Joshua Shinavier <jo...@fortytwo.net>.
Hi Marko,

Get ready for monads
<https://en.wikipedia.org/wiki/Monad_(functional_programming)>. I mentioned
them in my post
<https://groups.google.com/d/msg/gremlin-users/MPNdNOAnYbs/sbowvioiDgAJ> on
algebraic property graphs. In functional programming, monads are a typical
way of composing chains of stateful operations together in such that they
do not violate functional purity. For example, an operation which adds a
vertex to a graph can be thought of as a function f : Graph -> Graph that
takes a graph as its input, adds a vertex, and returns the resulting graph
as its output. The function f doesn't actually mutate the graph on disk,
but it gives you an in-memory representation of the mutated graph, which
can then be persisted to disk. Some things you need in order to make this
work:

1) a snapshot of the state of the graph / database as it existed when the
transaction was started
2) a transaction log, within the TinkerPop VM, containing all atomic
changes that were made to the graph since the transaction was started
3) a view of the graph overlaid with the contents of the transaction log
4) the ability to persist the transaction log to the database

Items (1) and (4) are pretty trivial if the underlying database itself
supports transactions. Item (2) is easy if we use a basic state monad. More
on that below. Item (3) requires some insight into how graphs and other
data structures are represented in TinkerPop4, and this is where the
interaction between the basic data model and the VM comes in. In terms of
what I called the APG data model, there are three basic changes of state:

1) add an element of a given type. E.g. the edge with label knows and id 42
didn't exist before, and now it does.
2) remove an element of a given type. E.g. the edge with label knows and id
42 existed before, but now it doesn't.
3) mutate an existing element of a given type. E.g. the element with label
knows and id 42 used to have Person vertex 1 as its out-element and Person
vertex 4 as its in-element, but now it has Person vertex 6 as its
in-element.

In other words, we support *create*, *update*, and *delete* operations for
typed elements. *Read* operations do not require appending to the
transaction log. Now, given that we have mutated the graph in our
transaction, but the graph on disk has not changed, how do we deliver a
consistent view of the mutated graph to subsequent read operations in the
same transaction? If we think of the graph as a set of relations (tables,
indexes), then we just need to wrap each read operation, from each table,
in such a way that the read operation respects the transaction log.

For example, if we have a relation like V() that represents all vertices in
the graph, and we have added a vertex, then the iterator for V() should be
the raw V() iterator for the unmodified graph -- filtered to exclude all
*delete* elements in the transaction log which are vertices -- concatenated
with a filtered iterator over all *create* elements which are vertices.
Once you have committed your transaction, the transaction log is empty, so
these wrapped iterators provide exactly the same elements as the raw
iterators.

How do you build a transaction log within a traversal? With a state monad
<https://en.wikipedia.org/wiki/Monad_(functional_programming)#State_monads>.
A state monad will allow you to execute any basic VM instruction and carry
the transaction log along with the computation. Most instructions are a
no-op with respect to state, but those few instructions which do affect
state must append to the transaction log. For example, a V() operation
doesn't just give you an iterator over vertices; it gives you a pair of
objects: the iterator over vertices, and also the transaction log . A
create-vertex operation also gives you a pair of objects: the newly-created
vertex, and also the state, in which we have appended a *create* element to
the transaction log.

In terms of language support, Java 8+ supports some things
<https://dzone.com/articles/whats-wrong-java-8-part-iv> that happen to be
monads, where the flatMap method is equivalent to the monadic bind
operator. Of course, you can also implement your own monads in Java. Scala
does not have a built-in monad concept or syntactic sugar either, although
it does have better support for higher-kinded types in general. In any
case, we only really need to implement one monad for the sake of
transactions: call it State or Transaction. In plain old Java, this would
look something like the following (ignoring applicative functors, which are
awkward in Java):

public class TransactionLog {
    private Iterable<Element> created;
    private Iterable<Element> updated;
    private Iterable<Element> deleted;

    public TransactionLog append(TransactionLog other) {
        ...
    }
}

public class State<A> {
    private TransactionLog log;
    private A object;

    public State(A object, TransactionLog log) {
        this.object = object;
        this.log = log;
    }

    public TransactionLog getLog() {
        return log;
    }

    public A getObject() {
        return object;
    }

    public <B> State<B> map(Function<A, B> mapper) {
        return new State(mapper.apply(object), log);
    }

    public <B> State<B> flatMap(Function<A, State<B>> mapper) {
        State<B> other = mapper.apply(object);
        return new State(other.object, log.append(other.log));
    }
}


Btw. a type-friendly definition of Element would look something like this:


public abstract class Type {
    public String name;
}

public class PrimitiveType extends Type {
    public Class valueClass;
}

public class TupleType extends Type {
    public List<Field> fields;
}

public class UnionType extends Type {
    public List<Field> alternatives;
}

public class Field {
    public String name;
    public Type type;
}

public class Element {
    public String id;
    public Type type;
    public Value value;
}

public abstract class Value {
}

public class PrimitiveValue<V> extends Value {
    public V value;
}

public class TupleValue extends Value {
    public List<Value> values;
}

public class UnionValue extends Value {
    public String fieldName;
    public Value value;
}



Josh





On Mon, May 13, 2019 at 5:08 PM Marko Rodriguez <ok...@gmail.com>
wrote:

> Hello Josh (others),
>
> You mentioned a week or so ago that the n-tuple model should be able to
> capture both indices and transactions.
>
> At the time, I scoffed at the notion. However, as you know, I have been
> recently enlightened to how n-tuples can model indices and am using it
> extensively in the spec. What I would like to contemplate now is how you
> figure transactions being modeled?
>
> Thanks,
> Marko.
>
> http://rredux.com <http://rredux.com/>
>
>
>
>
>