Value returned from Accumulator#update() is non-transactional

Bug #1167056 reported by Nathan Williams on 2013-04-09
6
This bug affects 1 person
Affects Status Importance Assigned to Milestone
Akiban Persistit
High
Peter Beaman

Bug Description

Persistit r428

Note that the return value is not documented.

Test case below fails with:
java.lang.AssertionError: newValB expected:<1> but was:<2>

@Test
public void updateRetVal() throws PersistitException {
    Transaction txn = _persistit.getTransaction();
    Exchange ex = _persistit.getExchange(UnitTestProperties.VOLUME_NAME, "accum_bug", true);
    Accumulator accum = ex.getTree().getAccumulator(Type.SUM, 3);

    txn.begin();
    assertEquals("init live", 0, accum.getLiveValue());
    assertEquals("init snap", 0, accum.getSnapshotValue(txn));
    txn.commit();
    txn.end();

    txn.begin();
    long newValA = accum.update(1, txn);
    assertEquals("newValA", 1, newValA);
    assertEquals("snap a", 1, accum.getSnapshotValue(txn));
    txn.rollback();
    txn.end();

    txn.begin();
    assertEquals("snap b", 0, accum.getSnapshotValue(txn));
    long newValB = accum.update(1, txn);
    assertEquals("newValB", 1, newValB);
    assertEquals("snap c", 1, accum.getSnapshotValue(txn));
    txn.commit();
    txn.end();

    txn.begin();
    assertEquals("snap d", 1, accum.getSnapshotValue(txn));
    txn.commit();
    txn.end();
}

Looking at the code, it appears it is actually the contents of the live value. If that is "as intended", we at least need to document it. I would vote for remove the behavior, though, so that any live value get is explicitly an opt-in.

Related branches

information type: Proprietary → Public
Peter Beaman (pbeaman) wrote :
Download full text (5.7 KiB)

Yes, it's interesting that the Javadoc in Accumulator is actually malformed. I don't know why the javadoc task doesn't kick out a warning.

So everything Nathan wrote is correct. This is an attempt to add to it.

The fundamental issue is that every generated auto-increment value needs to be unique for all time (subject to the maxValue wrapping behavior of sequences).

There are two ways to do this:

(a) Serialize all update and insert transactions that increment an auto-increment value. That way, any transaction that needs a new value is able to see all prior committed updates, and the newly incremented value it commits will be unique because no other transaction is running concurrently.

(b) Allocate a provisional ID value (for example, by incrementing an AtomicLong) and then record the transaction in such a way that this value is permanently retired and will never be generated again. As a corollary to this behavior, a transaction that allocates and ID and then rolls back will leave a "hole" in the sequence numbers. We believe this is a reasonable outcome preferable to running all auto-incrementing transactions serially.

Currently the Sequence code uses a Persistit SUM accumulator to maintain the count. The semantics of SUM are to provide a transactionally accurate count. So if three transactions concurrently increment a SUM accumulator, and then two commit and one aborts, the result will be 2.

What confuses the issue is that Accumulators offer two values: the "snapshot" value, which is consistent with the state of the database at the start of the transaction, and the "live" value, which is modified as updates are executed. The live value is not transactionally correct; it is an "estimate" of the value accurate only if ever transaction has committed. (I note that there's no attempt to adjust the live value even when an aborted transaction is pruned. We might want to change that.) The live value of a SUM accumulator is not maintained transactionally - in fact it explicitly diverges from any consistent snapshot view.

What further confuses the issue, as Nathan notes, is that the Accumulator#update operation always returns the live value, but is not documented. What the code today is actually doing is using the live value of a SUM accumulator, which appears to work just fine for awhile. To see a failure there must be one or more update transactions that increment the accumulator and then abort, leaving the live value larger than the snapshot value by N where N is the number of transactions that aborted. Everything continues to work correctly until the server is restarted; when that happens the live value is reset to the snapshot value that existed at the time of the shutdown, and therefore after restarting, the next auto-increment value obtained is smaller than one produced prior to shutdown - hence the duplicate key exceptions.

The only way to use a SUM accumulator to generate unique ID values is to use its snapshot value. But unfortunately, this will work only if all update transactions that perform auto-increment are constrained to execute serially. That is, to take out a big lock (or force a w-w-conflict) to prevent concurrent...

Read more...

Nathan Williams (nwilliams) wrote :

Thanks for the excellent summary Peter.

What does incrementing by 1 and mul/mod buy us? More runway before needing a reset?

The upgrade procedure you proposed sounds about right: drop, scan for max, and recreate. Care will need to be taken with reusing the index (i.e. a new one and deprecate the old is probably simpler), but that's just details.

As far as the API, I would propose an "opt-in" for the live value. Something like update() return void and add a new updateAndGetLive() that is documented as such.

Thomas Jones-Low (tjoneslo) wrote :

I distinctly recall having the discussion of the use of the SEQ vs SUM accumulators for the sequences. I had assumed that both accumulators were the same transactionally.

>
> (a) We have no way of rolling the value back; it always, for all time, monotonically increases.
>

This is the reason we chose SUM over SEQ. We couldn't implement cycle nor increment by -1 as SEQ accumulators. I felt it was better to have the accumulator hold the true value of the sequence, rather than having a two step process to derive the value.

if, in order to get the transactional support we require for the underlying accumulator, sequences need to use SEQ accumulators the process to derive the true sequence value will need to multiply the SEQ accumulator value by the increment and mod by the cycle value.

Changed in akiban-persistit:
status: New → Fix Committed
importance: Undecided → High
assignee: nobody → Peter Beaman (pbeaman)
milestone: none → 3.2.8
Changed in akiban-server:
status: New → Fix Committed
importance: Undecided → High
assignee: nobody → Nathan Williams (nwilliams)
milestone: none → 1.6.1
Peter Beaman (pbeaman) wrote :

The outcome:

Persistit Version 3.2.9 has a modified API for Accumulators. The Javadoc has been reworked, hopefully to clarify everything.

You now get an accumulator of a specific type with code such as this:

  SeqAccumulator sa = tree.getSeqAccumulator(index);

You update the accumulator with a method that is specific to that type; for example, SeqAccumulator#allocate() is the method used to allocate a new sequence number, while SumAccumulator#add(long) increments to a SumAccumulator. Only SeqAccumulator#allocate() returns a value - the other updating methods are are of return type void. This is because only in the case of the SeqAccumulator#allocate() method is the returned value useful.

We think these changes will make the specific use cases more natural to use and will help prevent confusion and error.

Changed in akiban-persistit:
status: Fix Committed → Fix Released
Changed in akiban-server:
status: Fix Committed → Fix Released
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers