Bug 97570 – IndexedDB: Allow multiple transactions to interleave request execution

• Status: RESOLVED
• Resolution: FIXED
• Component: WebCore Misc.

[Joshua Bell]

Per spec http://dvcs.w3.org/hg/IndexedDB/raw-file/tip/Overview.html#transaction-concept transactions within a database can run in parallel:

* a version change transaction precludes all other transactions
* "readonly" transactions can run at the same time even if their scopes are overlapping
* multiple "readwrite" transactions can't run at the same time if their scopes are overlapping

More details in the spec about letting readonly and readwrite transactions run in parallel - basically, transactions should read from a data snapshot so that their view of data is consistent.

Following webkit.org/b/97501 WebKit runs transactions serially within a database. Allowing read-only transactions to run in parallel will be a nice performance boost. We can do this incrementally:

(1) Allow transactions with non-overlapping scopes to run in parallel
(2) Allow read-only transactions with overlapping scopes to run in parallel
(3) Give each transaction a "snapshot" of the database, and only serialize read-write transactions with overlapping scopes

[Joshua Bell]

Created attachment 165628 [details]
Sample C++ code for scope comparison

The attachment contains some C++ code that implements the overlapping scope semantics. It was not developed against the current IDB implementation so it is not just a patch, just capturing implementation ideas.

[Joshua Bell]

Created attachment 177599 [details]
Patch

[Joshua Bell]

Created attachment 177600 [details]
Patch

[Joshua Bell]

Blurgh, introduced WebIDBTransaction::Mode enum, will mean some Chromium hijinx to land this.

[Joshua Bell]

Created attachment 177602 [details]
Patch

[Joshua Bell]

Leaving mode as just an unsigned short in the chromium public WebKit API for now.

[Joshua Bell]

Comment on attachment 177602 [details]
Patch

Passes in content_shell and various other Chromium tests locally. 

dgrogan@, alecflett@ - please take a look.

[Peter Beverloo (cr-android ews)]

Comment on attachment 177602 [details]
Patch

Attachment 177602 [details] did not pass cr-android-ews (chromium-android):
Output: http://queues.webkit.org/results/15158095

[David Grogan]

Comment on attachment 177602 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=177602&action=review

I'm assuming you're going to add a test that RW transactions block other transactions, etc.

It's impressive that all the prep work allowed this patch to be so small.

> Source/WebCore/Modules/indexeddb/IDBTransactionCoordinator.cpp:104
> +    ListHashSet<IDBTransactionBackendImpl*>::const_iterator it = m_startedTransactions.begin();

You'll have to add some stuff here to take care of the A blocks A,B which should block B,C situation?

> Source/WebCore/Modules/indexeddb/IDBTransactionCoordinator.cpp:109
> +            m_startedTransactions.remove(transaction);

I feel like "started" is used as "queued."

> Source/WebCore/Modules/indexeddb/IDBTransactionCoordinator.cpp:112
> +        }

I can't convince myself either way of a starvation problem. If there is one I think you could use else { return; } here as a sledgehammer that would also fix the A->A,B->B,C problem.

> LayoutTests/storage/indexeddb/database-close-expected.txt:-42
> -awaiting_transaction_count -= 1

What was happening here?

[WebKit Review Bot]

Comment on attachment 177602 [details]
Patch

Attachment 177602 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/15136005

[Joshua Bell]

Created attachment 177763 [details]
Patch

[Joshua Bell]

(In reply to comment #9)
> > Source/WebCore/Modules/indexeddb/IDBTransactionCoordinator.cpp:104
> > +    ListHashSet<IDBTransactionBackendImpl*>::const_iterator it = m_startedTransactions.begin();
> 
> You'll have to add some stuff here to take care of the A blocks A,B which should block B,C situation?

Yes. Probably build up a union of all prior scopes, and look closely at the spec re: being blocked on started vs. running transactions.
 
> > Source/WebCore/Modules/indexeddb/IDBTransactionCoordinator.cpp:109
> > +            m_startedTransactions.remove(transaction);
> 
> I feel like "started" is used as "queued."

Yeah, it's confusing. I think it matches the spec terminology but I'll revisit.

> > Source/WebCore/Modules/indexeddb/IDBTransactionCoordinator.cpp:112
> > +        }
> 
> I can't convince myself either way of a starvation problem. If there is one I think you could use else { return; } here as a sledgehammer that would also fix the A->A,B->B,C problem.
> 
> > LayoutTests/storage/indexeddb/database-close-expected.txt:-42
> > -awaiting_transaction_count -= 1
> 
> What was happening here?

Surprisingly only two tests had output affected by the change. This one fired off two transactions and then waiting for them both to finish. Prior to this patch the first would log completion before the second started. With the patch they'd both run then complete at the "same time" so the placement of this line in the output would differ. Since the test was not about transaction sequencing I made the output "agnostic" rather than reliant on the change.

[Joshua Bell]

Created attachment 177830 [details]
Patch

[Joshua Bell]

> > You'll have to add some stuff here to take care of the A blocks A,B which should block B,C situation?
> 
> Yes. Probably build up a union of all prior scopes, and look closely at the spec re: being blocked on started vs. running transactions.

Easier than I thought - just need to loop over both started and queued transactions. Anything earlier that overlaps blocks a transaction.

> > I feel like "started" is used as "queued."
> 
> Yeah, it's confusing. I think it matches the spec terminology but I'll revisit.

Renamed started->queued, running->started which matches spec.
 
> > I can't convince myself either way of a starvation problem. If there is one I think you could use else { return; } here as a sledgehammer that would also fix the A->A,B->B,C problem.

Added a test for the [A], [A,B], [B,C] case.

The spec says "If multiple "readwrite" transactions are attempting to access the same object store (i.e. if they have overlapping scope), the transaction that was created first must be the transaction which gets access to the object store first. Due to the requirements in the previous paragraph, this also means that it is the only transaction which has access to the object store until the transaction is finished."

If I'm reading it right, that prevents a transaction filed later from ever blocking a transaction filed earlier.

dgrogan@, another look?

[David Grogan]

Comment on attachment 177830 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=177830&action=review

Could you add a test that tries to starve a readwrite transaction? The part of the spec I'm worried about is:

User agents must ensure a reasonable level of fairness across transactions to prevent starvation. For example, if multiple "readonly" transactions are started one after another the implementation must not indefinitely prevent a pending "readwrite" transaction from starting.

Something like
(function {
  db.transaction(A).store(A).get(adsf).onsuccess = this;
})();

db.transaction(A, rw).objectStore(A).get(adsfa).onsuccess = finishJSTest;

(Sorry, that was just fun to write. Write the test however you want :)

Though if you want to commit this before worrying about starvation, I'm fine with that: LGTM

> Source/WebCore/Modules/indexeddb/IDBTransactionCoordinator.cpp:118
> +    for (HashSet<int64_t >::const_iterator it = scope1.begin(); it != scope1.end(); ++it) {

extra space before >

> Source/WebCore/Modules/indexeddb/IDBTransactionCoordinator.cpp:144
> +            if ((*it)->mode() == IDBTransaction::READ_WRITE && doScopesOverlap(transaction->scope(), (*it)->scope()))

Isn't transaction still in m_queuedTransactions and needs to be skipped?

[Joshua Bell]

(In reply to comment #15)
> (From update of attachment 177830 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=177830&action=review
> 
> Could you add a test that tries to starve a readwrite transaction? 

Will do. 
 
> > Source/WebCore/Modules/indexeddb/IDBTransactionCoordinator.cpp:118
> > +    for (HashSet<int64_t >::const_iterator it = scope1.begin(); it != scope1.end(); ++it) {
> 
> extra space before >

Fixed.
 
> > Source/WebCore/Modules/indexeddb/IDBTransactionCoordinator.cpp:144
> > +            if ((*it)->mode() == IDBTransaction::READ_WRITE && doScopesOverlap(transaction->scope(), (*it)->scope()))
> 
> Isn't transaction still in m_queuedTransactions and needs to be skipped?

Not just skipped - it's actually the loop termination condition (so the check is in there but not on its own line), because the transaction in question shouldn't block on any subsequent queued transactions. This is covered by the existing test since otherwise in [A], [A,B], [B,C] the second would block on the third.

[David Grogan]

Comment on attachment 177830 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=177830&action=review

>>> Source/WebCore/Modules/indexeddb/IDBTransactionCoordinator.cpp:144
>>> +            if ((*it)->mode() == IDBTransaction::READ_WRITE && doScopesOverlap(transaction->scope(), (*it)->scope()))
>> 
>> Isn't transaction still in m_queuedTransactions and needs to be skipped?
> 
> Not just skipped - it's actually the loop termination condition (so the check is in there but not on its own line), because the transaction in question shouldn't block on any subsequent queued transactions. This is covered by the existing test since otherwise in [A], [A,B], [B,C] the second would block on the third.

Ah, missed that termination condition. Good algorithm.

I suspect something similar will be necessary in "case READ_ONLY:" above.

[Joshua Bell]

Created attachment 177852 [details]
Patch

[Joshua Bell]

(In reply to comment #17)
>
> I suspect something similar will be necessary in "case READ_ONLY:" above.

As we talked about offline, it appears from the spec that readonly transactions are never blocked nor do they ever block other transactions, so no additional tests are necessary here.

[Joshua Bell]

tony@ - r?

[David Grogan]

Comment on attachment 177852 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=177852&action=review

> LayoutTests/storage/indexeddb/resources/transaction-starvation.js:38
> +    transaction.oncomplete = function() {

I think that this should be in a request.onsuccess handler, not the complete handler. As it stands here, I don't think it would detect a starvation problem if there were one: when the readwrite transaction is started both m_queuedTransactions and m_startedTransactions are empty, so the readwrite transaction would proceed merrily. We want to test the scenario wherein a readwrite transaction is started when there's >0 readonly transactions in m_startedTransactions.

Or am I missing something?

> LayoutTests/storage/indexeddb/resources/transaction-starvation.js:57
> +        shouldBeTrue("readOnlyTransactionRunning");

Ah, and this tests that a readonly transaction is not blocked on a readwrite. I like it.

[Joshua Bell]

(In reply to comment #21)
> (From update of attachment 177852 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=177852&action=review
> 
> > LayoutTests/storage/indexeddb/resources/transaction-starvation.js:38
> > +    transaction.oncomplete = function() {
> 
> I think that this should be in a request.onsuccess handler, not the complete handler. 

You're right, it could slip in. I'll fix.

[Joshua Bell]

Created attachment 177856 [details]
Patch

[Joshua Bell]

(In reply to comment #23)
> Created an attachment (id=177856) [details]
> Patch

Slight tweak per discussion - the starvation test now "merely" verifies that a "readonly" transaction doesn't block a "readwrite" transaction. It doesn't generate a chain of "readonly" transactions as that could permit a bug (e.g. a bogus anti-starvation algorithm) to allow the new "readonly" to get delayed until after the "readwrite"

tony@ - r?

[Tony Chang]

Comment on attachment 177856 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=177856&action=review

> Source/WebCore/ChangeLog:3
> +        IndexedDB: Allow multiple transactions to run in parallel

Thanks for explaining this to me in person. I think saying that the transactions are interleaved is more accurate than saying they run in parallel since they still take turns hitting the database.

[Joshua Bell]

(In reply to comment #25)
> I think saying that the transactions are interleaved is more accurate than saying they run in parallel since they still take turns hitting the database.

I'll twiddle the bug title/changelogs a bit, thanks!

[Joshua Bell]

Created attachment 177872 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 177872 [details]
Patch for landing

Clearing flags on attachment: 177872

Committed r136782: <http://trac.webkit.org/changeset/136782>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.