Mailing-List: contact dev-help@directory.apache.org; run by ezmlm
Precedence: bulk
Reply-To: "Apache Directory Developers List" <dev@directory.apache.org>
Received-SPF: pass (athena.apache.org: domain of elecharny@gmail.com
 designates 74.125.82.178 as permitted sender)
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=message-id:date:from:reply-to:user-agent:mime-version:to:subject
         :content-type:content-transfer-encoding;
        b=SS4jNv1TD3xCp5oe5/l82xC4Bv+cpz+osoajwJyK09HvNTcQNnSD8pqa+KD/bv7mQ6
         faKrDRKRRfWjWu3A6/s9YS5J75grz6v5pvJodOnzKAJA1aah7kwdGXUSGtFmhz6zwVov
         oZidHfBiArWqcNYVGR9s8c7WvwRzWv5AQU29E=
Message-ID: <4BFB955E.2070602@gmail.com>
Date: Tue, 25 May 2010 11:16:14 +0200
From: Emmanuel Lecharny <elecharny@gmail.com>
Reply-To: elecharny@apache.org
User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.6; en-US;
 rv:1.9.1.9) Gecko/20100317 Thunderbird/3.0.4
MIME-Version: 1.0
To: Apache Directory Developers List <dev@directory.apache.org>
Subject: About index and atomic operations
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 8bit

Hi guys,

as I'm currently reviewing the JDBM code, I think we might get better 
performance if we use another solution than brutal synchronization (also 
the current implementation is not 100% threadsafe). Right now, the 
AbstractStore is the class responsible for accessing the entries, and 
update the DIT. As we must provide operation atomicity, we have 
synchronized those methods :
- add(entry)
- delete(DN)
- modify()
- move()
- rename()
All the other methods aren't synchronized, so for instance calling 
getUserIndex() does not guarantee that the returned index is protected 
against concurrent modifications.

In fact, we must see an operation as atomic, which means no other thread 
can access the modified index and data while the operation is not 
completely done.

JDBM does not offer such a level of protection.

In order to guarantee atomic operations, we should instead implement a 
system based on MVCC (Multiple Version Concurrent Control), where all 
the reads are done expecting that the data hasn't been modified since 
the operation started (avoiding costly locks to be used), and a two 
steps modification :
- first locally modify the data structure (nothing is locked until all 
the modified elements are updated in memory). That means we read from 
the disk and store in memory the necessary elements for this operation.
- then when done, acquire a global lock and update the data structure 
for all the modified elements

Doing so will allow us to  spare a lot of contention, as we only update 
the modified elements (ie, if we add an entry, the associated BTrees 
index won't necessary be updated from root to leaves. Usually, only one 
leaf is modified), restricting the time necessary to do the commit to 
the minimum.

In any case, read are not synchronized, we just return what is present 
in the backend using the latest version. Obviously, we can get an error 
if for instance we are reading all the children of an entry, and if this 
entry is deleted since the operation started, but that's not a problem: 
there is no guarantee in LDAP that a returned resut is stil present in 
the DIT.

In order to do that, we will associate a version to each element we 
store, so we just have to compare the element version with the latest 
version for this element.

Ok, this is a rough description of the whole mechanism, but that should 
work well.

-- 
Regards,
Cordialement,
Emmanuel L�charny
www.nextury.com