- This article is about the computer term. For towns with this name, see Cache, Utah or Cache, Oklahoma.
In computer science, a cache (pronounced kăsh) is a
collection of data duplicating original values stored elsewhere or computed earlier, where the original data are expensive
(usually in terms of access time) to fetch or compute relative to reading the cache. Once the data are stored in the cache,
future use can be made by accessing the cached copy rather than refetching or recomputing the original data, so that the average
access time is lower.
Caches have proved extremely effective in many areas of computing, because access patterns in typical computer applications
have locality of reference. There are several sorts of
locality, but we mainly mean that the same data are often used several times, with accesses that are close together in time, or
that data near to each other are accessed close together in time.
Operation
A cache is a pool of entries. Each entry has a datum, which is a copy of the datum in some backing store. Each entry also has
a tag, which specifies the identity of the datum in the backing store of which the entry is a copy.
When the cache client (a CPU, web browser, operating system) wishes to access a datum presumably in the backing store, it
first checks the cache. If an entry can be found with a tag matching that of the desired datum, the datum in the entry is used
instead. This situation is known as a cache hit. So, for example, a web browser program might check it's 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 datum.
The alternative situation, when the cache is consulted and found not to contain the desired datum, is known as a cache
miss. The datum fetched from the backing store during miss handling is usually inserted into the cache, ready for the next
access. If the cache has limited storage, it may have to eject some other entry in order to make room. The heuristic used to select the entry to eject is
known as the replacement policy. One popular replacement policy, LRU, replaces the least recently used entry.
When a datum is written to the cache, it must at some point be written to the backing store as well. The timing of this write
is controlled by what is known as the write policy. In a write-through cache, every write to the cache causes a
write to the backing store. Alternatively, in a write-back cache, writes are not immediately mirrored to memory. Instead,
the cache tracks which locations have been written over (these locations are marked dirty). The data in these locations is
written back to main memory when that data is evicted from the cache. For this reason, a miss in a write-back cache will often
require two memory accesses to service.
Data write-back may be triggered by other policies as well. The client may make many changes to a datum in the cache, and then
explicitly notify the cache to write back the datum.
The data in main memory being cached may be changed by other entities, 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 that data in other caches will
become stale. Communication protocols between the cache managers which keep the data consistent are known as coherency protocols.
Applications
CPU caches
Main article: CPU cache
Small memories on or close to the CPU chip can be made faster than the much larger main memory. Most CPUs since the 1980s have
used one or more caches, and modern general-purpose CPUs inside personal computers may have as many as half a dozen, each
specialized to a different part of the problem of executing programs.
Disk buffer
(also known as disk cache or cache buffer)
Hard disks have historically often been packaged with embedded computers used for control and interface protocols. Since the
late 1980s, nearly all disks sold have these embedded computers and either an ATA, SCSI, or Fibre Channel interface. The embedded computer usually has some small amount of memory which it uses to
store the bits going to and coming from the disk platter.
The disk buffer is physically distinct from and is used differently than the page cache typically kept by the operating system in the computer's main memory. The disk buffer is controlled by the embedded computer in the disk drive, and the page cache is
controlled by the computer to which that disk is attached. The disk buffer is usually quite small, 2 to 8 MB, and the page cache
is generally all unused physical memory, which in a 2004 PC may be between 20 and 2000 MB. And while data in the page cache is
reused multiple times, the data in the disk buffer is typically never reused. In this sense, the phrases disk cache and cache
buffer are misnomers, and the embedded computer's memory is more appropriately called the disk buffer.
The disk buffer has multiple uses:
- Readahead / readbehind: When executing a read from the disk, the disk arm moves the read/write head to (or near) the correct
track, and after some settling time the read head begins to pick up bits. Usually, the first sectors to be read are not the ones
that have been requested by the operating system. The disk's embedded computer typically saves these unrequested sectors in the
disk buffer, in case the operating system requests them later.
- Speed matching: The speed of the disk's I/O interface to the computer
almost never matches the speed at which the bits are transferred to and from the hard disk platter. The disk buffer is used so that both the I/O interface and the disk read/write head
can operate at full speed.
- Write acceleration: The disk's embedded computer may signal the main computer that a disk write is complete immediately after
receiving the write data, before the data are actually written to the platter. This early signal allows the main computer to
continue working, but is somewhat dangerous because, if power is lost before the data are permanently fixed in the magnetic
media, the data will be lost from the disk buffer, and the filesystem on the disk may be left in an inconsistent state. Write
acceleration is controversial, and for this reason can usually be turned off. On some disks, this vulnerable period between
signalling the write complete and fixing the data can be arbitrarily long, as the write can be deferred indefinitely by newly
arriving requests. Write acceleration is very rarely used on database servers or other machines where the integrity of the data
on the disks is very important.
- Command queueing: Newer SATA and most SCSI disks can accept multiple commands while any one
command is in operation. These commands are stored by the disk's embedded computer until they are completed. Should a read
reference the data at the destination of a queued write, the write's data will be returned. Command queueing is different from
write acceleration in that the main computer's operating system is notified when data are actually written onto the magnetic
media. The O/S can use this information to keep the filesystem consistent through rescheduled writes.
Other caches
CPU caches are generally managed entirely by hardware. Other caches are managed by a variety of software. The cache of disk
sectors in main memory is usually managed by the operating system kernel or file system. The BIND DNS daemon caches a mapping of domain names to IP addresses, 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 coherency protocol required between multiple write-back caches when communication is unreliable. For
instance, web page caches and client-side network file system caches (like those in NFS or SMB) are typically
read-only or write-through specifically to keep the network protocol simple and reliable.
A cache of recently visited web pages can be managed by your Web browser.
Some browsers are 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
keeps a cached copy of each page it examines on the web. These copies are used by the Google indexing software, but they are also
made available to Google users, 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.
Ccache is a program that caches the output of the compilation to speed up the
second-time compilation.
External links
|
