Correctness rules

Let’s start with an example that models the above update() call:

• Operation w1 targets shard B and has no dependencies
• Operation w2 targets shard A and has no dependencies
• Operation w3 targets shard A and depends on w1 and w2.

We can imagine building up a graph of these operations while trying to group operations on the same shard. We’ll start by placing w1 in the graph in a new group for shard B.

Shard │
      │
    A │
      │
      │
      │   ┌────┐
    B │   │ w1 │
      │   └────┘

Next, we place w2, which targets shard A, so we create a new group for that shard:

Shard │
      │   ┌────┐
    A │   │ w2 │
      │   └────┘
      │
      │   ┌────┐
    B │   │ w1 │
      │   └────┘

Finally, we need to add w3, which depends on the other two operations. It must therefore be executed either after or at the same time as these operations to achieve safety. It targets shard A, so our question is: can we put it in the existing group containing w1, or must we create a new group? In this case, w3 depends directly on w1 and it is safe to place it in the same group, meaning w1 and w3 will be applied in the same write request.

We add w3 to the graph in the group with w1 and make dependency links between the operations:

Shard │
      │   ┌────────────┐
    A │   │ w2 ---- w3 │
      │   └────────/───┘
      │           /
      │      ┌───/┐
    B │      │ w1 │
      │      └────┘

The finished graph has a dependency between the [w2, w3] group and the [w1] group, forcing the writes to be executed in that order:

Shard │
      │                         ┌─────────────────┐
    A │                         │ WRITE ░░░░░░░░░░│
      │                         ├─────────────────┘
      │                         └─ w2, w3
      │   ┌─────────────────┐
    B │   │ WRITE ░░░░░░░░░░│
      │   ├─────────────────┘
          └─ w1

Now imagine that we add a fourth operation w4 that targets B and depends on w3. Can we put it in the same group as w1? No, we cannot: this would mean executing w1 and w4 in one write, and then w2 and w3 in another. w3 happens after w4, or possibly not at all if the second write fails, so we’ve violated the dependency order of w4 on w3. Therefore w4 needs to be put in its own group, separate from w1.

Shard │
      │   ┌────────────┐
    A │   │ w2 ---- w3 │
      │   └────────/──\┘
      │           /    \
      │      ┌───/┐    ┌\───┐
    B │      │ w1 │    │ w4 │
      │      └────┘    └────┘

That gives us the following write sequence:

Shard │
      │                       ┌─────────────────┐
    A │                       │ WRITE ░░░░░░░░░░│
      │                       ├─────────────────┘
      │                       └─ w2, w3
      │   ┌─────────────────┐                     ┌─────────────────┐
    B │   │ WRITE ░░░░░░░░░░│                     │ WRITE ░░░░░░░░░░│
      │   ├─────────────────┘                     ├─────────────────┘
          └─ w1                                   └─ w4

This small example has given us some useful constraints for building graphs:

• If no write groups exist for a shard, a new group must be created.

• If operations P and Q target the same shard, and P depends directly on Q, then P may be placed in the same group as Q, but must not be placed in any earlier group.

• If an operation P depends indirectly on another operation Q, that is it depends on Q via an operation on another shard, then P must be placed in a later group than Q.

• Otherwise, operations may be assigned to any group we choose without breaking causality, assuming we record dependencies to force the groups to execute in the correct order.