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
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.
Created attachment 177599 [details] Patch
Created attachment 177600 [details] Patch
Blurgh, introduced WebIDBTransaction::Mode enum, will mean some Chromium hijinx to land this.
Created attachment 177602 [details] Patch
Leaving mode as just an unsigned short in the chromium public WebKit API for now.
Comment on attachment 177602 [details] Patch Passes in content_shell and various other Chromium tests locally. dgrogan@, alecflett@ - please take a look.
Comment on attachment 177602 [details] Patch Attachment 177602 [details] did not pass cr-android-ews (chromium-android): Output: http://queues.webkit.org/results/15158095
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?
Comment on attachment 177602 [details] Patch Attachment 177602 [details] did not pass chromium-ews (chromium-xvfb): Output: http://queues.webkit.org/results/15136005
Created attachment 177763 [details] Patch
(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.
Created attachment 177830 [details] Patch
> > 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?
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?
(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.
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.
Created attachment 177852 [details] Patch
(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.
tony@ - r?
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.
(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.
Created attachment 177856 [details] Patch
(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?
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.
(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!
Created attachment 177872 [details] Patch for landing
Comment on attachment 177872 [details] Patch for landing Clearing flags on attachment: 177872 Committed r136782: <http://trac.webkit.org/changeset/136782>
All reviewed patches have been landed. Closing bug.