From: Robert Varga Date: Sat, 6 Nov 2021 10:18:54 +0000 (+0100) Subject: Use UnsignedLongSet instead of RangeSet in metadata X-Git-Tag: v4.0.6~4 X-Git-Url: https://git.opendaylight.org/gerrit/gitweb?p=controller.git;a=commitdiff_plain;h=e9efe27538adb5ae575f77fda90f147d46341801 Use UnsignedLongSet instead of RangeSet in metadata Split UnsignedLongSet into two implementations, mutable and immutable. Use the mutable implementation in runtime tracking of identifiers and use the immutable implementation for tracking identifiers in metadata. The serialization format is kept compatible with RangeSets, although that implies a minor penalty in serdes. This switch ends up potentially using more objects for small sets, but that is offset by not having Cut indirections and most notably being resistent to allocation of huge arrays. JIRA: CONTROLLER-2011 Change-Id: I0c84ffaaa4ce39299cef9006784b8aff78dd0f83 Signed-off-by: Robert Varga --- diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/AbstractFrontendHistory.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/AbstractFrontendHistory.java index e437b07c64..b102e8c45b 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/AbstractFrontendHistory.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/AbstractFrontendHistory.java @@ -32,7 +32,7 @@ import org.opendaylight.controller.cluster.access.concepts.LocalHistoryIdentifie import org.opendaylight.controller.cluster.access.concepts.RequestEnvelope; import org.opendaylight.controller.cluster.access.concepts.RequestException; import org.opendaylight.controller.cluster.access.concepts.TransactionIdentifier; -import org.opendaylight.controller.cluster.datastore.utils.UnsignedLongSet; +import org.opendaylight.controller.cluster.datastore.utils.MutableUnsignedLongSet; import org.opendaylight.yangtools.concepts.Identifiable; import org.opendaylight.yangtools.yang.data.api.schema.tree.DataTreeModification; import org.slf4j.Logger; @@ -48,7 +48,7 @@ abstract class AbstractFrontendHistory implements Identifiable transactions = new HashMap<>(); - private final UnsignedLongSet purgedTransactions; + private final MutableUnsignedLongSet purgedTransactions; private final String persistenceId; private final ShardDataTree tree; @@ -59,7 +59,7 @@ abstract class AbstractFrontendHistory implements Identifiable closedTransactions; AbstractFrontendHistory(final String persistenceId, final ShardDataTree tree, - final Map closedTransactions, final UnsignedLongSet purgedTransactions) { + final Map closedTransactions, final MutableUnsignedLongSet purgedTransactions) { this.persistenceId = requireNonNull(persistenceId); this.tree = requireNonNull(tree); this.closedTransactions = requireNonNull(closedTransactions); diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/FrontendClientMetadataBuilder.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/FrontendClientMetadataBuilder.java index d4befae83e..acb585e080 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/FrontendClientMetadataBuilder.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/FrontendClientMetadataBuilder.java @@ -14,10 +14,6 @@ import com.google.common.base.MoreObjects; import com.google.common.base.MoreObjects.ToStringHelper; import com.google.common.collect.Collections2; import com.google.common.collect.ImmutableList; -import com.google.common.collect.ImmutableRangeSet; -import com.google.common.collect.RangeSet; -import com.google.common.primitives.UnsignedLong; -import java.util.Collection; import java.util.HashMap; import java.util.Map; import org.eclipse.jdt.annotation.NonNull; @@ -26,7 +22,8 @@ import org.opendaylight.controller.cluster.access.concepts.LocalHistoryIdentifie import org.opendaylight.controller.cluster.access.concepts.TransactionIdentifier; import org.opendaylight.controller.cluster.datastore.persisted.FrontendClientMetadata; import org.opendaylight.controller.cluster.datastore.persisted.FrontendHistoryMetadata; -import org.opendaylight.controller.cluster.datastore.utils.UnsignedLongSet; +import org.opendaylight.controller.cluster.datastore.utils.ImmutableUnsignedLongSet; +import org.opendaylight.controller.cluster.datastore.utils.MutableUnsignedLongSet; import org.opendaylight.yangtools.concepts.Builder; import org.opendaylight.yangtools.concepts.Identifiable; import org.slf4j.Logger; @@ -44,7 +41,7 @@ abstract class FrontendClientMetadataBuilder implements Builder currentHistories = new HashMap<>(); + private final MutableUnsignedLongSet purgedHistories; private final LocalHistoryIdentifier standaloneId; - private final UnsignedLongSet purgedHistories; Enabled(final String shardName, final ClientIdentifier identifier) { super(shardName, identifier); - purgedHistories = UnsignedLongSet.of(); + purgedHistories = MutableUnsignedLongSet.of(); // History for stand-alone transactions is always present standaloneId = standaloneHistoryId(); @@ -101,7 +98,7 @@ abstract class FrontendClientMetadataBuilder implements Builder current = meta.getCurrentHistories(); - final RangeSet purged = meta.getPurgedHistories(); - // Completely empty histories imply disabled state, as otherwise we'd have a record of the single history -- // either purged or active - return current.isEmpty() && purged.isEmpty() ? new Disabled(shardName, meta.getIdentifier()) - : new Enabled(shardName, meta); + return meta.getCurrentHistories().isEmpty() && meta.getPurgedHistories().isEmpty() + ? new Disabled(shardName, meta.getIdentifier()) : new Enabled(shardName, meta); } @Override diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/FrontendHistoryMetadataBuilder.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/FrontendHistoryMetadataBuilder.java index 0dd3c48f6c..72bab449f4 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/FrontendHistoryMetadataBuilder.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/FrontendHistoryMetadataBuilder.java @@ -18,7 +18,7 @@ import org.opendaylight.controller.cluster.access.concepts.ClientIdentifier; import org.opendaylight.controller.cluster.access.concepts.LocalHistoryIdentifier; import org.opendaylight.controller.cluster.access.concepts.TransactionIdentifier; import org.opendaylight.controller.cluster.datastore.persisted.FrontendHistoryMetadata; -import org.opendaylight.controller.cluster.datastore.utils.UnsignedLongSet; +import org.opendaylight.controller.cluster.datastore.utils.MutableUnsignedLongSet; import org.opendaylight.yangtools.concepts.Builder; import org.opendaylight.yangtools.concepts.Identifiable; @@ -26,21 +26,21 @@ final class FrontendHistoryMetadataBuilder implements Builder { private final @NonNull Map closedTransactions; - private final @NonNull UnsignedLongSet purgedTransactions; + private final @NonNull MutableUnsignedLongSet purgedTransactions; private final @NonNull LocalHistoryIdentifier identifier; private boolean closed; FrontendHistoryMetadataBuilder(final LocalHistoryIdentifier identifier) { this.identifier = requireNonNull(identifier); - purgedTransactions = UnsignedLongSet.of(); + purgedTransactions = MutableUnsignedLongSet.of(); closedTransactions = new HashMap<>(2); } FrontendHistoryMetadataBuilder(final ClientIdentifier clientId, final FrontendHistoryMetadata meta) { identifier = new LocalHistoryIdentifier(clientId, meta.getHistoryId(), meta.getCookie()); closedTransactions = new HashMap<>(meta.getClosedTransactions()); - purgedTransactions = UnsignedLongSet.of(meta.getPurgedTransactions()); + purgedTransactions = meta.getPurgedTransactions().mutableCopy(); closed = meta.isClosed(); } @@ -52,7 +52,7 @@ final class FrontendHistoryMetadataBuilder implements Builder { // Histories which have not been purged private final Map localHistories; - // RangeSet performs automatic merging, hence we keep minimal state tracking information - private final UnsignedLongSet purgedHistories; + // UnsignedLongSet performs automatic merging, hence we keep minimal state tracking information + private final MutableUnsignedLongSet purgedHistories; // Used for all standalone transactions private final AbstractFrontendHistory standaloneHistory; @@ -75,12 +75,12 @@ abstract class LeaderFrontendState implements Identifiable { private Long lastSeenHistory = null; Enabled(final String persistenceId, final ClientIdentifier clientId, final ShardDataTree tree) { - this(persistenceId, clientId, tree, UnsignedLongSet.of(), + this(persistenceId, clientId, tree, MutableUnsignedLongSet.of(), StandaloneFrontendHistory.create(persistenceId, clientId, tree), new HashMap<>()); } Enabled(final String persistenceId, final ClientIdentifier clientId, final ShardDataTree tree, - final UnsignedLongSet purgedHistories, final AbstractFrontendHistory standaloneHistory, + final MutableUnsignedLongSet purgedHistories, final AbstractFrontendHistory standaloneHistory, final Map localHistories) { super(persistenceId, clientId, tree); this.purgedHistories = requireNonNull(purgedHistories); diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/LocalFrontendHistory.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/LocalFrontendHistory.java index 129ef3a5eb..3125ed651a 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/LocalFrontendHistory.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/LocalFrontendHistory.java @@ -17,7 +17,7 @@ import java.util.Optional; import java.util.SortedSet; import org.opendaylight.controller.cluster.access.concepts.LocalHistoryIdentifier; import org.opendaylight.controller.cluster.access.concepts.TransactionIdentifier; -import org.opendaylight.controller.cluster.datastore.utils.UnsignedLongSet; +import org.opendaylight.controller.cluster.datastore.utils.MutableUnsignedLongSet; import org.opendaylight.yangtools.yang.data.api.schema.tree.DataTreeModification; /** @@ -30,21 +30,21 @@ final class LocalFrontendHistory extends AbstractFrontendHistory { private LocalFrontendHistory(final String persistenceId, final ShardDataTree tree, final ShardDataTreeTransactionChain chain, final Map closedTransactions, - final UnsignedLongSet purgedTransactions) { + final MutableUnsignedLongSet purgedTransactions) { super(persistenceId, tree, closedTransactions, purgedTransactions); this.chain = requireNonNull(chain); } static LocalFrontendHistory create(final String persistenceId, final ShardDataTree tree, final ShardDataTreeTransactionChain chain) { - return new LocalFrontendHistory(persistenceId, tree, chain, ImmutableMap.of(), UnsignedLongSet.of()); + return new LocalFrontendHistory(persistenceId, tree, chain, ImmutableMap.of(), MutableUnsignedLongSet.of()); } static LocalFrontendHistory recreate(final String persistenceId, final ShardDataTree tree, final ShardDataTreeTransactionChain chain, final Map closedTransactions, - final UnsignedLongSet purgedTransactions) { + final MutableUnsignedLongSet purgedTransactions) { return new LocalFrontendHistory(persistenceId, tree, chain, new HashMap<>(closedTransactions), - purgedTransactions.copy()); + purgedTransactions.mutableCopy()); } @Override diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/StandaloneFrontendHistory.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/StandaloneFrontendHistory.java index be85f689eb..0278c1d1e5 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/StandaloneFrontendHistory.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/StandaloneFrontendHistory.java @@ -19,7 +19,7 @@ import org.eclipse.jdt.annotation.NonNull; import org.opendaylight.controller.cluster.access.concepts.ClientIdentifier; import org.opendaylight.controller.cluster.access.concepts.LocalHistoryIdentifier; import org.opendaylight.controller.cluster.access.concepts.TransactionIdentifier; -import org.opendaylight.controller.cluster.datastore.utils.UnsignedLongSet; +import org.opendaylight.controller.cluster.datastore.utils.MutableUnsignedLongSet; import org.opendaylight.yangtools.yang.data.api.schema.tree.DataTreeModification; /** @@ -29,12 +29,12 @@ import org.opendaylight.yangtools.yang.data.api.schema.tree.DataTreeModification * @author Robert Varga */ final class StandaloneFrontendHistory extends AbstractFrontendHistory { - private final LocalHistoryIdentifier identifier; - private final ShardDataTree tree; + private final @NonNull LocalHistoryIdentifier identifier; + private final @NonNull ShardDataTree tree; private StandaloneFrontendHistory(final String persistenceId, final ClientIdentifier clientId, final ShardDataTree tree, final Map closedTransactions, - final UnsignedLongSet purgedTransactions) { + final MutableUnsignedLongSet purgedTransactions) { super(persistenceId, tree, closedTransactions, purgedTransactions); identifier = new LocalHistoryIdentifier(clientId, 0); this.tree = requireNonNull(tree); @@ -42,14 +42,15 @@ final class StandaloneFrontendHistory extends AbstractFrontendHistory { static @NonNull StandaloneFrontendHistory create(final String persistenceId, final ClientIdentifier clientId, final ShardDataTree tree) { - return new StandaloneFrontendHistory(persistenceId, clientId, tree, ImmutableMap.of(), UnsignedLongSet.of()); + return new StandaloneFrontendHistory(persistenceId, clientId, tree, ImmutableMap.of(), + MutableUnsignedLongSet.of()); } static @NonNull StandaloneFrontendHistory recreate(final String persistenceId, final ClientIdentifier clientId, final ShardDataTree tree, final Map closedTransactions, - final UnsignedLongSet purgedTransactions) { + final MutableUnsignedLongSet purgedTransactions) { return new StandaloneFrontendHistory(persistenceId, clientId, tree, new HashMap<>(closedTransactions), - purgedTransactions.copy()); + purgedTransactions.mutableCopy()); } @Override diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendClientMetadata.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendClientMetadata.java index c1199699ec..f384c928a6 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendClientMetadata.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendClientMetadata.java @@ -11,32 +11,26 @@ import static java.util.Objects.requireNonNull; import com.google.common.base.MoreObjects; import com.google.common.collect.ImmutableList; -import com.google.common.collect.ImmutableRangeSet; -import com.google.common.collect.ImmutableRangeSet.Builder; -import com.google.common.collect.Range; -import com.google.common.collect.RangeSet; -import com.google.common.primitives.UnsignedLong; import java.io.DataInput; import java.io.DataOutput; import java.io.IOException; import java.util.ArrayList; import java.util.Collection; -import java.util.Set; import org.eclipse.jdt.annotation.NonNull; import org.opendaylight.controller.cluster.access.concepts.ClientIdentifier; +import org.opendaylight.controller.cluster.datastore.utils.ImmutableUnsignedLongSet; import org.opendaylight.yangtools.concepts.Identifiable; import org.opendaylight.yangtools.concepts.WritableObject; -import org.opendaylight.yangtools.concepts.WritableObjects; public final class FrontendClientMetadata implements Identifiable, WritableObject { private final @NonNull ImmutableList currentHistories; - private final @NonNull ImmutableRangeSet purgedHistories; + private final @NonNull ImmutableUnsignedLongSet purgedHistories; private final @NonNull ClientIdentifier identifier; - public FrontendClientMetadata(final ClientIdentifier identifier, final RangeSet purgedHistories, + public FrontendClientMetadata(final ClientIdentifier identifier, final ImmutableUnsignedLongSet purgedHistories, final Collection currentHistories) { this.identifier = requireNonNull(identifier); - this.purgedHistories = ImmutableRangeSet.copyOf(purgedHistories); + this.purgedHistories = requireNonNull(purgedHistories); this.currentHistories = ImmutableList.copyOf(currentHistories); } @@ -44,7 +38,7 @@ public final class FrontendClientMetadata implements Identifiable getPurgedHistories() { + public ImmutableUnsignedLongSet getPurgedHistories() { return purgedHistories; } @@ -56,12 +50,7 @@ public final class FrontendClientMetadata implements Identifiable> ranges = purgedHistories.asRanges(); - out.writeInt(ranges.size()); - for (final Range r : ranges) { - WritableObjects.writeLongs(out, r.lowerEndpoint().longValue(), r.upperEndpoint().longValue()); - } + purgedHistories.writeTo(out); out.writeInt(currentHistories.size()); for (final FrontendHistoryMetadata h : currentHistories) { @@ -71,24 +60,16 @@ public final class FrontendClientMetadata implements Identifiable b = ImmutableRangeSet.builder(); - for (int i = 0; i < purgedSize; ++i) { - final byte header = WritableObjects.readLongHeader(in); - final UnsignedLong lower = UnsignedLong.fromLongBits(WritableObjects.readFirstLong(in, header)); - final UnsignedLong upper = UnsignedLong.fromLongBits(WritableObjects.readSecondLong(in, header)); - - b.add(Range.closedOpen(lower, upper)); - } + final var purgedHistories = ImmutableUnsignedLongSet.readFrom(in); final int currentSize = in.readInt(); - final Collection currentHistories = new ArrayList<>(currentSize); + // FIXME: ImmutableList.builder() + final var currentHistories = new ArrayList(currentSize); for (int i = 0; i < currentSize; ++i) { currentHistories.add(FrontendHistoryMetadata.readFrom(in)); } - return new FrontendClientMetadata(id, b.build(), currentHistories); + return new FrontendClientMetadata(id, purgedHistories, currentHistories); } @Override diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendHistoryMetadata.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendHistoryMetadata.java index e9a076e5c7..7e27f86f45 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendHistoryMetadata.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendHistoryMetadata.java @@ -7,13 +7,11 @@ */ package org.opendaylight.controller.cluster.datastore.persisted; +import static java.util.Objects.requireNonNull; + import com.google.common.base.MoreObjects; import com.google.common.base.Verify; import com.google.common.collect.ImmutableMap; -import com.google.common.collect.ImmutableRangeSet; -import com.google.common.collect.Range; -import com.google.common.collect.RangeSet; -import com.google.common.collect.TreeRangeSet; import com.google.common.primitives.UnsignedLong; import java.io.DataInput; import java.io.DataOutput; @@ -21,25 +19,25 @@ import java.io.IOException; import java.util.HashMap; import java.util.Map; import java.util.Map.Entry; -import java.util.Set; import org.eclipse.jdt.annotation.NonNull; +import org.opendaylight.controller.cluster.datastore.utils.ImmutableUnsignedLongSet; import org.opendaylight.yangtools.concepts.WritableObject; import org.opendaylight.yangtools.concepts.WritableObjects; public final class FrontendHistoryMetadata implements WritableObject { - private final @NonNull ImmutableRangeSet purgedTransactions; + private final @NonNull ImmutableUnsignedLongSet purgedTransactions; private final @NonNull ImmutableMap closedTransactions; private final long historyId; private final long cookie; private final boolean closed; public FrontendHistoryMetadata(final long historyId, final long cookie, final boolean closed, - final Map closedTransactions, final RangeSet purgedTransactions) { + final Map closedTransactions, final ImmutableUnsignedLongSet purgedTransactions) { this.historyId = historyId; this.cookie = cookie; this.closed = closed; this.closedTransactions = ImmutableMap.copyOf(closedTransactions); - this.purgedTransactions = ImmutableRangeSet.copyOf(purgedTransactions); + this.purgedTransactions = requireNonNull(purgedTransactions); } public long getHistoryId() { @@ -54,11 +52,11 @@ public final class FrontendHistoryMetadata implements WritableObject { return closed; } - public Map getClosedTransactions() { + public ImmutableMap getClosedTransactions() { return closedTransactions; } - public RangeSet getPurgedTransactions() { + public ImmutableUnsignedLongSet getPurgedTransactions() { return purgedTransactions; } @@ -67,15 +65,13 @@ public final class FrontendHistoryMetadata implements WritableObject { WritableObjects.writeLongs(out, historyId, cookie); out.writeBoolean(closed); - final Set> purgedRanges = purgedTransactions.asRanges(); - WritableObjects.writeLongs(out, closedTransactions.size(), purgedRanges.size()); + final int purgedSize = purgedTransactions.size(); + WritableObjects.writeLongs(out, closedTransactions.size(), purgedSize); for (Entry e : closedTransactions.entrySet()) { WritableObjects.writeLong(out, e.getKey().longValue()); out.writeBoolean(e.getValue()); } - for (Range r : purgedRanges) { - WritableObjects.writeLongs(out, r.lowerEndpoint().longValue(), r.upperEndpoint().longValue()); - } + purgedTransactions.writeRangesTo(out, purgedSize); } public static FrontendHistoryMetadata readFrom(final DataInput in) throws IOException { @@ -99,13 +95,7 @@ public final class FrontendHistoryMetadata implements WritableObject { final Boolean value = in.readBoolean(); closedTransactions.put(key, value); } - final RangeSet purgedTransactions = TreeRangeSet.create(); - for (int i = 0; i < psize; ++i) { - final byte h = WritableObjects.readLongHeader(in); - final UnsignedLong l = UnsignedLong.fromLongBits(WritableObjects.readFirstLong(in, h)); - final UnsignedLong u = UnsignedLong.fromLongBits(WritableObjects.readSecondLong(in, h)); - purgedTransactions.add(Range.closedOpen(l, u)); - } + final var purgedTransactions = ImmutableUnsignedLongSet.readFrom(in, psize); return new FrontendHistoryMetadata(historyId, cookie, closed, closedTransactions, purgedTransactions); } diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/ImmutableUnsignedLongSet.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/ImmutableUnsignedLongSet.java new file mode 100644 index 0000000000..e6c900b0f8 --- /dev/null +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/ImmutableUnsignedLongSet.java @@ -0,0 +1,74 @@ +/* + * Copyright (c) 2021 PANTHEON.tech, s.r.o. 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.cluster.datastore.utils; + +import com.google.common.annotations.Beta; +import java.io.DataInput; +import java.io.DataOutput; +import java.io.IOException; +import java.util.TreeSet; +import org.eclipse.jdt.annotation.NonNull; +import org.opendaylight.yangtools.concepts.Immutable; +import org.opendaylight.yangtools.concepts.WritableObject; + +@Beta +public final class ImmutableUnsignedLongSet extends UnsignedLongSet implements Immutable, WritableObject { + private static final @NonNull ImmutableUnsignedLongSet EMPTY = new ImmutableUnsignedLongSet(new TreeSet<>()); + + private ImmutableUnsignedLongSet(final TreeSet ranges) { + super(ranges); + } + + static @NonNull ImmutableUnsignedLongSet of(final TreeSet ranges) { + return ranges.isEmpty() ? EMPTY : new ImmutableUnsignedLongSet(ranges); + } + + public static @NonNull ImmutableUnsignedLongSet of() { + return EMPTY; + } + + @Override + public ImmutableUnsignedLongSet immutableCopy() { + return this; + } + + public static @NonNull ImmutableUnsignedLongSet readFrom(final DataInput in) throws IOException { + return readFrom(in, in.readInt()); + } + + public static @NonNull ImmutableUnsignedLongSet readFrom(final DataInput in, final int size) throws IOException { + if (size == 0) { + return EMPTY; + } + + final var ranges = new TreeSet(); + for (int i = 0; i < size; ++i) { + ranges.add(Entry.readUnsigned(in)); + } + return new ImmutableUnsignedLongSet(ranges); + } + + @Override + public void writeTo(final DataOutput out) throws IOException { + out.writeInt(size()); + writeRanges(out); + } + + public void writeRangesTo(final @NonNull DataOutput out, final int size) throws IOException { + if (size != size()) { + throw new IOException("Mismatched size: expected " + size() + ", got " + size); + } + writeRanges(out); + } + + private void writeRanges(final @NonNull DataOutput out) throws IOException { + for (var range : trustedRanges()) { + range.writeUnsigned(out); + } + } +} diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/MutableUnsignedLongSet.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/MutableUnsignedLongSet.java new file mode 100644 index 0000000000..e8e479c798 --- /dev/null +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/MutableUnsignedLongSet.java @@ -0,0 +1,40 @@ +/* + * Copyright (c) 2021 PANTHEON.tech, s.r.o. 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.cluster.datastore.utils; + +import com.google.common.annotations.Beta; +import com.google.common.collect.Collections2; +import com.google.common.collect.ImmutableRangeSet; +import com.google.common.primitives.UnsignedLong; +import java.util.TreeSet; +import org.eclipse.jdt.annotation.NonNull; +import org.opendaylight.yangtools.concepts.Mutable; + +@Beta +public final class MutableUnsignedLongSet extends UnsignedLongSet implements Mutable { + MutableUnsignedLongSet(final TreeSet ranges) { + super(ranges); + } + + public static @NonNull MutableUnsignedLongSet of() { + return new MutableUnsignedLongSet(new TreeSet<>()); + } + + @Override + public ImmutableUnsignedLongSet immutableCopy() { + return ImmutableUnsignedLongSet.of(copyRanges()); + } + + public void add(final long longBits) { + addImpl(longBits); + } + + public ImmutableRangeSet toRangeSet() { + return ImmutableRangeSet.copyOf(Collections2.transform(trustedRanges(), Entry::toUnsigned)); + } +} diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSet.java b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSet.java index ac599a6624..4d4b99bbc9 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSet.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSet.java @@ -11,17 +11,23 @@ import static com.google.common.base.Verify.verify; import static java.util.Objects.requireNonNull; import com.google.common.annotations.Beta; +import com.google.common.annotations.VisibleForTesting; import com.google.common.base.MoreObjects; import com.google.common.collect.BoundType; import com.google.common.collect.Collections2; -import com.google.common.collect.ImmutableRangeSet; import com.google.common.collect.Range; import com.google.common.collect.RangeSet; import com.google.common.primitives.UnsignedLong; +import java.io.DataInput; +import java.io.DataOutput; +import java.io.IOException; +import java.util.Collections; import java.util.Iterator; +import java.util.NavigableSet; import java.util.TreeSet; import org.eclipse.jdt.annotation.NonNull; import org.opendaylight.yangtools.concepts.Mutable; +import org.opendaylight.yangtools.concepts.WritableObjects; /** * A class holding an equivalent of {@code Set}. It is geared towards efficiently tracking ranges of @@ -33,9 +39,10 @@ import org.opendaylight.yangtools.concepts.Mutable; * * @author Robert Varga */ -@Beta -public final class UnsignedLongSet implements Mutable { - private static final class Entry implements Comparable, Mutable { +abstract class UnsignedLongSet { + @Beta + @VisibleForTesting + public static final class Entry implements Comparable, Mutable { // Note: mutable to allow efficient merges. long lowerBits; long upperBits; @@ -59,6 +66,16 @@ public final class UnsignedLongSet implements Mutable { return of(range.lowerEndpoint().longValue(), range.upperEndpoint().longValue() - 1); } + @VisibleForTesting + public UnsignedLong lower() { + return UnsignedLong.fromLongBits(lowerBits); + } + + @VisibleForTesting + public UnsignedLong upper() { + return UnsignedLong.fromLongBits(upperBits); + } + boolean contains(final long longBits) { return Long.compareUnsigned(lowerBits, longBits) <= 0 && Long.compareUnsigned(upperBits, longBits) >= 0; } @@ -72,6 +89,24 @@ public final class UnsignedLongSet implements Mutable { return Range.closedOpen(UnsignedLong.fromLongBits(lowerBits), UnsignedLong.fromLongBits(upperBits + 1)); } + // These two methods provide the same serialization format as the one we've used to serialize + // Range + static @NonNull Entry readUnsigned(final DataInput in) throws IOException { + final byte hdr = WritableObjects.readLongHeader(in); + final long first = WritableObjects.readFirstLong(in, hdr); + final long second = WritableObjects.readSecondLong(in, hdr) - 1; + if (Long.compareUnsigned(first, second) > 0) { + throw new IOException("Lower endpoint " + Long.toUnsignedString(first) + " is greater than upper " + + "endpoint " + Long.toUnsignedString(second)); + } + + return new Entry(first, second); + } + + void writeUnsigned(final @NonNull DataOutput out) throws IOException { + WritableObjects.writeLongs(out, lowerBits, upperBits + 1); + } + @Override @SuppressWarnings("checkstyle:parameterName") public int compareTo(final Entry o) { @@ -105,28 +140,13 @@ public final class UnsignedLongSet implements Mutable { // for a contains() operation we just need the first headSet() entry. For insert operations we just update either // the lower bound or the upper bound of an existing entry. When we do, we also look at prev/next entry and if they // are contiguous with the updated entry, we adjust the entry once more and remove the prev/next entry. - private final TreeSet ranges; + private final @NonNull TreeSet ranges; - private UnsignedLongSet(final TreeSet ranges) { + UnsignedLongSet(final TreeSet ranges) { this.ranges = requireNonNull(ranges); } - private UnsignedLongSet(final RangeSet rangeSet) { - ranges = new TreeSet<>(); - for (var range : rangeSet.asRanges()) { - ranges.add(Entry.of(range)); - } - } - - public static @NonNull UnsignedLongSet of() { - return new UnsignedLongSet(new TreeSet<>()); - } - - public static @NonNull UnsignedLongSet of(final RangeSet rangeSet) { - return new UnsignedLongSet(rangeSet); - } - - public void add(final long longBits) { + final void addImpl(final long longBits) { final var range = Entry.of(longBits); final var headIt = headIter(range); @@ -161,31 +181,49 @@ public final class UnsignedLongSet implements Mutable { ranges.add(range); } - public boolean contains(final long longBits) { + public final boolean contains(final long longBits) { final var headIt = headIter(Entry.of(longBits)); return headIt.hasNext() && headIt.next().contains(longBits); } - public UnsignedLongSet copy() { - return new UnsignedLongSet(new TreeSet<>(Collections2.transform(ranges, Entry::copy))); + public final boolean isEmpty() { + return ranges.isEmpty(); + } + + public final int size() { + return ranges.size(); + } + + public abstract @NonNull ImmutableUnsignedLongSet immutableCopy(); + + public final @NonNull MutableUnsignedLongSet mutableCopy() { + return new MutableUnsignedLongSet(copyRanges()); + } + + final @NonNull TreeSet copyRanges() { + return new TreeSet<>(Collections2.transform(ranges, Entry::copy)); + } + + public final @NonNull NavigableSet ranges() { + return Collections.unmodifiableNavigableSet(ranges); } - public ImmutableRangeSet toRangeSet() { - return ImmutableRangeSet.copyOf(Collections2.transform(ranges, Entry::toUnsigned)); + final @NonNull NavigableSet trustedRanges() { + return ranges; } @Override - public int hashCode() { + public final int hashCode() { return ranges.hashCode(); } @Override - public boolean equals(final Object obj) { + public final boolean equals(final Object obj) { return obj == this || obj instanceof UnsignedLongSet && ranges.equals(((UnsignedLongSet) obj).ranges); } @Override - public String toString() { + public final String toString() { final var helper = MoreObjects.toStringHelper(this); final int size = ranges.size(); diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/AbstractDistributedDataStoreIntegrationTest.java b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/AbstractDistributedDataStoreIntegrationTest.java index f7fbb051da..cedd4ace0d 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/AbstractDistributedDataStoreIntegrationTest.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/AbstractDistributedDataStoreIntegrationTest.java @@ -22,8 +22,6 @@ import akka.actor.ActorRef; import akka.actor.ActorSystem; import com.google.common.base.Throwables; import com.google.common.collect.ImmutableMap; -import com.google.common.collect.Range; -import com.google.common.primitives.UnsignedLong; import com.google.common.util.concurrent.FluentFuture; import com.google.common.util.concurrent.ListenableFuture; import com.google.common.util.concurrent.MoreExecutors; @@ -35,7 +33,6 @@ import java.util.Collections; import java.util.Iterator; import java.util.List; import java.util.Optional; -import java.util.Set; import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutionException; import java.util.concurrent.TimeUnit; @@ -296,9 +293,7 @@ public abstract class AbstractDistributedDataStoreIntegrationTest { while (iterator.hasNext() && metadata.getHistoryId() != 1) { metadata = iterator.next(); } - Set> ranges = metadata.getPurgedTransactions().asRanges(); - - assertEquals(1, ranges.size()); + assertEquals(1, metadata.getPurgedTransactions().size()); } else { // ask based should track no metadata assertTrue(frontendMetadata.getClients().get(0).getCurrentHistories().isEmpty()); diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/DistributedDataStoreRemotingIntegrationTest.java b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/DistributedDataStoreRemotingIntegrationTest.java index c01949c930..da219faaf1 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/DistributedDataStoreRemotingIntegrationTest.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/DistributedDataStoreRemotingIntegrationTest.java @@ -32,7 +32,6 @@ import akka.testkit.javadsl.TestKit; import com.google.common.base.Stopwatch; import com.google.common.base.Throwables; import com.google.common.collect.ImmutableMap; -import com.google.common.collect.Range; import com.google.common.primitives.UnsignedLong; import com.google.common.util.concurrent.ListenableFuture; import com.google.common.util.concurrent.MoreExecutors; @@ -45,7 +44,6 @@ import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Optional; -import java.util.Set; import java.util.concurrent.ExecutionException; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; @@ -402,8 +400,12 @@ public class DistributedDataStoreRemotingIntegrationTest extends AbstractTest { } assertEquals(0, metadata.getClosedTransactions().size()); - assertEquals(Range.closedOpen(UnsignedLong.valueOf(0), UnsignedLong.valueOf(11)), - metadata.getPurgedTransactions().asRanges().iterator().next()); + + final var purgedRanges = metadata.getPurgedTransactions().ranges(); + assertEquals(1, purgedRanges.size()); + final var purgedRange = purgedRanges.first(); + assertEquals(UnsignedLong.ZERO, purgedRange.lower()); + assertEquals(UnsignedLong.valueOf(10), purgedRange.upper()); } else { // ask based should track no metadata assertTrue(frontendMetadata.getClients().get(0).getCurrentHistories().isEmpty()); @@ -466,10 +468,8 @@ public class DistributedDataStoreRemotingIntegrationTest extends AbstractTest { metadata = iterator.next(); } - Set> ranges = metadata.getPurgedTransactions().asRanges(); - assertEquals(0, metadata.getClosedTransactions().size()); - assertEquals(1, ranges.size()); + assertEquals(1, metadata.getPurgedTransactions().size()); } else { // ask based should track no metadata assertTrue(frontendMetadata.getClients().get(0).getCurrentHistories().isEmpty()); diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendShardDataTreeSnapshotMetadataTest.java b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendShardDataTreeSnapshotMetadataTest.java index 25b5128dba..dc7e1c8ca2 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendShardDataTreeSnapshotMetadataTest.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendShardDataTreeSnapshotMetadataTest.java @@ -14,9 +14,6 @@ import static org.junit.Assert.assertThrows; import static org.junit.Assert.assertTrue; import com.google.common.collect.ImmutableMap; -import com.google.common.collect.Range; -import com.google.common.collect.RangeSet; -import com.google.common.collect.TreeRangeSet; import com.google.common.primitives.UnsignedLong; import java.io.ByteArrayInputStream; import java.io.ByteArrayOutputStream; @@ -33,6 +30,8 @@ import org.opendaylight.controller.cluster.access.concepts.ClientIdentifier; import org.opendaylight.controller.cluster.access.concepts.FrontendIdentifier; import org.opendaylight.controller.cluster.access.concepts.FrontendType; import org.opendaylight.controller.cluster.access.concepts.MemberName; +import org.opendaylight.controller.cluster.datastore.utils.ImmutableUnsignedLongSet; +import org.opendaylight.controller.cluster.datastore.utils.MutableUnsignedLongSet; public class FrontendShardDataTreeSnapshotMetadataTest { @@ -105,14 +104,15 @@ public class FrontendShardDataTreeSnapshotMetadataTest { FrontendType.forName(index)); final ClientIdentifier clientIdentifier = ClientIdentifier.create(frontendIdentifier, num); - final RangeSet purgedHistories = TreeRangeSet.create(); - purgedHistories.add(Range.closedOpen(UnsignedLong.ZERO, UnsignedLong.ONE)); + final MutableUnsignedLongSet tmp = MutableUnsignedLongSet.of(); + tmp.add(0); + final ImmutableUnsignedLongSet purgedHistories = tmp.immutableCopy(); final Set currentHistories = Set.of( new FrontendHistoryMetadata(num, num, true, ImmutableMap.of(UnsignedLong.ZERO, Boolean.TRUE), purgedHistories)); - return new FrontendClientMetadata(clientIdentifier, purgedHistories, currentHistories); + return new FrontendClientMetadata(clientIdentifier, purgedHistories.immutableCopy(), currentHistories); } private static void testObject(final T object, final T equalObject) { diff --git a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSetTest.java b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSetTest.java index 7742cf3b75..1a67547722 100644 --- a/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSetTest.java +++ b/opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSetTest.java @@ -7,40 +7,43 @@ */ package org.opendaylight.controller.cluster.datastore.utils; +import static org.junit.Assert.assertArrayEquals; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertTrue; -import com.google.common.collect.ImmutableRangeSet; -import com.google.common.collect.Range; -import com.google.common.primitives.UnsignedLong; +import java.io.ByteArrayInputStream; +import java.io.ByteArrayOutputStream; +import java.io.DataInputStream; +import java.io.DataOutputStream; +import java.io.IOException; import org.junit.Test; public class UnsignedLongSetTest { @Test public void testOperations() { - final var set = UnsignedLongSet.of(); - assertEquals("UnsignedLongSet{size=0}", set.toString()); + final var set = MutableUnsignedLongSet.of(); + assertEquals("MutableUnsignedLongSet{size=0}", set.toString()); assertFalse(set.contains(0)); set.add(0); assertTrue(set.contains(0)); - assertEquals("UnsignedLongSet{span=[0..0], size=1}", set.toString()); + assertEquals("MutableUnsignedLongSet{span=[0..0], size=1}", set.toString()); set.add(1); assertTrue(set.contains(1)); - assertEquals("UnsignedLongSet{span=[0..1], size=1}", set.toString()); + assertEquals("MutableUnsignedLongSet{span=[0..1], size=1}", set.toString()); set.add(1); - assertEquals("UnsignedLongSet{span=[0..1], size=1}", set.toString()); + assertEquals("MutableUnsignedLongSet{span=[0..1], size=1}", set.toString()); set.add(4); - assertEquals("UnsignedLongSet{span=[0..4], size=2}", set.toString()); + assertEquals("MutableUnsignedLongSet{span=[0..4], size=2}", set.toString()); set.add(3); - assertEquals("UnsignedLongSet{span=[0..4], size=2}", set.toString()); + assertEquals("MutableUnsignedLongSet{span=[0..4], size=2}", set.toString()); set.add(2); - assertEquals("UnsignedLongSet{span=[0..4], size=1}", set.toString()); + assertEquals("MutableUnsignedLongSet{span=[0..4], size=1}", set.toString()); assertTrue(set.contains(2)); assertTrue(set.contains(3)); @@ -48,18 +51,35 @@ public class UnsignedLongSetTest { } @Test - public void testOfRangeSet() { - final var rangeSet = ImmutableRangeSet.builder() - .add(Range.closedOpen(UnsignedLong.valueOf(0), UnsignedLong.valueOf(2))) - .add(Range.closedOpen(UnsignedLong.valueOf(3), UnsignedLong.valueOf(5))) - .build(); - assertEquals("[[0..2), [3..5)]", rangeSet.toString()); - assertEquals("UnsignedLongSet{span=[0..4], size=2}", UnsignedLongSet.of(rangeSet).toString()); + public void testSerialization() throws IOException { + final var tmp = MutableUnsignedLongSet.of(); + tmp.add(0); + tmp.add(1); + tmp.add(4); + tmp.add(3); + + final var set = tmp.immutableCopy(); + + final var bos = new ByteArrayOutputStream(); + try (var out = new DataOutputStream(bos)) { + set.writeTo(out); + } + + final var bytes = bos.toByteArray(); + assertArrayEquals(new byte[] { 0, 0, 0, 2, 16, 2, 17, 3, 5 }, bytes); + + final ImmutableUnsignedLongSet read; + try (var in = new DataInputStream(new ByteArrayInputStream(bytes))) { + read = ImmutableUnsignedLongSet.readFrom(in); + assertEquals(0, in.available()); + } + + assertEquals(set, read); } @Test public void testToRangeSet() { - final var set = UnsignedLongSet.of(); + final var set = MutableUnsignedLongSet.of(); set.add(0); set.add(1); set.add(4);