directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Alex Karasulu <akaras...@apache.org>
Subject [ApacheDS] Implementing isolation using multi-version concurrency control (MVCC)
Date Sat, 31 Jan 2009 02:43:08 GMT
Hi all,

Emmanuel and I were having an interesting conversation about the kinds of
transaction properties needed by ApacheDS to comply with various
specification requirements. For example all LDAP operations must be atomic
and must preserve consistency. Furthermore, one can easily debate the need
for isolation where any operation does not see or get impacted by the
partial changes of another concurrent operation.

We started discussing these ACID properties and ways in which they could be
implemented. Isolation is very interesting now thanks to directory
versioning and the change log. We can easily implement isolation now. When a
relatively lengthy operation like a search is being conducted, it should not
see modifications within scope that occur after the search began. The search
operation in the example can be replaced with any other operation minus all
unbind, some extended, and all abandon requests.

The change log, not only tracks each change, but it allows the directory
server to inject the "revisions" attribute into entries. The revisions
attribute is multi-valued and lists all the revisions of changes which
altered the entry. For the search example, we can conduct the search
operation while locking it down to a revision.  This is best implemented by
conditionally filtering out or injecting candidates with revisions greater
than the revision at which the search operation started. Let's call the
revision when search started S. So entries in the server which posses
revision numbers greater than S need further evaluation. We have to evaluate
if the filter matches these entries with revisions > S when their state was
at revision S. This may require some reverse patching and re-evaluation of
the filter on the patched entry in state S.  This is not so bad because
there usually are not that many changes taking place at the same time on the
same entry: meaning the number of LDIF's to patch on an entry to evaluate in
it's former state at S will be small. This way we effectively lock down the
search to a specific revision, giving the search operation what appears to
be a snapshot of the DIT. The search results will not be impacted by any
concurrent changes.

Again similar strategies can be applied to any other operation in place of
the search example with specific consideration for each operation.

This is a form of multi-version concurrency control [0], rather than using
locking mechanisms to achieve isolation. This technique works pretty well in
modern DBMS'.

--Alex

--------
[0] - http://en.wikipedia.org/wiki/Multiversion_concurrency_control

Mime
View raw message