Return-Path: Delivered-To: apmail-directory-dev-archive@www.apache.org Received: (qmail 21967 invoked from network); 31 Jan 2009 16:12:54 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.2) by minotaur.apache.org with SMTP; 31 Jan 2009 16:12:54 -0000 Received: (qmail 72474 invoked by uid 500); 31 Jan 2009 16:12:53 -0000 Delivered-To: apmail-directory-dev-archive@directory.apache.org Received: (qmail 72434 invoked by uid 500); 31 Jan 2009 16:12:53 -0000 Mailing-List: contact dev-help@directory.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: "Apache Directory Developers List" Delivered-To: mailing list dev@directory.apache.org Received: (qmail 72424 invoked by uid 99); 31 Jan 2009 16:12:53 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Sat, 31 Jan 2009 08:12:52 -0800 X-ASF-Spam-Status: No, hits=2.2 required=10.0 tests=HTML_MESSAGE,SPF_PASS X-Spam-Check-By: apache.org Received-SPF: pass (nike.apache.org: domain of akarasulu@gmail.com designates 209.85.220.15 as permitted sender) Received: from [209.85.220.15] (HELO mail-fx0-f15.google.com) (209.85.220.15) by apache.org (qpsmtpd/0.29) with ESMTP; Sat, 31 Jan 2009 16:12:44 +0000 Received: by fxm8 with SMTP id 8so789060fxm.1 for ; Sat, 31 Jan 2009 08:12:23 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :date:message-id:subject:from:to:content-type; bh=PS10GLSNfw4Q7d+DYyonMHr9ZExDCADlnDbfRuuJax0=; b=QJcXi54/i9YPS1qs0s0//sqZ7i9MTJjaA/oMgXnBBHvXpauTfClZ/QHrXEzrDY71Mp MZmqRqhZspRfJS1hVM8+9PZozQPC6OOgOQGYd5pzVi89J/wwfu2UqhAJk2Ls27iWKquT E3cAiUipwgSBAkIUKIeY9bJfBupKY8UddLPLw= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; b=cJKJbA1n6eXaVrg5BtFhSM1Thh7volmx0+qikJ5It+G64hc9j3ha1Ql9wdeg2r/GrO J8faUn2OtUunF5vp244PEyVwQFaWD6oO9+McJy+LQ/vfpR6ZLGzm6L/iwWoH1mxG6Rc2 Eya24MKYeJxdvBlsup6Pgso3uNAvb2ZlLaB4k= MIME-Version: 1.0 Received: by 10.223.116.205 with SMTP id n13mr1097509faq.103.1233418343837; Sat, 31 Jan 2009 08:12:23 -0800 (PST) In-Reply-To: <4984270D.4070900@nextury.com> References: <4984270D.4070900@nextury.com> Date: Sat, 31 Jan 2009 11:12:23 -0500 Message-ID: Subject: Re: [ApacheDS] Implementing isolation using multi-version concurrency control (MVCC) From: Alex Karasulu To: Apache Directory Developers List Content-Type: multipart/alternative; boundary=001636c5a4903e6fd60461c996d6 X-Virus-Checked: Checked by ClamAV on apache.org --001636c5a4903e6fd60461c996d6 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit On Sat, Jan 31, 2009 at 5:25 AM, Emmanuel Lecharny wrote: > Alex Karasulu wrote: > >> 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. >> >> > Atomicity and Isolation are both complex to guarantee in a LDAP server. > > If we think about Atomicity, for instance, even if we can guarantee it > somehow for somesimple operation like Modify, Add or Delete, for the ModDN > operation is not that simple. We have to guarantee that all the potential > renames are done - or reverted - as a whole. Yep. I was thinking about this exact example and how the modifyDn operation could potentially change a lot of descendants. > As this operation can impact a big part of the server, and could take > several seconds (minutes, hours, dependening on the number of entries), this > is obviously not trivial. However, moddn operation aren't the most frequent > one. Regarding the most simpler operation (add, delete and modify), I think > we should implement some kind of "transaction" in the backend : the modified > entry has to be tagged as 'under modification' until the backend has updated > correctly the modification (or rollbacked it). Well I'd like to avoid using the partition to implement something like this since it is not a generalized solution. When this capability is pushed into a partition then all implementations will need to implement it their own way. Partitions are already complicated to implement so adding this requirement on top can make it overwhelming. We want people to be able to make partitions for whatever data they want to present through LDAP to create a rich environment for choosing different partitions. For example JDBM offers transactions. We could have piggy backed on this feature to provide ACID properties under JDBM. Their are some quirks though with how JDBM does this but it can be leveraged. I decided a while back while implementing the partition not to do this because I wanted the transaction management to be handled above the partitions. > Then we can untag the entry, and it's available back. How the CL can come > into play here is to be discussed. IMHO, the CL and this 'transaction' will > work hand to hand at some point. > Yes although I don't know how yet I agree that the CL is key here. Perhaps we need to build a transaction manager on top of the CL that handles and tracks these things as well as manages the transactions. The tracking of a transaction context, it's commit, or rollback is all up to a transaction manager. The CL is just there for history and logging and is something the transaction manager uses as a tool to do it's job. > > Regarding isolation, it's a bit more difficult, as a search can already > have sent back some results which could be change by another modify > operation. This is especially the case for a ModDN operation. > >> 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. >> > That does not work for deleted entries, obviously ... > Sure it can work for deletes. You must have wrote this without reading further. Basically according to the change log, any entries with changes after time S when search began are evaluated to see if they should be included or removed from the result set returned by the search operation. You don't just let search produce candidates returning all and forgetting about the changes that occurred after the search began. > > 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. >> >> > Well, I don't think this is the best approach. In any case, a Ldap Search > is considered as a dirty read. We have no way to lock down the modification > on the read entries. So the user has _no_ guarantee that the entry he gets > back will be valid. Usually, it doesn't matter, because the ratio of read vs > writes on a LDAP server is just so big that we consider we don't have > modifications. So we can simply return the latest revision, whatever it is. > Anyway, there is another aspect we have to consider : once the user gets his > entry, and before he uses it, before potentially send it back as a > modification to the server, the very same entry can have been modified in > between. As we don't lock entries, we can't protect the users from such a > case. The point is, the search should be conducted as if it were performed on a snapshot of the DIT at the time the search was issued. Now if you get dirty reads then you can have inconsistent views of the information which is rare yes but possible. The beauty of this approach is that it allows us to search the DIT at an time not just when the search occurred (time S as stated above). This actually allows us to for example to implement a "search in the past" control where the user can conduct a search on the server at an earlier time. This is insanely powerful in terms of being able to have versioned views in the server of information. Say you have some application's configuration in the DIT and you locked the appilcation down to read at some time/rev associated with a release date for the application. So the application pulls it's configs from the DS with this control. Then you continue making changes to the configuration data as you change the application in developement. You can setup and run both the production application and the development application but using different revisions when performing the lookups. The power this provides for configuration management is awesome to say the least. Now I am digressing. > > > > We have to remember here that we are not dealing with bank accounts and > balances, or nuclear plants. Most of the case, we are using a LDAP server to > handle identities. They rarely change, or when they do, it's because the > person owning this identity is changing his own identity - thus limitating > the odds that he is using it at the same time -. Usually, if we think about > authorizations, which are subject to way more changes that identities, we > can't consider it as a continuous flow of modification. Yes yes I think you know that I would know this :-). However we're just thinking about these features. We have to know how much of a bitch it is by going into the details then stepping back and looking at the big picture. Finished reading the digression and I think we've told each other this several times before in the past. I used to think this way a lot but there are several things that have impacted my views. For example we need atomicity period which is a bigger deal with moddn. Also with triggers we need atomicity badly too. These are protocol requirements and there's no arguing with that. To do all this we're going to need a transaction manager that can begin, commit or rollback sets of changes to the DIT. > > > In other words, creations or deletion of entries might be frequent, > modification should be quite rare. In today's day and age directories are being used in a myriad of ways - especially after the identity buzz. I don't think we can be as comfortable generalizing the scenario to expect as much as we used to. > > > I have gathered some stats from some of my clients, and the ration > changes/reads is like 1/5000... I would be interested to get more numbers > here ! > > Last, not least, I consider that if the ratio goes up to something like > 1/100, then it's time to consider using a transactional system, namely, a > RDBMS. Yeah stats are good but we need a lot of them from different industries to understand this picture. > > > > So far, I'm not saying that it's wrong to think about using a MVCC system, > but I'm a bit sceptic about the gain in term of isolation (the I in ACID) it > will offer in our case. > We're doing it somewhat today just not going all the way. This whole versioning facility is the basis for it. I don't think I understand why you're skeptical. I hope to explore how this sense is coming to you because maybe you have a seriously important reason behind it and just are not vocalizing it. Thanks, Alex --001636c5a4903e6fd60461c996d6 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable On Sat, Jan 31, 2009 at 5:25 AM, Emmanuel Lecharny <elecharny@apache.org> w= rote:
Alex Karasulu wrote:
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<= br> and must preserve consistency. Furthermore, one can easily debate the need<= br> 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 no= t
see modifications within scope that occur after the search began. The searc= h
operation in the example can be replaced with any other operation minus all=
unbind, some extended, and all abandon requests.
 
Atomicity and Isolation are both complex to guarantee in a LDAP server.

If we think about Atomicity, for instance, even if we can guarantee it some= how for somesimple operation like Modify, Add or Delete, for the ModDN oper= ation is not that simple. We have to guarantee that all the potential renam= es are done - or reverted - as a whole.

Yep. I was thinking about this exact example and how the modifyDn = operation could potentially change a lot of descendants.
 
As this operation can impact a big part of the server, and could take sever= al seconds (minutes, hours, dependening on the number of entries), this is = obviously not trivial. However, moddn operation aren't the most frequen= t one. Regarding the most simpler operation (add, delete and modify), I thi= nk we should implement some kind of "transaction" in the backend = : the modified entry has to be tagged as 'under modification' until= the backend has updated correctly the modification (or rollbacked it).

Well I'd like to avoid using the partition to implement someth= ing like this since it is not a generalized solution.  When this capab= ility is pushed into a partition then all implementations will need to impl= ement it their own way. Partitions are already complicated to implement so = adding this requirement on top can make it overwhelming.  We want peop= le to be able to make partitions for whatever data they want to present thr= ough LDAP to create a rich environment for choosing different partitions.
For example JDBM offers transactions. We could have piggy backed on thi= s feature to provide ACID properties under JDBM. Their are some quirks thou= gh with how JDBM does this but it can be leveraged.  I decided a while= back while implementing the partition not to do this because I wanted the = transaction management to be handled above the partitions.
 
Then = we can untag the entry, and it's available back. How the CL can come in= to play here is to be discussed. IMHO, the CL and this 'transaction'= ; will work hand to hand at some point.

Yes although I don't know how yet I agree that th= e CL is key here.  Perhaps we need to build a transaction manager on t= op of the CL that handles and tracks these things as well as manages the tr= ansactions. The tracking of a transaction context, it's commit, or roll= back is all up to a transaction manager.  The CL is just there for his= tory and logging and is something the transaction manager uses as a tool to= do it's job.
 

Regarding isolation, it's a bit more difficult, as a search can already= have sent back some results which could be change by another modify operat= ion. This is especially the case for a ModDN operation.

The change log, not only tracks each change, but it allows the directory server to inject the "revisions" attribute into entries. The revi= sions
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.
That does not work for deleted entries, obviously ...
=

Sure it can work for deletes.  You must ha= ve wrote this without reading further.  Basically according to the cha= nge log, any entries with changes after time S when search began are evalua= ted to see if they should be included or removed from the result set return= ed by the search operation.  You don't just let search produce can= didates returning all and forgetting about the changes that occurred after = the search began.
 

 This is best implemented by
conditionally filtering out or injecting candidates with revisions greater<= br> 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 evaluat= e
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<= br> the filter on the patched entry in state S.  This is not so bad becaus= e
there usually are not that many changes taking place at the same time on th= e
same entry: meaning the number of LDIF's to patch on an entry to evalua= te 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<= br> be a snapshot of the DIT. The search results will not be impacted by any concurrent changes.
 
Well, I don't think this is the best approach. In any case, a Ldap Sear= ch is considered as a dirty read. We have no way to lock down the modificat= ion on the read entries. So the user has _no_ guarantee that the entry he g= ets back will be valid. Usually, it doesn't matter, because the ratio o= f read vs writes on a LDAP server is just so big that we consider we don= 9;t have modifications. So we can simply return the latest revision, whatev= er it is. Anyway, there is another aspect we have to consider : once the us= er gets his entry, and before he uses it, before potentially send it back a= s a modification to the server, the very same entry can have been modified = in between. As we don't lock entries, we can't protect the users fr= om such a case.

The point is, the search should be conducted as if it were perform= ed on a snapshot of the DIT at the time the search was issued.  Now if= you get dirty reads then you can have inconsistent views of the informatio= n which is rare yes but possible.

The beauty of this approach is that it allows us to search the DIT at a= n time not just when the search occurred (time S as stated above).  Th= is actually allows us to for example to implement a "search in the pas= t" control where the user can conduct a search on the server at an ear= lier time.  This is insanely powerful in terms of being able to have v= ersioned views in the server of information.  Say you have some applic= ation's configuration in the DIT and you locked the appilcation down to= read at some time/rev associated with a release date for the application.&= nbsp; So the application pulls it's configs from the DS with this contr= ol. Then you continue making changes to the configuration data as you chang= e the application in developement. You can setup and run both the productio= n application and the development application but using different revisions= when performing the lookups. 

The power this provides for configuration management is awesome to say = the least.  Now I am digressing.
 


<digression>
We have to remember here that we are not dealing with bank accounts and bal= ances, or nuclear plants. Most of the case, we are using a LDAP server to h= andle identities. They rarely change, or when they do, it's because the= person owning this identity is changing his own identity - thus limitating= the odds that he is using it at the same time -. Usually, if we think abou= t authorizations, which are subject to way more changes that identities, we= can't consider it as a continuous flow of modification.

Yes yes I think you know that I would know this :-). However we= 9;re just thinking about these features.  We have to know how much of = a bitch it is by going into the details then stepping back and looking at t= he big picture.  Finished reading the digression and I think we've= told each other this several times before in the past.

I used to think this way a lot but there are several things that have i= mpacted my views.  For example we need atomicity period which is a big= ger deal with moddn.  Also with triggers we need atomicity badly too.&= nbsp; These are protocol requirements and there's no arguing with that.= To do all this we're going to need a transaction manager that can begi= n, commit or rollback sets of changes to the DIT.
 


In other words, creations or deletion of entries might be frequent, modific= ation should be quite rare.

In today's day and age= directories are being used in a myriad of ways - especially after the iden= tity buzz. I don't think we can be as comfortable generalizing the scen= ario to expect as much as we used to.
 


I have gathered some stats from some of my clients, and the ration changes/= reads is like 1/5000... I would be interested to get more numbers here !
Last, not least, I consider that if the ratio goes up to something like 1/1= 00, then it's time to consider using a transactional system, namely, a = RDBMS.

Yeah stats are good but we need a lot of them f= rom different industries to understand this picture.
 
<= br> </digression>

So far, I'm not saying that it's wrong to think about using a MVCC = system, but I'm a bit sceptic about the gain in term of isolation (the = I in ACID) it will offer in our case.

We're doing it somewhat today just not going all= the way. This whole versioning facility is the basis for it.  I don&#= 39;t think I understand why you're skeptical. I hope to explore how thi= s sense is coming to you because maybe you have a seriously important reaso= n behind it and just are not vocalizing it.

Thanks,
Alex



--001636c5a4903e6fd60461c996d6--