1.5 level cache hierarchy

Some of you may remember the presentation I made about the digest mesh and the
possibility of the mesh to be of use to countries which do not have a
top-level country wide cache.

It turns out Henrik Nordstorm has already had some thoughts along these lines,
(apparently before I thought of it) and he was kind enough to share some ideas
and his notes.

Henrik calls this idea "The 1.5 level hierarchy", with L1 caches doing most of
the work, and central caches keeping an global hint index of where objects are
located and also caching "interesting" objects. The central caches can be
viewed as something in between a sibling and parent function. One way to
implement the indexing is using digest merging into a large "superdigest",
representing a hint state if objects are located inside the cache mesh or
not. The process that makes such a superdigest is called "a digestive".

When the digestive is used within one country, or within one ISPs network, it
can collect digests from all the "institutional caches" and merge them. The
institutional caches then fetch a single digest from the digestive - any
object which appears in that digest is already on the local network. The
institutional caches can thus fetch the object from the digestive using the
normal ICP protocols (the digestive may or may not cache such requests -
anyway what it doesn't have, it can fetch from the institutional cache which
has it).

There are several problems with this scheme: To be able to merge digests, the
digestive needs to be able to order digests which are of the same size (or a
multiple of the same size), so there needs to be a way to negotiate the
size. This is also combined with the fact that the negotiated size is probably
going to be fairly large. Efficient implementation of this scheme might
require cache diffs to cut digest traffic down to a manageable size.

Preliminary testing of the feasibility of this idea can get underway even
before there is a way to merge digests, with the siblings requesting objects
thorugh normal ICP. That removes the "zero added latency" advantages, but
leaves those countries which already have top-level caches no worse off, and
it would give us a starting idea of how much a network of caches could benefit
from a digestive (aka level 1.5) cache.

Here are some advantages of the digestive approach:
A digestive can compare the cache digests of the institutional caches, and, by
simple bit compare, discover which digests are most different from one
another, and taking into account the difference and the time needed to fetch
data from a given institutional cache, it can decide that some caches are not
worth the trouble of being used, therefore it may fetch digests from them only
once a day and not advertise their content to other caches.

If the digestive scheme is implemented with digest merging and digest diffs,
the institutional caches gain the advantage of a big number of peers without
having to deal with a big number of digests (like they would have to in a full
digest mesh) and without any added latency for misses (which they would incurr
in a large scale ICP mesh).

You can of course, connect digestives in the same way (recursively) to create
an international digest mesh.

However, I don't want to wait with the tests of the digest mesh until this
technology is developed: the mesh would certainly benefit greatly from it, but
is not vitaly depended on it.

Please send any comments, ideas, etc, to the list.

Matija
Received on Tue May 23 2000 - 02:36:24 MDT