heads up about DIRSERVER-1377/1369

[Emmanuel Lecharny <el...@apache.org>]

Hi,

so I think the issue is now fixed (crossing fingers). I write this mail 
in order to give some info about what has been done.

First, I would like to thank Kiran who seconded me during the long 
process of trying to get the bug fixed. I would like to thank Sumit 
Goyal and Murali Krishna who found the bug and submitted a test to 
exhibit the problem. It was incredibly useful.

It took me a month - even if I didn't worked only on this problem, as I 
also had to deal with some client at the same time -, but I can tell 
that it was the most complicated problem I have ever had to work on. I'm 
not 100% sure what exactly was the problem, I'm afraid that I just put 
it aside when I removed the AvlTree implentation to replace it with some 
simpler data structure.

When the issue was first created, I thought it was a problem with MINA, 
as we had a concurrency issue with version 2.0.0-M4. Then I bumped up 
the version to 2.0.0-M5, and closed the initial issue. Sadly, after some 
more tests, another issue showed up, with a different error message, and 
the JIRA was reopened.

A test was provided, which was the most useful thing possible, as it 
helped me to reproduce the error on my computer. We started some more 
debugging session, and the problem occurred quite immediately.

But first, we have seen another problem : an index was growing without 
bound (SubLevel). We debugged the server with Kiran, and found the 
reason. At least, it was easy to fix, even if it wasn't related to the 
initial issue. Lesson learned : when something is wrong, it's very 
likely that while investigating the problem, you find some other 
problems around :). The bad news is that many parts of the server need 
more thorough tests :/

While reviewing the index handling, as the problem seemed to be in this 
area (some few stackTrace helped to show that, at least : sometime old 
school debugging with printf come to the rescue... ), we also cleaned 
many small things, like useless deletion of non existing elements in index.

Then we started to think about the way the server stores data on disk. 
Basically, you have N threads updating many index and the master table, 
and all those data read and write is done in a thread-safe part of the 
server (Jdbm backend). As every access to JDBM is synchronized, we 
discarded the idea that JDBM was buggy at this point. It narrowed the 
issue to what is in between the interceptor chain and JDBM.

Then we saw that the place we massage index was not thread safe. In 
other words, as we have to update around 10 index when updating an 
entry, it must be done in a way that guarantee that the index can't be 
fooled by another thread. This was not the case. We then thought we 
found the reason of the concurrent problem. We fixed that by adding a 
hell of synchronized all over this part of the code.

Great success ! When the multithreaded test was launched, instead of 
failing after a few hundreds of updates, it was now running well for 
thousands of updates (I went up to 700 000 updates before getting a 
breakage).

That was the good news. The bad news was that the problem was still 
around, but deeper. At least, we know for sure that we removed a real 
concurrent issue in the code. So what could be the problem ?

When we are storing data in indexes, we store one key associated to many 
values (for instance, an ObjectClass can be related to many entries). In 
order to manage this, we use a ordered data structure to store those 
values. Namely, depending on the number of values, either an AvlTree or 
a BTree. This AvlTree has to be serialized and deserialized in order to 
be stored on disk. This is where I thought we could have an issue : the 
de/serialization was done outside of the synchronised part, which is not 
a problem per se, but we send and get back a byte[] from JDBM. What is 
fishy here is that JDBM caches some data, and returns a *reference* to 
the data . Getting a reference on a byte[] means that some other thread 
can perfectly modify this byte[] at the same time, with a potential 
impact on the expected result. It sounded like a good catch, so I 
modified JDBM to get it return a copy of the byte[]. It didn't changed 
anything, I still get the error after a few hundred thousands updates.

Next step was to start suspecting the AvlTree implementation. I decided 
that rewriting this part was a sane idea. What a fool ... AvlTree is a 
complex data structure, and writing an iterative implementation needs 
time, and a hell of tests. Basically, as I was stuck with no other 
ideas, I followed this idea, even if it was crazy. (some little voice in 
my head was telling me I'm not any more a student, and this was a lost 
of time, but the other side of my personality told me that I was smart 
enough to do better than what we have ...). The bad thing about Avl 
trees is that documentation about it is *very* rough on the internet. 
There are some C implementations, but they use pointers, something we 
don't have in Java, making it quite complex to implement. We also have 
some specific needs, like we want to be able to move backward and 
forward in the tree, adding more constraints.

After around 2 weeks and a half, having a partially working AVLTree 
impelmentation, I just had a better idea. In the mean time, Kiran has 
implemented an in-jdbm serialization, removing the previous potential 
problem with byte[] copies.

So the new idea was that we don't need AvlTree, we just need a sorted 
array, which was less costly when searching data into it (O(N) for a 
sorted array, compared to a 1.44O(N) for an AvlTree). Sure, insertion 
and removal was more costly, as it needs an array copy, but as we don't 
do a lot of addition or removal, that was a good trade. More important, 
it save a lot of memory, and serialization was way easier (memory shring 
by 4, for references to an entry, as we have less pointers (left and 
right child, previous and next leaf, and the balance)). Less memory 
consumption means more cache, less garbage collection, less pointer 
update, faster read and write on disk.

I ended by writing this ArrayTree implementation, which took me three 
days, with all the necessary tests, and a bit of problems with the 
current Cursor interface (there are some semantic I really don't like in 
this area). Then I just had to substitute AvlTree with ArrayTree, and voilà.

Tests went up to 2 000 000 updates, without any problem. Twice. So I 
closed the issue.

My understanding is that the previous AvlTree had a problem in the way 
it managed next/previous index. I didn't spent time in analysing the 
code, it was too complex. Last, not least, I added a lot of debug logs 
in the server, and tried to see what the logs gave. That led me to 
grep/sed a few gigabytes of logs, with little success. It just sucked 
time, with no result except to eliminate other options.

Last, not least, what made me thing that the bug was a problem in 
AvlTree in some very specific cases, is that we always had a NPE in the 
very same line, and that the analyze of the byte[] taken from the JDBM 
backend shown that there were some missing elements in the serialized 
tree. As the tree was correctly serialized (I added some check in the 
serialize() method : the byte[] was deserialized before being stored in 
JDBM to be sure that the serialization was ok, and I had no problem in 
it), that mean something was broken while rebuilding the AvlTree.

It now seems to work, but I'm not 100% sure the problem is really fixed. 
I think I just pushed some dust in the trash bin, expecting that it was 
not pushing them under the rug...

In any case, this part of the server needs a deep check, as I saw many 
potential problems that needs to be addressed. We probably have to run 
this multi-threaded test on a more powerful computer, to see if it is 
really fixed.


-- 
--
cordialement, regards,
Emmanuel Lécharny
www.iktek.com
directory.apache.org