Topic: data caching

topics > computer science > operating system > Group: file system

memory management

alias names
computer architecture
dependency analysis
file cache
hash table and hash functions
information as a hint
managing shared memory
memory cache
memory management by paging
memory management by working sets
replicated data
system builds
updating information in a distributed system


A data cache stores a copy of data for efficient access. If the original copy changes the cached data also changes. Similarly changes to the cached data must propagate to the original data. This process is called cache coherence or cache-consistency. Cached data needs to be restored on power fail.

Cache replacement occurs when the cache is full and items must be removed from the cache. (cbb 11/07)

Subtopic: cache frequently accessed data up

Quote: caching: data that is accessed most often should be the cheapest to access [»bentJL_1982]
Quote: use caching, replication, and prediction to improve latency [»pattDA10_2004]
Quote: Autocode's one-level store, a cache, automatically moved floating-point variables between drum disks and electronic store [»campB4_1980]
Quote: designed Google data structures to avoid disk seeks; a seek still takes 10 milliseconds [»brinS4_1998]

Subtopic: cache coherence up

Quote: cache coherence if a read always returns the value of the last write; stronger than sequential consistency [»afekY1_1993]
Quote: lazy cache algorithm buffers read and write requests; sequential consistency by atomic write to In queues, and flush on by a processor [»afekY1_1993]
Quote: data consistency becomes a problem when multiple copies exist; traditionally, all copies are kept identical [»afekY1_1993]
Quote: taxonomy of cache-consistency algorithms for client-server, object databases [»franMJ9_1997]
Quote: classify cache-consistency by whether it detects or avoids stale data

Subtopic: cache replacement algorithms up

Quote: a Vesta administrator specifies the deletion policy of the function cache weeder; e.g., keep lastest releases, latest build, and checkouts [»heydA_2006]
Quote: concurrent weeding by cache entry leases and a hit filter; prevents deletion and forces cache misses respectively [»heydA_2006]
Quote: least-unified value algorithm for cache replacement of distributed, non-uniform data objects; robust and efficient [»bahnH6_2002]
Quote: least recently/frequently used (LRFU) block replacement policy; up to 30% better than LRU; uses linked list and priority heap based on threshold of recency and frequency value [»leeD9_1997]
Quote: the adaptive replacement cache balances recency and frequency; ignores one-time sequential requests and low temporal locality; outperform LRU on most traces and cache sizes [»megiN4_2004]
Quote: the ARC cache maintains LRU page lists for pages seen once recently and pages seen twice recently; keep both lists the same size as the cache [»megiN4_2004]

Subtopic: reuse distance up

Quote: reuse distance is the number of distinct data elements between accesses of the same data element; also called LRU stack distance [»shenX1_2007]
Quote: approximate program locality with easily-obtained time distance histograms; 17x faster, 99% accurate for cache reuse, 94% for element reuse

Subtopic: network disconnect up

Quote: can run disconnected from a network if cache data; allows one to two day disconnections; update afterwards in a minute [»kistJJ2_1992]

Subtopic: version stamp up

Quote: use version stamps for cached data shared by multiple threads; raise an exception if the version stamp does not match [»birrAD_1991]

Subtopic: copy on write up

Quote: copy on write: don't allocate backing store for a copied page until write to it; lazy evaluation [»giffDK7_1985, OK]
Quote: Mach sends a large message as copy-on-write data via a temporary kernel address map [»acceM6_1986]

Subtopic: write vs. read up

Quote: with increasing memory caches, disk traffic will become dominated by writes [»roseM2_1992]

Subtopic: stale data up

Quote: V's name cache flushes stale data when detected by using that data [»cherDR3_1988]
Quote: in some applications, cached data may be slightly out of date [»cherDR5_1986]

Subtopic: calculation cache up

Quote: Vesta caches the results of expensive function calls with precise, dynamic, fine-grained dependencies
Quote: cache files and build results by fingerprint; distinguish large (1+ MB) and small files [»heydA_2006]
Quote: the Vesta cache is indexed by the fingerprint of all dependencies at a function invocation site; secondary dependencies checked by their name and fingerprint [»heydA_2006]
Quote: partition a primary key by the values of its common names; i.e., those names used in every cache entry [»heydA_2006]
Quote: Vesta's bridges are balanced subtrees of files; if a file changes, only one subtree is affected, reducing cache lookups [»heydA_2006]
Quote: the Vesta weeder deletes cache entries and their derived files from the function call graph, as represented by the graph log [»heydA_2006]
Quote: survey of external memory algorithms; includes sorting, permuting, FFT, graphs, databases, GIS, text processing [»vittJS6_2001]

Subtopic: interpretation using result cache up

Quote: interpret by dynamically translating a compact, flexible or mnemonic representation into a fast representation and caching the result [»lampBW10_1983]

Subtopic: crash recovery up

Quote: for crash recovery, a database needs to flush buffers in the correct order [»stonM7_1981]

Subtopic: skip caching up

Quote: Unix devices drivers can mark a buffer for immediate reuse [»ritcDM_1979]

Subtopic: security issues up

Quote: sensitive data should not be written to disk; lock into memory instead

Related Topics up

Group: memory management   (11 topics, 367 quotes)

Topic: alias names (39 items)
Topic: computer architecture (46 items)
Topic: dependency analysis (34 items)
Topic: efficiency (96 items)
Topic: file cache (23 items)
Topic: hash table and hash functions (41 items)
Topic: information as a hint (18 items)
Topic: managing shared memory (74 items)
Topic: memory cache (29 items)
Topic: memory management by paging (23 items)
Topic: memory management by working sets (18 items)
Topic: replicated data (51 items)
Topic: system builds (43 items)
Topic: updating information in a distributed system
(50 items)

Updated barberCB 5/04
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.