You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by be...@apache.org on 2023/01/26 12:43:19 UTC

[cassandra-accord] branch trunk updated: Introduce RangeDeps (#21)

This is an automated email from the ASF dual-hosted git repository.

benedict pushed a commit to branch trunk
in repository https://gitbox.apache.org/repos/asf/cassandra-accord.git


The following commit(s) were added to refs/heads/trunk by this push:
     new 686326e  Introduce RangeDeps (#21)
686326e is described below

commit 686326eedc8d2553c98a30abc81a925be3942b8c
Author: Benedict Elliott Smith <be...@apache.org>
AuthorDate: Thu Jan 26 12:43:14 2023 +0000

    Introduce RangeDeps (#21)
    
    Refactor Deps into KeyDeps and RangeDeps
    
    patch by Benedict; reviewed by Aleksey Yeschenko for CASSANDRA-18173
---
 accord-core/src/main/java/accord/api/Agent.java    |    1 +
 accord-core/src/main/java/accord/api/Key.java      |    6 +
 accord-core/src/main/java/accord/api/Result.java   |    1 +
 .../src/main/java/accord/api/TopologySorter.java   |    2 +
 .../java/accord/api/UncaughtExceptionListener.java |    1 +
 .../main/java/accord/coordinate/Coordinate.java    |    3 +-
 .../java/accord/coordinate/ReadCoordinator.java    |    3 +-
 .../src/main/java/accord/coordinate/Recover.java   |    2 +-
 .../src/main/java/accord/impl/InMemoryCommand.java |    1 +
 .../java/accord/impl/InMemoryCommandStore.java     |   10 +
 .../main/java/accord/impl/SimpleProgressLog.java   |    1 +
 .../src/main/java/accord/local/Command.java        |    4 +-
 accord-core/src/main/java/accord/local/Node.java   |    4 +
 .../main/java/accord/local/SafeCommandStore.java   |    1 -
 .../src/main/java/accord/messages/Accept.java      |    2 +
 .../src/main/java/accord/messages/Apply.java       |    3 +
 .../main/java/accord/messages/BeginRecovery.java   |   10 +-
 .../src/main/java/accord/messages/CheckStatus.java |    2 +
 .../src/main/java/accord/messages/Commit.java      |    2 +
 .../src/main/java/accord/messages/Defer.java       |    2 +-
 .../src/main/java/accord/messages/GetDeps.java     |    1 +
 .../main/java/accord/messages/InformDurable.java   |    1 +
 .../java/accord/messages/InformHomeDurable.java    |    1 +
 .../src/main/java/accord/messages/PreAccept.java   |   10 +-
 .../src/main/java/accord/messages/ReadData.java    |    1 +
 .../src/main/java/accord/messages/TxnRequest.java  |    1 +
 .../main/java/accord/messages/WaitOnCommit.java    |    1 +
 .../main/java/accord/primitives/AbstractKeys.java  |   13 +-
 .../java/accord/primitives/AbstractRanges.java     |   17 +-
 .../accord/primitives/AbstractRoutableKeys.java    |   11 -
 .../accord/primitives/AbstractUnseekableKeys.java  |   19 +
 .../src/main/java/accord/primitives/Ballot.java    |    1 +
 .../src/main/java/accord/primitives/Deps.java      | 1306 ++------------------
 .../main/java/accord/primitives/FullKeyRoute.java  |    1 +
 .../java/accord/primitives/FullRangeRoute.java     |    1 +
 .../src/main/java/accord/primitives/KeyDeps.java   |  537 ++++++++
 .../src/main/java/accord/primitives/KeyRoute.java  |    2 +-
 .../main/java/accord/primitives/PartialDeps.java   |   63 +-
 .../java/accord/primitives/PartialKeyRoute.java    |    5 +-
 .../java/accord/primitives/PartialRangeRoute.java  |    4 +
 .../main/java/accord/primitives/PartialRoute.java  |    1 +
 .../main/java/accord/primitives/PartialTxn.java    |    3 +
 .../src/main/java/accord/primitives/Range.java     |   51 +-
 .../src/main/java/accord/primitives/RangeDeps.java |  663 ++++++++++
 .../src/main/java/accord/primitives/Ranges.java    |    2 +-
 .../main/java/accord/primitives/RoutableKey.java   |    3 +
 .../src/main/java/accord/primitives/Route.java     |    3 +
 .../main/java/accord/primitives/RoutingKeys.java   |    7 +-
 .../src/main/java/accord/primitives/Seekable.java  |    4 +
 .../src/main/java/accord/primitives/Seekables.java |    2 +
 .../src/main/java/accord/primitives/TxnId.java     |    1 +
 .../main/java/accord/primitives/Unseekables.java   |    2 +
 .../main/java/accord/primitives/package-info.java  |    4 +-
 .../src/main/java/accord/topology/Topology.java    |    4 +-
 .../src/main/java/accord/utils/ArrayBuffers.java   |  123 +-
 .../accord/utils/DeterministicIdentitySet.java     |    9 +-
 .../java/accord/utils/IntrusiveLinkedList.java     |    1 +
 .../src/main/java/accord/utils/MapReduce.java      |    1 +
 .../main/java/accord/utils/MapReduceConsume.java   |    1 +
 .../main/java/accord/utils/RelationMultiMap.java   | 1004 +++++++++++++++
 .../java/accord/utils/SearchableRangeList.java     |  292 +++++
 .../accord/utils/SearchableRangeListBuilder.java   | 1077 ++++++++++++++++
 .../src/main/java/accord/utils/SortedArrays.java   |   97 +-
 .../java/accord/utils/SymmetricComparator.java     |    7 +
 .../java/accord/coordinate/CoordinateTest.java     |    5 +-
 .../test/java/accord/messages/PreAcceptTest.java   |   10 +-
 .../DepsTest.java => primitives/KeyDepsTest.java}  |  127 +-
 .../test/java/accord/primitives/RangeDepsTest.java |  229 ++++
 .../src/main/java/accord/maelstrom/Json.java       |   65 +-
 69 files changed, 4426 insertions(+), 1429 deletions(-)

diff --git a/accord-core/src/main/java/accord/api/Agent.java b/accord-core/src/main/java/accord/api/Agent.java
index 83f51a7..0045eb0 100644
--- a/accord-core/src/main/java/accord/api/Agent.java
+++ b/accord-core/src/main/java/accord/api/Agent.java
@@ -47,6 +47,7 @@ public interface Agent extends UncaughtExceptionListener
      */
     void onInconsistentTimestamp(Command command, Timestamp prev, Timestamp next);
 
+    @Override
     void onUncaughtException(Throwable t);
 
     void onHandledException(Throwable t);
diff --git a/accord-core/src/main/java/accord/api/Key.java b/accord-core/src/main/java/accord/api/Key.java
index 5307828..8c4078c 100644
--- a/accord-core/src/main/java/accord/api/Key.java
+++ b/accord-core/src/main/java/accord/api/Key.java
@@ -18,6 +18,7 @@
 
 package accord.api;
 
+import accord.primitives.Range;
 import accord.primitives.RoutableKey;
 import accord.primitives.Seekable;
 
@@ -26,4 +27,9 @@ import accord.primitives.Seekable;
  */
 public interface Key extends Seekable, RoutableKey
 {
+    @Override
+    default Key asKey() { return this; }
+
+    @Override
+    default Range asRange() { throw new UnsupportedOperationException(); }
 }
diff --git a/accord-core/src/main/java/accord/api/Result.java b/accord-core/src/main/java/accord/api/Result.java
index a5ac298..d8b8fd6 100644
--- a/accord-core/src/main/java/accord/api/Result.java
+++ b/accord-core/src/main/java/accord/api/Result.java
@@ -28,5 +28,6 @@ import accord.primitives.ProgressToken;
  */
 public interface Result extends Outcome
 {
+    @Override
     default ProgressToken asProgressToken() { return ProgressToken.APPLIED; }
 }
diff --git a/accord-core/src/main/java/accord/api/TopologySorter.java b/accord-core/src/main/java/accord/api/TopologySorter.java
index c3587b2..c78f049 100644
--- a/accord-core/src/main/java/accord/api/TopologySorter.java
+++ b/accord-core/src/main/java/accord/api/TopologySorter.java
@@ -15,7 +15,9 @@ public interface TopologySorter
 
     interface StaticSorter extends Supplier, TopologySorter
     {
+        @Override
         default TopologySorter get(Topology topologies) { return this; }
+        @Override
         default TopologySorter get(Topologies topologies) { return this; }
     }
 
diff --git a/accord-core/src/main/java/accord/api/UncaughtExceptionListener.java b/accord-core/src/main/java/accord/api/UncaughtExceptionListener.java
index 60105f0..8395ea6 100644
--- a/accord-core/src/main/java/accord/api/UncaughtExceptionListener.java
+++ b/accord-core/src/main/java/accord/api/UncaughtExceptionListener.java
@@ -5,6 +5,7 @@ import java.util.function.BiConsumer;
 public interface UncaughtExceptionListener extends BiConsumer<Object, Throwable>
 {
     void onUncaughtException(Throwable t);
+    @Override
     default void accept(Object ignore, Throwable t)
     {
         if (t != null)
diff --git a/accord-core/src/main/java/accord/coordinate/Coordinate.java b/accord-core/src/main/java/accord/coordinate/Coordinate.java
index dec539c..aa70507 100644
--- a/accord-core/src/main/java/accord/coordinate/Coordinate.java
+++ b/accord-core/src/main/java/accord/coordinate/Coordinate.java
@@ -53,7 +53,7 @@ public class Coordinate extends AsyncFuture<Result> implements Callback<PreAccep
     final Txn txn;
     final FullRoute<?> route;
 
-    private FastPathTracker tracker;
+    private final FastPathTracker tracker;
     private boolean preAcceptIsDone;
     private final List<PreAcceptOk> successes;
 
@@ -108,6 +108,7 @@ public class Coordinate extends AsyncFuture<Result> implements Callback<PreAccep
         tryFailure(failure);
     }
 
+    @Override
     public synchronized void onSuccess(Id from, PreAcceptReply reply)
     {
         if (preAcceptIsDone)
diff --git a/accord-core/src/main/java/accord/coordinate/ReadCoordinator.java b/accord-core/src/main/java/accord/coordinate/ReadCoordinator.java
index 837b2cc..3892b04 100644
--- a/accord-core/src/main/java/accord/coordinate/ReadCoordinator.java
+++ b/accord-core/src/main/java/accord/coordinate/ReadCoordinator.java
@@ -55,7 +55,7 @@ abstract class ReadCoordinator<Reply extends accord.messages.Reply> extends Read
     final TxnId txnId;
     private boolean isDone;
     private Throwable failure;
-    Map<Id, Object> debug = DEBUG ? new HashMap<>() : null;
+    final Map<Id, Object> debug = DEBUG ? new HashMap<>() : null;
 
     ReadCoordinator(Node node, Topologies topologies, TxnId txnId)
     {
@@ -102,6 +102,7 @@ abstract class ReadCoordinator<Reply extends accord.messages.Reply> extends Read
         }
     }
 
+    @Override
     public void onSlowResponse(Id from)
     {
         handle(recordSlowResponse(from));
diff --git a/accord-core/src/main/java/accord/coordinate/Recover.java b/accord-core/src/main/java/accord/coordinate/Recover.java
index 3ad5d67..ccad4e7 100644
--- a/accord-core/src/main/java/accord/coordinate/Recover.java
+++ b/accord-core/src/main/java/accord/coordinate/Recover.java
@@ -100,7 +100,7 @@ public class Recover implements Callback<RecoverReply>, BiConsumer<Result, Throw
         for (int i = 0 ; i < waitOn.txnIdCount() ; ++i)
         {
             TxnId txnId = waitOn.txnId(i);
-            new AwaitCommit(node, txnId, waitOn.someRoutables(txnId)).addCallback((success, failure) -> {
+            new AwaitCommit(node, txnId, waitOn.someUnseekables(txnId)).addCallback((success, failure) -> {
                 if (future.isDone())
                     return;
                 if (success != null && remaining.decrementAndGet() == 0)
diff --git a/accord-core/src/main/java/accord/impl/InMemoryCommand.java b/accord-core/src/main/java/accord/impl/InMemoryCommand.java
index d72b574..8525046 100644
--- a/accord-core/src/main/java/accord/impl/InMemoryCommand.java
+++ b/accord-core/src/main/java/accord/impl/InMemoryCommand.java
@@ -309,6 +309,7 @@ public class InMemoryCommand extends Command
         return waitingOnCommit != null && !waitingOnCommit.isEmpty();
     }
 
+    @Override
     public boolean isWaitingOnDependency()
     {
         return isWaitingOnCommit() || isWaitingOnApply();
diff --git a/accord-core/src/main/java/accord/impl/InMemoryCommandStore.java b/accord-core/src/main/java/accord/impl/InMemoryCommandStore.java
index 7977d2c..b2444ec 100644
--- a/accord-core/src/main/java/accord/impl/InMemoryCommandStore.java
+++ b/accord-core/src/main/java/accord/impl/InMemoryCommandStore.java
@@ -79,17 +79,20 @@ public class InMemoryCommandStore
             this.commandStore = commandStore;
         }
 
+        @Override
         public Command ifPresent(TxnId txnId)
         {
             return commands.get(txnId);
         }
 
         // TODO (required): mimic caching to test C* behaviour
+        @Override
         public Command ifLoaded(TxnId txnId)
         {
             return commands.get(txnId);
         }
 
+        @Override
         public Command command(TxnId txnId)
         {
             return commands.computeIfAbsent(txnId, id -> new InMemoryCommand(commandStore, id));
@@ -100,6 +103,7 @@ public class InMemoryCommandStore
             return commands.containsKey(txnId);
         }
 
+        @Override
         public CommandsForKey commandsForKey(Key key)
         {
             return commandsForKey.computeIfAbsent(key, k -> new InMemoryCommandsForKey((Key) k));
@@ -110,11 +114,13 @@ public class InMemoryCommandStore
             return commandsForKey.containsKey(key);
         }
 
+        @Override
         public CommandsForKey maybeCommandsForKey(Key key)
         {
             return commandsForKey.get(key);
         }
 
+        @Override
         public void addAndInvokeListener(TxnId txnId, CommandListener listener)
         {
             command(txnId).addListener(listener);
@@ -221,6 +227,7 @@ public class InMemoryCommandStore
             }
         }
 
+        @Override
         public <T> T mapReduce(Routables<?, ?> keysOrRanges, Ranges slice, Function<CommandsForKey, T> map, BinaryOperator<T> reduce, T initialValue)
         {
             switch (keysOrRanges.kindOfContents()) {
@@ -241,6 +248,7 @@ public class InMemoryCommandStore
             }
         }
 
+        @Override
         public void forEach(Routables<?, ?> keysOrRanges, Ranges slice, Consumer<CommandsForKey> forEach)
         {
             switch (keysOrRanges.kindOfContents()) {
@@ -259,6 +267,7 @@ public class InMemoryCommandStore
             }
         }
 
+        @Override
         public void forEach(Routable keyOrRange, Ranges slice, Consumer<CommandsForKey> forEach)
         {
             switch (keyOrRange.domain())
@@ -294,6 +303,7 @@ public class InMemoryCommandStore
                 return submit(context, i -> { consumer.accept(i); return null; });
             }
 
+            @Override
             public synchronized <T> Future<T> submit(PreLoadContext context, Function<? super SafeCommandStore, T> function)
             {
                 AsyncPromise<T> promise = new AsyncPromise<>();
diff --git a/accord-core/src/main/java/accord/impl/SimpleProgressLog.java b/accord-core/src/main/java/accord/impl/SimpleProgressLog.java
index e27553f..fa9d48b 100644
--- a/accord-core/src/main/java/accord/impl/SimpleProgressLog.java
+++ b/accord-core/src/main/java/accord/impl/SimpleProgressLog.java
@@ -156,6 +156,7 @@ public class SimpleProgressLog implements ProgressLog.Factory
             }
 
             // exists only on home shard
+            // TODO (expected): should not take any prompt action if we're ourselves already coordinating the transaction
             class CoordinateState extends Monitoring
             {
                 CoordinateStatus status = CoordinateStatus.NotWitnessed;
diff --git a/accord-core/src/main/java/accord/local/Command.java b/accord-core/src/main/java/accord/local/Command.java
index 4f7697f..16c7a71 100644
--- a/accord-core/src/main/java/accord/local/Command.java
+++ b/accord-core/src/main/java/accord/local/Command.java
@@ -408,7 +408,7 @@ public abstract class Command implements CommandListener, BiConsumer<SafeCommand
     {
         Ranges ranges = safeStore.ranges().since(executeAt().epoch());
         if (ranges != null) {
-            partialDeps().forEachOn(ranges, txnId -> {
+            partialDeps().forEach(ranges, txnId -> {
                 Command command = safeStore.ifLoaded(txnId);
                 if (command == null)
                 {
@@ -764,7 +764,7 @@ public abstract class Command implements CommandListener, BiConsumer<SafeCommand
                     }
 
                     Unseekables<?, ?> someKeys = cur.maxUnseekables();
-                    if (someKeys == null && prev != null) someKeys = prev.partialDeps().someRoutables(cur.txnId());
+                    if (someKeys == null && prev != null) someKeys = prev.partialDeps().someUnseekables(cur.txnId());
                     Invariants.checkState(someKeys != null);
                     logger.trace("{} blocked on {} until {}", txnIds[0], cur.txnId(), until);
                     safeStore.progressLog().waiting(cur.txnId(), until, someKeys);
diff --git a/accord-core/src/main/java/accord/local/Node.java b/accord-core/src/main/java/accord/local/Node.java
index 9047034..15de0dc 100644
--- a/accord-core/src/main/java/accord/local/Node.java
+++ b/accord-core/src/main/java/accord/local/Node.java
@@ -159,6 +159,7 @@ public class Node implements ConfigurationService.Listener, NodeTimeService
         return messageSink;
     }
 
+    @Override
     public long epoch()
     {
         return topology().epoch();
@@ -235,6 +236,7 @@ public class Node implements ConfigurationService.Listener, NodeTimeService
         });
     }
 
+    @Override
     public Timestamp uniqueNow(Timestamp atLeast)
     {
         if (now.get().compareTo(atLeast) < 0)
@@ -247,6 +249,7 @@ public class Node implements ConfigurationService.Listener, NodeTimeService
         return uniqueNow();
     }
 
+    @Override
     public long now()
     {
         return nowSupplier.getAsLong();
@@ -505,6 +508,7 @@ public class Node implements ConfigurationService.Listener, NodeTimeService
         return agent;
     }
 
+    @Override
     public Id id()
     {
         return id;
diff --git a/accord-core/src/main/java/accord/local/SafeCommandStore.java b/accord-core/src/main/java/accord/local/SafeCommandStore.java
index 04ace5c..1dc118c 100644
--- a/accord-core/src/main/java/accord/local/SafeCommandStore.java
+++ b/accord-core/src/main/java/accord/local/SafeCommandStore.java
@@ -61,7 +61,6 @@ public interface SafeCommandStore
     void forEach(Routables<?, ?> keys, Ranges slice, Consumer<CommandsForKey> forEach);
     void forEach(Routable keyOrRange, Ranges slice, Consumer<CommandsForKey> forEach);
 
-
     CommandStore commandStore();
     DataStore dataStore();
     Agent agent();
diff --git a/accord-core/src/main/java/accord/messages/Accept.java b/accord-core/src/main/java/accord/messages/Accept.java
index 7ea2631..bb9cffd 100644
--- a/accord-core/src/main/java/accord/messages/Accept.java
+++ b/accord-core/src/main/java/accord/messages/Accept.java
@@ -114,6 +114,7 @@ public class Accept extends TxnRequest.WithUnsynced<Accept.AcceptReply>
         node.reply(replyTo, replyContext, reply);
     }
 
+    @Override
     public void process()
     {
         node.mapReduceConsumeLocal(this, minEpoch, executeAt.epoch(), this);
@@ -220,6 +221,7 @@ public class Accept extends TxnRequest.WithUnsynced<Accept.AcceptReply>
             this.someKey = someKey;
         }
 
+        @Override
         public void process()
         {
             node.mapReduceConsumeLocal(this, someKey, txnId.epoch(), this);
diff --git a/accord-core/src/main/java/accord/messages/Apply.java b/accord-core/src/main/java/accord/messages/Apply.java
index c692d8d..7dac560 100644
--- a/accord-core/src/main/java/accord/messages/Apply.java
+++ b/accord-core/src/main/java/accord/messages/Apply.java
@@ -70,12 +70,14 @@ public class Apply extends TxnRequest<ApplyReply>
         this.result = result;
     }
 
+    @Override
     public void process()
     {
         // note, we do not also commit here if txnId.epoch != executeAt.epoch, as the scope() for a commit would be different
         node.mapReduceConsumeLocal(this, txnId.epoch(), untilEpoch, this);
     }
 
+    @Override
     public ApplyReply apply(SafeCommandStore safeStore)
     {
         Command command = safeStore.command(txnId);
@@ -91,6 +93,7 @@ public class Apply extends TxnRequest<ApplyReply>
         }
     }
 
+    @Override
     public ApplyReply reduce(ApplyReply a, ApplyReply b)
     {
         return a.compareTo(b) >= 0 ? a : b;
diff --git a/accord-core/src/main/java/accord/messages/BeginRecovery.java b/accord-core/src/main/java/accord/messages/BeginRecovery.java
index dad40c5..2d4bd1d 100644
--- a/accord-core/src/main/java/accord/messages/BeginRecovery.java
+++ b/accord-core/src/main/java/accord/messages/BeginRecovery.java
@@ -297,7 +297,7 @@ public class BeginRecovery extends TxnRequest<BeginRecovery.RecoverReply>
 
     private static Deps acceptedStartedBeforeWithoutWitnessing(SafeCommandStore commandStore, TxnId txnId, Ranges ranges, Seekables<?, ?> keys)
     {
-        try (Deps.OrderedBuilder builder = Deps.orderedBuilder(true))
+        try (Deps.Builder builder = Deps.builder())
         {
             commandStore.forEach(keys, ranges, forKey -> {
                 // accepted txns with an earlier txnid that do not have our txnid as a dependency
@@ -312,10 +312,9 @@ public class BeginRecovery extends TxnRequest<BeginRecovery.RecoverReply>
                  * Which is to say, we expect the previously proposed dependencies (if any) to be used to evaluate this
                  * condition.
                  */
-                builder.nextKey(forKey.key());
                 forKey.uncommitted().before(txnId, RorWs, WITHOUT, txnId, HAS_BEEN, Accepted).forEach((command) -> {
                     if (command.executeAt.compareTo(txnId) > 0)
-                        builder.add(command.txnId);
+                        builder.add(forKey.key(), command.txnId);
                 });
             });
             return builder.build();
@@ -324,7 +323,7 @@ public class BeginRecovery extends TxnRequest<BeginRecovery.RecoverReply>
 
     private static Deps committedStartedBeforeAndWitnessed(SafeCommandStore commandStore, TxnId txnId, Ranges ranges, Seekables<?, ?> keys)
     {
-        try (Deps.OrderedBuilder builder = Deps.orderedBuilder(true))
+        try (Deps.Builder builder = Deps.builder())
         {
             commandStore.forEach(keys, ranges, forKey -> {
                 /*
@@ -332,9 +331,8 @@ public class BeginRecovery extends TxnRequest<BeginRecovery.RecoverReply>
                  * so that we can remove these from the set of acceptedStartedBeforeAndDidNotWitness
                  * on other nodes, to minimise the number of transactions we try to wait for on recovery
                  */
-                builder.nextKey(forKey.key());
                 forKey.committedById().before(txnId, RorWs, WITH, txnId, HAS_BEEN, Committed)
-                        .forEach(builder::add);
+                        .forEach(id -> builder.add(forKey.key(), id));
             });
             return builder.build();
         }
diff --git a/accord-core/src/main/java/accord/messages/CheckStatus.java b/accord-core/src/main/java/accord/messages/CheckStatus.java
index d3242dd..0399e1e 100644
--- a/accord-core/src/main/java/accord/messages/CheckStatus.java
+++ b/accord-core/src/main/java/accord/messages/CheckStatus.java
@@ -100,6 +100,7 @@ public class CheckStatus extends AbstractEpochRequest<CheckStatus.CheckStatusOk>
         this.includeInfo = includeInfo;
     }
 
+    @Override
     public void process()
     {
         node.mapReduceConsumeLocal(this, query, startEpoch, endEpoch, this);
@@ -272,6 +273,7 @@ public class CheckStatus extends AbstractEpochRequest<CheckStatus.CheckStatusOk>
          * reply, the info would potentially be unsafe to act upon when given a higher status
          * (e.g. Accepted executeAt is very different to Committed executeAt))
          */
+        @Override
         public CheckStatusOk merge(CheckStatusOk that)
         {
             CheckStatusOk max = super.merge(that);
diff --git a/accord-core/src/main/java/accord/messages/Commit.java b/accord-core/src/main/java/accord/messages/Commit.java
index 55c1c88..a498cd7 100644
--- a/accord-core/src/main/java/accord/messages/Commit.java
+++ b/accord-core/src/main/java/accord/messages/Commit.java
@@ -138,6 +138,7 @@ public class Commit extends TxnRequest<ReadNack>
         return Keys.EMPTY;
     }
 
+    @Override
     public void process()
     {
         node.mapReduceConsumeLocal(this, txnId.epoch(), executeAt.epoch(), this);
@@ -268,6 +269,7 @@ public class Commit extends TxnRequest<ReadNack>
             return waitForEpoch;
         }
 
+        @Override
         public void process(Node node, Id from, ReplyContext replyContext)
         {
             node.forEachLocal(this, scope, txnId.epoch(), invalidateUntilEpoch,
diff --git a/accord-core/src/main/java/accord/messages/Defer.java b/accord-core/src/main/java/accord/messages/Defer.java
index ede92ba..6fa9579 100644
--- a/accord-core/src/main/java/accord/messages/Defer.java
+++ b/accord-core/src/main/java/accord/messages/Defer.java
@@ -18,7 +18,7 @@ class Defer implements CommandListener
 
     final Function<Command, Ready> waitUntil;
     final TxnRequest<?> request;
-    IntHashSet waitingOn = new IntHashSet(); // TODO (easy): use Agrona when available
+    final IntHashSet waitingOn = new IntHashSet(); // TODO (easy): use Agrona when available
     int waitingOnCount;
     boolean isDone;
 
diff --git a/accord-core/src/main/java/accord/messages/GetDeps.java b/accord-core/src/main/java/accord/messages/GetDeps.java
index de4d518..13e9bc4 100644
--- a/accord-core/src/main/java/accord/messages/GetDeps.java
+++ b/accord-core/src/main/java/accord/messages/GetDeps.java
@@ -42,6 +42,7 @@ public class GetDeps extends TxnRequest.WithUnsynced<PartialDeps>
         this.kind = kind;
     }
 
+    @Override
     public void process()
     {
         node.mapReduceConsumeLocal(this, minEpoch, executeAt.epoch(), this);
diff --git a/accord-core/src/main/java/accord/messages/InformDurable.java b/accord-core/src/main/java/accord/messages/InformDurable.java
index 5586c22..20066e4 100644
--- a/accord-core/src/main/java/accord/messages/InformDurable.java
+++ b/accord-core/src/main/java/accord/messages/InformDurable.java
@@ -45,6 +45,7 @@ public class InformDurable extends TxnRequest<Reply> implements PreLoadContext
         this.durability = durability;
     }
 
+    @Override
     public void process()
     {
         Timestamp at = txnId;
diff --git a/accord-core/src/main/java/accord/messages/InformHomeDurable.java b/accord-core/src/main/java/accord/messages/InformHomeDurable.java
index 1f91153..d0282f4 100644
--- a/accord-core/src/main/java/accord/messages/InformHomeDurable.java
+++ b/accord-core/src/main/java/accord/messages/InformHomeDurable.java
@@ -29,6 +29,7 @@ public class InformHomeDurable implements Request
         this.persistedOn = persistedOn;
     }
 
+    @Override
     public void process(Node node, Id replyToNode, ReplyContext replyContext)
     {
         // TODO (expected, efficiency): do not load txnId first
diff --git a/accord-core/src/main/java/accord/messages/PreAccept.java b/accord-core/src/main/java/accord/messages/PreAccept.java
index 310c0a0..bb90b40 100644
--- a/accord-core/src/main/java/accord/messages/PreAccept.java
+++ b/accord-core/src/main/java/accord/messages/PreAccept.java
@@ -88,6 +88,7 @@ public class PreAccept extends WithUnsynced<PreAccept.PreAcceptReply>
         node.mapReduceConsumeLocal(this, minEpoch, maxEpoch, this);
     }
 
+    @Override
     public PreAcceptReply apply(SafeCommandStore safeStore)
     {
         // note: this diverges from the paper, in that instead of waiting for JoinShard,
@@ -210,24 +211,23 @@ public class PreAccept extends WithUnsynced<PreAccept.PreAcceptReply>
 
     static PartialDeps calculatePartialDeps(SafeCommandStore commandStore, TxnId txnId, Seekables<?, ?> keys, Txn.Kind kindOfTxn, Timestamp executeAt, Ranges ranges)
     {
-        try (PartialDeps.OrderedBuilder builder = PartialDeps.orderedBuilder(ranges, false))
+        try (PartialDeps.Builder builder = PartialDeps.builder(ranges))
         {
             return calculateDeps(commandStore, txnId, keys, kindOfTxn, executeAt, ranges, builder);
         }
     }
 
-    private static <T extends Deps> T calculateDeps(SafeCommandStore commandStore, TxnId txnId, Seekables<?, ?> keys, Txn.Kind kindOfTxn, Timestamp executeAt, Ranges ranges, Deps.AbstractOrderedBuilder<T> builder)
+    private static <T extends Deps> T calculateDeps(SafeCommandStore commandStore, TxnId txnId, Seekables<?, ?> keys, Txn.Kind kindOfTxn, Timestamp executeAt, Ranges ranges, Deps.AbstractBuilder<T> builder)
     {
         TestKind testKind = kindOfTxn.isWrite() ? RorWs : Ws;
         commandStore.forEach(keys, ranges, forKey -> {
-            builder.nextKey(forKey.key());
             forKey.uncommitted().before(executeAt, testKind, ANY_DEPS, null, ANY_STATUS, null)
                     .forEach(info -> {
-                        if (!info.txnId.equals(txnId)) builder.add(info.txnId);
+                        if (!info.txnId.equals(txnId)) builder.add(forKey.key(), info.txnId);
                     });
             forKey.committedByExecuteAt().before(executeAt, testKind, ANY_DEPS, null, ANY_STATUS, null)
                     .forEach(id -> {
-                        if (!id.equals(txnId)) builder.add(id);
+                        if (!id.equals(txnId)) builder.add(forKey.key(), id);
                     });
         });
 
diff --git a/accord-core/src/main/java/accord/messages/ReadData.java b/accord-core/src/main/java/accord/messages/ReadData.java
index d204de2..fee7e27 100644
--- a/accord-core/src/main/java/accord/messages/ReadData.java
+++ b/accord-core/src/main/java/accord/messages/ReadData.java
@@ -320,6 +320,7 @@ public class ReadData extends AbstractEpochRequest<ReadData.ReadNack> implements
             return READ_RSP;
         }
 
+        @Override
         public boolean isOk()
         {
             return true;
diff --git a/accord-core/src/main/java/accord/messages/TxnRequest.java b/accord-core/src/main/java/accord/messages/TxnRequest.java
index 58bc8d4..5b9b928 100644
--- a/accord-core/src/main/java/accord/messages/TxnRequest.java
+++ b/accord-core/src/main/java/accord/messages/TxnRequest.java
@@ -129,6 +129,7 @@ public abstract class TxnRequest<R> implements Request, PreLoadContext, MapReduc
      * to permit a recipient to process a request before knowing of a topology change if the sender determines it is
      * safe to do so.
      */
+    @Override
     public long waitForEpoch()
     {
         return waitForEpoch;
diff --git a/accord-core/src/main/java/accord/messages/WaitOnCommit.java b/accord-core/src/main/java/accord/messages/WaitOnCommit.java
index 490bc65..b7c20f9 100644
--- a/accord-core/src/main/java/accord/messages/WaitOnCommit.java
+++ b/accord-core/src/main/java/accord/messages/WaitOnCommit.java
@@ -65,6 +65,7 @@ public class WaitOnCommit implements Request, MapReduceConsume<SafeCommandStore,
         this.scope = scope;
     }
 
+    @Override
     public void process(Node node, Id replyToNode, ReplyContext replyContext)
     {
         this.node = node;
diff --git a/accord-core/src/main/java/accord/primitives/AbstractKeys.java b/accord-core/src/main/java/accord/primitives/AbstractKeys.java
index 9b11cc4..6fc570a 100644
--- a/accord-core/src/main/java/accord/primitives/AbstractKeys.java
+++ b/accord-core/src/main/java/accord/primitives/AbstractKeys.java
@@ -35,11 +35,18 @@ public abstract class AbstractKeys<K extends RoutableKey, KS extends Routables<K
         return Arrays.equals(keys, that.keys);
     }
 
-    public final int indexOf(K key)
+    @Override
+    public int indexOf(K key)
+    {
+        return Arrays.binarySearch(keys, key);
+    }
+
+    public int indexOf(RoutingKey key)
     {
         return Arrays.binarySearch(keys, key);
     }
 
+    @Override
     public final K get(int indexOf)
     {
         return keys[indexOf];
@@ -51,21 +58,25 @@ public abstract class AbstractKeys<K extends RoutableKey, KS extends Routables<K
         return Key;
     }
 
+    @Override
     public final boolean isEmpty()
     {
         return keys.length == 0;
     }
 
+    @Override
     public final int size()
     {
         return keys.length;
     }
 
+    @Override
     public final boolean contains(RoutableKey key)
     {
         return Arrays.binarySearch(keys, key) >= 0;
     }
 
+    @Override
     public final boolean containsAll(Routables<?, ?> keysOrRanges)
     {
         return keysOrRanges.size() == Routables.foldl(keysOrRanges, this, (k, p, v, i) -> v + 1, 0, 0, 0);
diff --git a/accord-core/src/main/java/accord/primitives/AbstractRanges.java b/accord-core/src/main/java/accord/primitives/AbstractRanges.java
index 9d5a4fa..740233b 100644
--- a/accord-core/src/main/java/accord/primitives/AbstractRanges.java
+++ b/accord-core/src/main/java/accord/primitives/AbstractRanges.java
@@ -50,16 +50,19 @@ public abstract class AbstractRanges<RS extends Routables<Range, ?>> implements
         return SortedArrays.binarySearch(ranges, 0, ranges.length, key, (k, r) -> -r.compareTo(k), FAST);
     }
 
+    @Override
     public int indexOf(Range find)
     {
         return SortedArrays.binarySearch(ranges, 0, ranges.length, find, Range::compareIntersecting, FAST);
     }
 
+    @Override
     public boolean contains(RoutableKey key)
     {
         return indexOf(key) >= 0;
     }
 
+    @Override
     public boolean containsAll(Routables<?, ?> that)
     {
         switch (that.kindOfContents())
@@ -90,6 +93,7 @@ public abstract class AbstractRanges<RS extends Routables<Range, ?>> implements
         return ((int) supersetLinearMerge(this.ranges, that.ranges)) == that.size();
     }
 
+    @Override
     public int size()
     {
         return ranges.length;
@@ -128,6 +132,7 @@ public abstract class AbstractRanges<RS extends Routables<Range, ?>> implements
         return findNextIntersection(0, keys, 0) >= 0;
     }
 
+    @Override
     public boolean intersects(AbstractRanges<?> that)
     {
         return SortedArrays.findNextIntersection(this.ranges, 0, that.ranges, 0, Range::compareIntersecting) >= 0;
@@ -139,12 +144,14 @@ public abstract class AbstractRanges<RS extends Routables<Range, ?>> implements
     }
 
     // returns ri in low 32 bits, ki in top, or -1 if no match found
+    @Override
     public long findNextIntersection(int ri, AbstractKeys<?, ?> keys, int ki)
     {
         return swapHighLow32b(SortedArrays.findNextIntersectionWithMultipleMatches(keys.keys, ki, ranges, ri));
     }
 
     // returns ki in bottom 32 bits, ri in top, or -1 if no match found
+    @Override
     public long findNextIntersection(int thisi, AbstractRanges<?> that, int thati)
     {
         return SortedArrays.findNextIntersectionWithMultipleMatches(ranges, thisi, that.ranges, thati, Range::compareIntersecting, Range::compareIntersecting);
@@ -411,20 +418,20 @@ public abstract class AbstractRanges<RS extends Routables<Range, ?>> implements
         if (ranges.length == 0)
             return input;
 
-        ObjectBuffers<Range> cachedKeyRanges = cachedRanges();
-        Range[] buffer = cachedKeyRanges.get(ranges.length);
+        ObjectBuffers<Range> cachedRanges = cachedRanges();
+        Range[] buffer = cachedRanges.get(ranges.length);
         try
         {
             int count = copyAndMergeTouching(ranges, 0, buffer, 0, ranges.length);
             if (count == buffer.length)
                 return input;
-            Range[] result = cachedKeyRanges.complete(buffer, count);
-            cachedKeyRanges.discard(buffer, count);
+            Range[] result = cachedRanges.complete(buffer, count);
+            cachedRanges.discard(buffer, count);
             return constructor.apply(result);
         }
         catch (Throwable t)
         {
-            cachedKeyRanges.forceDiscard(buffer, ranges.length);
+            cachedRanges.forceDiscard(buffer, ranges.length);
             throw t;
         }
     }
diff --git a/accord-core/src/main/java/accord/primitives/AbstractRoutableKeys.java b/accord-core/src/main/java/accord/primitives/AbstractRoutableKeys.java
deleted file mode 100644
index a7ae455..0000000
--- a/accord-core/src/main/java/accord/primitives/AbstractRoutableKeys.java
+++ /dev/null
@@ -1,11 +0,0 @@
-package accord.primitives;
-
-import accord.api.RoutingKey;
-
-public abstract class AbstractRoutableKeys<KS extends Unseekables<RoutingKey, ?>> extends AbstractKeys<RoutingKey, KS> implements Iterable<RoutingKey>, Unseekables<RoutingKey, KS>
-{
-    AbstractRoutableKeys(RoutingKey[] keys)
-    {
-        super(keys);
-    }
-}
diff --git a/accord-core/src/main/java/accord/primitives/AbstractUnseekableKeys.java b/accord-core/src/main/java/accord/primitives/AbstractUnseekableKeys.java
new file mode 100644
index 0000000..6176193
--- /dev/null
+++ b/accord-core/src/main/java/accord/primitives/AbstractUnseekableKeys.java
@@ -0,0 +1,19 @@
+package accord.primitives;
+
+import accord.api.RoutingKey;
+
+import java.util.Arrays;
+
+public abstract class AbstractUnseekableKeys<KS extends Unseekables<RoutingKey, ?>> extends AbstractKeys<RoutingKey, KS> implements Iterable<RoutingKey>, Unseekables<RoutingKey, KS>
+{
+    AbstractUnseekableKeys(RoutingKey[] keys)
+    {
+        super(keys);
+    }
+
+    @Override
+    public final int indexOf(RoutingKey key)
+    {
+        return Arrays.binarySearch(keys, key);
+    }
+}
diff --git a/accord-core/src/main/java/accord/primitives/Ballot.java b/accord-core/src/main/java/accord/primitives/Ballot.java
index 7e66668..121dd0a 100644
--- a/accord-core/src/main/java/accord/primitives/Ballot.java
+++ b/accord-core/src/main/java/accord/primitives/Ballot.java
@@ -54,6 +54,7 @@ public class Ballot extends Timestamp
         super(msb, lsb, node);
     }
 
+    @Override
     public Ballot merge(Timestamp that)
     {
         return merge(this, that, Ballot::fromBits);
diff --git a/accord-core/src/main/java/accord/primitives/Deps.java b/accord-core/src/main/java/accord/primitives/Deps.java
index f72b33b..5b4a984 100644
--- a/accord-core/src/main/java/accord/primitives/Deps.java
+++ b/accord-core/src/main/java/accord/primitives/Deps.java
@@ -18,1311 +18,223 @@
 
 package accord.primitives;
 
-import java.util.*;
-import java.util.function.BiConsumer;
-import java.util.function.Consumer;
-import java.util.function.Function;
-import java.util.function.Predicate;
-
-import java.util.stream.Collectors;
-
 import accord.api.Key;
-import accord.utils.ArrayBuffers;
-import accord.api.RoutingKey;
-import accord.utils.SortedArrays;
 import accord.utils.Invariants;
 
-import static accord.utils.ArrayBuffers.*;
-import static accord.utils.SortedArrays.*;
-import static accord.utils.SortedArrays.Search.FAST;
+import java.util.AbstractList;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.function.Consumer;
+import java.util.function.Function;
+import java.util.function.Predicate;
 
 /**
- * A collection of dependencies for a transaction, organised by the key the dependency is adopted via.
- * An inverse map from TxnId to Key may also be constructed and stored in this collection.
+ * A collection of transaction dependencies, keyed by the key or range on which they were adopted
  */
-// TODO (desired, consider): switch to RoutingKey? Would mean adopting execution dependencies less precisely, but saving ser/deser of large keys
-public class Deps implements Iterable<Map.Entry<Key, TxnId>>
+public class Deps
 {
-    private static final boolean DEBUG_CHECKS = true;
-
-    private static final TxnId[] NO_TXNIDS = new TxnId[0];
-    private static final int[] NO_INTS = new int[0];
-    public static final Deps NONE = new Deps(Keys.EMPTY, NO_TXNIDS, NO_INTS);
+    public static final Deps NONE = new Deps(KeyDeps.NONE, RangeDeps.NONE);
 
-    public static class SerializerSupport
+    public static Builder builder()
     {
-        private SerializerSupport() {}
-
-        public static int keyToTxnIdCount(Deps deps)
-        {
-            return deps.keyToTxnId.length;
-        }
-
-        public static int keyToTxnId(Deps deps, int idx)
-        {
-            return deps.keyToTxnId[idx];
-        }
-
-        public static Deps create(Keys keys, TxnId[] txnIds, int[] keyToTxnId)
-        {
-            return new Deps(keys, txnIds, keyToTxnId);
-        }
-    }
-
-    public static Deps none(Keys keys)
-    {
-        int[] keysToTxnId = new int[keys.size()];
-        Arrays.fill(keysToTxnId, keys.size());
-        return new Deps(keys, NO_TXNIDS, keysToTxnId);
-    }
-
-    /**
-     * Expects Command to be provided in TxnId order
-     */
-    public static OrderedBuilder orderedBuilder(boolean hasOrderedTxnId)
-    {
-        return new OrderedBuilder(hasOrderedTxnId);
+        return new Builder();
     }
 
     // TODO (expected, efficiency): cache this object per thread
-    public static abstract class AbstractOrderedBuilder<T extends Deps> implements AutoCloseable
+    public static abstract class AbstractBuilder<T extends Deps> implements AutoCloseable
     {
-        final ObjectBuffers<TxnId> cachedTxnIds = cachedTxnIds();
-        final ObjectBuffers<Key> cachedKeys = cachedKeys();
-        final IntBuffers cachedInts = cachedInts();
-
-        final boolean hasOrderedTxnId;
-        Key[] keys;
-        int[] keyLimits;
-        // txnId -> Offset
-        TxnId[] keyToTxnId;
-        int keyCount;
-        int keyOffset;
-        int totalCount;
-
-        public AbstractOrderedBuilder(boolean hasOrderedTxnId)
-        {
-            this.keys = cachedKeys.get(16);
-            this.keyLimits = cachedInts.getInts(keys.length);
-            this.hasOrderedTxnId = hasOrderedTxnId;
-            this.keyToTxnId = cachedTxnIds.get(16);
-        }
-
-        public boolean isEmpty()
-        {
-            return totalCount() == 0;
-        }
-
-        private int totalCount()
-        {
-            return totalCount;
-        }
+        final KeyDeps.Builder keyBuilder;
+        RangeDeps.Builder rangeBuilder;
 
-        public void nextKey(Key key)
+        AbstractBuilder()
         {
-            if (keyCount > 0 && keys[keyCount - 1].compareTo(key) >= 0)
-            {
-                throw new IllegalArgumentException("Key " + key + " has already been visited or was provided out of order ("
-                        + Arrays.toString(Arrays.copyOf(keys, keyCount)) + ")");
-            }
-
-            finishKey();
-
-            if (keyCount == keys.length)
-            {
-                Key[] newKeys = cachedKeys.get(keyCount * 2);
-                System.arraycopy(keys, 0, newKeys, 0, keyCount);
-                cachedKeys.forceDiscard(keys, keyCount);
-                keys = newKeys;
-                int[] newKeyLimits = cachedInts.getInts(keyCount * 2);
-                System.arraycopy(keyLimits, 0, newKeyLimits, 0, keyCount);
-                cachedInts.forceDiscard(keyLimits, keyCount);
-                keyLimits = newKeyLimits;
-            }
-            keys[keyCount++] = key;
+            this.keyBuilder = KeyDeps.builder();
         }
 
-        private void finishKey()
+        public AbstractBuilder<T> add(Seekable keyOrRange, TxnId txnId)
         {
-            if (totalCount == keyOffset && keyCount > 0)
-                --keyCount; // remove this key; no data
-
-            if (keyCount == 0)
-                return;
-
-            if (totalCount != keyOffset && !hasOrderedTxnId)
+            switch (keyOrRange.domain())
             {
-                // TODO (low priority, efficiency): this allocates a significant amount of memory: would be preferable to be able to sort using a pre-defined scratch buffer
-                Arrays.sort(keyToTxnId, keyOffset, totalCount);
-                for (int i = keyOffset + 1 ; i < totalCount ; ++i)
-                {
-                    if (keyToTxnId[i - 1].equals(keyToTxnId[i]))
-                        throw new IllegalArgumentException("TxnId for " + keys[keyCount - 1] + " are not unique: " + Arrays.asList(keyToTxnId).subList(keyOffset, totalCount));
-                }
+                default: throw new AssertionError();
+                case Key:
+                    keyBuilder.add(keyOrRange.asKey(), txnId);
+                    break;
+                case Range:
+                    if (rangeBuilder == null)
+                        rangeBuilder = RangeDeps.builder();
+                    rangeBuilder.add(keyOrRange.asRange(), txnId);
+                    break;
             }
-
-            keyLimits[keyCount - 1] = totalCount;
-            keyOffset = totalCount;
-        }
-
-        public void add(Key key, TxnId txnId)
-        {
-            if (keyCount == 0 || !keys[keyCount - 1].equals(key))
-                nextKey(key);
-            add(txnId);
-        }
-
-        /**
-         * Add this command as a dependency for each intersecting key
-         */
-        public void add(TxnId txnId)
-        {
-            if (hasOrderedTxnId && totalCount > keyOffset && keyToTxnId[totalCount - 1].compareTo(txnId) >= 0)
-                throw new IllegalArgumentException("TxnId provided out of order");
-
-            if (totalCount >= keyToTxnId.length)
-            {
-                TxnId[] newTxnIds = cachedTxnIds.get(keyToTxnId.length * 2);
-                System.arraycopy(keyToTxnId, 0, newTxnIds, 0, totalCount);
-                cachedTxnIds.forceDiscard(keyToTxnId, totalCount);
-                keyToTxnId = newTxnIds;
-            }
-
-            keyToTxnId[totalCount++] = txnId;
-        }
-
-        public T build()
-        {
-            if (totalCount == 0)
-                return build(Keys.EMPTY, NO_TXNIDS, NO_INTS);
-
-            finishKey();
-
-            TxnId[] uniqueTxnId = cachedTxnIds.get(totalCount);
-            System.arraycopy(keyToTxnId, 0, uniqueTxnId, 0, totalCount);
-            Arrays.sort(uniqueTxnId, 0, totalCount);
-            int txnIdCount = 1;
-            for (int i = 1 ; i < totalCount ; ++i)
-            {
-                if (!uniqueTxnId[txnIdCount - 1].equals(uniqueTxnId[i]))
-                    uniqueTxnId[txnIdCount++] = uniqueTxnId[i];
-            }
-
-            TxnId[] txnIds = cachedTxnIds.complete(uniqueTxnId, txnIdCount);
-            cachedTxnIds.discard(uniqueTxnId, totalCount);
-
-            int[] result = new int[keyCount + totalCount];
-            int offset = keyCount;
-            for (int k = 0 ; k < keyCount ; ++k)
-            {
-                result[k] = keyCount + keyLimits[k];
-                int from = k == 0 ? 0 : keyLimits[k - 1];
-                int to = keyLimits[k];
-                offset = (int)SortedArrays.foldlIntersection(txnIds, 0, txnIdCount, keyToTxnId, from, to, (key, p, v, li, ri) -> {
-                    result[(int)v] = li;
-                    return v + 1;
-                }, keyCount, offset, -1);
-            }
-
-            return build(Keys.ofSortedUnchecked(cachedKeys.complete(keys, keyCount)), txnIds, result);
+            return this;
         }
 
-        abstract T build(Keys keys, TxnId[] txnIds, int[] keyToTxnId);
+        public abstract T build();
 
         @Override
         public void close()
         {
-            cachedKeys.discard(keys, keyCount);
-            cachedInts.forceDiscard(keyLimits, keyCount);
-            cachedTxnIds.forceDiscard(keyToTxnId, totalCount);
-        }
-    }
-
-    public static class OrderedBuilder extends AbstractOrderedBuilder<Deps>
-    {
-        public OrderedBuilder(boolean hasOrderedTxnId)
-        {
-            super(hasOrderedTxnId);
-        }
-
-        @Override
-        Deps build(Keys keys, TxnId[] txnIds, int[] keysToTxnIds)
-        {
-            return new Deps(keys, txnIds, keysToTxnIds);
+            keyBuilder.close();
+            if (rangeBuilder != null)
+                rangeBuilder.close();
         }
     }
 
-    /**
-     * An object for managing a sequence of efficient linear merges Deps objects.
-     * Its primary purpose is to manage input and output buffers, so that we reuse output buffers
-     * as input to the next merge, and if any input is a superset of the other inputs that this input
-     * is returned unmodified.
-     *
-     * This is achieved by using PassThroughXBuffers so that the result buffers (and their sizes) are returned
-     * unmodified, and the buffers are cached as far as possible. In general, the buffers should be taken
-     * out of pre-existing caches, but if the buffers are too large then we cache any additional buffers we
-     * allocate for the duration of the merge.
-     */
-    private static class LinearMerger extends PassThroughObjectAndIntBuffers<TxnId> implements DepsConstructor<Key, TxnId, Object>
+    public static class Builder extends AbstractBuilder<Deps>
     {
-        final PassThroughObjectBuffers<Key> keyBuffers;
-        Key[] bufKeys;
-        TxnId[] bufTxnIds;
-        int[] buf = null;
-        int bufKeysLength, bufTxnIdsLength = 0, bufLength = 0;
-        Deps from = null;
-
-        LinearMerger()
+        public Builder()
         {
-            super(cachedTxnIds(), cachedInts());
-            keyBuffers = new PassThroughObjectBuffers<>(cachedKeys());
+            super();
         }
 
         @Override
-        public Object construct(Key[] keys, int keysLength, TxnId[] txnIds, int txnIdsLength, int[] out, int outLength)
-        {
-            if (from == null)
-            {
-                // if our input buffers were themselves buffers, we want to discard them unless they have been returned back to us
-                discard(keys, txnIds, out);
-            }
-            else if (buf != out)
-            {
-                // the output is not equal to a prior input
-                from = null;
-            }
-
-            if (from == null)
-            {
-                bufKeys = keys;
-                bufKeysLength = keysLength;
-                bufTxnIds = txnIds;
-                bufTxnIdsLength = txnIdsLength;
-                buf = out;
-                bufLength = outLength;
-            }
-            else
-            {
-                Invariants.checkState(keys == bufKeys && keysLength == bufKeysLength);
-                Invariants.checkState(txnIds == bufTxnIds && txnIdsLength == bufTxnIdsLength);
-                Invariants.checkState(outLength == bufLength);
-            }
-            return null;
-        }
-
-        void update(Deps deps)
-        {
-            if (buf == null)
-            {
-                bufKeys = deps.keys.keys;
-                bufKeysLength = deps.keys.keys.length;
-                bufTxnIds = deps.txnIds;
-                bufTxnIdsLength = deps.txnIds.length;
-                buf = deps.keyToTxnId;
-                bufLength = deps.keyToTxnId.length;
-                from = deps;
-                return;
-            }
-
-            linearUnion(
-                    bufKeys, bufKeysLength, bufTxnIds, bufTxnIdsLength, buf, bufLength,
-                    deps.keys.keys, deps.keys.keys.length, deps.txnIds, deps.txnIds.length, deps.keyToTxnId, deps.keyToTxnId.length,
-                    keyBuffers, this, this, this
-            );
-            if (buf == deps.keyToTxnId)
-            {
-                Invariants.checkState(deps.keys.keys == bufKeys && deps.keys.keys.length == bufKeysLength);
-                Invariants.checkState(deps.txnIds == bufTxnIds && deps.txnIds.length == bufTxnIdsLength);
-                Invariants.checkState(deps.keyToTxnId.length == bufLength);
-                from = deps;
-            }
-        }
-
-        Deps get()
-        {
-            if (buf == null)
-                return NONE;
-
-            if (from != null)
-                return from;
-
-            return new Deps(
-                    Keys.ofSortedUnchecked(keyBuffers.realComplete(bufKeys, bufKeysLength)),
-                    realComplete(bufTxnIds, bufTxnIdsLength),
-                    realComplete(buf, bufLength));
-        }
-
-        /**
-         * Free any buffers we no longer need
-         */
-        void discard()
+        public Deps build()
         {
-            if (from == null)
-                discard(null, null, null);
-        }
-
-        /**
-         * Free buffers unless they are equal to the corresponding parameter
-         */
-        void discard(Key[] freeKeysIfNot, TxnId[] freeTxnIdsIfNot, int[] freeBufIfNot)
-        {
-            if (from != null)
-                return;
-
-            if (bufKeys != freeKeysIfNot)
-            {
-                keyBuffers.realDiscard(bufKeys, bufKeysLength);
-                bufKeys = null;
-            }
-            if (bufTxnIds != freeTxnIdsIfNot)
-            {
-                realDiscard(bufTxnIds, bufTxnIdsLength);
-                bufTxnIds = null;
-            }
-            if (buf != freeBufIfNot)
-            {
-                realDiscard(buf, bufLength);
-                buf = null;
-            }
+            return new Deps(keyBuilder.build(), rangeBuilder == null ? RangeDeps.NONE : rangeBuilder.build());
         }
     }
 
-    public static <T> Deps merge(List<T> merge, Function<T, Deps> getter)
-    {
-        LinearMerger linearMerger = new LinearMerger();
-        try
-        {
-            int mergeIndex = 0, mergeSize = merge.size();
-            while (mergeIndex < mergeSize)
-            {
-                Deps deps = getter.apply(merge.get(mergeIndex++));
-                if (deps == null || deps.isEmpty())
-                    continue;
-
-                linearMerger.update(deps);
-            }
-
-            return linearMerger.get();
-        }
-        finally
-        {
-            linearMerger.discard();
-        }
-    }
-
-    final Keys keys; // unique Keys
-    final TxnId[] txnIds; // unique TxnId TODO (low priority, efficiency): this could be a BTree?
-
-    /**
-     * This represents a map of {@code Key -> [TxnId] } where each TxnId is actually a pointer into the txnIds array.
-     * The beginning of the array (the first keys.size() entries) are offsets into this array.
-     * <p/>
-     * Example:
-     * <p/>
-     * {@code
-     *   int keyIdx = keys.indexOf(key);
-     *   int startOfTxnOffset = keyIdx == 0 ? keys.size() : keyToTxnId[keyIdx - 1];
-     *   int endOfTxnOffset = keyToTxnId[keyIdx];
-     *   for (int i = startOfTxnOffset; i < endOfTxnOffset; i++)
-     *   {
-     *       TxnId id = txnIds[keyToTxnId[i]]
-     *       ...
-     *   }
-     * }
-     */
-    final int[] keyToTxnId; // Key -> [TxnId]
-    // Lazy loaded in ensureTxnIdToKey()
-    int[] txnIdToKey; // TxnId -> [Key]
+    public final KeyDeps keyDeps;
+    public final RangeDeps rangeDeps;
 
-    Deps(Keys keys, TxnId[] txnIds, int[] keyToTxnId)
+    public Deps(KeyDeps keyDeps, RangeDeps rangeDeps)
     {
-        this.keys = keys;
-        this.txnIds = txnIds;
-        this.keyToTxnId = keyToTxnId;
-        if (!(keys.isEmpty() || keyToTxnId[keys.size() - 1] == keyToTxnId.length))
-            throw new IllegalArgumentException(String.format("Last key (%s) in keyToTxnId does not point (%d) to the end of the array (%d);\nkeyToTxnId=%s", keys.get(keys.size() - 1), keyToTxnId[keys.size() - 1], keyToTxnId.length, Arrays.toString(keyToTxnId)));
-        if (DEBUG_CHECKS)
-            checkValid();
+        this.keyDeps = keyDeps;
+        this.rangeDeps = rangeDeps;
     }
 
-    public PartialDeps slice(Ranges ranges)
-    {
-        if (isEmpty())
-            return new PartialDeps(ranges, keys, txnIds, keyToTxnId);
-
-        Keys select = keys.slice(ranges);
-
-        if (select.isEmpty())
-            return new PartialDeps(ranges, Keys.EMPTY, NO_TXNIDS, NO_INTS);
-
-        if (select.size() == keys.size())
-            return new PartialDeps(ranges, keys, txnIds, keyToTxnId);
-
-        int i = 0;
-        int offset = select.size();
-        for (int j = 0 ; j < select.size() ; ++j)
-        {
-            int findi = keys.findNext(i, select.get(j), FAST);
-            if (findi < 0)
-                continue;
-
-            i = findi;
-            offset += keyToTxnId[i] - (i == 0 ? keys.size() : keyToTxnId[i - 1]);
-        }
-
-        int[] src = keyToTxnId;
-        int[] trg = new int[offset];
-
-        i = 0;
-        offset = select.size();
-        for (int j = 0 ; j < select.size() ; ++j)
-        {
-            int findi = keys.findNext(i, select.get(j), FAST);
-            if (findi >= 0)
-            {
-                i = findi;
-                int start = i == 0 ? keys.size() : src[i - 1];
-                int count = src[i] - start;
-                System.arraycopy(src, start, trg, offset, count);
-                offset += count;
-            }
-            trg[j] = offset;
-        }
-
-        TxnId[] txnIds = trimUnusedTxnId(select, this.txnIds, trg);
-        return new PartialDeps(ranges, select, txnIds, trg);
-    }
-
-    /**
-     * Returns the set of {@link TxnId}s that are referenced by {@code keysToTxnId}, and <strong>updates</strong>
-     * {@code keysToTxnId} to point to the new offsets in the returned set.
-     * @param keys object referenced by {@code keysToTxnId} index
-     * @param txnIds to trim to the seen {@link TxnId}s
-     * @param keysToTxnId to use as reference for trimming, this index will be updated to reflect the trimmed offsets.
-     * @return smallest set of {@link TxnId} seen in {@code keysToTxnId}
-     */
-    private static TxnId[] trimUnusedTxnId(Keys keys, TxnId[] txnIds, int[] keysToTxnId)
+    public boolean contains(TxnId txnId)
     {
-        IntBuffers cache = ArrayBuffers.cachedInts();
-        // we use remapTxnId twice:
-        //  - first we use the end to store a bitmap of those TxnId we are actually using
-        //  - then we use it to store the remap index (incrementally replacing the bitmap)
-        int bitMapOffset = txnIds.length + 1 - (txnIds.length+31)/32;
-        int[] remapTxnId = cache.getInts(txnIds.length + 1);
-        try
-        {
-            Arrays.fill(remapTxnId, bitMapOffset, txnIds.length + 1, 0);
-            for (int i = keys.size() ; i < keysToTxnId.length ; ++i)
-                setBit(remapTxnId, bitMapOffset, keysToTxnId[i]);
-
-            int offset = 0;
-            for (int i = 0 ; i < txnIds.length ; ++i)
-            {
-                if (hasSetBit(remapTxnId, bitMapOffset, i)) remapTxnId[i] = offset++;
-                else remapTxnId[i] = -1;
-            }
-
-            TxnId[] result = txnIds;
-            if (offset < txnIds.length)
-            {
-                result = new TxnId[offset];
-                for (int i = 0 ; i < txnIds.length ; ++i)
-                {
-                    if (remapTxnId[i] >= 0)
-                        result[remapTxnId[i]] = txnIds[i];
-                }
-                // Update keysToTxnId to point to the new remapped TxnId offsets
-                for (int i = keys.size() ; i < keysToTxnId.length ; ++i)
-                    keysToTxnId[i] = remapTxnId[keysToTxnId[i]];
-            }
-
-            return result;
-        }
-        finally
-        {
-            cache.forceDiscard(remapTxnId, txnIds.length);
-        }
+        return keyDeps.contains(txnId) || rangeDeps.contains(txnId);
     }
 
     public Deps with(Deps that)
     {
-        if (isEmpty() || that.isEmpty())
-            return isEmpty() ? that : this;
-
-        return linearUnion(
-                this.keys.keys, this.keys.keys.length, this.txnIds, this.txnIds.length, this.keyToTxnId, this.keyToTxnId.length,
-                that.keys.keys, that.keys.keys.length, that.txnIds, that.txnIds.length, that.keyToTxnId, that.keyToTxnId.length,
-                cachedKeys(), cachedTxnIds(), cachedInts(),
-                (keys, keysLength, txnIds, txnIdsLength, out, outLength) ->
-                        new Deps(Keys.ofSortedUnchecked(cachedKeys().complete(keys, keysLength)),
-                                cachedTxnIds().complete(txnIds, txnIdsLength),
-                                cachedInts().complete(out, outLength))
-                );
-    }
-
-    /**
-     * Turn a set of key, value and mapping buffers into a merge result;
-     * K and V are either Key and TxnId, or vice versa, depending on which mapping direction was present
-     */
-    interface DepsConstructor<K, V, T>
-    {
-        T construct(K[] keys, int keysLength, V[] values, int valuesLength, int[] out, int outLength);
-    }
-
-    private static boolean arraysEqual(int[] left, int[] right, int length)
-    {
-        if (left.length < length || right.length < length)
-            return false;
-
-        for (int i=0; i<length; i++)
-            if (left[i] !=right[i])
-                return false;
-
-        return true;
-    }
-
-    private static <T> boolean arraysEqual(T[] left, T[] right, int length)
-    {
-        if (left.length < length || right.length < length)
-            return false;
-
-        for (int i=0; i<length; i++)
-            if (!Objects.equals(left[i], right[i]))
-                return false;
-
-        return true;
-    }
-
-    // TODO (low priority, efficiency): this method supports merging keyToTxnId OR txnIdToKey; we can perhaps save time
-    //  and effort when constructing Deps on remote hosts by only producing txnIdToKey with OrderedCollector and serializing
-    //  only this, and merging on the recipient before inverting, so that we only have to invert the final assembled deps
-    private static <K extends Comparable<? super K>, V extends Comparable<? super V>, T>
-    T linearUnion(K[] leftKeys, int leftKeysLength, V[] leftValues, int leftValuesLength, int[] left, int leftLength,
-                  K[] rightKeys, int rightKeysLength, V[] rightValues, int rightValuesLength, int[] right, int rightLength,
-                  ObjectBuffers<K> keyBuffers, ObjectBuffers<V> valueBuffers, IntBuffers intBuffers, DepsConstructor<K, V, T> constructor)
-    {
-        K[] outKeys = null;
-        V[] outValues = null;
-        int[] remapLeft = null, remapRight = null, out = null;
-        int outLength = 0, outKeysLength = 0, outTxnIdsLength = 0;
-
-        try
-        {
-            outKeys = SortedArrays.linearUnion(leftKeys, leftKeysLength, rightKeys, rightKeysLength, keyBuffers);
-            outKeysLength = keyBuffers.lengthOfLast(outKeys);
-            outValues = SortedArrays.linearUnion(leftValues, leftValuesLength, rightValues, rightValuesLength, valueBuffers);
-            outTxnIdsLength = valueBuffers.lengthOfLast(outValues);
-
-            remapLeft = remapToSuperset(leftValues, leftValuesLength, outValues, outTxnIdsLength, intBuffers);
-            remapRight = remapToSuperset(rightValues, rightValuesLength, outValues, outTxnIdsLength, intBuffers);
-
-            if (remapLeft == null && remapRight == null && leftLength == rightLength && leftKeysLength == rightKeysLength
-                    && arraysEqual(left, right, rightLength)
-                    && arraysEqual(leftKeys, rightKeys, rightKeysLength)
-                )
-            {
-                return constructor.construct(leftKeys, leftKeysLength, leftValues, leftValuesLength, left, leftLength);
-            }
-
-            int lk = 0, rk = 0, ok = 0, l = leftKeysLength, r = rightKeysLength;
-            outLength = outKeysLength;
-
-            if (remapLeft == null && outKeys == leftKeys)
-            {
-                // "this" knows all the TxnId and Keys already, but do both agree on what Keys map to TxnIds?
-                noOp: while (lk < leftKeysLength && rk < rightKeysLength)
-                {
-                    int ck = leftKeys[lk].compareTo(rightKeys[rk]);
-                    if (ck < 0)
-                    {
-                        // "this" knows of a key not present in "that"
-                        outLength += left[lk] - l; // logically append the key's TxnIds to the size
-                        l = left[lk];
-                        assert outLength == l && ok == lk && left[ok] == outLength;
-                        ok++;
-                        lk++;
-                    }
-                    else if (ck > 0)
-                    {
-                        // if this happened there is a bug with keys.union or keys are not actually sorted
-                        throwUnexpectedMissingKeyException(leftKeys, lk, leftKeysLength, rightKeys, rk, rightKeysLength, true);
-                    }
-                    else
-                    {
-                        // both "this" and "that" know of the key
-                        while (l < left[lk] && r < right[rk])
-                        {
-                            int nextLeft = left[l];
-                            int nextRight = remap(right[r], remapRight);
-
-                            if (nextLeft < nextRight)
-                            {
-                                // "this" knows of the txn that "that" didn't
-                                outLength++;
-                                l++;
-                            }
-                            else if (nextRight < nextLeft)
-                            {
-                                out = copy(left, outLength, leftLength + rightLength - r, intBuffers);
-                                break noOp;
-                            }
-                            else
-                            {
-                                outLength++;
-                                l++;
-                                r++;
-                            }
-                        }
-
-                        if (l < left[lk])
-                        {
-                            outLength += left[lk] - l;
-                            l = left[lk];
-                        }
-                        else if (r < right[rk])
-                        {
-                            // "that" thinks a key includes a TxnId as a dependency but "this" doesn't, need to include this knowledge
-                            out = copy(left, outLength, leftLength + rightLength - r, intBuffers);
-                            break;
-                        }
-
-                        assert outLength == l && ok == lk && left[ok] == outLength;
-                        ok++;
-                        rk++;
-                        lk++;
-                    }
-                }
-
-                if (out == null)
-                    return constructor.construct(leftKeys, leftKeysLength, leftValues, leftValuesLength, left, leftLength);
-            }
-            else if (remapRight == null && outKeys == rightKeys)
-            {
-                // "that" knows all the TxnId and keys already, but "this" does not
-                noOp: while (lk < leftKeysLength && rk < rightKeysLength)
-                {
-                    int ck = leftKeys[lk].compareTo(rightKeys[rk]);
-                    if (ck < 0)
-                    {
-                        // if this happened there is a bug with keys.union or keys are not actually sorted
-                        throwUnexpectedMissingKeyException(leftKeys, lk, leftKeysLength, rightKeys, rk, rightKeysLength, false);
-                    }
-                    else if (ck > 0)
-                    {
-                        outLength += right[rk] - r;
-                        r = right[rk];
-                        assert outLength == r && ok == rk && right[ok] == outLength;
-                        ok++;
-                        rk++;
-                    }
-                    else
-                    {
-                        // both "this" and "that" know of the key
-                        while (l < left[lk] && r < right[rk])
-                        {
-                            int nextLeft = remap(left[l], remapLeft);
-                            int nextRight = right[r];
-
-                            if (nextLeft < nextRight)
-                            {
-                                // "this" thinks a TxnID depends on Key but "that" doesn't, need to include this knowledge
-                                out = copy(right, outLength, rightLength + leftLength - l, intBuffers);
-                                break noOp;
-                            }
-                            else if (nextRight < nextLeft)
-                            {
-                                // "that" knows of the txn that "this" didn't
-                                outLength++;
-                                r++;
-                            }
-                            else
-                            {
-                                outLength++;
-                                l++;
-                                r++;
-                            }
-                        }
-
-                        if (l < left[lk])
-                        {
-                            out = copy(right, outLength, rightLength + leftLength - l, intBuffers);
-                            break;
-                        }
-                        else if (r < right[rk])
-                        {
-                            outLength += right[rk] - r;
-                            r = right[rk];
-                        }
-
-                        assert outLength == r && ok == rk && right[ok] == outLength;
-                        ok++;
-                        rk++;
-                        lk++;
-                    }
-                }
-
-                if (out == null)
-                    return constructor.construct(rightKeys, rightKeysLength, rightValues, rightValuesLength, right, rightLength);
-            }
-            else
-            {
-                out = intBuffers.getInts(leftLength + rightLength);
-            }
-
-            while (lk < leftKeysLength && rk < rightKeysLength)
-            {
-                int ck = leftKeys[lk].compareTo(rightKeys[rk]);
-                if (ck < 0)
-                {
-                    while (l < left[lk])
-                        out[outLength++] = remap(left[l++], remapLeft);
-                    out[ok++] = outLength;
-                    lk++;
-                }
-                else if (ck > 0)
-                {
-                    while (r < right[rk])
-                        out[outLength++] = remap(right[r++], remapRight);
-                    out[ok++] = outLength;
-                    rk++;
-                }
-                else
-                {
-                    while (l < left[lk] && r < right[rk])
-                    {
-                        int nextLeft = remap(left[l], remapLeft);
-                        int nextRight = remap(right[r], remapRight);
-
-                        if (nextLeft <= nextRight)
-                        {
-                            out[outLength++] = nextLeft;
-                            l += 1;
-                            r += nextLeft == nextRight ? 1 : 0;
-                        }
-                        else
-                        {
-                            out[outLength++] = nextRight;
-                            ++r;
-                        }
-                    }
-
-                    while (l < left[lk])
-                        out[outLength++] = remap(left[l++], remapLeft);
-
-                    while (r < right[rk])
-                        out[outLength++] = remap(right[r++], remapRight);
-
-                    out[ok++] = outLength;
-                    rk++;
-                    lk++;
-                }
-            }
-
-            while (lk < leftKeysLength)
-            {
-                while (l < left[lk])
-                    out[outLength++] = remap(left[l++], remapLeft);
-                out[ok++] = outLength;
-                lk++;
-            }
-
-            while (rk < rightKeysLength)
-            {
-                while (r < right[rk])
-                    out[outLength++] = remap(right[r++], remapRight);
-                out[ok++] = outLength;
-                rk++;
-            }
-
-            return constructor.construct(outKeys, outKeysLength, outValues, outTxnIdsLength, out, outLength);
-        }
-        finally
-        {
-            if (outKeys != null)
-                keyBuffers.discard(outKeys, outKeysLength);
-            if (outValues != null)
-                valueBuffers.discard(outValues, outTxnIdsLength);
-            if (out != null)
-                intBuffers.discard(out, outLength);
-            if (remapLeft != null)
-                intBuffers.forceDiscard(remapLeft, leftValuesLength);
-            if (remapRight != null)
-                intBuffers.forceDiscard(remapRight, rightValuesLength);
-        }
-    }
-
-    private static <A> void throwUnexpectedMissingKeyException(A[] leftKeys, int leftKeyIndex, int leftKeyLength, A[] rightKeys, int rightKeyIndex, int rightKeyLength, boolean isMissingLeft)
-    {
-        StringBuilder sb = new StringBuilder();
-        String missing = isMissingLeft ? "left" : "right";
-        String extra = isMissingLeft ? "right" : "left";
-        sb.append(missing).append(" knows all keys, yet ").append(extra).append(" knew of an extra key at indexes left[")
-                .append(leftKeyIndex).append("] = ").append(leftKeys[leftKeyIndex])
-                .append(", right[").append(rightKeyIndex).append("] = ").append(rightKeys[rightKeyIndex]).append("\n");
-        sb.append("leftKeys = ").append(Arrays.stream(leftKeys, 0, leftKeyLength).map(Object::toString).collect(Collectors.joining())).append('\n');
-        sb.append("rightKeys = ").append(Arrays.stream(rightKeys, 0, rightKeyLength).map(Object::toString).collect(Collectors.joining())).append('\n');
-        throw new IllegalStateException(sb.toString());
-    }
-
-    private static int[] copy(int[] src, int to, int length, IntBuffers bufferManager)
-    {
-        if (length == 0)
-            return NO_INTS;
-
-        int[] result = bufferManager.getInts(length);
-        if (result.length < length)
-            throw new IllegalStateException();
-        System.arraycopy(src, 0, result, 0, to);
-        return result;
+        return new Deps(this.keyDeps.with(that.keyDeps), this.rangeDeps.with(that.rangeDeps));
     }
 
     public Deps without(Predicate<TxnId> remove)
     {
-        if (isEmpty())
-            return this;
-
-        IntBuffers cache = ArrayBuffers.cachedInts();
-        TxnId[] oldTxnIds = txnIds;
-        int[] oldKeyToTxnId = keyToTxnId;
-        int[] remapTxnIds = cache.getInts(oldTxnIds.length);
-        int[] newKeyToTxnId = null;
-        TxnId[] newTxnIds;
-        int o = 0;
-        try
-        {
-            int count = 0;
-            for (int i = 0 ; i < oldTxnIds.length ; ++i)
-            {
-                if (remove.test(oldTxnIds[i])) remapTxnIds[i] = -1;
-                else remapTxnIds[i] = count++;
-            }
-
-            if (count == oldTxnIds.length)
-                return this;
-
-            if (count == 0)
-                return NONE;
-
-            newTxnIds = new TxnId[count];
-            for (int i = 0 ; i < oldTxnIds.length ; ++i)
-            {
-                if (remapTxnIds[i] >= 0)
-                    newTxnIds[remapTxnIds[i]] = oldTxnIds[i];
-            }
-
-            newKeyToTxnId = cache.getInts(oldKeyToTxnId.length);
-            int k = 0, i = keys.size();
-            o = i;
-            while (i < oldKeyToTxnId.length)
-            {
-                while (oldKeyToTxnId[k] == i)
-                    newKeyToTxnId[k++] = o;
-
-                int remapped = remapTxnIds[oldKeyToTxnId[i]];
-                if (remapped >= 0)
-                    newKeyToTxnId[o++] = remapped;
-                ++i;
-            }
-
-            while (k < keys.size())
-                newKeyToTxnId[k++] = o;
-        }
-        catch (Throwable t)
-        {
-            cache.forceDiscard(newKeyToTxnId, o);
-            throw t;
-        }
-        finally
-        {
-            cache.forceDiscard(remapTxnIds, oldTxnIds.length);
-        }
-
-        newKeyToTxnId = cache.completeAndDiscard(newKeyToTxnId, o);
-        return new Deps(keys, newTxnIds, newKeyToTxnId);
+        return new Deps(keyDeps.without(remove), rangeDeps.without(remove));
     }
 
-    public boolean contains(TxnId txnId)
+    public PartialDeps slice(Ranges covering)
     {
-        return Arrays.binarySearch(txnIds, txnId) >= 0;
+        return new PartialDeps(covering, keyDeps.slice(covering), rangeDeps.slice(covering));
     }
 
-    // return true iff we map any keys to any txnId
-    // if the mapping is empty we return false, whether or not we have any keys or txnId by themselves
     public boolean isEmpty()
     {
-        return keyToTxnId.length == keys.size();
-    }
-
-    public Keys someKeys(TxnId txnId)
-    {
-        int txnIdIndex = Arrays.binarySearch(txnIds, txnId);
-        if (txnIdIndex < 0)
-            return Keys.EMPTY;
-
-        ensureTxnIdToKey();
-
-        int start = txnIdIndex == 0 ? txnIds.length : txnIdToKey[txnIdIndex - 1];
-        int end = txnIdToKey[txnIdIndex];
-        if (start == end)
-            return Keys.EMPTY;
-
-        Key[] result = new Key[end - start];
-        for (int i = start ; i < end ; ++i)
-            result[i - start] = keys.get(txnIdToKey[i]);
-        return Keys.of(result);
-    }
-
-    public Unseekables<RoutingKey, ?> someRoutables(TxnId txnId)
-    {
-        return toUnseekables(txnId, array -> {
-            if (array.length == 0)
-                throw new IllegalStateException("Cannot create a RouteFragment without any keys");
-            return new RoutingKeys(array);
-        });
-    }
-
-    private <R> R toUnseekables(TxnId txnId, Function<RoutingKey[], R> constructor)
-    {
-        int txnIdIndex = Arrays.binarySearch(txnIds, txnId);
-        if (txnIdIndex < 0)
-            constructor.apply(RoutingKeys.EMPTY.keys);
-
-        ensureTxnIdToKey();
-
-        int start = txnIdIndex == 0 ? txnIds.length : txnIdToKey[txnIdIndex - 1];
-        int end = txnIdToKey[txnIdIndex];
-        RoutingKey[] result = new RoutingKey[end - start];
-        if (start == end)
-            constructor.apply(RoutingKeys.EMPTY.keys);
-
-        result[0] = keys.get(txnIdToKey[start]).toUnseekable();
-        int resultCount = 1;
-        for (int i = start + 1 ; i < end ; ++i)
-        {
-            RoutingKey next = keys.get(txnIdToKey[i]).toUnseekable();
-            if (!next.equals(result[resultCount - 1]))
-                result[resultCount++] = next;
-        }
-
-        if (resultCount < result.length)
-            result = Arrays.copyOf(result, resultCount);
-        return constructor.apply(result);
-    }
-
-    void ensureTxnIdToKey()
-    {
-        if (txnIdToKey != null)
-            return;
-
-        txnIdToKey = invert(keyToTxnId, keyToTxnId.length, keys.size(), txnIds.length);
-    }
-
-    private static int[] invert(int[] src, int srcLength, int srcKeyCount, int trgKeyCount)
-    {
-        int[] trg = new int[trgKeyCount + srcLength - srcKeyCount];
-
-        // first pass, count number of txnId per key
-        for (int i = srcKeyCount ; i < srcLength ; ++i)
-            trg[src[i]]++;
-
-        // turn into offsets (i.e. add txnIds.size() and then sum them)
-        trg[0] += trgKeyCount;
-        for (int i = 1; i < trgKeyCount ; ++i)
-            trg[i] += trg[i - 1];
-
-        // shuffle forwards one, so we have the start index rather than end
-        System.arraycopy(trg, 0, trg, 1, trgKeyCount - 1);
-        trg[0] = trgKeyCount;
-
-        // convert the offsets to end, and set the key at the target positions
-        int k = 0;
-        for (int i = srcKeyCount ; i < srcLength ; ++i)
-        {
-            // if at the end offset, switch to the next key
-            while (i == src[k])
-                ++k;
-
-            // find the next key offset for the TxnId and set the offset to this key
-            trg[trg[src[i]]++] = k;
-        }
-
-        return trg;
-    }
-
-    public void forEachOn(Ranges ranges, Predicate<Key> include, BiConsumer<Key, TxnId> forEach)
-    {
-        Routables.foldl(keys, ranges, (key, value, index) -> {
-            if (!include.test(key))
-                return null;
-
-            for (int t = startOffset(index), end = endOffset(index); t < end ; ++t)
-            {
-                TxnId txnId = txnIds[keyToTxnId[t]];
-                forEach.accept(key, txnId);
-            }
-            return null;
-        }, null);
-    }
-
-    /**
-     * For each {@link TxnId} that references a key within the {@link Ranges}; the {@link TxnId} will be seen exactly once.
-     * @param ranges to match on
-     * @param forEach function to call on each unique {@link TxnId}
-     */
-    public void forEachOn(Ranges ranges, Consumer<TxnId> forEach)
-    {
-        // Find all keys within the ranges, but record existence within an int64 bitset.  Since the bitset is limited
-        // to 64, this search must be called multiple times searching for different TxnIds in txnIds; this also has
-        // the property that forEach is called in TxnId order.
-        //TODO (expected, efficiency): reconsider this, probably not worth trying to save allocations at cost of multiple loop
-        //                             use BitSet, or perhaps extend so we can have no nested allocations when few bits
-        for (int offset = 0 ; offset < txnIds.length ; offset += 64)
-        {
-            long bitset = Routables.foldl(keys, ranges, (key, off, value, keyIndex) -> {
-                int index = startOffset(keyIndex);
-                int end = endOffset(keyIndex);
-                if (off > 0)
-                {
-                    // TODO (low priority, efficiency): interpolation search probably great here
-                    index = Arrays.binarySearch(keyToTxnId, index, end, (int)off);
-                    if (index < 0)
-                        index = -1 - index;
-                }
-
-                while (index < end)
-                {
-                    long next = keyToTxnId[index++] - off;
-                    if (next >= 64)
-                        break;
-                    value |= 1L << next;
-                }
-
-                return value;
-            }, offset, 0, -1L);
-
-            while (bitset != 0)
-            {
-                int i = Long.numberOfTrailingZeros(bitset);
-                TxnId txnId = txnIds[offset + i];
-                forEach.accept(txnId);
-                bitset ^= Long.lowestOneBit(bitset);
-            }
-        }
-    }
-
-    public void forEach(Key key, Consumer<TxnId> forEach)
-    {
-        int keyIndex = keys.indexOf(key);
-        if (keyIndex < 0)
-            return;
-
-        int index = startOffset(keyIndex);
-        int end = endOffset(keyIndex);
-        while (index < end)
-            forEach.accept(txnIds[keyToTxnId[index++]]);
-    }
-
-    public Keys keys()
-    {
-        return keys;
+        return keyDeps.isEmpty() && rangeDeps.isEmpty();
     }
 
     public int txnIdCount()
     {
-        return txnIds.length;
-    }
-
-    public int totalCount()
-    {
-        return keyToTxnId.length - keys.size();
+        return keyDeps.txnIdCount() + rangeDeps.txnIdCount();
     }
 
     public TxnId txnId(int i)
     {
-        return txnIds[i];
+        return i < keyDeps.txnIdCount()
+                ? keyDeps.txnId(i)
+                : rangeDeps.txnId(i - keyDeps.txnIdCount());
     }
 
-    public Collection<TxnId> txnIds()
+    public List<TxnId> txnIds()
     {
-        return Arrays.asList(txnIds);
-    }
-
-    public List<TxnId> txnIds(Key key)
-    {
-        int keyIndex = keys.indexOf(key);
-        if (keyIndex < 0)
-            return Collections.emptyList();
-
-        int start = startOffset(keyIndex);
-        int end = endOffset(keyIndex);
-        int size = end - start;
-
-        return new AbstractList<TxnId>()
-        {
+        final int txnIdCount = txnIdCount();
+        final int keyDepsCount = keyDeps.txnIdCount();
+        return new AbstractList<TxnId>() {
             @Override
             public TxnId get(int index)
             {
-                if (index > end)
-                    throw new IndexOutOfBoundsException();
-                return txnIds[keyToTxnId[start + index]];
+                return index < keyDepsCount
+                        ? keyDeps.txnId(index)
+                        : rangeDeps.txnId(index - keyDepsCount);
             }
 
             @Override
             public int size()
             {
-                return size;
+                return txnIdCount;
             }
         };
     }
 
-    private int startOffset(int keyIndex)
-    {
-        return keyIndex == 0 ? keys.size() : keyToTxnId[keyIndex - 1];
-    }
-
-    private int endOffset(int keyIndex)
+    public List<TxnId> txnIds(Seekable keyOrRange)
     {
-        return keyToTxnId[keyIndex];
-    }
-
-    @Override
-    public Iterator<Map.Entry<Key, TxnId>> iterator()
-    {
-        return new Iterator<Map.Entry<Key, TxnId>>()
+        List<TxnId> keyIds, rangeIds;
+        switch (keyOrRange.domain())
         {
-            int i = keys.size(), k = 0;
-
-            @Override
-            public boolean hasNext()
+            default: throw new AssertionError();
+            case Key:
             {
-                return i < keyToTxnId.length;
+                Key key = keyOrRange.asKey();
+                keyIds = keyDeps.txnIds(key);
+                rangeIds = rangeDeps.txnIds(key);
+                break;
             }
-
-            @Override
-            public Map.Entry<Key, TxnId> next()
+            case Range:
             {
-                Entry result = new Entry(keys.get(k), txnIds[keyToTxnId[i++]]);
-                if (i == keyToTxnId[k])
-                    ++k;
-                return result;
+                Range range = keyOrRange.asRange();
+                keyIds = keyDeps.txnIds(range);
+                rangeIds = rangeDeps.txnIds(range);
             }
-        };
-    }
-
-    @Override
-    public String toString()
-    {
-        return toSimpleString();
-    }
+        }
 
-    public String toSimpleString()
-    {
-        if (keys.isEmpty())
-            return "{}";
+        if (rangeIds.isEmpty()) return keyIds;
+        if (keyIds.isEmpty()) return rangeIds;
 
-        StringBuilder builder = new StringBuilder("{");
-        for (int k = 0, t = keys.size(); k < keys.size() ; ++k)
+        List<TxnId> output = new ArrayList<>(keyIds.size() + rangeIds.size());
+        int ki = 0, ri = 0;
+        while (ki < keyIds.size() && ri < rangeIds.size())
         {
-            if (builder.length() > 1)
-                builder.append(", ");
-
-            builder.append(keys.get(k));
-            builder.append(":[");
-            boolean first = true;
-            while (t < keyToTxnId[k])
-            {
-                if (first) first = false;
-                else builder.append(", ");
-                builder.append(txnIds[keyToTxnId[t++]]);
-            }
-            builder.append("]");
+            int c = keyIds.get(ki).compareTo(rangeIds.get(ri));
+            Invariants.checkState(c != 0);
+            if (c < 0) output.add(keyIds.get(ki++));
+            else output.add(rangeIds.get(ri++));
         }
-        builder.append("}");
-        return builder.toString();
+        while (ki < keyIds.size())
+            output.add(keyIds.get(ki++));
+        while (ri < rangeIds.size())
+            output.add(rangeIds.get(ri++));
+        return output;
     }
 
-    @Override
-    public boolean equals(Object o)
+    public Unseekables<?, ?> someUnseekables(TxnId txnId)
     {
-        if (this == o) return true;
-        if (o == null || getClass() != o.getClass()) return false;
-        return equals((Deps) o);
+        if (keyDeps.contains(txnId))
+            return keyDeps.someUnseekables(txnId);
+        else
+            return rangeDeps.someUnseekables(txnId);
     }
 
-    public boolean equals(Deps that)
+    // NOTE: filter only applied to keyDeps
+    public void forEach(Ranges ranges, Consumer<TxnId> forEach)
     {
-        return this.txnIds.length == that.txnIds.length
-               && this.keys.size() == that.keys.size()
-               && Arrays.equals(this.keyToTxnId, that.keyToTxnId)
-               && Arrays.equals(this.txnIds, that.txnIds)
-               && this.keys.equals(that.keys);
+        keyDeps.forEachUniqueTxnId(ranges, forEach);
+        rangeDeps.forEachUniqueTxnId(ranges, forEach);
     }
 
-    public static class Entry implements Map.Entry<Key, TxnId>
+    public static <T> Deps merge(List<T> list, Function<T, Deps> getter)
     {
-        final Key key;
-        final TxnId txnId;
-
-        public Entry(Key key, TxnId txnId)
-        {
-            this.key = key;
-            this.txnId = txnId;
-        }
-
-        @Override
-        public Key getKey()
-        {
-            return key;
-        }
-
-        @Override
-        public TxnId getValue()
-        {
-            return txnId;
-        }
-
-        @Override
-        public TxnId setValue(TxnId value)
-        {
-            throw new UnsupportedOperationException();
-        }
-
-        @Override
-        public String toString()
-        {
-            return key + "->" + txnId;
-        }
+        return new Deps(KeyDeps.merge(list, getter, deps -> deps.keyDeps),
+                        RangeDeps.merge(list, getter, deps -> deps.rangeDeps));
     }
 
-    private void checkValid()
+    @Override
+    public String toString()
     {
-        int k = 0;
-        for (int i = keys.size() ; i < keyToTxnId.length ; ++i)
-        {
-            boolean first = true;
-            while (i < keyToTxnId[k])
-            {
-                if (first) first = false;
-                else if (keyToTxnId[i - 1] == keyToTxnId[i])
-                {
-                    Key key = keys.get(i);
-                    TxnId txnId = txnIds[keyToTxnId[i]];
-                    throw new IllegalStateException(String.format("Duplicate TxnId (%s) found for key %s", txnId, key));
-                }
-                i++;
-            }
-            ++k;
-        }
+        return keyDeps.toString() + ", " + rangeDeps.toString();
     }
 
-    private static void setBit(int[] array, int offset, int index)
+    @Override
+    public boolean equals(Object that)
     {
-        array[offset + index / 32] |= (1 << (index & 31));
+        return this == that || (that instanceof Deps && equals((Deps)that));
     }
 
-    private static boolean hasSetBit(int[] array, int offset, int index)
+    public boolean equals(Deps that)
     {
-        return (array[offset + index / 32] & (1 << (index & 31))) != 0;
+        return this.keyDeps.equals(that.keyDeps) && this.rangeDeps.equals(that.rangeDeps);
     }
-
 }
diff --git a/accord-core/src/main/java/accord/primitives/FullKeyRoute.java b/accord-core/src/main/java/accord/primitives/FullKeyRoute.java
index 469ed59..0806df5 100644
--- a/accord-core/src/main/java/accord/primitives/FullKeyRoute.java
+++ b/accord-core/src/main/java/accord/primitives/FullKeyRoute.java
@@ -49,6 +49,7 @@ public class FullKeyRoute extends KeyRoute implements FullRoute<RoutingKey>
         return slice(ranges);
     }
 
+    @Override
     public FullKeyRoute toMaximalUnseekables()
     {
         return this;
diff --git a/accord-core/src/main/java/accord/primitives/FullRangeRoute.java b/accord-core/src/main/java/accord/primitives/FullRangeRoute.java
index 7e39fd7..848311d 100644
--- a/accord-core/src/main/java/accord/primitives/FullRangeRoute.java
+++ b/accord-core/src/main/java/accord/primitives/FullRangeRoute.java
@@ -56,6 +56,7 @@ public class FullRangeRoute extends RangeRoute implements FullRoute<Range>
         return slice(ranges);
     }
 
+    @Override
     public FullRangeRoute toMaximalUnseekables()
     {
         return this;
diff --git a/accord-core/src/main/java/accord/primitives/KeyDeps.java b/accord-core/src/main/java/accord/primitives/KeyDeps.java
new file mode 100644
index 0000000..1ac6b65
--- /dev/null
+++ b/accord-core/src/main/java/accord/primitives/KeyDeps.java
@@ -0,0 +1,537 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package accord.primitives;
+
+import accord.api.Key;
+import accord.api.RoutingKey;
+import accord.utils.ArrayBuffers;
+import accord.utils.SymmetricComparator;
+
+import java.util.*;
+import java.util.function.BiConsumer;
+import java.util.function.Consumer;
+import java.util.function.Function;
+import java.util.function.Predicate;
+
+import static accord.utils.ArrayBuffers.*;
+import static accord.utils.RelationMultiMap.*;
+import static accord.utils.SortedArrays.Search.FAST;
+
+/**
+ * A collection of dependencies for a transaction, organised by the key the dependency is adopted via.
+ * An inverse map from TxnId to Key may also be constructed and stored in this collection.
+ */
+// TODO (desired, consider): switch to RoutingKey? Would mean adopting execution dependencies less precisely, but saving ser/deser of large keys
+public class KeyDeps implements Iterable<Map.Entry<Key, TxnId>>
+{
+    public static final KeyDeps NONE = new KeyDeps(Keys.EMPTY, NO_TXNIDS, NO_INTS);
+
+    public static class SerializerSupport
+    {
+        private SerializerSupport() {}
+
+        public static int keysToTxnIdsCount(KeyDeps deps)
+        {
+            return deps.keysToTxnIds.length;
+        }
+
+        public static int keysToTxnIds(KeyDeps deps, int idx)
+        {
+            return deps.keysToTxnIds[idx];
+        }
+
+        public static KeyDeps create(Keys keys, TxnId[] txnIds, int[] keyToTxnId)
+        {
+            return new KeyDeps(keys, txnIds, keyToTxnId);
+        }
+    }
+
+    public static KeyDeps none(Keys keys)
+    {
+        int[] keysToTxnId = new int[keys.size()];
+        Arrays.fill(keysToTxnId, keys.size());
+        return new KeyDeps(keys, NO_TXNIDS, keysToTxnId);
+    }
+
+    /**
+     * Expects Command to be provided in TxnId order
+     */
+    public static Builder builder()
+    {
+        return new Builder();
+    }
+
+    public static class Builder extends AbstractBuilder<Key, TxnId, KeyDeps>
+    {
+        public Builder()
+        {
+            super(ADAPTER);
+        }
+
+        @Override
+        protected KeyDeps none()
+        {
+            return KeyDeps.NONE;
+        }
+
+        @Override
+        protected KeyDeps build(Key[] keys, TxnId[] txnIds, int[] keysToTxnIds)
+        {
+            return new KeyDeps(Keys.ofSorted(keys), txnIds, keysToTxnIds);
+        }
+    }
+
+    public static <T1, T2> KeyDeps merge(List<T1> merge, Function<T1, T2> getter1, Function<T2, KeyDeps> getter2)
+    {
+        try (LinearMerger<Key, TxnId, KeyDeps> linearMerger = new LinearMerger<>(ADAPTER))
+        {
+            int mergeIndex = 0, mergeSize = merge.size();
+            while (mergeIndex < mergeSize)
+            {
+                T2 intermediate = getter1.apply(merge.get(mergeIndex++));
+                if (intermediate == null)
+                    continue;
+
+                KeyDeps deps = getter2.apply(intermediate);
+                if (deps == null || deps.isEmpty())
+                    continue;
+
+                linearMerger.update(deps, deps.keys.keys, deps.txnIds, deps.keysToTxnIds);
+            }
+
+            return linearMerger.get(KeyDeps::new, NONE);
+        }
+    }
+
+    final Keys keys; // unique Keys
+    final TxnId[] txnIds; // unique TxnId
+
+    /**
+     * This represents a map of {@code Key -> [TxnId] } where each TxnId is actually a pointer into the txnIds array.
+     * The beginning of the array (the first keys.size() entries) are offsets into this array.
+     * <p/>
+     * Example:
+     * <p/>
+     * {@code
+     *   int keyIdx = keys.indexOf(key);
+     *   int startOfTxnOffset = keyIdx == 0 ? keys.size() : keyToTxnId[keyIdx - 1];
+     *   int endOfTxnOffset = keyToTxnId[keyIdx];
+     *   for (int i = startOfTxnOffset; i < endOfTxnOffset; i++)
+     *   {
+     *       TxnId id = txnIds[keyToTxnId[i]]
+     *       ...
+     *   }
+     * }
+     */
+    final int[] keysToTxnIds; // Key -> [TxnId]
+    // Lazy loaded in ensureTxnIdToKey()
+    int[] txnIdsToKeys; // TxnId -> [Key] TODO (low priority, efficiency): this could be a BTree?
+
+    KeyDeps(Key[] keys, TxnId[] txnIds, int[] keysToTxnIds)
+    {
+        this(Keys.ofSorted(keys), txnIds, keysToTxnIds);
+    }
+
+    KeyDeps(Keys keys, TxnId[] txnIds, int[] keysToTxnIds)
+    {
+        this.keys = keys;
+        this.txnIds = txnIds;
+        this.keysToTxnIds = keysToTxnIds;
+        if (!(keys.isEmpty() || keysToTxnIds[keys.size() - 1] == keysToTxnIds.length))
+            throw new IllegalArgumentException(String.format("Last key (%s) in keyToTxnId does not point (%d) to the end of the array (%d);\nkeyToTxnId=%s", keys.get(keys.size() - 1), keysToTxnIds[keys.size() - 1], keysToTxnIds.length, Arrays.toString(keysToTxnIds)));
+        checkValid(keys.keys, txnIds, keysToTxnIds);
+    }
+
+    public KeyDeps slice(Ranges ranges)
+    {
+        if (isEmpty())
+            return new KeyDeps(keys, txnIds, keysToTxnIds);
+
+        // TODO (low priority, efficiency): can slice in parallel with selecting keyToTxnId contents to avoid duplicate merging
+        Keys select = keys.slice(ranges);
+
+        if (select.isEmpty())
+            return new KeyDeps(Keys.EMPTY, NO_TXNIDS, NO_INTS);
+
+        if (select.size() == keys.size())
+            return new KeyDeps(keys, txnIds, keysToTxnIds);
+
+        int i = 0;
+        int offset = select.size();
+        for (int j = 0 ; j < select.size() ; ++j)
+        {
+            int findi = keys.findNext(i, select.get(j), FAST);
+            if (findi < 0)
+                continue;
+
+            i = findi;
+            offset += keysToTxnIds[i] - (i == 0 ? keys.size() : keysToTxnIds[i - 1]);
+        }
+
+        int[] src = keysToTxnIds;
+        int[] trg = new int[offset];
+
+        i = 0;
+        offset = select.size();
+        for (int j = 0 ; j < select.size() ; ++j)
+        {
+            int findi = keys.findNext(i, select.get(j), FAST);
+            if (findi >= 0)
+            {
+                i = findi;
+                int start = i == 0 ? keys.size() : src[i - 1];
+                int count = src[i] - start;
+                System.arraycopy(src, start, trg, offset, count);
+                offset += count;
+            }
+            trg[j] = offset;
+        }
+
+        TxnId[] txnIds = trimUnusedValues(select.keys, this.txnIds, trg, TxnId[]::new);
+        return new KeyDeps(select, txnIds, trg);
+    }
+
+    public KeyDeps with(KeyDeps that)
+    {
+        if (isEmpty() || that.isEmpty())
+            return isEmpty() ? that : this;
+
+        return linearUnion(
+                this.keys.keys, this.keys.keys.length, this.txnIds, this.txnIds.length, this.keysToTxnIds, this.keysToTxnIds.length,
+                that.keys.keys, that.keys.keys.length, that.txnIds, that.txnIds.length, that.keysToTxnIds, that.keysToTxnIds.length,
+                Key::compareTo, TxnId::compareTo,
+                cachedKeys(), cachedTxnIds(), cachedInts(),
+                (keys, keysLength, txnIds, txnIdsLength, out, outLength) ->
+                        new KeyDeps(Keys.ofSortedUnchecked(cachedKeys().complete(keys, keysLength)),
+                                cachedTxnIds().complete(txnIds, txnIdsLength),
+                                cachedInts().complete(out, outLength))
+                );
+    }
+
+    public KeyDeps without(Predicate<TxnId> remove)
+    {
+        return remove(this, keys.keys, txnIds, keysToTxnIds, remove,
+                NONE, TxnId[]::new, keys, KeyDeps::new);
+    }
+
+    public boolean contains(TxnId txnId)
+    {
+        return Arrays.binarySearch(txnIds, txnId) >= 0;
+    }
+
+    // return true iff we map any keys to any txnId
+    // if the mapping is empty we return false, whether or not we have any keys or txnId by themselves
+    public boolean isEmpty()
+    {
+        return keysToTxnIds.length == keys.size();
+    }
+
+    public Keys someKeys(TxnId txnId)
+    {
+        int txnIdIndex = Arrays.binarySearch(txnIds, txnId);
+        if (txnIdIndex < 0)
+            return Keys.EMPTY;
+
+        ensureTxnIdToKey();
+
+        int start = txnIdIndex == 0 ? txnIds.length : txnIdsToKeys[txnIdIndex - 1];
+        int end = txnIdsToKeys[txnIdIndex];
+        if (start == end)
+            return Keys.EMPTY;
+
+        Key[] result = new Key[end - start];
+        for (int i = start ; i < end ; ++i)
+            result[i - start] = keys.get(txnIdsToKeys[i]);
+        return Keys.of(result);
+    }
+
+    public Unseekables<RoutingKey, ?> someUnseekables(TxnId txnId)
+    {
+        int txnIdIndex = Arrays.binarySearch(txnIds, txnId);
+        if (txnIdIndex < 0)
+            throw new IllegalStateException("Cannot create a RouteFragment without any keys");
+
+        ensureTxnIdToKey();
+
+        int start = txnIdIndex == 0 ? txnIds.length : txnIdsToKeys[txnIdIndex - 1];
+        int end = txnIdsToKeys[txnIdIndex];
+        if (start == end)
+            throw new IllegalStateException("Cannot create a RouteFragment without any keys");
+
+        RoutingKey[] result = new RoutingKey[end - start];
+        result[0] = keys.get(txnIdsToKeys[start]).toUnseekable();
+        int resultCount = 1;
+        for (int i = start + 1 ; i < end ; ++i)
+        {
+            RoutingKey next = keys.get(txnIdsToKeys[i]).toUnseekable();
+            if (!next.equals(result[resultCount - 1]))
+                result[resultCount++] = next;
+        }
+
+        if (resultCount < result.length)
+            result = Arrays.copyOf(result, resultCount);
+        return new RoutingKeys(result);
+    }
+
+    void ensureTxnIdToKey()
+    {
+        if (txnIdsToKeys != null)
+            return;
+
+        txnIdsToKeys = invert(keysToTxnIds, keysToTxnIds.length, keys.size(), txnIds.length);
+    }
+
+    public void forEach(Ranges ranges, BiConsumer<Key, TxnId> forEach)
+    {
+        Routables.foldl(keys, ranges, (key, value, index) -> {
+            for (int t = startOffset(index), end = endOffset(index); t < end ; ++t)
+            {
+                TxnId txnId = txnIds[keysToTxnIds[t]];
+                forEach.accept(key, txnId);
+            }
+            return null;
+        }, null);
+    }
+
+    /**
+     * For each {@link TxnId} that references a key within the {@link Ranges}; the {@link TxnId} will be seen exactly once.
+     * @param ranges to match on
+     * @param forEach function to call on each unique {@link TxnId}
+     */
+    public void forEachUniqueTxnId(Ranges ranges, Consumer<TxnId> forEach)
+    {
+        // Find all keys within the ranges, but record existence within an int64 bitset.  Since the bitset is limited
+        // to 64, this search must be called multiple times searching for different TxnIds in txnIds; this also has
+        // the property that forEach is called in TxnId order.
+        //TODO (expected, efficiency): reconsider this, probably not worth trying to save allocations at cost of multiple loop
+        //                             use BitSet, or perhaps extend so we can have no nested allocations when few bits
+        for (int offset = 0 ; offset < txnIds.length ; offset += 64)
+        {
+            long bitset = Routables.foldl(keys, ranges, (key, off, value, keyIndex) -> {
+                int index = startOffset(keyIndex);
+                int end = endOffset(keyIndex);
+                if (off > 0)
+                {
+                    // TODO (low priority, efficiency): interpolation search probably great here
+                    index = Arrays.binarySearch(keysToTxnIds, index, end, (int)off);
+                    if (index < 0)
+                        index = -1 - index;
+                }
+
+                while (index < end)
+                {
+                    long next = keysToTxnIds[index++] - off;
+                    if (next >= 64)
+                        break;
+                    value |= 1L << next;
+                }
+
+                return value;
+            }, offset, 0, -1L);
+
+            while (bitset != 0)
+            {
+                int i = Long.numberOfTrailingZeros(bitset);
+                TxnId txnId = txnIds[offset + i];
+                forEach.accept(txnId);
+                bitset ^= Long.lowestOneBit(bitset);
+            }
+        }
+    }
+
+    public void forEach(Key key, Consumer<TxnId> forEach)
+    {
+        int keyIndex = keys.indexOf(key);
+        if (keyIndex < 0)
+            return;
+
+        int index = startOffset(keyIndex);
+        int end = endOffset(keyIndex);
+        while (index < end)
+            forEach.accept(txnIds[keysToTxnIds[index++]]);
+    }
+
+    public Keys keys()
+    {
+        return keys;
+    }
+
+    public int txnIdCount()
+    {
+        return txnIds.length;
+    }
+
+    public int totalCount()
+    {
+        return keysToTxnIds.length - keys.size();
+    }
+
+    public TxnId txnId(int i)
+    {
+        return txnIds[i];
+    }
+
+    public Collection<TxnId> txnIds()
+    {
+        return Arrays.asList(txnIds);
+    }
+
+    public List<TxnId> txnIds(Key key)
+    {
+        int keyIndex = keys.indexOf(key);
+        if (keyIndex < 0)
+            return Collections.emptyList();
+
+        int start = startOffset(keyIndex);
+        int end = endOffset(keyIndex);
+        int size = end - start;
+        return txnIds(keysToTxnIds, start, size);
+    }
+
+    public List<TxnId> txnIds(Range range)
+    {
+        int startIndex = keys.indexOf(range.start());
+        if (startIndex < 0) startIndex = -1 - startIndex;
+        else if (!range.startInclusive()) ++startIndex;
+
+        int endIndex = keys.indexOf(range.end());
+        if (endIndex < 0) endIndex = -1 - endIndex;
+        else if (range.endInclusive()) ++endIndex;
+
+        if (startIndex == endIndex)
+            return Collections.emptyList();
+
+        int maxLength = Math.min(txnIds.length, startOffset(endIndex) - startOffset(startIndex));
+        int[] scratch = cachedInts().getInts(maxLength);
+        int count = 0;
+        for (int i = startIndex ; i < endIndex ; ++i)
+        {
+            int ri = startOffset(i), re = endOffset(i);
+            if (ri == re)
+                continue;
+
+            System.arraycopy(scratch, 0, scratch, maxLength - count, count);
+            int li = maxLength - count, le = maxLength;
+            count = 0;
+            while (li < le && ri < re)
+            {
+                int c = scratch[li] - keysToTxnIds[ri];
+                if (c <= 0)
+                {
+                    scratch[count++] = scratch[li++];
+                    if (c == 0) ++ri;
+                }
+                else
+                {
+                    scratch[count++] = keysToTxnIds[ri++];
+                }
+            }
+            while (li < le)
+                scratch[count++] = scratch[li++];
+            while (ri < re)
+                scratch[count++] = keysToTxnIds[ri++];
+
+            if (count == maxLength)
+                break;
+        }
+
+        int[] ids = cachedInts().completeAndDiscard(scratch, count);
+        return txnIds(ids, 0, count);
+    }
+
+    private List<TxnId> txnIds(int[] ids, int start, int size)
+    {
+        return new AbstractList<TxnId>()
+        {
+            @Override
+            public TxnId get(int index)
+            {
+                if (index > size)
+                    throw new IndexOutOfBoundsException();
+                return txnIds[ids[start + index]];
+            }
+
+            @Override
+            public int size()
+            {
+                return size;
+            }
+        };
+    }
+
+    private int startOffset(int keyIndex)
+    {
+        return keyIndex == 0 ? keys.size() : keysToTxnIds[keyIndex - 1];
+    }
+
+    private int endOffset(int keyIndex)
+    {
+        return keysToTxnIds[keyIndex];
+    }
+
+    public boolean equals(Object that)
+    {
+        return this == that || (that instanceof KeyDeps && equals((KeyDeps)that));
+    }
+
+    public boolean equals(KeyDeps that)
+    {
+        return testEquality(this.keys.keys, this.txnIds, this.keysToTxnIds, that.keys.keys, that.txnIds, that.keysToTxnIds);
+    }
+
+    @Override
+    public Iterator<Map.Entry<Key, TxnId>> iterator()
+    {
+        return newIterator(keys.keys, txnIds, keysToTxnIds);
+    }
+
+    @Override
+    public String toString()
+    {
+        return toSimpleString(keys.keys, txnIds, keysToTxnIds);
+    }
+
+    private static final KeyDepsAdapter ADAPTER = new KeyDepsAdapter();
+    static class KeyDepsAdapter implements Adapter<Key, TxnId>
+    {
+        @Override
+        public final SymmetricComparator<? super Key> keyComparator()
+        {
+            return Key::compareTo;
+        }
+
+        @Override
+        public final SymmetricComparator<? super TxnId> valueComparator()
+        {
+            return TxnId::compareTo;
+        }
+
+        @Override
+        public final ObjectBuffers<Key> cachedKeys()
+        {
+            return ArrayBuffers.cachedKeys();
+        }
+
+        @Override
+        public final ObjectBuffers<TxnId> cachedValues()
+        {
+            return ArrayBuffers.cachedTxnIds();
+        }
+    }
+}
diff --git a/accord-core/src/main/java/accord/primitives/KeyRoute.java b/accord-core/src/main/java/accord/primitives/KeyRoute.java
index ccb2a9f..39f0653 100644
--- a/accord-core/src/main/java/accord/primitives/KeyRoute.java
+++ b/accord-core/src/main/java/accord/primitives/KeyRoute.java
@@ -7,7 +7,7 @@ import accord.utils.SortedArrays;
 
 import javax.annotation.Nonnull;
 
-public abstract class KeyRoute extends AbstractRoutableKeys<Route<RoutingKey>> implements Route<RoutingKey>
+public abstract class KeyRoute extends AbstractUnseekableKeys<Route<RoutingKey>> implements Route<RoutingKey>
 {
     public final RoutingKey homeKey;
 
diff --git a/accord-core/src/main/java/accord/primitives/PartialDeps.java b/accord-core/src/main/java/accord/primitives/PartialDeps.java
index addf11e..4a633ad 100644
--- a/accord-core/src/main/java/accord/primitives/PartialDeps.java
+++ b/accord-core/src/main/java/accord/primitives/PartialDeps.java
@@ -1,49 +1,38 @@
 package accord.primitives;
 
-import com.google.common.base.Preconditions;
+import accord.utils.Invariants;
 
 public class PartialDeps extends Deps
 {
-    public static final PartialDeps NONE = new PartialDeps(Ranges.EMPTY, Deps.NONE.keys, Deps.NONE.txnIds, Deps.NONE.keyToTxnId);
+    public static final PartialDeps NONE = new PartialDeps(Ranges.EMPTY, KeyDeps.NONE, RangeDeps.NONE);
 
-    public static class SerializerSupport
+    public static Builder builder(Ranges covering)
     {
-        private SerializerSupport() {}
-
-        public static PartialDeps create(Ranges covering, Keys keys, TxnId[] txnIds, int[] keyToTxnId)
-        {
-            return new PartialDeps(covering, keys, txnIds, keyToTxnId);
-        }
+        return new Builder(covering);
     }
-
-    public static class OrderedBuilder extends AbstractOrderedBuilder<PartialDeps>
+    public static class Builder extends AbstractBuilder<PartialDeps>
     {
         final Ranges covering;
-        public OrderedBuilder(Ranges covering, boolean hasOrderedTxnId)
+        public Builder(Ranges covering)
         {
-            super(hasOrderedTxnId);
             this.covering = covering;
         }
 
         @Override
-        PartialDeps build(Keys keys, TxnId[] txnIds, int[] keysToTxnIds)
+        public PartialDeps build()
         {
-            return new PartialDeps(covering, keys, txnIds, keysToTxnIds);
+            return new PartialDeps(covering, keyBuilder.build(), rangeBuilder == null ? RangeDeps.NONE : rangeBuilder.build());
         }
     }
 
-    public static OrderedBuilder orderedBuilder(Ranges ranges, boolean hasOrderedTxnId)
-    {
-        return new OrderedBuilder(ranges, hasOrderedTxnId);
-    }
-
     public final Ranges covering;
 
-    PartialDeps(Ranges covering, Keys keys, TxnId[] txnIds, int[] keyToTxnId)
+    public PartialDeps(Ranges covering, KeyDeps keyDeps, RangeDeps rangeDeps)
     {
-        super(keys, txnIds, keyToTxnId);
+        super(keyDeps, rangeDeps);
         this.covering = covering;
-        Preconditions.checkState(covering.containsAll(keys));
+        Invariants.checkState(covering.containsAll(keyDeps.keys));
+        Invariants.checkState(rangeDeps.isCoveredBy(covering));
     }
 
     public boolean covers(Unseekables<?, ?> keysOrRanges)
@@ -53,15 +42,17 @@ public class PartialDeps extends Deps
 
     public PartialDeps with(PartialDeps that)
     {
-        Deps merged = with((Deps) that);
-        return new PartialDeps(covering.union(that.covering), merged.keys, merged.txnIds, merged.keyToTxnId);
+        Invariants.checkArgument((this.rangeDeps == null) == (that.rangeDeps == null));
+        return new PartialDeps(that.covering.union(this.covering),
+                this.keyDeps.with(that.keyDeps),
+                this.rangeDeps == null ? null : this.rangeDeps.with(that.rangeDeps));
     }
 
     public Deps reconstitute(FullRoute<?> route)
     {
         if (!covers(route))
             throw new IllegalArgumentException();
-        return new Deps(keys, txnIds, keyToTxnId);
+        return new Deps(keyDeps, rangeDeps);
     }
 
     // PartialRoute<?>might cover a wider set of ranges, some of which may have no involved keys
@@ -73,7 +64,24 @@ public class PartialDeps extends Deps
         if (covers(route.covering()))
             return this;
 
-        return new PartialDeps(route.covering(), keys, txnIds, keyToTxnId);
+        return new PartialDeps(route.covering(), keyDeps, rangeDeps);
+    }
+
+    @Override
+    public boolean equals(Object that)
+    {
+        return this == that || (that instanceof PartialDeps && equals((PartialDeps) that));
+    }
+
+    @Override
+    public boolean equals(Deps that)
+    {
+        return that instanceof PartialDeps && equals((PartialDeps) that);
+    }
+
+    public boolean equals(PartialDeps that)
+    {
+        return this.covering.equals(that.covering) && super.equals(that);
     }
 
     @Override
@@ -81,5 +89,4 @@ public class PartialDeps extends Deps
     {
         return covering + ":" + super.toString();
     }
-
 }
diff --git a/accord-core/src/main/java/accord/primitives/PartialKeyRoute.java b/accord-core/src/main/java/accord/primitives/PartialKeyRoute.java
index da9143a..212bffb 100644
--- a/accord-core/src/main/java/accord/primitives/PartialKeyRoute.java
+++ b/accord-core/src/main/java/accord/primitives/PartialKeyRoute.java
@@ -26,6 +26,7 @@ public class PartialKeyRoute extends KeyRoute implements PartialRoute<RoutingKey
         this.covering = covering;
     }
 
+    @Override
     public PartialKeyRoute sliceStrict(Ranges newRanges)
     {
         if (!covering.containsAll(newRanges))
@@ -55,7 +56,7 @@ public class PartialKeyRoute extends KeyRoute implements PartialRoute<RoutingKey
     }
 
     @Override
-    public AbstractRoutableKeys<?> with(RoutingKey withKey)
+    public AbstractUnseekableKeys<?> with(RoutingKey withKey)
     {
         if (contains(withKey))
             return this;
@@ -63,6 +64,7 @@ public class PartialKeyRoute extends KeyRoute implements PartialRoute<RoutingKey
         return new RoutingKeys(toRoutingKeysArray(withKey));
     }
 
+    @Override
     public PartialKeyRoute slice(Ranges newRanges)
     {
         if (newRanges.containsAll(covering))
@@ -78,6 +80,7 @@ public class PartialKeyRoute extends KeyRoute implements PartialRoute<RoutingKey
         return covering;
     }
 
+    @Override
     public PartialKeyRoute union(PartialRoute<RoutingKey> with)
     {
         if (!(with instanceof PartialKeyRoute))
diff --git a/accord-core/src/main/java/accord/primitives/PartialRangeRoute.java b/accord-core/src/main/java/accord/primitives/PartialRangeRoute.java
index 42a9aac..204d939 100644
--- a/accord-core/src/main/java/accord/primitives/PartialRangeRoute.java
+++ b/accord-core/src/main/java/accord/primitives/PartialRangeRoute.java
@@ -50,6 +50,7 @@ public class PartialRangeRoute extends RangeRoute implements PartialRoute<Range>
         return ranges.intersects(covering);
     }
 
+    @Override
     public PartialRangeRoute sliceStrict(Ranges newRange)
     {
         if (!covering.containsAll(newRange))
@@ -64,6 +65,7 @@ public class PartialRangeRoute extends RangeRoute implements PartialRoute<Range>
         throw new UnsupportedOperationException();
     }
 
+    @Override
     public PartialRangeRoute slice(Ranges newRanges)
     {
         if (newRanges.containsAll(covering))
@@ -72,6 +74,7 @@ public class PartialRangeRoute extends RangeRoute implements PartialRoute<Range>
         return slice(newRanges, this, homeKey, PartialRangeRoute::new);
     }
 
+    @Override
     public Unseekables<Range, ?> with(RoutingKey withKey)
     {
         throw new UnsupportedOperationException();
@@ -84,6 +87,7 @@ public class PartialRangeRoute extends RangeRoute implements PartialRoute<Range>
         return union((PartialRangeRoute) that);
     }
 
+    @Override
     public PartialRangeRoute union(PartialRoute<Range> with)
     {
         if (!(with instanceof PartialRangeRoute))
diff --git a/accord-core/src/main/java/accord/primitives/PartialRoute.java b/accord-core/src/main/java/accord/primitives/PartialRoute.java
index cb93004..50ebea5 100644
--- a/accord-core/src/main/java/accord/primitives/PartialRoute.java
+++ b/accord-core/src/main/java/accord/primitives/PartialRoute.java
@@ -2,6 +2,7 @@ package accord.primitives;
 
 public interface PartialRoute<T extends Unseekable> extends Route<T>
 {
+    @Override
     boolean isEmpty();
     Ranges covering();
 
diff --git a/accord-core/src/main/java/accord/primitives/PartialTxn.java b/accord-core/src/main/java/accord/primitives/PartialTxn.java
index f9588b1..71e7554 100644
--- a/accord-core/src/main/java/accord/primitives/PartialTxn.java
+++ b/accord-core/src/main/java/accord/primitives/PartialTxn.java
@@ -50,6 +50,7 @@ public interface PartialTxn extends Txn
             return covering;
         }
 
+        @Override
         public PartialTxn with(PartialTxn add)
         {
             if (!add.kind().equals(kind()))
@@ -78,6 +79,7 @@ public interface PartialTxn extends Txn
             return covering.containsAll(ranges);
         }
 
+        @Override
         public Txn reconstitute(FullRoute<?> route)
         {
             if (!covers(route) || query() == null)
@@ -86,6 +88,7 @@ public interface PartialTxn extends Txn
             return new Txn.InMemory(kind(), keys(), read(), query(), update());
         }
 
+        @Override
         public PartialTxn reconstitutePartial(PartialRoute<?> route)
         {
             if (!covers(route))
diff --git a/accord-core/src/main/java/accord/primitives/Range.java b/accord-core/src/main/java/accord/primitives/Range.java
index 463a910..98fb673 100644
--- a/accord-core/src/main/java/accord/primitives/Range.java
+++ b/accord-core/src/main/java/accord/primitives/Range.java
@@ -18,6 +18,7 @@
 
 package accord.primitives;
 
+import accord.api.Key;
 import accord.api.RoutingKey;
 import accord.utils.Invariants;
 import accord.utils.SortedArrays;
@@ -67,6 +68,12 @@ public abstract class Range implements Comparable<RoutableKey>, Unseekable, Seek
         {
             return new EndInclusive(start, end);
         }
+
+        @Override
+        public String toString()
+        {
+            return "Range(" + start() + ", " + end() + ']';
+        }
     }
 
     public static class StartInclusive extends Range
@@ -103,6 +110,12 @@ public abstract class Range implements Comparable<RoutableKey>, Unseekable, Seek
         {
             return new StartInclusive(start, end);
         }
+
+        @Override
+        public String toString()
+        {
+            return "Range[" + start() + ", " + end() + ')';
+        }
     }
 
     public static Range range(RoutingKey start, RoutingKey end, boolean startInclusive, boolean endInclusive)
@@ -163,7 +176,7 @@ public abstract class Range implements Comparable<RoutableKey>, Unseekable, Seek
         if (start.compareTo(end) >= 0)
             throw new IllegalArgumentException(start + " >= " + end);
         if (startInclusive() == endInclusive())
-            throw new IllegalStateException("KeyRange must have one side inclusive, and the other exclusive. KeyRange of different types should not be mixed.");
+            throw new IllegalStateException("Range must have one side inclusive, and the other exclusive. Range of different types should not be mixed.");
         this.start = start;
         this.end = end;
     }
@@ -178,6 +191,7 @@ public abstract class Range implements Comparable<RoutableKey>, Unseekable, Seek
         return end;
     }
 
+    @Override
     public final Domain domain() { return Domain.Range; }
 
     public abstract boolean startInclusive();
@@ -185,6 +199,18 @@ public abstract class Range implements Comparable<RoutableKey>, Unseekable, Seek
 
     public abstract Range subRange(RoutingKey start, RoutingKey end);
 
+    @Override
+    public Key asKey()
+    {
+        throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public Range asRange()
+    {
+        return this;
+    }
+
     @Override
     public boolean equals(Object o)
     {
@@ -200,16 +226,11 @@ public abstract class Range implements Comparable<RoutableKey>, Unseekable, Seek
         return start.hashCode() * 31 + end.hashCode();
     }
 
-    @Override
-    public String toString()
-    {
-        return "Range[" + start + ", " + end + ']';
-    }
-
     /**
      * Returns a negative integer, zero, or a positive integer as the provided key is greater than, contained by,
      * or less than this range.
      */
+    @Override
     public abstract int compareTo(RoutableKey key);
 
     public boolean contains(RoutableKey key)
@@ -224,7 +245,7 @@ public abstract class Range implements Comparable<RoutableKey>, Unseekable, Seek
     public int compareIntersecting(Range that)
     {
         if (that.getClass() != this.getClass())
-            throw new IllegalArgumentException("Cannot mix KeyRange of different types");
+            throw new IllegalArgumentException("Cannot mix Range of different types");
         if (this.start.compareTo(that.end) >= 0)
             return 1;
         if (this.end.compareTo(that.start) <= 0)
@@ -232,6 +253,18 @@ public abstract class Range implements Comparable<RoutableKey>, Unseekable, Seek
         return 0;
     }
 
+    /**
+     * Sorts by start then end
+     */
+    public int compare(Range that)
+    {
+        if (that.getClass() != this.getClass())
+            throw new IllegalArgumentException("Cannot mix Range of different types");
+        int c = this.start.compareTo(that.start);
+        if (c == 0) c = this.end.compareTo(that.end);
+        return c;
+    }
+
     public boolean contains(Range that)
     {
         return that.start.compareTo(this.start) >= 0 && that.end.compareTo(this.end) <= 0;
@@ -297,7 +330,7 @@ public abstract class Range implements Comparable<RoutableKey>, Unseekable, Seek
     }
 
     @Override
-    public Unseekable toUnseekable()
+    public Range toUnseekable()
     {
         return this;
     }
diff --git a/accord-core/src/main/java/accord/primitives/RangeDeps.java b/accord-core/src/main/java/accord/primitives/RangeDeps.java
new file mode 100644
index 0000000..74da4cd
--- /dev/null
+++ b/accord-core/src/main/java/accord/primitives/RangeDeps.java
@@ -0,0 +1,663 @@
+package accord.primitives;
+
+import accord.api.Key;
+import accord.utils.*;
+import accord.utils.RelationMultiMap.AbstractBuilder;
+import accord.utils.RelationMultiMap.Adapter;
+import net.nicoulaj.compilecommand.annotations.DontInline;
+import net.nicoulaj.compilecommand.annotations.Inline;
+
+import javax.annotation.Nonnull;
+import javax.annotation.Nullable;
+import java.util.*;
+import java.util.function.Consumer;
+import java.util.function.Function;
+import java.util.function.Predicate;
+
+import static accord.utils.ArrayBuffers.*;
+import static accord.utils.RelationMultiMap.*;
+import static accord.utils.RelationMultiMap.remove;
+import static accord.utils.SearchableRangeListBuilder.Links.LINKS;
+import static accord.utils.SearchableRangeListBuilder.Strategy.ACCURATE;
+import static accord.utils.SortedArrays.Search.CEIL;
+
+/**
+ * <p>Maintains a lazily-constructed, bidirectional map between Range and TxnId.
+ * <p>Ranges are stored sorted by start then end, and indexed by a secondary {@link SearchableRangeList} structure.
+ * <p>The relationship between Range and TxnId is maintained via {@code int[]} utilising {@link RelationMultiMap}
+ * functionality.
+ */
+public class RangeDeps implements Iterable<Map.Entry<Range, TxnId>>
+{
+    public static class SerializerSupport
+    {
+        private SerializerSupport() {}
+
+        public static int rangesToTxnIdsCount(RangeDeps deps)
+        {
+            return deps.rangesToTxnIds.length;
+        }
+
+        public static int rangesToTxnIds(RangeDeps deps, int idx)
+        {
+            return deps.rangesToTxnIds[idx];
+        }
+
+        public static RangeDeps create(Range[] ranges, TxnId[] txnIds, int[] rangesToTxnIds)
+        {
+            return new RangeDeps(ranges, txnIds, rangesToTxnIds);
+        }
+    }
+
+    private static final Range[] NO_RANGES = new Range[0];
+    public static final RangeDeps NONE = new RangeDeps(new Range[0], new TxnId[0], new int[0], new int[0]);
+
+    final TxnId[] txnIds;
+    // the list of ranges and their mappings to txnIds
+    // unique, and sorted by start()
+    final Range[] ranges;
+    /**
+     * See {@link RelationMultiMap}.
+     * TODO consider alternative layout depending on real-world data distributions:
+     *      if most ranges have at most TxnId (or vice-versa) might be better to use negative values
+     *      to index into the dynamic portion of the array. We started with this, but decided it was
+     *      hard to justify the extra work for two layouts for the moment.
+     */
+    final int[] rangesToTxnIds;
+    int[] txnIdsToRanges;
+
+    private SearchableRangeList searchable;
+
+    public static <T1, T2> RangeDeps merge(List<T1> merge, Function<T1, T2> getter1, Function<T2, RangeDeps> getter2)
+    {
+        try (LinearMerger<Range, TxnId, RangeDeps> linearMerger = new LinearMerger<>(ADAPTER))
+        {
+            int mergeIndex = 0, mergeSize = merge.size();
+            while (mergeIndex < mergeSize)
+            {
+                T2 intermediate = getter1.apply(merge.get(mergeIndex++));
+                if (intermediate == null)
+                    continue;
+
+                RangeDeps deps = getter2.apply(intermediate);
+                if (deps == null || deps.isEmpty())
+                    continue;
+
+                linearMerger.update(deps, deps.ranges, deps.txnIds, deps.rangesToTxnIds);
+            }
+
+            return linearMerger.get(RangeDeps::new, NONE);
+        }
+    }
+
+    private RangeDeps(Range[] ranges, TxnId[] txnIds, int[] rangesToTxnIds)
+    {
+        this(ranges, txnIds, rangesToTxnIds, null);
+    }
+
+    private RangeDeps(Range[] ranges, TxnId[] txnIds, int[] rangesToTxnIds, int[] txnIdsToRanges)
+    {
+        Invariants.checkArgument(rangesToTxnIds.length >= ranges.length);
+        Invariants.checkArgument(ranges.length > 0 || rangesToTxnIds.length == 0);
+        Invariants.paranoid(SortedArrays.isSorted(ranges, Range::compare));
+        this.ranges = ranges;
+        this.txnIds = txnIds;
+        this.rangesToTxnIds = rangesToTxnIds;
+        this.txnIdsToRanges = txnIdsToRanges;
+    }
+
+    @Inline
+    public <P1, P2, P3> int forEach(Key key, IndexedTriConsumer<P1, P2, P3> forEachScanOrCheckpoint, IndexedRangeTriConsumer<P1, P2, P3> forEachRange, P1 p1, P2 p2, P3 p3, int minIndex)
+    {
+        return ensureSearchable().forEach(key, forEachScanOrCheckpoint, forEachRange, p1, p2, p3, minIndex);
+    }
+
+    private int forEach(Key key, Consumer<TxnId> forEach, int minIndex, @Nullable BitSet visited)
+    {
+        return forEach(key, RangeDeps::visitTxnIdsForRangeIndex, RangeDeps::visitTxnIdsForRangeIndex,
+                this, forEach, visited, minIndex);
+    }
+
+    @Inline
+    public <P1, P2, P3> int forEach(Range range, IndexedTriConsumer<P1, P2, P3> forEachScanOrCheckpoint, IndexedRangeTriConsumer<P1, P2, P3> forEachRange, P1 p1, P2 p2, P3 p3, int minIndex)
+    {
+        return ensureSearchable().forEach(range, forEachScanOrCheckpoint, forEachRange, p1, p2, p3, minIndex);
+    }
+
+    private <P1, P2, P3> void forEach(Ranges ranges, IndexedTriConsumer<P1, P2, P3> forEachScanOrCheckpoint, IndexedRangeTriConsumer<P1, P2, P3> forEachRange, P1 p1, P2 p2, P3 p3)
+    {
+        int minIndex = 0;
+        for (int i = 0; i < ranges.size() ; ++i)
+            minIndex = forEach(ranges.get(i), forEachScanOrCheckpoint, forEachRange, p1, p2, p3, minIndex);
+    }
+
+    private int forEach(Range range, Consumer<TxnId> forEach, int minIndex, @Nullable BitSet visited)
+    {
+        return forEach(range, RangeDeps::visitTxnIdsForRangeIndex, RangeDeps::visitTxnIdsForRangeIndex,
+                this, forEach, visited, minIndex);
+    }
+
+    private void visitTxnIdsForRangeIndex(Consumer<TxnId> forEach, @Nullable BitSet visited, int rangeIndex)
+    {
+        for (int i = startOffset(ranges, rangesToTxnIds, rangeIndex), end = endOffset(rangesToTxnIds, rangeIndex) ; i < end ; ++i)
+            visitTxnIdx(rangesToTxnIds[i], forEach, visited);
+    }
+
+    private void visitTxnIdsForRangeIndex(Consumer<TxnId> forEach, @Nullable BitSet visited, int start, int end)
+    {
+        if (end == 0)
+            return;
+        for (int i = startOffset(ranges, rangesToTxnIds, start) ; i < endOffset(rangesToTxnIds, end - 1) ; ++i)
+            visitTxnIdx(rangesToTxnIds[i], forEach, visited);
+    }
+
+    // TODO (low priority, efficiency): ideally we would accept something like a BitHashSet or IntegerTrie
+    //   as O(N) space needed for BitSet here (but with a very low constant multiplier)
+    private void visitTxnIdx(int txnIdx, Consumer<TxnId> forEach, @Nullable BitSet visited)
+    {
+        if (visited == null || !visited.get(txnIdx))
+        {
+            if (visited != null)
+                visited.set(txnIdx);
+            forEach.accept(txnIds[txnIdx]);
+        }
+    }
+
+    /**
+     * Each matching TxnId will be provided precisely once
+     */
+    public void forEachUniqueTxnId(Key key, Consumer<TxnId> forEach)
+    {
+        forEach(key, forEach, 0, new BitSet());
+    }
+
+    /**
+     * The same TxnId may be provided as a parameter multiple times
+     */
+    public void forEach(Range range, Consumer<TxnId> forEach)
+    {
+        forEach(range, forEach, 0, null);
+    }
+
+    /**
+     * The same TxnId may be provided as a parameter multiple times
+     */
+    public void forEach(Ranges ranges, Consumer<TxnId> forEach)
+    {
+        int minIndex = 0;
+        for (int i = 0; i < ranges.size() ; ++i)
+            minIndex = forEach(ranges.get(i), forEach, minIndex, null);
+    }
+
+    /**
+     * Each matching TxnId will be provided precisely once
+     */
+    public void forEachUniqueTxnId(Range range, Consumer<TxnId> forEach)
+    {
+        forEach(range, forEach, 0, new BitSet());
+    }
+
+    /**
+     * Each matching TxnId will be provided precisely once
+     *
+     * @param ranges to match on
+     * @param forEach function to call on each unique {@link TxnId}
+     */
+    public void forEachUniqueTxnId(Ranges ranges, Consumer<TxnId> forEach)
+    {
+        int minIndex = 0;
+        for (int i = 0; i < ranges.size() ; ++i)
+            minIndex = forEach(ranges.get(i), forEach, minIndex, new BitSet());
+    }
+
+    // return true iff we map any ranges to any txnId
+    // if the mapping is empty we return false, whether or not we have any ranges or txnId by themselves
+    public boolean isEmpty()
+    {
+        return RelationMultiMap.isEmpty(ranges, rangesToTxnIds);
+    }
+
+    public Unseekables<Range, ?> someUnseekables(TxnId txnId)
+    {
+        int txnIdIndex = Arrays.binarySearch(txnIds, txnId);
+        if (txnIdIndex < 0)
+            throw new IllegalStateException("Cannot create a RouteFragment without any keys");
+
+        ensureTxnIdToRange();
+
+        int start = txnIdIndex == 0 ? txnIds.length : txnIdsToRanges[txnIdIndex - 1];
+        int end = txnIdsToRanges[txnIdIndex];
+        if (start == end)
+            throw new IllegalStateException("Cannot create a RouteFragment without any keys");
+
+        Range[] result = new Range[end - start];
+        result[0] = ranges[txnIdsToRanges[start]].toUnseekable();
+        int resultCount = 1;
+        for (int i = start + 1 ; i < end ; ++i)
+        {
+            Range next = ranges[txnIdsToRanges[i]];
+            if (!next.equals(result[resultCount - 1]))
+                result[resultCount++] = next;
+        }
+
+        if (resultCount < result.length)
+            result = Arrays.copyOf(result, resultCount);
+        return new Ranges(result);
+    }
+
+    void ensureTxnIdToRange()
+    {
+        if (txnIdsToRanges != null)
+            return;
+
+        txnIdsToRanges = invert(rangesToTxnIds, rangesToTxnIds.length, ranges.length, txnIds.length);
+    }
+
+    public RangeDeps slice(Ranges select)
+    {
+        if (isEmpty())
+            return new RangeDeps(NO_RANGES, txnIds, NO_INTS);
+
+        try (RangeAndMapCollector collector = new RangeAndMapCollector(ensureSearchable().maxScanAndCheckpointMatches))
+        {
+            forEach(select, collector, collector, ranges, rangesToTxnIds, null);
+
+            if (collector.rangesCount == 0)
+                return new RangeDeps(NO_RANGES, NO_TXNIDS, NO_INTS);
+
+            if (collector.rangesCount == this.ranges.length)
+                return this;
+
+            Range[] ranges = collector.getRanges();
+            int[] rangesToTxnIds = collector.getRangesToTxnIds();
+            TxnId[] txnIds = trimUnusedValues(ranges, this.txnIds, rangesToTxnIds, TxnId[]::new);
+            return new RangeDeps(ranges, txnIds, rangesToTxnIds);
+        }
+    }
+
+    public RangeDeps with(RangeDeps that)
+    {
+        if (isEmpty() || that.isEmpty())
+            return isEmpty() ? that : this;
+
+        return linearUnion(
+                this.ranges, this.ranges.length, this.txnIds, this.txnIds.length, this.rangesToTxnIds, this.rangesToTxnIds.length,
+                that.ranges, that.ranges.length, that.txnIds, that.txnIds.length, that.rangesToTxnIds, that.rangesToTxnIds.length,
+                rangeComparator(), TxnId::compareTo,
+                cachedRanges(), cachedTxnIds(), cachedInts(),
+                (ranges, rangesLength, txnIds, txnIdsLength, out, outLength) ->
+                        new RangeDeps(cachedRanges().complete(ranges, rangesLength),
+                                cachedTxnIds().complete(txnIds, txnIdsLength),
+                                cachedInts().complete(out, outLength))
+        );
+    }
+
+    public RangeDeps without(Predicate<TxnId> remove)
+    {
+        return remove(this, ranges, txnIds, rangesToTxnIds, remove,
+                NONE, TxnId[]::new, ranges, RangeDeps::new);
+    }
+
+    public boolean contains(TxnId txnId)
+    {
+        return Arrays.binarySearch(txnIds, txnId) >= 0;
+    }
+
+    public boolean isCoveredBy(Ranges covering)
+    {
+        // check that every entry intersects with some entry in covering
+        int prev = 0;
+        for (Range range : covering)
+        {
+            int start = SortedArrays.binarySearch(ranges, 0, ranges.length, range.start(), (a, b) -> a.compareTo(b.start()), CEIL);
+            if (start < 0) start = -1 - start;
+            int end = SortedArrays.binarySearch(ranges, 0, ranges.length, range.end(), (a, b) -> a.compareTo(b.start()), CEIL);
+            if (end < 0) end = -1 - end;
+            for (int i = prev; i < start ; ++i)
+            {
+                if (range.compareIntersecting(ranges[i]) != 0)
+                    return false;
+            }
+            prev = end;
+        }
+        return prev == ranges.length;
+    }
+
+    public List<TxnId> txnIds(Key key)
+    {
+        List<TxnId> result = new ArrayList<>();
+        forEachUniqueTxnId(key, result::add);
+        result.sort(TxnId::compareTo);
+        return result;
+    }
+
+    public List<TxnId> txnIds(Range key)
+    {
+        List<TxnId> result = new ArrayList<>();
+        forEachUniqueTxnId(key, result::add);
+        result.sort(TxnId::compareTo);
+        return result;
+    }
+
+    public TxnId txnId(int i)
+    {
+        return txnIds[i];
+    }
+
+    public int txnIdCount()
+    {
+        return txnIds.length;
+    }
+
+    public Range range(int i)
+    {
+        return ranges[i];
+    }
+
+    public int rangeCount()
+    {
+        return ranges.length;
+    }
+
+    @Override
+    public boolean equals(Object that)
+    {
+        return this == that || (that instanceof RangeDeps && equals((RangeDeps)that));
+    }
+
+    public boolean equals(RangeDeps that)
+    {
+        return testEquality(this.ranges, this.txnIds, this.rangesToTxnIds, that.ranges, that.txnIds, that.rangesToTxnIds);
+    }
+
+    @Override
+    public String toString()
+    {
+        return RelationMultiMap.toSimpleString(ranges, txnIds, rangesToTxnIds);
+    }
+
+    @Nonnull
+    @Override
+    public Iterator<Map.Entry<Range, TxnId>> iterator()
+    {
+        return newIterator(ranges, txnIds, rangesToTxnIds);
+    }
+
+    private SearchableRangeList ensureSearchable()
+    {
+        if (searchable == null)
+            buildSearchable();
+        return searchable;
+    }
+
+    @DontInline
+    private void buildSearchable()
+    {
+        searchable = SearchableRangeList.build(ranges);
+    }
+
+    public boolean isSearchable()
+    {
+        return searchable != null;
+    }
+
+    static class RangeCollector implements
+            IndexedRangeTriConsumer<Range[], int[], Object>,
+            IndexedTriConsumer<Range[], int[], Object>,
+            AutoCloseable
+    {
+        int[] oooBuffer;
+        Range[] rangesOut;
+        int oooCount, rangesCount;
+
+        RangeCollector(int maxScanAndCheckpointCount)
+        {
+            oooBuffer = cachedInts().getInts(maxScanAndCheckpointCount);
+            rangesOut = cachedRanges().get(32);
+        }
+
+        @Override
+        public void accept(Range[] o, int[] o2, Object o3, int index)
+        {
+            oooBuffer[oooCount++] = index;
+        }
+
+        @Override
+        public void accept(Range[] ranges, int[] rangesToTxnIds, Object o3, int fromIndex, int toIndex)
+        {
+            if (oooCount > 0)
+            {
+                Arrays.sort(oooBuffer, 0, oooCount);
+                int oooCount = Arrays.binarySearch(oooBuffer, 0, this.oooCount, fromIndex);
+                if (oooCount < 0) oooCount = -1 - oooCount;
+                copy(ranges, rangesToTxnIds, oooCount, fromIndex, toIndex);
+                this.oooCount = 0;
+            }
+            else if (fromIndex < toIndex)
+            {
+                copy(ranges, rangesToTxnIds, 0, fromIndex, toIndex);
+            }
+        }
+
+        protected void copy(Range[] ranges, int[] rangesToTxnIds, int oooCount, int start, int end)
+        {
+            int count = oooCount + (end - start);
+            if (rangesCount + count >= rangesOut.length)
+                rangesOut = cachedRanges().resize(rangesOut, rangesCount, rangesCount + count + (rangesCount /2));
+            for (int i = 0 ; i < oooCount ; ++i)
+                rangesOut[rangesCount++] = ranges[oooBuffer[i]];
+            for (int i = start ; i < end ; ++i)
+                rangesOut[rangesCount++] = ranges[i];
+        }
+
+        Range[] getRanges()
+        {
+            Range[] result = cachedRanges().completeAndDiscard(rangesOut, rangesCount);
+            rangesOut = null;
+            return result;
+        }
+
+        @Override
+        public void close()
+        {
+            if (oooBuffer != null)
+            {
+                cachedInts().forceDiscard(oooBuffer);
+                oooBuffer = null;
+            }
+            if (rangesOut != null)
+            {
+                cachedRanges().forceDiscard(rangesOut, rangesCount);
+                rangesOut = null;
+            }
+        }
+    }
+
+    static class RangeAndMapCollector extends RangeCollector
+    {
+        int[] headers;
+        int[] lists;
+        int headerCount, listOffset;
+
+        RangeAndMapCollector(int maxScanAndCheckpointCount)
+        {
+            super(maxScanAndCheckpointCount);
+            headers = cachedInts().getInts(32);
+            lists = cachedInts().getInts(32);
+        }
+
+        @Override
+        protected void copy(Range[] ranges, int[] rangesToTxnIds, int oooCount, int start, int end)
+        {
+            super.copy(ranges, rangesToTxnIds, oooCount, start, end);
+            int count = oooCount + (end - start);
+            if (headerCount + count >= headers.length)
+                headers = cachedInts().resize(headers, headerCount, headerCount + count + (headerCount /2));
+            for (int i = 0 ; i < oooCount ; ++i)
+            {
+                int ri = oooBuffer[i];
+                copyToDynamic(rangesToTxnIds, startOffset(ranges, rangesToTxnIds, ri), endOffset(rangesToTxnIds, ri));
+                headers[headerCount++] = listOffset;
+            }
+            int startOffset = startOffset(ranges, rangesToTxnIds, start);
+            for (int i = start ; i < end ; ++i)
+                headers[this.headerCount++] = listOffset + rangesToTxnIds[i] - startOffset;
+            copyToDynamic(rangesToTxnIds, startOffset, startOffset(ranges, rangesToTxnIds, end));
+        }
+
+        protected void copyToDynamic(int[] rangesToTxnIds, int start, int end)
+        {
+            int count = end - start;
+            if (count + listOffset >= lists.length)
+                lists = cachedInts().resize(lists, listOffset, listOffset + (listOffset /2) + count);
+            System.arraycopy(rangesToTxnIds, start, lists, listOffset, count);
+            listOffset += count;
+        }
+
+        public int[] getRangesToTxnIds()
+        {
+            int[] out = new int[headerCount + listOffset];
+            for (int i = 0; i < headerCount; ++i)
+                out[i] = headers[i] + headerCount;
+            System.arraycopy(lists, 0, out, headerCount, listOffset);
+            return out;
+        }
+    }
+
+    public static RangeDeps of(Map<TxnId, Ranges> txnIdRanges)
+    {
+        if (txnIdRanges.isEmpty())
+            return NONE;
+
+        try (BuilderByTxnId builder = new BuilderByTxnId())
+        {
+            for (Map.Entry<TxnId, Ranges> e : txnIdRanges.entrySet())
+            {
+                builder.nextKey(e.getKey());
+                Ranges ranges = e.getValue();
+                for (int i = 0 ; i < ranges.size() ; ++i)
+                    builder.add(ranges.get(i));
+            }
+            return builder.build();
+        }
+    }
+
+    public static Builder builder()
+    {
+        return new Builder();
+    }
+
+    public static class Builder extends AbstractBuilder<Range, TxnId, RangeDeps>
+    {
+        public Builder()
+        {
+            super(ADAPTER);
+        }
+
+        @Override
+        protected RangeDeps none()
+        {
+            return RangeDeps.NONE;
+        }
+
+        @Override
+        protected RangeDeps build(Range[] ranges, TxnId[] txnIds, int[] keyToValue)
+        {
+            return new RangeDeps(ranges, txnIds, keyToValue);
+        }
+    }
+
+    public static BuilderByTxnId byTxnIdBuilder()
+    {
+        return new BuilderByTxnId();
+    }
+
+    public static class BuilderByTxnId extends AbstractBuilder<TxnId, Range, RangeDeps>
+    {
+        public BuilderByTxnId()
+        {
+            super(REVERSE_ADAPTER);
+        }
+
+        @Override
+        protected RangeDeps none()
+        {
+            return RangeDeps.NONE;
+        }
+
+        @Override
+        protected RangeDeps build(TxnId[] txnIds, Range[] ranges, int[] txnIdsToRanges)
+        {
+            return new RangeDeps(ranges, txnIds, invert(txnIdsToRanges, txnIdsToRanges.length, txnIds.length, ranges.length), txnIdsToRanges);
+        }
+    }
+
+    public static SymmetricComparator<? super Range> rangeComparator()
+    {
+        return RangeDeps::compare;
+    }
+
+    public static int compare(Range left, Range right)
+    {
+        int c = left.start().compareTo(right.start());
+        if (c == 0) c = left.end().compareTo(right.end());
+        return c;
+    }
+
+    private static final RangeDepsAdapter ADAPTER = new RangeDepsAdapter();
+    private static final class RangeDepsAdapter implements Adapter<Range, TxnId>
+    {
+        @Override
+        public SymmetricComparator<? super Range> keyComparator()
+        {
+            return rangeComparator();
+        }
+
+        @Override
+        public SymmetricComparator<? super TxnId> valueComparator()
+        {
+            return TxnId::compareTo;
+        }
+
+        @Override
+        public ObjectBuffers<Range> cachedKeys()
+        {
+            return ArrayBuffers.cachedRanges();
+        }
+
+        @Override
+        public ObjectBuffers<TxnId> cachedValues()
+        {
+            return ArrayBuffers.cachedTxnIds();
+        }
+    }
+
+    private static final ReverseRangeDepsAdapter REVERSE_ADAPTER = new ReverseRangeDepsAdapter();
+    private static final class ReverseRangeDepsAdapter implements Adapter<TxnId, Range>
+    {
+        @Override
+        public SymmetricComparator<? super TxnId> keyComparator()
+        {
+            return TxnId::compareTo;
+        }
+
+        @Override
+        public SymmetricComparator<? super Range> valueComparator()
+        {
+            return rangeComparator();
+        }
+
+        @Override
+        public ObjectBuffers<TxnId> cachedKeys()
+        {
+            return ArrayBuffers.cachedTxnIds();
+        }
+
+        @Override
+        public ObjectBuffers<Range> cachedValues()
+        {
+            return ArrayBuffers.cachedRanges();
+        }
+    }
+
+}
diff --git a/accord-core/src/main/java/accord/primitives/Ranges.java b/accord-core/src/main/java/accord/primitives/Ranges.java
index 6101195..2b8a2bc 100644
--- a/accord-core/src/main/java/accord/primitives/Ranges.java
+++ b/accord-core/src/main/java/accord/primitives/Ranges.java
@@ -128,7 +128,7 @@ public class Ranges extends AbstractRanges<Ranges> implements Iterable<Range>, S
     }
 
     /**
-     * Subtracts the given set of key ranges from this
+     * Subtracts the given set of ranges from this
      */
     public Ranges difference(AbstractRanges<?> that)
     {
diff --git a/accord-core/src/main/java/accord/primitives/RoutableKey.java b/accord-core/src/main/java/accord/primitives/RoutableKey.java
index f8de9d6..c48124d 100644
--- a/accord-core/src/main/java/accord/primitives/RoutableKey.java
+++ b/accord-core/src/main/java/accord/primitives/RoutableKey.java
@@ -44,10 +44,13 @@ public interface RoutableKey extends Routable, Comparable<RoutableKey>
      * @param that the object to be compared.
      * @return
      */
+    @Override
     int compareTo(@Nonnull RoutableKey that);
 
+    @Override
     default Domain domain() { return Domain.Key; }
 
+    @Override
     RoutingKey toUnseekable();
 
     @Override default RoutingKey someIntersectingRoutingKey() { return toUnseekable(); }
diff --git a/accord-core/src/main/java/accord/primitives/Route.java b/accord-core/src/main/java/accord/primitives/Route.java
index a349b4e..01b5ebd 100644
--- a/accord-core/src/main/java/accord/primitives/Route.java
+++ b/accord-core/src/main/java/accord/primitives/Route.java
@@ -10,8 +10,11 @@ public interface Route<K extends Unseekable> extends Unseekables<K, Route<K>>
 
     default boolean isRoute() { return true; }
     boolean covers(Ranges ranges);
+    @Override
     boolean intersects(AbstractRanges<?> ranges);
+    @Override
     Route<K> union(Route<K> route);
+    @Override
     PartialRoute<K> slice(Ranges ranges);
     PartialRoute<K> sliceStrict(Ranges ranges);
 
diff --git a/accord-core/src/main/java/accord/primitives/RoutingKeys.java b/accord-core/src/main/java/accord/primitives/RoutingKeys.java
index fd30ecf..0e29954 100644
--- a/accord-core/src/main/java/accord/primitives/RoutingKeys.java
+++ b/accord-core/src/main/java/accord/primitives/RoutingKeys.java
@@ -5,7 +5,7 @@ import accord.utils.SortedArrays;
 
 import static accord.utils.ArrayBuffers.cachedRoutingKeys;
 
-public class RoutingKeys extends AbstractRoutableKeys<AbstractRoutableKeys<?>> implements Unseekables<RoutingKey, AbstractRoutableKeys<?>>
+public class RoutingKeys extends AbstractUnseekableKeys<AbstractUnseekableKeys<?>> implements Unseekables<RoutingKey, AbstractUnseekableKeys<?>>
 {
     public static class SerializationSupport
     {
@@ -27,11 +27,13 @@ public class RoutingKeys extends AbstractRoutableKeys<AbstractRoutableKeys<?>> i
         return new RoutingKeys(sort(keys));
     }
 
-    public RoutingKeys union(AbstractRoutableKeys<?> that)
+    @Override
+    public RoutingKeys union(AbstractUnseekableKeys<?> that)
     {
         return wrap(SortedArrays.linearUnion(keys, that.keys, cachedRoutingKeys()), that);
     }
 
+    @Override
     public RoutingKeys with(RoutingKey with)
     {
         if (contains(with))
@@ -45,6 +47,7 @@ public class RoutingKeys extends AbstractRoutableKeys<AbstractRoutableKeys<?>> i
         return UnseekablesKind.RoutingKeys;
     }
 
+    @Override
     public RoutingKeys slice(Ranges ranges)
     {
         return wrap(slice(ranges, RoutingKey[]::new));
diff --git a/accord-core/src/main/java/accord/primitives/Seekable.java b/accord-core/src/main/java/accord/primitives/Seekable.java
index cc84767..f702353 100644
--- a/accord-core/src/main/java/accord/primitives/Seekable.java
+++ b/accord-core/src/main/java/accord/primitives/Seekable.java
@@ -1,8 +1,12 @@
 package accord.primitives;
 
+import accord.api.Key;
+
 /**
  * Something that can be found within the cluster AND found on disk, queried and returned
  */
 public interface Seekable extends Routable
 {
+    Key asKey();
+    Range asRange();
 }
diff --git a/accord-core/src/main/java/accord/primitives/Seekables.java b/accord-core/src/main/java/accord/primitives/Seekables.java
index da3a532..0bed766 100644
--- a/accord-core/src/main/java/accord/primitives/Seekables.java
+++ b/accord-core/src/main/java/accord/primitives/Seekables.java
@@ -7,7 +7,9 @@ import accord.api.RoutingKey;
  */
 public interface Seekables<K extends Seekable, U extends Seekables<K, ?>> extends Routables<K, U>
 {
+    @Override
     U slice(Ranges ranges);
+    @Override
     Seekables<K, U> union(U with);
     Unseekables<?, ?> toUnseekables();
 
diff --git a/accord-core/src/main/java/accord/primitives/TxnId.java b/accord-core/src/main/java/accord/primitives/TxnId.java
index e2b40bb..5f51c20 100644
--- a/accord-core/src/main/java/accord/primitives/TxnId.java
+++ b/accord-core/src/main/java/accord/primitives/TxnId.java
@@ -82,6 +82,7 @@ public class TxnId extends Timestamp
         return domain(flags());
     }
 
+    @Override
     public TxnId merge(Timestamp that)
     {
         return merge(this, that, TxnId::fromBits);
diff --git a/accord-core/src/main/java/accord/primitives/Unseekables.java b/accord-core/src/main/java/accord/primitives/Unseekables.java
index 68e0206..8cdb2ee 100644
--- a/accord-core/src/main/java/accord/primitives/Unseekables.java
+++ b/accord-core/src/main/java/accord/primitives/Unseekables.java
@@ -22,7 +22,9 @@ public interface Unseekables<K extends Unseekable, U extends Unseekables<K, ?>>
         }
     }
 
+    @Override
     U slice(Ranges ranges);
+    @Override
     Unseekables<K, U> union(U with);
     Unseekables<K, ?> with(RoutingKey withKey);
     UnseekablesKind kind();
diff --git a/accord-core/src/main/java/accord/primitives/package-info.java b/accord-core/src/main/java/accord/primitives/package-info.java
index f25136d..f75bcb8 100644
--- a/accord-core/src/main/java/accord/primitives/package-info.java
+++ b/accord-core/src/main/java/accord/primitives/package-info.java
@@ -1,9 +1,11 @@
 package accord.primitives;
 
 /**
- * Routable: a RoutingKey or Range (of RoutingKey). Something that can address a replica in the cluster.
+ * Routable: a RoutingKey, Key or Range. Something that can address a replica in the cluster.
+ * Unseekable: a RoutingKey or Range (of RoutingKey). Something that can ONLY address a replica in the cluster.
  * Seekable: a Key or Range (of either RoutingKey or Key). Something that can address some physical data on a node.
  * Routables: a collection of Routable
+ * Unseekables: a collection of Unseekable
  * Seekables: a collection of Seekable
  * Route: a collection of Routable including a homeKey. Represents a consistent slice (or slices) of token ranges.
  *        Either a PartialRoute or a FullRoute.
diff --git a/accord-core/src/main/java/accord/topology/Topology.java b/accord-core/src/main/java/accord/topology/Topology.java
index a502bd4..c055a82 100644
--- a/accord-core/src/main/java/accord/topology/Topology.java
+++ b/accord-core/src/main/java/accord/topology/Topology.java
@@ -177,7 +177,7 @@ public class Topology
         return info != null ? info.ranges : Ranges.EMPTY;
     }
 
-    // TODO: optimised HomeKey concept containing the Key, Shard and Topology to avoid lookups when topology hasn't changed
+    // TODO (low priority, efficiency): optimised HomeKey concept containing the Key, Shard and Topology to avoid lookups when topology hasn't changed
     public Shard forKey(RoutingKey key)
     {
         int i = ranges.indexOf(key);
@@ -294,7 +294,7 @@ public class Topology
         }
         catch (Throwable t)
         {
-            cachedInts.forceDiscard(newSubset, count);
+            cachedInts.forceDiscard(newSubset);
             throw t;
         }
 
diff --git a/accord-core/src/main/java/accord/utils/ArrayBuffers.java b/accord-core/src/main/java/accord/utils/ArrayBuffers.java
index d1ad72a..c021f25 100644
--- a/accord-core/src/main/java/accord/utils/ArrayBuffers.java
+++ b/accord-core/src/main/java/accord/utils/ArrayBuffers.java
@@ -90,13 +90,30 @@ public class ArrayBuffers
     public interface IntBufferAllocator
     {
         /**
-         * Return an {@code int[]} of size at least {@code minSize}, possibly from a pool
+         * Return an {@code int[]} of size at least {@code minSize}, possibly from a pool.
+         * This array may not be zero initialized, and its contents should be treated as random.
          */
         int[] getInts(int minSize);
     }
 
     public interface IntBuffers extends IntBufferAllocator
     {
+        /**
+         * Return an {@code int[]} of size at least {@code minSize}, possibly from a pool,
+         * and copy the contents of {@code copyAndDiscard} into it.
+         *
+         * The remainder of the array may not be zero-initialized, and should be assumed to contain random data.
+         *
+         * The parameter will be returned to the pool, if eligible.
+         */
+        default int[] resize(int[] copyAndDiscard, int usedSize, int minSize)
+        {
+            int[] newBuf = getInts(minSize);
+            System.arraycopy(copyAndDiscard, 0, newBuf, 0, usedSize);
+            forceDiscard(copyAndDiscard);
+            return newBuf;
+        }
+
         /**
          * To be invoked on the result buffer with the number of elements contained;
          * either the buffer will be returned and the size optionally captured, or else the result may be
@@ -134,29 +151,59 @@ public class ArrayBuffers
          * Indicate this buffer is definitely unused, and return it to a pool if possible
          * @return true if the buffer is discarded (and discard-able), false if it was retained
          */
-        boolean forceDiscard(int[] buffer, int usedSize);
+        boolean forceDiscard(int[] buffer);
     }
 
     public interface ObjectBuffers<T>
     {
         /**
-         * Return an {@code T[]} of size at least {@code minSize}, possibly from a pool
+         * Return an {@code T[]} of size at least {@code minSize}, possibly from a pool.
+         * This array will be null-initialized and can be assumed to be empty.
          */
         T[] get(int minSize);
 
+        /**
+         * Return an {@code T[]} of size at least {@code minSize}, possibly from a pool,
+         * and copy the contents of {@code copyAndDiscard} into it.
+         *
+         * The remainder of the array can be assumed to be null initialized.
+         *
+         * The parameter will be returned to the pool, if eligible.
+         */
+        default T[] resize(T[] copyAndDiscard, int usedSize, int minSize)
+        {
+            T[] newBuf = get(minSize);
+            System.arraycopy(copyAndDiscard, 0, newBuf, 0, usedSize);
+            forceDiscard(copyAndDiscard, usedSize);
+            return newBuf;
+        }
+
         /**
          * To be invoked on the result buffer with the number of elements contained;
          * either the buffer will be returned and the size optionally captured, or else the result may be
          * shrunk to the size of the contents, depending on implementation.
          */
-        T[] complete(T[] buffer, int size);
+        T[] complete(T[] buffer, int usedSize);
+
+        /**
+         * Equivalent to
+         *   int[] result = complete(buffer, usedSize);
+         *   discard(buffer, usedSize);
+         *   return result;
+         */
+        default T[] completeAndDiscard(T[] buffer, int usedSize)
+        {
+            T[] result = complete(buffer, usedSize);
+            discard(buffer, usedSize);
+            return result;
+        }
 
         /**
          * To be invoked on an input buffer that constitutes the result, with the number of elements it contained;
          * either the buffer will be returned and the size optionally captured, or else the result may be
          * shrunk to the size of the contents, depending on implementation.
          */
-        T[] completeWithExisting(T[] buffer, int size);
+        T[] completeWithExisting(T[] buffer, int usedSize);
 
         /**
          * The buffer is no longer needed by the caller, which is discarding the array;
@@ -172,7 +219,7 @@ public class ArrayBuffers
          *
          * @return true if the buffer is discarded (and discard-able), false if it was retained or is believed to be in use
          */
-        boolean discard(T[] buffer, int size);
+        boolean discard(T[] buffer, int usedSize);
 
         /**
          * Indicate this buffer is definitely unused, and return it to a pool if possible
@@ -181,7 +228,7 @@ public class ArrayBuffers
          *
          * @return true if the buffer is discarded (and discard-able), false if it was retained
          */
-        boolean forceDiscard(T[] buffer, int size);
+        boolean forceDiscard(T[] buffer, int usedSize);
 
         /**
          * Returns the {@code size} parameter provided to the most recent {@link #complete(Object[], int)} or {@link #completeWithExisting(Object[], int)}
@@ -216,11 +263,11 @@ public class ArrayBuffers
         @Override
         public boolean discard(int[] buffer, int usedSize)
         {
-            return forceDiscard(buffer, usedSize);
+            return forceDiscard(buffer);
         }
 
         @Override
-        public boolean forceDiscard(int[] buffer, int usedSize)
+        public boolean forceDiscard(int[] buffer)
         {
             // if FULLY_UNCACHED we want our caller to also not cache us, so we indicate the buffer has been retained
             return !FULLY_UNCACHED;
@@ -242,18 +289,18 @@ public class ArrayBuffers
         }
 
         @Override
-        public T[] complete(T[] buffer, int size)
+        public T[] complete(T[] buffer, int usedSize)
         {
-            if (size == buffer.length)
+            if (usedSize == buffer.length)
                 return buffer;
 
-            return Arrays.copyOf(buffer, size);
+            return Arrays.copyOf(buffer, usedSize);
         }
 
         @Override
-        public T[] completeWithExisting(T[] buffer, int size)
+        public T[] completeWithExisting(T[] buffer, int usedSize)
         {
-            return checkArgument(buffer, buffer.length == size);
+            return checkArgument(buffer, buffer.length == usedSize);
         }
 
         @Override
@@ -263,13 +310,13 @@ public class ArrayBuffers
         }
 
         @Override
-        public boolean discard(T[] buffer, int size)
+        public boolean discard(T[] buffer, int usedSize)
         {
-            return forceDiscard(buffer, size);
+            return forceDiscard(buffer, usedSize);
         }
 
         @Override
-        public boolean forceDiscard(T[] buffer, int size)
+        public boolean forceDiscard(T[] buffer, int usedSize)
         {
             // if FULLY_UNCACHED we want our caller to also not cache us, so we indicate the buffer has been retained
             return !FULLY_UNCACHED;
@@ -368,9 +415,9 @@ public class ArrayBuffers
         }
 
         @Override
-        public boolean forceDiscard(int[] buffer, int usedSize)
+        public boolean forceDiscard(int[] buffer)
         {
-            return discardInternal(buffer, buffer.length, usedSize, true);
+            return discardInternal(buffer, buffer.length, -1, true);
         }
 
         @Override
@@ -390,34 +437,37 @@ public class ArrayBuffers
             this.allocator = allocator;
         }
 
-        public T[] complete(T[] buffer, int size)
+        @Override
+        public T[] complete(T[] buffer, int usedSize)
         {
-            if (size == buffer.length)
+            if (usedSize == buffer.length)
                 return buffer;
 
-            return Arrays.copyOf(buffer, size);
+            return Arrays.copyOf(buffer, usedSize);
         }
 
         @Override
-        public T[] completeWithExisting(T[] buffer, int size)
+        public T[] completeWithExisting(T[] buffer, int usedSize)
         {
             return buffer;
         }
 
+        @Override
         public int lengthOfLast(T[] buffer)
         {
             return buffer.length;
         }
 
-        public boolean discard(T[] buffer, int size)
+        @Override
+        public boolean discard(T[] buffer, int usedSize)
         {
-            return discardInternal(buffer, buffer.length, size, false);
+            return discardInternal(buffer, buffer.length, usedSize, false);
         }
 
         @Override
-        public boolean forceDiscard(T[] buffer, int size)
+        public boolean forceDiscard(T[] buffer, int usedSize)
         {
-            return discardInternal(buffer, buffer.length, size, true);
+            return discardInternal(buffer, buffer.length, usedSize, true);
         }
 
         @Override
@@ -455,16 +505,16 @@ public class ArrayBuffers
         }
 
         @Override
-        public T[] complete(T[] buffer, int size)
+        public T[] complete(T[] buffer, int usedSize)
         {
-            length = size;
+            length = usedSize;
             return buffer;
         }
 
         @Override
-        public T[] completeWithExisting(T[] buffer, int size)
+        public T[] completeWithExisting(T[] buffer, int usedSize)
         {
-            length = size;
+            length = usedSize;
             return buffer;
         }
 
@@ -477,16 +527,16 @@ public class ArrayBuffers
         }
 
         @Override
-        public boolean discard(T[] buffer, int size)
+        public boolean discard(T[] buffer, int usedSize)
         {
             return true;
         }
 
         @Override
-        public boolean forceDiscard(T[] buffer, int size)
+        public boolean forceDiscard(T[] buffer, int usedSize)
         {
             length = -1;
-            if (!objs.forceDiscard(buffer, size))
+            if (!objs.forceDiscard(buffer, usedSize))
                 return false;
 
             return discardInternal(buffer);
@@ -513,6 +563,7 @@ public class ArrayBuffers
             return true;
         }
 
+        @Override
         public int lengthOfLast(T[] buffer)
         {
             if (length == -1)
@@ -561,9 +612,9 @@ public class ArrayBuffers
         }
 
         @Override
-        public boolean forceDiscard(int[] buffer, int usedSize)
+        public boolean forceDiscard(int[] buffer)
         {
-            if (!ints.forceDiscard(buffer, usedSize))
+            if (!ints.forceDiscard(buffer))
                 return false;
 
             if (savedInts != null && savedInts.length >= buffer.length)
diff --git a/accord-core/src/main/java/accord/utils/DeterministicIdentitySet.java b/accord-core/src/main/java/accord/utils/DeterministicIdentitySet.java
index e380e39..1bb9410 100644
--- a/accord-core/src/main/java/accord/utils/DeterministicIdentitySet.java
+++ b/accord-core/src/main/java/accord/utils/DeterministicIdentitySet.java
@@ -105,6 +105,7 @@ public class DeterministicIdentitySet<T> extends AbstractSet<T>
     }
 
     // we add to the front, and iterate in reverse order, so that we can add and remove while iterating without modifying the set we iterate over
+    @Override
     public boolean add(T item)
     {
         Entry<T> entry = lookup.computeIfAbsent(item, Entry::new);
@@ -117,6 +118,7 @@ public class DeterministicIdentitySet<T> extends AbstractSet<T>
         return true;
     }
 
+    @Override
     public boolean remove(Object item)
     {
         Entry<T> entry = lookup.remove(item);
@@ -129,6 +131,7 @@ public class DeterministicIdentitySet<T> extends AbstractSet<T>
         return true;
     }
 
+    @Override
     public void forEach(Consumer<? super T> consumer)
     {
         Entry<T> cur = head.next;
@@ -152,10 +155,4 @@ public class DeterministicIdentitySet<T> extends AbstractSet<T>
             cur = cur.next;
         }
     }
-
-    @Override
-    public String toString()
-    {
-        return super.toString();
-    }
 }
diff --git a/accord-core/src/main/java/accord/utils/IntrusiveLinkedList.java b/accord-core/src/main/java/accord/utils/IntrusiveLinkedList.java
index 8b822e9..b9cefb4 100644
--- a/accord-core/src/main/java/accord/utils/IntrusiveLinkedList.java
+++ b/accord-core/src/main/java/accord/utils/IntrusiveLinkedList.java
@@ -77,6 +77,7 @@ public class IntrusiveLinkedList<O extends IntrusiveLinkedListNode> extends Intr
         return next == this;
     }
 
+    @Override
     public Iterator<O> iterator()
     {
         return new Iterator<O>()
diff --git a/accord-core/src/main/java/accord/utils/MapReduce.java b/accord-core/src/main/java/accord/utils/MapReduce.java
index 5cc4adc..ac6ddf8 100644
--- a/accord-core/src/main/java/accord/utils/MapReduce.java
+++ b/accord-core/src/main/java/accord/utils/MapReduce.java
@@ -5,6 +5,7 @@ import java.util.function.Function;
 public interface MapReduce<I, O> extends Function<I, O>
 {
     // TODO (desired, safety): ensure mutual exclusivity when calling each of these methods
+    @Override
     O apply(I in);
     O reduce(O o1, O o2);
 }
diff --git a/accord-core/src/main/java/accord/utils/MapReduceConsume.java b/accord-core/src/main/java/accord/utils/MapReduceConsume.java
index c0a2f92..5ec710b 100644
--- a/accord-core/src/main/java/accord/utils/MapReduceConsume.java
+++ b/accord-core/src/main/java/accord/utils/MapReduceConsume.java
@@ -5,6 +5,7 @@ import java.util.function.Consumer;
 
 public interface MapReduceConsume<I, O> extends MapReduce<I, O>, BiConsumer<O, Throwable>
 {
+    @Override
     void accept(O result, Throwable failure);
 
     static <I> MapReduceConsume<I, Void> forEach(Consumer<I> forEach, BiConsumer<Object, Throwable> consume)
diff --git a/accord-core/src/main/java/accord/utils/RelationMultiMap.java b/accord-core/src/main/java/accord/utils/RelationMultiMap.java
new file mode 100644
index 0000000..cd3c8fb
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/RelationMultiMap.java
@@ -0,0 +1,1004 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package accord.utils;
+
+import accord.primitives.*;
+import net.nicoulaj.compilecommand.annotations.Inline;
+
+import java.util.*;
+import java.util.function.IntFunction;
+import java.util.function.Predicate;
+import java.util.stream.Collectors;
+
+import static accord.utils.ArrayBuffers.*;
+import static accord.utils.SortedArrays.remap;
+import static accord.utils.SortedArrays.remapToSuperset;
+
+/**
+ * Instead of creating a parent object and having generic key/value methods, we introduce a bunch of static helper methods.
+ * This class helps maintain three sorted arrays: keys (of type K[]), values (of type V[]) and keysToValues (of type int[])
+ * <p>
+ * keysToValues represents a map of {@code Key -> [Value] } where each Value is a pointer into a sorted values array.
+ * The beginning of the array (the first keys.length entries) are offsets into this array.
+ * <p>
+ * Example:
+ * <p>
+ * {@code
+ *   int keyIdx = Arrays.binarySearch(keys, key);
+ *   int startOfValues = keyIdx == 0 ? keys.length : keysToValues[keyIdx - 1];
+ *   int endOfValues = keysToValues[keyIdx];
+ *   for (int i = startOfValues; i < endOfValues; i++)
+ *   {
+ *       V id = value[keysToValues[i]]
+ *       ...
+ *   }
+ * }
+ */
+public class RelationMultiMap
+{
+    private static final boolean DEBUG_CHECKS = true;
+    public static final int[] NO_INTS = new int[0];
+    public static final TxnId[] NO_TXNIDS = new TxnId[0];
+
+    /**
+     * Turn a set of key, value and mapping buffers into a merge result;
+     * K and V are either Key and TxnId, or vice versa, depending on which mapping direction was present
+     */
+    public interface Constructor<K, V, T>
+    {
+        T construct(K[] keys, int keysLength, V[] values, int valuesLength, int[] out, int outLength);
+    }
+    public interface SimpleConstructor<K, V, T>
+    {
+        T construct(K keys, V values, int[] out);
+    }
+
+    public interface Adapter<K, V>
+    {
+        SymmetricComparator<? super K> keyComparator();
+        SymmetricComparator<? super V> valueComparator();
+        ObjectBuffers<K> cachedKeys();
+        ObjectBuffers<V> cachedValues();
+    }
+
+
+    // TODO (expected, efficiency): cache this object per thread
+    public static abstract class AbstractBuilder<K, V, T> implements AutoCloseable
+    {
+        final Adapter<K, V> adapter;
+        final ObjectBuffers<K> cachedKeys;
+        final ObjectBuffers<V> cachedValues;
+        final IntBuffers cachedInts = cachedInts();
+
+        K[] keys;
+        int[] keyLimits;
+        // txnId -> Offset
+        V[] keysToValues;
+        int keyCount;
+        int keyOffset;
+        int totalCount;
+        boolean hasOrderedKeys = true;
+        boolean hasOrderedValues = true;
+
+        public AbstractBuilder(Adapter<K, V> adapter)
+        {
+            this.adapter = adapter;
+            this.cachedKeys = adapter.cachedKeys();
+            this.cachedValues = adapter.cachedValues();
+            this.keys = cachedKeys.get(16);
+            this.keyLimits = cachedInts.getInts(keys.length);
+            this.keysToValues = cachedValues.get(16);
+        }
+
+        public boolean isEmpty()
+        {
+            return totalCount() == 0;
+        }
+
+        private int totalCount()
+        {
+            return totalCount;
+        }
+
+        public void nextKey(K key)
+        {
+            if (keyCount > 0 && adapter.keyComparator().compare(keys[keyCount - 1], key) >= 0)
+                hasOrderedKeys = false;
+
+            finishKey();
+
+            if (keyCount == keys.length)
+            {
+                K[] newKeys = cachedKeys.get(keyCount * 2);
+                System.arraycopy(keys, 0, newKeys, 0, keyCount);
+                cachedKeys.forceDiscard(keys, keyCount);
+                keys = newKeys;
+                int[] newKeyLimits = cachedInts.getInts(keyCount * 2);
+                System.arraycopy(keyLimits, 0, newKeyLimits, 0, keyCount);
+                cachedInts.forceDiscard(keyLimits);
+                keyLimits = newKeyLimits;
+            }
+            keys[keyCount++] = key;
+            hasOrderedValues = true;
+        }
+
+        private void finishKey()
+        {
+            if (totalCount == keyOffset && keyCount > 0)
+            {
+                --keyCount; // remove this key; no data
+                return;
+            }
+
+            if (keyCount == 0)
+                return;
+
+            if (!hasOrderedValues)
+            {
+                // TODO (low priority, efficiency): this allocates a significant amount of memory: would be preferable to be able to sort using a pre-defined scratch buffer
+                Arrays.sort(keysToValues, keyOffset, totalCount);
+                for (int i = keyOffset + 1 ; i < totalCount ; ++i)
+                {
+                    if (keysToValues[i - 1].equals(keysToValues[i]))
+                        throw new IllegalArgumentException("TxnId for " + keys[keyCount - 1] + " are not unique: " + Arrays.asList(keysToValues).subList(keyOffset, totalCount));
+                }
+            }
+
+            keyLimits[keyCount - 1] = totalCount;
+            keyOffset = totalCount;
+        }
+
+        public void add(K key, V value)
+        {
+            if (keyCount == 0 || !keys[keyCount - 1].equals(key))
+                nextKey(key);
+            add(value);
+        }
+
+        /**
+         * Add this command as a dependency for each intersecting key
+         */
+        public void add(V value)
+        {
+            if (hasOrderedValues && totalCount > keyOffset && adapter.valueComparator().compare(keysToValues[totalCount - 1], value) >= 0)
+                hasOrderedValues = false;
+
+            if (totalCount >= keysToValues.length)
+            {
+                V[] newValues = cachedValues.get(keysToValues.length * 2);
+                System.arraycopy(keysToValues, 0, newValues, 0, totalCount);
+                cachedValues.forceDiscard(keysToValues, totalCount);
+                keysToValues = newValues;
+            }
+
+            keysToValues[totalCount++] = value;
+        }
+
+        public T build()
+        {
+            if (totalCount == 0)
+                return none();
+
+            finishKey();
+
+            V[] uniqueValues = cachedValues.get(totalCount);
+            System.arraycopy(keysToValues, 0, uniqueValues, 0, totalCount);
+            Arrays.sort(uniqueValues, 0, totalCount, adapter.valueComparator());
+            int valueCount = 1;
+            for (int i = 1 ; i < totalCount ; ++i)
+            {
+                if (!uniqueValues[valueCount - 1].equals(uniqueValues[i]))
+                    uniqueValues[valueCount++] = uniqueValues[i];
+            }
+
+            V[] values = cachedValues.complete(uniqueValues, valueCount);
+            cachedValues.discard(uniqueValues, totalCount);
+
+            int[] sortedKeyIndexes;
+            K[] sortedKeys;
+            if (hasOrderedKeys)
+            {
+                sortedKeyIndexes = null;
+                sortedKeys = cachedKeys.completeAndDiscard(keys, keyCount);
+            }
+            else
+            {
+                sortedKeyIndexes = new int[keyCount];
+                sortedKeys = Arrays.copyOf(keys, keyCount);
+                Arrays.sort(sortedKeys);
+
+                for (int i = 1 ; i < keyCount ; ++i)
+                {
+                    if (sortedKeys[i-1].equals(sortedKeys[i]))
+                        throw new IllegalArgumentException("Key " + sortedKeys[i] + " has been visited more than once ("
+                                + Arrays.toString(Arrays.copyOf(keys, keyCount)) + ")");
+                }
+                for (int i = 0 ; i < keyCount ; ++i)
+                    sortedKeyIndexes[Arrays.binarySearch(sortedKeys, keys[i])] = i;
+                cachedKeys.forceDiscard(keys, keyCount);
+            }
+
+            int[] result = new int[keyCount + totalCount];
+            int offset = keyCount;
+            for (int ki = 0 ; ki < keyCount ; ++ki)
+            {
+                int k = sortedKeyIndexes == null ? ki : sortedKeyIndexes[ki];
+                int from = k == 0 ? 0 : keyLimits[k - 1];
+                int to = keyLimits[k];
+                offset = (int)SortedArrays.foldlIntersection(adapter.valueComparator(), values, 0, valueCount, keysToValues, from, to, (key, p, v, li, ri) -> {
+                    result[(int)v] = li;
+                    return v + 1;
+                }, 0, offset, -1);
+                result[ki] = offset;
+            }
+
+            return build(sortedKeys, values, result);
+        }
+
+        protected abstract T none();
+        protected abstract T build(K[] keys, V[] values, int[] keyToValue);
+
+        @Override
+        public void close()
+        {
+            cachedInts.forceDiscard(keyLimits);
+            cachedValues.forceDiscard(keysToValues, totalCount);
+        }
+    }
+
+    /**
+     * An object for managing a sequence of efficient linear merges Deps objects.
+     * Its primary purpose is to manage input and output buffers, so that we reuse output buffers
+     * as input to the next merge, and if any input is a superset of the other inputs that this input
+     * is returned unmodified.
+     *
+     * This is achieved by using PassThroughXBuffers so that the result buffers (and their sizes) are returned
+     * unmodified, and the buffers are cached as far as possible. In general, the buffers should be taken
+     * out of pre-existing caches, but if the buffers are too large then we cache any additional buffers we
+     * allocate for the duration of the merge.
+     */
+    public static class LinearMerger<K, V, T> extends PassThroughObjectAndIntBuffers<V> implements Constructor<K, V, Object>, AutoCloseable
+    {
+        final Adapter<K, V> adapter;
+        final PassThroughObjectBuffers<K> keyBuffers;
+        K[] bufKeys;
+        V[] bufValues;
+        int[] buf = null;
+        int bufKeysLength, bufValuesLength = 0, bufLength = 0;
+        T from = null;
+
+        public LinearMerger(Adapter<K, V> adapter)
+        {
+            super(adapter.cachedValues(), cachedInts());
+            keyBuffers = new PassThroughObjectBuffers<>(adapter.cachedKeys());
+            this.adapter = adapter;
+        }
+
+        @Override
+        public Object construct(K[] keys, int keysLength, V[] txnIds, int txnIdsLength, int[] out, int outLength)
+        {
+            if (from == null)
+            {
+                // if our input buffers were themselves buffers, we want to discard them unless they have been returned back to us
+                discard(keys, txnIds, out);
+            }
+            else if (buf != out)
+            {
+                // the output is not equal to a prior input
+                from = null;
+            }
+
+            if (from == null)
+            {
+                bufKeys = keys;
+                bufKeysLength = keysLength;
+                bufValues = txnIds;
+                bufValuesLength = txnIdsLength;
+                buf = out;
+                bufLength = outLength;
+            }
+            else
+            {
+                Invariants.checkState(keys == bufKeys && keysLength == bufKeysLength);
+                Invariants.checkState(txnIds == bufValues && txnIdsLength == bufValuesLength);
+                Invariants.checkState(outLength == bufLength);
+            }
+            return null;
+        }
+
+        public void update(T merge, K[] keys, V[] values, int[] keysToValues)
+        {
+            if (buf == null)
+            {
+                bufKeys = keys;
+                bufKeysLength = keys.length;
+                bufValues = values;
+                bufValuesLength = values.length;
+                buf = keysToValues;
+                bufLength = keysToValues.length;
+                from = merge;
+                return;
+            }
+
+            linearUnion(
+                    bufKeys, bufKeysLength, bufValues, bufValuesLength, buf, bufLength,
+                    keys, keys.length, values, values.length, keysToValues, keysToValues.length,
+                    adapter.keyComparator(), adapter.valueComparator(),
+                    keyBuffers, this, this, this
+            );
+            if (buf == keysToValues)
+            {
+                Invariants.checkState(keys == bufKeys && keys.length == bufKeysLength);
+                Invariants.checkState(values == bufValues && values.length == bufValuesLength);
+                Invariants.checkState(keysToValues.length == bufLength);
+                from = merge;
+            }
+        }
+
+        public T get(SimpleConstructor<K[], V[], T> constructor, T none)
+        {
+            if (buf == null)
+                return none;
+
+            if (from != null)
+                return from;
+
+            return constructor.construct(keyBuffers.realComplete(bufKeys, bufKeysLength),
+                    realComplete(bufValues, bufValuesLength),
+                    realComplete(buf, bufLength));
+        }
+
+        /**
+         * Free buffers unless they are equal to the corresponding parameter
+         */
+        void discard(K[] freeKeysIfNot, V[] freeValuesIfNot, int[] freeBufIfNot)
+        {
+            if (from != null)
+                return;
+
+            if (bufKeys != freeKeysIfNot)
+            {
+                keyBuffers.realDiscard(bufKeys, bufKeysLength);
+                bufKeys = null;
+            }
+            if (bufValues != freeValuesIfNot)
+            {
+                realDiscard(bufValues, bufValuesLength);
+                bufValues = null;
+            }
+            if (buf != freeBufIfNot)
+            {
+                realDiscard(buf, bufLength);
+                buf = null;
+            }
+        }
+
+        @Override
+        public void close()
+        {
+            if (from == null)
+                discard(null, null, null);
+        }
+    }
+
+    /**
+     * Returns the set of {@link TxnId}s that are referenced by {@code keysToTxnId}, and <strong>updates</strong>
+     * {@code keysToTxnId} to point to the new offsets in the returned set.
+     * @param keys object referenced by {@code keysToTxnId} index
+     * @param values to trim to the seen {@link TxnId}s
+     * @param keysToTxnId to use as reference for trimming, this index will be updated to reflect the trimmed offsets.
+     * @return smallest set of {@link TxnId} seen in {@code keysToTxnId}
+     *
+     * TODO (desired, efficiency): algorithmic complexity is poor if have shrunk TxnId dramatically.
+     */
+    public static <K, V> V[] trimUnusedValues(K[] keys, V[] values, int[] keysToTxnId, IntFunction<V[]> valueAllocator)
+    {
+        IntBuffers cache = ArrayBuffers.cachedInts();
+        // we use remapTxnId twice:
+        //  - first we use the end to store a bitmap of those TxnId we are actually using
+        //  - then we use it to store the remap index (incrementally replacing the bitmap)
+        int bitMapOffset = values.length + 1 - (values.length+31)/32;
+        int[] remapTxnId = cache.getInts(values.length + 1);
+        try
+        {
+            Arrays.fill(remapTxnId, bitMapOffset, values.length + 1, 0);
+            for (int i = keys.length ; i < keysToTxnId.length ; ++i)
+                setBit(remapTxnId, bitMapOffset, keysToTxnId[i]);
+
+            int offset = 0;
+            for (int i = 0 ; i < values.length ; ++i)
+            {
+                if (hasSetBit(remapTxnId, bitMapOffset, i)) remapTxnId[i] = offset++;
+                else remapTxnId[i] = -1;
+            }
+
+            V[] result = values;
+            if (offset < values.length)
+            {
+                result = valueAllocator.apply(offset);
+                for (int i = 0 ; i < values.length ; ++i)
+                {
+                    if (remapTxnId[i] >= 0)
+                        result[remapTxnId[i]] = values[i];
+                }
+                // Update keysToTxnId to point to the new remapped TxnId offsets
+                for (int i = keys.length ; i < keysToTxnId.length ; ++i)
+                    keysToTxnId[i] = remapTxnId[keysToTxnId[i]];
+            }
+
+            return result;
+        }
+        finally
+        {
+            cache.forceDiscard(remapTxnId);
+        }
+    }
+
+    static boolean arraysEqual(int[] left, int[] right, int length)
+    {
+        if (left.length < length || right.length < length)
+            return false;
+
+        for (int i=0; i<length; i++)
+            if (left[i] !=right[i])
+                return false;
+
+        return true;
+    }
+
+    static <T> boolean arraysEqual(T[] left, T[] right, int length)
+    {
+        if (left.length < length || right.length < length)
+            return false;
+
+        for (int i=0; i<length; i++)
+            if (!Objects.equals(left[i], right[i]))
+                return false;
+
+        return true;
+    }
+
+    // TODO (low priority, efficiency): this method supports merging keyToTxnId OR txnIdToKey; we can perhaps save time
+    //  and effort when constructing Deps on remote hosts by only producing txnIdToKey with OrderedCollector and serializing
+    //  only this, and merging on the recipient before inverting, so that we only have to invert the final assembled deps
+    @Inline
+    public static <K, V, T>
+    T linearUnion(K[] leftKeys, int leftKeysLength, V[] leftValues, int leftValuesLength, int[] left, int leftLength,
+                  K[] rightKeys, int rightKeysLength, V[] rightValues, int rightValuesLength, int[] right, int rightLength,
+                  SymmetricComparator<? super K> keyComparator, SymmetricComparator<? super V> valueComparator,
+                  ObjectBuffers<K> keyBuffers, ObjectBuffers<V> valueBuffers, IntBuffers intBuffers, Constructor<K, V, T> constructor)
+    {
+        K[] outKeys = null;
+        V[] outValues = null;
+        int[] remapLeft = null, remapRight = null, out = null;
+        int outLength = 0, outKeysLength = 0, outValuesLength = 0;
+
+        try
+        {
+            outKeys = SortedArrays.linearUnion(leftKeys, leftKeysLength, rightKeys, rightKeysLength, keyComparator, keyBuffers);
+            outKeysLength = keyBuffers.lengthOfLast(outKeys);
+            outValues = SortedArrays.linearUnion(leftValues, leftValuesLength, rightValues, rightValuesLength, valueComparator, valueBuffers);
+            outValuesLength = valueBuffers.lengthOfLast(outValues);
+
+            remapLeft = remapToSuperset(leftValues, leftValuesLength, outValues, outValuesLength, valueComparator, intBuffers);
+            remapRight = remapToSuperset(rightValues, rightValuesLength, outValues, outValuesLength, valueComparator, intBuffers);
+
+            if (remapLeft == null && remapRight == null && leftLength == rightLength && leftKeysLength == rightKeysLength
+                    && arraysEqual(left, right, rightLength)
+                    && arraysEqual(leftKeys, rightKeys, rightKeysLength)
+                )
+            {
+                return constructor.construct(leftKeys, leftKeysLength, leftValues, leftValuesLength, left, leftLength);
+            }
+
+            int lk = 0, rk = 0, ok = 0, l = leftKeysLength, r = rightKeysLength;
+            outLength = outKeysLength;
+
+            if (remapLeft == null && outKeys == leftKeys)
+            {
+                // "this" knows all the TxnId and Keys already, but do both agree on what Keys map to TxnIds?
+                noOp: while (lk < leftKeysLength && rk < rightKeysLength)
+                {
+                    int ck = keyComparator.compare(leftKeys[lk], rightKeys[rk]);
+                    if (ck < 0)
+                    {
+                        // "this" knows of a key not present in "that"
+                        outLength += left[lk] - l; // logically append the key's TxnIds to the size
+                        l = left[lk];
+                        assert outLength == l && ok == lk && left[ok] == outLength;
+                        ok++;
+                        lk++;
+                    }
+                    else if (ck > 0)
+                    {
+                        // if this happened there is a bug with keys.union or keys are not actually sorted
+                        throwUnexpectedMissingKeyException(leftKeys, lk, leftKeysLength, rightKeys, rk, rightKeysLength, true);
+                    }
+                    else
+                    {
+                        // both "this" and "that" know of the key
+                        while (l < left[lk] && r < right[rk])
+                        {
+                            int nextLeft = left[l];
+                            int nextRight = remap(right[r], remapRight);
+
+                            if (nextLeft < nextRight)
+                            {
+                                // "this" knows of the txn that "that" didn't
+                                outLength++;
+                                l++;
+                            }
+                            else if (nextRight < nextLeft)
+                            {
+                                out = copy(left, outLength, leftLength + rightLength - r, intBuffers);
+                                break noOp;
+                            }
+                            else
+                            {
+                                outLength++;
+                                l++;
+                                r++;
+                            }
+                        }
+
+                        if (l < left[lk])
+                        {
+                            outLength += left[lk] - l;
+                            l = left[lk];
+                        }
+                        else if (r < right[rk])
+                        {
+                            // "that" thinks a key includes a TxnId as a dependency but "this" doesn't, need to include this knowledge
+                            out = copy(left, outLength, leftLength + rightLength - r, intBuffers);
+                            break;
+                        }
+
+                        assert outLength == l && ok == lk && left[ok] == outLength;
+                        ok++;
+                        rk++;
+                        lk++;
+                    }
+                }
+
+                if (out == null)
+                    return constructor.construct(leftKeys, leftKeysLength, leftValues, leftValuesLength, left, leftLength);
+            }
+            else if (remapRight == null && outKeys == rightKeys)
+            {
+                // "that" knows all the TxnId and keys already, but "this" does not
+                noOp: while (lk < leftKeysLength && rk < rightKeysLength)
+                {
+                    int ck = keyComparator.compare(leftKeys[lk], rightKeys[rk]);
+                    if (ck < 0)
+                    {
+                        // if this happened there is a bug with keys.union or keys are not actually sorted
+                        throwUnexpectedMissingKeyException(leftKeys, lk, leftKeysLength, rightKeys, rk, rightKeysLength, false);
+                    }
+                    else if (ck > 0)
+                    {
+                        outLength += right[rk] - r;
+                        r = right[rk];
+                        assert outLength == r && ok == rk && right[ok] == outLength;
+                        ok++;
+                        rk++;
+                    }
+                    else
+                    {
+                        // both "this" and "that" know of the key
+                        while (l < left[lk] && r < right[rk])
+                        {
+                            int nextLeft = remap(left[l], remapLeft);
+                            int nextRight = right[r];
+
+                            if (nextLeft < nextRight)
+                            {
+                                // "this" thinks a TxnID depends on Key but "that" doesn't, need to include this knowledge
+                                out = copy(right, outLength, rightLength + leftLength - l, intBuffers);
+                                break noOp;
+                            }
+                            else if (nextRight < nextLeft)
+                            {
+                                // "that" knows of the txn that "this" didn't
+                                outLength++;
+                                r++;
+                            }
+                            else
+                            {
+                                outLength++;
+                                l++;
+                                r++;
+                            }
+                        }
+
+                        if (l < left[lk])
+                        {
+                            out = copy(right, outLength, rightLength + leftLength - l, intBuffers);
+                            break;
+                        }
+                        else if (r < right[rk])
+                        {
+                            outLength += right[rk] - r;
+                            r = right[rk];
+                        }
+
+                        assert outLength == r && ok == rk && right[ok] == outLength;
+                        ok++;
+                        rk++;
+                        lk++;
+                    }
+                }
+
+                if (out == null)
+                    return constructor.construct(rightKeys, rightKeysLength, rightValues, rightValuesLength, right, rightLength);
+            }
+            else
+            {
+                out = intBuffers.getInts(leftLength + rightLength);
+            }
+
+            while (lk < leftKeysLength && rk < rightKeysLength)
+            {
+                int ck = keyComparator.compare(leftKeys[lk], rightKeys[rk]);
+                if (ck < 0)
+                {
+                    while (l < left[lk])
+                        out[outLength++] = remap(left[l++], remapLeft);
+                    out[ok++] = outLength;
+                    lk++;
+                }
+                else if (ck > 0)
+                {
+                    while (r < right[rk])
+                        out[outLength++] = remap(right[r++], remapRight);
+                    out[ok++] = outLength;
+                    rk++;
+                }
+                else
+                {
+                    while (l < left[lk] && r < right[rk])
+                    {
+                        int nextLeft = remap(left[l], remapLeft);
+                        int nextRight = remap(right[r], remapRight);
+
+                        if (nextLeft <= nextRight)
+                        {
+                            out[outLength++] = nextLeft;
+                            l += 1;
+                            r += nextLeft == nextRight ? 1 : 0;
+                        }
+                        else
+                        {
+                            out[outLength++] = nextRight;
+                            ++r;
+                        }
+                    }
+
+                    while (l < left[lk])
+                        out[outLength++] = remap(left[l++], remapLeft);
+
+                    while (r < right[rk])
+                        out[outLength++] = remap(right[r++], remapRight);
+
+                    out[ok++] = outLength;
+                    rk++;
+                    lk++;
+                }
+            }
+
+            while (lk < leftKeysLength)
+            {
+                while (l < left[lk])
+                    out[outLength++] = remap(left[l++], remapLeft);
+                out[ok++] = outLength;
+                lk++;
+            }
+
+            while (rk < rightKeysLength)
+            {
+                while (r < right[rk])
+                    out[outLength++] = remap(right[r++], remapRight);
+                out[ok++] = outLength;
+                rk++;
+            }
+
+            return constructor.construct(outKeys, outKeysLength, outValues, outValuesLength, out, outLength);
+        }
+        finally
+        {
+            if (outKeys != null)
+                keyBuffers.discard(outKeys, outKeysLength);
+            if (outValues != null)
+                valueBuffers.discard(outValues, outValuesLength);
+            if (out != null)
+                intBuffers.discard(out, outLength);
+            if (remapLeft != null)
+                intBuffers.forceDiscard(remapLeft);
+            if (remapRight != null)
+                intBuffers.forceDiscard(remapRight);
+        }
+    }
+
+    static <A> void throwUnexpectedMissingKeyException(A[] leftKeys, int leftKeyIndex, int leftKeyLength, A[] rightKeys, int rightKeyIndex, int rightKeyLength, boolean isMissingLeft)
+    {
+        StringBuilder sb = new StringBuilder();
+        String missing = isMissingLeft ? "left" : "right";
+        String extra = isMissingLeft ? "right" : "left";
+        sb.append(missing).append(" knows all keys, yet ").append(extra).append(" knew of an extra key at indexes left[")
+                .append(leftKeyIndex).append("] = ").append(leftKeys[leftKeyIndex])
+                .append(", right[").append(rightKeyIndex).append("] = ").append(rightKeys[rightKeyIndex]).append("\n");
+        sb.append("leftKeys = ").append(Arrays.stream(leftKeys, 0, leftKeyLength).map(Object::toString).collect(Collectors.joining())).append('\n');
+        sb.append("rightKeys = ").append(Arrays.stream(rightKeys, 0, rightKeyLength).map(Object::toString).collect(Collectors.joining())).append('\n');
+        throw new IllegalStateException(sb.toString());
+    }
+
+    static int[] copy(int[] src, int to, int length, IntBuffers bufferManager)
+    {
+        if (length == 0)
+            return NO_INTS;
+
+        int[] result = bufferManager.getInts(length);
+        if (result.length < length)
+            throw new IllegalStateException();
+        System.arraycopy(src, 0, result, 0, to);
+        return result;
+    }
+
+    public static <K, K2, V, T> T remove(T from, K[] keys, V[] oldValues, int[] oldKeysToValues, Predicate<V> remove, T none, IntFunction<V[]> newValueArray,
+                                     K2 passthroughKeys, SimpleConstructor<K2, V[], T> constructor)
+    {
+        if (isEmpty(keys, oldKeysToValues))
+            return from;
+
+        IntBuffers cache = ArrayBuffers.cachedInts();
+        int[] remapValue = cache.getInts(oldValues.length);
+        int[] newKeyToValue = null;
+        V[] newValues;
+        int o;
+        try
+        {
+            int count = 0;
+            for (int i = 0 ; i < oldValues.length ; ++i)
+            {
+                if (remove.test(oldValues[i])) remapValue[i] = -1;
+                else remapValue[i] = count++;
+            }
+
+            if (count == oldValues.length)
+                return from;
+
+            if (count == 0)
+                return none;
+
+            newValues = newValueArray.apply(count);
+            for (int i = 0 ; i < oldValues.length ; ++i)
+            {
+                if (remapValue[i] >= 0)
+                    newValues[remapValue[i]] = oldValues[i];
+            }
+
+            newKeyToValue = cache.getInts(oldKeysToValues.length);
+            int k = 0, i = keys.length;
+            o = i;
+            while (i < oldKeysToValues.length)
+            {
+                while (oldKeysToValues[k] == i)
+                    newKeyToValue[k++] = o;
+
+                int remapped = remapValue[oldKeysToValues[i]];
+                if (remapped >= 0)
+                    newKeyToValue[o++] = remapped;
+                ++i;
+            }
+
+            while (k < keys.length)
+                newKeyToValue[k++] = o;
+        }
+        catch (Throwable t)
+        {
+            cache.forceDiscard(newKeyToValue);
+            throw t;
+        }
+        finally
+        {
+            cache.forceDiscard(remapValue);
+        }
+
+        newKeyToValue = cache.completeAndDiscard(newKeyToValue, o);
+        return constructor.construct(passthroughKeys, newValues, newKeyToValue);
+    }
+
+    @Inline
+    public static int[] invert(int[] src, int srcLength, int srcKeyCount, int trgKeyCount)
+    {
+        int[] trg = new int[trgKeyCount + srcLength - srcKeyCount];
+
+        // first pass, count number of txnId per key
+        for (int i = srcKeyCount ; i < srcLength ; ++i)
+            trg[src[i]]++;
+
+        // turn into offsets (i.e. add txnIds.size() and then sum them)
+        trg[0] += trgKeyCount;
+        for (int i = 1; i < trgKeyCount ; ++i)
+            trg[i] += trg[i - 1];
+
+        // shuffle forwards one, so we have the start index rather than end
+        System.arraycopy(trg, 0, trg, 1, trgKeyCount - 1);
+        trg[0] = trgKeyCount;
+
+        // convert the offsets to end, and set the key at the target positions
+        int k = 0;
+        for (int i = srcKeyCount ; i < srcLength ; ++i)
+        {
+            // if at the end offset, switch to the next key
+            while (i == src[k])
+                ++k;
+
+            // find the next key offset for the TxnId and set the offset to this key
+            trg[trg[src[i]]++] = k;
+        }
+
+        return trg;
+    }
+
+    public static <K, V> Iterator<Map.Entry<K, V>> newIterator(K[] keys, V[] values, int[] keysToValues)
+    {
+        return new Iterator<Map.Entry<K, V>>()
+        {
+            int i = keys.length, k = 0;
+
+            @Override
+            public boolean hasNext()
+            {
+                return i < keysToValues.length;
+            }
+
+            @Override
+            public Map.Entry<K, V> next()
+            {
+                Entry<K, V> result = new Entry<>(keys[k], values[keysToValues[i++]]);
+                if (i == keysToValues[k])
+                    ++k;
+                return result;
+            }
+        };
+    }
+
+    public static <K, V> String toSimpleString(K[] keys, V[] values, int[] keysToValues)
+    {
+        if (isEmpty(keys, keysToValues))
+            return "{}";
+
+        StringBuilder builder = new StringBuilder("{");
+        for (int k = 0, t = keys.length; k < keys.length ; ++k)
+        {
+            if (builder.length() > 1)
+                builder.append(", ");
+
+            builder.append(keys[k]);
+            builder.append(":[");
+            boolean first = true;
+            while (t < keysToValues[k])
+            {
+                if (first) first = false;
+                else builder.append(", ");
+                builder.append(values[keysToValues[t++]]);
+            }
+            builder.append("]");
+        }
+        builder.append("}");
+        return builder.toString();
+    }
+
+    public static boolean isEmpty(Object[] keys, int[] keysToValues)
+    {
+        return keys.length == keysToValues.length;
+    }
+
+    public static int startOffset(Object[] keys, int[] keysToValues, int keyIndex)
+    {
+        return keyIndex == 0 ? keys.length : keysToValues[keyIndex - 1];
+    }
+
+    public static int endOffset(int[] keysToValues, int keyIndex)
+    {
+        return keysToValues[keyIndex];
+    }
+
+    @Inline
+    public static <K, V> boolean testEquality(K[] thisKeys, V[] thisValues, int[] thisKeysToValues,
+                                              K[] thatKeys, V[] thatValues, int[] thatKeysToValues)
+    {
+        return thisValues.length == thatValues.length
+               && thisKeys.length == thatKeys.length
+               && Arrays.equals(thisKeysToValues, thatKeysToValues)
+               && Arrays.equals(thisValues, thatValues)
+               && Arrays.equals(thisKeys, thatKeys);
+    }
+
+    public static class Entry<K, V> implements Map.Entry<K, V>
+    {
+        final K key;
+        final V value;
+
+        public Entry(K key, V value)
+        {
+            this.key = key;
+            this.value = value;
+        }
+
+        @Override
+        public K getKey()
+        {
+            return key;
+        }
+
+        @Override
+        public V getValue()
+        {
+            return value;
+        }
+
+        @Override
+        public V setValue(V value)
+        {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public String toString()
+        {
+            return key + "->" + value;
+        }
+    }
+
+    @Inline
+    public static <K, V> void checkValid(K[] keys, V[] values, int[] keysToValues)
+    {
+        if (!DEBUG_CHECKS)
+            return;
+
+        int k = 0;
+        for (int i = keys.length; i < keysToValues.length ; ++i)
+        {
+            boolean first = true;
+            while (i < keysToValues[k])
+            {
+                if (first) first = false;
+                else if (keysToValues[i - 1] == keysToValues[i])
+                {
+                    K key = keys[i];
+                    V value = values[keysToValues[i]];
+                    throw new IllegalStateException(String.format("Duplicate value (%s) found for key %s", value, key));
+                }
+                i++;
+            }
+            ++k;
+        }
+    }
+
+    private static void setBit(int[] array, int offset, int index)
+    {
+        array[offset + index / 32] |= (1 << (index & 31));
+    }
+
+    private static boolean hasSetBit(int[] array, int offset, int index)
+    {
+        return (array[offset + index / 32] & (1 << (index & 31))) != 0;
+    }
+}
diff --git a/accord-core/src/main/java/accord/utils/SearchableRangeList.java b/accord-core/src/main/java/accord/utils/SearchableRangeList.java
new file mode 100644
index 0000000..3c6e3d4
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/SearchableRangeList.java
@@ -0,0 +1,292 @@
+package accord.utils;
+
+import accord.api.Key;
+import accord.primitives.Range;
+import accord.primitives.RoutableKey;
+import accord.utils.SearchableRangeListBuilder.Links;
+import accord.utils.SearchableRangeListBuilder.Strategy;
+import net.nicoulaj.compilecommand.annotations.Inline;
+
+import java.util.*;
+
+import static accord.utils.SearchableRangeListBuilder.Links.LINKS;
+import static accord.utils.SearchableRangeListBuilder.Strategy.ACCURATE;
+import static accord.utils.SortedArrays.Search.*;
+
+/**
+ * Based on CINTIA, the Checkpoint INTerval Array
+ * [Transactions on Big Data; Ruslan Mavlyutov and Philippe Cudre-Mauroux of U. of Fribourg]
+ * <p>
+ * CINTIA is a very simple augmentation of a sorted list of intervals that permits efficient intersection queries.
+ * The key insight is to augment the list of intervals (sorted by their start bound) with periodic checkpoints
+ * containing a list of the intervals that remain open from an earlier point in the list.
+ * The sorted interval list can easily return all intersections whose start overlaps a provided interval, and a
+ * backwards walk through the list to the prior checkpoint, plus a walk of the checkpoint, can answer all intersections
+ * that started prior, but whose ends overlap the query interval.
+ * <p>
+ * Besides this key insight, which honestly isn't that different to Cassandra packing active range tombstone bounds
+ * into index files, we largely take our own approach.
+ * <p>
+ * <ul>
+ * <li> We sort the intervals by start then end bound, so that we may easily find all overlaps that <i>start</i> in a queried range
+ * <li> Checkpoints are maintained in an auxiliary structure, keyed by the index of the first range they cover so that
+ *      we have good locality and may perform fast binary search on the lower range index we find in step one
+ * <li> By being maintained separately we may dynamically decide when to insert a checkpoint.
+ *      This potentially permits a single checkpoint to cover a large area.
+ * <li> Our scan runs for some fixed distance from the first overlapping range we find by simple binary search,
+ *      with each checkpoint defining the scan distance. This permits checkpoints to cover longer regions, and
+ *      also to avoid serializing ranges that occur before the checkpoint but that are easily scanned.
+ * <li> We write our dynamic checkpoints based on some simple maths that yield linear space overhead and O(k)
+ *      additional work where k is the number of overlapping ranges with any given point
+ *   <ul>
+ *     <li> We perform a greedy iteration of the ranges, with some initial {@code goalScanDistance}; any range that can be found
+ *          from every overlapping range index by a backwards scan shorter than this will record only the actual distance required.
+ *     <li> Other ranges are "tenured" and will trigger a checkpoint to be written either immediately (if the last checkpoint was
+ *          long ago enough), or else within the maximum scan distance from the first location the range was first encountered
+ *     <li> The maximum scan distance is proportional to the larger of: the logarithm of the total number of ranges in the collection,
+ *          and the number of tenured ranges written to the last checkpoint, discounted by the number of ranges since removed.
+ *          This guarantees O(lg(N)+k) where k is the size of the result set for a query, while ensuring our O(N) space requirements.
+ *          Essentially, we require that the distance between two checkpoints be at least as large as the number of duplicate
+ *          elements we may serialize, so we can write at most O(N) duplicate entries, and we can write unique entries at most
+ *          once, i.e. O(N) in total. Since we sort the checkpoints in descending order, we will never visit more than O(k)
+ *          entries, where k is the number of matches. The number of scanned entries is similarly capped by the same logic;
+ *          for each entry we remove from the tenured collection we bring our threshold for writing a new checkpoint down,
+ *          so that by the time we are permitted to write a checkpoint we must have fewer tenured entries than we may scan.
+ *          TODO (low priority, efficiency): probably we want to take the maximum of the current tenured.size() and the
+ *           discounted minimum span when deciding IF we want to write a new checkpoint, even if our complexity permits
+ *           writing solely based on the discounted minimum span.
+ *    </ul>
+ *    <li>We additionally permit our checkpoints to reference earlier checkpoints whose end bounds are still open.
+ *        We permit this to a depth of at most one, i.e. we do not transitively explore checkpoints referenced by
+ *        earlier checkpoints.
+ * </ul>
+ */
+public class SearchableRangeList
+{
+    // scan distance can be kept very small as we guarantee to use at most linear extra space even with a scan distance of zero
+    static final int MAX_SCAN_DISTANCE = 255;
+    private static final int BIT30 = 0x40000000;
+    private static final int BIT29 = 0x20000000;
+
+    private static final SearchableRangeList EMPTY_CHECKPOINTS = new SearchableRangeList(new Range[0], new int[0], new int[] { 0, 0 }, new int[0], 0);
+
+    final Range[] ranges;
+
+    /**
+     * The lower bound for each checkpoint.
+     * The checkpoint {@code i} applies to all ranges (incl) starting from {@code lowerBounds[i]},
+     * but before (excl) {@code lowerBounds[i+1]}.
+     */
+    final int[] lowerBounds;
+
+    /**
+     * Logically one entry per checkpoint, mapping {@link #lowerBounds} to {@link #checkpointLists},
+     * however we also encode an additional byte per entry representing the scan distance for the
+     * ranges handled by this checkpoint. These are grouped into an integer per four mappings, i.e.
+     * we encode batches of five ints, with the first int containing the four scan distances for the
+     * next four checkpoints, and the following four ints containing the respective offsets into
+     * {@link #checkpointLists}.
+     * <p>
+     * [0.........32b.........64b.........96b........128b........160b........192b]
+     * [ d1 d2 d3 d4  mapping1    mapping2   mapping3    mapping4    d5 d6 d7 d8 ]
+     */
+    final int[] headers;
+
+    /**
+     * A list of indexes in {@link #ranges} contained by each checkpoint; checkpoints are
+     * mapped from {@link #lowerBounds} by {@link #headers}.
+     * <p>
+     * Entries are sorted in descending order by the end of the range they cover, so that
+     * a search of this collection my terminate as soon as it encounters a range that does
+     * not cover the item we are searching for.
+     * <p>
+     * This collection may contain negative values, in which case these point to other
+     * checkpoints, whose <i>direct</i> contents (i.e. the positive values of) we may
+     * search.
+     * <ul> if negative, points to an earlier checkpoint, and:
+     *   <li>if the 30th bit is set, the low 20 bits point to checkpointsList,
+     *       and the 9 bits in-between provide the length of the range</li>
+     *   <li>otherwise, if the 29th bit is set, the lower 29 bits points to checkpointsList,
+     *       and can be iterated safely without an endIndex</li>
+     *   <li>otherwise, the low 29 bits provide the length of the run, and the low 31 bits
+     *       of the following entry (which will also be negative) provide a pointer to
+     *       checkpointsList</li>
+     * </ul>
+     */
+    final int[] checkpointLists;
+
+    public final int maxScanAndCheckpointMatches;
+
+    SearchableRangeList(Range[] ranges, int[] lowerBounds, int[] headers, int[] checkpointLists, int maxScanAndCheckpointMatches)
+    {
+        this.ranges = ranges;
+        this.lowerBounds = lowerBounds;
+        this.headers = headers;
+        this.checkpointLists = checkpointLists;
+        this.maxScanAndCheckpointMatches = maxScanAndCheckpointMatches;
+    }
+
+    @Inline
+    public <P1, P2, P3> int forEach(Range range, IndexedTriConsumer<P1, P2, P3> forEachScanOrCheckpoint, IndexedRangeTriConsumer<P1, P2, P3> forEachRange, P1 p1, P2 p2, P3 p3, int minIndex)
+    {
+        if (ranges.length == 0 || minIndex == ranges.length)
+            return minIndex;
+
+        int end = SortedArrays.binarySearch(ranges, minIndex, ranges.length, range.end(), (a, b) -> a.compareTo(b.start()), CEIL);
+        if (end < 0) end = -1 - end;
+        if (end <= minIndex) return minIndex;
+
+        int floor = SortedArrays.binarySearch(ranges, minIndex, ranges.length, range.start(), (a, b) -> a.compareTo(b.start()), CEIL);
+        int start = floor;
+        if (floor < 0)
+        {
+            // if there's no precise match on start, step backwards;
+            // if this range does not overlap us, step forwards again for start
+            // but retain the floor index for performing scan and checkpoint searches from
+            // as this contains all ranges that might overlap us (whereas those that end
+            // after us but before the next range's start would be missed by the next range index)
+            start = floor = -2 - floor;
+            if (start < 0)
+                start = floor = 0;
+            else if (ranges[start].end().compareTo(range.start()) <= 0)
+                ++start;
+        }
+
+        return forEach(start, end, floor, range.start(), forEachScanOrCheckpoint, forEachRange, p1, p2, p3, minIndex);
+    }
+
+    @Inline
+    public <P1, P2, P3> int forEach(Key key, IndexedTriConsumer<P1, P2, P3> forEachScanOrCheckpoint, IndexedRangeTriConsumer<P1, P2, P3> forEachRange, P1 p1, P2 p2, P3 p3, int minIndex)
+    {
+        if (ranges.length == 0 || minIndex == ranges.length)
+            return minIndex;
+
+        int end = SortedArrays.binarySearch(ranges, minIndex, ranges.length, key, (a, b) -> a.compareTo(b.start()), FLOOR);
+        if (end < 0) end = -1 - end;
+        if (end <= minIndex) return minIndex;
+
+        int floor = SortedArrays.binarySearch(ranges, minIndex, ranges.length, key, (a, b) -> a.compareTo(b.start()), CEIL);
+        int start = floor;
+        if (floor < 0)
+        {
+            // if there's no precise match on start, step backwards;
+            // if this range does not overlap us, step forwards again for start
+            // but retain the floor index for performing scan and checkpoint searches from
+            // as this contains all ranges that might overlap us (whereas those that end
+            // after us but before the next range's start would be missed by the next range index)
+            start = floor = -2 - floor;
+            if (start < 0)
+                start = floor = 0;
+            else if (ranges[start].end().compareTo(key) <= 0)
+                ++start;
+        }
+
+        // Key cannot equal RoutingKey, so can ignore inclusivity/exclusivity of end bound
+        return forEach(start, end, floor, key, forEachScanOrCheckpoint, forEachRange, p1, p2, p3, minIndex);
+    }
+
+    @Inline
+    private <P1, P2, P3> int forEach(int start, int end, int floor, RoutableKey startBound,
+                                     IndexedTriConsumer<P1, P2, P3> forEachScanOrCheckpoint, IndexedRangeTriConsumer<P1, P2, P3> forEachRange,
+                                     P1 p1, P2 p2, P3 p3, int minIndex)
+    {
+        if (start < minIndex) start = minIndex;
+
+        // find the checkpoint array, so we know how far to step back
+        int checkpoint = Arrays.binarySearch(lowerBounds, floor);
+        if (checkpoint < 0) checkpoint = -2 - checkpoint;
+        if (checkpoint < 0) return end;
+
+        int headerBaseIndex = (checkpoint / 4) * 5;
+        int headerSubIndex = checkpoint & 3;
+        int headerListIndex = headerBaseIndex + 1 + headerSubIndex;
+
+        int scanDistance = (headers[headerBaseIndex] >>> (8 * headerSubIndex)) & 0xff;
+        int checkpointStart = headers[headerListIndex];
+        int checkpointEnd = headers[headerListIndex + (headerSubIndex + 5)/4]; // skip the next header
+
+        if (scanDistance == MAX_SCAN_DISTANCE)
+        {
+            scanDistance = -checkpointLists[checkpointStart++];
+            Invariants.checkState(scanDistance >= MAX_SCAN_DISTANCE);
+        }
+
+        // NOTE: we visit in approximately ascending order, and this is a requirement for correctness of RangeDeps builders
+        //       Only the checkpoint is visited in uncertain order, but it is visited entirely, before the scan matches
+        //       and the range matches
+        int minScanIndex = Math.max(floor - scanDistance, minIndex);
+        for (int i = checkpointStart; i < checkpointEnd ; ++i)
+        {
+            int ri = checkpointLists[i];
+            if (ri < 0)
+            {
+                int subStart, subEnd;
+                if ((ri & BIT30) != 0)
+                {
+                    subStart = ri & 0xfffff;
+                    subEnd = subStart + ((ri >>> 20) & 0x1ff);
+                }
+                else if ((ri & BIT29) != 0)
+                {
+                    subStart = ri & 0x1fffffff;
+                    subEnd = Integer.MAX_VALUE;
+                }
+                else
+                {
+                    int length = ri & 0x1fffffff;
+                    subStart = checkpointLists[++i];
+                    subEnd = subStart + length;
+                }
+
+                for (int j = subStart ; j < subEnd ; ++j)
+                {
+                    ri = checkpointLists[j];
+                    if (ri < 0)
+                        continue;
+
+                    if (ranges[ri].end().compareTo(startBound) <= 0)
+                        break;
+
+                    if (ri >= minIndex && ri < minScanIndex)
+                        forEachScanOrCheckpoint.accept(p1, p2, p3, ri);
+                }
+            }
+            else
+            {
+                // if startBound is key, we cannot be equal to it;
+                // if startBound is a Range start, we also cannot be equal to it due to the requirement that
+                // endInclusive() != startInclusive(), so equality really means inequality
+                if (ranges[ri].end().compareTo(startBound) <= 0)
+                    break;
+
+                if (ri >= minIndex && ri < minScanIndex)
+                    forEachScanOrCheckpoint.accept(p1, p2, p3, ri);
+            }
+        }
+
+        for (int i = minScanIndex; i < floor ; ++i)
+        {
+            if (ranges[i].end().compareTo(startBound) > 0)
+                forEachScanOrCheckpoint.accept(p1, p2, p3, i);
+        }
+
+        forEachRange.accept(p1, p2, p3, start, end);
+        return end;
+    }
+
+    public static SearchableRangeList build(Range[] ranges)
+    {
+        if (ranges.length == 0)
+            return EMPTY_CHECKPOINTS;
+
+        return new SearchableRangeListBuilder(ranges, ACCURATE, LINKS).build();
+    }
+
+    public static SearchableRangeList build(Range[] ranges, int maxScanDistance, Strategy strategy, Links links)
+    {
+        if (ranges.length == 0)
+            return EMPTY_CHECKPOINTS;
+
+        return new SearchableRangeListBuilder(ranges, maxScanDistance, strategy, links).build();
+    }
+}
diff --git a/accord-core/src/main/java/accord/utils/SearchableRangeListBuilder.java b/accord-core/src/main/java/accord/utils/SearchableRangeListBuilder.java
new file mode 100644
index 0000000..4629498
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/SearchableRangeListBuilder.java
@@ -0,0 +1,1077 @@
+package accord.utils;
+
+import accord.api.RoutingKey;
+import accord.primitives.Range;
+import accord.utils.ArrayBuffers.IntBuffers;
+
+import javax.annotation.Nonnull;
+import java.util.Arrays;
+import java.util.Objects;
+import java.util.TreeSet;
+import java.util.stream.Collectors;
+
+import static accord.utils.ArrayBuffers.cachedInts;
+import static accord.utils.SearchableRangeList.MAX_SCAN_DISTANCE;
+import static accord.utils.SearchableRangeListBuilder.Links.LINKS;
+import static accord.utils.SearchableRangeListBuilder.Strategy.ACCURATE;
+import static accord.utils.SortedArrays.Search.CEIL;
+
+/**
+ * Builder for {@link SearchableRangeList}
+ */
+public class SearchableRangeListBuilder
+{
+    public enum Strategy
+    {
+        /**
+         * Do not tenure any ranges that are scannable from the currently in-effect max scan distance.
+         * This means we probably do less work on construction, but that our measure of the match count
+         * at any point is inaccurate, and so our heuristics for when to write checkpoints may be wrong,
+         * leading to more checkpoints than necessary.
+         */
+        FAST,
+
+        /**
+         * Tenure every range covering more than goalScanDistance. Any within max scan distance will also
+         * update the scan distance, so that they will be filtered when a checkpoint is written. But
+         * in the meantime they permit accurate tracking of the number of matches a query can return,
+         * permitting our complexity calculations (that determine when checkpoints should be written, and
+         * what our maximum scan distance should be), to be accurate. This can avoid bouncing between
+         * two extremes, where a low max scan distance tenures and correctly detects a desirable larger scan
+         * distance, which we rollover and this prevents us tenuring and tracking the number of matches, so
+         * that we then pick a low max scan distance (and thereby also write a new checkpoint)
+         */
+        ACCURATE
+    }
+
+    /**
+     * Should we maintain pointers to prior checkpoints that we may reference instead of reserializing
+     * the remaining contents. This is cheap to visit as we stop enumerating as soon as we encounter
+     * an entry that no longer covers us. We use some simple heuristics when deciding whether to do
+     * this, namely that there are at least two entries (so we save one checkpoint entry) and that
+     * there is at least one direct entry for each indirect/link entry in the range we will link.
+     */
+    public enum Links
+    {
+        LINKS,
+        NO_LINKS
+    }
+
+    private static final int BIT31 = 0x80000000;
+    private static final int BIT30 = 0x40000000;
+    private static final int BIT29 = 0x20000000;
+    static final int MIN_INDIRECT_LINK_LENGTH = 2;
+
+    final boolean isAccurate;
+    final boolean withLinks;
+    final Range[] ranges;
+
+    int[] bounds;
+    int[] headers;
+    int[] lists;
+    int checkpointCount, headerPointer, listCount;
+
+    final Scan scan = new Scan();
+    final TenuredSet tenured = new TenuredSet();
+    final PendingCheckpoint pending = new PendingCheckpoint();
+
+    // track the maximum possible number of entries we can match with both a scan + checkpoint lookup
+    // this is an over-estimate and may be used by consumers to allocate out-of-order buffers for visitations
+    int maxScanAndCheckpointMatches;
+
+    public SearchableRangeListBuilder(Range[] ranges, Strategy strategy, Links links)
+    {
+        this(ranges, Math.min(MAX_SCAN_DISTANCE, 34 - Integer.numberOfLeadingZeros(ranges.length)), strategy, links);
+    }
+
+    public SearchableRangeListBuilder(Range[] ranges, int goalScanDistance, Strategy strategy, Links links)
+    {
+        this.isAccurate = strategy == ACCURATE;
+        this.withLinks = links == LINKS;
+        Invariants.checkArgument(goalScanDistance <= MAX_SCAN_DISTANCE);
+        Invariants.checkArgument(goalScanDistance > 0);
+        this.ranges = ranges;
+        init(ranges, goalScanDistance);
+    }
+
+    void init(Range[] ranges, int goalScanDistance)
+    {
+        // we write checkpoints at least goalScanDistance apart
+        scan.init(goalScanDistance);
+        IntBuffers cachedInts = cachedInts();
+        // ask for int buffers in descending order of size
+        this.lists = cachedInts.getInts(ranges.length); // this one might need to grow
+        // +2 to round-up each division, and +2 to account for the final entry (which might require an empty scan distance header)
+        this.headers = cachedInts.getInts(((ranges.length / goalScanDistance) * 5) / 4 + 4);
+        this.bounds = cachedInts.getInts(ranges.length / goalScanDistance + 1);
+    }
+
+    /**
+     * Walk over each range, looking ahead by {@link #maxScanDistance} to decide if a range should
+     * be tenured (written to a checkpoint) or scanned; the maximum scan distance is determined by the
+     * number of open tenured entries, i.e. the minimum number of results we can expect to be returned
+     * (or, if greater, the logarithm of the number of ranges in the collection).
+     * <p>
+     * Once we encounter a range that should be tenured, either write a checkpoint immediately
+     * or make a note of the position we must scan to from the last entry in this checkpoint
+     * and wait until it is permitted to write a checkpoint. This range will be tenured either
+     * way for the following checkpoint.
+     * <p>
+     * The only reason not to write a checkpoint immediately is in the case we would breach
+     * our linear space complexity limit, which is imposed by ensuring we have a space between
+     * checkpoints at least as large as the number of entries written to the last checkpoint,
+     * discounted by the number of entries we have removed from the tenured collection since
+     * the last checkpoint.
+     */
+    public SearchableRangeList build()
+    {
+        for (int ri = 0 ; ri < ranges.length ; ++ri)
+        {
+            // write a checkpoint if we meet our linear space complexity requirements
+            // and we either have a tenured range that we must scan,
+            // or the scan distance is now much larger than the minimum number of search results
+            if (shouldWriteCheckpoint(ri))
+                writeCheckpoint(ri);
+
+            // either tenure or update scan distance, potentially writing a checkpoint
+            tenureOrScan(ri);
+            tenured.untenure(ri);
+        }
+
+        // write our final pending checkpoint
+        writeCheckpoint(ranges.length);
+        closeHeaders();
+
+        IntBuffers cachedInts = cachedInts();
+        int[] lists = cachedInts.completeAndDiscard(this.lists, listCount);
+        int[] headers = cachedInts.completeAndDiscard(this.headers, headerPointer);
+        int[] bounds = cachedInts.completeAndDiscard(this.bounds, checkpointCount);
+        return new SearchableRangeList(ranges, bounds, headers, lists, maxScanAndCheckpointMatches);
+    }
+
+    /**
+     * Categorise the candidateIdx as either scannable, and if so update the scan distance;
+     * or unscannable, in which case add it to the {@link #tenured} collection.
+     * Note, that in ACCURATE mode we tenure the item if it is outside of the goalScanDistance
+     * so we may track O(k) accurately above the O(lg2(N)) search and default scan distance,
+     * but we still update the scan distance so that the checkpoint will exclude this entry.
+     */
+    private void tenureOrScan(int index)
+    {
+        Invariants.checkArgument(index >= 0);
+
+        // then either migrate the index to pendingTenured, or ensure it will be scanned
+        RoutingKey end = ranges[index].end();
+        int scanLimit = scanLimit(index, isAccurate ? scan.goal : maxScanDistance());
+        if (shouldTenure(end, scanLimit))
+        {
+            int lastIndex = tenured.tenure(end, index, ranges, scanLimit + 1);
+            if (lastIndex - index > maxScanDistance()) scan.tenured(index);
+            else if (!isAccurate) throw new IllegalStateException();
+            else scan.updateScanDistance(index, lastIndex - index, this);
+        }
+        else
+        {
+            // TODO (low priority, efficiency): if the prior checkpoint has a scan distance >= this one,
+            //  and <= 50% more than this one and there's no scanMustReachIndex nor tenuredRanges, don't
+            //  write a new checkpoint (perhaps split shouldWriteCheckpoint logic in two)
+            scan.update(end, index, ranges, scanLimit, this);
+        }
+    }
+
+    /**
+     * We are forbidden from writing a checkpoint nearer than this to a prior checkpoint.
+     * This imposes our linear space complexity bounds, while not harming our O(log2(N) + K)
+     * complexity bounds, as we guarantee minimumSpan is never more than the number of query
+     * results.
+     */
+    private int minimumSpan()
+    {
+        return Math.max(scan.goal(), tenured.minimumSpan());
+    }
+
+    private int maxScanDistance()
+    {
+        // minimumSpan() reduces overtime, but there is no reason to reduce our scan distance
+        // for tenuring below the scan distance we will write
+        return Math.max(scan.watermark(), minimumSpan());
+    }
+
+    /**
+     * The index after the last index we can scan from {@code atIndex} with at most {@code maxScanDistance}.
+     */
+    private int scanLimit(int atIndex, int maxScanDistance)
+    {
+        return Math.min(1 + atIndex + maxScanDistance, ranges.length);
+    }
+
+    private boolean shouldTenure(RoutingKey end, int scanLimit)
+    {
+        return scanLimit < ranges.length && end.compareTo(ranges[scanLimit].start()) > 0;
+    }
+
+    private boolean canWriteCheckpoint(int atIndex)
+    {
+        return atIndex - pending.atIndex >= minimumSpan();
+    }
+
+    private boolean shouldWriteCheckpoint(int atIndex)
+    {
+        if (!canWriteCheckpoint(atIndex))
+            return false;
+
+        // TODO (desired, efficiency): consider these triggers
+        if (scan.mustCheckpointToScanTenured(atIndex, maxScanDistance()))
+            return true;
+
+        if (scan.hasMaybeDivergedFromMatchSize(tenured))
+            return true;
+
+        return false;
+    }
+
+    /**
+     * Write a checkpoint for ranges[prevCheckpointIndex...ri)
+     *
+     * 1) Finalise the scan distance
+     * 2) Write the header
+     * 3) Filter the pending tenured ranges to remove those we can scan
+     * 4) Write this list out
+     * 5) Setup a link to this list, if it is large enough
+     * 6) Rollover the scan, tenured and pending structures for the new pending checkpoint
+     */
+    private void writeCheckpoint(int nextCheckpointIndex)
+    {
+        int lastIndex = nextCheckpointIndex - 1;
+        int scanDistance = scan.finalise(lastIndex);
+        scanDistance = extendScanDistance(lastIndex, scanDistance);
+
+        if (pending.atIndex < 0)
+        {
+            // we don't have any checkpoints pending, so don't try to finalise it
+            // but if the new checkpoint doesn't cover index 0, insert a new empty
+            // checkpoint for the scan distance
+            if (nextCheckpointIndex > 0)
+            {
+                // setup an initial empty checkpoint to store the first scan distance
+                maxScanAndCheckpointMatches = scanDistance;
+                writeHeader(scanDistance, 0);
+            }
+        }
+        else
+        {
+            writeHeader(scanDistance, pending.atIndex);
+            int maxCheckpointMatchCount = pending.filter(scanDistance, lastIndex);
+            int listIndex = writeList(pending);
+            if (withLinks)
+                pending.setupLinkChain(tenured, listIndex, listCount);
+            maxScanAndCheckpointMatches = Math.max(maxScanAndCheckpointMatches, scanDistance + maxCheckpointMatchCount);
+        }
+
+        savePendingCheckpointAndResetScanDistance(nextCheckpointIndex);
+    }
+
+    private void savePendingCheckpointAndResetScanDistance(int checkpointIndex)
+    {
+        // use the tail of checkpointListBuf to buffer ranges we plan to tenure
+        ensureCapacity(tenured.count() + scan.watermark());
+
+        scan.reset();
+
+        if (isAccurate)
+        {
+            // TODO (low priority, efficiency): we can shift back the existing scanDistance if it's far enough from
+            //  the next checkpoint. this might permit us to skip some comparisons
+            scan.resetPeakMax(tenured);
+            for (Tenured tenured : this.tenured)
+            {
+                int distanceToEnd = (tenured.lastIndex - checkpointIndex);
+                if (distanceToEnd >= scan.peakMax)
+                    break;
+
+                int scanDistance = tenured.lastIndex - tenured.index;
+                if (scanDistance <= scan.peakMax)
+                    scan.updateScanDistance(tenured.index, scanDistance, null);
+            }
+
+            if (scan.watermark() < scan.goal)
+            {
+                int ri = Scan.minScanIndex(checkpointIndex, scan.goal);
+                while (ri < checkpointIndex)
+                {
+                    RoutingKey end = ranges[ri].end();
+                    int scanLimit = scanLimit(ri, scan.peakMax);
+                    if (!shouldTenure(end, scanLimit))
+                        scan.update(end, ri, ranges, scanLimit, null);
+                    ++ri;
+                }
+            }
+        }
+        else
+        {
+            // the maximum scan distance that could ever have been adopted for last chunk
+            int oldPeakMax = scan.peakMax();
+            // the minimum scan distance we will start with for processing the proceeding ranges
+            // note: this may increase if we decide to tenure additional ranges, at which point it will be the actual newPeakMax
+            int newMinPeakMax = scan.newPeakMax(tenured);
+            int minUntenuredIndex = scan.minUntenuredIndex(checkpointIndex, tenured);
+            int minScanIndex = Scan.minScanIndex(checkpointIndex, newMinPeakMax);
+
+            // we now make sure tenured and scan are correct for the new parameters.
+            // 1) if our peakMax is lower then we need to go back and find items to tenure that we previously marked for scanning
+            // 2) we must also reset our scan distances
+
+            // since our peakMax is determined by tenured.count(), but we are tenuring items here we keep things simple
+            // and do not account for those items we tenure but would later permit to scan as our peakMax grows
+
+            int ri = Math.min(minUntenuredIndex, minScanIndex);
+            while (ri < checkpointIndex)
+            {
+                RoutingKey end = ranges[ri].end();
+                int newPeakMax = scan.newPeakMax(tenured);
+                int scanLimit = scanLimit(ri, newPeakMax);
+                if (shouldTenure(end, scanLimit))
+                {
+                    // note: might have already been tenured
+                    // in this case our untenureLimit may be incorrect, but we won't use it
+                    if (ri >= minUntenuredIndex && newPeakMax < oldPeakMax)
+                        tenured.tenure(end, ri, ranges, scanLimit + 1, scanLimit(ri, oldPeakMax));
+                }
+                else
+                {
+                    // this might effectively remove a previously tenured item
+                    scan.update(end, ri, ranges, scanLimit, null);
+                }
+                ++ri;
+            }
+
+            scan.resetPeakMax(tenured);
+        }
+
+        pending.atIndex = checkpointIndex;
+        pending.clear();
+        tenured.rollover(pending);
+    }
+
+    private int extendScanDistance(int lastIndex, int scanDistance)
+    {
+        // now we've established our lower bound on scan distance, see how many checkpoints we can remove
+        // by increasing our scan distance so that it remains proportional to the number of results returned
+        // TODO (low priority, efficiency): can reduce cost here by using scanDistances array for upper bounds to scan distance
+        int maxScanDistance = scan.goal() + 2 * Math.min(tenured.count(), tenured.countAtPrevCheckpoint());
+        if (maxScanDistance >= 1 + scanDistance + scanDistance/4 && pending.count() >= (maxScanDistance - scanDistance)/2)
+        {
+            int removeCount = 0;
+            int extendedScanDistance = scanDistance;
+            int target = (maxScanDistance - scanDistance)/2;
+            for (int i = 0 ; i < pending.count() ; ++i)
+            {
+                Tenured t = pending.get(i);
+                if (t.index < 0)
+                    continue;
+
+                int distance = Math.min(lastIndex, t.lastIndex) - t.index;
+                if (distance <= scanDistance)
+                    continue; // already scanned or untenured
+
+                if (distance <= maxScanDistance)
+                {
+                    ++removeCount;
+                    extendedScanDistance = Math.max(extendedScanDistance, distance);
+                    if (extendedScanDistance == maxScanDistance && removeCount >= target)
+                        break;
+                }
+            }
+
+            // TODO (low priority, efficiency): should perhaps also gate this decision on the span we're covering
+            //  algorithmically, however, so long as we are under maxScanDistance we are fine
+            if (removeCount >= (extendedScanDistance - scanDistance)/2)
+                scanDistance = extendedScanDistance;
+        }
+        return scanDistance;
+    }
+
+    int writeList(PendingCheckpoint pending)
+    {
+        int startIndex = listCount;
+        for (int i = pending.count() - 1 ; i >= 0 ; --i)
+        {
+            Tenured t = pending.get(i);
+            if (t.index >= 0)
+            {
+                lists[listCount++] = t.index;
+            }
+            else
+            {
+                int index = t.index & ~BIT31;
+                int length = t.linkLength & ~BIT31;
+                if (length <= 0xff && index <= 0xfffff)
+                {
+                    lists[listCount++] = BIT31 | BIT30 | (length << 20) | index;
+                }
+                else if (t.linkLength >= 0 && length < BIT30)
+                {
+                    lists[listCount++] = BIT31 | BIT29 | index;
+                }
+                else
+                {
+                    lists[listCount++] = BIT31 | length;
+                    lists[listCount++] = BIT31 | pending.count();
+                }
+            }
+        }
+        return startIndex;
+    }
+
+    void writeHeader(int scanDistance, int lowerBound)
+    {
+        int headerScanDistance = Math.min(scanDistance, MAX_SCAN_DISTANCE);
+
+        if ((checkpointCount & 3) == 0)
+            headers[headerPointer++] = headerScanDistance;
+        else
+            headers[headerPointer - (1 + (checkpointCount & 3))] |= headerScanDistance << (8 * (checkpointCount & 3));
+
+        bounds[checkpointCount++] = lowerBound;
+        headers[headerPointer++] = listCount;
+
+        if (scanDistance >= MAX_SCAN_DISTANCE)
+            lists[listCount++] = -scanDistance; // serialize as a negative value so we ignore it in most cases automatically
+    }
+
+    void closeHeaders()
+    {
+        // write our final checkpoint header
+        if ((checkpointCount & 3) == 0) headers[headerPointer++] = 0;
+        headers[headerPointer++] = listCount;
+    }
+
+    void ensureCapacity(int maxPendingSize)
+    {
+        if (listCount + maxPendingSize >= lists.length)
+            lists = cachedInts().resize(lists, listCount, lists.length + lists.length/2 + maxPendingSize);
+    }
+
+    static class Scan
+    {
+        /** the scan distance we are aiming for; should be proportional to log2(N) */
+        int goal;
+
+        /** the indexes at which we increased the scan distance, and the new scan distance */
+        int[] distances = new int[16];
+        /** the number of unique scan distances we have adopted since the last checkpoint */
+        int count;
+        /** the highest scan distance we have adopted (==scanDistance(scanDistanceCount-1)) */
+        int watermark;
+        /**
+         * the first index we have tenured a range from, but for which we did not immediately write a new checkpoint
+         * we *must* scan at least from the last index in the checkpoint to here
+         */
+        int scanTenuredAtIndex = -1;
+
+        /** The maximum (i.e. initial) scan distance limit we have used since the last attempted checkpoint write */
+        int peakMax;
+
+        void init(int goalScanDistance)
+        {
+            goal = peakMax = goalScanDistance;
+        }
+
+        private void update(RoutingKey end, int atIndex, Range[] ranges, int scanLimit, SearchableRangeListBuilder checkpoint)
+        {
+            int newScanDistance = find(end, atIndex, ranges, scanLimit, watermark);
+            updateScanDistance(atIndex, newScanDistance, checkpoint);
+        }
+
+        private void updateScanDistance(int atIndex, int newScanDistance, SearchableRangeListBuilder checkpoint)
+        {
+            if (newScanDistance > watermark)
+            {
+                // TODO (desired, efficiency): we don't mind slight increases to the watermark;
+                //  should really look at scan distance history and ensure we haven't e.g. doubled since
+                //  some earlier point (and should track the match count + scan distance at each bump
+                //  to check overall work hasn't increased too much)
+                if (checkpoint != null && checkpoint.canWriteCheckpoint(atIndex))
+                    checkpoint.writeCheckpoint(atIndex);
+
+                watermark = newScanDistance;
+                if (count * 2 == distances.length)
+                    distances = Arrays.copyOf(distances, distances.length * 2);
+                distances[count * 2] = newScanDistance;
+                distances[count * 2 + 1] = atIndex;
+                ++count;
+            }
+        }
+
+        private int find(RoutingKey end, int atIndex, Range[] ranges, int scanLimit, int currentScanDistance)
+        {
+            int lowerIndex = SortedArrays.exponentialSearch(ranges, atIndex + currentScanDistance, scanLimit, end, (e, s) -> e.compareTo(s.start()), CEIL);
+            if (lowerIndex < 0) lowerIndex = -2 - lowerIndex;
+            else lowerIndex -= 1;
+            return lowerIndex - atIndex;
+        }
+
+        boolean isAboveGoal()
+        {
+            return watermark > goal;
+        }
+
+        int watermark()
+        {
+            return watermark;
+        }
+
+        int goal()
+        {
+            return goal;
+        }
+
+        int distanceToTenured(int lastIndex)
+        {
+            return scanTenuredAtIndex >= 0 ? lastIndex - scanTenuredAtIndex : 0;
+        }
+
+        boolean mustCheckpointToScanTenured(int checkpointIndex, int maxScanDistance)
+        {
+            return scanTenuredAtIndex >= 0 && checkpointIndex - scanTenuredAtIndex >= maxScanDistance;
+        }
+
+        /**
+         * Are we scanning a much longer distance than the minimum number of matches we know a query will return?
+         * Note: with Strategy.FAST, {@code tenured.count()} gets less accurate as scan distance increases, so this
+         * will bounce around triggering checkpoints due to the larger scan distance, resetting the scan distance
+         * and starting again
+         */
+        boolean hasMaybeDivergedFromMatchSize(TenuredSet tenured)
+        {
+            return isAboveGoal() && tenured.count() < watermark()/2;
+        }
+
+        private int distance(int i)
+        {
+            return distances[i*2];
+        }
+
+        private int index(int i)
+        {
+            return distances[i*2+1];
+        }
+
+        int finalise(int lastIndex)
+        {
+            Invariants.checkState(distanceToTenured(lastIndex) <= Math.max(watermark(), peakMax()));
+
+            int scanDistance = watermark;
+            // then, compute the minimum scan distance implied by any tenured ranges we did not immediately
+            // write a checkpoint for - we *must* scan back as far as this record
+            int minScanDistance = scanTenuredAtIndex >= 0 ? lastIndex - scanTenuredAtIndex : 0;
+            if (minScanDistance > scanDistance)
+            {
+                // if this minimum is larger than the largest scan distance we picked up for non-tenured ranges
+                // then we are done, as there's nothing we can save
+                scanDistance = minScanDistance;
+            }
+            else if (scanDistance > 0)
+            {
+                // otherwise, we can look to see if any of the scan distances we computed overflow the checkpoint,
+                // i.e. where no records served by this checkpoint need to scan the full distance to reach it
+                int distanceToLastScanIndex = lastIndex - index(count -1);
+                // if the distance to the last scan index is larger than its scan distance, we have overflowed;
+                if (distanceToLastScanIndex < scanDistance)
+                {
+                    minScanDistance = Math.max(distanceToLastScanIndex, minScanDistance);
+                    // loop until we find one that doesn't overflow, as this is another minimum scan distance
+                    int i = count - 1;
+                    while (--i >= 0)
+                    {
+                        int distance = lastIndex - index(i);
+                        if (distance >= distance(i)) break;
+                        else if (distance > minScanDistance) minScanDistance = distance;
+                    }
+                    if (i >= 0) scanDistance = Math.max(minScanDistance, distance(i));
+                    else scanDistance = minScanDistance;
+                }
+            }
+
+            return scanDistance;
+        }
+
+        void reset()
+        {
+            // we could in theory reset our scan distance using the contents of scanDistance[]
+            // but it's a bit complicated, as we want to have the first item to increment the scan distance
+            // so that we can use it in writeScanDistance to shrink the scan distance;
+            // jumping straight to the highest scan distance breaks this
+            count = 0;
+            scanTenuredAtIndex = -1;
+            watermark = 0;
+        }
+
+        void resetPeakMax(TenuredSet tenured)
+        {
+            peakMax = newPeakMax(tenured);
+        }
+
+        int peakMax()
+        {
+            return peakMax;
+        }
+
+        int newPeakMax(TenuredSet tenured)
+        {
+            return Math.max(goal, tenured.count());
+        }
+
+        /**
+         * The minimum index containing a range that might need to be tenured, if we have a smaller max scan distance than before
+         */
+        int minUntenuredIndex(int checkpointIndex, TenuredSet tenured)
+        {
+            int minUntenuredIndex = Math.max(0, (checkpointIndex - 1) - watermark());
+            // the maximum scan distance that cxould ever have been adopted for the ranges processed since last checkpoint
+            int oldPeakMax = peakMax;
+            int newMinPeakMax = newPeakMax(tenured);
+            if (newMinPeakMax < oldPeakMax)
+            {
+                // minimise range we unnecessarily re-tenure over
+                // TODO (low priority, efficiency): see if can also use to reduce range we re-scan e.g. can recycle
+                //  scanDistances contents if we know we won't need to step back further at next checkpoint
+                for (int i = count - 1; i >= 0 ; --i)
+                {
+                    if (index(i) <= minUntenuredIndex)
+                        break;
+                    if (distance(i) <= newMinPeakMax)
+                        return i + 1 == count ? index(i) : index(i + 1) - 1;
+                }
+            }
+            return minUntenuredIndex;
+        }
+
+        /**
+         * Record that a range at this index has been tenured, so that we can track how far back
+         * we need to scan to determine how long we can defer writing a new checkpoint while still
+         * being able to scan it.
+         *
+         * TODO (low priority, efficiency): when a checkpoint is written, we should consider moving it
+         *  earlier if the scan distance is increased primarily because of this index, and the tenured
+         *  collection is otherwise unchanged (so can be written with minimal overhead)
+         */
+        void tenured(int atIndex)
+        {
+            if (scanTenuredAtIndex < 0)
+                scanTenuredAtIndex = atIndex;
+        }
+
+        static int minScanIndex(int checkpointIndex, int scanDistance)
+        {
+            return Math.max(0, (checkpointIndex - 1) - scanDistance);
+        }
+
+        @Override
+        public String toString()
+        {
+            return "Scan{watermark=" + watermark + ", tenured=" + scanTenuredAtIndex + '}';
+        }
+    }
+
+    /**
+     * Record-keeping for a range we have decided is not scannable
+     */
+    static class Tenured implements Comparable<Tenured>
+    {
+        /**
+         * The end of the tenured range covered by the contents referred to be {@link #index}
+         */
+        RoutingKey end;
+
+        /**
+         * <ul>
+         * <li>If positive, this points to {@code ranges[index]}</li>
+         * <li>If negative, this points to an entry in {@link #lists};
+         * see {@link SearchableRangeList#checkpointLists}</li>
+         * </ul>
+         */
+        int index;
+
+        /**
+         * The last index in {@link #ranges} covered by this tenured range
+         */
+        int lastIndex;
+
+        /**
+         * set when this record is serialized in a checkpoint list to either:
+         * <ul>
+         * <li>point to itself, in which case no action should be
+         *     taken on removal (it is only retained for size bookkeeping); or</li>
+         * <li>point to the next item in the checkpoint list; the first
+         *     such element removed triggers the clearing of the checkpoint
+         *     list so that its entries are re-inserted in the next checkpoint</li>
+         * </ul>
+         */
+        Tenured next;
+
+        /**
+         * Only set for link entries, i.e. where {@code index < 0}.
+         * <ul>
+         * <li>if positive, the length is optional as we will terminate safely using the end bound filtering</li>
+         * <li>if negative, the low 31 bits <b>must</b> be retrieved as the length for safe iteration</li>
+         * </ul>
+         */
+        int linkLength;
+
+        Tenured(RoutingKey end, int index)
+        {
+            this.end = end;
+            this.index = index;
+        }
+
+        @Override
+        public int compareTo(@Nonnull Tenured that)
+        {
+            int c = this.end.compareTo(that.end);
+            // we sort indexes in reverse order so later tenured items find the earlier ones with same end when searching
+            // for higher entries for the range of indexes to search, and
+            if (c == 0) c = -Integer.compare(this.index, that.index);
+            return c;
+        }
+
+        @Override
+        public String toString()
+        {
+            return "Tenured{end=" + end + ", index=" + index + '}';
+        }
+    }
+
+    /**
+     * The set of ranges that we intend to write to checkpoints that remain open at the current point in the iteration
+     * This collection may be filtered before serialization, but every member will be visited either by scanning
+     * or visiting the checkpoint list
+     * TODO (low priority, efficiency): save garbage by using an insertion-sorted array for collections where
+     *  this is sufficient. later, introduce a mutable b-tree supporting object recycling. we would also like
+     *  to use a collection that permits us to insert and return a finger into the tree so we can find the
+     *  successor as part of insertion, and that permits constant-time first() calls
+     */
+    static class TenuredSet extends TreeSet<Tenured>
+    {
+        /**
+         * the number of direct tenured entries (i.e. ignoring link entries)
+         * this is used to provide a minimum bound on the number of results a range query can return
+         * note: with Strategy.FAST this gets less accurate as the span distance increases
+         */
+        int directCount;
+        int directCountAtPrevCheckpoint;
+        int minSpan;
+
+        // a stack of recently used EndAndIndex objects - used only for the duration of a single build
+        Tenured reuse, pendingReuse, pendingReuseTail;
+
+        int count()
+        {
+            return directCount;
+        }
+
+        int countAtPrevCheckpoint()
+        {
+            return directCountAtPrevCheckpoint;
+        }
+
+        /**
+         * We require a checkpoint to cover a distance at least as large as the number of tenured ranges leftover
+         * since the prior checkpoint, to ensure these require at most linear additional space, while not requiring
+         * more than O(k) additional complexity on search (i.e., we will scan a number of elements at most equal
+         * to the number we have to visit in the checkpoint).
+         *
+         * We achieve this by recording the minimum number of match results as of the prior checkpoint (i.e. {@link #count()})
+         * and discounting it by one each time we untenure a range, so that for each tenured range from the prior checkpoint
+         * we have either untenured a range or processed at least one additional input.
+         */
+        int minimumSpan()
+        {
+            return minSpan;
+        }
+
+        private int tenure(RoutingKey end, int index, Range[] ranges, int minUntenureIndex)
+        {
+            return tenure(newTenured(end, index), ranges, minUntenureIndex, ranges.length);
+        }
+
+        private void tenure(RoutingKey end, int index, Range[] ranges, int minUntenureIndex, int untenureLimit)
+        {
+            tenure(newTenured(end, index), ranges, minUntenureIndex, untenureLimit);
+        }
+
+        private int tenure(Tenured tenure, Range[] ranges, int untenureMinIndex, int untenureLimit)
+        {
+            if (!add(tenure))
+                return tenure.lastIndex;
+
+            Tenured next = higher(tenure);
+            if (next != null)
+                untenureLimit = Math.min(untenureLimit, next.lastIndex + 1);
+            int untenureIndex = SortedArrays.binarySearch(ranges, untenureMinIndex, untenureLimit, tenure.end, (e, s) -> e.compareTo(s.start()), CEIL);
+            if (untenureIndex < 0) untenureIndex = -1 - untenureIndex;
+            tenure.lastIndex = untenureIndex - 1;
+            Invariants.checkState(tenure.end.compareTo(ranges[tenure.lastIndex].start()) > 0);
+            Invariants.checkState(tenure.lastIndex + 1 == ranges.length || tenure.end.compareTo(ranges[tenure.lastIndex + 1].start()) <= 0);
+            ++directCount;
+            return untenureIndex - 1;
+        }
+
+        private Tenured newTenured(RoutingKey end, int index)
+        {
+            Tenured result = reuse;
+            if (result == null)
+                return new Tenured(end, index);
+
+            reuse = result.next;
+            result.end = end;
+            result.index = index;
+            result.lastIndex = 0;
+            result.next = null;
+            return result;
+        }
+
+        private Tenured addLinkEntry(RoutingKey end, int index, int lastIndex, int length)
+        {
+            Invariants.checkArgument(index < 0);
+            Tenured result = newTenured(end, index);
+            result.linkLength = length;
+            result.lastIndex = lastIndex;
+            add(result);
+            return result;
+        }
+
+        /**
+         * Retire any active tenured ranges that no longer cover the pointer into ranges;
+         * if this crosses our checkpoint threshold, write a new checkpoint.
+         */
+        void untenure(int index)
+        {
+            while (!isEmpty() && first().lastIndex < index)
+            {
+                Tenured removed = pollFirst();
+
+                // if removed.next == null, this is not referenced by a link
+                // if removed.next == removed, it is referenced by a link but does not modify the link on removal
+                if (removed.next != null && removed.next != removed)
+                {
+                    // this is a member of a link's chain, which may serve one of two purposes:
+                    // 1) it may be the entry nominated to invalidate the link, due to the link
+                    //    membership shrinking below the required threshold; in which case we
+                    //    must clear the chain to reactivate its members for insertion into the
+                    //    next checkpoint, and remove the chain link itself
+                    // 2) it may be nominated as an entry to update the chain link info, to make
+                    //    it more succinct: if every entry of the chain remains active, and there
+                    //    are *many* entries then we need two integers to represent the chain, but
+                    //    as soon as any entry is invalid we can rely on this entry to terminate
+                    //    iteration, so we update the bookkeeping on the first entry we remove in
+                    //    this case
+
+                    // first clear the chain starting at the removed entry
+                    Tenured prev = removed, next = removed.next;
+                    while (next.next != null)
+                    {
+                        prev = next;
+                        next = next.next;
+                        prev.next = null;
+                    }
+                    Invariants.checkState(next.index < 0);
+                    if (prev.end == next.end)
+                    {
+                        // if this is the last entry in the link, the link is expired and should be removed/reused
+                        remove(next);
+                        if (pendingReuseTail == null)
+                            pendingReuseTail = next;
+                        next.next = pendingReuse;
+                        pendingReuse = next;
+                    }
+                    else if (next.linkLength < 0)
+                    {
+                        // otherwise, flag the link as safely consumed without knowing the length
+                        next.linkLength = next.linkLength & Integer.MAX_VALUE;
+                    }
+                }
+
+                // this was not a link reference; update our bookkeeping and save it for reuse
+                Invariants.checkState(removed.index >= 0);
+                --directCount;
+                --minSpan;
+                if (pendingReuseTail == null)
+                    pendingReuseTail = removed;
+                removed.next = pendingReuse;
+                pendingReuse = removed;
+            }
+        }
+
+        /**
+         * Write out any direct entries that are not pointed to by a chain entry, and any chain entries;
+         * rollover any per-checkpoint data and free up for reuse discarded Tenured objects
+         */
+        void rollover(PendingCheckpoint pending)
+        {
+            for (Tenured tenured : this)
+            {
+                if (tenured.next == null)
+                    pending.add(tenured);
+            }
+            // make freed Tenured objects available for reuse
+            if (pendingReuse != null)
+            {
+                pendingReuseTail.next = reuse;
+                reuse = pendingReuse;
+                pendingReuseTail = pendingReuse = null;
+            }
+            directCountAtPrevCheckpoint = minSpan = directCount;
+        }
+    }
+
+    /**
+     * we write checkpoints out before knowing the scan distance needed for the range, as a checkpoint precedes
+     * the ranges it covers; so we record the position and contents of the checkpoint, and once the scan distance is
+     * known (i.e. when the next checkpoint is written) we re-process the list to remove items we can now scan before
+     * serializing to checkpointListsBuf.
+     */
+    static class PendingCheckpoint
+    {
+        int atIndex = -1;
+        int count;
+
+        Tenured[] contents = new Tenured[10];
+
+        int openDirectCount, firstOpenDirect, openIndirectCount;
+        boolean hasClosedDirect;
+
+        int count()
+        {
+            return count;
+        }
+
+        Tenured get(int i)
+        {
+            return contents[i];
+        }
+
+        void add(Tenured tenured)
+        {
+            if (contents.length == count)
+                contents = Arrays.copyOf(contents, 2 * contents.length);
+            contents[count++] = tenured;
+        }
+
+        void clear()
+        {
+            count = 0;
+        }
+
+        /**
+         * Remove pending entries that will be scanned by the scanDistance, and update
+         * our bookkeeping for creating links
+         */
+        int filter(int scanDistance, int lastIndex)
+        {
+            int matchCountModifier = 0;
+            int maxi = count;
+            count = 0;
+            openDirectCount = 0;
+            openIndirectCount = 0;
+            firstOpenDirect = -1;
+//            lastClosedDirect = -1;
+
+            for (int i = 0; i < maxi ; ++i)
+            {
+                Tenured t = get(i);
+                if (t.index >= 0)
+                {
+                    if (t.index + scanDistance >= lastIndex)
+                        continue; // last index will find it with a scan
+
+                    if (t.lastIndex <= t.index + scanDistance)
+                        continue; // all indexes will find it with a scan
+
+                    if (t.lastIndex > lastIndex)
+                    {
+                        // this range remains open for the next checkpoint;
+                        // we may want to reference this list from there
+                        // so track count and position of first one to make a determination
+                        ++openDirectCount;
+                        if (firstOpenDirect < 0) firstOpenDirect = count;
+                    }
+                    else hasClosedDirect = true;
+                }
+                else
+                {
+                    // note: we over count here, as we count pointers within the chain
+                    matchCountModifier += (t.linkLength & Integer.MAX_VALUE) - 1; // (subtract 1 to discount the pointer)
+                    if (t.lastIndex > lastIndex)
+                        ++openIndirectCount;
+                }
+
+                if (i == count) ++count;
+                else contents[count++] = t;
+            }
+
+            return count + matchCountModifier;
+        }
+
+        /**
+         * Setup a link for referencing this chain later, if permitted.
+         * Must have at least two items, and at least as many direct records as indirect
+         */
+        void setupLinkChain(TenuredSet tenured, int startIndex, int endIndex)
+        {
+            int minSizeToReference = openIndirectCount + MIN_INDIRECT_LINK_LENGTH;
+            if (openDirectCount >= minSizeToReference)
+            {
+                int i = firstOpenDirect;
+                Tenured prev = get(i++);
+
+                while (openDirectCount > minSizeToReference)
+                {
+                    Tenured e = get(i++);
+                    if (e.index < 0)
+                    {
+                        --minSizeToReference;
+                        continue;
+                    }
+
+                    Invariants.checkState(prev.next == null);
+                    prev.next = prev;
+                    prev = e;
+                    --openDirectCount;
+                }
+
+                while (i < count)
+                {
+                    Tenured next = get(i++);
+                    if (next.index < 0)
+                        continue;
+
+                    Invariants.checkState(prev.next == null);
+                    prev.next = next;
+                    prev = next;
+                }
+
+                // may be more than one entry per item (though usually not)
+                int length = endIndex - startIndex;
+                Tenured chainEntry = tenured.addLinkEntry(prev.end, BIT31 | startIndex, prev.lastIndex, length);
+                prev.next = chainEntry;
+                if (hasClosedDirect && (startIndex > 0xfffff || (length > 0xff)))
+                {
+                    // TODO (expected, testing): make sure this is tested, as not a common code path (may never be executed in normal operation)
+                    // we have no closed ranges so iteration needs to know the end bound, but we cannot encode our bounds cheaply
+                    // so link the first bound to the chain entry, so that on removal it triggers an update of endIndex to note
+                    // that it can be iterated safely without an end bound
+                    get(firstOpenDirect).next = chainEntry;
+                }
+            }
+        }
+
+        @Override
+        public String toString()
+        {
+            return Arrays.stream(contents, 0, count)
+                    .map(Objects::toString)
+                    .collect(Collectors.joining(",", "[", "]"));
+        }
+    }
+}
diff --git a/accord-core/src/main/java/accord/utils/SortedArrays.java b/accord-core/src/main/java/accord/utils/SortedArrays.java
index 542f8e2..85c49c7 100644
--- a/accord-core/src/main/java/accord/utils/SortedArrays.java
+++ b/accord-core/src/main/java/accord/utils/SortedArrays.java
@@ -29,7 +29,13 @@ import net.nicoulaj.compilecommand.annotations.Inline;
 import javax.annotation.Nullable;
 
 import static accord.utils.ArrayBuffers.uncached;
+import static accord.utils.SortedArrays.Search.FAST;
 
+// TODO (low priority, efficiency): improvements:
+//        - Either by manually duplicating or using compiler inlining directives to
+//           - compile separate versions for Comparators vs Comparable.compareTo
+//           - compile dedicated binarySearch and exponentialSearch functions for FLOOR, CEIL, HIGHER, LOWER
+//        - Exploit exponentialSearch in union/intersection/etc
 public class SortedArrays
 {
     /**
@@ -71,6 +77,11 @@ public class SortedArrays
      * and it would not be much costlier.
      */
     public static <T extends Comparable<? super T>> T[] linearUnion(T[] left, int leftLength, T[] right, int rightLength, ObjectBuffers<T> buffers)
+    {
+        return linearUnion(left, leftLength, right, rightLength, Comparable::compareTo, buffers);
+    }
+
+    public static <T> T[] linearUnion(T[] left, int leftLength, T[] right, int rightLength, AsymmetricComparator<? super T, ? super T> comparator, ObjectBuffers<T> buffers)
     {
         int leftIdx = 0;
         int rightIdx = 0;
@@ -86,7 +97,7 @@ public class SortedArrays
             {
                 T leftKey = left[leftIdx];
                 T rightKey = right[rightIdx];
-                int cmp = leftKey == rightKey ? 0 : leftKey.compareTo(rightKey);
+                int cmp = leftKey == rightKey ? 0 : comparator.compare(leftKey, rightKey);
 
                 if (cmp <= 0)
                 {
@@ -119,7 +130,7 @@ public class SortedArrays
             {
                 T leftKey = left[leftIdx];
                 T rightKey = right[rightIdx];
-                int cmp = leftKey == rightKey ? 0 : leftKey.compareTo(rightKey);
+                int cmp = leftKey == rightKey ? 0 : comparator.compare(leftKey, rightKey);
 
                 if (cmp >= 0)
                 {
@@ -153,7 +164,7 @@ public class SortedArrays
             {
                 T leftKey = left[leftIdx];
                 T rightKey = right[rightIdx];
-                int cmp = leftKey == rightKey ? 0 : leftKey.compareTo(rightKey);
+                int cmp = leftKey == rightKey ? 0 : comparator.compare(leftKey, rightKey);
 
                 T minKey;
                 if (cmp == 0)
@@ -220,7 +231,7 @@ public class SortedArrays
      *
      * TODO (low priority, efficiency): introduce exponential search optimised version
      */
-    public static <T> T[] linearIntersection(T[] left, int leftLength, T[] right, int rightLength, Comparator<T> comparator, ObjectBuffers<T> buffers)
+    public static <T> T[] linearIntersection(T[] left, int leftLength, T[] right, int rightLength, AsymmetricComparator<? super T, ? super T> comparator, ObjectBuffers<T> buffers)
     {
         int leftIdx = 0;
         int rightIdx = 0;
@@ -544,7 +555,7 @@ public class SortedArrays
      */
     public static <T1, T2 extends Comparable<? super T1>> int exponentialSearch(T1[] in, int from, int to, T2 find)
     {
-        return exponentialSearch(in, from, to, find, Comparable::compareTo, Search.FAST);
+        return exponentialSearch(in, from, to, find, Comparable::compareTo, FAST);
     }
 
     public enum Search
@@ -736,6 +747,7 @@ public class SortedArrays
      * Given two sorted arrays where an item in each array may match at most one in the other, find the next
      * index in each array containing an equal item.
      */
+    @Inline
     public static <T extends Comparable<? super T>> long findNextIntersection(T[] as, int ai, T[] bs, int bi)
     {
         return findNextIntersection(as, ai, as.length, bs, bi, bs.length);
@@ -745,18 +757,30 @@ public class SortedArrays
      * Given two sorted arrays where an item in each array may match at most one in the other, find the next
      * index in each array containing an equal item.
      */
+    @Inline
     public static <T extends Comparable<? super T>> long findNextIntersection(T[] as, int ai, int alim, T[] bs, int bi, int blim)
     {
-        return findNextIntersection(as, ai, alim, bs, bi, blim, Comparable::compareTo, Comparable::compareTo, Search.FAST);
+        return findNextIntersection(as, ai, alim, bs, bi, blim, Comparable::compareTo, Comparable::compareTo, FAST);
+    }
+
+    /**
+     * Given two sorted arrays where an item in each array may match at most one in the other, find the next
+     * index in each array containing an equal item.
+     */
+    @Inline
+    public static <T> long findNextIntersection(T[] as, int ai, int alim, T[] bs, int bi, int blim, AsymmetricComparator<? super T, ? super T> comparator)
+    {
+        return findNextIntersection(as, ai, alim, bs, bi, blim, comparator, comparator, FAST);
     }
 
     /**
      * Given two sorted arrays where an item in each array may match at most one in the other, find the next
      * index in each array containing an equal item.
      */
+    @Inline
     public static <T> long findNextIntersection(T[] as, int ai, T[] bs, int bi, AsymmetricComparator<T, T> comparator)
     {
-        return findNextIntersection(as, ai, as.length, bs, bi, bs.length, comparator, comparator, Search.FAST);
+        return findNextIntersection(as, ai, as.length, bs, bi, bs.length, comparator, comparator, FAST);
     }
 
     /**
@@ -765,7 +789,8 @@ public class SortedArrays
      * Works with CEIL or FAST; FAST to be used if precisely one match for each item in either list, CEIL if one item
      * in either list may be matched to multiple in the other list.
      */
-    private static <T1, T2> long findNextIntersection(T1[] as, int ai, int asLength, T2[] bs, int bi, int bsLength, AsymmetricComparator<T1, T2> cmp1, AsymmetricComparator<T2, T1> cmp2, Search op)
+    @Inline
+    private static <T1, T2> long findNextIntersection(T1[] as, int ai, int asLength, T2[] bs, int bi, int bsLength, AsymmetricComparator<? super T1, ? super T2> cmp1, AsymmetricComparator<? super T2, ? super T1> cmp2, Search op)
     {
         if (ai == asLength)
             return -1;
@@ -808,6 +833,13 @@ public class SortedArrays
     @Nullable
     public static <T extends Comparable<? super T>> int[] remapToSuperset(T[] src, int srcLength, T[] trg, int trgLength,
                                                                           IntBufferAllocator allocator)
+    {
+        return remapToSuperset(src, srcLength, trg, trgLength, Comparable::compareTo, allocator);
+    }
+
+    @Nullable
+    public static <T> int[] remapToSuperset(T[] src, int srcLength, T[] trg, int trgLength, AsymmetricComparator<? super T, ? super T> comparator,
+                                            IntBufferAllocator allocator)
     {
         if (src == trg || trgLength == srcLength)
             return null;
@@ -819,7 +851,7 @@ public class SortedArrays
         {
             if (src[i] != trg[j] && !src[i].equals(trg[j]))
             {
-                j = SortedArrays.exponentialSearch(trg, j, trgLength, src[i]);
+                j = SortedArrays.exponentialSearch(trg, j, trgLength, src[i], comparator, FAST);
                 if (j < 0)
                 {
                     if (i > 0 && src[i] == src[i-1])
@@ -845,10 +877,16 @@ public class SortedArrays
      */
     @Inline
     public static <T extends Comparable<? super T>> long foldlIntersection(T[] as, int ai, int alim, T[] bs, int bi, int blim, IndexedFoldIntersectToLong<? super T> fold, long param, long initialValue, long terminalValue)
+    {
+        return foldlIntersection(Comparable::compareTo, as, ai, alim, bs, bi, blim, fold, param, initialValue, terminalValue);
+    }
+
+    @Inline
+    public static <T> long foldlIntersection(AsymmetricComparator<? super T, ? super T> comparator, T[] as, int ai, int alim, T[] bs, int bi, int blim, IndexedFoldIntersectToLong<? super T> fold, long param, long initialValue, long terminalValue)
     {
         while (true)
         {
-            long abi = findNextIntersection(as, ai, alim, bs, bi, blim);
+            long abi = findNextIntersection(as, ai, alim, bs, bi, blim, comparator);
             if (abi < 0)
                 break;
 
@@ -865,4 +903,43 @@ public class SortedArrays
 
         return initialValue;
     }
+
+    public static <T extends Comparable<T>> void assertSorted(T[] array)
+    {
+        if (!isSorted(array))
+            throw new IllegalArgumentException(Arrays.toString(array) + " is not sorted");
+    }
+
+    public static <T extends Comparable<T>> boolean isSorted(T[] array)
+    {
+        return isSorted(array, Comparable::compareTo);
+    }
+
+    public static <T> boolean isSorted(T[] array, Comparator<T> comparator)
+    {
+        return isSorted(array, comparator, 1);
+    }
+
+
+    public static <T extends Comparable<T>> boolean isSortedUnique(T[] array)
+    {
+        return isSortedUnique(array, Comparable::compareTo);
+    }
+
+    public static  <T> boolean isSortedUnique(T[] array, Comparator<T> comparator)
+    {
+        return isSorted(array, comparator, 0);
+    }
+
+    private static <T> boolean isSorted(T[] array, Comparator<T> comparator, int compareTo)
+    {
+        for (int i = 1 ; i < array.length ; ++i)
+        {
+            if (comparator.compare(array[i - 1], array[i]) >= compareTo)
+                return false;
+        }
+        return true;
+    }
+
+
 }
diff --git a/accord-core/src/main/java/accord/utils/SymmetricComparator.java b/accord-core/src/main/java/accord/utils/SymmetricComparator.java
new file mode 100644
index 0000000..ff66ca6
--- /dev/null
+++ b/accord-core/src/main/java/accord/utils/SymmetricComparator.java
@@ -0,0 +1,7 @@
+package accord.utils;
+
+import java.util.Comparator;
+
+public interface SymmetricComparator<T> extends AsymmetricComparator<T, T>, Comparator<T>
+{
+}
diff --git a/accord-core/src/test/java/accord/coordinate/CoordinateTest.java b/accord-core/src/test/java/accord/coordinate/CoordinateTest.java
index 8017b21..08471f6 100644
--- a/accord-core/src/test/java/accord/coordinate/CoordinateTest.java
+++ b/accord-core/src/test/java/accord/coordinate/CoordinateTest.java
@@ -22,10 +22,7 @@ import accord.local.Node;
 import accord.impl.mock.MockCluster;
 import accord.api.Result;
 import accord.impl.mock.MockStore;
-import accord.primitives.Keys;
-import accord.primitives.FullKeyRoute;
-import accord.primitives.Txn;
-import accord.primitives.TxnId;
+import accord.primitives.*;
 import org.junit.jupiter.api.Assertions;
 import org.junit.jupiter.api.Test;
 
diff --git a/accord-core/src/test/java/accord/messages/PreAcceptTest.java b/accord-core/src/test/java/accord/messages/PreAcceptTest.java
index f1f1117..6619555 100644
--- a/accord-core/src/test/java/accord/messages/PreAcceptTest.java
+++ b/accord-core/src/test/java/accord/messages/PreAcceptTest.java
@@ -109,7 +109,8 @@ public class PreAcceptTest
 
             messageSink.assertHistorySizes(0, 1);
             Assertions.assertEquals(ID2, messageSink.responses.get(0).to);
-            Assertions.assertEquals(new PreAccept.PreAcceptOk(txnId, txnId, PartialDeps.NONE),
+            PartialDeps expectedDeps = new PartialDeps(Ranges.of(range(0, 12)), KeyDeps.NONE, RangeDeps.NONE);
+            Assertions.assertEquals(new PreAccept.PreAcceptOk(txnId, txnId, expectedDeps),
                                     messageSink.responses.get(0).payload);
         }
         finally
@@ -168,7 +169,7 @@ public class PreAcceptTest
 
             messageSink.assertHistorySizes(0, 1);
             Assertions.assertEquals(ID3, messageSink.responses.get(0).to);
-            PartialDeps expectedDeps = Deps.NONE.slice(ranges(range(0, 12)));
+            PartialDeps expectedDeps = new PartialDeps(Ranges.of(range(0, 12)), KeyDeps.NONE, RangeDeps.NONE);
             Assertions.assertEquals(new PreAccept.PreAcceptOk(txnId2, Timestamp.fromValues(1, 110, ID1), expectedDeps),
                                     messageSink.responses.get(0).payload);
         }
@@ -199,7 +200,7 @@ public class PreAcceptTest
 
             messageSink.assertHistorySizes(0, 1);
             Assertions.assertEquals(ID2, messageSink.responses.get(0).to);
-            PartialDeps expectedDeps = PartialDeps.NONE;
+            PartialDeps expectedDeps = new PartialDeps(Ranges.of(range(0, 12)), KeyDeps.NONE, RangeDeps.NONE);
             Assertions.assertEquals(new PreAccept.PreAcceptOk(txnId, txnId, expectedDeps),
                                     messageSink.responses.get(0).payload);
         }
@@ -237,7 +238,8 @@ public class PreAcceptTest
 
             messageSink.assertHistorySizes(0, 1);
             Assertions.assertEquals(ID2, messageSink.responses.get(0).to);
-            Assertions.assertEquals(new PreAccept.PreAcceptOk(txnId, Timestamp.fromValues(2, 110, ID1), Deps.NONE.slice(ranges(range(0, 12)))),
+            PartialDeps expectedDeps = new PartialDeps(Ranges.of(range(0, 12)), KeyDeps.NONE, RangeDeps.NONE);
+            Assertions.assertEquals(new PreAccept.PreAcceptOk(txnId, Timestamp.fromValues(2, 110, ID1), expectedDeps),
                                     messageSink.responses.get(0).payload);
         }
         finally
diff --git a/accord-core/src/test/java/accord/txn/DepsTest.java b/accord-core/src/test/java/accord/primitives/KeyDepsTest.java
similarity index 83%
rename from accord-core/src/test/java/accord/txn/DepsTest.java
rename to accord-core/src/test/java/accord/primitives/KeyDepsTest.java
index 9c480ad..c490041 100644
--- a/accord-core/src/test/java/accord/txn/DepsTest.java
+++ b/accord-core/src/test/java/accord/primitives/KeyDepsTest.java
@@ -16,30 +16,24 @@
  * limitations under the License.
  */
 
-package accord.txn;
-
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.List;
-import java.util.Map;
-import java.util.Random;
-import java.util.Set;
-import java.util.TreeMap;
-import java.util.TreeSet;
+package accord.primitives;
+
+import java.util.*;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
 import java.util.concurrent.Executors;
 import java.util.concurrent.Future;
 import java.util.concurrent.ThreadLocalRandom;
 import java.util.function.BiConsumer;
+import java.util.function.Function;
 import java.util.function.Supplier;
 import java.util.stream.IntStream;
 
 import accord.impl.IntHashKey.Hash;
-import accord.primitives.*;
-import accord.primitives.Deps.OrderedBuilder;
+import accord.primitives.KeyDeps.Builder;
 import accord.utils.Gen;
 import accord.utils.Gens;
+import accord.utils.RelationMultiMap.Entry;
 import com.google.common.collect.Sets;
 import org.junit.jupiter.api.Assertions;
 import org.junit.jupiter.api.Test;
@@ -50,7 +44,6 @@ import org.slf4j.LoggerFactory;
 import accord.api.Key;
 import accord.impl.IntHashKey;
 import accord.local.Node.Id;
-import accord.primitives.Deps.Entry;
 
 import static accord.utils.Gens.lists;
 import static accord.utils.Property.qt;
@@ -58,9 +51,9 @@ import static accord.utils.Utils.toArray;
 
 // TODO (expected, testing): test Keys with no contents, "without", "with" where TxnId and Keys are the same, but Key -> [TxnId] does not match;
 //  ensure high code coverage
-public class DepsTest
+public class KeyDepsTest
 {
-    private static final Logger logger = LoggerFactory.getLogger(DepsTest.class);
+    private static final Logger logger = LoggerFactory.getLogger(KeyDepsTest.class);
 
     @Test
     public void testRandom()
@@ -87,7 +80,7 @@ public class DepsTest
         List<Deps> deps = new ArrayList<>(count);
         while (count-- > 0)
             deps.add(supplier.get());
-        testOneDeps(random, DepsTest.Deps.merge(deps), 200);
+        testOneDeps(random, KeyDepsTest.Deps.merge(deps), 200);
     }
 
     @Test
@@ -118,12 +111,12 @@ public class DepsTest
             // no matches
             Assertions.assertSame(deps.test, deps.test.without(ignore -> false));
             // all match
-            Assertions.assertSame(accord.primitives.Deps.NONE, deps.test.without(ignore -> true));
+            Assertions.assertSame(accord.primitives.KeyDeps.NONE, deps.test.without(ignore -> true));
 
             // remove specific TxnId
             for (TxnId txnId : deps.test.txnIds())
             {
-                accord.primitives.Deps without = deps.test.without(i -> i.equals(txnId));
+                accord.primitives.KeyDeps without = deps.test.without(i -> i.equals(txnId));
                 // Was the TxnId removed?
                 List<TxnId> expectedTxnId = new ArrayList<>(deps.test.txnIds());
                 expectedTxnId.remove(txnId);
@@ -150,7 +143,7 @@ public class DepsTest
         });
     }
 
-    private static List<TxnId> get(accord.primitives.Deps deps, Key key)
+    private static List<TxnId> get(accord.primitives.KeyDeps deps, Key key)
     {
         List<TxnId> ids = new ArrayList<>();
         deps.forEach(key, ids::add);
@@ -161,7 +154,7 @@ public class DepsTest
     public void testIterator()
     {
         qt().forAll(Deps::generate).check(deps -> {
-            try (OrderedBuilder builder = accord.primitives.Deps.orderedBuilder(true))
+            try (Builder builder = accord.primitives.KeyDeps.builder())
             {
                 for (Map.Entry<Key, TxnId> e : deps.test)
                     builder.add(e.getKey(), e.getValue());
@@ -181,7 +174,7 @@ public class DepsTest
                 throw new AssertionError(start + " == " + end);
 
             TreeSet<TxnId> seen = new TreeSet<>();
-            deps.test.forEachOn(Ranges.of(Range.range(start.toUnseekable(), end.toUnseekable(), false, true)), txnId -> {
+            deps.test.forEachUniqueTxnId(Ranges.of(Range.range(start.toUnseekable(), end.toUnseekable(), false, true)), txnId -> {
                 if (!seen.add(txnId))
                     throw new AssertionError("Seen " + txnId + " multiple times");
             });
@@ -205,7 +198,7 @@ public class DepsTest
             Key end = keys.get(keys.size() - 1);
 
             TreeSet<TxnId> seen = new TreeSet<>();
-            deps.test.forEachOn(Ranges.of(Range.range(start.toUnseekable(), end.toUnseekable(), true, false)), txnId -> {
+            deps.test.forEachUniqueTxnId(Ranges.of(Range.range(start.toUnseekable(), end.toUnseekable(), true, false)), txnId -> {
                 if (!seen.add(txnId))
                     throw new AssertionError("Seen " + txnId + " multiple times");
             });
@@ -229,7 +222,7 @@ public class DepsTest
             Key end = keys.get(0);
 
             TreeSet<TxnId> seen = new TreeSet<>();
-            deps.test.forEachOn(Ranges.of(Range.range(start.toUnseekable(), end.toUnseekable(), true, false)), txnId -> {
+            deps.test.forEachUniqueTxnId(Ranges.of(Range.range(start.toUnseekable(), end.toUnseekable(), true, false)), txnId -> {
                 if (!seen.add(txnId))
                     throw new AssertionError("Seen " + txnId + " multiple times");
             });
@@ -240,14 +233,14 @@ public class DepsTest
     @Test
     public void testMergeFull()
     {
-        qt().forAll(lists(Deps::generate).ofSizeBetween(0, 20)).check(DepsTest::testMergedProperty);
+        qt().forAll(lists(Deps::generate).ofSizeBetween(0, 20)).check(KeyDepsTest::testMergedProperty);
     }
 
     @Test
     public void testMergeFullConcurrent()
     {
         // pure=false due to shared buffer pool
-        Runnable test = () -> qt().withPure(false).forAll(lists(Deps::generate).ofSizeBetween(0, 20)).check(DepsTest::testMergedProperty);
+        Runnable test = () -> qt().withPure(false).forAll(lists(Deps::generate).ofSizeBetween(0, 20)).check(KeyDepsTest::testMergedProperty);
         int numThreads = Runtime.getRuntime().availableProcessors() * 4;
         ExecutorService executor = Executors.newFixedThreadPool(numThreads);
         List<Future<?>> futures = new ArrayList<>(numThreads);
@@ -276,33 +269,35 @@ public class DepsTest
         expected.testSimpleEquality();
 
         // slightly redundant due to Deps.merge using this method... it is here for completeness
-        Assertions.assertEquals(expected.test, accord.primitives.Deps.merge(list, a -> a.test));
-        Assertions.assertEquals(expected.test, list.stream().map(a -> a.test).reduce(accord.primitives.Deps.NONE, accord.primitives.Deps::with));
+        Assertions.assertEquals(expected.test, accord.primitives.KeyDeps.merge(list, a -> a.test, Function.identity()));
+        Assertions.assertEquals(expected.test, list.stream().map(a -> a.test).reduce(accord.primitives.KeyDeps.NONE, accord.primitives.KeyDeps::with));
     }
 
     @Test
-    public void orderedBuilder()
+    public void builder()
     {
         qt().forAll(Deps::generate, Gens.random()).check((deps, random) -> {
-            OrderedBuilder builder = accord.primitives.Deps.orderedBuilder(false);
-            for (Key key : deps.canonical.keySet())
+            try (Builder builder = accord.primitives.KeyDeps.builder();)
             {
-                builder.nextKey(key);
-                List<TxnId> ids = new ArrayList<>(deps.canonical.get(key));
-                Collections.shuffle(ids, random);
-                ids.forEach(builder::add);
-            }
+                for (Key key : deps.canonical.keySet())
+                {
+                    builder.nextKey(key);
+                    List<TxnId> ids = new ArrayList<>(deps.canonical.get(key));
+                    Collections.shuffle(ids, random);
+                    ids.forEach(builder::add);
+                }
 
-            Assertions.assertEquals(deps.test, builder.build());
+                Assertions.assertEquals(deps.test, builder.build());
+            }
         });
     }
 
     static class Deps
     {
-        final Map<Key, Set<TxnId>> canonical;
-        final accord.primitives.Deps test;
+        final Map<Key, NavigableSet<TxnId>> canonical;
+        final accord.primitives.KeyDeps test;
 
-        Deps(Map<Key, Set<TxnId>> canonical, accord.primitives.Deps test)
+        Deps(Map<Key, NavigableSet<TxnId>> canonical, accord.primitives.KeyDeps test)
         {
             this.canonical = canonical;
             this.test = test;
@@ -347,7 +342,7 @@ public class DepsTest
                 txnIds = new ArrayList<>(tmp);
             }
 
-            Map<Key, Set<TxnId>> canonical = new TreeMap<>();
+            TreeMap<Key, NavigableSet<TxnId>> canonical = new TreeMap<>();
             for (int i = 0 ; i < totalCount ; ++i)
             {
                 Key key = populateKeys.get(random.nextInt(uniqueKeys));
@@ -355,22 +350,24 @@ public class DepsTest
                 canonical.computeIfAbsent(key, ignore -> new TreeSet<>()).add(txnId);
             }
 
-            try (OrderedBuilder builder = accord.primitives.Deps.orderedBuilder(false))
+            boolean inOrderKeys = random.nextBoolean();
+            boolean inOrderValues = random.nextBoolean();
+            try (Builder builder = accord.primitives.KeyDeps.builder())
             {
-                canonical.forEach((key, ids) -> {
+                (inOrderKeys ? canonical : canonical.descendingMap()).forEach((key, ids) -> {
                     builder.nextKey(key);
-                    ids.forEach(builder::add);
+                    (inOrderValues ? ids : ids.descendingSet()).forEach(builder::add);
                 });
 
-                accord.primitives.Deps test = builder.build();
+                accord.primitives.KeyDeps test = builder.build();
                 return new Deps(canonical, test);
             }
         }
 
         Deps select(Ranges ranges)
         {
-            Map<Key, Set<TxnId>> canonical = new TreeMap<>();
-            for (Map.Entry<Key, Set<TxnId>> e : this.canonical.entrySet())
+            Map<Key, NavigableSet<TxnId>> canonical = new TreeMap<>();
+            for (Map.Entry<Key, NavigableSet<TxnId>> e : this.canonical.entrySet())
             {
                 if (ranges.contains(e.getKey()))
                     canonical.put(e.getKey(), e.getValue());
@@ -381,10 +378,10 @@ public class DepsTest
 
         Deps with(Deps that)
         {
-            Map<Key, Set<TxnId>> canonical = new TreeMap<>();
-            for (Map.Entry<Key, Set<TxnId>> e : this.canonical.entrySet())
+            Map<Key, NavigableSet<TxnId>> canonical = new TreeMap<>();
+            for (Map.Entry<Key, NavigableSet<TxnId>> e : this.canonical.entrySet())
                 canonical.computeIfAbsent(e.getKey(), ignore -> new TreeSet<>()).addAll(e.getValue());
-            for (Map.Entry<Key, Set<TxnId>> e : that.canonical.entrySet())
+            for (Map.Entry<Key, NavigableSet<TxnId>> e : that.canonical.entrySet())
                 canonical.computeIfAbsent(e.getKey(), ignore -> new TreeSet<>()).addAll(e.getValue());
 
             return new Deps(canonical, test.with(that.test));
@@ -393,7 +390,7 @@ public class DepsTest
         void testSimpleEquality()
         {
             Assertions.assertArrayEquals(canonical.keySet().toArray(new Key[0]), ((Keys)test.keys()).stream().toArray(Key[]::new));
-            for (Map.Entry<Key, Set<TxnId>> e : canonical.entrySet())
+            for (Map.Entry<Key, NavigableSet<TxnId>> e : canonical.entrySet())
             {
                 List<TxnId> canonical = new ArrayList<>(e.getValue());
                 List<TxnId> test = new ArrayList<>();
@@ -412,7 +409,7 @@ public class DepsTest
 
             StringBuilder builder = new StringBuilder();
             builder.append("{");
-            for (Map.Entry<Key, Set<TxnId>> e : canonical.entrySet())
+            for (Map.Entry<Key, NavigableSet<TxnId>> e : canonical.entrySet())
             {
                 if (builder.length() > 1)
                     builder.append(", ");
@@ -421,13 +418,13 @@ public class DepsTest
                 builder.append(e.getValue());
             }
             builder.append("}");
-            Assertions.assertEquals(builder.toString(), test.toSimpleString());
+            Assertions.assertEquals(builder.toString(), test.toString());
         }
 
         TreeMap<TxnId, List<Key>> invertCanonical()
         {
             TreeMap<TxnId, List<Key>> result = new TreeMap<>();
-            for (Map.Entry<Key, Set<TxnId>> e : canonical.entrySet())
+            for (Map.Entry<Key, NavigableSet<TxnId>> e : canonical.entrySet())
             {
                 e.getValue().forEach(txnId -> result.computeIfAbsent(txnId, ignore -> new ArrayList<>())
                                                     .add(e.getKey()));
@@ -438,14 +435,14 @@ public class DepsTest
 
         static Deps merge(List<Deps> deps)
         {
-            Map<Key, Set<TxnId>> canonical = new TreeMap<>();
+            Map<Key, NavigableSet<TxnId>> canonical = new TreeMap<>();
             for (Deps that : deps)
             {
-                for (Map.Entry<Key, Set<TxnId>> e : that.canonical.entrySet())
+                for (Map.Entry<Key, NavigableSet<TxnId>> e : that.canonical.entrySet())
                     canonical.computeIfAbsent(e.getKey(), ignore -> new TreeSet<>()).addAll(e.getValue());
             }
 
-            return new Deps(canonical, accord.primitives.Deps.merge(deps, d -> d.test));
+            return new Deps(canonical, accord.primitives.KeyDeps.merge(deps, d -> d.test, Function.identity()));
         }
     }
 
@@ -474,7 +471,7 @@ public class DepsTest
         Random random = random(seed);
         int totalCount = 1 + random.nextInt(totalCountRange - 1);
         testOneDeps(random,
-                    DepsTest.Deps.generate(random, uniqueTxnIds, epochRange, hlcRange, 0, nodeRange, uniqueKeys, emptyKeys, keyRange, totalCount),
+                    KeyDepsTest.Deps.generate(random, uniqueTxnIds, epochRange, hlcRange, 0, nodeRange, uniqueKeys, emptyKeys, keyRange, totalCount),
                     keyRange);
     }
 
@@ -483,13 +480,13 @@ public class DepsTest
     {
         return () -> {
             if (random.nextInt(100) == 0)
-                return new Deps(new TreeMap<>(), accord.primitives.Deps.NONE);
+                return new Deps(new TreeMap<>(), accord.primitives.KeyDeps.NONE);
 
             int uniqueTxnIds = 1 + random.nextInt(uniqueTxnIdsRange - 1);
             int uniqueKeys = 1 + random.nextInt(uniqueKeysRange - 1);
             int emptyKeys = 1 + random.nextInt(emptyKeysRange - 1);
             int totalCount = random.nextInt(Math.min(totalCountRange, uniqueKeys * uniqueTxnIds));
-            return DepsTest.Deps.generate(random, uniqueTxnIds,
+            return KeyDepsTest.Deps.generate(random, uniqueTxnIds,
                                                   epochRange, hlcRange, flagRange, nodeRange,
                                                   uniqueKeys, emptyKeys, keyRange, totalCount);
         };
@@ -500,25 +497,25 @@ public class DepsTest
         deps.testSimpleEquality();
         {
             Deps nestedSelect = null;
-            // generate some random KeyRanges, and slice using them
+            // generate some random Ranges, and slice using them
             for (int i = 0, count = 1 + random.nextInt(4); i < count ; ++i)
             {
                 Ranges ranges = randomKeyRanges(random, 1 + random.nextInt(5), keyRange);
 
                 {   // test forEach(key, txnId)
-                    List<Entry> canonical = new ArrayList<>();
+                    List<Entry<Key, TxnId>> canonical = new ArrayList<>();
                     for (Key key : deps.canonical.keySet())
                     {
                         if (ranges.contains(key))
-                            deps.canonical.get(key).forEach(txnId -> canonical.add(new Entry(key, txnId)));
+                            deps.canonical.get(key).forEach(txnId -> canonical.add(new Entry<>(key, txnId)));
                     }
-                    deps.test.forEachOn(ranges, ignore -> true, new BiConsumer<Key, TxnId>()
+                    deps.test.forEach(ranges, new BiConsumer<>()
                     {
                         int i = 0;
                         @Override
                         public void accept(Key key, TxnId txnId)
                         {
-                            Entry entry = canonical.get(i);
+                            Entry<Key, TxnId> entry = canonical.get(i);
                             Assertions.assertEquals(entry.getKey(), key);
                             Assertions.assertEquals(entry.getValue(), txnId);
                             ++i;
@@ -534,7 +531,7 @@ public class DepsTest
                         if (ranges.contains(key))
                             canonical.addAll(deps.canonical.get(key));
                     }
-                    deps.test.forEachOn(ranges, test::add);
+                    deps.test.forEachUniqueTxnId(ranges, test::add);
                     test.sort(Timestamp::compareTo);
                     Assertions.assertEquals(new ArrayList<>(canonical), test);
                 }
diff --git a/accord-core/src/test/java/accord/primitives/RangeDepsTest.java b/accord-core/src/test/java/accord/primitives/RangeDepsTest.java
new file mode 100644
index 0000000..ed62bbf
--- /dev/null
+++ b/accord-core/src/test/java/accord/primitives/RangeDepsTest.java
@@ -0,0 +1,229 @@
+package accord.primitives;
+
+import accord.impl.IntKey;
+import accord.local.Node;
+import accord.primitives.Routable.Domain;
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+
+import java.util.*;
+
+import static accord.primitives.Txn.Kind.Write;
+
+public class RangeDepsTest
+{
+    static class GenerateRanges
+    {
+        final int rangeDomain;
+        final float minRangesDomain, maxRangesDomain, minRangesSpan, maxRangesSpan;
+
+        GenerateRanges(int rangeDomain, float minRangesDomain, float maxRangesDomain, float minRangesSpan, float maxRangesSpan)
+        {
+            this.rangeDomain = rangeDomain;
+            this.minRangesDomain = minRangesDomain;
+            this.maxRangesDomain = maxRangesDomain;
+            this.minRangesSpan = minRangesSpan;
+            this.maxRangesSpan = maxRangesSpan;
+        }
+
+        private Range[] generateRanges(Random random, int rangeCount)
+        {
+            Range[] ranges = new Range[rangeCount];
+            int txnDomain = Math.max(ranges.length, (int) (((random.nextFloat() * (maxRangesDomain - minRangesDomain)) + minRangesDomain) * rangeDomain));
+            int txnSpan = Math.max(txnDomain, (int) (((random.nextFloat() * (maxRangesSpan - minRangesSpan)) + minRangesSpan) * rangeDomain));
+            int gapSpan = txnSpan - txnDomain;
+            int start = rangeDomain == txnSpan ? 0 : random.nextInt(rangeDomain - txnSpan);
+            int end = start + txnSpan;
+            int[] gaps = new int[ranges.length];
+            int[] gapSpans = new int[ranges.length];
+            for (int i = 0 ; i < ranges.length ; ++i)
+            {
+                gaps[i] = start + random.nextInt(end - start);
+                gapSpans[i] = i == ranges.length - 1 || gapSpan <= 1 ? gapSpan : 1 + random.nextInt(Math.max(1, 2 * gapSpan/(ranges.length - i)));
+            }
+            Arrays.sort(gaps);
+            for (int i = 0 ; i < ranges.length ; ++i)
+            {
+                end = Math.max(start + 1, gaps[i]);
+                ranges[i] = r(start, end);
+                start = end + gapSpans[i];
+            }
+            return ranges;
+        }
+    }
+
+    static class Validate
+    {
+        final GenerateRanges generate;
+        final Map<TxnId, Ranges> canonical;
+        final RangeDeps test;
+
+        Validate(GenerateRanges generate, Map<TxnId, Ranges> canonical, RangeDeps test)
+        {
+            this.generate = generate;
+            this.canonical = canonical;
+            this.test = test;
+        }
+
+        Set<TxnId> canonicalOverlaps(Range range)
+        {
+            Set<TxnId> set = new TreeSet<>();
+            for (Map.Entry<TxnId, Ranges> e : canonical.entrySet())
+            {
+                if (e.getValue().intersects(range))
+                    set.add(e.getKey());
+            }
+            return set;
+        }
+
+        Set<TxnId> testOverlaps(Range range)
+        {
+            Set<TxnId> set = new TreeSet<>();
+            test.forEachUniqueTxnId(range, set::add);
+            return set;
+        }
+
+        void validate(Random random)
+        {
+            Assertions.assertEquals(canonical.size(), test.txnIdCount());
+            Assertions.assertArrayEquals(canonical.keySet().stream().toArray(TxnId[]::new), test.txnIds);
+            for (int i = 0 ; i < test.rangeCount() ; ++i)
+            {
+                Assertions.assertEquals(canonicalOverlaps(test.range(i)), testOverlaps(test.range(i)));
+            }
+            for (int i = 0 ; i < test.rangeCount() ; ++i)
+            {
+                Range range = generate.generateRanges(random, 1)[0];
+                Assertions.assertEquals(canonicalOverlaps(range), testOverlaps(range));
+            }
+        }
+    }
+
+    private static final boolean EXHAUSTIVE = false;
+
+    // TODO (expected, testing): generate ranges of different sizes at different ratios
+    private static Validate generate(Random random, GenerateRanges generate, int txnIdCount, int rangeCount)
+    {
+        Map<TxnId, Ranges> map = new TreeMap<>();
+        for (int txnId = 0; txnId < txnIdCount ; ++txnId)
+        {
+            int thisRangeCount = txnIdCount == 1 ? rangeCount : 1 + random.nextInt((2 * rangeCount / txnIdCount) - 1);
+            Range[] ranges = generate.generateRanges(random, thisRangeCount);
+            map.put(id(txnId), Ranges.of(ranges));
+        }
+        return new Validate(generate, map, RangeDeps.of(map));
+    }
+
+    private static Validate generateIdenticalTxns(Random random, GenerateRanges generate, int txnIdCount, int rangeCount)
+    {
+        Map<TxnId, Ranges> map = new TreeMap<>();
+        Range[] ranges = generate.generateRanges(random, rangeCount / txnIdCount);
+        for (int txnId = 0; txnId < txnIdCount ; ++txnId)
+            map.put(id(txnId), Ranges.of(ranges));
+        return new Validate(generate, map, RangeDeps.of(map));
+    }
+
+    private static Validate generateNemesisRanges(int width, int nemesisTxnIdCount, int rangeCount, int nonNemesisEntryPerNemesisEntry)
+    {
+        Map<Integer, List<Range>> build = new TreeMap<>();
+        int nonNemesisTxnIdCount = nemesisTxnIdCount * nonNemesisEntryPerNemesisEntry;
+        rangeCount /= (1 + nonNemesisEntryPerNemesisEntry);
+        int rangeDomain = 0;
+        for (int i = 0 ; i < rangeCount ; ++i)
+        {
+            build.computeIfAbsent(i % nemesisTxnIdCount, ignore -> new ArrayList<>()).add(r(i, i + width));
+            for (int j = 0 ; j < nonNemesisEntryPerNemesisEntry ; ++j)
+                build.computeIfAbsent(nemesisTxnIdCount + (i % nonNemesisTxnIdCount), ignore -> new ArrayList<>()).add(r(i, i + 1));
+            rangeDomain = i + width;
+        }
+        Map<TxnId, Ranges> result = new TreeMap<>();
+        for (int txnId = 0; txnId < nemesisTxnIdCount + nonNemesisTxnIdCount ; ++txnId)
+            result.put(id(txnId), Ranges.of(build.get(txnId).toArray(new Range[0])));
+        return new Validate(new GenerateRanges(rangeDomain, 0f, 1f, 0f, 1f), result, RangeDeps.of(result));
+    }
+
+
+    // TODO (now): broaden patterns of random contents, sizes of collection etc.
+    @Test
+    public void testRandom()
+    {
+        Random random = new Random();
+//        long[] seeds = new long[]{-6268194734307361517L, -1531261279965735959L};
+//        Validate[] validates = new Validate[seeds.length];
+        for (int i = 0 ; i < 1000 ; ++i)
+        {
+            long seed = random.nextLong();
+//            long seed = -5637243003494330136L;
+            System.out.println("Seed: " + seed);
+            random.setSeed(seed);
+            generate(random, new GenerateRanges(1000, 0.01f, 0.3f, 0.1f, 1f), 100, 1000)
+                    .validate(random);
+        }
+    }
+
+    @Test
+    public void testIdenticalTransactions()
+    {
+        Random random = new Random();
+        for (int copies = 1 ; copies < 500 ; ++copies)
+        {
+            long seed = random.nextLong();
+//            long seed = -4951029115911714505L;
+            System.out.println("Seed: " + seed + ", copies: " + copies);
+            random.setSeed(seed);
+            generateIdenticalTxns(random, new GenerateRanges(1000, 0.01f, 0.3f, 0.1f, 1f), copies, 1000)
+                    .validate(random);
+        }
+    }
+
+    @Test
+    public void testNemesisRanges()
+    {
+        testNemesisRanges(0);
+    }
+
+    @Test
+    public void testHalfNemesisRanges()
+    {
+        testNemesisRanges(1);
+    }
+
+    private static void testNemesisRanges(int nonNemesisEntryPerNemesisEntry)
+    {
+        Random random = new Random();
+        long seed = random.nextLong();
+        System.out.println("Seed: " + seed);
+        random.setSeed(seed);
+
+        if (EXHAUSTIVE)
+        {
+            for (int width = 1 ; width < 512 ; ++width)
+            {
+                for (int txnIdCount = 1; txnIdCount < 100 ; txnIdCount *= 2)
+                {
+                    // TODO (now): verify that we write only a small number of checkpoints
+                    generateNemesisRanges(width, txnIdCount, 1000, nonNemesisEntryPerNemesisEntry)
+                            .validate(random);
+                }
+            }
+        }
+        else
+        {
+            for (int i = 0 ; i < 1000 ; ++i)
+            {
+                generateNemesisRanges(1 + random.nextInt(511), 1 + random.nextInt(99), 1000, nonNemesisEntryPerNemesisEntry)
+                        .validate(random);
+            }
+        }
+    }
+
+    private static TxnId id(int i)
+    {
+        return new TxnId(1, i, Write, Domain.Key, new Node.Id(1));
+    }
+
+    private static Range r(int i, int j)
+    {
+        return new IntKey.Range(new IntKey.Routing(i), new IntKey.Routing(j));
+    }
+}
diff --git a/accord-maelstrom/src/main/java/accord/maelstrom/Json.java b/accord-maelstrom/src/main/java/accord/maelstrom/Json.java
index 98a8345..ba08474 100644
--- a/accord-maelstrom/src/main/java/accord/maelstrom/Json.java
+++ b/accord-maelstrom/src/main/java/accord/maelstrom/Json.java
@@ -21,8 +21,10 @@ package accord.maelstrom;
 import java.io.IOException;
 import java.util.*;
 
+import accord.api.RoutingKey;
 import accord.local.Node;
 import accord.api.Result;
+import accord.primitives.*;
 import com.google.gson.Gson;
 import com.google.gson.GsonBuilder;
 import com.google.gson.TypeAdapter;
@@ -31,13 +33,6 @@ import com.google.gson.stream.JsonToken;
 import com.google.gson.stream.JsonWriter;
 import accord.local.Node.Id;
 import accord.api.Key;
-import accord.primitives.Deps;
-import accord.primitives.Txn;
-import accord.primitives.TxnId;
-import accord.primitives.Writes;
-import accord.primitives.Ballot;
-import accord.primitives.Keys;
-import accord.primitives.Timestamp;
 import accord.messages.ReadData.ReadOk;
 
 public class Json
@@ -320,7 +315,7 @@ public class Json
         public void write(JsonWriter out, Deps value) throws IOException
         {
             out.beginArray();
-            for (Map.Entry<Key, TxnId> e : value)
+            for (Map.Entry<Key, TxnId> e : value.keyDeps)
             {
                 out.beginArray();
                 ((MaelstromKey)e.getKey()).datum.write(out);
@@ -328,37 +323,53 @@ public class Json
                 out.endArray();
             }
             out.endArray();
+            out.beginArray();
+            for (Map.Entry<Range, TxnId> e : value.rangeDeps)
+            {
+                out.beginArray();
+                ((MaelstromKey)e.getKey().start()).datum.write(out);
+                ((MaelstromKey)e.getKey().end()).datum.write(out);
+                GSON.toJson(e.getValue(), TxnId.class, out);
+                out.endArray();
+            }
+            out.endArray();
         }
 
         @Override
         public Deps read(JsonReader in) throws IOException
         {
-            in.beginArray();
-            if (!in.hasNext())
+            KeyDeps keyDeps;
+            try (KeyDeps.Builder builder = KeyDeps.builder())
             {
+                in.beginArray();
+                while (in.hasNext())
+                {
+                    in.beginArray();
+                    Key key = MaelstromKey.readKey(in);
+                    TxnId txnId = GSON.fromJson(in, TxnId.class);
+                    builder.add(key, txnId);
+                    in.endArray();
+                }
                 in.endArray();
-                return Deps.NONE;
+                keyDeps = builder.build();
             }
-
-            TreeMap<Key, List<TxnId>> byKey = new TreeMap<>();
-            while (in.hasNext())
+            RangeDeps rangeDeps;
+            try (RangeDeps.Builder builder = RangeDeps.builder())
             {
                 in.beginArray();
-                Key key = MaelstromKey.readKey(in);
-                TxnId txnId = GSON.fromJson(in, TxnId.class);
-                byKey.computeIfAbsent(key, ignore -> new ArrayList<>()).add(txnId);
+                while (in.hasNext())
+                {
+                    in.beginArray();
+                    RoutingKey start = MaelstromKey.readRouting(in);
+                    RoutingKey end = MaelstromKey.readRouting(in);
+                    TxnId txnId = GSON.fromJson(in, TxnId.class);
+                    builder.add(new MaelstromKey.Range(start, end), txnId);
+                    in.endArray();
+                }
                 in.endArray();
+                rangeDeps = builder.build();
             }
-            in.endArray();
-
-            try (Deps.OrderedBuilder builder = Deps.orderedBuilder(true))
-            {
-                byKey.forEach((key, txnIds) -> {
-                    builder.nextKey(key);
-                    txnIds.forEach(builder::add);
-                });
-                return builder.build();
-            }
+            return new Deps(keyDeps, rangeDeps);
         }
     };
 


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@cassandra.apache.org
For additional commands, e-mail: commits-help@cassandra.apache.org