The Order of Conflict-checking and Appending to the tLog

Development FoundationDB Core
#1

Hi,

Are transactions appended to the tLog in the order in which they are conflict-checked? Because otherwise, can’t the following scenario occur?

T1 {
if (x == 1)
x = 3
}

T2 {
x = 2
}

Now, suppose we conflict-check T1 first. Since no update exists for x, it is good to go and will pass conflict checking. Next, we conflict-check T2, and since its read-set is empty, there is nothing to check, so it will pass as well. Now, if we append and apply T2 before T1 then we will end up in a state where x = 3 which is not equivalent to any serial execution.

History: R1(x) W2(x) R1(x) thus we have T1 —> T2 —> T1 (cycle)

Since proxies conflict-check independently and in parallel, isn’t it possible they append to tLog out of order of the conflict-checking?

So

  • Does fbd guarantee that the order of conflict-checking is preserved on the tlog? if yes how? given we have multiple proxies.

  • Does conflict-checking only check the read-set? or it also checks the write-set as well? because if we keep track of what version is overwritten by a transaction, in the scenario above T2 will be aborted.

#2

These transactions will have a consistent order between conflict resolution and writing to the log. This is done by assigning each commit batch a unique version from the master while on the proxy and then processing all batches in order on the resolvers and transaction logs.

A transaction cannot be failed with a conflict because of a key it wrote, and only the read set is checked. A write only transaction like T2, therefore, won’t fail during conflict checking.

#3

Thanks @ajbeamon for the explanation.
Ok, so you confirm that the order that we conflict-check and the order we append to tLog are the same.

To better understand how this order is enforced, I have a follow-up question:
Each transaction (transaction batch) get the commit timestamp from master. How do the resolver and tlog make sure they process and append transactions in order? Do they expect to see requests with consecutive numbers 1,2,3…and if something is missing they wait for it? like if proxies submits request 1, 3… the resolver don’t conflict check 3 and wait for 2?

For resolver, I can see it can wait, but for tLog not every transaction go to tlog, so tlog cannot expect consecutive numbers.

Plus, if we want to wait for all numbers, what happens when a proxy is slow? the whole system waits for it?

#4

Each transaction batch knows the version of the prior batch from the master as well. On the resolver and logs, they won’t process a batch until they’ve seen the prior batch version come through.

Commits with no data destined for a log still need to send confirmation of an empty commit, so this check is still possible.

That’s right, if a batch gets held up somewhere (e.g. on a proxy), all subsequent commits will stall.

1 Like