List:Falcon Storage Engine« Previous MessageNext Message »
From:Olav Sandstaa Date:December 9 2008 10:18pm
Subject:New dependency manager - optimization for read-only transactions
View as plain text  

The last days I have been working on re-introducing optimizations for 
read-only transactions in the new dependency manager.  This email gives 
an overview of these changes in case someone is interested to learn 
about these and for helping any reviewers to understand the changes.

I have done the optimizations as three separate patches - both to be 
able to verify that each of them worked correctly and to see the effect 
individual optimizations have. The optimizations I have implemented are:

1. Re-introduce Transaction::commitNoUpdates():

    -This is a special implementation of commit for read-only 
transactions. It commits the transactions without having them go through 
the complete commit code path. They are basically just taken out of the 
active transaction list, cleaned up and the transaction object is released.

    -The initial patch did not re-use transaction objects, just deleted 
them. So the saving was mainly in reduced code path and for not having 
to lock the committed transaction list (the active transaction list was 
locked exclusively)

    -The patch is available here:

2. Introduce CAS allocation and batch-allocation of transaction objects:

    -This patch reduces the number of times an exclusive lock is needed 
on the active transaction list when allocating a transaction object. The 
allocation is now done by searching the list for an "available" (free) 
transaction object. This is done when only having a shared lock on the 
list and the allocation is done by using a CAS (compare-and-swap) operation.

    -If not available transaction is found in the active list, an 
exclusive lock is set and a new transaction object is allocated. To 
increase the likelihood for the next thread searching for an available 
transaction, we allocates ten extra free transaction objects since we 
anyway have the exclusive lock on the list.

    -The "drawback" about introducing this is that the active 
transaction list no longer is guaranteed to be sorted by transactionId. 
This complicates the test for determining when a transaction object can 
be purged from the committed transaction list. Until this introduction 
it was enough to compare the transaction's commitId (endEvent) with the 
transactionId (startEvent) of the first transaction in the active list. 
After this change we have to search the active transaction list in order 
to find the oldest active transaction (and do this while other threads 
are doing CAS on it is a bit, well..  (Yes, Jim, I agree with you about 
non-blocking, concurrent data structures....) (and I am actually 
considering to put an exclusive lock on it while searching for the 
oldest transaction... .- and I am considering to do purging less 
frequently - but that might be a topic of another discussion...)

    -The saving of this patch is that we in most cases is able to 
allocate a transaction object without an exclusive lock on the active 
transaction list.

    - The patch is available here:

3. Re-use read-only transaction objects.

    -This patch changes Transaction::commitNoUpdates() to not delete the 
transaction objects but let them stay in the active transaction list 
marked as "available" (so they can be picked up and re-used by the code 
used in patch 2). Basically, commitNoUpdates() are back as it where when 
I started on this rewrite.

    -The advantage of this is that we now are able to run read-only 
transaction without having to set exclusive locks on the active 
transaction list neither at start of the transaction nor at commit. As 
an example: for each of the patches I have made for the new dependency 
manager I have run a ten hour stress test. Before this latest patch this 
test allocates about 225 million transaction objects. With the latest 
patch it allocates in total about 140 transaction objects (yes, it is a 
read-only test).

    -The patch is ready, but not yet committed.

The effect of these patches are shown in the attached graph for a 
"singel-record select test" (yes, I know it is not representative but I 
selected this test because it is simple and a test where the dependency 
manager's allocation of transaction objects is really stressed and it 
will have huge impact on performance):

   -Red line: performance of old transaction manager
   -Green and blue: new implementation without any optimizations for 
read-only transactions
   -Purple: patch 1 above: shorter code path, no exclusive lock on 
committed list
   -Cyan: patch 2 above: batch allocation of transaction objects and CAS 
   -Brown:  patch 3 above: reuse of transaction objects.

So far so good, and hadn't it been for this morning a single test failed 
on a Windows machine that is most likely related to changes in the 
dependency manager, well time for debugging..... (more info about this 
is a separate email)...

Any questions and comments are as usual welcome (as long as they do not 
involve sorting of lists using CAS....)


New dependency manager - optimization for read-only transactionsOlav Sandstaa9 Dec
  • Re: New dependency manager - optimization for read-only transactionsOlav Sandstaa9 Dec
  • Re: New dependency manager - optimization for read-only transactionsJim Starkey9 Dec
    • Re: New dependency manager - optimization for read-only transactionsOlav Sandstaa10 Dec
      • Re: New dependency manager - optimization for read-only transactionsKevin Lewis10 Dec