Re: [Exist-development] [Exist-open] Performance of concurrent read queries.

[Jason S. <js...@in...>]

The problem with deadlocks (the one I ran into) doesn't actually have anything to do with the collection hierarchy.  They are simply caused by taking two locks out of order. The fact that ReentrantReadWriteLock appears to be using a hierarchy (it actually isn't) is a red herring.

If I understand this correctly, the new design will need to manage, potentially, hundreds of thousands of locks that can be taken in arbitrary order.  If that's true, there are still going to be deadlocks.  And since this is such fantastically granular locking, finding the deadlocks will be very slow (I think it's an n^2 algorithm - at least Java's deadlock detection appears to be n^2).

There are only three ways to avoid deadlocks.

THE THREE WAYS TO PREVENT DEADLOCKS

1) Use a single global mutex to lock.  A single mutex cannot deadlock.
2) If you have more than one lock, guarantee that all locks are taken in the same order every time.
3) Don't use locking at all.  Use a scheme that avoids the need for locking.

Otherwise, if you are using mutex locks, you will have deadlocks.  They are, unfortunately, unavoidable if the design doesn't fall into one of these 3 categories.

Option 2 is actually feasible.  This is the Clojure approach to the world - all data structures are read only, and you "mutate" something by reconstructing a new copy with the changes (sharing the old data wherever possible).  

I am assuming, going forward, that the structures in the database are intended to be mutable, and they need to be protected by locks that can be taken in arbitrary order.  If that is correct, then deadlocks are going to occur.  

Does this make sense, or am I out in left field? :-)



-----Original Message-----
From: Wolfgang Meier [mailto:wol...@ex...] 
Sent: Wednesday, September 01, 2010 2:53 AM
To: Jason Smith
Cc: Adam Retter; Paul Ryan; eXist development; Michael J. Pelikan; Todd Gochenour
Subject: Re: [Exist-development] [Exist-open] Performance of concurrent read queries.

> If you remove collection locks, does that mean you are planning to lock at the resource level?

Yes. In the current design, a resource does physically belong to a
collection. To read or write a resource, you have to access the
collection object first, then acquire a lock on the resource. Removing
this direct dependency between collection and resource will have a
number of benefits:

1) resource updates will become faster and scale better: indexes are
currently organized by collection, which introduces a dependency
between collection size and update speed (this has already been
dropped for the structural index in trunk). The larger the collection,
the slower your updates. Removing this dependency will increase
scalability. You will be able to index or reindex a single resource
without touching or locking the rest of the collection.

2) queries will consume less memory: right now, a query needs to load
all required collections plus the internal metadata (name,
permissions, owner...) for all resources at the start. This is slow
and takes a lot of space. If resources are decoupled from collections,
a query will just need the document id plus the lock for every
resource. We no longer have to retrieve the actual document object.
Instead, a lock manager maintains a simple map of documentId -> lock
and the query uses the documentId only. A stored node in eXist is
currently represented by a pair <DocumentImpl doc, long nodeId>. This
will change to <int docId, long nodeId>.

3) the transaction log will become much easier to maintain. Right now
we have to make sure that transactional integrity is preserved for
both: dom.dbx and collections.dbx, at the same time, which introduces
a number of problems. Decoupling them simplifies the transaction log
since both indexes become independent and can be maintained
independently.

4) the main deadlock issue, which is caused by the hierarchy of
collection and resource locks, will disappear. If the collection is
just a virtual entity, you only need to lock it if you modify its
metadata (name, owner, permissions). Writing or reading a resource
will not require a lock on the collection anymore since the resources
are just loosely assigned to a collection.

5) if collections are entirely virtual, you can assign a resource to
more than one collection. On the other hand, it may become possible
for a resource to not be a member of any collection at all (in which
case it is handled as a direct child of the root collection?).

> Wouldn't that potentially lead to an awful lot of locks being taken?  Am I misreading the idea?

You won't need to take more locks than you do right now (rather less,
since the collection locks disappear).

Related to this discussion is the question of dirty reads: currently
the query engine does allow dirty reads to some extent. I'm not yet
sure if we should keep it like that (and just handle them more
transparently) or disallow them completely.

I'll try to come up with some graphic or mind map to explain the
overall picture.

Wolfgang