You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@directory.apache.org by Martin Alderson <eq...@planetquake.com> on 2007/11/23 00:19:15 UTC

[ApacheDS][Mitosis] Replication data

Hi all,

I am currently looking into some of the replication issues, specifically 
DIRSERVER-894 ("Older concurrent changes are never replicated"), 
DIRSERVER-1097 ("Only send net changes during replication") and 
DIRSERVER-1101 ("New replicas may never receive some recent modifications").

I think these issues will require changing the replication data format. 
  Currently the replication logs are stored in a single database table 
with time, replica ID, sequence number and operation columns.  The first 
3 comprise the CSN and the last is for a serialised operation object.

DIRSERVER-894 needs a way to work out the CSN at the point a specific 
attribute was last modified.  DIRSERVER-1097 needs a way to find 
previous log entries based on entryUUID, modification type and attribute 
ID.  We are also planning on moving the replication data to the DIT. 
Given all this I am thinking of removing the serialised operation blob 
and replacing it with extra table(s) for each operation type storing the 
operation's data across multiple columns.  This will allow us to 
efficiently query the replication logs based on the operation data.

Perhaps this would be a good time to make the jump to storing the 
replication data in the DIT.  It seems that that would be well suited to 
storing the operations in an "exploded" format.  I am thinking of the 
following kind of format:

ou=logs/
   cn=<csn>/
       objectClass: ... (indicates operation type)
       time: ...
       replicaID: ...
       operationSequence: ...
       entryUUID: ...
       attributeID: <attributeName> (for attribute modifications)
       cn=attributes/
         <attributeName>: <attributeValues>

The biggest concern I have for this is the inflexibility of LDAP 
searches.  Do we have a sort control in ApacheDS?  Also, if we have the 
attributes for the operation in a child entry how can we find an 
operation in the logs based on those attributes.

At the same time I am thinking about a couple of things in the 
replication system that don't seem to be necessary.

Firstly, once DIRSERVER-894 is fixed, I don't think we will need the 
entryCSN attribute.  I believe that it is only used to check whether an 
operation should be applied to an entry or not (i.e. is it a new 
modification), but this is broken and we need to check the CSN per 
attribute by using the logs instead.

Secondly, I don't really see the point of "tombstoning" entries (marking 
them as deleted instead of really deleting them).  The only time I can 
see it having any kind of effect is when a replica receives a 
modification for an entry it thinks has been deleted - then it will 
resurrect it.  This seems like a very bad idea to me.  I would expect 
this to be a fatal replication error as something has gone seriously wrong.

Sorry for the long email... if anyone's managed to read this far any 
comments would be much appreciated.

Thanks,

Martin

Re: [ApacheDS][Mitosis] Replication data

Posted by Howard Chu <hy...@symas.com>.
Howard Chu wrote:
> Martin Alderson wrote:
>> So do you OpenLDAP guys store the changes in LDAP as entries?  If not,
>> do you wrap your backend changelog store with an LDAP interface as Alex
>> is suggesting?

I didn't fully answer this question... Our log is implemented by an overlay; 
as such it can be instantiated on top of any LDAP backend and targeted to any 
other LDAP backend. Normally it is targeted at a separate local database but 
that's not a requirement; e.g. you can point it at back-ldap instead of 
back-bdb if you want to forward log records to some other centralized logging 
machine.

> Yes we store changes as LDAP entries; that's why I keep pointing you guys at
> our Logging schema...
> 
> Here it is again
> http://highlandsun.com/hyc/drafts/draft-chu-ldap-logschema-xx.html


-- 
   -- Howard Chu
   Chief Architect, Symas Corp.  http://www.symas.com
   Director, Highland Sun        http://highlandsun.com/hyc/
   Chief Architect, OpenLDAP     http://www.openldap.org/project/

Re: [ApacheDS][Mitosis] Replication data

Posted by Howard Chu <hy...@symas.com>.
Martin Alderson wrote:
> Howard Chu wrote:
>> As Kurt used to remind me, a CSN is a Change Sequence Number, but it
>> is not a Commit Sequence Number. The order in which you see CSNs
>> isn't necessarily the order in which those changes were committed in
>> the DB. As such, the syncrepl protocol assumes that the changes it
>> receives are in random order.
> 
> I'm not sure I see the difference.  I thought CSN's were used to
> determine the order in which changes occurred.  The changes would need
> to be committed in the same order unless they were totally unrelated.
> 
> In ApacheDS we are currently committing the changes as soon as they are
> received.

Yes, assuming one change was received after the previous one was committed, 
then the order of those two changes would be perfectly sequential. But in a 
multi-threaded environment with many clients submitting unrelated changes, 
there's no guarantee that they get committed to disk in the same order the 
server received them.

>>> Also, if we have the attributes in a child entry of the actual log
>>> entry as I suggested we would need to specify a parent-child
>>> relationship in the search.
>> That sounds like a painful model to implement.
> 
> Painful because there is no way to specify a parent-child relationship
> in an LDAP search, yes.  I could probably flatten it into a single entry
> for each change, though.
> 
> So do you OpenLDAP guys store the changes in LDAP as entries?  If not,
> do you wrap your backend changelog store with an LDAP interface as Alex
> is suggesting?

Yes we store changes as LDAP entries; that's why I keep pointing you guys at 
our Logging schema...

Here it is again
http://highlandsun.com/hyc/drafts/draft-chu-ldap-logschema-xx.html
-- 
   -- Howard Chu
   Chief Architect, Symas Corp.  http://www.symas.com
   Director, Highland Sun        http://highlandsun.com/hyc/
   Chief Architect, OpenLDAP     http://www.openldap.org/project/

Re: [ApacheDS][Mitosis] Replication data

Posted by Martin Alderson <eq...@planetquake.com>.
Howard Chu wrote:
> As Kurt used to remind me, a CSN is a Change Sequence Number, but it 
> is not a Commit Sequence Number. The order in which you see CSNs 
> isn't necessarily the order in which those changes were committed in 
> the DB. As such, the syncrepl protocol assumes that the changes it 
> receives are in random order.

I'm not sure I see the difference.  I thought CSN's were used to
determine the order in which changes occurred.  The changes would need
to be committed in the same order unless they were totally unrelated.

In ApacheDS we are currently committing the changes as soon as they are
received.

>> Currently we also find the current CSN vector by just getting the 
>> most recent log
> Hm, we only search for that at startup time; at runtime it's always 
> maintained in memory.

Yeah, we probably should be doing that for efficiency's sake.  It's
still something we need to search for at some point though, unless we go
storing it in some other place.

>> Also, if we have the attributes in a child entry of the actual log 
>> entry as I suggested we would need to specify a parent-child 
>> relationship in the search.
> That sounds like a painful model to implement.

Painful because there is no way to specify a parent-child relationship
in an LDAP search, yes.  I could probably flatten it into a single entry
for each change, though.

So do you OpenLDAP guys store the changes in LDAP as entries?  If not,
do you wrap your backend changelog store with an LDAP interface as Alex
is suggesting?



Alex Karasulu wrote:
> I probably did not express myself well enough the last time.  I'm 
> 100% for accessing the replication logs via LDAP and that's why we 
> would wrap this store with a Partition.  I think by "stored in LDAP" 
> you mean storing the logs in the JDBM partition implementation right?

Yep.  I had assumed that that was the aim before I started this thread. 
  I hadn't thought about the possibility of just wrapping the custom 
store in an LDAP interface.

>> My main reasons for suggesting storing the logs in LDAP are: 1. So 
>> we can have optional attributes in each log entry.  This is needed 
>> when we "explode" the current message blob so it can be queried 
>> efficiently.  With JDBM I guess we would have to specify a new 
>> table for each type of message.
> Oh I see you want to query the log looking for specific attributes by
> name?

Exactly.  We need this to fix 
https://issues.apache.org/jira/browse/DIRSERVER-894.

> Sorry I feel I'm misunderstanding you :(.
> 
> Are you suggesting using the directoryService handle you get in the 
> ReplicationInterceptor.init() method to perform log store operations 
> against replication log entries in the DIT?

> I guess we can do that sure. I'm guessing you want to use the 
> directoryService and get a JNDI context to use in your 
> ReplicationStore implementation.  So your going to define a 
> replication log schema, implement an JNDI based ReplicationStore 
> implementation?

Yes, that was the idea.

> Oh BTW the reasons why I wanted to write a custom store was because 
> the rep log store is simple and requires primitive searches.  I did 
> not want to add code reentering the interceptor chain again as well 
> for writes but we have bypass operations to ignore replication.

As you say, we could completely bypass the interceptor chain for storing 
the logs in the DIT.  Also, the replication log store has to become more 
complex to fix certain issues (in an efficient way) - that's what 
triggered my current thought path.

Martin

Re: [ApacheDS][Mitosis] Replication data

Posted by Alex Karasulu <ak...@apache.org>.
Hi Martin,

On Dec 5, 2007 7:00 PM, Martin Alderson <eq...@planetquake.com> wrote:

>
> Thanks for the responses, all.
>
> Apologies for the delay in getting back to you - having a family problem
> at the moment so have very little spare time.
>

No problem hope all is well.


> I thought having the replication logs stored in LDAP sounded nice - for
> new replicas we have to send all replicatable entries but after that the
> log LDAP entries can be sent instead.  It would be pretty much the same
> code logic and it just seemed to solve all the problems with a large
> amount of code re-use.  I was worried about possible performance hits
> though and it sounds like you (Alex) don't want to store the logs in
> LDAP for the same reason.
>

I probably did not express myself well enough the last time.  I'm 100% for
accessing the replication logs via LDAP and that's why we would wrap this
store with a Partition.  I think by "stored in LDAP" you mean storing the
logs in the JDBM partition implementation right?

We can store it in there and it will still be efficient but not as efficient
as building a custom store for it.  We could at this point customize the
JDBM store so it performs pretty close to a custom implementation.  However
consider the overheads that are built in like dealing with aliases etc and a
full fledged search capability.  There will be a latency cost for that.  But
for starters why not just use the JDBM partition and we can optimize
later.   I may also be over doing it here so please feel free to slap some
reality into me.

Really though a custom partition would not be that hard to implement
especially if we reused some existing code from the jdbm partition.


> My main reasons for suggesting storing the logs in LDAP are:
> 1. So we can have optional attributes in each log entry.  This is needed
> when we "explode" the current message blob so it can be queried
> efficiently.  With JDBM I guess we would have to specify a new table for
> each type of message.


Oh I see you want to query the log looking for specific attributes by name?


> 2. To reduce the code complexity.  We would have virtually the same code
> for sending whole entries as sending the logs and we would have less
> code for dealing with the data storage in general.
> 3. To reduce the current tight coupling with the backend database.  By
> using LDAP as the abstraction layer we could leverage ApacheDS' existing
> mechanism for specifying the data store.
> 4. To allow an easy way to view the logs.
> 5. It seems to be the most natural fit.  Since we need to store (part
> of) an LDAP entry in the logs, why not store it in LDAP?
>
> I'll take another stab at explaining that: we already have code to store
> LDAP entries in a database, so why would we want to write that again?
>

Sorry I feel I'm misunderstanding you :(.

Are you suggesting using the directoryService handle you get in the
ReplicationInterceptor.init() method to perform log store operations against
replication log entries in the DIT?

I guess we can do that sure. I'm guessing you want to use the
directoryService and get a JNDI context to use in your ReplicationStore
implementation.  So your going to define a replication log schema, implement
an JNDI based ReplicationStore implementation?

Oh BTW the reasons why I wanted to write a custom store was because the rep
log store is simple and requires primitive searches.  I did not want to add
code reentering the interceptor chain again as well for writes but we have
bypass operations to ignore replication.  I was thinking the store can then
be exposed as a read-only partition if we write a simple partition wrapper
for it.


>
>  > Oh this reminds me that we also need to make sure we're generating
>  > UUIDs all the time even if replication is not enabled.
>
> Yeah, we have a JIRA about this:
> https://issues.apache.org/jira/browse/DIRSERVER-776
>
>
Yeah a while back.  Still not resolved and the tombstoning is creating
complications.

...


>  > For example you have a delete of a node occur right when you add a
>  > child to it.  The server would probably put the child into some
>  > lost and found area and alert the administrator.  With tombstoning
>  > you can easily resuscitate the deleted parent and move the child
>  > back under it.
>
> Resuscitating a deleted entry seems like something most people wouldn't
> want.


Maybe I don't know.


> If we are attempting to simulate a single server as much as
> possible (which is my main aim)


Yeah that should be our main goal as is cited several times in the
literature.


> then the new child entry should be
> deleted when the peers synchronise.  As you said, we could have an
> optional lost and found area for cases where conflict resolution causes
> data loss like this, along with optional notifications to an
> administrator.
>

Exactly that's the only reason for this lost and found area: to recover data
which is lost due to automatic conflict resolution.


>
>  >> Also our MMR support is still immature, we don't yet do value-level
>  >> conflict resolution.
>  > Yeash we have yet to consider that.
>
> We will have this once I have fixed
> https://issues.apache.org/jira/browse/DIRSERVER-894.
>
>
Excellent.

Alex

Re: [ApacheDS][Mitosis] Replication data

Posted by Howard Chu <hy...@symas.com>.
Martin Alderson wrote:
> Thanks for the responses, all.
> 
> Apologies for the delay in getting back to you - having a family problem
> at the moment so have very little spare time.
> 
> I thought having the replication logs stored in LDAP sounded nice - for
> new replicas we have to send all replicatable entries but after that the
> log LDAP entries can be sent instead.  It would be pretty much the same
> code logic and it just seemed to solve all the problems with a large
> amount of code re-use.  I was worried about possible performance hits
> though and it sounds like you (Alex) don't want to store the logs in
> LDAP for the same reason.

That all makes sense. That's the rationale behind the OpenLDAP accesslog 
overlay, which implements our logging schema.

> My main reasons for suggesting storing the logs in LDAP are:
> 1. So we can have optional attributes in each log entry.  This is needed
> when we "explode" the current message blob so it can be queried
> efficiently.  With JDBM I guess we would have to specify a new table for
> each type of message.

The logging schema format we use is already efficiently searchable.

> 2. To reduce the code complexity.  We would have virtually the same code
> for sending whole entries as sending the logs and we would have less
> code for dealing with the data storage in general.
> 3. To reduce the current tight coupling with the backend database.  By
> using LDAP as the abstraction layer we could leverage ApacheDS' existing
> mechanism for specifying the data store.
> 4. To allow an easy way to view the logs.
> 5. It seems to be the most natural fit.  Since we need to store (part
> of) an LDAP entry in the logs, why not store it in LDAP?

> I'll take another stab at explaining that: we already have code to store
> LDAP entries in a database, so why would we want to write that again?

Yes to all of the above.

>  >> The biggest concern I have for this is the inflexibility of LDAP
>  >> searches. Do we have a sort control in ApacheDS?
>  > What types of searches do you envision performing, for which LDAP
>  > is too inflexible? OpenLDAP's syncrepl can be pretty much entirely
>  > mapped onto plain search operations. We gain a lot of versatility
>  > by keeping things generic.
> 
> We need to search for log entries beyond a certain CSN and have the
> results ordered based on CSN.  I guess if the results are always
> returned in creation date order then it might not be an issue (I'm not
> yet sure what ApacheDS does or what the LDAP standard says).

As Kurt used to remind me, a CSN is a Change Sequence Number, but it is not a 
Commit Sequence Number. The order in which you see CSNs isn't necessarily the 
order in which those changes were committed in the DB. As such, the syncrepl 
protocol assumes that the changes it receives are in random order. That means 
we can't update our replication state upon every entry received. So 
incremental refreshes can only update the replica state once the refresh has 
completed, at which point we record the greatest CSN we saw. (This also means 
that if a refresh is interrupted, it starts over from the exact same starting 
point on the next retry. The syncrepl consumer does comparisons to discard any 
received updates that it has seen before.)

> Currently
> we also find the current CSN vector by just getting the most recent log
> - we do this by performing a search with inverted sort by CSN and 1
> result maximum.

Hm, we only search for that at startup time; at runtime it's always maintained 
in memory.

> Also, if we have the attributes in a child entry of the
> actual log entry as I suggested we would need to specify a parent-child
> relationship in the search.

That sounds like a painful model to implement.

>  >> Also our MMR support is still immature, we don't yet do value-level
>  >> conflict resolution.
>  > Yeash we have yet to consider that.
> 
> We will have this once I have fixed
> https://issues.apache.org/jira/browse/DIRSERVER-894.
> 
> 
>  > The trick to get from basic single-master to basic (entry-level
>  > only) multi-master is just to store multiple contextCSNs - one for
>  > each peer master, and ignore entry updates that are older than an
>  > entry's current entryCSN. The other requirement here is that you
>  > have reliable, tightly synced clocks, otherwise the conflict
>  > resolution policy falls apart.
> 
> That's exactly how our replication module works at the moment except we
> just send the changes rather than the whole entry.  I am currently
> looking at improving the way we store the logs so we can efficiently do
> attribute value level conflict resolution.  I suspect that I will end up
> with something very similar to delta-syncrepl.  I will try and dig out
> some information on that from the openldap mailing list.

Yeah, the stuff Emmanuel pointed me at indicated that your approach is already 
very similar to syncrepl.

-- 
   -- Howard Chu
   Chief Architect, Symas Corp.  http://www.symas.com
   Director, Highland Sun        http://highlandsun.com/hyc/
   Chief Architect, OpenLDAP     http://www.openldap.org/project/

Re: [ApacheDS][Mitosis] Replication data

Posted by Martin Alderson <eq...@planetquake.com>.
Thanks for the responses, all.

Apologies for the delay in getting back to you - having a family problem 
at the moment so have very little spare time.

I thought having the replication logs stored in LDAP sounded nice - for 
new replicas we have to send all replicatable entries but after that the 
log LDAP entries can be sent instead.  It would be pretty much the same 
code logic and it just seemed to solve all the problems with a large 
amount of code re-use.  I was worried about possible performance hits 
though and it sounds like you (Alex) don't want to store the logs in 
LDAP for the same reason.

My main reasons for suggesting storing the logs in LDAP are:
1. So we can have optional attributes in each log entry.  This is needed 
when we "explode" the current message blob so it can be queried 
efficiently.  With JDBM I guess we would have to specify a new table for 
each type of message.
2. To reduce the code complexity.  We would have virtually the same code 
for sending whole entries as sending the logs and we would have less 
code for dealing with the data storage in general.
3. To reduce the current tight coupling with the backend database.  By 
using LDAP as the abstraction layer we could leverage ApacheDS' existing 
mechanism for specifying the data store.
4. To allow an easy way to view the logs.
5. It seems to be the most natural fit.  Since we need to store (part 
of) an LDAP entry in the logs, why not store it in LDAP?

I'll take another stab at explaining that: we already have code to store 
LDAP entries in a database, so why would we want to write that again?


 > Oh this reminds me that we also need to make sure we're generating
 > UUIDs all the time even if replication is not enabled.

Yeah, we have a JIRA about this: 
https://issues.apache.org/jira/browse/DIRSERVER-776


 >> The biggest concern I have for this is the inflexibility of LDAP
 >> searches. Do we have a sort control in ApacheDS?
 > What types of searches do you envision performing, for which LDAP
 > is too inflexible? OpenLDAP's syncrepl can be pretty much entirely
 > mapped onto plain search operations. We gain a lot of versatility
 > by keeping things generic.

We need to search for log entries beyond a certain CSN and have the 
results ordered based on CSN.  I guess if the results are always 
returned in creation date order then it might not be an issue (I'm not 
yet sure what ApacheDS does or what the LDAP standard says).  Currently 
we also find the current CSN vector by just getting the most recent log 
- we do this by performing a search with inverted sort by CSN and 1 
result maximum.  Also, if we have the attributes in a child entry of the 
actual log entry as I suggested we would need to specify a parent-child 
relationship in the search.


 > Active Directory has a lot of misfeatures... Having spent a couple
 > weeks of "quality time" with it, the flaws just leap out... Do you
 > really like the idea of carrying obsolete info around and needing a
 > sweep task to go thru and clean up periodically?

My thoughts exactly.  I'll try and do some more research here and dig 
out the reason AD uses them, but I think I'll leave that to a separate 
thread.


 > For example you have a delete of a node occur right when you add a
 > child to it.  The server would probably put the child into some
 > lost and found area and alert the administrator.  With tombstoning
 > you can easily resuscitate the deleted parent and move the child
 > back under it.

Resuscitating a deleted entry seems like something most people wouldn't 
want.  If we are attempting to simulate a single server as much as 
possible (which is my main aim) then the new child entry should be 
deleted when the peers synchronise.  As you said, we could have an 
optional lost and found area for cases where conflict resolution causes 
data loss like this, along with optional notifications to an administrator.


 >> Also our MMR support is still immature, we don't yet do value-level
 >> conflict resolution.
 > Yeash we have yet to consider that.

We will have this once I have fixed 
https://issues.apache.org/jira/browse/DIRSERVER-894.


 > The trick to get from basic single-master to basic (entry-level
 > only) multi-master is just to store multiple contextCSNs - one for
 > each peer master, and ignore entry updates that are older than an
 > entry's current entryCSN. The other requirement here is that you
 > have reliable, tightly synced clocks, otherwise the conflict
 > resolution policy falls apart.

That's exactly how our replication module works at the moment except we 
just send the changes rather than the whole entry.  I am currently 
looking at improving the way we store the logs so we can efficiently do 
attribute value level conflict resolution.  I suspect that I will end up 
with something very similar to delta-syncrepl.  I will try and dig out 
some information on that from the openldap mailing list.

Martin


Re: [ApacheDS][Mitosis] Replication data

Posted by Alex Karasulu <ak...@apache.org>.
Hi Howard and Quanah,

Thanks for supplying all this great information on your replication
mechanism. I'm going to need to read all this material and RFC4533 to
educate myself a little bit. I'm really intrigued by how you adapted
syncrepl to do MMR.

Regards,
Alex

On Dec 1, 2007 7:55 PM, Quanah Gibson-Mount <qu...@zimbra.com> wrote:

>
>
> --On December 1, 2007 4:45:51 PM -0800 Howard Chu <hy...@symas.com> wrote:
>
> >> That sounds like a sensible approach. Searching the changelog is the
> >> key. I'd love to get the big picture here and try to make sure we can
> >> replicate between ApacheDS and OpenLDAP. This would be very beneficial
> >> to both user bases.
> >
> > It sounds to me like you already have all of the schema elements in
> place
> > to get RFC4533 implemented. We can work out the delta MMR stuff as a
> > joint project, always good to have someone else to check our
> assumptions.
>
> Also, if you are interested in setting up OpenLDAP with delta-syncrel, I
> documented it on Symas' tech tips at:
>
> <http://www.connexitor.com/forums/viewtopic.php?t=3>
>
>
> It's been my preferred replication mechanism with OpenLDAP, as it is
> significantly less overhead traffic wise as well in a high-write
> environment.
>
> --Quanah
>
> --
>
> Quanah Gibson-Mount
> Principal Software Engineer
> Zimbra, Inc
> --------------------
> Zimbra ::  the leader in open source messaging and collaboration
>

Re: [ApacheDS][Mitosis] Replication data

Posted by Quanah Gibson-Mount <qu...@zimbra.com>.

--On December 1, 2007 4:45:51 PM -0800 Howard Chu <hy...@symas.com> wrote:

>> That sounds like a sensible approach. Searching the changelog is the
>> key. I'd love to get the big picture here and try to make sure we can
>> replicate between ApacheDS and OpenLDAP. This would be very beneficial
>> to both user bases.
>
> It sounds to me like you already have all of the schema elements in place
> to get RFC4533 implemented. We can work out the delta MMR stuff as a
> joint project, always good to have someone else to check our assumptions.

Also, if you are interested in setting up OpenLDAP with delta-syncrel, I 
documented it on Symas' tech tips at:

<http://www.connexitor.com/forums/viewtopic.php?t=3>


It's been my preferred replication mechanism with OpenLDAP, as it is 
significantly less overhead traffic wise as well in a high-write 
environment.

--Quanah

--

Quanah Gibson-Mount
Principal Software Engineer
Zimbra, Inc
--------------------
Zimbra ::  the leader in open source messaging and collaboration

Re: [ApacheDS][Mitosis] Replication data

Posted by Howard Chu <hy...@symas.com>.
Alex Karasulu wrote:
> No. You're absolutely right. Things like that are a hacks. The algorithm 
> needs to make sure these situations are avoided.
> 
> Again I don't know what the best option here is and have seen 
> tombstoning referenced all over papers on replication and having more 
> information while making this decision is the best option. Your thoughts 
> on the matter however do help further my doubts on tombstoning. I want 
> to think about the alternative options for handling specific conflict 
> resolution problems.

> For example you have a delete of a node occur right when you add a child 
> to it. The server would probably put the child into some lost and found 
> area and alert the administrator. With tombstoning you can easily 
> resuscitate the deleted parent and move the child back under it. But 
> then again with a full log you can simply recreate the state of the 
> deleted parent anyway so yes alternatives do exist.

> Tombstoning, incidentally, is a freaking nightmare in the architecture 
> that is to this day causing us much grief and bugs we have yet to 
> realize. So if you have better alternatives I'm all open to it. I just 
> wish I had the 2-years to really read all those ACM and IEEE papers on 
> the topic and attack this better.

I had considered tombstones at one point for syncrepl as well. The motivation 
being, in a syncrepl Refresh we need to see if a consumer's last known CSN is 
still present in the provider's DB. If the last CSN was assigned to a Delete 
operation, then this lookup would fail because there is no entry in the DB 
with that corresponding entryCSN. In this case, the log fulfills the same 
purpose as a tombstone. (Without the log, we simply look for any CSN <= the 
consumer's CSN. If anything older is present in the DB, then we know the 
consumer is not out of date. Otherwise the consumer's state is too old and we 
perform a full resync.)

For the example you cite above, we just create glue entries for missing parent 
entries. We need that capability anyway, and tombstoning doesn't provide the 
equivalent solution, because we support partial and fractional replication. 
(Active Directory only supports full replication.) E.g., if you define your 
replication criteria with a particular search filter, entries can appear and 
disappear from the replication context arbitrarily, without any add/delete 
operations being involved. If you only have tombstone support, you can't 
handle these cases at all.

>     It's fair to say that we've faced the same issues already ;) Also
>     our MMR
>     support is still immature, we don't yet do value-level conflict
>     resolution.
>     But the plan for that is pretty straightforward.
> 
> 
> Yeash we have yet to consider that. If you have a clear idea of how it 
> can be done cheap that's great. Can you point us to some documentation 
> on how you've implemented replication?

Well, RFC4533 gives the syncrepl fundamentals. If you just read RFC4533 you 
can get basic single-master replication working. There's no written 
documentation on how we've implemented MMR on top of it (aside from, perhaps, 
discussions on openldap-devel). In some ways we violate the spirit of the 
spec: a consumer is not supposed to be aware of the contents of the syncrepl 
cookie or ever look inside. In OpenLDAP, we expect the cookie to contain CSNs, 
and we parse them with that expectation. (That's a design decision made before 
I got involved. Don't see a way around it though.)

The trick to get from basic single-master to basic (entry-level only) 
multi-master is just to store multiple contextCSNs - one for each peer master, 
and ignore entry updates that are older than an entry's current entryCSN. The 
other requirement here is that you have reliable, tightly synced clocks, 
otherwise the conflict resolution policy falls apart.

>  > (2) I know OpenLDAP leverages a changelog similar but not exactly the
>  > same as our changelog. Perhaps we need to explore this relationship and
>  > figure out how to better leverage this changelog. I think the CSN is
>  > synonymous with a revision except revisions are local and CSN's are 
> global.
> 
>     Normal syncrepl doesn't rely on any logs; it simply uses entryCSNs. It
>     replicates whole entries (and therefore MMR only provides
>     entry-level conflict
>     resolution). 

> Yeah that's a big problem when several scenarios for attribute and value 
> level conflicts arise. You must be adding to this in your implementation 
> to compensate.

For plain syncrepl, we're not going to enhance this any further. It's entry 
based, and last writer wins. It may not always be "right" from someone's point 
of view but it's trivial to guarantee consistency.

>     It can use a session log to optimize the replication of delete
>     operations, but doesn't actually need that.
> 
>     Delta-syncrepl uses the log schema (which I pointed you at already) to
>     replicate only individual changes. 

> Sorry I have no idea what delta-syncrepl is. Is it an RFC I've missed? 
> Can you give us some references?

There's no RFC specifically for it; it's a natural progression from combining 
the log schema with regular syncrepl. (I like lego-block style design...) 
Since syncrepl only sends whole entries, I use a log whose entries record the 
deltas on some other DB. The syncrepl consumer is configured with two search 
bases, the main DB and the log DB. It always starts up by sending a sync 
search against the log DB; if it's not out of date then it will receive the 
log's entries and parse them into appropriate modify operations. If it *is* 
out of date, the provider will return a "ReloadRequired" result and the 
consumer will try again against the main DB, thus it automatically and 
transparently falls back to normal operation until it catches up again.

So the protocol is pretty much identical to RFC4533, the only difference is 
the content of the entries being transferred.

>     This is the mechanism we'll be extending to
>     provide value-level conflict resolution for MMR. The basic approach
>     is that
>     with every delta received, we also send the entry's old entryCSN. If
>     that
>     doesn't match the entryCSN on the replica, then some other write has
>     occurred
>     and there is a potential conflict. At that point we can search backward
>     through the changelog for that entryUUID or entryCSN and find the
>     point of
>     divergence.

> That sounds like a sensible approach. Searching the changelog is the 
> key. I'd love to get the big picture here and try to make sure we can 
> replicate between ApacheDS and OpenLDAP. This would be very beneficial 
> to both user bases.

It sounds to me like you already have all of the schema elements in place to 
get RFC4533 implemented. We can work out the delta MMR stuff as a joint 
project, always good to have someone else to check our assumptions.
-- 
   -- Howard Chu
   Chief Architect, Symas Corp.  http://www.symas.com
   Director, Highland Sun        http://highlandsun.com/hyc/
   Chief Architect, OpenLDAP     http://www.openldap.org/project/

Re: [ApacheDS][Mitosis] Replication data

Posted by Alex Karasulu <ak...@apache.org>.
On Dec 1, 2007 4:30 PM, Howard Chu <hy...@symas.com> wrote:

> Alex Karasulu wrote:
> >     It seems that that would be well suited to
> >     storing the operations in an "exploded" format. I am thinking of the
> >     following kind of format:
> >
> >     ou=logs/
> >     cn=<csn>/
> >     objectClass: ... (indicates operation type)
> >     time: ...
> >     replicaID: ...
> >     operationSequence: ...
> >     entryUUID: ...
> >     attributeID: <attributeName> (for attribute modifications)
> >     cn=attributes/
> >     <attributeName>: <attributeValues>
> >
> >     The biggest concern I have for this is the inflexibility of LDAP
> >     searches. Do we have a sort control in ApacheDS?
>
> What types of searches do you envision performing, for which LDAP is too
> inflexible? OpenLDAP's syncrepl can be pretty much entirely mapped onto
> plain
> search operations. We gain a lot of versatility by keeping things generic.
>
> >     At the same time I am thinking about a couple of things in the
> >     replication system that don't seem to be necessary.
> >
> >     Firstly, once DIRSERVER-894 is fixed, I don't think we will need the
> >     entryCSN attribute. I believe that it is only used to check whether
> an
> >     operation should be applied to an entry or not (i.e. is it a new
> >     modification), but this is broken and we need to check the CSN per
> >     attribute by using the logs instead.
>
> In some ways the entryCSN is redundant info, but it's still useful for 3rd
> party clients. It's essential for OpenLDAP syncrepl.
>
> > Right no problem if you want to axe it we can do that. Oh this reminds
> > me that we also need to make sure we're generating UUIDs all the time
> > even if replication is not enabled. We want to have the entryUUID as an
> > operational attribute of all entries so when replication is turned
> > things work. We can also use the UUID for many other things.
>
> Yes.
>
> >     Secondly, I don't really see the point of "tombstoning" entries
> >     (marking
> >     them as deleted instead of really deleting them). The only time I
> can
> >     see it having any kind of effect is when a replica receives a
> >     modification for an entry it thinks has been deleted - then it will
> >     resurrect it. This seems like a very bad idea to me. I would expect
> >     this to be a fatal replication error as something has gone seriously
> >     wrong.
> >
> > I've got to admit that I'm not well versed enough on this topic to
> > answer you on this but I do know that it is a valid techique that is
> > widely practiced in replication theory. For example it's used in Active
> > Directory. So I would recommend researching this topic a little bit but
> > I'm open to anything as long as we are educated about it.
>
> Active Directory has a lot of misfeatures... Having spent a couple weeks
> of
> "quality time" with it, the flaws just leap out... Do you really like the
> idea
> of carrying obsolete info around and needing a sweep task to go thru and
> clean
> up periodically?
>

No.  You're absolutely right.  Things like that are a hacks.  The algorithm
needs to make sure these situations are avoided.

Again I don't know what the best option here is and have seen tombstoning
referenced all over papers on replication and having more information while
making this decision is the best option.  Your thoughts on the matter
however do help further my doubts on tombstoning. I want to think about the
alternative options for handling specific conflict resolution problems.

For example you have a delete of a node occur right when you add a child to
it.  The server would probably put the child into some lost and found area
and alert the administrator.  With tombstoning you can easily resuscitate
the deleted parent and move the child back under it.  But then again with a
full log you can simply recreate the state of the deleted parent anyway so
yes alternatives do exist.

Tombstoning, incidentally, is a freaking nightmare in the architecture that
is to this day causing us much grief and bugs we have yet to realize.  So if
you have better alternatives I'm all open to it.  I just wish I had the
2-years to really read all those ACM and IEEE papers on the topic and attack
this better.


>
> >     Sorry for the long email... if anyone's managed to read this far any
> >     comments would be much appreciated.
>
> > Hey it took me a while sorry for that. This is a very important topic
> > that we need to get right. I also have a couple of other points or
> > topics I want to touch on.
>
> > (1) I think it would be really nice to be able to replicate with
> > OpenLDAP and also learn about the sync replication mechanism used.
> > Perhaps they have some nice techniques which we have not thought of yet.
>
> It's fair to say that we've faced the same issues already ;) Also our MMR
> support is still immature, we don't yet do value-level conflict
> resolution.
> But the plan for that is pretty straightforward.
>

Yeash we have yet to consider that.  If you have a clear idea of how it can
be done cheap that's great.  Can you point us to some documentation on how
you've implemented replication?

> (2) I know OpenLDAP leverages a changelog similar but not exactly the
> same as our changelog. Perhaps we need to explore this relationship and
> figure out how to better leverage this changelog. I think the CSN is
> synonymous with a revision except revisions are local and CSN's are
global.

Normal syncrepl doesn't rely on any logs; it simply uses entryCSNs. It
> replicates whole entries (and therefore MMR only provides entry-level
> conflict
> resolution).


Yeah that's a big problem when several scenarios for attribute and value
level conflicts arise. You must be adding to this in your implementation to
compensate.


> It can use a session log to optimize the replication of delete
> operations, but doesn't actually need that.
>
> Delta-syncrepl uses the log schema (which I pointed you at already) to
> replicate only individual changes.


Sorry I have no idea what delta-syncrepl is. Is it an RFC I've missed? Can
you give us some references?


> This is the mechanism we'll be extending to
> provide value-level conflict resolution for MMR. The basic approach is
> that
> with every delta received, we also send the entry's old entryCSN. If that
> doesn't match the entryCSN on the replica, then some other write has
> occurred
> and there is a potential conflict. At that point we can search backward
> through the changelog for that entryUUID or entryCSN and find the point of
> divergence.
>

That sounds like a sensible approach.  Searching the changelog is the key.
I'd love to get the big picture here and try to make sure we can replicate
between ApacheDS and OpenLDAP.  This would be very beneficial to both user
bases.

Thanks Howard!
Alex

Re: [ApacheDS][Mitosis] Replication data

Posted by Howard Chu <hy...@symas.com>.
Alex Karasulu wrote:
>     It seems that that would be well suited to
>     storing the operations in an "exploded" format. I am thinking of the
>     following kind of format:
> 
>     ou=logs/
>     cn=<csn>/
>     objectClass: ... (indicates operation type)
>     time: ...
>     replicaID: ...
>     operationSequence: ...
>     entryUUID: ...
>     attributeID: <attributeName> (for attribute modifications)
>     cn=attributes/
>     <attributeName>: <attributeValues>
> 
>     The biggest concern I have for this is the inflexibility of LDAP
>     searches. Do we have a sort control in ApacheDS? 

What types of searches do you envision performing, for which LDAP is too 
inflexible? OpenLDAP's syncrepl can be pretty much entirely mapped onto plain 
search operations. We gain a lot of versatility by keeping things generic.

>     At the same time I am thinking about a couple of things in the
>     replication system that don't seem to be necessary.
> 
>     Firstly, once DIRSERVER-894 is fixed, I don't think we will need the
>     entryCSN attribute. I believe that it is only used to check whether an
>     operation should be applied to an entry or not (i.e. is it a new
>     modification), but this is broken and we need to check the CSN per
>     attribute by using the logs instead.

In some ways the entryCSN is redundant info, but it's still useful for 3rd 
party clients. It's essential for OpenLDAP syncrepl.

> Right no problem if you want to axe it we can do that. Oh this reminds 
> me that we also need to make sure we're generating UUIDs all the time 
> even if replication is not enabled. We want to have the entryUUID as an 
> operational attribute of all entries so when replication is turned 
> things work. We can also use the UUID for many other things.

Yes.

>     Secondly, I don't really see the point of "tombstoning" entries
>     (marking
>     them as deleted instead of really deleting them). The only time I can
>     see it having any kind of effect is when a replica receives a
>     modification for an entry it thinks has been deleted - then it will
>     resurrect it. This seems like a very bad idea to me. I would expect
>     this to be a fatal replication error as something has gone seriously
>     wrong.
> 
> I've got to admit that I'm not well versed enough on this topic to 
> answer you on this but I do know that it is a valid techique that is 
> widely practiced in replication theory. For example it's used in Active 
> Directory. So I would recommend researching this topic a little bit but 
> I'm open to anything as long as we are educated about it.

Active Directory has a lot of misfeatures... Having spent a couple weeks of 
"quality time" with it, the flaws just leap out... Do you really like the idea 
of carrying obsolete info around and needing a sweep task to go thru and clean 
up periodically?

>     Sorry for the long email... if anyone's managed to read this far any
>     comments would be much appreciated.

> Hey it took me a while sorry for that. This is a very important topic 
> that we need to get right. I also have a couple of other points or 
> topics I want to touch on.

> (1) I think it would be really nice to be able to replicate with 
> OpenLDAP and also learn about the sync replication mechanism used. 
> Perhaps they have some nice techniques which we have not thought of yet.

It's fair to say that we've faced the same issues already ;) Also our MMR 
support is still immature, we don't yet do value-level conflict resolution. 
But the plan for that is pretty straightforward.

> (2) I know OpenLDAP leverages a changelog similar but not exactly the 
> same as our changelog. Perhaps we need to explore this relationship and 
> figure out how to better leverage this changelog. I think the CSN is 
> synonymous with a revision except revisions are local and CSN's are global.

Normal syncrepl doesn't rely on any logs; it simply uses entryCSNs. It 
replicates whole entries (and therefore MMR only provides entry-level conflict 
resolution). It can use a session log to optimize the replication of delete 
operations, but doesn't actually need that.

Delta-syncrepl uses the log schema (which I pointed you at already) to 
replicate only individual changes. This is the mechanism we'll be extending to 
provide value-level conflict resolution for MMR. The basic approach is that 
with every delta received, we also send the entry's old entryCSN. If that 
doesn't match the entryCSN on the replica, then some other write has occurred 
and there is a potential conflict. At that point we can search backward 
through the changelog for that entryUUID or entryCSN and find the point of 
divergence.
-- 
   -- Howard Chu
   Chief Architect, Symas Corp.  http://www.symas.com
   Director, Highland Sun        http://highlandsun.com/hyc/
   Chief Architect, OpenLDAP     http://www.openldap.org/project/

Re: [ApacheDS][Mitosis] Replication data

Posted by Alex Karasulu <ak...@apache.org>.
Hi Martin,

I must first apologize for taking so long to respond to you.  I just wanted
to clear enough time to look into these issues and think properly about
them.

On Nov 22, 2007 6:19 PM, Martin Alderson <eq...@planetquake.com> wrote:

> Hi all,
>
> I am currently looking into some of the replication issues, specifically
> DIRSERVER-894 ("Older concurrent changes are never replicated"),
> DIRSERVER-1097 ("Only send net changes during replication") and
> DIRSERVER-1101 ("New replicas may never receive some recent
> modifications").
>
> I think these issues will require changing the replication data format.
>  Currently the replication logs are stored in a single database table
> with time, replica ID, sequence number and operation columns.  The first
> 3 comprise the CSN and the last is for a serialised operation object.
>
> DIRSERVER-894 needs a way to work out the CSN at the point a specific
> attribute was last modified.  DIRSERVER-1097 needs a way to find
> previous log entries based on entryUUID, modification type and attribute
> ID.  We are also planning on moving the replication data to the DIT.
> Given all this I am thinking of removing the serialised operation blob
> and replacing it with extra table(s) for each operation type storing the
> operation's data across multiple columns.  This will allow us to
> efficiently query the replication logs based on the operation data.
>
> Perhaps this would be a good time to make the jump to storing the
> replication data in the DIT.


Before we think about storing it in the DIT let's think about the most
optimal kind of storage and format possible for this data.  I have a feeling
it might be better to write a custom high capacity store implementation that
answers very specific questions and is highly optimized for them.  I'm
thinking it might be worth writing a custom BTree based store not so much a
partition which is a bit more general.

This store can hard code and optimize the way these questions are
specifically answered using indices. Furthermore we have all the
dependencies we need for this.  Also we can build a partition wrapper around
the store interface mapping that over to the LDAP Namespace.

I know the idea of having yet another non-optional user partition for this
is a bit overkill since we already have the system and schema partitions.
However the issues with this will change when we allow for nestable
partitions and do away with this nexus concept with this issue:

    https://issues.apache.org/jira/browse/DIRSERVER-465

I think this feature will be implemented at some point before 2.0 but until
then we can work on just making a special Partition implementation which
wraps the ReplicationStore interface.  This way any store implementation can
be exposed by the DIT simply by adding the partition to some context in the
DIT.

It seems that that would be well suited to
> storing the operations in an "exploded" format.  I am thinking of the
> following kind of format:
>
> ou=logs/
>   cn=<csn>/
>       objectClass: ... (indicates operation type)
>       time: ...
>       replicaID: ...
>       operationSequence: ...
>       entryUUID: ...
>       attributeID: <attributeName> (for attribute modifications)
>       cn=attributes/
>         <attributeName>: <attributeValues>
>
> The biggest concern I have for this is the inflexibility of LDAP
> searches.  Do we have a sort control in ApacheDS?


Yeah don't worry about that I can make sure we can search efficiently.  I
can talk to you more about your specific search needs.  Just model a solid
JDBC schema that you need to do replication right - we can easily deduce an
LDAP schema for this with the appropriate changes to make the questions you
need answered fast and easy.  But keep in mind you can ask questions through
the store interface as well and don't need to resort to an LDAP interface
but you can do both.

Also, if we have the
> attributes for the operation in a child entry how can we find an
> operation in the logs based on those attributes.
>

I think we can use LDAP backlinks for such associations which is another
feature we're working on.  However we might just want to build the right
store implementation using JDBM and just for now keep in mind how we can
wrap the store interface as a partition to expose this through LDAP.


>
> At the same time I am thinking about a couple of things in the
> replication system that don't seem to be necessary.
>
> Firstly, once DIRSERVER-894 is fixed, I don't think we will need the
> entryCSN attribute.  I believe that it is only used to check whether an
> operation should be applied to an entry or not (i.e. is it a new
> modification), but this is broken and we need to check the CSN per
> attribute by using the logs instead.
>

Right no problem if you want to axe it we can do that.  Oh this reminds me
that we also need to make sure we're generating UUIDs all the time even if
replication is not enabled.  We want to have the entryUUID as an operational
attribute of all entries so when replication is turned things work.  We can
also use the UUID for many other things.

>
> Secondly, I don't really see the point of "tombstoning" entries (marking
> them as deleted instead of really deleting them).  The only time I can
> see it having any kind of effect is when a replica receives a
> modification for an entry it thinks has been deleted - then it will
> resurrect it.  This seems like a very bad idea to me.  I would expect
> this to be a fatal replication error as something has gone seriously
> wrong.
>

I've got to admit that I'm not well versed enough on this topic to answer
you on this but I do know that it is a valid techique that is widely
practiced in replication theory.  For example it's used in Active
Directory.  So I would recommend researching this topic a little bit but I'm
open to anything as long as we are educated about it.


> Sorry for the long email... if anyone's managed to read this far any
> comments would be much appreciated.
>

Hey it took me a while sorry for that.  This is a very important topic that
we need to get right.  I also have a couple of other points or topics I want
to touch on.

(1) I think it would be really nice to be able to replicate with OpenLDAP
and also learn about the sync replication mechanism used.  Perhaps they have
some nice techniques which we have not thought of yet.

(2) I know OpenLDAP leverages a changelog similar but not exactly the same
as our changelog. Perhaps we need to explore this relationship and figure
out how to better leverage this changelog.  I think the CSN is synonymous
with a revision except revisions are local and CSN's are global.

Alex

Re: [ApacheDS][Mitosis] Replication data

Posted by Alex Karasulu <ak...@apache.org>.
Hey Martin,

I just saw this email however I'm out for Thanksgiving (holiday here).
 I'll try to get back to you at some point soon.

Cheers,
Alex

On Nov 22, 2007 6:19 PM, Martin Alderson <eq...@planetquake.com> wrote:
> Hi all,
>
> I am currently looking into some of the replication issues, specifically
> DIRSERVER-894 ("Older concurrent changes are never replicated"),
> DIRSERVER-1097 ("Only send net changes during replication") and
> DIRSERVER-1101 ("New replicas may never receive some recent modifications").
>
> I think these issues will require changing the replication data format.
>   Currently the replication logs are stored in a single database table
> with time, replica ID, sequence number and operation columns.  The first
> 3 comprise the CSN and the last is for a serialised operation object.
>
> DIRSERVER-894 needs a way to work out the CSN at the point a specific
> attribute was last modified.  DIRSERVER-1097 needs a way to find
> previous log entries based on entryUUID, modification type and attribute
> ID.  We are also planning on moving the replication data to the DIT.
> Given all this I am thinking of removing the serialised operation blob
> and replacing it with extra table(s) for each operation type storing the
> operation's data across multiple columns.  This will allow us to
> efficiently query the replication logs based on the operation data.
>
> Perhaps this would be a good time to make the jump to storing the
> replication data in the DIT.  It seems that that would be well suited to
> storing the operations in an "exploded" format.  I am thinking of the
> following kind of format:
>
> ou=logs/
>    cn=<csn>/
>        objectClass: ... (indicates operation type)
>        time: ...
>        replicaID: ...
>        operationSequence: ...
>        entryUUID: ...
>        attributeID: <attributeName> (for attribute modifications)
>        cn=attributes/
>          <attributeName>: <attributeValues>
>
> The biggest concern I have for this is the inflexibility of LDAP
> searches.  Do we have a sort control in ApacheDS?  Also, if we have the
> attributes for the operation in a child entry how can we find an
> operation in the logs based on those attributes.
>
> At the same time I am thinking about a couple of things in the
> replication system that don't seem to be necessary.
>
> Firstly, once DIRSERVER-894 is fixed, I don't think we will need the
> entryCSN attribute.  I believe that it is only used to check whether an
> operation should be applied to an entry or not (i.e. is it a new
> modification), but this is broken and we need to check the CSN per
> attribute by using the logs instead.
>
> Secondly, I don't really see the point of "tombstoning" entries (marking
> them as deleted instead of really deleting them).  The only time I can
> see it having any kind of effect is when a replica receives a
> modification for an entry it thinks has been deleted - then it will
> resurrect it.  This seems like a very bad idea to me.  I would expect
> this to be a fatal replication error as something has gone seriously wrong.
>
> Sorry for the long email... if anyone's managed to read this far any
> comments would be much appreciated.
>
> Thanks,
>
> Martin
>