Subject: Re: URP - Distinguished Not Present - New Option?

From: [email-masked]
Date: Fri, 03 Sep 1999 17:43:36 +0100

Hi John,
     I've been working through some examples, but I'm afraid I don't have
any conclusive opinion yet.  I got through most of the examples Steve gave
in his mail, but I'm not sure what impact the fixes to the problems below
will have.

A comment - the removes appear to be happening in the same manner as the
current option 2, i.e. they are delayed until the attribute is made
non-distinguished, rather than being ignored if they occur in the period
while an attribute is distinguished (Option 4).  The advantage over option
2 then is that it allows purging of the dnp values?  I haven't got into
considering the purging yet.

Firstly, a request for some clarification.  Example 1 below is a rework of
an example from Steve's mail.  It was used to demonstrate the need for
additional information in Option 4.  When I did it with your approach, I
got different states at the end.  This could be just a bit of missing code
on the procedure ---rename-make-value-non-distinguished---- (e.g. add an
else that resolves the case where the dnp_csn is after operation_csn where
there is currently nothing).

However, I thought about it a bit more and added another operation (shown
in Example 2 below).  Again the resultant states are different.  And, if we
take the above fix for the previous problem, then the resultant state for
Example 2A will hold in both cases, but it is an odd, undesirable state in
that the attribute is deleted, but is also the distinguished name.
Possibly again another bit of missing code for
-----rename-make-value-distinguished------- for the case where the value is
deleted and the deleted_csn is_after the operation_csn.

Cheers,
Alison

Example 1 (from Steve's mail) - Different Resultant Values
_________________________________________________
Operations :
t1, U1, A, rename entry to V
t2, U2, B, rename entry to W
t3, U3, C, delete V

Time 0 state :
E = {dn = u, vals = [u,v,w]}

A.  Order U2, U3, U1

U2: dn = w:dn2 vals = [u,v,w:p2]
U3: dn = w:dn2 vals = [u,v:d3, w:p2]
U1: dn = w:dn2 vals = [u, v:d3, w:p2]

B.  Order U1, U3, U2

U1: dn = v:dn1 vals = [u, v:p1, w]
U3: dn = v:dn1 vals = [u,v:p1,dnp3, w]
U2: dn = w:dn2 vals = [u,v:p1,dnp3, w:p2]

Example 2
__________
As above, with another operation
t2+, U4, D, rename entry to V

Order U2, U3, U1, U4
---as above (A)---
U4: dn = v:dn2+     vals = [u, v:d3, w:p2]

Order U1,U3,U2, U4
----as above (B)---
U4: dn = v:dn2+     vals = [u, v:p2+, w:p2]

---

From: Steven Legg <[email-masked]>
Date: Mon, 27 Sep 1999 17:50:07 +1000 (EST)

John,

Apologies for taking so long to get around to replying.

John Merrells wrote:
> I think that our suggestion is slightly different from Option 4, in that
> between the purge point and the present time we allow the delete to go
> ahead if a rename (before or after) would permit it to do so, after the
> purge point we behave as if we ignored the delete.

The outcome using your suggestion critically depends on whether earlier
information has been purged at the time of a later decision. However we
can't rely on the consistent purging of old information across all replicas.
The specific order in which updates arrive and CSNs are purged will
vary from replica to replica.

> Going back to the example... where t# is time, u# is update, and the
> replicas are {A,B,C}, and the entry E has DN=u and values {u,v,w}
> 
> t1, u1, A, rename entry to v
> t2, u2, B, delete v
> t3, u3, C, rename entry to w

I need to introduce two extra updates to hurry along the purge point in order
to demonstrate the problem. Assume these two updates are unrelated changes to
entries other than E.

t2, u4, A
t2, u5, C

Note: u5 must always preceed u3 and u1 must always preceed u4.

There are two orders of the five updates that are interesting.

u1, u2, u5, u3, u4
u2, u1, u4, u5, u3

> ~~~~ purge ~~~~
> 
> Assume that we purge all csns stored on the value immediatly.
> The purge csn is the smallest csn in the update vector.
> When a dnp_csn is purged the value stays present.

I'm assuming that any CSN less than or *equal* to the purge csn is eligible
to be purged.

> I'll now apply these rules to our sample entry, which at time zero
> is identical at each replica, and is composed of a dn and some values.
> 
> E= {dn=u, vals=[u,v,w] }
> 
> The csns on the value are of the form "value[;csn]*" where the csn can
> be d# for deleted, p# for present, and dnp# for distinguished not present.
> There's also a csn on the DN, which I'll denote with dn#
> 
> The update vector is a a sequence of csn numbers, uv = [1,2,3], and the
> purge point (pp) is the smallest csn of the update vector.

Order 7: u1, u2, u5, u3, u4

u1: dn=v;dn1 vals=[u,v;p1,w] uv=[1,0,0] pp=0
u2: dn=v;dn1 vals=[u,v;p1;dnp2,w] uv=[1,2,0] pp=0
u5: dn=v;dn1 vals=[u,v;dnp2,w] uv=[1,2,2] pp=1
u3: dn=w;dn3 vals=[u,v;d2,w;p3] uv=[1,2,3] pp=1
u4: dn=w;dn3 vals=[u,w;p3] uv=[2,2,3] pp=2

Order 8: u2, u1, u4, u5, u3

u2: dn=u     vals=[u,v;d2,w] uv= [0,2,0] pp=0
u1: dn=v;dn1 vals=[u,v;p1;dnp2,w] uv= [1,2,0] pp=0
u4: dn=v;dn1 vals=[u,v;p1;dnp2,w] uv= [2,2,0] pp=0
u5: dn=v     vals=[u,v,w] uv= [2,2,2] pp=2
u3: dn=w;dn3 vals=[u,v,w;p3] uv= [2,2,3] pp=2

The outcome of u3 on v depends on whether the distinguished-not-present flag
has been purged by the time u3 is seen. Sometimes it has been (8) and
sometimes it hasn't (7). I haven't been able to find a way to solve this
problem except to make the distinguished-not-present flag persistent.

Incidentally, I trust you realize that the purge point calculation you
are using in these examples only applies to CSNs in the DIT used for
processing received updates, and not to the updates to be sent to other
replicas (and so implies a log based implementation). As calculated here,
the purge point indicates the oldest possible CSN the replica might yet
receive. It does not indicate the oldest of the updates that the replica
might yet have to send. To calculate the latter, the purge point must be
the smallest CSN in all of the update vectors as reported by all of the
replicas.

Regarding which option we go with for dealing with deletes of distinguished
values, I still prefer option 1 (let the delete proceed and make the uid the
RDN) but note that option 3 (reassert the existence of the distinguished
value) is only a slight change from, and compatible with, option 1 as far
as URP is concerned. We could mandate that read-only replicas must use
option 1 (I want to avoid read-only replicas emitting extra update
primitives), writeable replicas are recommended to use option 1, but may
use option 3.

Regards,
Steven