Cache (computing): Difference between revisions

Revision as of 15:54, 25 May 2024

Latest revision as of 09:39, 14 August 2025

(45 intermediate revisions by 24 users not shown)

Line 1:

{{Short description|Additional storage that enables faster access to main storage}}

{{Use dmy dates|date=August 2020}}

{{Use American English|date=July 2024}}

{{Redirect|Caching|3=Cache (disambiguation)}}

[[File:cache,basic.svg|thumb|upright=1|Diagram of a CPU memory cache operation]]

In szlaczki cache[[computing]], a '''cache''' ({{IPAc-en|audio=LL-Q1860 (eng)-Back ache-cache.wav|k|æ|ʃ}} {{respell|KASH}})<ref>

{{cite web|url=http://www.oxforddictionaries.com/definition/english/cache|archive-url=https://web.archive.org/web/20120818122040/http://oxforddictionaries.com/definition/english/cache|url-status=dead|archive-date=18 August 2012|title=Cache|work=Oxford Dictionaries|access-date=2 August 2016}}</ref> is a hardware or software component that stores data so that future requests for that data can be served faster; the data stored in a cache might be the result of an earlier computation or a copy 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 that can be served from the cache, the faster the system performs.<ref>{{Cite journal|last1=Zhong|first1=Liang|last2=Zheng|first2=Xueqian|last3=Liu|first3=Yong|last4=Wang|first4=Mengting|last5=Cao|first5=Yang|date=February 2020|title=Cache hit ratio maximization in device-to-device communications overlaying cellular networks|url=http://dx.doi.org/10.23919/jcc.2020.02.018|journal=China Communications|volume=17|issue=2|pages=232–238|doi=10.23919/jcc.2020.02.018|s2cid=212649328|issn=1673-5447|url-access=subscription}}</ref>

To be cost-effective, caches must be relatively small. Nevertheless, caches are effective in many areas of computing because typical [[Application software|computer applications]] access data with a high degree of [[locality of reference]]. Such access patterns exhibit temporal locality, where data is requested that has been recently requested, and spatial locality, where data is requested that is stored near data that has already been requested.

Line 20 ⟶ 23:

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 (CPUs), [[solid-state drive]]s (SSDs) and hard disk drives (HDDs) frequently include hardware-based cache, while [[web browser]]s and [[web server]]s commonly rely on software caching.

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 CPU, 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'''. 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 content 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.

Line 28 ⟶ 31:

During a cache miss, some other previously existing cache entry is typically removed in order to make room for the newly retrieved data. The [[Heuristic (computer science)|heuristic]] used to select the entry to replace is known as the [[Cache replacement policies|replacement policy]]. One popular replacement policy, least recently used (LRU), replaces the oldest entry, the entry that was accessed less recently than any other entry. More sophisticated caching algorithms also take into account the frequency of use of entries.

==={{Anchor|Dirty|WRITEPOLICIES|WRITE-BACK|WRITE-BEHIND|WRITE-THROUGH|WRITE-AROUND}}WritingWrite policies===

[[File:Write-through with no-write-allocation.svg|thumb|380px|A write-through cache without write allocation]]

[[File:Write-back with write-allocation.svg|thumb|500px|A write-back cache with write allocation]]

When a systemCache writes data to cache, it must ateventually somebe point write that datapropagated to the backing store as well. The timing offor this write is controlledgoverned by what is known as the ''write policy''. There areThe two basicprimary writingwrite approachespolicies are:<ref>{{Cite web|url=https://www.linuxjournal.com/article/7105|title=Understanding Caching|last=Bottomley|first=James|date=2004-01-01|website=Linux Journal|access-date=2019-10-01}}</ref>

* ''Write-through'': writeWrites isare doneperformed synchronously to both to the cache and to the backing store.

* ''Write-back'': initiallyInitially, writing is done only to the cache. The write to the backing store is postponed until the modified content is about to be replaced by another cache block.

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, a process referred to as a ''lazy write''. For this reason, a read miss in a write-back cache will oftenmay require two memory backing store accesses to servicethe backing store: one for theto write back the dirty data, and one to retrieve the neededrequested 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.

SinceWrite nooperations datado isnot returnedreturn todata. the requester on write operationsConsequently, a decision needs to be made for write misses: whether or not datato wouldload bethe loadeddata into the cache. onThis is determined by these ''write-miss misses.policies'':

* ''Write allocate'' (also called ''fetch on write''): dataData 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''): dataData at the missed-write ___location is not loaded to cache, and is written directly to the backing store. In this approach, data is loaded into the cache on read misses only.

BothWhile write-through andboth write-back policies can useImplement either of these write-miss policiespolicy, but usually they are typically paired. as follows:<ref name="HennessyPatterson2011">{{cite book|last1=Hennessy|first1=John L.|url=https://books.google.com/books?id=v3-1hVwHnHwC&pg=SL2-PA12|title=Computer Architecture: A Quantitative Approach|last2=Patterson|first2=David A.|publisher=Elsevier|year=2011|isbn=978-0-12-383872-8|page=B–12|language=en}}</ref><ref>{{cite book|title=Computer Architecture A Quantitative Approach|last1=Patterson|first1=David A.|last2=Hennessy|first2=John L.|isbn=1-55860-069-8|date=1990|page=413|publisher=Morgan Kaufmann Publishers}}</ref>

* A write-back cache usestypically employs write allocate, hopinganticipating forthat subsequent writes (or even reads) to the same ___location, whichwill isbenefit nowfrom having the data already in the cachedcache.

* 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 thosethat data in other caches will become stale. Communication protocols between the cache managers that keep the data consistent are associated with [[cache coherence]].

===Prefetch===

Line 56 ⟶ 59:

Caches with a [[prefetch input queue]] or more general ''anticipatory paging policy'' go further—they not only read the data requested, but guess that the next chunk or two of data will soon be required, and so prefetch that data into the cache ahead of time. Anticipatory paging is especially helpful when the backing store has a long latency to read the first chunk and much shorter times to sequentially read the next few chunks, such as [[disk storage]] and DRAM.

A few operating systems go further with a [[loader (computing)|loader]] that always pre-loads the entire executable into RAM. A few caches go even further, not only pre-loading an entire file, but also starting to load other related files that may soon be requested, such as the [[page cache]] associated with a [[prefetcher]] or the [[web cache]] associated with [[link prefetching]].<!--[[User:Kvng/RTH]]-->

=={{anchor|HARDWARE}}Examples of hardware caches==

===CPU cache===

{{Main|CPU cache}}

Small memories on or close to the CPU can operate faster than the much larger [[main memory]].<ref>{{Cite journal|last1=Su|first1=Chao|last2=Zeng|first2=Qingkai|date=2021-06-10|editor-last=Nicopolitidis|editor-first=Petros|title=Survey of CPU Cache-Based Side-Channel Attacks: Systematic Analysis, Security Models, and Countermeasures|journal=Security and Communication Networks|language=en|volume=2021|pages=1–15|doi=10.1155/2021/5559552|issn=1939-0122|doi-access=free}}</ref> Most CPUs since the 1980s have used one or more caches, sometimes [[CPU cache#Multi-level caches|in cascaded levels]]; modern high-end [[Embedded computing|embedded]], [[Desktop computer|desktop]] and server [[microprocessor]]s may have as many as six types of cache (between levels and functions).<ref>{{cite web|title=Intel Broadwell Core i7 5775C '128MB L4 Cache' Gaming Behemoth and Skylake Core i7 6700K Flagship Processors Finally Available In Retail|date=25 September 2015|url=https://wccftech.com/intel-broadwell-core-i7-5775c-128mb-l4-cache-and-skylake-core-i7-6700k-flagship-processors-available-retail/}} Mentions L4 cache. Combined with separate I-Cache and TLB, this brings the total 'number of caches (levels+functions) to 6.</ref> Some examples of caches with a specific function are the [[D-cache]], [[I-cache]] and the [[translation lookaside buffer]] for the [[memory management unit]] (MMU).

==={{Anchor|GPU}}GPU cache===

Earlier [[graphics processing unit]]s (GPUs) often had limited read-only [[texture cache]]s, and introducedused [[Mortonswizzling order]](computer [[swizzled texturegraphics)|swizzling]]s to improve 2D [[cachelocality coherencyof reference]]. [[Cache miss]]es would drastically affect performance, e.g. if [[mipmapping]] was not used. Caching was important to leverage 32-bit (and wider) transfers for texture data that was often as little as 4&nbsp; bits per pixel, indexed in complex patterns by arbitrary [[UV coordinates]] and [[perspective transformation]]s in [[inverse texture mapping]].

As GPUs advanced, (especially withsupporting [[GPGPU|General-purpose computing on Purposegraphics GPUprocessing units (software)|general-purpose computing on graphics processing units]] and [[compute shaderkernel]]s), they have developed progressively larger and increasingly general caches, including [[instruction cache]]s for [[shader]]s, exhibiting increasinglyfunctionality commoncommonly functionalityfound within CPU caches. For example, [[GeForce 200 series|GT200]] architecture GPUs did not feature an L2 cache, while the GTX 490 GPU has 768&nbsp;KB of last-level cache, the GTX TITAN GPU has 1536&nbsp;KB of last-level cache, and the GTX 980 GPU has 2048&nbsp;KB of last-level cache. These caches have grown to handle [[synchronisationsynchronization primitive]]s between threads and [[atomic operation]]s, and interface with a CPU-style MMU.

===DSPs===

[[Digital signal processor]]s have similarly generalisedgeneralized over the years. Earlier designs used [[scratchpad memory]] fed by [[direct memory access]], but modern DSPs such as [[Qualcomm Hexagon]] often include a very similar set of caches to a CPU (e.g. [[Modified Harvard architecture]] with shared L2, split L1 I-cache and D-cache).<ref>{{cite web|title=qualcom Hexagon DSP SDK overview|url=https://developer.qualcomm.com/software/hexagon-dsp-sdk/dsp-processor}}</ref>

===Translation lookaside buffer===

Line 77 ⟶ 80:

==In-network cache==

===Information-centric networking===

[[Information-centric networking]] (ICN) is an approach to evolve the [[Internet]] infrastructure away from a host-centric paradigm, based on perpetual connectivity and the [[end-to-end principle]], to a network architecture in which the focal point is identified information (or content or data). Due to the inherent caching capability of the nodes in an ICN, it can be viewed as a loosely connected network of caches, which has unique requirements offor caching policies. However, ubiquitous content caching introduces the challenge to content protection against unauthorized access, which requires extra care and solutions.<ref>{{cite journal|author=Bilal, Muhammad|display-authors=etal|title=Secure Distribution of Protected Content in Information-Centric Networking|journal=IEEE Systems Journal|pages=1–12|arxiv=1907.11717|year=2019|volume=14|issue=2|doi=10.1109/JSYST.2019.2931813|bibcode=2020ISysJ..14.1921B|s2cid=198967720}}</ref>

Unlike proxy servers, in ICN the cache is a network-level solution. Therefore, it has rapidly changing cache states and higher request arrival rates; moreover, smaller cache sizes further impose a different kind of requirements on the content eviction policies. In particular, eviction policies for ICN should be fast and lightweight. Various cache replication and eviction schemes for different ICN architectures and applications have been proposed.{{cn|date=August 2024}}

====Policies====

=====Time aware least recently used (TLRU)=====

The Timetime aware Leastleast Recentlyrecently Usedused (TLRU)<ref>{{cite conference|last1=Bilal|first1=Muhammad|first2=Shin-Gak|last2=Kang|conference=16th International Conference on Advanced Communication Technology|title=Time Aware Least Recent Used (TLRU) cache management policy in ICN|year=2014|pages=528–532|doi=10.1109/ICACT.2014.6779016|arxiv=1801.00390|bibcode=2018arXiv180100390B|isbn=978-89-968650-3-2|s2cid=830503}}</ref> is a variant of LRU designed for the situation where the stored contents in cache have a valid life timelifetime. The algorithm is suitable in network cache applications, such as ICN, [[content delivery network]]s (CDNs) and distributed networks in general. TLRU introduces a new term: TTU (Timetime to Useuse (TTU). TTU is a time stamp of aon content/page which stipulates the usability time for the content based on the locality of the content and information from the content publisher announcement. Owing to this locality -based time stamp, TTU provides more control to the local administrator to regulate in -network storage.

In the TLRU algorithm, when a piece of content arrives, a cache node calculates the local TTU value based on the TTU value assigned by the content publisher. The local TTU value is calculated by using a locally defined function. Once the local TTU value is calculated the replacement of content is performed on a subset of the total content stored in cache node. The TLRU ensures that less popular and small lifeshort-lived content should be replaced with the incoming content.<ref>{{cite conference|last1=Bilal|first1=Muhammad|first2=Shin-Gak|last2=Kang|conference=16th International Conference on Advanced Communication Technology|title=Time Aware Least Recent Used (TLRU) cache management policy in ICN|year=2014|pages=528–532|doi=10.1109/ICACT.2014.6779016|arxiv=1801.00390|bibcode=2018arXiv180100390B|isbn=978-89-968650-3-2|s2cid=830503}}</ref>

=====Least frequent recently used (LFRU)=====

The Leastleast Frequentfrequent Recentlyrecently Usedused (LFRU)<ref>{{cite journal|author=Bilal, Muhammad|display-authors=etal|title=A Cache Management Scheme for Efficient Content Eviction and Replication in Cache Networks|journal=IEEE Access|volume=5|pages=1692–1701|arxiv=1702.04078|bibcode=2017arXiv170204078B|year=2017|doi=10.1109/ACCESS.2017.2669344|s2cid=14517299}}</ref> cache replacement scheme combines the benefits of LFU and LRU schemes. LFRU is suitable for 'in network' cache applications, such as ICN, CDNs and distributed networks in general. In LFRU, the cache is divided into two partitions called privileged and unprivileged partitions. The privileged partition can be definedseen as a protected partition. If content is highly popular, it is pushed into the privileged partition. Replacement of the privileged partition is done asby follows:first LFRU evictsevicting content from the unprivileged partition, pushesthen pushing content from the privileged partition to the unprivileged partition, and finally insertsinserting new content into the privileged partition. In the above procedure, the LRU is used for the privileged partition and an approximated LFU (ALFU) scheme is used for the unprivileged partition, hence the abbreviation LFRU. The basic idea is to filter outcache the locally popular contentscontent with the ALFU scheme and push the popular contentscontent to one of the privileged partition.<ref>{{cite journal|author=Bilal, Muhammad|display-authors=etal|title=A Cache Management Scheme for Efficient Content Eviction and Replication in Cache Networks|journal=IEEE Access|volume=5|pages=1692–1701|arxiv=1702.04078|bibcode=2017arXiv170204078B|year=2017|doi=10.1109/ACCESS.2017.2669344|s2cid=14517299}}</ref>

====Weather forecast====

In 2011, the use of smartphones with weather forecasting options was overly taxing [[AccuWeather]] servers; two requests withinfrom the same parkarea would generate separate requests. An optimization by edge-servers to truncate the GPS coordinates to fewer decimal places meant that the cached results from thea earliernearby query would be used. The number of to-the-server lookups per day dropped by half.<ref>{{cite magazine|author=Murphy|first=Chris|date=May 30, 2011|title=5 Lines Of Code In The Cloud|magazine=[[InformationWeek]]|page=28|quote=300 million to 500 million fewer requests a day handled by AccuWeather servers}}</ref>

==Software caches==

===Disk cache===

While CPU 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 (operating system)| kernel]].

{{Main|Page cache}}

While CPU 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 (operating system)|kernel]].

While the [[disk buffer]], which is an integrated part of the hard disk drive or solid state 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, highHigh-end [[disk controller]]s often have their own on-board cache offor the hard disk drive's 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 drives (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 browsers and [[Proxy server|web proxy serversserver]]s, either locally or at the [[Internet service provider]] (ISP), employ web caches to store previous responses from web servers, such as [[web page]]s and [[image file format|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=http://docforge.com/wiki/Web_application/Caching|title=Web application caching|author=Multiple (wiki)|work=Docforge|access-date=2013-07-24|archive-date=12 December 2019|archive-url=https://web.archive.org/web/20191212152625/http://www.docforge.com/wiki/Web_application/Caching|url-status=dead}}</ref>

Web browsers employ a built-in web cache, but some [[Internet service provider]]s (ISPs) 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>{{cite conference|last1=Tyson|first1=Gareth|last2=Mauthe|first2=Andreas|last3=Kaune|first3=Sebastian|last4=Mu|first4=Mu|last5=Plagemann|first5=Thomas|title=Corelli: A Dynamic Replication Service for Supporting Latency-Dependent Content in Community Networks|url=http://comp.eprints.lancs.ac.uk/2044/1/MMCN09.pdf|conference=MMCN'09|archive-url=https://web.archive.org/web/20150618193018/http://comp.eprints.lancs.ac.uk/2044/1/MMCN09.pdf|archive-date=2015-06-18}}</ref>

[[Distributed computing|Distributed web applications]] should consider [[Distributed cache|distributed caching]].

===Memoization===

Line 117 ⟶ 115:

===Content delivery network===

{{Mainmain|Content delivery network}}

A [[content delivery network]] (CDN) is a network of distributed servers that deliver pages and other Web[[web content]] to a user, based on the geographic locations of the user, the origin of the web page and the content delivery server.

CDNs beganwere introduced in the late 1990s as a way to speed up the delivery of static content, such as HTML pages, images and videos. By replicating content on multiple servers around the world and delivering it to users based on their ___location, CDNs can significantly improve the speed and availability of a website or application. When a user requests a piece of content, the CDN will check to see if it has a copy of the content in its cache. If it does, the CDN will deliver the content to the user from the cache.<ref name=":0">{{cite web|url=https://people.cs.umass.edu/~ramesh/Site/PUBLICATIONS_files/DMPPSW02.pdf|title=Globally Distributed Content Delivery, by J. Dilley, B. Maggs, J. Parikh, H. Prokop, R. Sitaraman and B. Weihl, IEEE Internet Computing, Volume 6, Issue 5, November 2002.|access-date=2019-10-25|archive-url=https://web.archive.org/web/20170809231307/http://people.cs.umass.edu/~ramesh/Site/PUBLICATIONS_files/DMPPSW02.pdf|archive-date=2017-08-09|url-status=live}}</ref>

===Cloud storage gateway===

{{Main|Cloud storage gateway}}

A [[cloud storage gateway, also known as an edge filer,]] is a [[hybrid cloud storage]] device that connects a local network to one or more [[cloud storage service]]s, typically [[object storage]] services such as [[Amazon S3]]. It provides a cache for frequently accessed data, providing high speed local access to frequently accessed data in the cloud storage service. Cloud storage gateways also provide additional benefits such as accessing cloud object storage through traditional file serving protocols as well as continued access to cached data during connectivity outages.<ref name="searchstorage1">{{cite web|url=https://www.techtarget.com/searchstorage/definition/cloud-storage-gateway|title=Definition: cloud storage gateway|work=SearchStorage|date=July 2014}}</ref>

===Other caches===

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

Write-through operation is common when operating over [[unreliable networks (like an Ethernet LAN)network]]s, because of the enormous complexity of the coherency protocol required between multiple write-back caches when communication is unreliable. For instance, web page caches and [[client-side]] caches for [[Network File System|networkdistributed file system]] cachess (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 pages they have indexed available from their cache.[[Search Forengine example, [[Googlecache|cache]] 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.

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

A [[distributed cache]]<ref>{{cite journal|last1=Paul|first1=S.|last2=Fei|first2=Z.|date=1 February 2001|title=Distributed caching with centralized control|journal=Computer Communications|volume=24|issue=2|pages=256–268|citeseerx=10.1.1.38.1094|doi=10.1016/S0140-3664(00)00322-4}}<!--|access-date=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|url=https://msdn.microsoft.com/magazine/dd942840.aspx|journal=MSDN|volume=24|issue=7|date=July 2009}}</ref> The hosts can be co-located or spread over different geographical regions.<!--[[User:Kvng/RTH]]-->

=={{anchor|The difference between buffer and cache}}<!--Former section name used in external links-->Buffer vs. cache==

Line 180 ⟶ 179:

{{Authority control}}

[[Category:Cache (computing)| ]]

[[Category:Computer architecture]]