Skip to Content.
Sympa Menu

bluesky - Root and Branch Naming

bluesky AT lists.ibiblio.org

Subject: Global-Scale Distributed Storage Systems

List archive

Chronological Thread  
  • From: Ted Anderson <ota AT transarc.com>
  • To: bluesky AT franklin.oit.unc.edu
  • Subject: Root and Branch Naming
  • Date: Sun, 18 Mar 2001 18:43:45 -0500


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

Subject: Root and Branch Naming

It seems that the previous discussion on namespaces, specifically root
names, disintegrated without reaching a conclusion. I would like to
gently approach the topic from a slightly different angle in hopes of
making some progress.

There are three aspects of the namimg problem which face different
constraints and so probably require diverse solutions. The first level
is the root names, this level faces tough non-technical problems.
Second is the quasi-static namespaces, below the root, but still high in

the naming hierarchy. This level has aggressive performance and
reliability requirements. Third, the lower level directories, are not
as widely shared, but maybe actively updated and is the control point
needing flexible access control and synchronization.

For reasons of stability and replication I think the upper parts (but
not the top) of the naming hierarchy are best implemented by static
directories and described / named by a content-based hash (CHK). Each
directory maps names to CHKs, and each CHK unambiguously designates a
lower level directory. Because these high levels of the namespace are
slowly changing and need to be very widely replicated and cached for
performance reasons, it makes sense to use hashes to authenticate and
identify them.

However, using hashes does work very far down. A change in any leaf
node leads to a change in its hash, which changes, its CHK and so
requires a change in its parent. This recurrence continues all the way
up to the root. Thus a single CHK in the root defines a snapshot of an
entire subtree. Changes in the tree are published by releasing new
snapshots periodically. Because these trees are static they can be
authenticated and cached with high reliability and confidence.

At some point, the relaxing performance demands on one hand and the
increasing update rate on the other force a change to another mechanism.

For lower levels of the namespace that are (relatively) little shared,
it makes more sense to have a server / client architecture. In this
environment the owner of the directory is a public key which is
authorized to update the directory's contents. The transition between
the second level hash tree and these online, lower level directories
takes the form of a certificate. In the parent, the directory's name is

mapped to the CHK of a certificate naming the public key of the
directory owner, a list of server locations, and a CHK of a recent
snapshot of the directory. This authorizes a server acting on behalf of

the owning principal to offer directory services, such as lookup,
update, and delegation. Delegation allows nodes with read access to
cache a copy of the directory and arrange to be notified of updates.
Delegation to a node authenticated as the owner allows the server named
in the certificate to offload all request to the delegatee by simply
forwarding all requests.

The use of delegation would be an optional performance enhancement,
which could be implemented by a whole spectrum of mechanism, depending
on the load and environment. Delegation could be built upon a high
performance algorithm such as used by distributed lock managers found in

cluster operating systems, or can be based on a simple scheme that
assumes that directories rarely move and the lookup and update load can
be handled by a single server.

Less optional than delegation is some form of synchronization. Because
of the immutability of CHKs, namespace updates are the mechanism for
implementing file modifications, namely mapping an existing name to a
new contents. Therefore consistency of writes to shared data that may
also be cached by readers depends upon some type of locking or
synchronization in the namespace.

---***---

I still think that an SPKI (Mark Miller's point that SDSI and SPKI have
merged in RFC 2692/3 is well taken), approach is best for handling root
names. I would imagine there would be two groups of competing root name

authorities, the first group would consist of a handful of conservative
organizations. These would only add names that were well defined and
widely agreed upon, specifically, within the group of conservative
naming authorities. The second group would consist of more liberal
naming authorities which would add names relatively quickly and easily.
Consequently they might sometime be in conflict with other naming
authorities and would sometimes remove names that caused clashes. They
would thus provide less stable naming than the first group. Most users
would use one authority from the first group to populate their top-level

names and possibly use one or more from the second group to fill in
behind the primary server.

My assumption is that most names users care about would be relatively
stable and reliable and that they would tolerate a certain messiness in
the management of names around the edges. Since this whole mechanism
depends on political and social factors that are undergoing rapid
evolution it may be impossible to reliably predict the most successful
approach. Flexibility and adaptability will be the most important
characteristics.

It is worth noting that the top-level of a namespace for a global
decentralized file system, is not going to rely heavily on the current
host-centric, DNS naming system. Because it is location independent,
naming servers is not as relevant as it is in the WWW. Many pathnames
will surely be defined by companies and so will have dot-com names near
the root. However, other data will be best named by semantic
classifications and other taxonomies whose naming authorities are
relatively easily established, such as UPC and ISBN. In the long run it

isn't clear what kind of global pathnames will be most common or useful.

Perhaps understanding this aspect of the naming system will produce more

light than heat.

In summary, I would suggest that there are three levels of the namespace

which require different implementation mechanisms:
1 - root names, depending on political and social issues
2 - hash tree namespaces, providing high performance and stability
3 - online directories, supporting updates and synchronization

Ted Anderson

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 7.0.3 for non-commercial use <http://www.pgp.com>

iQCVAwUBOrVHLwGojC9e/wyBAQFbNQQAkZE8zPRi0N2QTJyo8rnjfXSsKx3+hp9Z
OEdgA/HZn0AGQGuF3GcDHJfn91mZmIDA7SS37G6dWLJItSgaXoFAmmz4F1jJBfNM
wZ0Au9wtMGxMlh98z4DZW9Rb9fk+KRfh1DlPLMKSkS+K/1o2lcT4GwxQDqEbS8Eq
PjKzNFnM+MY=
=NzhT
-----END PGP SIGNATURE-----






Archive powered by MHonArc 2.6.24.

Top of Page