Sharded implementation of DOMDataTreeService 99/15199/13
authorRobert Varga <rovarga@cisco.com>
Thu, 12 Feb 2015 14:09:54 +0000 (15:09 +0100)
committerTony Tkacik <ttkacik@cisco.com>
Tue, 24 Feb 2015 08:29:07 +0000 (08:29 +0000)
This patch adds a simplistic implementation of a DOMDataTreeService and
a DOMDataTreeShardingService.

Change-Id: Ibb76c99d0fa842b1034a2b747c4ec57816f99c7d
Signed-off-by: Robert Varga <rovarga@cisco.com>
opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardRegistration.java [new file with mode: 0644]
opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardedDOMDataTree.java [new file with mode: 0644]
opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardedDOMDataTreeProducer.java [new file with mode: 0644]
opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardedDOMDataWriteTransaction.java [new file with mode: 0644]
opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardingTableEntry.java [new file with mode: 0644]

diff --git a/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardRegistration.java b/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardRegistration.java
new file mode 100644 (file)
index 0000000..9a71089
--- /dev/null
@@ -0,0 +1,33 @@
+/*
+ * Copyright (c) 2015 Cisco Systems, Inc. and others.  All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.controller.md.sal.dom.broker.impl;
+
+import com.google.common.base.Preconditions;
+import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeIdentifier;
+import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeShard;
+import org.opendaylight.yangtools.concepts.AbstractListenerRegistration;
+
+final class ShardRegistration<T extends DOMDataTreeShard> extends AbstractListenerRegistration<T> {
+    private final DOMDataTreeIdentifier prefix;
+    private final ShardedDOMDataTree tree;
+
+    protected ShardRegistration(final ShardedDOMDataTree tree, final DOMDataTreeIdentifier prefix, final T shard) {
+        super(shard);
+        this.tree = Preconditions.checkNotNull(tree);
+        this.prefix = Preconditions.checkNotNull(prefix);
+    }
+
+    DOMDataTreeIdentifier getPrefix() {
+        return prefix;
+    }
+
+    @Override
+    protected void removeRegistration() {
+        tree.removeShard(this);
+    }
+}
diff --git a/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardedDOMDataTree.java b/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardedDOMDataTree.java
new file mode 100644 (file)
index 0000000..11eae5d
--- /dev/null
@@ -0,0 +1,181 @@
+/*
+ * Copyright (c) 2015 Cisco Systems, Inc. and others.  All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.controller.md.sal.dom.broker.impl;
+
+import com.google.common.base.Preconditions;
+import java.util.Collection;
+import java.util.EnumMap;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.TreeMap;
+import javax.annotation.concurrent.GuardedBy;
+import org.opendaylight.controller.md.sal.common.api.data.LogicalDatastoreType;
+import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeIdentifier;
+import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeListener;
+import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeProducer;
+import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeService;
+import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeShard;
+import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeShardingConflictException;
+import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeShardingService;
+import org.opendaylight.yangtools.concepts.ListenerRegistration;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+public final class ShardedDOMDataTree implements DOMDataTreeService, DOMDataTreeShardingService {
+    private static final Logger LOG = LoggerFactory.getLogger(ShardedDOMDataTree.class);
+    private final Map<LogicalDatastoreType, ShardingTableEntry> shardingTables = new EnumMap<>(LogicalDatastoreType.class);
+    @GuardedBy("this")
+    private final Map<DOMDataTreeIdentifier, DOMDataTreeProducer> idToProducer = new TreeMap<>();
+
+    @GuardedBy("this")
+    private ShardingTableEntry lookupShard(final DOMDataTreeIdentifier prefix) {
+        final ShardingTableEntry t = shardingTables.get(prefix.getDatastoreType());
+        if (t == null) {
+            return null;
+        }
+
+        return t.lookup(prefix.getRootIdentifier());
+    }
+
+    @GuardedBy("this")
+    private void storeShard(final DOMDataTreeIdentifier prefix, final ShardRegistration<?> reg) {
+        ShardingTableEntry t = shardingTables.get(prefix.getDatastoreType());
+        if (t == null) {
+            t = new ShardingTableEntry();
+            shardingTables.put(prefix.getDatastoreType(), t);
+        }
+
+        t.store(prefix.getRootIdentifier(), reg);
+    }
+
+    void removeShard(final ShardRegistration<?> reg) {
+        final DOMDataTreeIdentifier prefix = reg.getPrefix();
+        final ShardRegistration<?> parentReg;
+
+        synchronized (this) {
+            final ShardingTableEntry t = shardingTables.get(prefix.getDatastoreType());
+            if (t == null) {
+                LOG.warn("Shard registration {} points to non-existent table", reg);
+                return;
+            }
+
+            t.remove(prefix.getRootIdentifier());
+            parentReg = lookupShard(prefix).getRegistration();
+
+            /*
+             * FIXME: adjust all producers. This is tricky, as we need different locking strategy,
+             *        simply because we risk AB/BA deadlock with a producer being split off from
+             *        a producer.
+             *
+             */
+        }
+
+        if (parentReg != null) {
+            parentReg.getInstance().onChildDetached(prefix, reg.getInstance());
+        }
+    }
+
+    @Override
+    public <T extends DOMDataTreeShard> ListenerRegistration<T> registerDataTreeShard(final DOMDataTreeIdentifier prefix, final T shard) throws DOMDataTreeShardingConflictException {
+        final ShardRegistration<T> reg;
+        final ShardRegistration<?> parentReg;
+
+        synchronized (this) {
+            /*
+             * Lookup the parent shard (e.g. the one which currently matches the prefix),
+             * and if it exists, check if its registration prefix does not collide with
+             * this registration.
+             */
+            final ShardingTableEntry parent = lookupShard(prefix);
+            parentReg = parent.getRegistration();
+            if (parentReg != null && prefix.equals(parentReg.getPrefix())) {
+                throw new DOMDataTreeShardingConflictException(String.format("Prefix %s is already occupied by shard {}", prefix, parentReg.getInstance()));
+            }
+
+            // FIXME: wrap the shard in a proper adaptor based on implemented interface
+
+            reg = new ShardRegistration<T>(this, prefix, shard);
+
+            storeShard(prefix, reg);
+
+            // FIXME: update any producers/registrations
+        }
+
+        // Notify the parent shard
+        if (parentReg != null) {
+            parentReg.getInstance().onChildAttached(prefix, shard);
+        }
+
+        return reg;
+    }
+
+    @GuardedBy("this")
+    private DOMDataTreeProducer findProducer(final DOMDataTreeIdentifier subtree) {
+        for (Entry<DOMDataTreeIdentifier, DOMDataTreeProducer> e : idToProducer.entrySet()) {
+            if (e.getKey().contains(subtree)) {
+                return e.getValue();
+            }
+        }
+
+        return null;
+    }
+
+    synchronized void destroyProducer(final ShardedDOMDataTreeProducer producer) {
+        for (DOMDataTreeIdentifier s : producer.getSubtrees()) {
+            DOMDataTreeProducer r = idToProducer.remove(s);
+            if (!producer.equals(r)) {
+                LOG.error("Removed producer %s on subtree %s while removing %s", r, s, producer);
+            }
+        }
+    }
+
+    @GuardedBy("this")
+    private DOMDataTreeProducer createProducer(final Map<DOMDataTreeIdentifier, DOMDataTreeShard> shardMap) {
+        // Record the producer's attachment points
+        final DOMDataTreeProducer ret = ShardedDOMDataTreeProducer.create(this, shardMap);
+        for (DOMDataTreeIdentifier s : shardMap.keySet()) {
+            idToProducer.put(s, ret);
+        }
+
+        return ret;
+    }
+
+    @Override
+    public synchronized DOMDataTreeProducer createProducer(final Collection<DOMDataTreeIdentifier> subtrees) {
+        Preconditions.checkArgument(!subtrees.isEmpty(), "Subtrees may not be empty");
+
+        final Map<DOMDataTreeIdentifier, DOMDataTreeShard> shardMap = new HashMap<>();
+        for (DOMDataTreeIdentifier s : subtrees) {
+            // Attempting to create a disconnected producer -- all subtrees have to be unclaimed
+            final DOMDataTreeProducer producer = findProducer(s);
+            Preconditions.checkArgument(producer == null, "Subtree %s is attached to producer %s", s, producer);
+
+            shardMap.put(s, lookupShard(s).getRegistration().getInstance());
+        }
+
+        return createProducer(shardMap);
+    }
+
+    synchronized DOMDataTreeProducer createProducer(final ShardedDOMDataTreeProducer parent, final Collection<DOMDataTreeIdentifier> subtrees) {
+        Preconditions.checkNotNull(parent);
+
+        final Map<DOMDataTreeIdentifier, DOMDataTreeShard> shardMap = new HashMap<>();
+        for (DOMDataTreeIdentifier s : subtrees) {
+            shardMap.put(s, lookupShard(s).getRegistration().getInstance());
+        }
+
+        return createProducer(shardMap);
+    }
+
+    @Override
+    public synchronized <T extends DOMDataTreeListener> ListenerRegistration<T> registerListener(final T listener, final Collection<DOMDataTreeIdentifier> subtrees, final boolean allowRxMerges, final Collection<DOMDataTreeProducer> producers) {
+        // TODO Auto-generated method stub
+        return null;
+    }
+}
diff --git a/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardedDOMDataTreeProducer.java b/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardedDOMDataTreeProducer.java
new file mode 100644 (file)
index 0000000..9712b25
--- /dev/null
@@ -0,0 +1,210 @@
+/*
+ * Copyright (c) 2015 Cisco Systems, Inc. and others.  All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.controller.md.sal.dom.broker.impl;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.BiMap;
+import com.google.common.collect.ImmutableBiMap;
+import com.google.common.collect.ImmutableBiMap.Builder;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.LinkedList;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Queue;
+import java.util.Set;
+import javax.annotation.concurrent.GuardedBy;
+import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeIdentifier;
+import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeProducer;
+import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeProducerBusyException;
+import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeProducerException;
+import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeShard;
+import org.opendaylight.controller.md.sal.dom.api.DOMDataWriteTransaction;
+import org.opendaylight.controller.sal.core.spi.data.DOMStore;
+import org.opendaylight.controller.sal.core.spi.data.DOMStoreTransactionChain;
+import org.opendaylight.controller.sal.core.spi.data.DOMStoreWriteTransaction;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+final class ShardedDOMDataTreeProducer implements DOMDataTreeProducer {
+    private static final Logger LOG = LoggerFactory.getLogger(ShardedDOMDataTreeProducer.class);
+    private final BiMap<DOMDataTreeShard, DOMStoreTransactionChain> shardToChain;
+    private final Map<DOMDataTreeIdentifier, DOMDataTreeShard> idToShard;
+    private final ShardedDOMDataTree dataTree;
+
+    @GuardedBy("this")
+    private Map<DOMDataTreeIdentifier, DOMDataTreeProducer> children = Collections.emptyMap();
+    @GuardedBy("this")
+    private DOMDataWriteTransaction openTx;
+    @GuardedBy("this")
+    private boolean closed;
+
+    ShardedDOMDataTreeProducer(final ShardedDOMDataTree dataTree, final Map<DOMDataTreeIdentifier, DOMDataTreeShard> shardMap, final Set<DOMDataTreeShard> shards) {
+        this.dataTree = Preconditions.checkNotNull(dataTree);
+
+        // Create shard -> chain map
+        final Builder<DOMDataTreeShard, DOMStoreTransactionChain> cb = ImmutableBiMap.builder();
+        final Queue<Exception> es = new LinkedList<>();
+
+        for (DOMDataTreeShard s : shards) {
+            if (s instanceof DOMStore) {
+                try {
+                    final DOMStoreTransactionChain c = ((DOMStore)s).createTransactionChain();
+                    LOG.trace("Using DOMStore chain {} to access shard {}", c, s);
+                    cb.put(s, c);
+                } catch (Exception e) {
+                    LOG.error("Failed to instantiate chain for shard {}", s, e);
+                    es.add(e);
+                }
+            } else {
+                LOG.error("Unhandled shard instance type {}", s.getClass());
+            }
+        }
+        this.shardToChain = cb.build();
+
+        // An error was encountered, close chains and report the error
+        if (shardToChain.size() != shards.size()) {
+            for (DOMStoreTransactionChain c : shardToChain.values()) {
+                try {
+                    c.close();
+                } catch (Exception e) {
+                    LOG.warn("Exception raised while closing chain %s", c, e);
+                }
+            }
+
+            final IllegalStateException e = new IllegalStateException("Failed to completely allocate contexts", es.poll());
+            while (!es.isEmpty()) {
+                e.addSuppressed(es.poll());
+            }
+
+            throw e;
+        }
+
+        idToShard = ImmutableMap.copyOf(shardMap);
+    }
+
+    @Override
+    public synchronized DOMDataWriteTransaction createTransaction(final boolean isolated) {
+        Preconditions.checkState(!closed, "Producer is already closed");
+        Preconditions.checkState(openTx == null, "Transaction %s is still open", openTx);
+
+        // Allocate backing transactions
+        final Map<DOMDataTreeShard, DOMStoreWriteTransaction> shardToTx = new HashMap<>();
+        for (Entry<DOMDataTreeShard, DOMStoreTransactionChain> e : shardToChain.entrySet()) {
+            shardToTx.put(e.getKey(), e.getValue().newWriteOnlyTransaction());
+        }
+
+        // Create the ID->transaction map
+        final ImmutableMap.Builder<DOMDataTreeIdentifier, DOMStoreWriteTransaction> b = ImmutableMap.builder();
+        for (Entry<DOMDataTreeIdentifier, DOMDataTreeShard> e : idToShard.entrySet()) {
+            b.put(e.getKey(), shardToTx.get(e.getValue()));
+        }
+
+        final ShardedDOMDataWriteTransaction ret = new ShardedDOMDataWriteTransaction(this, b.build());
+        openTx = ret;
+        return ret;
+    }
+
+    @GuardedBy("this")
+    private boolean haveSubtree(final DOMDataTreeIdentifier subtree) {
+        for (DOMDataTreeIdentifier i : idToShard.keySet()) {
+            if (i.contains(subtree)) {
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+    @GuardedBy("this")
+    private DOMDataTreeProducer lookupChild(final DOMDataTreeIdentifier s) {
+        for (Entry<DOMDataTreeIdentifier, DOMDataTreeProducer> e : children.entrySet()) {
+            if (e.getKey().contains(s)) {
+                return e.getValue();
+            }
+        }
+
+        return null;
+    }
+
+    @Override
+    public synchronized DOMDataTreeProducer createProducer(final Collection<DOMDataTreeIdentifier> subtrees) {
+        Preconditions.checkState(!closed, "Producer is already closed");
+        Preconditions.checkState(openTx == null, "Transaction %s is still open", openTx);
+
+        for (DOMDataTreeIdentifier s : subtrees) {
+            // Check if the subtree was visible at any time
+            if (!haveSubtree(s)) {
+                throw new IllegalArgumentException(String.format("Subtree %s was never available in producer %s", s, this));
+            }
+
+            // Check if the subtree has not been delegated to a child
+            final DOMDataTreeProducer child = lookupChild(s);
+            Preconditions.checkArgument(child == null, "Subtree %s is delegated to child producer %s", s, child);
+
+            // Check if part of the requested subtree is not delegated to a child.
+            for (DOMDataTreeIdentifier c : children.keySet()) {
+                if (s.contains(c)) {
+                    throw new IllegalArgumentException(String.format("Subtree %s cannot be delegated as it is superset of already-delegated %s", s, c));
+                }
+            }
+        }
+
+        final DOMDataTreeProducer ret = dataTree.createProducer(this, subtrees);
+        final ImmutableMap.Builder<DOMDataTreeIdentifier, DOMDataTreeProducer> cb = ImmutableMap.builder();
+        cb.putAll(children);
+        for (DOMDataTreeIdentifier s : subtrees) {
+            cb.put(s, ret);
+        }
+
+        children = cb.build();
+        return ret;
+    }
+
+    @Override
+    public synchronized void close() throws DOMDataTreeProducerException {
+        if (!closed) {
+            if (openTx != null) {
+                throw new DOMDataTreeProducerBusyException(String.format("Transaction %s is still open", openTx));
+            }
+
+            closed = true;
+            dataTree.destroyProducer(this);
+        }
+    }
+
+    static DOMDataTreeProducer create(final ShardedDOMDataTree dataTree, final Map<DOMDataTreeIdentifier, DOMDataTreeShard> shardMap) {
+        /*
+         * FIXME: we do not allow multiple multiple shards in a producer because we do not implement the
+         *        synchronization primitives yet
+         */
+        final Set<DOMDataTreeShard> shards = ImmutableSet.copyOf(shardMap.values());
+        if (shards.size() > 1) {
+            throw new UnsupportedOperationException("Cross-shard producers are not supported yet");
+        }
+
+        return new ShardedDOMDataTreeProducer(dataTree, shardMap, shards);
+    }
+
+    Set<DOMDataTreeIdentifier> getSubtrees() {
+        return idToShard.keySet();
+    }
+
+    synchronized void cancelTransaction(final ShardedDOMDataWriteTransaction transaction) {
+        if (!openTx.equals(transaction)) {
+            LOG.warn("Transaction {} is not open in producer {}", transaction, this);
+            return;
+        }
+
+        LOG.debug("Transaction {} cancelled", transaction);
+        openTx = null;
+    }
+}
diff --git a/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardedDOMDataWriteTransaction.java b/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardedDOMDataWriteTransaction.java
new file mode 100644 (file)
index 0000000..33f15e3
--- /dev/null
@@ -0,0 +1,125 @@
+/*
+ * Copyright (c) 2015 Cisco Systems, Inc. and others.  All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.controller.md.sal.dom.broker.impl;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.util.concurrent.CheckedFuture;
+import com.google.common.util.concurrent.Futures;
+import com.google.common.util.concurrent.ListenableFuture;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
+import java.util.concurrent.atomic.AtomicLong;
+import javax.annotation.concurrent.GuardedBy;
+import javax.annotation.concurrent.NotThreadSafe;
+import org.opendaylight.controller.md.sal.common.api.TransactionStatus;
+import org.opendaylight.controller.md.sal.common.api.data.LogicalDatastoreType;
+import org.opendaylight.controller.md.sal.common.api.data.TransactionCommitFailedException;
+import org.opendaylight.controller.md.sal.common.impl.service.AbstractDataTransaction;
+import org.opendaylight.controller.md.sal.dom.api.DOMDataTreeIdentifier;
+import org.opendaylight.controller.md.sal.dom.api.DOMDataWriteTransaction;
+import org.opendaylight.controller.sal.core.spi.data.DOMStoreThreePhaseCommitCohort;
+import org.opendaylight.controller.sal.core.spi.data.DOMStoreWriteTransaction;
+import org.opendaylight.yangtools.yang.common.RpcResult;
+import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier;
+import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+@NotThreadSafe
+final class ShardedDOMDataWriteTransaction implements DOMDataWriteTransaction {
+    private static final Logger LOG = LoggerFactory.getLogger(ShardedDOMDataWriteTransaction.class);
+    private static final AtomicLong COUNTER = new AtomicLong();
+    private final Map<DOMDataTreeIdentifier, DOMStoreWriteTransaction> idToTransaction;
+    private final ShardedDOMDataTreeProducer producer;
+    private final String identifier;
+    @GuardedBy("this")
+    private boolean closed =  false;
+
+    ShardedDOMDataWriteTransaction(final ShardedDOMDataTreeProducer producer, final Map<DOMDataTreeIdentifier, DOMStoreWriteTransaction> idToTransaction) {
+        this.producer = Preconditions.checkNotNull(producer);
+        this.idToTransaction = Preconditions.checkNotNull(idToTransaction);
+        this.identifier = "SHARDED-DOM-" + COUNTER.getAndIncrement();
+    }
+
+    // FIXME: use atomic operations
+    @GuardedBy("this")
+    private DOMStoreWriteTransaction lookup(final LogicalDatastoreType store, final YangInstanceIdentifier path) {
+        final DOMDataTreeIdentifier id = new DOMDataTreeIdentifier(store, path);
+
+        for (Entry<DOMDataTreeIdentifier, DOMStoreWriteTransaction> e : idToTransaction.entrySet()) {
+            if (e.getKey().contains(id)) {
+                return e.getValue();
+            }
+        }
+
+        throw new IllegalArgumentException(String.format("Path %s is not acessible from transaction %s", id, this));
+    }
+
+    @Override
+    public String getIdentifier() {
+        return identifier;
+    }
+
+    @Override
+    public synchronized boolean cancel() {
+        if (closed) {
+            return false;
+        }
+
+        LOG.debug("Cancelling transaction {}", identifier);
+        for (DOMStoreWriteTransaction tx : ImmutableSet.copyOf(idToTransaction.values())) {
+            tx.close();
+        }
+
+        closed = true;
+        producer.cancelTransaction(this);
+        return true;
+    }
+
+    @Override
+    public synchronized CheckedFuture<Void, TransactionCommitFailedException> submit() {
+        Preconditions.checkState(!closed, "Transaction %s is already closed", identifier);
+
+        final Set<DOMStoreWriteTransaction> txns = ImmutableSet.copyOf(idToTransaction.values());
+        final List<DOMStoreThreePhaseCommitCohort> cohorts = new ArrayList<>(txns.size());
+        for (DOMStoreWriteTransaction tx : txns) {
+            cohorts.add(tx.ready());
+        }
+
+        try {
+            return Futures.immediateCheckedFuture(new CommitCoordinationTask(this, cohorts, null).call());
+        } catch (TransactionCommitFailedException e) {
+            return Futures.immediateFailedCheckedFuture(e);
+        }
+    }
+
+    @Override
+    @Deprecated
+    public ListenableFuture<RpcResult<TransactionStatus>> commit() {
+        return AbstractDataTransaction.convertToLegacyCommitFuture(submit());
+    }
+
+    @Override
+    public synchronized void delete(final LogicalDatastoreType store, final YangInstanceIdentifier path) {
+        lookup(store, path).delete(path);
+    }
+
+    @Override
+    public synchronized void put(final LogicalDatastoreType store, final YangInstanceIdentifier path, final NormalizedNode<?, ?> data) {
+        lookup(store, path).write(path, data);
+    }
+
+    @Override
+    public synchronized void merge(final LogicalDatastoreType store, final YangInstanceIdentifier path, final NormalizedNode<?, ?> data) {
+        lookup(store, path).merge(path, data);
+    }
+}
diff --git a/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardingTableEntry.java b/opendaylight/md-sal/sal-dom-broker/src/main/java/org/opendaylight/controller/md/sal/dom/broker/impl/ShardingTableEntry.java
new file mode 100644 (file)
index 0000000..fcd0ebd
--- /dev/null
@@ -0,0 +1,97 @@
+/*
+ * Copyright (c) 2015 Cisco Systems, Inc. and others.  All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.controller.md.sal.dom.broker.impl;
+
+import com.google.common.base.Preconditions;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.Map;
+import org.opendaylight.yangtools.concepts.Identifiable;
+import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier;
+import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+final class ShardingTableEntry implements Identifiable<PathArgument> {
+    private static final Logger LOG = LoggerFactory.getLogger(ShardingTableEntry.class);
+    private final Map<PathArgument, ShardingTableEntry> children = Collections.emptyMap();
+    private final PathArgument identifier;
+    private ShardRegistration<?> registration;
+
+    ShardingTableEntry() {
+        identifier = null;
+    }
+
+    ShardingTableEntry(final PathArgument identifier) {
+        this.identifier = Preconditions.checkNotNull(identifier);
+    }
+
+    @Override
+    public PathArgument getIdentifier() {
+        return identifier;
+    }
+
+    public ShardRegistration<?> getRegistration() {
+        return registration;
+    }
+
+    ShardingTableEntry lookup(final YangInstanceIdentifier id) {
+        final Iterator<PathArgument> it = id.getPathArguments().iterator();
+        ShardingTableEntry entry = this;
+
+        while (it.hasNext()) {
+            final PathArgument a = it.next();
+            final ShardingTableEntry child = entry.children.get(a);
+            if (child == null) {
+                LOG.debug("Lookup of {} stopped at {}", id, a);
+                break;
+            }
+
+            entry = child;
+        }
+
+        return entry;
+    }
+
+    void store(final YangInstanceIdentifier id, final ShardRegistration<?> reg) {
+        final Iterator<PathArgument> it = id.getPathArguments().iterator();
+        ShardingTableEntry entry = this;
+
+        while (it.hasNext()) {
+            final PathArgument a = it.next();
+            ShardingTableEntry child = entry.children.get(a);
+            if (child == null) {
+                child = new ShardingTableEntry(a);
+                entry.children.put(a, child);
+            }
+        }
+
+        Preconditions.checkState(entry.registration == null);
+        entry.registration = reg;
+    }
+
+    private boolean remove(final Iterator<PathArgument> it) {
+        if (it.hasNext()) {
+            final PathArgument arg = it.next();
+            final ShardingTableEntry child = children.get(arg);
+            if (child != null) {
+                if (child.remove(it)) {
+                    children.remove(arg);
+                }
+            } else {
+                LOG.warn("Cannot remove non-existent child {}", arg);
+            }
+        }
+
+        return registration == null && children.isEmpty();
+    }
+
+    void remove(final YangInstanceIdentifier id) {
+        this.remove(id.getPathArguments().iterator());
+    }
+}