Repository: tinkerpop Updated Branches: refs/heads/TINKERPOP-1564 [created] 0b07e6d47
first push on the query routing protocol for Gremlin 'OLTP'/'OLAP'. This push contains the Partition concept where a Graph has a PhysicalPartitions that can be broken up into as many LogicalPartitions as desired. These logical partitions will then serve as the subgraph that a Worker will be responsible for processing traversers at. This is all determined at the TraversalSource via graph.traversal().withPartitioner(...). Basically, how do you want your PROCESS partitioned in reference to your STRUCTURE partition. Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/0b07e6d4 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/0b07e6d4 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/0b07e6d4 Branch: refs/heads/TINKERPOP-1564 Commit: 0b07e6d47feb74a28d077005255ad3c8cce21ce3 Parents: 16180e1 Author: Marko A. Rodriguez <[email protected]> Authored: Thu Nov 24 05:57:03 2016 -0700 Committer: Marko A. Rodriguez <[email protected]> Committed: Thu Nov 24 05:57:03 2016 -0700 ---------------------------------------------------------------------- .../process/traversal/TraversalSource.java | 10 +++ .../dsl/graph/GraphTraversalSource.java | 6 ++ .../tinkerpop/gremlin/structure/Graph.java | 13 +++ .../tinkerpop/gremlin/structure/Partition.java | 73 +++++++++++++++ .../gremlin/structure/Partitioner.java | 33 +++++++ .../structure/util/GlobalPartitioner.java | 83 +++++++++++++++++ .../gremlin/structure/util/HashPartitioner.java | 95 ++++++++++++++++++++ .../groovy/jsr223/GroovyTranslatorTest.java | 2 - 8 files changed, 313 insertions(+), 2 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0b07e6d4/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalSource.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalSource.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalSource.java index df1d89a..02ccfcf 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalSource.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalSource.java @@ -26,7 +26,9 @@ import org.apache.tinkerpop.gremlin.process.computer.traversal.strategy.decorati import org.apache.tinkerpop.gremlin.process.remote.RemoteConnection; import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.SackStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.SideEffectStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.PartitionerStrategy; import org.apache.tinkerpop.gremlin.structure.Graph; +import org.apache.tinkerpop.gremlin.structure.Partitioner; import org.apache.tinkerpop.gremlin.util.function.ConstantSupplier; import java.io.Serializable; @@ -91,6 +93,7 @@ public interface TraversalSource extends Cloneable, AutoCloseable { public static final String withComputer = "withComputer"; public static final String withSideEffect = "withSideEffect"; public static final String withRemote = "withRemote"; + public static final String withPartitioner = "withPartitioner"; } ///////////////////////////// @@ -127,6 +130,13 @@ public interface TraversalSource extends Cloneable, AutoCloseable { return clone; } + public default TraversalSource withPartitioner(final Partitioner partitioner) { + final TraversalSource clone = this.clone(); + clone.getStrategies().addStrategies(new PartitionerStrategy(partitioner)); + clone.getBytecode().addSource(Symbols.withPartitioner, partitioner); + return clone; + } + /** * Using the provided {@link Bindings} to create {@link org.apache.tinkerpop.gremlin.process.traversal.Bytecode.Binding}. * The bindings serve as a relay for ensure bound arguments are encoded as {@link org.apache.tinkerpop.gremlin.process.traversal.Bytecode.Binding} in {@link Bytecode}. http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0b07e6d4/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversalSource.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversalSource.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversalSource.java index 362c571..33c9cae 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversalSource.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversalSource.java @@ -38,6 +38,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.Requir import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement; import org.apache.tinkerpop.gremlin.structure.Edge; import org.apache.tinkerpop.gremlin.structure.Graph; +import org.apache.tinkerpop.gremlin.structure.Partitioner; import org.apache.tinkerpop.gremlin.structure.T; import org.apache.tinkerpop.gremlin.structure.Transaction; import org.apache.tinkerpop.gremlin.structure.Vertex; @@ -134,6 +135,11 @@ public class GraphTraversalSource implements TraversalSource { } @Override + public GraphTraversalSource withPartitioner(final Partitioner partitioner) { + return (GraphTraversalSource) TraversalSource.super.withPartitioner(partitioner); + } + + @Override public GraphTraversalSource withBindings(final Bindings bindings) { return (GraphTraversalSource) TraversalSource.super.withBindings(bindings); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0b07e6d4/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/Graph.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/Graph.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/Graph.java index 2db37d3..0bdb7dc 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/Graph.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/Graph.java @@ -28,6 +28,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.engine.ComputerTraversalEn import org.apache.tinkerpop.gremlin.structure.io.Io; import org.apache.tinkerpop.gremlin.structure.io.IoRegistry; import org.apache.tinkerpop.gremlin.structure.util.FeatureDescriptor; +import org.apache.tinkerpop.gremlin.structure.util.GlobalPartitioner; import org.apache.tinkerpop.gremlin.structure.util.GraphFactory; import org.apache.tinkerpop.gremlin.structure.util.Host; import org.javatuples.Pair; @@ -285,6 +286,18 @@ public interface Graph extends AutoCloseable, Host { public Iterator<Edge> edges(final Object... edgeIds); /** + * Get the physical {@link Partitioner}s associated with the graph. + * For distributed graph systems, this {@link Partitioner} typically maintains the physical subgraph partitions. + * For single-machine graph systems, this {@link Partitioner} typically maintains a single partition. + * The default implementation returns a {@link GlobalPartitioner} which has a single partition. + * + * @return the {@link Partitioner} denoting the physical partition of the graph. + */ + public default Partitioner partitioner() { + return new GlobalPartitioner(this); + } + + /** * Configure and control the transactions for those graphs that support this feature. Note that this method does * not indicate the creation of a "transaction" object. A {@link Transaction} in the TinkerPop context is a * transaction "factory" or "controller" that helps manage transactions owned by the underlying graph database. http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0b07e6d4/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/Partition.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/Partition.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/Partition.java new file mode 100644 index 0000000..1864fd0 --- /dev/null +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/Partition.java @@ -0,0 +1,73 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +package org.apache.tinkerpop.gremlin.structure; + +import java.net.URI; +import java.util.Iterator; + +/** + * A {@code Partition} represents a physical or logical split of the underlying {@link Graph} structure. + * In distributed graph systems, a physical partition denotes which vertices/edges are in the subgraph of the underyling + * physical machine. In a logical partition, a physical partition may be split amongst multiple threads and thus, + * while isolated logically, they are united physically. + * + * @author Marko A. Rodriguez (http://markorodriguez.com) + */ +public interface Partition { + + /** + * Whether or not this element was, is, or will be contained in this partition. + * Containment is not whether the element currently exists, but instead whether if it did exist, would it be + * contained in this partition. + * + * @param element the element to check for containment + * @return whether the element would be contained in this partition + */ + public boolean contains(final Element element); + + /** + * The current existing vertices contained in this partition. + * + * @param ids filtering to only those ids provided + * @return an iterator of vertices contained in the partition + */ + public Iterator<Vertex> vertices(final Object... ids); + + /** + * The current existing edges contained in this partition. + * + * @param ids filtering to only those ids provided + * @return an iterator of edges contained in the partition + */ + public Iterator<Edge> edges(final Object... ids); + + /** + * Get the {@link URI} location of the partition. + * + * @return the location of the partition + */ + public URI location(); + + public static interface PhysicalPartition extends Partition { + } + + public static interface LogicalPartition extends Partition { + } +} http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0b07e6d4/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/Partitioner.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/Partitioner.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/Partitioner.java new file mode 100644 index 0000000..1d4aae1 --- /dev/null +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/Partitioner.java @@ -0,0 +1,33 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +package org.apache.tinkerpop.gremlin.structure; + +import java.util.List; + +/** + * @author Marko A. Rodriguez (http://markorodriguez.com) + */ +public interface Partitioner { + + public List<Partition> getPartitions(); + + public Partition getPartition(final Element element); + +} http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0b07e6d4/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/GlobalPartitioner.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/GlobalPartitioner.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/GlobalPartitioner.java new file mode 100644 index 0000000..d78a084 --- /dev/null +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/GlobalPartitioner.java @@ -0,0 +1,83 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +package org.apache.tinkerpop.gremlin.structure.util; + +import org.apache.tinkerpop.gremlin.structure.Edge; +import org.apache.tinkerpop.gremlin.structure.Element; +import org.apache.tinkerpop.gremlin.structure.Graph; +import org.apache.tinkerpop.gremlin.structure.Partition; +import org.apache.tinkerpop.gremlin.structure.Partitioner; +import org.apache.tinkerpop.gremlin.structure.Vertex; + +import java.net.URI; +import java.util.Collections; +import java.util.Iterator; +import java.util.List; + +/** + * @author Marko A. Rodriguez (http://markorodriguez.com) + */ +public final class GlobalPartitioner implements Partitioner { + + private final GlobalPartition partition; + + public GlobalPartitioner(final Graph graph) { + this.partition = new GlobalPartition(graph); + } + + @Override + public List<Partition> getPartitions() { + return Collections.singletonList(this.partition); + } + + @Override + public Partition getPartition(final Element element) { + return this.partition; + } + + private class GlobalPartition implements Partition { + + private final Graph graph; + + private GlobalPartition(final Graph graph) { + this.graph = graph; + } + + @Override + public boolean contains(final Element element) { + return true; + } + + @Override + public Iterator<Vertex> vertices(final Object... ids) { + return this.graph.vertices(ids); + } + + @Override + public Iterator<Edge> edges(final Object... ids) { + return this.graph.edges(ids); + } + + @Override + public URI location() { + return URI.create("localhost"); + } + } +} http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0b07e6d4/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/HashPartitioner.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/HashPartitioner.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/HashPartitioner.java new file mode 100644 index 0000000..e6e6593 --- /dev/null +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/HashPartitioner.java @@ -0,0 +1,95 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +package org.apache.tinkerpop.gremlin.structure.util; + +import org.apache.tinkerpop.gremlin.structure.Edge; +import org.apache.tinkerpop.gremlin.structure.Element; +import org.apache.tinkerpop.gremlin.structure.Partition; +import org.apache.tinkerpop.gremlin.structure.Partitioner; +import org.apache.tinkerpop.gremlin.structure.Vertex; +import org.apache.tinkerpop.gremlin.util.iterator.IteratorUtils; + +import java.net.URI; +import java.util.ArrayList; +import java.util.Iterator; +import java.util.List; + +/** + * @author Marko A. Rodriguez (http://markorodriguez.com) + */ +public final class HashPartitioner implements Partitioner { + + private final List<Partition> partitions = new ArrayList<>(); + + public HashPartitioner(final Partitioner basePartitioner, final int splits) { + for (final Partition partition : basePartitioner.getPartitions()) { + for (int i = 0; i < splits; i++) { + this.partitions.add(new HashPartition(partition, i, splits)); + } + } + } + + @Override + public List<Partition> getPartitions() { + return this.partitions; + } + + @Override + public Partition getPartition(final Element element) { + for (final Partition partition : this.partitions) { + if (partition.contains(element)) + return partition; + } + throw new IllegalArgumentException("The provided element is not in any known partition: " + element); + } + + private static final class HashPartition implements Partition { + + private final Partition basePartition; + private final int totalSplits; + private final int splitId; + + private HashPartition(final Partition basePartition, final int splitId, final int totalSplits) { + this.basePartition = basePartition; + this.totalSplits = totalSplits; + this.splitId = splitId; + } + + @Override + public boolean contains(final Element element) { + return (this.splitId == element.hashCode() % this.totalSplits) && this.basePartition.contains(element); + } + + @Override + public Iterator<Vertex> vertices(final Object... ids) { + return IteratorUtils.filter(this.basePartition.vertices(ids), vertex -> this.splitId == vertex.hashCode() % this.totalSplits); + } + + @Override + public Iterator<Edge> edges(final Object... ids) { + return IteratorUtils.filter(this.basePartition.edges(ids), edge -> this.splitId == edge.hashCode() % this.totalSplits); + } + + @Override + public URI location() { + return this.basePartition.location(); + } + } +} http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/0b07e6d4/gremlin-groovy-test/src/main/java/org/apache/tinkerpop/gremlin/groovy/jsr223/GroovyTranslatorTest.java ---------------------------------------------------------------------- diff --git a/gremlin-groovy-test/src/main/java/org/apache/tinkerpop/gremlin/groovy/jsr223/GroovyTranslatorTest.java b/gremlin-groovy-test/src/main/java/org/apache/tinkerpop/gremlin/groovy/jsr223/GroovyTranslatorTest.java index 59903ac..826f0e0 100644 --- a/gremlin-groovy-test/src/main/java/org/apache/tinkerpop/gremlin/groovy/jsr223/GroovyTranslatorTest.java +++ b/gremlin-groovy-test/src/main/java/org/apache/tinkerpop/gremlin/groovy/jsr223/GroovyTranslatorTest.java @@ -27,7 +27,6 @@ import org.apache.tinkerpop.gremlin.process.traversal.Traverser; import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversal; import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversalSource; import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__; -import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.PartitionStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.SubgraphStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.TranslationStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.verification.ReadOnlyStrategy; @@ -38,7 +37,6 @@ import org.junit.Test; import javax.script.Bindings; import javax.script.SimpleBindings; import java.util.ArrayList; -import java.util.Collections; import java.util.HashMap; import java.util.List;
