Cache

In computer science, a \'cache is a tiny short-term memory space in a computer with quicker access speed than main memory to fill the gap between slow devices and fast devices. There may be multiple levels of cache, and in general such an architecture is referred to as a hierarchical memory' system.

Table of contents

1 System-level caches
2 Higher-level caches
3 Design considerations
4 Common cache implementations
5 External link

System-level caches

The cache operates by storing a part of the data, allowing that part to be accessed more quickly. A speed-up is achieved if many accesses to the data can access the data in the cache. The reason caches work at all is that many access patterns in typical computer applications have locality of reference. There are several sorts of locality, but we mainly mean that often the same data is accessed frequently or with accesses that are close together in time, or that data near to each other are accessed close together in time.

One example is a RAM that caches the accesses to the hard drive, so that when two subsequent reads of the same file from the hard disk occur, only one physical read from the disk is performed. Modern disk drives have such a cache built in to the electronics of the drive. Most modern operating systems also operate some sort of disk cache using the computer's main memory.

Caches are also used between the CPU and the (slower) main RAM in modern PC. There are often several levels of cache, with different sizes and access speed. Generally the caches get smaller, faster, and more expensive, the closer to the CPU they are. When the CPU requires data from these caches, there is an increasing penalty to speed according to how far away the cache is.

Higher-level caches

Caches do not have to be thought about in purely low level/OS terms, software can cache return values that are likely to be re-used in the near future. A good example of this is the BIND DNS daemon which caches domain name replies for a period before going back to the authorative source of the name to IP mapping. Resolver libraries also perform almost exactly the same caching.

Web browsers also use caches. Some browsers implement their own cache of recently visited web pages; this saves having to download them again when you revisit. Most browsers can be configured to use an external proxy web cache, a server program through which all web requests are routed so that it can cache frequently accessed pages for everyone in an organization. Many ISPs use proxy caches to save bandwidth on frequently-accessed web pages.

The search engine Google takes a snapshot of each page examined as it crawls the web and caches these as a back-up in case the original page is unavailable. If you click on the "Cached" link in a Google search result, you will see the web page as it looked when Google indexed it.

Design considerations

When designing a cache there are a number of points to consider:

What data should be cached?
What are the typical access patterns to this data?
How big should I make the cache?
How should data be brought into the cache?
When the cache is full, what data should be removed (evicted) from the cache to make room for more recent data?

A number of different algorithms are used for optimizing the contents of the cache, including to remove the "least recently used" - LRU - contents when the cache is full.

Common cache implementations

Accesses to memory or disk are composed of read and write operations. Caching for reading access is far more common than for writing because writing can complicate the consistency of data.

Write-through (or write-thru) is a cache architecture in which data is written to main memory at the same time as it is cached.
Buffered write-through is a variation of write-through where the cache uses a "write buffer" to hold data being written back to main memory. This frees the cache to service read requests while the write is taking place. There is usually only one stage of buffering so subsequent writes must wait until the first is complete. Most accesses are reads so buffered write-through is only useful for very slow main memory.
A cache with a posted write-through policy (e.g. Intel 80386) delays the write-back to main memory until the bus is not in use.
Write-back is a cache architecture in which data is only written to main memory when it is forced out of the cache. A write-back cache is also called a copy-back cache. It is the opposite of a write-through architecture.

This article contains material from FOLDOC, used with permission. Update as needed.

External link

http://www.foldoc.org/foldoc/foldoc.cgi?cache