List:Falcon Storage Engine« Previous MessageNext Message »
From:Jim Starkey Date:December 9 2008 10:37pm
Subject:Re: New dependency manager - optimization for read-only transactions
View as plain text  
Olav Sandstaa wrote:
> 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:
Olav, have you consider pre-assigning transaction ids to the extra 
transactions added to the list?  That would keep the transaction ids in 
order and eliminate the hassle about the oldest active transaction.

If you were to add cycle locking, you could let the cycle manager remove 
completed, no-commit transactions from the middle of the active 
transaction list and move them to the end of the list as available 
transactions.  (If you added two cycle managers, you could have bicycles 
or maybe outboard motors)
> 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 allocation
>   -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....)
Leaving committed no-update transactions in the active transaction list 
for a cycle manager to move to the end is simple, fast, elegant, and 

Jim Starkey
President, NimbusDB, Inc.
978 526-1376

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