RE: Search over referrals (Re: LAST CALL: draft-ietf-ldapext-ref erral-00.txt)

[Alan Lloyd <Alan.Lloyd@OpenDirectory.com.au>]

> -----Original Message-----
> From:	Tim Howes [SMTP:howes@netscape.com]
> Sent:	Tuesday, April 07, 1998 6:47 AM
> To:	Alan Lloyd
> Cc:	Harald Tveit Alvestrand; ietf-ldapext@netscape.com
> Subject:	Re: Search over referrals (Re: LAST CALL:
> draft-ietf-ldapext-ref	erral-00.txt)
> 
> As David mentioned, yes, I had in mind the distributed
> searching and indexing problem. The X.500 model works
> great when you can narrow the scope of your search using
> the namespace to one or a relatively small number of servers.
> 
	We have put 20 or so of these together with 80m attributes and
used complex searches ..

> Then, searching them all in parallel (or serially even) is
> feasible. If you can't narrow your scope in this way, you are
> out of luck for a system of any size. To handle this situation,
> holding distributed indexing information that tells you
> which other servers might be worth searching is one solution.
	But this gets dated - and predictive seaching for 1000mmms of
users across a global directory system is not scaleable 

> (Another solution might be creating parallel namespaces for
> each kind of search you want to do. There are other possibilities
> as well.)
> 
	People seem to confuse organisational naming models with service
provision naming models (eg CAs, etc) and alternate views of the same
info using alias to represent localities, work groups., etc.We do this
in X.500.

	My view is with powerful distributed directory services many
interconnected systems can be constructed with diffrent views of
information and that having indexing information via protocols  is
adding more mechanisms and maintenance when good old horsepower and
smart RDBs in X.500 can do the job.



> The FIND IETF working group has done some work on this
> problem. In particular, they've developed a protocol to be used
> in passing this indexing information among servers. Check out
> draft-ietf-find-* for more information.                  -- Tim
> 
	We would rather go for deployability - the more protocols
supporting the distributed directory service the worse it will get. Ours
seems to work and scale so it aint broke - so we dont need to fix it :-)


	regards alan 
> Alan Lloyd wrote:
> 
> > It seems from the text below we keep putting more and more "user
> > visible" engineering in to do what the technology of good directory
> > products already do - and are supposed to do. I probably sound like
> a
> > cracked record but for directories to scale in the User and Business
> > environment - should we not build coherent systems using industry
> > strengh components (such as RDBs that index), not many "protocol"
> parts
> > which require massive configuration resource which naturally limit
> > usefulness and scale.
> >
> > Should we not rely on good distributed object oriented system design
> > like X.500 (and interconnected servers via DSP) and the integration
> of
> > good information management and retrieval systems like relational
> > databases.
> > We married the two and dont seem to have the problems described or
> > inflict such problematic service delivery issues on customers. So
> IMHO
> > much of the detail below has been solved by products already . So I
> > question why do we need a standard or the introduction of "indexing"
> > mechanisms....
> >
> > In addition - looking at the Persistent Search draft - I wonder how
> this
> > will scale and work in a distributed fashion. Does this PS
> requirement
> > mean that every server in the directory system must now remember
> User
> > operation "state" and possibly multiple instances of it. eg. say I
> did a
> > Search over a dozen servers with PS and then repeated this 100,000
> times
> > - does this mean that each server must no hold "state" for all these
> > searches. - what happens if some reach a limit, what happens if some
> > servers dont do PS....
> >
> > > -----Original Message-----
> > > From: Tim Howes [SMTP:howes@netscape.com]
> > > Sent: Wednesday, March 25, 1998 4:08 AM
> > > To:   Harald Tveit Alvestrand
> > > Cc:   ietf-ldapext@netscape.com
> > > Subject:      Re: Search over referrals (Re: LAST CALL:
> > > draft-ietf-ldapext-referral-00.txt)
> > >
> > > Harald Tveit Alvestrand wrote:
> > >
> > > > Tim, gang:
> > > > when reading the referral draft, I started wondering.
> > > >
> > > > The drawing goes like this:
> > > >
> > > >
> > > |------------------------------------------------------------|
> > > >        |                    Server A
> > > |
> > > >        | dn: o=abc,c=us                dn: o=xyz,c=us
> > > |
> > > >        | ref: ldap://hostB/o=abc,c=us  ref:
> ldap://hostD/o=xyz,c=us
> > > |
> > > >        | ref: ldap://hostC/o=abc,c=us  objectclass: referral
> > > |
> > > >        | objectclass: referral
> > > |
> > > >
> > > |____________________________________________________________|
> > > >
> > > >   |---------------------| |---------------------|
> > > |---------------------|
> > > >   |       Server B      | |       Server D      | |      Server
> C
> > > |
> > > >   | dn: o=abc,c=us      | | dn: o=xyz,c=us      | | dn:
> o=abc,c=us
> > > |
> > > >   | o: abc              | | o: xyz              | | o: abc
> > > |
> > > >   | other attributes... | | other attributes... | | other
> > > attributes... |
> > > >   |_____________________| |_____________________|
> > > |_____________________|
> > > >
> > > > A subtree search under o=abc,c=us is well defined.
> > > >
> > > > But: What is going to be returned on a single level search under
> > > c=us
> > > > for "phone=+47 22 33 44 56"?
> > > >
> > > > There are 3 alternatives:
> > > >
> > > > - Server A holds complete copies of all attributes for the
> entries
> > > >   that have "referral" as its object class. It can answer the
> > > >   search without referring.
> > > >
> > > > - Server A holds only the referral data, and returns as many
> > > referrals
> > > >   as there are second-level servers.
> > >
> > > > - I have misunderstood something, and there is a third
> alternative.
> > >
> > > It's not this black and white, nor does it need to be. At one
> > > end of the spectrum, Server A holds only referrals, and yes,
> > > it returns as many referrals as are in scope. Clearly, if you
> > > have thousands of referrals there, it's not going to work too
> > > well.
> > >
> > > At the other end of the spectrum, Server A holds replicas
> > > of all the entries (or even all the subtrees - hey why not go
> > > all the way!) and just answers the query without referring.
> > > This has its own problems, though, relating to scale and other
> > > things (like maybe I don't trust Server A to replicate my
> > > data, maybe the staleness of the data is not acceptable, etc.).
> > >
> > > Somewhere in between is a third alternative that works better.
> > > This is where indexing comes in. Suppose Server A contains
> > > an index on the phone attribute from its subordinate servers.
> > > (Perhaps it maintains this index using CIP - that problem is
> > > orthogonal to this one.) Then Server A can consult its index
> > > to determine which referrals to send to the client. This is
> > > similar to the unnamed reference case discussed in the draft.
> > >
> > > The advantages of this scheme over the replication scheme
> > > are that you only have to send the index data, staleness is not
> > > an issue for anything except the index data, etc. Remember,
> > > the search might be by phone, but I might want back phone,
> > > name, address, etc.
> > >
> > > This same problem exists for subtree searches as well. I'm
> > > not sure why you think the one-level search is different.
> > >
> > >
> > > > I believe a DIT structured as the second alternative will be a
> total
> > > > disaster if one is building a directory with any significant
> > > distribution
> > > > at all; I can imagine a client chasing 5 referrals; I can *NOT*
> > > imagine
> > > > a client chasing 20.000 referrals.
> > > > (There is no procedure in the draft for merging referrals; even
> if
> > > you
> > > > get 20.000 referrals to only 5 servers, there are 20.000
> referrals
> > > to
> > > > be chased).
> > >
> > > "If you want to search everything - well, that's a lot of stuff."
> > >     - Me, just now
> > >
> > > So if you want to solve this problem you need to think about
> > > indexing (e.g., CIP) to help constrain the search space. The
> > > scheme described in this draft is designed exactly to work with
> > > something like CIP and in simple "namespace connection"
> > > situations where it's not required.
> > >
> >         We thought about indexing in fact we use an RDB and our
> table
> > design to do that for every attribute - automatically. We also have
> > efficient distributed search algorithms - All of these are included
> in
> > our integrated X.500 and LDAP with RDB server product.
> >         And none of this needs configuration or CIPs.
> >
> > > > If we want the first alternative, I believe "Referral" should be
> an
> > > auxillary
> > > > object class, not a structural one, and the requirement to
> shadow
> > > the
> > > > referred-to entry should be plain in the text.
> > > > (Yes, I know X.500 doesn't have this restriction. And I know
> that
> > > the
> > > > problem has been encountered in X.500 setups.)
> > >
> > > Probably making referral auxiliary is a better way to do it
> > > than what's currently in the draft (structural + allows any
> > > attribute - which is probably not really legal). Thanks, I'll
> > > make this change unless somebody stops me.          -- Tim
> 
>