Mailing-List: contact derby-dev-help@db.apache.org; run by ezmlm
Precedence: bulk
Reply-To: <derby-dev@db.apache.org>
Message-ID: <616110653.1229946284357.JavaMail.jira@brutus>
Date: Mon, 22 Dec 2008 03:44:44 -0800 (PST)
From: "Knut Anders Hatlen (JIRA)" <jira@apache.org>
To: derby-dev@db.apache.org
Subject: [jira] Commented: (DERBY-2991) Index split deadlock
In-Reply-To: <16734720.1186114252905.JavaMail.jira@brutus>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


    [ https://issues.apache.org/jira/browse/DERBY-2991?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12658514#action_12658514 ] 

Knut Anders Hatlen commented on DERBY-2991:
-------------------------------------------

Thanks for your comments, Mike.

> I am not sure if the following will do better, but it is what I
> thought of. It seems like the worst case would be cases where we
> move the scan a lot without having latch on page. ie. case where we
> get one row at a time from the page. So I would suggest using the
> bulk fetch property to only get 1 row at a time: CALL
> SYSCS_UTIL.SYSCS_SET_DATABASE_PROPERTY('derby.language.bulkFetchDefault','1');

Thanks, I wasn't aware of that property. I'll do some experiments with
it.

> 1000 rows does not seem like enough data to do a test. One of the
> problems with the new approach, especially with something like
> decimal is that there is going to be extra object allocation per
> row. So you want enough rows to see what effect it might have on
> GC.

I picked 1000 rows to make sure that we had at least a couple of full
index pages in each of the test cases. I assumed that having multiple
iterations on a smaller number of rows would have about the same
effect on GC as fewer iterations on a larger data set.

> I usually tried to make sure performance test took at least a
> second, and maybe 60 seconds for at least a one time run.

The tests mentioned in my previous comment had a fixed number of
iterations, so the total time for each test case varied between 20 and
150 seconds depending on key size. (The times in milliseconds in the
table must be multiplied by four to get the actual time spent because
of the way the framework runs the tests.) I can also try some longer
runs.

> Is a read only test affected by pages going out of cache? From your
> description I don't think so unless you get very strange cache
> behavior in that the scan current page goes out of cache during the
> scan of that page.

That's correct. Read only tests should not be affected by pages going
out of the cache. Even if the current page goes out while we don't
hold the latch, they shouldn't be affected unless there has been a
modification on the page after the latch was released. In that case
the page will have the dirty flag in addition to the recently-used
flag, so it's highly unlikely that it will be chosen for eviction.

> But might be worth showing that a both approaches
> perform same on a scan of a table that is bigger than the cache when
> the scan is executed multiple times in a row.

Good point. I'll run such a test.

> Should there be something that exercises the worst case where the
> page is updated? Again for this having a bigger dataset wil cause
> more overhead for the search. For this maybe something like a 2 part
> key with first part being as the current test and the second part
> being an int and the test runs a cursor through the table and after
> reading each index row then updates the second part of the key by
> minus one, likely leaving the key on the same page - but not putting
> the scan into an infinite loop. Make sure the cursor choice is one
> which goes to the table every time, not one that caches the values
> in the client somehow.

I think I understand what you're suggesting, but a couple of questions
just to make sure that I'm not missing the point:

  - the purpose of this test is to check that we don't perform any
    repositioning by key just because there has been an update on the
    page?

  - by making sure that the client doesn't cache the values, you
    basically mean that bulk fetch should be disabled? So setting
    derby.language.bulkFetchDefault or perhaps using an updatable
    cursor and positioned updates should do the trick?

> Index split deadlock
> --------------------
>
>                 Key: DERBY-2991
>                 URL: https://issues.apache.org/jira/browse/DERBY-2991
>             Project: Derby
>          Issue Type: Bug
>          Components: Store
>    Affects Versions: 10.2.2.0, 10.3.1.4
>         Environment: Windows XP, Java 6
>            Reporter: Bogdan Calmac
>            Assignee: Knut Anders Hatlen
>         Attachments: d2991-preview-1a.diff, d2991-preview-1a.stat, d2991-preview-1b.diff, d2991-preview-1b.stat, d2991-preview-1c.diff, d2991-preview-1c.stat, d2991-preview-1d.diff, d2991-preview-1d.stat, derby.log, InsertSelectDeadlock.java, perftest.diff, Repro2991.java, stacktraces_during_deadlock.txt
>
>
> After doing dome research on the mailing list, it appears that the index split deadlock is a known behaviour, so I will start by describing the theoretical problem first and then follow with the details of my test case.
> If you have concurrent select and insert transactions on the same table, the observed locking behaviour is as follows:
>  - the select transaction acquires an S lock on the root block of the index and then waits for an S lock on some uncommitted row of the insert transaction
>  - the insert transaction acquires X locks on the inserted records and if it needs to do an index split creates a sub-transaction that tries to acquire an X lock on the root block of the index
> In summary: INDEX LOCK followed by ROW LOCK + ROW LOCK followed by INDEX LOCK = deadlock
> In the case of my project this is an important issue (lack of concurrency after being forced to use table level locking) and I would like to contribute to the project and fix this issue (if possible). I was wondering if someone that knows the code can give me a few pointers on the implications of this issue:
>  - Is this a limitation of the top-down algorithm used?
>  - Would fixing it require to use a bottom up algorithm for better concurrency (which is certainly non trivial)?
>  - Trying to break the circular locking above, I would first question why does the select transaction need to acquire (and hold) a lock on the root block of the index. Would it be possible to ensure the consistency of the select without locking the index?
> -----
> The attached test (InsertSelectDeadlock.java) tries to simulate a typical data collection application, it consists of: 
>  - an insert thread that inserts records in batch 
>  - a select thread that 'processes' the records inserted by the other thread: 'select * from table where id > ?' 
> The derby log provides detail about the deadlock trace and stacktraces_during_deadlock.txt shows that the inser thread is doing an index split.
> The test was run on 10.2.2.0 and 10.3.1.4 with identical behaviour.
> Thanks,
> Bogdan Calmac.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.