-----BEGIN PGP SIGNED MESSAGE-----

On Mon, 19 Apr 1999 16:31:37 -0700 Wei Dai <weidai@eskimo.com> wrote:
> location server - Given a cfid, it returns a list of content servers
> that can deliver the referenced file. Given the hash of a public key,
> it returns the public key and the cfid of the file with the highest
> serial number among those signed with the corresponding private
> key. Each location server should choose a binary prefix and handle all
> cfids or key hashes with that prefix. Optionally, all location servers
> can be linked together by a broadcast network, so each content server
> only has to make one location submission to the network per file.

> meta-location server - Given a cfid or key hash, it returns a list of
> location servers that handles the cfid or key hash.

The binary prefix idea is a good one.  There is a generalization of this
I have seen proposed for doing directory lookups.  The GFS[1] file
system, being developed at the University of Minnesota, uses a hash of
the directory entry name to locate the directory page containing the
entry.  The number of bits of hash that are considered depends on the
size of the directory, so you can easily handle the full range of
possible sizes.  In the case of cfids, local caches that consist of only
a few repositories containing local files you would use many bits, for
global comprehensive caches each servers would have only a few bits.

To handle a wide variety of situations, I think the client would want to
consult a variety of sources.  Two that come immediately to mind are
local caches of items popular within the neighborhood and local
repositories of items created by producers in the neighborhood.  An
obvious special case of local producers, is the repository of objects
created by the client himself.  This could be enhanced further by
defining "neighborhood" in several ways.  If I am employed by a company
but work remotely via a local ISP, then neighborhood could be defined
logically with respect to the company or physically WRT my network
connectivity.  One could imagine both corporate and ISP supported caches
and repositories.  This could be extended in several more dimensions,
with some sort of world wide index infrastructure forming an slow,
expensive backstop of last resort.  In all of these cases a list of a
half dozen collection identifiers could provide useful hints as to where
to look for data.

So rather than a single monolithic data location system, better would be
a number of layers each consisting of numerous agents with different
specialties.  The layers are applied serially (due to differences in
expense or performance) while the applicable resources at each level are
queried in parallel.  Hints allow the potential usefulness of resources
to be evaluated a priori which would greatly reduce the number of
unsuccessful requests that were transmitted in each layer.

This search mechanism applies to both file location information and file
content.  Clearly the location information is much more abbreviated but
still enormous in a system deployed on a global scale.  For "local"
information sources, contacting a few likely data servers directly would
probably make sense, but for wider searches, even within a medium size
company or a small ISP, the indirection step of contacting location
servers would be best.  For truly global searches, however, the first
step would be contacting a meta-location server to locate a server that
specializes in the collections mentioned in the hint list.

I view location information has taking two forms.  Slowly changing data
such as the contents of repositories, replicas, mirrors and the like and
ephemeral data describing the membership of caches.  In the former case,
the files contained can easily be identified by a collection identifier,
e.g. 'ota Transarc files', 'GNU Source', 'MSDN Knowledge Base articles
from 1997', etc.  The stream of location updates to these type of
collections are modest and pretty easy to handle.  In the case of caches
the content changes very rapidly and has little logical coherency.  I
think the saving grace here, however, is that caches are generally
local.  They are positioned at choke points and so have contents defined
by their position.  For example, a local host cache contains files I've
referenced lately and sits between me and my machine's network
connection; a firewall cache contains files recently fetched by
employees through the corporate firewall; and a server cache sits in
front of the MSDN servers holding recently requested knowledge base
articles.  Generally caches will not have their contents published but
will be configured as data resources for cfids matching certain hints.

> With these servers in place, it would be easy to find the location of
> any file given its cfid. Namespace lookups could also be done using
> the normal content delivery mechanism, by retrieving the latest
> directory signed with the owner's key. This buys you robustness at the
> cost of losing synchronicity, but the loss of synchronicity can be
> mitigated by including timing information (e.g. expiration date) in
> the signed directory. It can at least be used as a backup mechanism in
> case the directory owner or his lookup service goes offline.

I really like the idea of associating a directory with a PK hash.  I had
been assuming that directories had permanent fids assigned "randomly" by
their creator, but I was having some trouble dealing with connecting the
fid to its owner.  What I came up with was binding the directory fids to
the cfid of an authorization certificate (and ACL basically) in the
parent directory.  It is equivalent, but much more elegant, to just
create a PK and use its hash as the fid.

If namespace directory location information includes both the last
snapshot as well as a list of servers then you get both consistency and
robustness.  If the server(s) can't be reached, no updates are happening
(if the server is actually down and not just behind a network
partition), so the snapshot is probably good.

I envision a sort of distributed mechanism where a namespace server
hands out caching leases to clients that want to cache directories it
knows about (via some subset of the PK hash bits).  When the directory
is updated the clients are contacted to break the lease, which informs
them of a change to the directory.  For an update to occur, however, a
machine must be running as a directory owner.  So it is delegated to
handle subsequent cache lease management and the namespace server will
redirect clients to it.  As long as the owner has the directory cached
and is up and running it handles lookup requests, updates (from other
authorized writers) and lease granting and breaking.  If the owner
finishes with the directory it can send the namespace server the latest
copy as well as returning the lease management responsibility.  If the
owner crashes, the delegation will expire after a while (it is just a
write lease), and the namespace server reclaims responsibility for
managing leases on the affected directories and hands out the last
snapshot it had (perhaps with a warning that the last owner had
crashed).

For higher levels in the namespace this mechanism won't work because the
number of clients requesting leases will be unmanageable.  In this case
the name space servers can resort to using cfids containing directory
data.  Periodic updates can be handled using either scheduled updates or
intermittently as needed.  Because changing a directory entry requires
changing its cfid in its parent, using cfids for directories means
changes must be propagated up from the leafs and become visible down
from the root.  An intermediate strategy would be for namespace servers
to grant leases without tracking individual clients.  While it would be
unable to break leases it could coordinate the lease expiration times so
that they all expire at the same time.  At this point it could allow
updates while holding off new readers.  This would permit consistent
operation in the face of infrequent updates even with large number of
clients.  At lower levels most directories are owned by a single user
who can obtain responsibility for managing infrequent lease requests for
clients looking at his files.  Only a few directories will be actively
updated and widely shared.  These should be supported by big,
highly-available, well-connected machines running with the credentials
of the owner so it can handle a large volume of updates and manage a
large population of lease holders.  In the vast majority of the cases,
however, directories are either semi-static, where caching works very
well, or semi-private, where almost all consistency messages can be
local.

Ted Anderson

[1] http://gfs.lcse.umn.edu/

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBNxymjAGojC9e/wyBAQGURAP/e02Qcy5+7xCOjErJ/0UGqLUOAP9W7vF3
Vf6jGO5dwuVAd0nL6T7UXJwt+rBDm9qfQoJCJ9QB0VvPTp6v4//JEZrdJMdxZ9Dc
FI9SzF4eoVGKAoJ4OiPpw2yl6sIwBY6xUiCk2BEgDXSp3ln54Tu0cgyLd+NNXvyF
/PSHZI76WZc=
=mOp/
-----END PGP SIGNATURE-----