Subject: RE: Info model revs...

From: Alan Lloyd <[email-masked]>
Date: Fri, 3 Sep 1999 12:41:26 +1000

Thanks for that Ed - sounds interesting. Some detail though if I may :-)

> -----Original Message-----
> From:	Ed Reed 
> Sent:	Wednesday, September 01, 1999 1:32 AM
> To:	[email-masked]; [email-masked]; 'Ed Reed';
> [email-masked]
> Subject:	RE: Info model revs...
> 
> 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.  
> 
	Good - Its good to keep the public aware of changes - in an
industry that  depends on them.

> 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.
> 
	But what was the schema of the entry - as we all know any tests
particularly on small, indexed attrs/entries  can be made to be fast.

> 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.
> 
	This is the very point - as most are aware we automatically
index everything - we dont need operators to work out what MUST be
searched on by anyone so that it can be manually configured as indexes -

	In the automatic index model - in a distributed system any
search from any where on any attribute is faily linear. ours!
	In a manually indexed system where the attribute index processes
may be limited to 12 or 20 or what ever, etc..If one does a serach on an
indexed attribute, then its fast, but if one does a search with a filter
EIS  on a non indexed attribute - the performance drops right off.. and
naturally consumes much more  processing and disk resources..Also schema
extensibility is lost - eg If add schema - then I may have just used up
my last index..

> 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".
	Ours works as well  !  its just we can prove scale and integrity
because our database approach uses commit services, etc.

	Well Ed . The question is not quite answered on LDUP is it  .
:-)  eg. Lots of entries described but the attributes of the OCs and
entries are not defined, spread across 8 servers - not sure if its
replicated or distributed (same of different namespace or a mixture) ,
realistic searches work as a demo if manual indexes defined - and then
say LDUP works because there is lots of NDS around.

	To prove LDUP I would like to know what was the update rate per
second on these servers was (answers of over 200 a second are
acceptable), what was the attribute type/lenght being updated , how many
replicas were there and what destructive testing was used - eg plug
pulling on replica servers  - and did you try collisions on
renames/deletes at a reasonable rate...

	Many systems "work" - Even planes work on the ground !

	regards as always..alan

> Cheers...
> 
> Ed
> 
> =================
> Ed Reed, Technologist
> Novell Product Management
> +1 801 222 3944 (new number!)
> 
> >>> Alan Lloyd <[email-masked]> 08/31/1999 01:49:07
> >>>
> 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.
> > 
> > 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!)
> >  << File: Ed Reed.vcf >>  << File: Ed Reed.vcf >>

---

From: "Ed Reed" <[email-masked]>
Date: Fri, 03 Sep 1999 10:19:07 -0600

True - fully indexed databases are fast on reads (as long as the index roots, at least, can remain in memory without paging out), but update times degrade as more and more indexes are added, too.  For heavily used directories, like NDS and ADS, where there are hundreds of attributes being active managed, that may eventually get to be a problem.  Right now, I'm encouraging our engineering team to ship with more, rather than less, indexes, but I know there's a wall, and only operational experience will tell us where that is for various deployment scenarios, machine configurations, distribution patterns and application data access profiles.

As I recall, the entries in our tree were populated with normal contact info (address, phone number, email address) and a public key and login attributes so they were really "users" and not just stubs.   Probably no more than 2500 bytes per entry, on average, though.

Ed

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

>>> Alan Lloyd <[email-masked]> 09/02/1999 20:41:26 >>>

	regards as always..alan