List:Falcon Storage Engine« Previous MessageNext Message »
From:Olav Sandstaa Date:January 23 2009 10:31pm
Subject:Re: Problems with record visibility and how it is computed
View as plain text  
Hi,

Here is a quick summary of some possible solutions for how to solve this 
problem that have popped up the last days.

First a summary of what the problem is: when determining if a 
RecordVersion should be visible for a transaction we check the 
RecordVersion's pointer to the transaction object. If this is non-null 
we access several member variables of the transaction object. At least 
one of the inconsistencies that I have seen occurs when the transaction 
object is deleted (and overwritten) just as we are using its member 
variables for determining the visibility of the transaction.

The list of more or less random ideas for how this can be solved:

1. We can stop using the pointer to the transaction and instead locate 
the transaction by searching for it using the transaction id. 
Disadvantage of this: a) searching for the correct transaction  could 
become costly. b) we would likely have to  introduce an extra data 
structure for locating transaction (e.g. a hash table) and c) we would 
need to  acquire the shared lock on the Transaction::committedList.

2. We can avoid that the transaction object get deleted "behind our 
back" by acquiring the shared lock on the committed transaction list 
each time we call Transaction::getRelativeState and 
Transaction::visible(). Disadvantage: a) a lot of access to this shared 
lock, potential contention

3. An alternative to 2: we introduce a new shared lock for just this 
purpose to avoid the contention on the committed transaction list lock. 
When purging transactions we must acquire an exclusive lock on this 
SyncObject (and we have to reduce the frequency of checking for purging 
of transactions). Disadvantage: a new shared lock that needs to be used 
by both the code checking for visibility and for purging of transactions 
- could still become a hot-spot (I do not think this is very different 
from cycle locking, but I have not thought too much about it yet).

4. Avoid having to access the transaction object: "Duplicate" the commit 
information (one integer) in every RecordVersion object. So when 
committing a transaction, we update every record version with the 
commitId of the transaction and all RecordVersion objects: 
Disadvantages: a) duplication of information b) issues with doing the 
commit as an "atomic operation".

5. "Make it safe to access the transaction pointer and transaction 
object": By never deleting the transaction object until all record 
objects pointing to it have been deleted. This would also simplify some 
of the code since we would always have the transaction available. 
Disadvantages: a) foot print would increase since we would potentially 
have a lot of old transaction objects laying around (and we do not want 
to introduce chilling or backlogging of transaction objects :-) ) b) The 
current scavenger (or a new transaction scavenger?) would need to be 
able to determine when a transaction object was ready for purging. I do 
not know this part of the code, but it might be solvable by having a 
"record version counter" in each transaction object. c) I do not know 
what extra this would cost but I think it should be possible to do 
without any locking.

6. Kevin/Jim's proposal to use a cycle locking - I have not had the time 
to consider this in detail but it might perform similar to alternative 3 
above.

I welcome comments and alternative suggestions.

My current "favorites" this far is 5 (simple, safe and almost lockfree - 
but uses way more memory) and 6 (because it is a great and general idea).

Olav



Olav Sandstaa wrote:
>
> Jim, Kevin, everybody,
>
> I am working on a group of bugs related to transactions not returning 
> the correct data every time. These issues are most likely related to 
> our implementation of isolation levels and visibility of record 
> versions. I have found the cause for one of these bugs but would like 
> input on what is the best way to solve it.
>
> The bug I have been analyzing is Bug #41357 "falcon.falcon_bug_34351_C 
> fails with assertion IS_CONSISTENT_READ". The assert happens in 
> Table::fetchForUpdate() due to the call to 
> Transaction::getRelativeState() returns CommittedInvisible for a 
> recordVersion when the current
> transaction is running in isolation level TRANSACTION_WRITE_COMMITTED. 
> This return value
> should only happen if the isolation level is TRANSACTION_CONSISTENT_READ.
>
> After having reproduced this assert several times with instrumentation 
> in the source it
> seems like this problems is caused by that the Transaction object that 
> the recordVersion
> object has a pointer to and which is used for computing the relative 
> state between the two
> transaction "changes state" during the execution of 
> Transaction::getRelativeState().
>
> Here is what normally happens when the CommittedInvisible state is 
> reached by the following code path:
>
> 1. Transaction::getRelativeState() is called and the following code is 
> run:
>
> if (transaction->state == Committed)
> {
>   // Return CommittedVisible if the other trans has a lower TransId and
>   // it was committed when we started.
>
>   if (visible (transaction, transId, FOR_WRITING))
>       return CommittedVisible;
>
>   return CommittedInvisible;
> }
>
> when this code is run the transaction->state == Committed (and the if 
> test is true).
> This results in Transaction::visible() being called.
>
> 2. In the code for Transaction::visible() the following code is run:
>
> // If the other transaction is not yet committed, the trans is not 
> visible.
>
> if (transaction->state != Committed)
>   return false;
>
> When the same test now is evaluated "transaction->state != Committed" 
> this test too
> succeed and returns that the transaction should not be visible.
>
> So based on traces in the code and studying core files it seems like the
> transaction->state variable changes value from being Committed to not 
> being Committed
> during the execution of these two methods. This leads to 
> Transaction::visible() returning "false" which again leads to
> Transaction::getRelativeState() returning CommittedInvisible (and the 
> assert occurs).
>
> The reason for the "mysterious" state change (at least in some of the 
> crashes I have reproduced) is that the transaction object which the 
> record version points too is deleted by another thread and thus the 
> check for committed (or not)  in Transaction::visible() is now 
> checking "free memory".
>
> This situation seems very similar to an issue Kevin had (and still 
> have?) with the scavenger checking which records that can be scavenged.
>
> Questions:
>
> -how do we either handle that Transaction object that is being pointed 
> to by RecordVersion objects are deleted at "any time". Like the code 
> for Transaction::getRelativeState and Transaction::visible() is now 
> this can lead to wrong conclusions about which records are visible or 
> not.
>
> -or do we need to introduce some kind of locking so that we can safely 
> use RecordVersion objects and the Transaction object they normally 
> refers to?
>
> -or can we do something about the order we clean up old transaction 
> objects versus the record version objects to avoid that we have record 
> object without a transaction object?
>
> I do not know enough about this part of the code (yet) to propose a 
> good solution so any suggestions would be appreciated.
>
> Olav
>
>
>

Thread
Problems with record visibility and how it is computedOlav Sandstaa21 Jan
  • search for null values in indexed columnsVladislav Vaintroub21 Jan
    • Re: search for null values in indexed columnsLars-Erik Bjørk21 Jan
    • Re: search for null values in indexed columnsKevin Lewis21 Jan
      • RE: search for null values in indexed columnsVladislav Vaintroub21 Jan
        • Re: search for null values in indexed columnsKevin Lewis21 Jan
      • Re: search for null values in indexed columnsJames Day23 Jan
  • Re: Problems with record visibility and how it is computedOlav Sandstaa23 Jan
    • Re: Problems with record visibility and how it is computedJim Starkey23 Jan
      • Re: Problems with record visibility and how it is computedKevin Lewis28 Jan
        • Re: Problems with record visibility and how it is computedJim Starkey28 Jan
          • Re: Problems with record visibility and how it is computedKevin Lewis28 Jan
            • Cycle Locking (was Problems with record visibility and how it iscomputed)Jim Starkey28 Jan
            • Re: Problems with record visibility and how it is computedAnn W. Harrison28 Jan
              • Re: Problems with record visibility and how it is computedJim Starkey28 Jan
                • Re: Problems with record visibility and how it is computedAnn W. Harrison28 Jan
                  • Re: Problems with record visibility and how it is computedOlav Sandstaa26 Feb
                    • New Transaction State object (Was: Problems with record visibility andhow it is computed)Olav Sandstaa16 Mar
                      • Re: New Transaction State object (Was: Problems with record visibilityand how it is computed)Kevin Lewis16 Mar
                      • Re: New Transaction State object (Was: Problems with record visibilityand how it is computed)Jim Starkey16 Mar
                        • Re: New Transaction State object (Was: Problems with record visibilityand how it is computed)Olav Sandstaa19 Mar
                          • Re: New Transaction State object (Was: Problems with record visibilityand how it is computed)Jim Starkey19 Mar
                            • RE: New Transaction State object (Was: Problems with record visibilityand how it is computed)Vladislav Vaintroub20 Mar
                            • Re: New Transaction State object (Was: Problems with record visibilityand how it is computed)Olav Sandstaa20 Mar
                              • Re: New Transaction State object (Was: Problems with record visibilityand how it is computed)Jim Starkey20 Mar
          • Re: Problems with record visibility and how it is computedOlav Sandstaa28 Jan
            • Re: Problems with record visibility and how it is computedJim Starkey28 Jan
              • Another Idea for Transaction Lifetime ControlJim Starkey28 Jan
                • Re: Another Idea for Transaction Lifetime ControlJim Starkey29 Jan
              • RE: Problems with record visibility and how it is computedXuekun Hu4 Feb
          • Re: Problems with record visibility and how it is computedAnn W. Harrison28 Jan
  • Quick question on row countsKeith Murphy24 Jan
    • Re: Quick question on row countsJim Starkey25 Jan
      • Re: Quick question on row countsKeith Murphy25 Jan