You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@directory.apache.org by Emmanuel Lecharny <el...@gmail.com> on 2009/01/14 23:54:27 UTC
[Mitosis] Push or pul, plus some random thoughts
Hi guys,
the current implementation of replication, AFAICT, is based on a pull
system. So to speak, each time you modify some entry, a message is sent
to all the replicas, waiting for an ack to be returned.
The main advantage is that we can't be faster: we replicate as soon as
possible.
The main issue is that if a replica is not connected, we will try and
try and try, until the remote server is back.
Here are some ideas I rehashed in the train on my way to office those
last two days...
- We should ask the replicas to register to the other servers using a
LDAP extended request
- then the server will push the modifications in a blocking queue for
each replicas
- the blocking queue is read by a thread and the modifications are
stored in a base, and sent to the replicas using a LDAP request, with a
control (Replication)
- the replica receives the modifications as simple LDAP requests, plus a
control, and deal with those, and send back a Ldap response with a
status, allowing the modification to be removed from the store.
- if the replica is disconnected (for any reason), the server does not
send anymore modifications to the replica, until the replica connects again.
- in this case, we simply restart the thread and send all the pending
modifications found in the store and in the queue to the replica.
There are a few questions I still have to rehash :
- how many threads should we have ? A pool or one thread per replicas ?
- how do we manage the queue and the store ?
- when we reconnect, how do we tell the server which is the last entry
correctly replicated ?
- and also how do we deal with reconnection if the server consider the
replica is still connected ?
wdyt ?
--
--
cordialement, regards,
Emmanuel Lécharny
www.iktek.com
directory.apache.org
Re: [Mitosis] Push or pul, plus some random thoughts
Posted by Martin Alderson <Ma...@salfordsoftware.co.uk>.
> In fact, when reconnecting, the replica should indicate what was the
> latest CSN it received, so the server can push back the modifications
> from this CSN up to the latest local CSN.
> There are two issues with this approach :
> - the deleted entries.
> - if the replica is connected to more than one other server, it will
> receive a hell lot of modifications from all the connected server at
> the same time.
I'm not sure why deleted entries are any different from other modifications here. The delete modification will be sent to the connecting replica where it will be applied.
Having lots of replicas shouldn't be a problem when a downed replica comes back up. The first replica to start replicating to the newly revived replica will acquire a lock - all other replicas will wait until the next replication cycle. This would also become much less of a problem if we don't need a replica to be connected to all other replicas.
> Right now, from the code I can read, the deleted enties are
> "tombstoned". Maybe we can get rid of this, as we also store the
> delete operation into the derby Store at this point.
Yeah, I should have phrased it as "We _have_ tombstone entries but don't _use_ them".
> I rethougt about this and the problem is that we won't be able to
> resync a server disconnected for a too long period, unless we simply
> erase its full base and ask for all the entries. can be costly when
> you have millions of entries ! However, in this very case (let's say
> you keep a one week period modifications), if you get out of this
> window, the best would probably to restore the base from a backup (way
> faster than reinjecting all the entries one by one !), and then resync
> using the modification log.
>
> So the modification log should only contain a limited number of
> modifications, depending on the configured storage period.
>
> In order to get this working, we have to implement a decent DRS too
> (Disaster Recovery System), which is on its way, as it's just a
> specific implementation of the current changelog interceptor (we have
> to store on disk the modifications, but not the reverse modifications,
> as it's done with the ChangeLog mechanism).
Exactly. When a replica comes back up after more than a week's downtime then it would have to be treated as a new replica, with its DIT replaced.
I think Alex mentioned a while back that it would be good to merge the changelog interceptor with the replication system - it seems a waste to have two pieces of code both maintaining modification logs. I'm not sure how close they are though.
It would also be good to have automatic backups as just another replica with certain options (read only, sync'd periodically).
Martin
Re: [Mitosis] Push or pul, plus some random thoughts
Posted by Emmanuel Lecharny <el...@gmail.com>.
On Thu, Jan 15, 2009 at 12:55 PM, Martin Alderson
<Ma...@salfordsoftware.co.uk> wrote:
>> the current implementation of replication, AFAICT, is based on a pull
>> system.
>
> The current system seems more like push than pull to me, in the sense that one replica decides to send modifications to another without being asked for them.
perfectly right.
>
> The process of A (client) replicating modifications to B (server) at the moment is:
>
> 1. A connects to B.
> 2. Periodically, A asks B for its current CSN vector.
> 3a. If A still has enough modifications in its log to bring B up to date: A sends B all the modifications that it has newer than B's CSN vector.
> 3b. If A doesn't have enough modifications in its log to bring B up to date: A sends B all entries in the DIT.
> 4. B applies the incoming modifications.
>
>
> There is a problem that you mention, where B goes down and A just keeps trying to reconnect blindly. It would be nice if the responsibility lay with B to notify all other replicas when it comes back up.
yep. Otherwise, we use the current retry mechanism : a thread tries to
connect to the replica, if it fails, it waits 2 secs, then 4, 8 16, 32
and 60 secs, until it gets a response back.
>
>
>> - how many threads should we have ? A pool or one thread per replicas ?
>
> I would say one thread per replica is OK (I think that's what we have now). Ideally we would have a system where we don't need to be connected to every replica (i.e. if A is connected to B and B is connected to C we don't need A to be connected to C).
>
>
>> The connecting replica could send the last entryCSN received, and then a
>> search can be done on the server for every CSN with a higher CSN. Then
>> you don't need to keep any modification on disk, as they are already
>> stored in the DiT.
>
> This would only be OK if you could guarantee that no new modifications would occur on the reconnecting replica until it has been brought back up to date. I think the current method of just sending the modification logs works better especially when the replica was only disconnected for something like a temporary network glitch.
In fact, when reconnecting, the replica should indicate what was the
latest CSN it received, so the server can push back the modifications
from this CSN up to the latest local CSN.
There are two issues with this approach :
- the deleted entries.
- if the replica is connected to more than one other server, it will
receive a hell lot of modifications from all the connected server at
the same time.
>
> I don't think there's a reason to have a separate list of modification logs for each replica stored in the server - we can just keep the main modification logs around until all replicas have them.
Right. I have overlooked this, I think.
>> The way Mitosis works atm is to keep the deleted entries in the DiT with
>> a added attribute telling if the entry has been deleted, so we keep them
>> in the DiT ( but not available for standard operations) until all the
>> replicas has been updated. So a disconnected replicas which reconnect
>> will get the deleted entry info when it connect back.
>
> As far as I can see mitosis doesn't really use these tombstone entries. A delete operation is stored in the modification logs which are sent to any replica that doesn't have them yet.
Right now, from the code I can read, the deleted enties are
"tombstoned". Maybe we can get rid of this, as we also store the
delete operation into the derby Store at this point.
>
>> How to handle the real deletion is the problem, as we have to keep a
>> state of each replica...
>
> Personally I think we can stop using tombstone entries completely and just rely on the modification logs. The question then is when do we purge the modification logs? At the moment a modification log item is purged after a certain (configurable) amount of time. It perhaps would be nicer if we kept modification log items around while we know other replicas still need them. This would just involve storing the CSN vector for each known replica.
I rethougt about this and the problem is that we won't be able to
resync a server disconnected for a too long period, unless we simply
erase its full base and ask for all the entries. can be costly when
you have millions of entries ! However, in this very case (let's say
you keep a one week period modifications), if you get out of this
window, the best would probably to restore the base from a backup (way
faster than reinjecting all the entries one by one !), and then resync
using the modification log.
So the modification log should only contain a limited number of
modifications, depending on the configured storage period.
In order to get this working, we have to implement a decent DRS too
(Disaster Recovery System), which is on its way, as it's just a
specific implementation of the current changelog interceptor (we have
to store on disk the modifications, but not the reverse modifications,
as it's done with the ChangeLog mechanism).
PS: I will try to sumarize all those ideas on the wiki page later.
Sadly, I'm pretty busy atm, having to sweat for a client :/
Thanks !
--
Regards,
Cordialement,
Emmanuel Lécharny
www.iktek.com
Re: [Mitosis] Push or pul, plus some random thoughts
Posted by Martin Alderson <Ma...@salfordsoftware.co.uk>.
> the current implementation of replication, AFAICT, is based on a pull
> system.
The current system seems more like push than pull to me, in the sense that one replica decides to send modifications to another without being asked for them.
The process of A (client) replicating modifications to B (server) at the moment is:
1. A connects to B.
2. Periodically, A asks B for its current CSN vector.
3a. If A still has enough modifications in its log to bring B up to date: A sends B all the modifications that it has newer than B's CSN vector.
3b. If A doesn't have enough modifications in its log to bring B up to date: A sends B all entries in the DIT.
4. B applies the incoming modifications.
There is a problem that you mention, where B goes down and A just keeps trying to reconnect blindly. It would be nice if the responsibility lay with B to notify all other replicas when it comes back up.
> - how many threads should we have ? A pool or one thread per replicas ?
I would say one thread per replica is OK (I think that's what we have now). Ideally we would have a system where we don't need to be connected to every replica (i.e. if A is connected to B and B is connected to C we don't need A to be connected to C).
> The connecting replica could send the last entryCSN received, and then a
> search can be done on the server for every CSN with a higher CSN. Then
> you don't need to keep any modification on disk, as they are already
> stored in the DiT.
This would only be OK if you could guarantee that no new modifications would occur on the reconnecting replica until it has been brought back up to date. I think the current method of just sending the modification logs works better especially when the replica was only disconnected for something like a temporary network glitch.
I don't think there's a reason to have a separate list of modification logs for each replica stored in the server - we can just keep the main modification logs around until all replicas have them.
> The way Mitosis works atm is to keep the deleted entries in the DiT with
> a added attribute telling if the entry has been deleted, so we keep them
> in the DiT ( but not available for standard operations) until all the
> replicas has been updated. So a disconnected replicas which reconnect
> will get the deleted entry info when it connect back.
As far as I can see mitosis doesn't really use these tombstone entries. A delete operation is stored in the modification logs which are sent to any replica that doesn't have them yet.
> How to handle the real deletion is the problem, as we have to keep a
> state of each replica...
Personally I think we can stop using tombstone entries completely and just rely on the modification logs. The question then is when do we purge the modification logs? At the moment a modification log item is purged after a certain (configurable) amount of time. It perhaps would be nicer if we kept modification log items around while we know other replicas still need them. This would just involve storing the CSN vector for each known replica.
Martin
Re: [Mitosis] Push or pul, plus some random thoughts
Posted by Howard Chu <hy...@symas.com>.
Emmanuel Lecharny wrote:
> Quanah Gibson-Mount wrote:
>> --On Thursday, January 15, 2009 1:28 AM +0100 Emmanuel Lecharny
>> <el...@gmail.com> wrote:
>>
>>
>>> The queue will be limited in size, obviously. I can even be empty, all
>>> the modification being stored on disk.
>>>
>>> However, we don't necessarily have to keep a track of pending modify for
>>> disconnect replicas, as it's easy to know which entries has not been
>>> replicated since the last time the replica was on. The connecting
>>> replica
>>> could send the last entryCSN received, and then a search can be done on
>>> the server for every CSN with a higher CSN. Then you don't need to keep
>>> any modification on disk, as they are already stored in the DiT.
>> Sounds a lot like syncrepl. ;)
> yeah, this is what I realized :)
>> That search doesn't sound like it handles deletes though, which is
>> always a PITA.
> it does. Any modification done somewhere which might impact the elements
> you are supposed to get back from this persistent search will be send
> back to the recipient. The way Mitosis works atm is to keep the deleted
> entries in the DiT with a added attribute telling if the entry has been
> deleted, so we keep them in the DiT ( but not available for standard
> operations) until all the replicas has been updated. So a disconnected
> replicas which reconnect will get the deleted entry info when it connect
> back.
Tombstones. Yuck. If you're leaving the entry in the DIT, what do you do if an
entry with the same DN is added again? Just resurrect the deleted entry and
replace its values with the newly added attributes? Will anyone care if a
replica never sees the delete, in this case?
> How to handle the real deletion is the problem, as we have to keep a
> state of each replica...
Don't leave the tombstone in the original location, move it to a reserved area
of the DIT. That will make housekeeping a lot simpler later; you can just
purge entries older than X under that particular branch rather than having to
search the entire DIT for cleanup targets.
--
-- Howard Chu
CTO, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/
Re: [Mitosis] Push or pul, plus some random thoughts
Posted by Emmanuel Lecharny <el...@gmail.com>.
Quanah Gibson-Mount wrote:
> --On Thursday, January 15, 2009 1:28 AM +0100 Emmanuel Lecharny
> <el...@gmail.com> wrote:
>
>
>> The queue will be limited in size, obviously. I can even be empty, all
>> the modification being stored on disk.
>>
>> However, we don't necessarily have to keep a track of pending modify for
>> disconnect replicas, as it's easy to know which entries has not been
>> replicated since the last time the replica was on. The connecting
>> replica
>> could send the last entryCSN received, and then a search can be done on
>> the server for every CSN with a higher CSN. Then you don't need to keep
>> any modification on disk, as they are already stored in the DiT.
>
> Sounds a lot like syncrepl. ;)
yeah, this is what I realized :)
>
> That search doesn't sound like it handles deletes though, which is
> always a PITA.
it does. Any modification done somewhere which might impact the elements
you are supposed to get back from this persistent search will be send
back to the recipient. The way Mitosis works atm is to keep the deleted
entries in the DiT with a added attribute telling if the entry has been
deleted, so we keep them in the DiT ( but not available for standard
operations) until all the replicas has been updated. So a disconnected
replicas which reconnect will get the deleted entry info when it connect
back.
How to handle the real deletion is the problem, as we have to keep a
state of each replica...
--
--
cordialement, regards,
Emmanuel Lécharny
www.iktek.com
directory.apache.org
Re: [Mitosis] Push or pul, plus some random thoughts
Posted by Quanah Gibson-Mount <qu...@zimbra.com>.
--On Thursday, January 15, 2009 1:28 AM +0100 Emmanuel Lecharny
<el...@gmail.com> wrote:
> The queue will be limited in size, obviously. I can even be empty, all
> the modification being stored on disk.
>
> However, we don't necessarily have to keep a track of pending modify for
> disconnect replicas, as it's easy to know which entries has not been
> replicated since the last time the replica was on. The connecting replica
> could send the last entryCSN received, and then a search can be done on
> the server for every CSN with a higher CSN. Then you don't need to keep
> any modification on disk, as they are already stored in the DiT.
Sounds a lot like syncrepl. ;)
That search doesn't sound like it handles deletes though, which is always a
PITA.
--Quanah
--
Quanah Gibson-Mount
Principal Software Engineer
Zimbra, Inc
--------------------
Zimbra :: the leader in open source messaging and collaboration
Re: [Mitosis] Push or pul, plus some random thoughts
Posted by Emmanuel Lecharny <el...@gmail.com>.
Howard Chu wrote:
> Emmanuel Lecharny wrote:
>> Hi guys,
>>
>> the current implementation of replication, AFAICT, is based on a pull
>> system. So to speak, each time you modify some entry, a message is sent
>> to all the replicas, waiting for an ack to be returned.
>>
>> The main advantage is that we can't be faster: we replicate as soon as
>> possible.
>>
>> The main issue is that if a replica is not connected, we will try and
>> try and try, until the remote server is back.
>
> That can become a serious PITA; it certainly was with OpenLDAP slurpd.
It is already a PITA for Mitosis ;)
>
>> Here are some ideas I rehashed in the train on my way to office those
>> last two days...
>>
>> - We should ask the replicas to register to the other servers using a
>> LDAP extended request
>> - then the server will push the modifications in a blocking queue for
>> each replicas
>> - the blocking queue is read by a thread and the modifications are
>> stored in a base, and sent to the replicas using a LDAP request, with a
>> control (Replication)
>> - the replica receives the modifications as simple LDAP requests, plus a
>> control, and deal with those, and send back a Ldap response with a
>> status, allowing the modification to be removed from the store.
>> - if the replica is disconnected (for any reason), the server does not
>> send anymore modifications to the replica, until the replica connects
>> again.
>> - in this case, we simply restart the thread and send all the pending
>> modifications found in the store and in the queue to the replica.
>
> Likewise, a queue of pending mods can become a serious PITA if the
> replica is offline for a long time.
The queue will be limited in size, obviously. I can even be empty, all
the modification being stored on disk.
However, we don't necessarily have to keep a track of pending modify for
disconnect replicas, as it's easy to know which entries has not been
replicated since the last time the replica was on. The connecting
replica could send the last entryCSN received, and then a search can be
done on the server for every CSN with a higher CSN. Then you don't need
to keep any modification on disk, as they are already stored in the DiT.
>
> See section 17.2.4.1 "Replacing Slurpd" here
> http://www.openldap.org/doc/admin24/replication.html
Damn, _know_, I see that my previous sentence is exactly what OpenLDAP
does... Either I'm a smart guy, or -more probably - I already read this
page and it remains somewhere in my fuzzy memory :)
I have to get some sleep, and start reading more instead of reinventing
the wheel, I guess :).
Thanks Howard !
--
--
cordialement, regards,
Emmanuel Lécharny
www.iktek.com
directory.apache.org
Re: [Mitosis] Push or pul, plus some random thoughts
Posted by Howard Chu <hy...@symas.com>.
Emmanuel Lecharny wrote:
> Hi guys,
>
> the current implementation of replication, AFAICT, is based on a pull
> system. So to speak, each time you modify some entry, a message is sent
> to all the replicas, waiting for an ack to be returned.
>
> The main advantage is that we can't be faster: we replicate as soon as
> possible.
>
> The main issue is that if a replica is not connected, we will try and
> try and try, until the remote server is back.
That can become a serious PITA; it certainly was with OpenLDAP slurpd.
> Here are some ideas I rehashed in the train on my way to office those
> last two days...
>
> - We should ask the replicas to register to the other servers using a
> LDAP extended request
> - then the server will push the modifications in a blocking queue for
> each replicas
> - the blocking queue is read by a thread and the modifications are
> stored in a base, and sent to the replicas using a LDAP request, with a
> control (Replication)
> - the replica receives the modifications as simple LDAP requests, plus a
> control, and deal with those, and send back a Ldap response with a
> status, allowing the modification to be removed from the store.
> - if the replica is disconnected (for any reason), the server does not
> send anymore modifications to the replica, until the replica connects again.
> - in this case, we simply restart the thread and send all the pending
> modifications found in the store and in the queue to the replica.
Likewise, a queue of pending mods can become a serious PITA if the replica is
offline for a long time.
See section 17.2.4.1 "Replacing Slurpd" here
http://www.openldap.org/doc/admin24/replication.html
for some of those issues. IME, a replication mechanism that requires the
provider to maintain per-replica state will not scale.
> There are a few questions I still have to rehash :
> - how many threads should we have ? A pool or one thread per replicas ?
> - how do we manage the queue and the store ?
> - when we reconnect, how do we tell the server which is the last entry
> correctly replicated ?
> - and also how do we deal with reconnection if the server consider the
> replica is still connected ?
>
> wdyt ?
--
-- Howard Chu
CTO, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/