apple / apple/foundationdb

Reduce conflict rates via reordering transactions within/across batches.

Open
#2,056 1 comment 2 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
16.7k
Forks
1.6k
Avg merge
1d 20h
Merged PRs (30d)
126

Description

To record some of the conversation that @xumengpanda and I had at VLDB about [Improving Optimistic Concurrency Control Through Transaction Batching and Operation Reordering](http://www.vldb.org/pvldb/vol12/p169-ding.pdf) and the overall topic of transaction reordering...

FDB already batches transactions and is optimistic, so we already fall into the space where these techniques are applicable. The described algorithms could be implemented in the resolver, and the proxy<->resolver protocol changed to allow the resolver to reorder transactions. However, we were concerned about the additional CPU usage on resolvers, since transaction reordering across two resolvers would probably have a higher conflict rate than no reordering on one resolver.

However, reordering transactions to maximally avoid intra-batch conflicts can be done on the proxy before even sending the transactions to the resolver. Any transactions which the proxy marks as aborted during this rearrangement don't even need to be sent to the resolver, which would actually be a direct speedup of the resolver. I'm far more comfortable with the idea of pushing the CPU cost of commits a big higher and requiring an additional proxy if that means fewer commits.

I think we also have an opportunity to reorder transactions across batches. Resolvers need to wait for each version's batch in version order, so there will be times when a resolver will have a queue of batches to process. Currently, we'd evaluate this queue of requests in order and independently. I _think_ it'd be fine for us to move transactions across version batches as long as we communicate the final, correct commit version to the client. This would definitely have to be done on the resolver and cost resolver CPU, and I'm not sure how much we'd actually gain from doing so.

Contributor guide

Open the contributing guide

Research direction

Start by reading the linked transaction-reordering paper and tracing how the proxy sends transaction batches through the proxy-resolver protocol to the resolver. Compare the current per-batch evaluation with the proposed intra- and cross-batch reordering, including conflict rates and resolver CPU cost. Done requires an agreed algorithm, any required protocol changes, and evidence that the trade-offs are worthwhile; the issue does not name files or tests.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
databases, distributed-systems
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.