Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement apply() atomicity on MVCC level #2012

tgrabiec opened this Issue Jan 13, 2017 · 0 comments


None yet
2 participants
Copy link

tgrabiec commented Jan 13, 2017

In order to provide apply() atomicity, memtable::apply() needs to have strong exception guarantees. Currently it's implemented on mutation_partition::apply() level by using reversible merging (see reversibly_mergeable.hh), which basically works by swapping atoms between source and destination. If merging fails in the middle, the atoms are swapped back.

We could implement this more efficiently now that we have MVCC, by only requiring mutation_partition::apply() to have weak exception guarantees, such that in case of failure the source and destination still commute to the same result (x' + y' = x + y). Such guarantees are simpler and more efficient to provide than reversible merging (no extra allocations, we just std::move() atoms).

We first allocate a new version entry. Then std::move the source mutation into it. If that succeeds, the mutation is logically already applied. Then we merge that version with the previous version. Even if that fails, logical state is unaffected because the two versions still commute to the same value due to exception guarantees.

The allocation of temporary version object could be avoided in the success path by some form of pooling.

@tzach tzach added this to the Yellowfin milestone Feb 8, 2017

@avikivity avikivity closed this in 49c0705 Nov 28, 2017

avikivity added a commit that referenced this issue Nov 28, 2017

Merge "Drop reversible apply() from mutation_partition" from Tomasz
"This simplifies implementation of mutation_partition merging by relaxing
exception guarantees it needs to provide. This allows reverters to be dropped.

Direct motivation for this is to make it easier to implement new semantics
for merging of clustering range continuity.

Implementation details:

We only need strong exception guarantees when applying to the memtable, which is
using MVCC. Instead of calling apply() with strong exception guarantees on the latest
version, we will move the incoming mutation to a new partition_version and then
use monotonic apply() to merge them. If that merging fails, we attach the version with
the remainder, which cannot fail. This way apply() always succeeds if the allocation
of partition_version object succeeds.

Results of `perf_simple_query_g -c1 -m1G --write` (high overwrite rate):


 101011.13 tps
 102498.07 tps
 103174.68 tps
 102879.55 tps
 103524.48 tps
 102794.56 tps
 103565.11 tps
 103018.51 tps
 103494.37 tps
 102375.81 tps
 103361.65 tps


 101785.37 tps
 101366.19 tps
 103532.26 tps
 100834.83 tps
 100552.11 tps
 100891.31 tps
 101752.06 tps
 101532.00 tps
 100612.06 tps
 102750.62 tps
 100889.16 tps

Fixes #2012."

* tag 'tgrabiec/drop-reversible-apply-v1' of
  mutation_partition: Drop apply_reversibly()
  mutation_partition: Relax exception guarantees of apply()
  mutation_partition: Introduce apply_weak()
  tests: mvcc: Add test for atomicity of partition_entry::apply()
  tests: Move failure_injecting_allocation_strategy to a header
  tests: mutation_partition: Test exception guarantees of apply_monotonically()
  mvcc: Use apply_monotonically() where sufficient
  mvcc: partition_version: Use apply_monotonically() to provide atomicity
  mvcc: Extract partition_entry::add_version()
  mutation_partition: Introduce apply_monotonically()
  mutation_partition: Introduce row::consume_with()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.