After having discussed with Alex yesterday about replication, I thought
a bit about what a replication system means, and I came to a point where
we should not consider replication from a server to server perspective,
but as a whole. Ok, know, it's a bit fuzzy. Let me explain what I have
in mind.
First, let's consider that all the servers are connected and replicate
correctly, without any kind of problem (ie, they never get disconnected,
they are all time-synchronized, all operations have their unique
timestamp). In this genuine case, we should consider that the full set
of LDAP server should be seen as a unique LDAP server : everything is
just available from any server, without any difference.
If at least one server get disconnected, the you have split this virtual
big LDAP server in two parts : the disconnected server, and the rest of
them. As they are still all connected, and perfectly synchronized, it's
really like if we have one giant LDAP server again, so we are just
facing two LDAP servers, disconnected.
If we move a bit forward, if M servers get disconnected from a group of
N servers, then we fall back in the same situation : M is seen as a
unique LDAP server, so is N.
One step further, if the set of servers is fragmented in many small
disconnected sets, then each of those sets are seen a unique LDAP server.
Ok, so far so good. Where did it brought us ? I think that replication
per se is just a matter of managing replication between 2 servers, any
other case can fell back to this category.
Now, how do we manage replication between server A and server B
(whatever the number of real servers present in A and B) ? Simple : as
each operation within A or B are done on a globally connected system,
with each operation having its unique timestamp (ie, two operations have
two different timestamps), all the modifications done globally are
ordered. It's just then a matter of re-ordering two lists of ordered
operations on A and B, and to apply them from the oldest operation to
the newest one. Let's see an example :
Server A and server B were synchronized at t0, when the connection was
broken. Since then, many modification operations occured on both servers :
on Server A : op[1, t1], ..., op[i-1, ti-1], op[i, ti], op[i+1, ti+1],
..., op[n-1, tn-1], op[n, tn]
on Server B : op[1, t'1], ..., op[j-1, t'j-1], op[j, t'j], op[j+1,
t'j+1], ..., op[m-1, t'm-1], op[m, t'm]
Server A and server B are now connected back to each other. each
modifications done on B are to be applied on A and each operations done
on A must be applied on B. What if some of those operations are
conflicting ? Let's just come back at t0, when both servers were
synchronized. If we consider that the servers remained synchronized all
along the connection breakage, then A and B would have received the
modifications from each other at the very moment they occurred, and each
conflict would have result to an error being sent to the client.
Let's do as if the connection never broke then :
we restore the initial state of A and B to t0 (which is possible, as we
have the ChangeLog system, allowing us to revert to a previous state).
Of course, we do so on both servers. Now, let's merge the modifications
form A and B :
op[A, 1, t1], op[B, 1, t'1]..., op[B,j-1, tj-1], op[B, j, tj], op[A,
i-1, ti-1],op[B, j+1, tj+1], op[A, i, ti], op[A, i+1, ti+1], ..., op[A,
n-1, tn-1], op[B, m-1, t'm-1], op[B, m, t'm], op[A, n, tn]
As the operation might have occurred at different times on both server,
they have been mixed, but in any case, as each operation are supposed to
have a unique timestamp, the resulting list of modification is still
order, on both servers.
Now, after having reverted to state t0, we just have to inject the
modifications from the merged list on A and B, rejecting every
modification which are errors. At the end, A and B will be perfectly
synchronized, without conflicts.
Now, remember that A and B are not unique servers, but set of servers.
It doesn't matter too much, as we can consider that all the servers in
set A and set B are totally replicated, so they are in the very same
state, and the merged list can just be applied the same way to any
server from A and B.
What if we have many group of disconnected servers ? This is a bit more
complex, but not so much. We just have to replicate the groups 2 by 2,
or assume they are replicated 2 by 2, and at the end of a potentially
long process, where we revert back to the time the server where
disconnected and reapply all the merged modifications, we will be back
in the same state for all the servers.
There are only two conditions we must met :
1) the servers must be time synchronized,
2) the modifications timestamp must be unique, whatever server they have
been done on.
Condition 2 can easily be met with the existing CSN, if we consider that
there is on order in the replicas (ie A < B < C, ... where A, B, C are
the replica's id). This is purely conventional, but necessary.
Regarding condition #1, we can't guarantee that all the servers will use
the same time. We just do our best to get this as accurate as possible.
Last, not least : the triggers. If some modification can triggers some
other (because of integrity constraints being activated), then it should
be logged in the change log. When replicating, the triggers _must_ be
disabled, as the merged operations will contain all the triggered
operations.
Ok, I'm done now. All this is of course a coarse approximation, but I
think it's pretty close to what we nned to deal with.
Please just tell me if I'm not totally off rail, or if you think I have
just did too much pot lately ;)
Thanks !
--
--
cordialement, regards,
Emmanuel Lécharny
www.iktek.com
directory.apache.org
