Prioritising the longest chains
Let’s consider another example where we’d want to constrain merging based on group depth. Imagine we have the following graph:
Shard │
│ ┌───────────┐
A │ │ w2 w3 │
│ └/─────────\┘
│ / \
│ ┌───/┐ ┌\───┐
B │ │ w1 │ │ w4 │
│ └────┘ └───\┘
│ \
│ ┌\───┐
C │ │ w5 │
│ └────┘
Now say we have operation w6 targeting C, and it has no dependencies. We decide not to merge it with the [w5] group, since that has depth 3, and we instead start a new depth-0 group for it.
Shard │
│ ┌───────────┐
A │ │ w2 w3 │
│ └/─────────\┘
│ / \
│ ┌───/┐ ┌\───┐
B │ │ w1 │ │ w4 │
│ └────┘ └───\┘
│ \
│ ┌────┐ ┌\───┐
C │ │ w6 │ │ w5 │
│ └────┘ └────┘
Again, if no further operations are added to this graph, we’d consider merging the [w6] and [w5] groups to reduce the number of groups without increasing depth. But imagine instead that we now add w7, which targets B and depends on w6. Which group do we add w7 to?
w7 does not depend in any way on w1 or w4, so we can add it to either of their groups. If we pick the earlier group, the [w1] one, then link that group to [w6], we end up increasing the depth of the graph to 5.
Shard │
│ ┌───────────┐
A │ │ w2 w3 │
│ └/─────────\┘
│ / \
│ ┌───────────/┐ ┌\───┐
B │ │ w7 w1 │ │ w4 │
│ └/───────────┘ └───\┘
│ / \
│ ┌───/┐ ┌\───┐
C │ │ w6 │ │ w5 │
│ └────┘ └────┘
However, if we placed w7 in the [w4] group, then linking this group to [w6] does not increase the graph’s depth and it remains at 4.
Shard │
│ ┌───────────┐
A │ │ w2 w3 │
│ └/─────────\┘
│ / \
│ ┌───/┐ ┌────────\───┐
B │ │ w1 │ │ w7 w4 │
│ └────┘ └/──────────\┘
│ / \
│ ┌───/┐ ┌\───┐
C │ │ w6 │ │ w5 │
│ └────┘ └────┘
Therefore when merging a non-leaf operation, we should pick a group whose depth is greater than that of any of the groups the operation depends on. Remember that it’s the depth of groups that matters here for the shape of the graph, not the depth of operations within their own local dependency relationships. This graph produces the following partly parallelised write sequence, and has N = 5 and D = 4.
Shard │
│ ┌─────────────┐
A │ │ WRITE ░░░░░░│
│ ├─────────────┘
│ └─ w2, w3
│ ┌─────────────┐ ┌─────────────┐
B │ │ WRITE ░░░░░░│ │ WRITE ░░░░░░│
│ ├─────────────┘ ├─────────────┘
│ └─ w1 └─ w7, w4
│ ┌─────────────┐ ┌─────────────┐
C │ │ WRITE ░░░░░░│ │ WRITE ░░░░░░│
│ ├─────────────┘ ├─────────────┘
└─ w6 └─ w5
This is a shorter graph depth than if we’d decided to merge w6 with w5, thus pushing w7 into its own group, or than if we’d merged w7 with w1 as described above. Both these other graphs would be fully sequential.
The results we end up with are sensitive to the order in which operations are added, and the merging decisions we make as a result. Imagine that in this example we’d instead ended up merging w1 and w4, rather than w2 and w3, which is perfectly allowed by their dependency relationships.
Shard │
│ ┌────┐ ┌────┐
A │ │ w3 │ │ w2 │
│ └───\┘ └/───┘
│ \ /
│ ┌\─────────/┐
B │ │ w4 w1 │
│ └───────────┘
│
│
C │
│
With the information up to w4, there’s no reason to prefer this over the previous plan, they’re structurally equivalent. The difference only becomes apparent when we add more operations.
We then add w5, creating a group of depth 2 that depends on the depth-1 [w4, w1] group, and we add w6 in its own depth-0 group rather than adding it to the depth-2 [w5] group.
Shard │
│ ┌────┐ ┌────┐
A │ │ w3 │ │ w2 │
│ └───\┘ └/───┘
│ \ /
│ ┌\─────────/┐
B │ │ w4 w1 │
│ └───\───────┘
│ \
│ ┌────┐ ┌\───┐
C │ │ w6 │ │ w5 │
│ └────┘ └────┘
Then we add w7, which we can merge into the [w4, w1] group, linking that group to [w6] creating a graph with N = 5 and D = 3.
Shard │
│ ┌────┐ ┌────┐
A │ │ w3 │ │ w2 │
│ └───\┘ └/───┘
│ \ /
│ ┌───────\────────/┐
B │ │ w7 w4 w1 │
│ └/─────────\──────┘
│ / \
│ ┌───/┐ ┌\───┐
C │ │ w6 │ │ w5 │
│ └────┘ └────┘
This graph has N = 5 like the ones before it, but now performs more of the writes in parallel. The difference isn’t big enough to be worth trying every possible grouping of operations, it’s more important to have an algorithm that can make some reasonable optimisations that runs in linear time relative to the number of operations. Sometimes we’ll miss a slightly more optimal solution, but that’s preferable to making the optimiser much more complicated or have super-linear performance scaling.
Shard │
│ ┌───────────────┐ ┌───────────────┐
A │ │ WRITE ░░░░░░░░│ │ WRITE ░░░░░░░░│
│ ├───────────────┘ ├───────────────┘
│ └─ w3 └─ w2
│ ┌───────────────┐
B │ │ WRITE ░░░░░░░░│
│ ├───────────────┘
│ └─ w1, w4, w7
│ ┌───────────────┐ ┌───────────────┐
C │ │ WRITE ░░░░░░░░│ │ WRITE ░░░░░░░░│
│ ├───────────────┘ ├───────────────┘
└─ w6 └─ w5
Is there a method we could use to convert the D = 4 solution for this set of operations into the D = 3 graph? Consider the graph shape we ended up with for D = 4:
Shard │
│ ┌───────────┐
A │ │ w2 w3 │
│ └/─────────\┘
│ / \
│ ┌───/┐ ┌────────\───┐
B │ │ w1 │ │ w7 w4 │
│ └────┘ └/──────────\┘
│ / \
│ ┌───/┐ ┌\───┐
C │ │ w6 │ │ w5 │
│ └────┘ └────┘
We can observe that the longest dependency chain between single operations is the one connecting w3, w4 and w5. Imagine that we construct a new graph containing just those operations, and split out the other operations into their own sub-graphs:
Shard │ │
│ ┌────┐ │ ┌────┐
A │ │ w3 │ │ │ w2 │
│ └───\┘ │ └/───┘
│ \ │ /
│ ┌\───┐ │ ┌───/┐ ┌────┐
B │ │ w4 │ │ │ w1 │ │ w7 │
│ └───\┘ │ └────┘ └/───┘
│ \ │ /
│ ┌\───┐ │ ┌───/┐
C │ │ w5 │ │ │ w6 │
│ └────┘ │ └────┘
We can then add the remaining operations back into the graph on the left. We start by merging w1 into the [w4] group, since w1 has no dependencies and the [w4] group has depth 1. Then we create a new group for w2 which depends on w1:
Shard │ │
│ ┌────┐ ┌────┐ │
A │ │ w3 │ │ w2 │ │
│ └───\┘ └/───┘ │
│ \ / │
│ ┌\─────────/┐ │ ┌────┐
B │ │ w4 w1 │ │ │ w7 │
│ └───\───────┘ │ └/───┘
│ \ │ /
│ ┌\───┐ │ ┌───/┐
C │ │ w5 │ │ │ w6 │
│ └────┘ │ └────┘
This leaves w6 and w7 to merge into the main graph. w6 gets a new group, rather than adding it to the [w5] group which has depth 2. w7 can be added to the [w4, w1] group and linked to the [w6] group.
Shard │
│ ┌────┐ ┌────┐
A │ │ w3 │ │ w2 │
│ └───\┘ └/───┘
│ \ /
│ ┌───────\────────/┐
B │ │ w7 w4 w1 │
│ └/─────────\──────┘
│ / \
│ ┌───/┐ ┌\───┐
C │ │ w6 │ │ w5 │
│ └────┘ └────┘
By extracting the longest dependency chain between individual operations and building the graph by starting with that chain, we reduce the total depth of the graph. Here’s another example of a graph that could be optimised in this way:
Shard │
│ ┌────┐ ┌────┐
A │ │ w1 │ │ w6 │
│ └───\┘ └/──\┘
│ \ / \
│ ┌\──────────/┐ ┌\───┐
B │ │ w2 w5 │ │ w7 │
│ └────────/───┘ └────┘
│ /
│ ┌───/┐
C │ │ w4 │
│ └/───┘
│ /
│ ┌───/┐
D │ │ w3 │
│ └────┘
The dominant chain in this graph is the set of operations [w3, w4, w5, w6, w7]. If we rebuild the graph starting with these operations, and then add w1 and w2 back in, we end up with the following graph where w1 and w2 are in their own groups because the existing groups for their shards have too high a depth.
Shard │
│ ┌────┐ ┌────┐
A │ │ w1 │ │ w6 │
│ └───\┘ └/──\┘
│ \ / \
│ ┌\───┐ ┌───/┐ ┌\───┐
B │ │ w2 │ │ w5 │ │ w7 │
│ └────┘ └/───┘ └────┘
│ /
│ ┌───/┐
C │ │ w4 │
│ └/───┘
│ /
│ ┌───/┐
D │ │ w3 │
│ └────┘
However we could then merge the [w1] and [w6] groups without increasing the total depth of the graph; the [w2] and [w7] groups both have depth 4 after this merge.
Shard │
│ ┌──────────────┐
A │ │ w6 w1 │
│ └/──\─────────\┘
│ / \ \
│ ┌───/┐ ┌\───┐ ┌\───┐
B │ │ w5 │ │ w7 │ │ w2 │
│ └/───┘ └────┘ └────┘
│ /
│ ┌───/┐
C │ │ w4 │
│ └/───┘
│ /
│ ┌───/┐
D │ │ w3 │
│ └────┘
Then we can also merge the [w7] and [w2] groups, because these operations are independent. We’re left with this graph that’s reduced N by 1 compared to the graph we started with.
Shard │
│ ┌───────────┐
A │ │ w6 w1 │
│ └/──\──────\┘
│ / \ \
│ ┌───/┐ ┌\──────\───┐
B │ │ w5 │ │ w7 w2 │
│ └/───┘ └───────────┘
│ /
│ ┌───/┐
C │ │ w4 │
│ └/───┘
│ /
│ ┌───/┐
D │ │ w3 │
│ └────┘
This type of optimisation assumes the total graph depth will be dominated by one or a few long operation chains; in EscoDB this won’t be especially useful since most writes involve chains of just two operations, but this could be useful for applying this planning algorithm to other problems. It might be useful to make this optimisation an optional task to perform once the initial graph is built, and before attempting to merge groups.