Group:
memory management
Topic:
alias names
Topic:
computer architecture
Topic:
dependency analysis
Topic:
efficiency
Topic:
file cache
Topic:
hash table and hash functions
Topic:
information as a hint
Topic:
managing shared memory
Topic:
memory cache
Topic:
memory management by paging
Topic:
memory management by working sets
Topic:
replicated data
Topic:
system builds
Topic:
updating information in a distributed system
| |
Summary
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 
| 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
| 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 write..read 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
| 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
| 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
| 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
| 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
| 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
| Quote: with increasing memory caches, disk traffic will become dominated by writes [»roseM2_1992]
|
Subtopic: stale data
| 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
| 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
| Quote: interpret by dynamically translating a compact, flexible or mnemonic representation into a fast representation and caching the result [»lampBW10_1983]
|
Subtopic: crash recovery
| Quote: for crash recovery, a database needs to flush buffers in the correct order [»stonM7_1981]
|
Subtopic: skip caching
| Quote: Unix devices drivers can mark a buffer for immediate reuse [»ritcDM_1979]
|
Subtopic: security issues
Quote: sensitive data should not be written to disk; lock into memory instead
[»gutmP7_1996]
|
Related Topics
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)
|
