directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Emmanuel Lecharny <>
Subject [Mitosis] Random thoughts (3)
Date Tue, 20 Jan 2009 22:07:32 GMT
As I can't really code atm, I will continue to forward my public 
transportations thoughts to the ML :)

So my last two mails presented some theorical replication system where 
servers replicates by reverting back to a previous solid state, and 
re-applied the ordered modifications. So far, so good.

What about performances ? They are obviously terrible... If you think 
about a server A on which you have injected 1 million entries, trying to 
replicate with a server B on which a unique entry has been modified. We 
will have to :
- revert the million entries on A
- revert the modification on B
- transmit the million entry from A to B
- transmit the entry from B to A
- order the million and 1 entry on both server
- inject one million and one entry on A and B.

Obviously, we will have to transmit the million entry to B and to apply 
them, but why should we revert and re-apply them on A? This is just a 

How can we improve this ?

We should think about the possible operations on a server. We have three 
kind of operations :
- add an entry
- delete an entry
- modify an entry

The rename/move operation can be seen as a combinaison :
rename = delete + (modification) + add
move = delete + add
move and rename = delete + (modification) + add

(The modification represent the RDN AT which has to be updated)

A modification is a special case, we will deal with it later. So it left 
only 2 operations : add and delete. Let's analyse what can happen when 
two servers are disconnected.

1) some entry are added on A and on B.
If any of those entries are 'colliding' (ie the intersection is not 
empty), we have to manage some conflict. We have two different cases :
- both entries are the same : that's just ok, we just keep the older one.
- entries share the same DN, but have different values : either we keep 
the older one, or we keep the one on the server with a higher priority - 
assuming we have set up some priority -

2) some entries are deleted from A and B.
As both servers were in sync when the deletion started, we just have to 
apply the deletion as they arrive, discarding any error (ie, if we rtry 
to delete an entry which does not exist, that means it has already been 

3) We have a mix of added and deleted entries from A and B.
This is the most complex case. Let's try to clarify it. We will consider 
only two operations done on A and B, op(a) and op(b). We don't really 
care if op(a) is a add or a delete, and about op(b) either.

Suppose that op(a) is done before op(b). What are the different cases ?
a) op(a) is an add, op(b) is an add : see case (1)
b) op(a) is a delete, op(b) is a delete : see case (2)
c) op(a) is an add, op(b) is a delete : the fact that both operations 
has been transmitted for replication means that they were valid. If 
op(a) and op(b) aren't pointing on the same DN, we just apply both 
modification, they will success. If  they are pointing to the same DN, 
then we will :
* on B : do nothing. The entry has already been deleted, as we have 
deleted it ...
* on A : delete the entry.
d) op(a) is a delete, op(b) is an add : This is exactly the same case as 
(c), reverted. Do the same thing, but inverting the servers.

And that's it. Well, pretty much. The only little problem is that we may 
have many other operations impacting the modified entry between op(a) 
and op(b), but we don't care : any other operation don't interact, 
otherwise they will have been treated the way we just dealt with op(a) 
and op(b). What I mean is that we have selected op(a) and op(b) exactly 
as if they were the first conflicting operations.

I'm not 100% sure, but I think this should be the way to deal with 
conflits for add and delete operations.

What about a modification ? I will let it for some more random thoughts, 
as I have around 2h and a half public transportation tomorrow :)

Ok, it's up to you know to tell me if I'm again high in the sky :)

Thanks !

cordialement, regards,
Emmanuel L├ęcharny

View raw message