WIXLIB

vice, but this flushing operation must be performedin any case, whether or not hints are used. As mentioned earlier, the first-tier cache typicallycaptures most of the temporal locality in the workload. Thus, many reads will be served from the firsttier cache. Writes, on the other hand, must go to thesecond tier. Thus, the second-tier cache will see ahigher fraction of writes in its workload than if itwere the only cache in the system. This providesmany opportunities for generating and using writehints. Using write hints is complementary to previousapproaches for managing second-tier caches. Wecould exploit other kinds of hints, demotion information, or inferences about the state of the first-tiercache in addition to using the write hints. If the workload has few writes (e.g., a decisionsupport workload), the behavior of the proposedhint-aware replacement policies will degenerate tothat of the underlying hint-oblivious policies. Inthat case, we expect neither benefit nor harm fromusing write hints.SQL requestsagentsDBMS(storage client) threadread/write requestsprefetchrequestsprefetchersbuffer poolpage cleanersflushrequestsstorage I/Ocachestorage serverFigure 2: DBMS ArchitectureOur contributions in this paper can be summarizedas follows. We propose different types of write hintsthat can be generated by storage clients, and we proposesecond-tier cache replacement policies that exploit thesehints. We evaluate the performance of these policies using traces collected from a real commercial DBMS running the industry standard TPC-C benchmark, and wecompare them to the hint-oblivious alternatives. We alsostudy an optimal replacement technique to provide an upper bound on how well we can do at the second tier.The rest of this paper is organized as follows. InSection 2, we give some background about the architecture of a modern DBMS and its characteristics as astorage client. In Section 3, we present our proposalfor using write hints, and in Section 4, we present threecache replacement policies that use these hints. Section 5presents an evaluation of the proposed policies. Section 6provides an overview of related work. We present ourconclusions in Section 7.2 BackgroundThe I/O workload experienced by a storage server depends on the properties of its clients. Since we areconsidering a scenario in which the storage client is aDBMS, we first present, in this section, the relevant aspects of the process architecture and buffer managementof a modern commercial DBMS. The specifics of thispresentation are taken from DB2 Universal Database [9].USENIX AssociationHowever, similar features are found in other major commercial and open-source database management systems.Figure 2 provides a simplified illustration of the multithreaded (or multi-process, depending on the platform)execution architecture of the DBMS. The DBMS is capable of processing several application SQL requests concurrently. One or more threads, known as agents, areused to execute each SQL statement. As the agentsrun, they read and update the database structures, suchas tables and indexes, through a block-oriented bufferpool. The DBMS may actually maintain several, independently managed buffer pools (not illustrated in Figure 2). Together, these pools constitute the storage clientcache.Each buffer pool is managed using a clock-based algorithm, so recency of reference is important in replacement decisions. However, the replacement policy alsoconsiders a number of other factors, including the typeof data in the block, whether the block is clean or dirty,and the expected access pattern of the last agent to haveused the block. Blocks are loaded into the buffer poolon demand from agents. Depending on the type of querybeing executed, prefetching may also be employed as ameans of removing demand paging delays from the critical paths of the agents. Agents send read-ahead requeststo a prefetching queue, which is serviced by a pool ofprefetching threads. Prefetching threads retrieve blocksFAST ’05: 4th USENIX Conference on File and Storage Technologies117

from the underlying storage system and load them intothe buffer pool, replacing blocks as necessary.As agents run, they may modify the contents of blocksthat are cached in the buffer pools. Modified (dirty) datablocks are generally not written immediately to the underlying storage system. Instead, one or more threadsknown as page cleaners are used to implement asynchronous (with respect to the agents) copy-back of dirtyblocks from the buffer pool. In the event that the bufferreplacement policy calls for the eviction of an updatedblock that has not been cleaned by a page cleaner, theagent (or prefetcher) that is responsible for the replacement flushes (writes) the dirty block back to the underlying storage system before completing the replacement.Note that flushing a dirty block does not by itself removethat block from the buffer pool. It simply ensures thatthe underlying storage device holds an up-to-date copyof the block.The page cleaners must choose which dirty blocks tocopy back to the storage system. There are two issueswhich affect this choice. First, the page cleaners try toensure that blocks that are likely to be replaced by theagents will be clean at the time of the replacement. Thisremoves the burden and latency associated with flushing dirty blocks from the execution path of the agents.To accomplish this, the page cleaners try to flush dirtyblocks that would otherwise be good candidates for replacement.The second issue considered by the page cleaners isfailure recovery time. The DBMS uses write-ahead logging to ensure that committed database updates will survive DBMS failures. When the DBMS is recoveringfrom a failure, the log is replayed to recreate any updates that were lost because they had not been flushed tothe underlying storage system prior to the failure. Theamount of log data that must be read and replayed to recover the proper database state depends on the age of theoldest changes that are in the buffer pool at the time ofthe failure. By copying relatively old updates from thebuffer pools to the storage system, the page cleaners tryto ensure that a configurable recovery time threshold willnot be exceeded.Several aspects of these mechanisms are worth noting. First, block writes to the underlying storage systemusually do not correspond to evictions from the DBMSbuffer pools. Writes correspond closely to evictions onlywhen they are performed synchronously, by the agents.However, in a well-tuned system, the page cleaners tryto ensure that such synchronous block writes are rare.Thus, if management of the storage server cache depends on knowledge of evictions from the client cache,that knowledge must be obtained by some other means,e.g., through the introduction of an explicit DEMOTEoperation [20]. Second, the replacement algorithm used118to manage the DBMS buffer pool is complex and usesapplication-specific information. This poses a challengeto storage server cache managers that rely on simulation of the storage client as a means of predicting whichblocks are in the client’s cache [2].3 Write HintsAs was noted in Section 1, we propose to use write requests to improve the performance of the storage servercache. Each write request generated by the storage clientincludes a copy of the block being written, so writerequests provide low-overhead opportunities to placeblocks into the storage server’s cache. Furthermore, thefact that the storage client has written block b to the storage server may also provide some clues as to the state ofthe storage client’s cache. The storage server can exploitthese hints to improve the exclusiveness of its cache withrespect to the client’s.What can the storage server infer about the storageclient from the occurrence of a write? One key to answering this question is the fact that there are several distinct reasons why the storage client issues write requests,as described in Section 2. The first reason is block replacement: if the client wants to replace block b and bhas been updated, then the client must write b back to thestorage server before replacing it. We call such write requests replacement writes. The second reason for writingis to limit data loss in the event of a failure at the storageclient. Thus, the storage client may write a block to thestorage server even through that block is not a likely replacement candidate, in order to ensure the recoverability of changes that have been made to that block. We callsuch write requests recoverability writes.A second key issue is the relationship between the timeof the client’s write of block b and the time of b’s evictionfrom the client’s cache. In some cases, the client writesa dirty block b to the storage server because it is aboutto evict b from its cache. In the DBMS architecture described in Section 2, such writes may be generated bythe agent threads when they need to replace a dirty blockin the buffer pool. We call these eviction-synchronouswrites, or simply synchronous writes. In other cases,such as when pages are flushed by the page cleaners, theeviction of the block is not imminent, and in fact may notoccur at all. We call these eviction-asynchronous writes,or simply asynchronous writes. Note that the distinction between synchronous and asynchronous writes andthe distinction between replacement and recoverabilitywrites are essentially orthogonal.Assuming that the storage server could somehowmake these distinctions, what kinds of hints could it takefrom write requests? We present several cases here.FAST ’05: 4th USENIX Conference on File and Storage TechnologiesUSENIX Association

synchronous writes: A synchronous write of blockb indicates that b is about to be evicted from the storage client’s cache. If the storage server chooses toplace b into its cache, it can be confident that b isnot also in the storage client’s cache. asynchronous replacement writes: An asynchronous replacement write of block b indicates twothings. First, b is present in the storage client’scache. Second, the storage client is preparing b foreventual eviction, although eviction may not be imminent. Thus, in this case, it is not obvious what thestorage server should infer from the occurrence ofthe write. However, we observe that if the storageclient is well-designed, an asynchronous replacement write does suggest that b is quite likely to beevicted from the storage client cache in the nearfuture. This is a weaker hint than that providedby a synchronous write. However, given that awell-designed client will seek to avoid synchronouswrites, asynchronous replacement write hints mayultimately be more useful because they are morefrequent.the least aggressive techniques in that category. On thepositive side, only a couple of bits per request are required for tagging, a negligible overhead. More importantly, we believe that it should be relatively easy and natural to identify write types from within the storage client.As noted in Section 5, we easily instrumented DB2 Universal Database to label each write with one of the threepossible write types described above. Moreover, thetypes of write requests that we consider are not specific to DB2. Other major commercial database management systems, including Oracle [17] and Microsoft SQLServer [14], distinguish recoverability writes from replacement writes and try to do the writes asynchronously,resorting to synchronous writes only when necessary.Non-DBMS storage clients, such as file systems, alsoface similar issues. Finally, it is worth noting that thestorage client does not need to understand how the storage server’s cache operates in order to attach hints to itswrites. Write hints provide information that may be useful to the storage server, but they do not specify how itshould manage its cache.4 Managing the Storage Server Cache asynchronous recoverability writes: An asynchronous recoverability write of block b indicatesthat b is present in the storage client’s cache andthat it may have been present there for some time,since recoverability writes should target old unwritten updates. Unlike an asynchronous replacementwrite, a recoverability write of block b does not indicate that b’s eviction from the storage client cacheis imminent, so b is a poor candidate for placementin the storage server cache.To exploit these hints, it is necessary for the storageserver to distinguish between these different types ofwrites. One possibility is for the server to attempt to infer the type of write based on the information carried inthe write request: the source of the block, the destination of the block in the storage server, or the contents ofthe block. Another alternative is for the storage clientto determine the type of each write and then label eachwrite with its type for the benefit of the storage server.This is the approach that we have taken. Specifically,we propose that the storage client associate a write hintwith each write request that it generates. A write hint issimply a tag with one of three possible values: S YNCH,R EPLACE, or R ECOV. These tags correspond to the threecases described earlier.The necessity of tagging means that the use of writehints is not entirely transparent to the storage client.Thus, under the classification proposed by Chen et al [5],write hints would be considered to be an “aggressivelycollaborative” technique, although they would be amongUSENIX AssociationIn this section, we discuss using the write hints introduced in Section 3 to improve the performance ofsecond-tier cache replacement policies. We present techniques for extending two important cache replacementpolicies (LRU and MQ) so that they take advantage ofwrite hints. We also present a new cache replacement algorithm that relies primarily on the information providedby write hints. But first, we address the question of howwrite hints can be used to achieve the goals of second-tiercache management.4.1 Using Hints for Cache ManagementOur goals in managing the second-tier cache are twofold.We want to maintain exclusiveness between the firstand second-tier caches, which means that the second tiershould not cache blocks that are already cached in thefirst tier. At the same time, we want the second tier tocache blocks that will eventually be useful for the firsttier. These are blocks whose re-reference distance (defined as the number of requests in the I/O stream betweensuccessive references to the block) is beyond the localitythat could be captured in the first tier, and so will eventually miss in the first tier.When choosing blocks to cache in the second tier, weshould bear in mind that hits in the second tier are onlyuseful for read requests from the first tier, but not writerequests. Thus, the second-tier cache management policyshould try to cache blocks that will cause read misses inthe first tier.FAST ’05: 4th USENIX Conference on File and Storage Technologies119

We should also bear in mind that the second tier doesnot have to cache every block that is accessed by thefirst tier. The storage server could choose not to cachea block that is accessed, but rather to send the blockfrom the storage device directly to the storage client (ona read miss), or from the client directly to the device (ona write).2 This is different from other caching scenarios (e.g., virtual memory) in which the cache managermust cache every block that is accessed. Thus, storageserver cache management has an extra degree of flexibility when compared to other kinds of cache management: when a new block arrives and the cache is full, thecache manager can evict a block to make room for thenew block, or it can choose not to cache the new block.With these points in mind, we consider the informationprovided by S YNCH, R EPLACE, and R ECOV write requests and also by read requests (which we label R EAD).S YNCH and R EPLACE writes of a block b indicate thatthe block will be evicted from the first tier, so they provide hints that b should be cached in the second tier,with S YNCH providing a stronger hint than R EPLACE.Caching b in the second tier will not violate exclusiveness, and future read accesses to b, which most likelywill miss in the first tier, will hit in the second tier.Conversely, a R EAD request for block b indicates thatb will have just been loaded into the first-tier cache. Wecannot determine from the R EAD request how long bwill be retained in the first-tier cache. If recency-of-useplays a role in the storage client’s cache management decisions, then we can expect that b will be a very poorcandidate for caching at the storage server, as it is likelyto remain in the client’s cache for some time. On theother hand, the client’s cache manager may take factorsbesides recency-of-use into account in deciding to evictb quickly. For example, if b is being read as part of alarge sequential table scan performed by a database system then b may be quickly evicted from the client, andpotentially re-referenced.R ECOV writes provides little information to the storage server cache. On the one hand, the written block isknown to be in the storage client cache, which makes ita poor candidate for caching at the server. On the otherhand, a R ECOV write of b indicates that b has probablybeen in the storage client cache for a long time. Thus, theR ECOV write does not provide as strong a negative hintas a R EAD.Next, we illustrate how two important cache replacement policies (LRU and MQ) can be extended to takeadvantage of hints, and we present a new algorithm thatrelies primarily on request types (i.e., hints) to managethe cache.1204.2 LRU HintsWe extend the least recently used (LRU) cache replacement policy by using hints to manage the LRU list and todecide whether or not to cache accessed blocks. We consider a simple extension: we cache blocks that occur inS YNCH or R EPLACE write requests, since such blocksare likely to be evicted from the storage client cache.Blocks that occur in R ECOV write requests or R EAD requests are not added to the cache.Specifically, in the case of a S YNCH or R EPLACEwrite for block b, we add b to the cache if it is not thereand we move it to the most-recently-used (MRU) end ofthe LRU list. If a replacement is necessary, the LRUblock is replaced. In the case of a R ECOV or R EAD request for block b, we make no changes to the contents ofthe cache or to the recency of the blocks, except duringcold start, when the cache is not full. During cold start,R ECOV and R EAD blocks are cached and placed at theLRU end of the LRU list. Of course, in the case of aR EAD request, the server checks whether the requestedblock is in its cache, and it serves the requested blockfrom the cache in case of a hit. This hint-aware policy issummarized in Algorithm 1.4.3 MQ HintsThe Multi-Queue (MQ) [21] algorithm is a recently proposed cache replacement algorithm designed specificallyfor second-tier cache management. It has been shownto perform better than prior cache replacement algorithms, including other recently proposed ones such asARC [13] and LIRS [10]. The algorithm uses multiple LRU queues, with each queue representing a rangeof reference frequencies. Blocks are promoted to higherfrequency queues as they get referenced more frequently,and when we need to evict a block, we evict from thelower frequency queues first. Thus, MQ chooses theblock for eviction based on a combination of recency andfrequency.To implement its eviction policy, MQ tracks the recency and frequency of references to the blocks thatare currently cached. MQ also uses an auxiliary datastructure called the out queue to maintain statistics aboutsome blocks that have been evicted from the cache, Eachentry in the out queue records only the block statistics,not the block itself, so the entries are relatively small.The out queue has a maximum size, which is a configurable parameter of the MQ policy, and it is managed asan LRU list.We extend the MQ algorithm with hints in the sameway in which we extended LRU. If a request is a S YNCHor R EPLACE, we treat it exactly as it would be treated under the original MQ algorithm. If the request is a R EAD,FAST ’05: 4th USENIX Conference on File and Storage TechnologiesUSENIX Association

Algorithm 1 LRU HintsLRUW ITH H INTS (b : block access)1234567if b is already in the cache /* cache hit */then if type(b) S YNCH or type(b) R EPLACEthen move b to the MRU end of the LRU list;elseif type(b) S YNCH or type(b) R EPLACE /* cache miss */then insert b at the MRU end of the LRU list, evicting the LRU block to make room if needed;elseif cache is not full /* cache miss and not S YNCH or R EPLACE */then insert b at the LRU end of the LRU list;we check the queues for a hit as usual. However, thequeues are not updated at all unless the cache is not full,in which case the block is added as it would be under theoriginal algorithm. R ECOV requests are ignored completely unless the cache is not full, in which case theblock is added as in the original algorithm.4.4 The TQ AlgorithmIn this section, we present a new cache replacement algorithm that relies primarily on request types, as indicatedby write hints, to make replacement decisions. We callthis algorithm the type queue (TQ) algorithm. Amongour hint-aware algorithms, TQ places the most emphasison using request types (or hints) for replacement. Weshow in Section 5 that the TQ algorithm outperformsother candidate algorithms. TQ is summarized in Figure 3 and Algorithm 2.As described earlier, blocks that occur in S YNCH andR EPLACE write requests are good candidates for cachingat the storage se

the second tier. Another reason why managing second-tier caches is difficult is that the second-tier cache may include blocks that are already present in the first-tier cache. Accesses tothese blockswould hitin thefirsttier,so cachingthem in the second tier is a poor use of available cache space. Hence, second-tier cachemanagementhas the .