View source for Cache (computing)

{{About|the computing optimization concept|other uses in the field of computing|Cache (disambiguation)#Computing{{!}}Cache (disambiguation) § Computing}}
{{Use dmy dates|date=April 2012}}
{{Refimprove|date=April 2011}}

[[File:cache,basic.svg|frame|Diagram of a *****U memory cache operation]]

In [[computing]], a '''cache''' ({{IPAc-en|ˈ|k|æ|ʃ}} {{respell|KASH|'}},<ref>
{{cite web
|url=https://www.merriam-webster.com/dictionary/cache
|title=Cache
|publisher=Merriam-Webster, Incorporated
|work=Merriam-Webster Online Dictionary
|accessdate=2 May 2011}}</ref> or {{IPAc-en|ˈ|k|eɪ|ʃ}} {{respell|KAYSH|'}} in [[Australian English|AuE]]<ref>
{{cite web
|url=https://www.macquariedictionary.com.au/features/word/search/?word=cache&search_word_type=Dictionary
|title=Cache
|publisher=Macmillan Publishers Group Australia 2015
|work=Macquarie Dictionary
|accessdate=21 July 2015}}</ref>) is a component that stores data so future requests for that data can be served faster; the data stored in a cache might be the result of an earlier computation, or the duplicate of data stored elsewhere.  A ''cache hit'' occurs when the requested data can be found in a cache, while a ''cache miss'' occurs when it cannot.  Cache hits are served by reading data from the cache, which is faster than recomputing a result or reading from a slower data store; thus, the more requests can be served from the cache, the faster the system performs.

To be cost-effective and to enable efficient use of data, caches are relatively small. Nevertheless, caches have proven themselves in many areas of computing because access patterns in typical [[Application software|computer applications]] exhibit the [[locality of reference]]. Moreover, access patterns exhibit [[Memory locality|temporal locality]] if data is requested again that has been recently requested already, while [[Memory locality|spatial locality]] refers to requests for data physically stored close to data that has been already requested.

== {{Anchor|CACHE-HIT}}Operation ==
Hardware implements cache as a [[block (data storage)|block]] of memory for temporary storage of data likely to be used again. [[Central processing unit]]s (*****Us) and [[hard disk drive]]s (HDDs) frequently use a cache, as do web browsers and web servers.

A cache is made up of a pool of entries. Each entry has associated data, which is a copy of the same data in some ''backing store''. Each entry also has a tag, which specifies the identity of the data in the backing store of which the entry is a copy.

When the cache client (a *****U, web browser, [[operating system]]) needs to access data presumed to exist in the backing store, it first checks the cache. If an entry can be found with a tag matching that of the desired data, the data in the entry is used instead. This situation is known as a '''cache hit'''. So, for example, a web browser program might check its local cache on disk to see if it has a local copy of the contents of a web page at a particular URL. In this example, the URL is the tag, and the contents of the web page is the data. The percentage of accesses that result in cache hits is known as the '''hit rate''' or '''hit ratio''' of the cache.

The alternative situation, when the cache is consulted and found not to contain data with the desired tag, has become known as a '''cache miss'''. The previously uncached data fetched from the backing store during miss handling is usually copied into the cache, ready for the next access.

During a cache miss, the *****U usually ejects some other entry in order to make room for the previously uncached data. The [[Heuristic (computer science)|heuristic]] used to select the entry to eject is known as the [[Cache algorithm|replacement policy]]. One popular replacement policy, "least recently used" (LRU), replaces the least recently used entry (see [[cache algorithm]]). More efficient caches compute use frequency against the size of the stored contents, as well as the [[Access time|latencies]] and throughputs for both the cache and the backing store. This works well for larger amounts of data, longer latencies and slower throughputs, such as experienced with a hard drive and the Internet, but is not efficient for use with a *****U cache.{{Citation needed|date=May 2007}}

=== {{Anchor|Dirty|WRITEPOLICIES|WRITE-BACK|WRITE-BEHIND|WRITE-THROUGH|WRITE-AROUND}}Writing policies ===
[[File:Write-through with no-write-allocation.svg|thumb|right|A write-through cache with no-write allocation]]
[[File:Write-back with write-allocation.svg|thumb|right|A write-back cache with write allocation]]

When a system writes data to cache, it must at some point write that data to the backing store as well. The timing of this write is controlled by what is known as the ''write policy''.

There are two basic writing approaches:
* ''Write-through'': write is done synchronously both to the cache and to the backing store.
* ''Write-back'' (or ''write-behind''): initially, writing is done only to the cache. The write to the backing store is postponed until the cache blocks containing the data are about to be modified/replaced by new content.

A write-back cache is more complex to implement, since it needs to track which of its locations have been written over, and mark them as ''dirty'' for later writing to the backing store. The data in these locations are written back to the backing store only when they are evicted from the cache, an effect referred to as a ''lazy write''. For this reason, a read miss in a write-back cache (which requires a block to be replaced by another) will often require two memory accesses to service: one to write the replaced data from the cache back to the store, and then one to retrieve the needed data.

Other policies may also trigger data write-back. The client may make many changes to data in the cache, and then explicitly notify the cache to write back the data.

No data is returned on write operations, thus there are two approaches for situations of write-misses:
* ''Write allocate'' (also called ''fetch on write''): data at the missed-write location is loaded to cache, followed by a write-hit operation. In this approach, write misses are similar to read misses.
* ''No-write allocate'' (also called ''write-no-allocate'' or ''write around''): data at the missed-write location is not loaded to cache, and is written directly to the backing store. In this approach, only the reads are being cached.

Both write-through and write-back policies can use either of these write-miss policies, but usually they are paired in this way:<ref name="HennessyPatterson2011">
{{cite book
|author1=John L. Hennessy
|author2=David A. Patterson
|title=Computer Architecture: A Quantitative Approach
|url=https://books.google.com/books?id=v3-1hVwHnHwC&pg=SL2-PA12
|accessdate=25 March 2012
|date=16 September 2011
|publisher=Elsevier
|isbn=978-0-12-383872-8
|pages=B–12}}</ref>
* A write-back cache uses write allocate, hoping for subsequent writes (or even reads) to the same location, which is now cached.
* A write-through cache uses no-write allocate. Here, subsequent writes have no advantage, since they still need to be written directly to the backing store.

Entities other than the cache may change the data in the backing store, in which case the copy in the cache may become out-of-date or ''stale''. Alternatively, when the client updates the data in the cache, copies of those data in other caches will become stale. Communication protocols between the cache managers which keep the data consistent are known as [[cache coherency|coherency protocols]].

== Applications ==

=== *****U cache ===
{{Main|*****U cache}}

Small memories on or close to the [[*****U]] can operate faster than the much larger [[main memory]]. Most *****Us since the 1980s have used one or more caches, and modern high-end embedded, desktop and server [[microprocessor]]s may have as many as six, each specialized for a specific function. Examples of caches with a specific function are the D-cache and I-cache (data cache and instruction cache).

=== {{Anchor|GPU}}GPU cache ===
Earlier [[graphics processing unit]]s (GPUs) did not feature hardware-managed caches; however, as GPUs moved toward general-purpose computing ([[GPGPU]]), they have introduced and used progressively larger caches.<ref name="ReferenceGCS7">S. Mittal, "[https://www.academia.edu/6940614/A_Survey_of_Techniques_for_Managing_and_Leveraging_Caches_in_GPUs A Survey of Techniques for Managing and Leveraging Caches in GPUs]", JCSC, 23(8), 2014.</ref> For example, [[GeForce 200 series|GT200]] architecture GPUs did not feature an L2 cache, while the [[Fermi (microarchitecture)|Fermi]] GPU has 768&nbsp;KB of last-level cache, the [[Kepler (microarchitecture)|Kepler]] GPU has 1536&nbsp;KB of last-level cache,<ref name="ReferenceGCS7"/> and the [[Maxwell (microarchitecture)|Maxwell]] GPU has 2048&nbsp;KB of last-level cache.

=== Translation lookaside buffer ===
{{Main|Translation lookaside buffer}}

A [[memory management unit]] (MMU) that fetches page table entries from main memory has a specialized cache, used for recording the results of [[virtual address]] to [[physical address]] translations. This specialized cache is called a [[translation lookaside buffer]] (TLB).<ref>{{cite web
 | url = https://cseweb.ucsd.edu/classes/su09/cse120/lectures/Lecture7.pdf
 | title = Lecture  7:  Memory  Management
 | work = CSE 120:  Principles  of  Operating  Systems
 | year = 2009 | accessdate = 2013-12-04
 | author = Frank  Uyeda | publisher = UC San Diego
 | format = PDF
}}</ref>

=== Disk cache ===
{{Main|Page cache}}

While *****U caches are generally managed entirely by hardware, a variety of software manages other caches. The [[page cache]] in main memory, which is an example of disk cache, is managed by the operating system [[Kernel (computing)|kernel]].

While the [[disk buffer]], which is an integrated part of the hard disk drive, is sometimes misleadingly referred to as "disk cache", its main functions are write sequencing and read prefetching. Repeated cache hits are relatively rare, due to the small size of the buffer in comparison to the drive's capacity. However, high-end [[disk controller]]s often have their own on-board cache of the hard disk drive's [[Block (data storage)|data blocks]].

Finally, a fast local hard disk drive can also cache information held on even slower data storage devices, such as remote servers ([[web cache]]) or local [[tape drive]]s or [[optical jukebox]]es; such a scheme is the main concept of [[hierarchical storage management]].  Also, fast flash-based [[solid-state drive]]s (SSDs) can be used as caches for slower rotational-media hard disk drives, working together as [[hybrid drive]]s or [[solid-state hybrid drive]]s (SSHDs).

=== Web cache ===
{{Main|Web cache}}

[[Web browser]]s and [[Proxy server|web proxy servers]] employ web caches to store previous responses from [[web server]]s, such as [[web page]]s and [[image]]s. Web caches reduce the amount of information that needs to be transmitted across the network, as information previously stored in the cache can often be re-used. This reduces bandwidth and processing requirements of the web server, and helps to improve [[responsiveness]] for users of the web.<ref>{{cite web | url=https://docforge.com/wiki/Web_application/Caching | title=Web application caching | author=Multiple (wiki) | work=Docforge | accessdate=2013-07-24 }}</ref>

Web browsers employ a built-in web cache, but some [[Internet Service Provider|internet service providers]] or organizations also use a caching proxy server, which is a web cache that is shared among all users of that network.

Another form of cache is [[P2P caching]], where the files most sought for by [[peer-to-peer]] applications are stored in an [[ISP]] cache to accelerate P2P transfers. Similarly, decentralised equivalents exist, which allow communities to perform the same task for P2P traffic, for example, Corelli.<ref>Gareth Tyson, Andreas Mauthe, Sebastian Kaune, Mu Mu and Thomas Plagemann. Corelli: A Dynamic Replication Service for Supporting Latency-Dependent Content in Community Networks. In Proc. MMCN'09 [https://comp.eprints.lancs.ac.uk/2044/1/MMCN09.pdf]</ref>

=== Memoization ===
{{Main|Memoization}}

A cache can store data that is computed on demand rather than retrieved from a backing store.  [[Memoization]] is an [[Program optimization|optimization]] technique that stores the results of resource-consuming [[function call]]s within a lookup table, allowing subsequent calls to reuse the stored results and avoid repeated computation.

=== Other caches ===
The BIND [[Domain Name System|DNS]] daemon caches a mapping of domain names to [[IP address]]es, as does a resolver library.

Write-through operation is common when operating over unreliable networks (like an Ethernet LAN), because of the enormous complexity of the [[cache coherency|coherency protocol]] required between multiple write-back caches when communication is unreliable. For instance, web page caches and [[client-side]] [[Network File System|network file system]] caches (like those in [[Network File System (protocol)|NFS]] or [[Server Message Block|SMB]]) are typically read-only or write-through specifically to keep the network protocol simple and reliable.

[[Web search engine|Search engine]]s also frequently make [[web page]]s they have indexed available from their cache. For example, [[Google]] provides a "Cached" link next to each search result. This can prove useful when web pages from a [[web server]] are temporarily or permanently inaccessible.

Another type of caching is storing computed results that will likely be needed again, or<!-- yes, this really is memoization; it is not a typo --> [[memoization]]. For example, [[ccache]]<!-- nor is this a typo, "ccache" is C compiler cache --> is a program that caches the output of the compilation, in order to speed up later compilation runs.

[[Database caching]] can substantially improve the throughput of [[database]] applications, for example in the processing of [[Index (database)|indexes]], [[Data dictionary|data dictionaries]], and frequently used subsets of data.

A [[distributed cache]]<ref>{{cite journal
| last        = Paul
| first       = S
|author2=Z Fei
| date        = 1 February 2001
| title       = Distributed caching with centralized control
| journal     = Computer Communications
| volume      = 24
| issue       = 2
| pages       = 256–268
| doi         = 10.1016/S0140-3664(00)00322-4
| accessdate  =18 November 2009
}}</ref> uses networked hosts to provide scalability, reliability and performance to the application.<ref>{{cite journal
| last          = Khan
| first         = Iqbal
| title         = Distributed Caching On The Path To Scalability
| magazine      = MSDN
| issue         = July 2009
| accessdate    =29 March 2012
}}</ref>  The hosts can be co-located or spread over different geographical regions.

=== Buffer vs. cache ===
The semantics of a "buffer" and a "cache" are not necessarily mutually exclusive; even so, there are fundamental differences in intent between the process of caching and the process of buffering.

Fundamentally, caching realizes a performance increase for transfers of data that is being repeatedly transferred. While a caching system may realize a performance increase upon the initial (typically write) transfer of a data item, this performance increase is due to buffering occurring within the caching system.

With read caches, a data item must have been fetched from its residing location at least once in order for subsequent reads of the data item to realize a performance increase by virtue of being able to be fetched from the cache's (faster) intermediate storage rather than the data's residing location. With write caches, a performance increase of writing a data item may be realized upon the first write of the data item by virtue of the data item immediately being stored in the cache's intermediate storage, deferring the transfer of the data item to its residing storage at a later stage or else occurring as a background process. Contrary to strict buffering, a caching process must adhere to a (potentially distributed) cache coherency protocol in order to maintain consistency between the cache's intermediate storage and the location where the data resides. Buffering, on the other hand,
* reduces the number of transfers for otherwise novel data amongst communicating processes, which amortizes overhead involved for several small transfers over fewer, larger transfers,
* provides an intermediary for communicating processes which are incapable of direct transfers amongst each other, or
* ensures a minimum data size or representation required by at least one of the communicating processes involved in a transfer.
With typical caching implementations, a data item that is read or written for the first time is effectively being buffered; and in the case of a write, mostly realizing a performance increase for the application from where the write originated. Additionally, the portion of a caching protocol where individual writes are deferred to a batch of writes is a form of buffering. The portion of a caching protocol where individual reads are deferred to a batch of reads is also a form of buffering, although this form may negatively impact the performance of at least the initial reads (even though it may positively impact the performance of the sum of the individual reads). In practice, caching almost always involves some form of buffering, while strict buffering does not involve caching.

A [[data buffer|buffer]] is a temporary memory location that is traditionally used because *****U [[instruction (computing)|instruction]]s cannot directly address data stored in peripheral devices. Thus, addressable memory is used as an intermediate stage. Additionally, such a buffer may be feasible when a large block of data is assembled or disassembled (as required by a storage device), or when data may be delivered in a different order than that in which it is produced. Also, a whole buffer of data is usually transferred sequentially (for example to hard disk), so buffering itself sometimes increases transfer performance or reduces the variation or jitter of the transfer's latency as opposed to caching where the intent is to reduce the latency. These benefits are present even if the buffered data are written to the [[Data buffer|buffer]] once and read from the buffer once.

A cache also increases transfer performance. A part of the increase similarly comes from the possibility that multiple small transfers will combine into one large block. But the main performance-gain occurs because there is a good chance that the same data will be read from cache multiple times, or that written data will soon be read. A cache's sole purpose is to reduce accesses to the underlying slower storage. Cache is also usually an [[abstraction layer]] that is designed to be invisible from the perspective of neighboring layers.

== See also ==
{{Div col||25em}}
* [[Cache algorithms]]
* [[Cache coherence]]
* [[Cache coloring]]
* [[Cache hierarchy]]
* [[Cache-oblivious algorithm]]
* [[Cache stampede]]
* [[Cache language model]]
* [[Database cache]]
* [[Dirty bit]]
* [[Disk buffer]]
* [[Cache manifest in HTML5]]
* [[Five-minute rule]]
* [[Materialized view]]
* [[Pipeline burst cache]]
* [[Temporary file]]
{{Div col end}}

== References ==
{{Reflist|30em}}

== Further reading ==
* [https://www.unilim.fr/sci/wiki/_media/cali/*****umemory.pdf "What Every Programmer Should Know About Memory"] by [[Ulrich Drepper]]
* [https://msdn.microsoft.com/en-us/library/dd129907.aspx "Caching in the Distributed Environment"]

{{Authority control}}

[[Category:Cache (computing)| ]]