Open antiguru opened 5 months ago
We figured that the approach taken in this PR changes what we report as the next lower bound of data to be extracted. As before, seal
captures a lower frontier of all the times in the batcher, but its semantics are different. Previously, the reported frontier was accurate, i.e., there existed data at the reported frontier. Now, it's any lower bound, but there is no guarantee that it's accurate.
The reason for this is that in the past, seal
would merge all data into a single chain, which means that each (d, t)
pair appears at most once. After this change, each (d, t)
pair can occur in all chains, which means that we can only compute a lower bound frontier of the uncompacted data, but not the precise lower frontier of the compacted data. We maintain a logarithmic amount of chains.
This can become a problem when all data cancels out, and can cause an unknown amount of additional work for the rest of the system, because it needs to maintain more capabilities and might need to ask for more data more times.
We don't have an immediate solution for this problem, but there are some options:
This PR shows how to implement a merge batcher that is smart about reconsidering data that's in advance of the current frontier. It does the following things:
This should have the potential to reduce the amount of work for outstanding data from $O(n)$ where $n$ is the number of records in the merge batcher to $O(n/1024)$ by considering only the block itself, but not the data it contains.
I am sorry for the formatting noise which originates from copying this code from DD to Mz and back again :/