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

[Tim Howes <howes@netscape.com>]

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.


> 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