Use UnsignedLongSet instead of RangeSet in metadata 02/98302/8
authorRobert Varga <robert.varga@pantheon.tech>
Sat, 6 Nov 2021 10:18:54 +0000 (11:18 +0100)
committerRobert Varga <robert.varga@pantheon.tech>
Sat, 6 Nov 2021 13:38:06 +0000 (14:38 +0100)
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 <robert.varga@pantheon.tech>
15 files changed:
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/AbstractFrontendHistory.java
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/FrontendClientMetadataBuilder.java
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/FrontendHistoryMetadataBuilder.java
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/LeaderFrontendState.java
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/LocalFrontendHistory.java
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/StandaloneFrontendHistory.java
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendClientMetadata.java
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendHistoryMetadata.java
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/ImmutableUnsignedLongSet.java [new file with mode: 0644]
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/MutableUnsignedLongSet.java [new file with mode: 0644]
opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSet.java
opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/AbstractDistributedDataStoreIntegrationTest.java
opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/DistributedDataStoreRemotingIntegrationTest.java
opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/persisted/FrontendShardDataTreeSnapshotMetadataTest.java
opendaylight/md-sal/sal-distributed-datastore/src/test/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSetTest.java

index e437b07..b102e8c 100644 (file)
@@ -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<LocalHistoryIdent
     private static final Logger LOG = LoggerFactory.getLogger(AbstractFrontendHistory.class);
 
     private final Map<TransactionIdentifier, FrontendTransaction> 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<LocalHistoryIdent
     private Map<UnsignedLong, Boolean> closedTransactions;
 
     AbstractFrontendHistory(final String persistenceId, final ShardDataTree tree,
-        final Map<UnsignedLong, Boolean> closedTransactions, final UnsignedLongSet purgedTransactions) {
+            final Map<UnsignedLong, Boolean> closedTransactions, final MutableUnsignedLongSet purgedTransactions) {
         this.persistenceId = requireNonNull(persistenceId);
         this.tree = requireNonNull(tree);
         this.closedTransactions = requireNonNull(closedTransactions);
index d4befae..acb585e 100644 (file)
@@ -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<FrontendClientMe
 
         @Override
         public FrontendClientMetadata build() {
-            return new FrontendClientMetadata(getIdentifier(), ImmutableRangeSet.of(), ImmutableList.of());
+            return new FrontendClientMetadata(getIdentifier(), ImmutableUnsignedLongSet.of(), ImmutableList.of());
         }
 
         @Override
@@ -85,13 +82,13 @@ abstract class FrontendClientMetadataBuilder implements Builder<FrontendClientMe
 
     static final class Enabled extends FrontendClientMetadataBuilder {
         private final Map<LocalHistoryIdentifier, FrontendHistoryMetadataBuilder> 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<FrontendClientMe
         Enabled(final String shardName, final FrontendClientMetadata meta) {
             super(shardName, meta.getIdentifier());
 
-            purgedHistories = UnsignedLongSet.of(meta.getPurgedHistories());
+            purgedHistories = meta.getPurgedHistories().mutableCopy();
             for (FrontendHistoryMetadata h : meta.getCurrentHistories()) {
                 final FrontendHistoryMetadataBuilder b = new FrontendHistoryMetadataBuilder(getIdentifier(), h);
                 currentHistories.put(b.getIdentifier(), b);
@@ -118,7 +115,7 @@ abstract class FrontendClientMetadataBuilder implements Builder<FrontendClientMe
 
         @Override
         public FrontendClientMetadata build() {
-            return new FrontendClientMetadata(getIdentifier(), purgedHistories.toRangeSet(),
+            return new FrontendClientMetadata(getIdentifier(), purgedHistories.immutableCopy(),
                 Collections2.transform(currentHistories.values(), FrontendHistoryMetadataBuilder::build));
         }
 
@@ -219,7 +216,7 @@ abstract class FrontendClientMetadataBuilder implements Builder<FrontendClientMe
             }
 
             return new LeaderFrontendState.Enabled(shard.persistenceId(), getIdentifier(), shard.getDataStore(),
-                purgedHistories.copy(), singleHistory, histories);
+                purgedHistories.mutableCopy(), singleHistory, histories);
         }
 
         @Override
@@ -255,13 +252,10 @@ abstract class FrontendClientMetadataBuilder implements Builder<FrontendClientMe
     }
 
     static FrontendClientMetadataBuilder of(final String shardName, final FrontendClientMetadata meta) {
-        final Collection<FrontendHistoryMetadata> current = meta.getCurrentHistories();
-        final RangeSet<UnsignedLong> 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
index 0dd3c48..72bab44 100644 (file)
@@ -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<FrontendHistoryMet
         Identifiable<LocalHistoryIdentifier> {
 
     private final @NonNull Map<UnsignedLong, Boolean> 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<FrontendHistoryMet
     @Override
     public FrontendHistoryMetadata build() {
         return new FrontendHistoryMetadata(identifier.getHistoryId(), identifier.getCookie(), closed,
-            closedTransactions, purgedTransactions.toRangeSet());
+            closedTransactions, purgedTransactions.immutableCopy());
     }
 
     void onHistoryClosed() {
index ea2ef2f..ba64bad 100644 (file)
@@ -31,7 +31,7 @@ import org.opendaylight.controller.cluster.access.concepts.RequestEnvelope;
 import org.opendaylight.controller.cluster.access.concepts.RequestException;
 import org.opendaylight.controller.cluster.access.concepts.UnsupportedRequestException;
 import org.opendaylight.controller.cluster.datastore.ShardDataTreeCohort.State;
-import org.opendaylight.controller.cluster.datastore.utils.UnsignedLongSet;
+import org.opendaylight.controller.cluster.datastore.utils.MutableUnsignedLongSet;
 import org.opendaylight.yangtools.concepts.Identifiable;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
@@ -65,8 +65,8 @@ abstract class LeaderFrontendState implements Identifiable<ClientIdentifier> {
         // Histories which have not been purged
         private final Map<LocalHistoryIdentifier, LocalFrontendHistory> 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<ClientIdentifier> {
         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<LocalHistoryIdentifier, LocalFrontendHistory> localHistories) {
             super(persistenceId, clientId, tree);
             this.purgedHistories = requireNonNull(purgedHistories);
index 129ef3a..3125ed6 100644 (file)
@@ -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<UnsignedLong, Boolean> 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<UnsignedLong, Boolean> closedTransactions,
-            final UnsignedLongSet purgedTransactions) {
+            final MutableUnsignedLongSet purgedTransactions) {
         return new LocalFrontendHistory(persistenceId, tree, chain, new HashMap<>(closedTransactions),
-            purgedTransactions.copy());
+            purgedTransactions.mutableCopy());
     }
 
     @Override
index be85f68..0278c1d 100644 (file)
@@ -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<UnsignedLong, Boolean> 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<UnsignedLong, Boolean> closedTransactions,
-            final UnsignedLongSet purgedTransactions) {
+            final MutableUnsignedLongSet purgedTransactions) {
         return new StandaloneFrontendHistory(persistenceId, clientId, tree, new HashMap<>(closedTransactions),
-            purgedTransactions.copy());
+            purgedTransactions.mutableCopy());
     }
 
     @Override
index c119969..f384c92 100644 (file)
@@ -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<ClientIdentifier>, WritableObject {
     private final @NonNull ImmutableList<FrontendHistoryMetadata> currentHistories;
-    private final @NonNull ImmutableRangeSet<UnsignedLong> purgedHistories;
+    private final @NonNull ImmutableUnsignedLongSet purgedHistories;
     private final @NonNull ClientIdentifier identifier;
 
-    public FrontendClientMetadata(final ClientIdentifier identifier, final RangeSet<UnsignedLong> purgedHistories,
+    public FrontendClientMetadata(final ClientIdentifier identifier, final ImmutableUnsignedLongSet purgedHistories,
             final Collection<FrontendHistoryMetadata> 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<ClientIdentifi
         return currentHistories;
     }
 
-    public RangeSet<UnsignedLong> getPurgedHistories() {
+    public ImmutableUnsignedLongSet getPurgedHistories() {
         return purgedHistories;
     }
 
@@ -56,12 +50,7 @@ public final class FrontendClientMetadata implements Identifiable<ClientIdentifi
     @Override
     public void writeTo(final DataOutput out) throws IOException {
         identifier.writeTo(out);
-
-        final Set<Range<UnsignedLong>> ranges = purgedHistories.asRanges();
-        out.writeInt(ranges.size());
-        for (final Range<UnsignedLong> 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<ClientIdentifi
 
     public static FrontendClientMetadata readFrom(final DataInput in) throws IOException {
         final ClientIdentifier id = ClientIdentifier.readFrom(in);
-
-        final int purgedSize = in.readInt();
-        final Builder<UnsignedLong> 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<FrontendHistoryMetadata> currentHistories = new ArrayList<>(currentSize);
+        // FIXME: ImmutableList.builder()
+        final var currentHistories = new ArrayList<FrontendHistoryMetadata>(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
index e9a076e..7e27f86 100644 (file)
@@ -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<UnsignedLong> purgedTransactions;
+    private final @NonNull ImmutableUnsignedLongSet purgedTransactions;
     private final @NonNull ImmutableMap<UnsignedLong, Boolean> 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<UnsignedLong, Boolean> closedTransactions, final RangeSet<UnsignedLong> purgedTransactions) {
+            final Map<UnsignedLong, Boolean> 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<UnsignedLong, Boolean> getClosedTransactions() {
+    public ImmutableMap<UnsignedLong, Boolean> getClosedTransactions() {
         return closedTransactions;
     }
 
-    public RangeSet<UnsignedLong> 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<Range<UnsignedLong>> purgedRanges = purgedTransactions.asRanges();
-        WritableObjects.writeLongs(out, closedTransactions.size(), purgedRanges.size());
+        final int purgedSize = purgedTransactions.size();
+        WritableObjects.writeLongs(out, closedTransactions.size(), purgedSize);
         for (Entry<UnsignedLong, Boolean> e : closedTransactions.entrySet()) {
             WritableObjects.writeLong(out, e.getKey().longValue());
             out.writeBoolean(e.getValue());
         }
-        for (Range<UnsignedLong> 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<UnsignedLong> 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 (file)
index 0000000..e6c900b
--- /dev/null
@@ -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<Entry> ranges) {
+        super(ranges);
+    }
+
+    static @NonNull ImmutableUnsignedLongSet of(final TreeSet<Entry> 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<Entry>();
+        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 (file)
index 0000000..e8e479c
--- /dev/null
@@ -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<Entry> 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<UnsignedLong> toRangeSet() {
+        return ImmutableRangeSet.copyOf(Collections2.transform(trustedRanges(), Entry::toUnsigned));
+    }
+}
index ac599a6..4d4b99b 100644 (file)
@@ -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<UnsignedLong>}. 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<Entry>, Mutable {
+abstract class UnsignedLongSet {
+    @Beta
+    @VisibleForTesting
+    public static final class Entry implements Comparable<Entry>, 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<UnsignedLong>
+        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<Entry> ranges;
+    private final @NonNull TreeSet<Entry> ranges;
 
-    private UnsignedLongSet(final TreeSet<Entry> ranges) {
+    UnsignedLongSet(final TreeSet<Entry> ranges) {
         this.ranges = requireNonNull(ranges);
     }
 
-    private UnsignedLongSet(final RangeSet<UnsignedLong> 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<UnsignedLong> 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<Entry> copyRanges() {
+        return new TreeSet<>(Collections2.transform(ranges, Entry::copy));
+    }
+
+    public final @NonNull NavigableSet<Entry> ranges() {
+        return Collections.unmodifiableNavigableSet(ranges);
     }
 
-    public ImmutableRangeSet<UnsignedLong> toRangeSet() {
-        return ImmutableRangeSet.copyOf(Collections2.transform(ranges, Entry::toUnsigned));
+    final @NonNull NavigableSet<Entry> 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();
index f7fbb05..cedd4ac 100644 (file)
@@ -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<Range<UnsignedLong>> 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());
index c01949c..da219fa 100644 (file)
@@ -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<Range<UnsignedLong>> 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());
index 25b5128..dc7e1c8 100644 (file)
@@ -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<UnsignedLong> 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<FrontendHistoryMetadata> 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 <T> void testObject(final T object, final T equalObject) {
index 7742cf3..1a67547 100644 (file)
@@ -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.<UnsignedLong>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);