Subject: Info model revs...

From: "Ed Reed" <[email-masked]>
Date: Mon, 30 Aug 1999 11:38:27 -0600

Okay, I'm getting down to brass tacks, on this...here are some of the realizations I've had trying to nail it down.

1) DSAs for LDAP aren't defined.  (see previous note to Mark and the list).  I'll probably have to create one.
2) I've defined the lookup table for replica IDs here, anticipating that this definition will be used in the replication protocol doc.  Needed to define it here so the description of CSNs would make sense, because
3) the only way to rationally describe the CSNs is to either
   a) refer to the look up table, defined above, or
   b) allow the RDN of the replica to be used when the lookup table doesn't define any numeric mappings

All this is necessary because I've got to define the CSN as being a fixed length string that will be able to use CaseIgnoreString comparison rules for equality and ordering, so we don't have to create a new syntax for CSNs (an action item from the Oslo meeting).  

But, even with fixed length S1 and S2 values (S and s in other descriptions - which are we using?) in the CSN, the representation of the replica via the lookup table (I call that a replicaNumber) must also be fixed length, base 10 encoding, zero padded to the left.  Note, however, that if the RDN name of the replia, what I'm calling the replicaID, won't pass a CaseIgnoreString match, even if it's fixed length space padded to the right, because CIS matching rules suppress duplicate white space in the match...so unless the RDN is EXACTLY the same length of non-white-space characters for ALL replicas referenced in the CSNs, the CIS match won't work.  Yes, a server can parse the string, compare each field of the string appropriately, but that's what is called a new syntx, which servers MAY implement, but which we'd like not to require.

Bottom line, the only reliable syntax uses the lookup table, with numeric representations for each replica referenced in the CSNs being transferred/compared.  The lookup table is provided by the supplier of CSN information.

My notion of allowing the CSN to include the RDN of the entry is to deal with LDAP Search operations (like READ) which are getting the information about an entry, including it's CSNs, for administrative purposes, for instance.  In that use, it seems silly to require the definition of a lookup table, so I provide the RDN values, instead.

Does anyone care what is required when the RDN of a replica is changed?  MAY I say that reuse of RDNs is disallowed, or is that as unworkable as I think it is?  Maybe instead of RDN we should use the GUID of the replica, instead...that would be fixed length, still long enough to benefit from the lookup table, but easily comparible via CaseIgnoreString.  Should replicas be named by their GUID?  (shudder - maybe that goes too far).

Reactions, both peacable and violent, are invited.

Ed

=================
Ed Reed, Technologist
Novell Product Management
+1 801 222 3944 (new number!)

---

From: Alan Lloyd <[email-masked]>
Date: Tue, 31 Aug 1999 17:49:07 +1000

Re this - Thanks Ed for inviting both peaseful and violent reactions. I
cannot offer either. Just my own humble personal opinions.

Actually I am personally waiting to see if anyone can get this LDUP
stuff  to work without blowing their R&D budget... 
Directory companies are now saying they can support billions of entries
-  But why would you do that in a replicated single server system?
We in fact we theoretically can do 10s of billions etc..across many,
many DSAs - distributed and we can store theoretically 10s of gigabytes
per attribute and thousands of attributes per entry  as well .. Enough
of this wonderful theory stuff.

The point - is that on large scale (big entry) distributed directory
service where multiple updates occur and this CSN stuff has to stay in
check, etc - is there any guarantee that this LDUP protocol actually
works, scales, provides integrity and commercial robustness to the
directory information. - will there be a global GUID administration
scheme for replica entries? Not in God's lifetime I think.
Given that this CSN stuff requires look up tables or some more
attributes stuck somewhere and that where a system carries millions of
entries, what load factors are placed on it during replica updates and
operational incident recovery..

We have come to like our Multi Master mode of working .. It was less
"complex" and avoided many "overheads"  :-)
regards alan
PS - Can those on the list who have models and prototypes on this stuff
publish them. I think trying to imagine large scale distributed and
replicated information systems, performing thousands of transactions a
second  with concurrent update collision mechanisms, - that is applied
by just  "a protocol" and "CSN management"  is somewhat daunting.

> -----Original Message-----
> From:	Ed Reed 
> Sent:	Tuesday, August 31, 1999 3:38 AM
> To:	[email-masked]; [email-masked]
> Subject:	Info model revs...
> 
> Okay, I'm getting down to brass tacks, on this...here are some of the
> realizations I've had trying to nail it down.
> 
> 2) I've defined the lookup table for replica IDs here, anticipating
> that this definition will be used in the replication protocol doc.
> Needed to define it here so the description of CSNs would make sense,
> because
> All this is necessary because I've got to define the CSN as being a
> fixed length string that will be able to use CaseIgnoreString
> comparison rules for equality and ordering, so we don't have to create
> a new syntax for CSNs (an action item from the Oslo meeting).  
> 
> But, even with fixed length S1 and S2 values (S and s in other
> descriptions - which are we using?) in the CSN, the representation of
> the replica via the lookup table (I call that a replicaNumber) must
> also be fixed length, base 10 encoding, zero padded to the left.
> Note, however, that if the RDN name of the replia, what I'm calling
> the replicaID, won't pass a CaseIgnoreString match, even if it's fixed
> length space padded to the right, because CIS matching rules suppress
> duplicate white space in the match...so unless the RDN is EXACTLY the
> same length of non-white-space characters for ALL replicas referenced
> in the CSNs, the CIS match won't work.  Yes, a server can parse the
> string, compare each field of the string appropriately, but that's
> what is called a new syntx, which servers MAY implement, but which
> we'd like not to require.
> 
> Bottom line, the only reliable syntax uses the lookup table, with
> numeric representations for each replica referenced in the CSNs being
> transferred/compared.  The lookup table is provided by the supplier of
> CSN information.
> 
> My notion of allowing the CSN to include the RDN of the entry is to
> deal with LDAP Search operations (like READ) which are getting the
> information about an entry, including it's CSNs, for administrative
> purposes, for instance.  In that use, it seems silly to require the
> definition of a lookup table, so I provide the RDN values, instead.
> 
> Does anyone care what is required when the RDN of a replica is
> changed?  MAY I say that reuse of RDNs is disallowed, or is that as
> unworkable as I think it is?  Maybe instead of RDN we should use the
> GUID of the replica, instead...that would be fixed length, still long
> enough to benefit from the lookup table, but easily comparible via
> CaseIgnoreString.  Should replicas be named by their GUID?  (shudder -
> maybe that goes too far).
> 
>  << File: Ed Reed.vcf >>

---

From: "Ed Reed" <[email-masked]>
Date: Tue, 31 Aug 1999 09:31:51 -0600

Alan -

Yes, there are companies claiming to support "billions and billions" of 
entries in their directories (I can think of one, where I work!).  Know, clearly,
that the purpose of that was to change market perceptions about a product
which up to that time had been largely relegated to distributed nameservice
operations, which was its original design point, and not to the kind of 
general purpose database that others in the market place were
creating.  

The interesting thing about the "billion user tree" which we demonstrated
was that large, flat, bushy trees could now be supported on our product.
Creating a tree with 8 servers and 150 million entries per server (in fact,
per container) stretched a lot of things in our product during the final
shakeout period of the NDS 8 beta tests...in replication, in background
processing, in the Virtual-List-View and Server-Side-Sorting LDAP controls
that we had to use to reasonably access it, etc.

Even distributed searches across the tree were quite acceptible for the
demos and press events for which it was intended.  The memory model
of the b-tree datastore demonstrated that it was not memory bound or
limited in performance, giving consistent search response times against
indexes (which can be added and deleted as needed by our support
staff - administrator managed indexes will appear in the future when we
clean up the user interface) for datasets well beyond the capacity of
the server main memory.

But most importantly, the robust, state-based, distributed multi-master
(the LDAP term) replication protocol still works nicely, with some tweaking,
on such large servers.  That's the same one running on more than a 
million deployed DSAs around the world, today.  And the same one that
is the basis of the LDUP replication design.

So, I guess I'd have to answer your question with "yes, Alan, it works".

Cheers...

Ed

=================
Ed Reed, Technologist

>>> Alan Lloyd <[email-masked]> 08/31/1999 01:49:07 >>>