db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Knut Anders Hatlen (JIRA)" <j...@apache.org>
Subject [jira] Commented: (DERBY-2991) Index split deadlock
Date Thu, 04 Dec 2008 17:08:44 GMT

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

Knut Anders Hatlen commented on DERBY-2991:

Thanks to all of you for looking at this.

To Kathey's questions, I will get back to working on this issue next
week and hope to have optimized the patch further and tested it some
more by the end of that week. It's difficult to say when a fix can be
committed to trunk, as it depends on whether we find the suggested
approach acceptable or if we need to find another way to fix it. And
as Mike mentioned more testing is needed in any case. I do hope we can
come up with an approach everyone feels comfortable with in the next
couple of weeks before the holiday season, and then get it implemented
and properly tested in January. I agree with Mike though, that it's
probably too risky to backport the fix, unless we end up with
something simpler than the current proposal. Not that I'm planning to
introduce any bugs, but since it changes some fundamental assumptions
in a critical part of the system, I wouldn't feel all that comfortable
with backporting it.

To Mike's questions:

Yes, I think it is possible to only save the position in situations
that could cause deadlocks. That would mean that we only save the
position if we need to wait for a lock. One possible complication is
that it's not necessarily the scan that's waiting for a lock that's
holding the scan lock that causes the deadlock. Therefore we would
need to save the position in all the open B-tree scans in the
transaction when a lock cannot be granted immediately. And this must
be done for all locks that we wait on, not only locks in B-tree scans,
so it will add complexity to code outside the B-tree code as
well. Given that this increases the complexity and removing the scan
locks reduces the complexity, I'd prefer a solution where the scan
locks are removed completely if it can be done with acceptable

As to the performance, I hope that it will be possible to measure the
actual cost of copying the key once I have removed the expensive and
unnecessary renavigation. You are right that the suggested
optimization will only save the renavigation, not the copying. Some

  - The current code that saves the key always allocates a new
    DataValueDescriptor array and populates it with empty
    DataValueDescriptors of the correct type. It shouldn't be
    necessary to do this more than once per scan. That could save much
    allocation/gc work.

  - When we save the key, we retrieve it by calling fetchFromSlot(),
    which will deserialize the value of the key from the page. I think
    that this is causing the same work to be performed twice when we
    save the position in methods like BTreeForwardScan.fetchRows(), at
    least when the scan is returning the full key, and we could
    probably make this more efficient.

  - What we save by not obtaining/releasing the scan lock includes 2-3
    lookups in a global hashtable per leaf page, which could give an
    extra benefit in a multi-threaded scenario.

  - It's not clear to me that the size of the key is significant. The
    cost of the scan lock is constant per page. Since a bigger key
    means fewer keys per page, the cost of copying keys should also be
    more or less constant per page. So the ratio between the cost
    saved and the cost added may not be that much affected by the size
    of the key.

  - One of the worst cases is probably where extra qualification of
    the row is needed. Like "SELECT index_column FROM t WHERE
    length(index_column) = 10", in which case I think we'll release
    the latch, and therefore also save the key, for every row in the

The suggestions for new tests look reasonable to me. The current
regression tests probably don't test that the current position has
been moved to another page while we didn't hold the latch, since those
situations would have resulted in a lock timeout before. So we
basically need to have tests for split/merge/reclaim for every call to
reposition() in the code. Will need to think more about how to do
that. Thanks for raising the concern for the previous key locking as

> Index split deadlock
> --------------------
>                 Key: DERBY-2991
>                 URL: https://issues.apache.org/jira/browse/DERBY-2991
>             Project: Derby
>          Issue Type: Bug
>          Components: Store
>    Affects Versions:,
>         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, derby.log, InsertSelectDeadlock.java,
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 and 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.

View raw message