``ULC: a file block placement and replacement protocol to effectively
exploit hierarchical locality in multi-level buffer caches",
Song Jiang and Xiaodong Zhang
Proceedings of the 24th International Conference on Distributed Computing
Systems (ICDCS'04), Tokyo, Japan, March 23-26, 2004.
In a large client/server cluster system, file blocks are cached
in a multi-level storage hierarchy. Existing file block placement
and replacement are either conducted on each level of the hierarchy
independently, or by applying an LRU policy on more than one levels.
One major limitation of these schemes is that hierarchical locality
of file blocks with non-uniform strengths is ignored, resulting in
many unnecessary block misses, or additional communication overhead.
To address this issue, we propose a client-directed, coordinated file
block placement and replacement protocol, where the non-uniform strengths
of locality are dynamically identified on the client level to direct
servers on placing or replacing file blocks accordingly on different
levels of the buffer caches. In other words, the caching layout of
the blocks in the hierarchy dynamically matches the locality of block
accesses. The effectiveness of our proposed protocol comes from achieving
the following three goals: (1) The multi-level cache retains the same hit
rate as that of a single level cache whose size equals to the aggregate
size of multi-level caches. (2) The non-uniform locality strengths of
blocks are fully exploited and ranked to fit into the physical multi-level
caches. (3) The communication overheads between caches are also reduced.