On Thu, May 27, 2010 at 6:40 PM, Emmanuel Lecharny <elecharny@gmail.com> wrote:
Hi guys,

as we already know, we may have issue in the way we handle modify operations in the server (add, modify, delete, moddn). Basically, we just synchronized the following methods in the AbstractStore class :
- add
- delete
- modify
- move
- rename

That's good enough to protect the server against concurrent modifications, but the problem is that behind the curtain, they are all being processed by a backend implementation, which can be Jdbm, HBase, Avl, Oracle, ... All those guys are dealing with concurrent access in their own way.

Aye more additional synchronization occurs there too.
Let's focus on Jdbm atm, as it's our main backend. Every operation access many indexes and the master table. Each index is a couple of JdbmTable (forward and backward), and the Master table itself is also a JdbmTable. A JdbmTable itself is backed by a BTree.

So far, so good.

It become a bit more complex when it comes to protecting all this against concurrent access :
- the upper layer (AbstractStore) does not synchronize the read operations
- nor does the JdbmIndex (add, drop(K,Long), sync and close are synchronized, lookups and more surprisingly drop(K) aren't)
- nor does JdbmTable( close, put, remove and sync methods are synchronized, get(K) isn't)
- but all the bTree methods are synchronized, including the one that read data.

That means that, whatever we do, we will have a bottleneck on read operations, and we also have overzealous synchronization as every layer protect all the modify operations. (regardless, this is not really an issue, as we don't care if we synchronize more than once as soon as we are already guaranteed to be thread safe once we get in the AbstractStore)

One question I have is whether or not we can now get rid of the Store layer. Am thinking this might not be needed now and it makes the picture more complex when evaluating these concerns.  Can we re-factor it out of the picture? Thoughts on this?
Now, the question is how can we release this contention on reads ? Obviously, we have to protect the way we modify data against concurrent modifications, otherwise the index will be broken quickly, but we want to allow searches to be done in parallel. That mean we must remove all the synchronization on reads from the BTree implementation.

If we do that, how do we guarantee that a search based on an index will return the correct data, instead of getting an exception because the index is being reorganized by another thread ?

MVCC would protect us from this. MVCC is like working on a copy under concurrency as you already know. Seems though we're dropping the MVCC attack due to how complicated it will be in JDBM.
Considering we keep the current JDBM implementation, I see two ways to do that :
- implementing a kind of barrier that let all the reads to be done without syncronization, blocking writes when they arrive until all the pending reads to be done, then all the following operations will have to wait until the write is done. If the next operations are read, then once the write is done, reads can be done in parallel again.

True this will work but you will still not have full isolation even though you'll remove the chance for dirty reads.  Dirty reads go away where you will not see the partial impact of write based operations. However if a read occurs before the write based operations complete it will see the final state of the write even though it should not since it came before the writes completed.
- using an optimistic lock system, assuming that a read is successful if no write occured between the time the read started and the time it finished. If not, then we redo the read. This can be done using a unique marker, which is incremented by any write operation. If we get any exception during a search, that means we tried to access some data which is not accessible just because a write is modifying the data structure, then we redo the read.

I think this will yield the similar ACID behaviors as the MVCC approach however we'll have read exceptions that require retries on reads. MVCC would not require retries on reads.
The second strategy is not 100% safe, as we have no guarantee n case we start a read just after a write has started, and finish the read before the write has finished. Let's see what it means on a time frame description :

scenario 1:

Thread 1 starts a read at t0
Thread 2 starts a read at t1
Thread 3 starts a write at t3 : it blocks until T0 and T1 are done

At t3, all the new read or writes operation are just blocked, waiting for Thread 3 to be done.

Thread 4 starts a read at t4 : it blocks waiting for T3 to be done
Thread 5 starts a read at t5 : it blocks waiting for T3 to be done
Thread 1 finishes at t6. Nothing changes.
Thread 6 starts a write at t7 : it blocks waiting for T3 to be done
Thread 2 finishes at t8 : Thread 3 is now unblocked, and can be processed. Threads 4, 5 and 6 are still blocked, waiting for T3 to be done
Thread 3 finishes at t9 : we can now process the pending threads : T4, T5 and T6
Thread 4 and 5 are reads, they are executed concurrently
Thread 6 is a write, it has to wait for both T4 and T5 to be done

Here, reads are executed concurrently without synchronization, but blocking the writes, and when a writes come in, everything is blocked until the write is done.

I've attached a hand written graphic as PDF for this scenario. Let me know if it is correct.  More to come on scenario 2  - need to run and take care of a few things first but will continue.

Scenario 2 :
when a write starts, it increment a TS which is global (AtomicLong, for instance)

case 1 :

    W start   W ends
    |         |
    V         V
 ^         ^
 |         |
 R starts  R ends

in this case, the read will grab the TS, and when it ends, the TS it grabs will be different, as a write has started. We can assume that the data we got is not valid anymore, and we redo a read.

case 2 :

    W start   W ends
    |         |
    V         V
 ^              ^
 |              |
 R starts       R ends

same as case 1

case 3 :

    W start   W ends
    |         |
    V         V
       ^         ^
       |         |
       R starts  R ends

Here, the TS is equal, so we may have an exception, or an invalid result. If we get an exception, we can simply restart the read. We have no way to know if the result is valid, so we assume it is, because we don't care if iit's not (once the user has got a result, as LDAP does dirty reads anyway, we are safe)

case 4 :

    W start         W ends
    |               |
    V               V
       ^         ^
       |         |
       R starts  R ends

Same as case 3.

--ends of scenarios--

So we have a scenario 1 where we are totally thread safe, but where reads can be blocked by a write. This is 100% safe, with less contention than what we have right now.

Scenario 2 is a bit less safe, but we don't block reads : we just redo them if we get an exception.

Any better solution implies we implement a better underlying system, based on MVCC for instance.

We also have to keep in mind that writes impact more than one table, and they should be atomic, so we must synchronize writes anyway.

Now, thanks for having read this long brain dump, but I'd like to know what's your opinion about those two strategies, which one should we implement, assuming I'm not off base or that you don't have a better solution to propose ?

Emmanuel Lécharny

Alex Karasulu
My Blog :: http://www.jroller.com/akarasulu/
Apache Directory Server :: http://directory.apache.org
Apache MINA :: http://mina.apache.org
To set up a meeting with me: http://tungle.me/AlexKarasulu