Sala 8

El ARC

Una caché en memoria tiene que elegir qué olvida. Si olvida el bloque usado menos recientemente, como una caché LRU, una sola lectura grande, una copia de seguridad o el recorrido de un archivo grande, expulsa todo lo que se estaba reutilizando: cada bloque recorrido es más reciente que el conjunto de trabajo. Si olvida el usado con menos frecuencia, como una caché LFU, los bloques que estaban calientes ayer se quedan, por fríos que estén hoy.

El ARC, la caché de ZFS, guarda los bloques vistos una vez recientemente en una lista, MRU, y los bloques vistos al menos dos veces en otra, MFU, de modo que un recorrido solo pasa por la primera. Y recuerda lo que acaba de expulsar: una lista fantasma conserva la cabecera de cada bloque expulsado, sin sus datos. Una lectura que encuentra un fantasma es un fallo que una lista más grande habría convertido en acierto, y el ARC desplaza su equilibrio hacia esa lista.

1 Leer, recorrer, volver a leer

La caché de abajo contiene 16 bloques de 128 KiB: es su tamaño objetivo, arc_c. Empieza con un conjunto caliente, H1 a H6, leído dos veces con un segundo de intervalo, así que los seis están en MFU. Cada lista va de su cabeza, el bloque más reciente, a su cola, que se expulsa primero. Lee un bloque nuevo, recorre doce nuevos, vuelve a leer el conjunto caliente, o selecciona cualquier bloque para leerlo, en caché, fantasma u olvidado. Un reloj avanza un segundo antes de cada acción, o 10 ms si lo eliges.

Prueba primero un recorrido: pasa por MRU, y el conjunto caliente se queda. Después lee un bloque de la lista MRU fantasma y observa cómo suben arc_pd y el objetivo de MRU. Vuelve a leer algunos bloques del recorrido para promoverlos, lee bloques nuevos hasta que MFU ceda un bloque caliente, y vuelve a leer ese bloque desde la lista MFU fantasma: el equilibrio se mueve en sentido contrario. Por último, a 10 ms, lee dos veces el mismo bloque nuevo.

MRU 0 bloques y MFU 6, de 16; MRU fantasma 0 cabeceras y MFU fantasma 0. arc_pd 50 %: el objetivo de MRU es 8 bloques de 16.

MRU fantasma

0 cabeceras, sin datos · como máximo 0 bloques · aciertos fantasma 0 KiB

vacía

MRU

0 bloques, datos en memoria

vacía

MFU

6 bloques, datos en memoria

  1. H6
  2. H5
  3. H4
  4. H3
  5. H2
  6. H1

MFU fantasma

0 cabeceras, sin datos · como máximo 0 bloques · aciertos fantasma 0 KiB

vacía

Olvidados

cabeceras destruidas: el ARC ya no conoce estos bloques

vacía

Versión en texto de esta figura

arc_c son 16 bloques de 128 KiB. Reloj: 2,01 s. Cada lista de la cabeza (el más reciente) a la cola (el primero en ser expulsado):

  1. MRU fantasma, 0: vacía.
  2. MRU, 0: vacía.
  3. MFU, 6: H6, H5, H4, H3, H2, H1.
  4. MFU fantasma, 0: vacía.

Olvidados (cabeceras destruidas), del más reciente al más antiguo: vacía.

arc_pd 50 %: el objetivo de MRU es 8 bloques de 16. Aciertos fantasma hasta ahora: MRU fantasma 0 KiB, MFU fantasma 0 KiB.

La idea, a tres profundidades

En una frase

El ARC separa los bloques vistos una vez de los vistos dos veces, recuerda las cabeceras de lo que ha expulsado, y cuando una lectura encuentra uno de esos fantasmas da más espacio a la lista que habría conservado el bloque.

En un párrafo

Un bloque nuevo entra en MRU. Una segunda lectura más de ARC_MINTIME, unos 62 ms, después de la primera lo promueve a MFU; las relecturas dentro de una misma ráfaga cuentan como un solo uso. Cuando la caché supera arc_c, una pasada de expulsión toma bloques de la cola de MRU si MRU está por encima de su parte, y de la cola de MFU en caso contrario. Un bloque expulsado pierde sus datos, pero su cabecera pasa a la lista fantasma correspondiente, que puede contener la mitad de lo que contienen las otras listas. Leer un fantasma es un fallo: el bloque se vuelve a leer del disco, pasa a MFU, y su tamaño cuenta como un acierto fantasma. En OpenZFS 2.4.4 ya no existe arc_p. Las partes son fracciones en coma fija, arc_pd para la parte de MRU en los datos, arc_pm para los metadatos y arc_meta entre ambos, y la pasada de expulsión siguiente las desplaza según los aciertos fantasma que encuentra: hacia arriba por aciertos en la lista MRU fantasma, hacia abajo por aciertos en la lista MFU fantasma, como mucho alrededor de 1/32 cada vez.

En detalle

Estados y cabeceras. Un bloque en el ARC tiene una cabecera, arc_buf_hdr_t, cuya clave son el DVA y el txg de nacimiento del bloque, y la cabecera está en uno de siete estados: anon, MRU, MRU fantasma, MFU, MFU fantasma, solo L2C y sin caché. La figura dibuja cuatro, como listas. La cabecera registra su estado, el momento de su último acceso, b_arc_access, y contadores de aciertos. Un bloque nuevo pasa de anon a MRU.

Visto una vez, visto dos veces. Un acierto en un bloque de MRU:

arc_access Extracto de module/zfs/arc.c, líneas 5398–5428, OpenZFS zfs-2.4.4. Ver en 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);
		}
  1. L5403–L5406 Un acierto en un bloque cuya lectura sigue en curso solo actualiza su momento. En la figura, cada lectura termina al instante.
  2. L5407–L5408 El acierto se cuenta en la cabecera.
  3. L5414–L5417 Un bloque leído primero por precarga no se promueve con la lectura bajo demanda que sigue. La figura no tiene precarga.
  4. L5423–L5428 Más de ARC_MINTIME después de b_arc_access: a MFU, y el momento se actualiza. Si no, nada se mueve, ni siquiera b_arc_access, así que una serie de relecturas con menos de 62 ms de intervalo se mide desde la primera. La comparación es estricta: 62 ms exactos no promueven.

ARC_MINTIME es hz >> 4, «62 ms». Un acierto en un bloque de MFU se queda en MFU y actualiza b_arc_access.

Cabeza y cola. arc_read llama a arc_access en un acierto, y en un fallo antes de asignar los datos. Mientras un lector retiene un bloque, su cabecera está fuera de su lista; la última liberación la devuelve, a la cabeza, y la expulsión toma de la cola. Así, cada lista está ordenada por último uso. En la figura, el lector suelta cada bloque al instante.

La expulsión conserva la cabecera. Cuando un bloque se expulsa de MRU o de MFU:

arc_evict_hdr Extracto de module/zfs/arc.c, líneas 3876–3891, OpenZFS zfs-2.4.4. Ver en 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);
  1. L3876–L3880 Los datos se liberan.
  2. L3882 La cabecera pasa al estado fantasma elegido más arriba: de MRU a MRU fantasma, de MFU a MFU fantasma. En la figura se desliza a la cabeza de la lista fantasma, sin datos.
  3. L3884–L3889 Solo se destruye la cabecera de un búfer sin caché. Una cabecera fantasma se queda en la tabla hash, así que una lectura posterior del mismo bloque la encuentra.

Qué lista cede un bloque. La pasada de expulsión, tras sus pasos de metadatos:

arc_evict Extracto de module/zfs/arc.c, líneas 4527–4556, OpenZFS zfs-2.4.4. Ver en 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;
  1. L4527–L4541 Primero los metadatos: los de MRU hasta su objetivo, luego los de MFU hasta la parte de los metadatos. La figura solo contiene bloques de datos, así que estos pasos no expulsan nada.
  2. L4543–L4550 Los datos de MRU, hasta su objetivo w = wt · arc_pd, y no más de lo que la caché supera arc_c (asize - ac). Un MRU en su objetivo o por debajo no cede nada.
  3. L4552–L4556 Los datos de MFU ceden el exceso que quede.

wt es lo que se puede expulsar, el propio arc_c cuando todos los bloques de la caché son expulsables, como en la figura. Cada paso expulsa como mucho lo que contiene la lista, y nada para una cantidad negativa, desde la cola, hasta haber expulsado al menos la cantidad pedida. Así que MRU no se reduce a su objetivo de una vez: cede su cola solo mientras la caché supera arc_c. El primer recorrido de la figura lo muestra: MRU conserva 10 bloques frente a un objetivo de 8, porque cada bloque nuevo deja la caché solo un bloque por encima.

Cuánto duran los fantasmas. Al final de la misma pasada:

arc_evict Extracto de module/zfs/arc.c, líneas 4558–4587, OpenZFS zfs-2.4.4. Ver en 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);
  1. L4569–L4572 La lista fantasma de los datos de MRU puede contener la mitad de las otras tres listas vivas. La figura no tiene listas de metadatos, así que es la mitad de MFU.
  2. L4579–L4582 La lista fantasma de los datos de MFU: la mitad de MRU en la figura.

Una lista fantasma no tiene el tamaño de la caché. En la figura, con un MFU vacío, la lista MRU fantasma no contiene nada. Una cabecera recortada de una lista fantasma se destruye; la figura la muestra como olvidada, y volver a leer el bloque es, para el ARC, un bloque nuevo.

Un acierto fantasma. Leer un bloque cuya cabecera está en la lista MRU fantasma:

arc_access Extracto de module/zfs/arc.c, líneas 5429–5449, OpenZFS zfs-2.4.4. Ver en 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);
  1. L5432–L5435 «Would we have bigger MRU, it would be an MRU hit»: un acierto fantasma es un fallo que una lista más grande habría evitado. Los datos se vuelven a leer del disco.
  2. L5437–L5441 Se cuenta en la cabecera, y el tamaño del bloque (su tamaño comprimido si está comprimido) se suma al contador de aciertos de la lista MRU fantasma. La figura muestra el contador bajo cada lista fantasma.
  3. L5442–L5449 De vuelta a la caché, en MFU, puesto que es su segundo uso; en MRU si el bloque venía de una precarga.

Un acierto en MFU fantasma hace lo mismo con el contador de la lista MFU fantasma y vuelve a MFU. arc_access no cambia ningún objetivo: solo suma bytes. La pasada de expulsión los lee.

De los aciertos fantasma a un equilibrio. Al principio de cada pasada:

arc_evict Extracto de module/zfs/arc.c, líneas 4479–4497, OpenZFS zfs-2.4.4. Ver en 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);
  1. L4480–L4491 Los bytes de aciertos fantasma desde la pasada anterior, de cuatro tipos: MRU fantasma y MFU fantasma, datos y metadatos. Los valores anteriores se conservan entre pasadas.
  2. L4494–L4495 arc_meta, la parte de los metadatos: sube con los aciertos fantasma de metadatos, baja con los de datos, y el paso hacia abajo se divide entre zfs_arc_meta_balance / 100, 5 por defecto.
  3. L4496 arc_pd, la parte de MRU en los datos: sube con los aciertos fantasma de datos en MRU, baja con los de MFU. El indicador de la figura.
  4. L4497 arc_pm, lo mismo para los metadatos.

Estas tres sustituyen a arc_p. Son fracciones de 232, y empiezan en 1/4 para los metadatos y en 1/2 para cada parte de MRU. El primer argumento después de la fracción es el tamaño objetivo de los fantasmas en la pasada anterior, de modo que un acierto desplaza una fracción aproximadamente en proporción a su tamaño frente al de las listas fantasma:

arc_evict_adj Extracto de module/zfs/arc.c, líneas 4405–4442, OpenZFS zfs-2.4.4. Ver en 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);
}
  1. L4409–L4410 Ningún cambio mientras no haya objetivo fantasma (la primera pasada de la figura) o si no hay aciertos.
  2. L4417–L4421 Los aciertos de 1/16 del total fantasma o más se reducen a alrededor de 1/32 de este: una pasada desplaza una fracción como mucho alrededor de 1/32 de su rango. En la figura, un solo acierto fantasma basta para alcanzar ese límite.
  3. L4424–L4426 Un desplazamiento elegido para que la división conserve tantos bits como sea posible.
  4. L4428–L4435 Cerca de 0 o de 1 (un lado cuatro veces el otro), el paso hacia ese extremo se divide aún más: una fracción se acerca a sus extremos cada vez más despacio.
  5. L4436 El paso hacia abajo dividido entre balance / 100: 1 para arc_pd.

El primer acierto fantasma de la figura, paso a paso: arc_pd = 231, la mitad; objetivos fantasma de 8 bloques, total = 220 bytes; un acierto de 128 KiB, 217. Es más de 1/16 del total, así que se divide entre 4, a 215; el desplazamiento es 32; up = 247 / 220 = 227, y arc_pd pasa a 231 + 227, 53,125 %. El objetivo de MRU pasa de 8 a 8,5 bloques. Un acierto en la lista MFU fantasma resta esos mismos 227.

Cuándo se ejecuta una pasada. No en un acierto: un acierto no asigna nada. Asignar los datos de un fallo puede despertar el hilo de expulsión, una vez que la caché supera arc_c en más de zfs_max_recordsize, 16 MiB en los sistemas de 64 bits. El hilo ejecuta arc_evict y sigue mientras expulsa algo y la caché sigue por encima de arc_c.

El propio arc_c es otro control. Crece en el tamaño de cada asignación, al menos 128 KiB, mientras la caché está a menos de 32 MiB de él (el doble del mayor tamaño de bloque), hasta arc_c_max, y se reduce bajo presión de memoria. Los aciertos fantasma desplazan las partes de arc_c, nunca arc_c. La figura lo mantiene en su máximo.

Coda: el L2ARC

Un dispositivo de caché puede ampliar el ARC: en palabras de su comentario de diseño, «a cache layer in-between main memory and disk», en discos de estado sólido, por ejemplo. El mismo comentario explica cómo se alimenta:

Level 2 ARC Extracto de module/zfs/arc.c, líneas 8261–8274, OpenZFS zfs-2.4.4. Ver en 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
  1. L8261–L8264 La expulsión no escribe en el dispositivo de caché: libera los datos y deja las cabeceras en las listas fantasma, como más arriba.
  2. L8266–L8270 Un hilo de alimentación copia bloques del extremo de expulsión de MRU y de MFU antes de que se expulsen.

Ese hilo, l2arc_feed_thread, se despierta aproximadamente una vez por segundo y lee las listas desde la cola. Una cabecera fantasma cuyo bloque está en el dispositivo de caché no se destruye al recortarse: se queda, como solo L2C, y una lectura de ella vuelve a MRU.

Lo que la figura deja fuera

La figura ejecuta las funciones de arriba solo sobre bloques de datos, todos de 128 KiB y sin comprimir: las listas de metadatos están vacías, así que los términos de metadatos de la pasada valen cero, y arc_meta y arc_pm, que entonces no cambian ningún objetivo de datos, no se dibujan. Cada estado es una sola lista; el código reparte las cabeceras en sublistas según un hash y las expulsa por turnos, así que su orden se acerca al del último uso, sin ser exactamente ese. Una pasada se ejecuta justo después de cada fallo que deja la caché por encima de arc_c, en lugar de en un hilo despertado 16 MiB más tarde, lo que a la escala de la figura serían ocho cachés. arc_c es fijo, el reloj es lógico, y cada bloque se libera en cuanto se lee. Sin precarga (los bloques precargados también tienen una vida mínima), sin búferes sin caché ni sucios, sin copias comprimidas o cifradas, sin L2ARC.