Extends Karma ([yafa07]) two a two-tier scenario in which multiple clients which share data also share a second-tier cache. Space is partitioned among clients, with one additional partition used for shared data. Within each partition, space is managed using Karma.

Includes lower and upper bounds on optimal off-line performance for multi-level caches. Proposes a scheme called PROMOTE for managing multi-tier caches. As a requested page is passed up through the cache tiers, each cache decides whether it will be responsible for caching the page. Once a cache has decided to cache the page, it notifies the higher level caches of this by attaching a flag to the page as it is passed up through tiers. The higher level caches then do not cache the page. This enforces exclusiveness among the caches. Pages that are repeatedly requested should tend to migrate to higher level caches. Behaviour on writes is not specified, e.g, can a write affect which cache is responsible for a particular page. This policy requires modification of the caching policies at every tier, as each tier must abide by caching decisions made at lower tiers, and must inform upper tiers of its decisions.

Assumes caches support read, read-save, and demote. Requires that blocks by grouped into ranges by the application. Application must also specify the frequency of access and access pattern for each range. Each range is assigned some space in some cache in the hierarchy, and each range's space is then managed using a separate replacement policy. Experiments used PostgreSQL explain to generate range and access pattern hints - however, explain data covers the situation before the DBMS cache.

Compares “hierarchically aware” approachs to “aggressively-collaborative” approaches. The former are transparent to the storage client (e.g., the DBMS), the latter are not. Aggressively-collaborative approaches include two types of hint-passing: access patterns and application semantics. Example of semantic hint is a hint that a block will be read only one time. Even more aggressive is content-aware caching, where the caches try explicitly to avoid duplication. Also considers some additional optimizations: Quick eviction of duplicated blocks (DU) removes pages from the buffer when they are read, Semantics-Directed Caching (SE) uses “importance” values from the storage client (in an ill-specified way) to affect buffering at the storage server. General conclusion is that the agressively-collaborative approaches do not help much compared to the hierarchically-aware approaches.

Presents a trace-based characterization of access patterns for second-tier (L2) buffer caches, noting that L2 cache reference streams don't exhibit any small reuse distances. Presents the MQ algorithm for managing L2 cache. MQ uses multiple LRU queues. Pages are promoted to higher queues according to frequency of reference. Replacements happen in low queues first. An aging mechanism is used to demote pages that cool down. Also describes so-called global replacement algorithms, in which the L2 cache is informed when replacements are made at L1. Evaluation is by trace-driven simulation and also by experiment with an storage system cache implementation.

Eviction-based placement means that a page is loaded into the storage cache when it is evicted from the storage client's cache, as opposed to when it is requested by the client. Proposes tracking evictions transparently by monitoring the target addresses of read requests. Evicted pages are prefetched from disk into the storage system cache at the time of predicted eviction from the storage client cache.

ARC maintains two LRU queues, one for pages that have been referenced once and one for pages that have been referenced more than once. For each queue, there is also a ghost queue that tracks additional pages. The sizes of the two queues are adjusted dynamically. A hit in the single-reference ghost queue causes the single-reference queue to grow. A hit in the multi-reference ghost queue causes the multi-referenced queue to grow.

Notes that storage system caches are often LRU-based, and points out the multi-tier cache inclusion problem: that a second-tier LRU cache behind a first-tier LRU cache will contain many of the same pages as the first-tier cache. Defines a “demote” operation to deal with this problem. Demote sends to the second tier a block that has been evicted from the first tier. Argues that the cost of sending these blocks to the second tier is low because storage networks have lots of bandwidth. Also defines a “demote” buffer management policy for tier two. This puts blocks read by tier one at the LRU end of the buffer (like our +read-read policy) and puts blocks demoted by the first tier at the MRU end.

Describes a cooperative two-level caching system in which first-level caches may fetch blocks from other first-level caches. A hint is potentially inaccurate information about the locations of blocks in the first-level caches.

Simulation study of bi-level LRU caches for a distributed file system. Found that increasing client cache size quickly reduces the hit rate of the second tier cache.

Describes a scheme for synchronizing writes in batches, rather than individually.