Room 8

The ARC

A cache in memory has to choose what to forget. Forget the least recently used block, as an LRU cache does, and one large read, a backup or a scan of a big file, pushes out everything that was being reused: every scanned block is more recent than the working set. Forget the least frequently used one, as an LFU cache does, and the blocks that were hot yesterday stay, however cold they are today.

The ARC, the cache of ZFS, keeps the blocks seen once recently on one list, MRU, and the blocks seen at least twice on another, MFU, so a scan only passes through the first. And it remembers what it has just evicted: a ghost list keeps the header of each evicted block, without its data. A read that finds a ghost is a miss that a bigger list would have turned into a hit, and the ARC shifts its balance towards that list.

1 Read, scan, read again

The cache below holds 16 blocks of 128 KiB: that is its target size, arc_c. It opens with a hot set, H1 to H6, read twice a second apart, so all six are in MFU. Each list runs from its head, the most recent, to its tail, which is evicted first. Read a new block, scan twelve new ones, read the hot set again, or select any block to read it, cached, ghost or forgotten. A clock moves one second before each action, or 10 ms if you choose.

Try a scan first: it passes through MRU, and the hot set stays. Then read a block from the MRU ghost list and watch arc_pd and the MRU target rise. Read a few scan blocks again to promote them, read new blocks until MFU gives up a hot block, and read that one back from the MFU ghost list: the balance moves the other way. Last, at 10 ms, read the same new block twice.

arc_pd 50%: the MRU target is 8 blocks of 16.

MRU ghost

0 headers, no data · at most 0 blocks · ghost hits 0 KiB

empty

MRU

0 blocks, data in memory

empty

MFU

6 blocks, data in memory

MFU ghost

0 headers, no data · at most 0 blocks · ghost hits 0 KiB

empty

Forgotten

headers destroyed: the ARC no longer knows these blocks

empty

Text version of this figure

arc_c is 16 blocks of 128 KiB. Clock: 2.01 s. Each list from head (most recent) to tail (evicted first):

MRU ghost, 0: empty.
MRU, 0: empty.
MFU, 6: H6, H5, H4, H3, H2, H1.
MFU ghost, 0: empty.

Forgotten (headers destroyed), most recent first: empty.

arc_pd 50%: the MRU target is 8 blocks of 16. Ghost hits so far: MRU ghost 0 KiB, MFU ghost 0 KiB.

The idea, at three depths

In one sentence

The ARC keeps blocks seen once apart from blocks seen twice, remembers the headers of what it evicted, and when a read finds one of those ghosts it gives more room to the list that would have kept the block.

In one paragraph

A new block enters MRU. A second read more than ARC_MINTIME, about 62 ms, after the first promotes it to MFU; re-reads within one burst count as one use. When the cache is over arc_c, an eviction pass takes blocks from the tail of MRU if MRU is above its share, and from the tail of MFU otherwise. An evicted block loses its data, but its header moves to the matching ghost list, which may hold half of what the other lists hold. Reading a ghost is a miss: the block is read from disk again, goes to MFU, and its size is counted as a ghost hit. There is no arc_p any more in OpenZFS 2.4.4. The shares are fixed-point fractions, arc_pd for the MRU share of data, arc_pm for metadata and arc_meta between the two, and the next eviction pass moves them with the ghost hits it finds: up for hits in the MRU ghost list, down for hits in the MFU ghost list, by at most about 1/32 at a time.

In detail

States and headers. A block in the ARC has a header, arc_buf_hdr_t, keyed by the block’s DVA and birth txg, and the header is in one of seven states: anon, MRU, MRU ghost, MFU, MFU ghost, L2C only and uncached. The figure draws four of them, as lists. The header records its state, the time of its last access, b_arc_access, and hit counters. A new block goes from anon to MRU.

Seen once, seen twice. A hit on an MRU block:

arc_access Excerpt of module/zfs/arc.c, lines 5398–5428, OpenZFS zfs-2.4.4. View on GitHub

	} else if (hdr->b_l1hdr.b_state == arc_mru) {
		/*
		 * This buffer has been accessed once recently and either
		 * its read is still in progress or it is in the cache.
		 */
		if (HDR_IO_IN_PROGRESS(hdr)) {
			hdr->b_l1hdr.b_arc_access = now;
			return;
		}
		hdr->b_l1hdr.b_mru_hits++;
		ARCSTAT_BUMP(arcstat_mru_hits);

		/*
		 * If the previous access was a prefetch, then it already
		 * handled possible promotion, so nothing more to do for now.
		 */
		if (was_prefetch) {
			hdr->b_l1hdr.b_arc_access = now;
			return;
		}

		/*
		 * If more than ARC_MINTIME have passed from the previous
		 * hit, promote the buffer to the MFU state.
		 */
		if (ddi_time_after(now, hdr->b_l1hdr.b_arc_access +
		    ARC_MINTIME)) {
			hdr->b_l1hdr.b_arc_access = now;
			DTRACE_PROBE1(new_state__mfu, arc_buf_hdr_t *, hdr);
			arc_change_state(arc_mfu, hdr);
		}

L5403–L5406 A hit on a block whose read is still in flight only refreshes its time. In the figure every read completes at once.
L5407–L5408 The hit is counted on the header.
L5414–L5417 A block first read by prefetch is not promoted by the demand read that follows. The figure has no prefetch.
L5423–L5428 More than ARC_MINTIME after b_arc_access: to MFU, and the time is refreshed. Otherwise nothing moves, not even b_arc_access, so a series of re-reads less than 62 ms apart is measured from the first one. The test is strict: exactly 62 ms does not promote.

ARC_MINTIME is hz >> 4, “62 ms”. A hit on an MFU block stays in MFU and refreshes b_arc_access.

Head and tail. arc_read calls arc_access on a hit, and on a miss before the data is allocated. While a reader holds a block, its header is off its list; the last release puts it back, at the head, and eviction takes from the tail. So each list is in order of last use. In the figure the reader lets go of each block at once.

Eviction keeps the header. When a block is evicted from MRU or MFU:

arc_evict_hdr Excerpt of module/zfs/arc.c, lines 3876–3891, OpenZFS zfs-2.4.4. View on GitHub

	if (hdr->b_l1hdr.b_pabd != NULL)
		arc_hdr_free_abd(hdr, B_FALSE);

	if (HDR_HAS_RABD(hdr))
		arc_hdr_free_abd(hdr, B_TRUE);

	arc_change_state(evicted_state, hdr);
	DTRACE_PROBE1(arc__evict, arc_buf_hdr_t *, hdr);
	if (evicted_state == arc_anon) {
		arc_hdr_destroy(hdr);
		*real_evicted += HDR_FULL_SIZE;
	} else {
		ASSERT(HDR_IN_HASH_TABLE(hdr));
	}

	return (bytes_evicted);

L3876–L3880 The data is freed.
L3882 The header moves to the ghost state chosen above: MRU to MRU ghost, MFU to MFU ghost. In the figure it slides into the head of the ghost list, without data.
L3884–L3889 Only an uncached buffer’s header is destroyed. A ghost header stays in the hash table, so a later read of the same block finds it.

Which list gives up a block. The eviction pass, after its metadata steps:

arc_evict Excerpt of module/zfs/arc.c, lines 4527–4556, OpenZFS zfs-2.4.4. View on GitHub

	/* Evict MRU metadata. */
	w = wt * (int64_t)(arc_meta * arc_pm >> 48) >> 16;
	e = MIN((int64_t)(asize - ac), (int64_t)(mrum - w));
	bytes = arc_evict_impl(arc_mru, ARC_BUFC_METADATA, e);
	total_evicted += bytes;
	mrum -= bytes;
	asize -= bytes;

	/* Evict MFU metadata. */
	w = wt * (int64_t)(arc_meta >> 16) >> 16;
	e = MIN((int64_t)(asize - ac), (int64_t)(m - bytes - w));
	bytes = arc_evict_impl(arc_mfu, ARC_BUFC_METADATA, e);
	total_evicted += bytes;
	mfum -= bytes;
	asize -= bytes;

	/* Evict MRU data. */
	wt -= m - total_evicted;
	w = wt * (int64_t)(arc_pd >> 16) >> 16;
	e = MIN((int64_t)(asize - ac), (int64_t)(mrud - w));
	bytes = arc_evict_impl(arc_mru, ARC_BUFC_DATA, e);
	total_evicted += bytes;
	mrud -= bytes;
	asize -= bytes;

	/* Evict MFU data. */
	e = asize - ac;
	bytes = arc_evict_impl(arc_mfu, ARC_BUFC_DATA, e);
	mfud -= bytes;
	total_evicted += bytes;

L4527–L4541 Metadata first: MRU metadata down to its target, then MFU metadata down to the metadata share. The figure holds data blocks only, so these steps evict nothing.
L4543–L4550 MRU data, down to its target w = wt · arc_pd, and no more than the cache is over arc_c (asize - ac). An MRU at or under its target gives up nothing.
L4552–L4556 MFU data gives up whatever overshoot remains.

wt is what can be evicted, arc_c itself when every block in the cache is evictable, as in the figure. Each step evicts at most what the list holds, and nothing for a negative amount, from the tail, until it has evicted at least the amount asked. So MRU is not evicted down to its target in one go: it gives up its tail only while the cache is over arc_c. The figure’s first scan shows it: MRU keeps 10 blocks against a target of 8, because each new block puts the cache only one block over.

How long the ghosts last. At the end of the same pass:

arc_evict Excerpt of module/zfs/arc.c, lines 4558–4587, OpenZFS zfs-2.4.4. View on GitHub

	/*
	 * Evict ghost lists
	 *
	 * Size of each state's ghost list represents how much that state
	 * may grow by shrinking the other states.  Would it need to shrink
	 * other states to zero (that is unlikely), its ghost size would be
	 * equal to sum of other three state sizes.  But excessive ghost
	 * size may result in false ghost hits (too far back), that may
	 * never result in real cache hits if several states are competing.
	 * So choose some arbitraty point of 1/2 of other state sizes.
	 */
	gsrd = (mrum + mfud + mfum) / 2;
	e = zfs_refcount_count(&arc_mru_ghost->arcs_size[ARC_BUFC_DATA]) -
	    gsrd;
	(void) arc_evict_impl(arc_mru_ghost, ARC_BUFC_DATA, e);

	gsrm = (mrud + mfud + mfum) / 2;
	e = zfs_refcount_count(&arc_mru_ghost->arcs_size[ARC_BUFC_METADATA]) -
	    gsrm;
	(void) arc_evict_impl(arc_mru_ghost, ARC_BUFC_METADATA, e);

	gsfd = (mrud + mrum + mfum) / 2;
	e = zfs_refcount_count(&arc_mfu_ghost->arcs_size[ARC_BUFC_DATA]) -
	    gsfd;
	(void) arc_evict_impl(arc_mfu_ghost, ARC_BUFC_DATA, e);

	gsfm = (mrud + mrum + mfud) / 2;
	e = zfs_refcount_count(&arc_mfu_ghost->arcs_size[ARC_BUFC_METADATA]) -
	    gsfm;
	(void) arc_evict_impl(arc_mfu_ghost, ARC_BUFC_METADATA, e);

L4569–L4572 The MRU-data ghost list may hold half of the three other live lists. The figure has no metadata lists, so that is half of MFU.
L4579–L4582 The MFU-data ghost list: half of MRU in the figure.

A ghost list is not the size of the cache. In the figure, with an empty MFU, the MRU ghost list holds nothing. A header trimmed from a ghost list is destroyed; the figure lists it as forgotten, and reading the block again is a new block to the ARC.

A ghost hit. Reading a block whose header is in the MRU ghost list:

arc_access Excerpt of module/zfs/arc.c, lines 5429–5449, OpenZFS zfs-2.4.4. View on GitHub

	} else if (hdr->b_l1hdr.b_state == arc_mru_ghost) {
		arc_state_t	*new_state;
		/*
		 * This buffer has been accessed once recently, but was
		 * evicted from the cache.  Would we have bigger MRU, it
		 * would be an MRU hit, so handle it the same way, except
		 * we don't need to check the previous access time.
		 */
		hdr->b_l1hdr.b_mru_ghost_hits++;
		ARCSTAT_BUMP(arcstat_mru_ghost_hits);
		hdr->b_l1hdr.b_arc_access = now;
		wmsum_add(&arc_mru_ghost->arcs_hits[arc_buf_type(hdr)],
		    arc_hdr_size(hdr));
		if (was_prefetch) {
			new_state = arc_mru;
			DTRACE_PROBE1(new_state__mru, arc_buf_hdr_t *, hdr);
		} else {
			new_state = arc_mfu;
			DTRACE_PROBE1(new_state__mfu, arc_buf_hdr_t *, hdr);
		}
		arc_change_state(new_state, hdr);

L5432–L5435 “Would we have bigger MRU, it would be an MRU hit”: a ghost hit is a miss that a bigger list would have avoided. The data is read from disk again.
L5437–L5441 Counted on the header, and the block’s size (its compressed size if compressed) added to the MRU ghost list’s hit counter. The figure shows the counter under each ghost list.
L5442–L5449 Back into the cache in MFU, since this is its second use; in MRU if the block was a prefetch.

An MFU-ghost hit does the same with the MFU ghost list’s counter and goes back to MFU. arc_access changes no target: it only adds up bytes. The eviction pass reads them.

From ghost hits to a balance. At the start of each pass:

arc_evict Excerpt of module/zfs/arc.c, lines 4479–4497, OpenZFS zfs-2.4.4. View on GitHub

	/* Get ARC ghost hits since last eviction. */
	ngrd = wmsum_value(&arc_mru_ghost->arcs_hits[ARC_BUFC_DATA]);
	uint64_t grd = ngrd - ogrd;
	ogrd = ngrd;
	ngrm = wmsum_value(&arc_mru_ghost->arcs_hits[ARC_BUFC_METADATA]);
	uint64_t grm = ngrm - ogrm;
	ogrm = ngrm;
	ngfd = wmsum_value(&arc_mfu_ghost->arcs_hits[ARC_BUFC_DATA]);
	uint64_t gfd = ngfd - ogfd;
	ogfd = ngfd;
	ngfm = wmsum_value(&arc_mfu_ghost->arcs_hits[ARC_BUFC_METADATA]);
	uint64_t gfm = ngfm - ogfm;
	ogfm = ngfm;

	/* Adjust ARC states balance based on ghost hits. */
	arc_meta = arc_evict_adj(arc_meta, gsrd + gsrm + gsfd + gsfm,
	    grm + gfm, grd + gfd, zfs_arc_meta_balance);
	arc_pd = arc_evict_adj(arc_pd, gsrd + gsfd, grd, gfd, 100);
	arc_pm = arc_evict_adj(arc_pm, gsrm + gsfm, grm, gfm, 100);

L4480–L4491 The ghost-hit bytes since the previous pass, four ways: MRU ghost and MFU ghost, data and metadata. The previous values are kept between passes.
L4494–L4495 arc_meta, the metadata share: up with metadata ghost hits, down with data ghost hits, the downward step divided by zfs_arc_meta_balance / 100, 5 by default.
L4496 arc_pd, the MRU share of data: up with MRU-ghost data hits, down with MFU-ghost data hits. The figure’s gauge.
L4497 arc_pm, the same for metadata.

These three replace arc_p. They are fractions of 2³², and start at 1/4 for metadata and 1/2 for each MRU share. The first argument after the fraction is the ghost target size of the previous pass, so a hit moves a fraction by about its size against the size of the ghost lists:

arc_evict_adj Excerpt of module/zfs/arc.c, lines 4405–4442, OpenZFS zfs-2.4.4. View on GitHub

static uint64_t
arc_evict_adj(uint64_t frac, uint64_t total, uint64_t up, uint64_t down,
    uint_t balance)
{
	if (total < 32 || up + down == 0)
		return (frac);

	/*
	 * We should not have more ghost hits than ghost size, but they may
	 * get close.  To avoid overflows below up/down should not be bigger
	 * than 1/5 of total.  But to limit maximum adjustment speed restrict
	 * it some more.
	 */
	if (up + down >= total / 16) {
		uint64_t scale = (up + down) / (total / 32);
		up /= scale;
		down /= scale;
	}

	/* Get maximal dynamic range by choosing optimal shifts. */
	int s = highbit64(total);
	s = MIN(64 - s, 32);

	ASSERT3U(frac, <=, 1ULL << 32);
	uint64_t ofrac = (1ULL << 32) - frac;

	if (frac >= 4 * ofrac)
		up /= frac / (2 * ofrac + 1);
	up = (up << s) / (total >> (32 - s));
	if (ofrac >= 4 * frac)
		down /= ofrac / (2 * frac + 1);
	down = (down << s) / (total >> (32 - s));
	down = down * 100 / balance;

	ASSERT3U(up, <=, (1ULL << 32) - frac);
	ASSERT3U(down, <=, frac);
	return (frac + up - down);
}

L4409–L4410 No change before there is any ghost target (the figure’s first pass) or without hits.
L4417–L4421 Hits of 1/16 of the ghost total or more are scaled down to about 1/32 of it: one pass moves a fraction by at most about 1/32 of its range. In the figure, one ghost hit is enough to reach that limit.
L4424–L4426 A shift chosen so the division keeps as many bits as possible.
L4428–L4435 Near 0 or 1 (one side four times the other), the step towards that end is divided further: a fraction approaches its ends ever more slowly.
L4436 The downward step divided by balance / 100: 1 for arc_pd.

The figure’s first ghost hit, worked through: arc_pd = 2³¹, one half; ghost targets of 8 blocks, total = 2²⁰ bytes; one hit of 128 KiB, 2¹⁷. That is over 1/16 of the total, so it is scaled by 4 to 2¹⁵; the shift is 32; up = 2⁴⁷ / 2²⁰ = 2²⁷, and arc_pd becomes 2³¹ + 2²⁷, 53.125%. The MRU target goes from 8 to 8.5 blocks. A hit in the MFU ghost list takes the same 2²⁷ away.

When a pass runs. Not on a hit: a hit allocates nothing. Allocating the data of a miss may wake the eviction thread, once the cache is over arc_c by more than zfs_max_recordsize, 16 MiB on 64-bit systems. The thread runs arc_evict and goes on while it evicts something and the cache is still over arc_c.

arc_c itself is another control. It grows by the size of each allocation, at least 128 KiB, while the cache is within 32 MiB of it (twice the largest block size), up to arc_c_max, and shrinks under memory pressure. Ghost hits move the shares of arc_c, never arc_c. The figure keeps it at its maximum.

Coda: the L2ARC

A cache device can extend the ARC: in the words of its design comment, “a cache layer in-between main memory and disk”, on solid-state disks for instance. The same comment says how it is fed:

Level 2 ARC Excerpt of module/zfs/arc.c, lines 8261–8274, OpenZFS zfs-2.4.4. View on GitHub

 * 1. There is no eviction path from the ARC to the L2ARC.  Evictions from
 * the ARC behave as usual, freeing buffers and placing headers on ghost
 * lists.  The ARC does not send buffers to the L2ARC during eviction as
 * this would add inflated write latencies for all ARC memory pressure.
 *
 * 2. The L2ARC attempts to cache data from the ARC before it is evicted.
 * It does this by periodically scanning buffers from the eviction-end of
 * the MFU and MRU ARC lists, copying them to the L2ARC devices if they are
 * not already there. It scans until a headroom of buffers is satisfied,
 * which itself is a buffer for ARC eviction. If a compressible buffer is
 * found during scanning and selected for writing to an L2ARC device, we
 * temporarily boost scanning headroom during the next scan cycle to make
 * sure we adapt to compression effects (which might significantly reduce
 * the data volume we write to L2ARC). The thread that does this is

L8261–L8264 Eviction does not write to the cache device: it frees data and leaves headers on the ghost lists, as above.
L8266–L8270 A feed thread copies blocks from the eviction end of MRU and MFU before they are evicted.

That thread, l2arc_feed_thread, wakes about once a second and reads the lists from their tails. A ghost header whose block is on the cache device is not destroyed when trimmed: it stays, as L2C only, and a read of it goes back to MRU.

What the figure leaves out

The figure runs the functions above over data blocks only, all of 128 KiB and uncompressed: the metadata lists are empty, so the metadata terms of the pass are zero, and arc_meta and arc_pm, which then change no data target, are not drawn. Each state is one list; the code spreads headers over sublists by hash and evicts them in turn, so its order is close to, not exactly, the order of last use. A pass runs right after each miss that puts the cache over arc_c, rather than in a thread woken 16 MiB later, which at the figure’s scale would be eight caches. arc_c is fixed, the clock is logical, and each block is released as soon as it is read. No prefetch (prefetched blocks also have a minimum lifetime), no uncached or dirty buffers, no compressed or encrypted copies, no L2ARC.

1 Read, scan, read again

What the last action did

The idea, at three depths

In one sentence

In one paragraph

In detail

Coda: the L2ARC

What the figure leaves out