Uberblok

Salle 7

Instantanés et clones

Un instantané doit figer d’un coup tout un système de fichiers, un téraoctet aussi bien qu’un kilooctet, sans ralentir les écritures qui suivent. Le prendre est la moitié facile. La moitié difficile vient à chaque réécriture et à chaque suppression qui suivent dans le système de fichiers vivant : l’ancien bloc sert-il encore à un instantané, ou sa place peut-elle être réutilisée ? Interroger chaque instantané voudrait dire les parcourir. Un compteur de références par bloc voudrait dire mettre à jour un compteur pour chaque bloc à chaque instantané.

ZFS ne fait ni l’un ni l’autre. Chaque pointeur de bloc enregistre le txg où le bloc est né. Le système de fichiers vivant retient le txg de son dernier instantané. Un bloc né après cet instantané ne peut appartenir à aucun instantané : il est libéré ; un bloc né avant ou pendant peut y appartenir : il est gardé, dans une deadlist. Une seule comparaison de deux nombres.

1 Écrire, prendre un instantané, synchroniser

fs est un système de fichiers de quatre blocs de données, A à D, sous un bloc racine, l’objset sur lequel pointe son ds_bp. Chaque bloc affiche son txg de naissance : A8 est né au txg 8. La figure s’ouvre après trois txg : A, B et C écrits au txg 8, l’instantané fs@s1 pris au txg 9, A réécrit au txg 10. Préparez des modifications dans le txg ouvert, prenez un instantané, clonez-en un ou détruisez-en un, puis synchronisez : chaque bloc que la synchronisation abandonne montre la comparaison et l’endroit où il va. Sélectionnez n’importe quel bloc pour voir quels instantanés le détiennent.

fs

tête, modifiableds_prev_snap_txg 9 (fs@s1)
ds_bp →R10A10B8C8D : vide
deadlist
  • > 0vide
  • > 1A8R8

fs@s1

instantané du txg 9ds_prev_snap_txg 1 ($ORIGIN)
ds_bp →R8A8B8C8D : vide
deadlist
  • > 0vide
Version texte de cette figure

Le txg ouvert est le 11. Les datasets, dans l’ordre :

  1. fs, tête, modifiable : ds_prev_snap_txg 9 ; ds_bp pointe sur la R10, la racine, née au txg 10 ; blocs de données : A10, né au txg 10, B8, né au txg 8, C8, né au txg 8, D : vide. Deadlist : entrée > 0 : vide ; entrée > 1 : A8, né au txg 8 et R8, la racine, née au txg 8.
  2. fs@s1, instantané du txg 9 : ds_prev_snap_txg 1 ; ds_bp pointe sur la R8, la racine, née au txg 8 ; blocs de données : A8, né au txg 8, B8, né au txg 8, C8, né au txg 8, D : vide. Deadlist : entrée > 0 : vide.

Libérés jusqu’ici : R7, la racine, née au txg 7 (au txg 8).

L’idée, à trois profondeurs

En une phrase

Chaque bloc porte le txg de sa naissance : quand le système de fichiers vivant abandonne un bloc, une seule comparaison avec le txg de son dernier instantané décide de le libérer, ou de le garder dans une deadlist pour les instantanés qui le détiennent encore.

En un paragraphe

Un instantané est un nouvel enregistrement de dataset qui copie un seul pointeur de bloc, ds_bp, la racine de l’arbre du système de fichiers, et rien d’autre : tous les blocs en dessous sont désormais partagés. La copie sur écriture ne modifie plus jamais ces blocs ; elle en écrit de nouveaux, nés dans des txg ultérieurs, et « tue » les anciens. dsl_dataset_block_kill compare la naissance de l’ancien bloc au ds_prev_snap_txg du système de fichiers, le txg de son dernier instantané. Né après, le bloc n’appartient qu’au système de fichiers vivant : il est libéré. Né avant ou pendant, le dernier instantané le détient : il va dans la deadlist. La deadlist est découpée en entrées par les txg des instantanés précédents : elle dit entre quels instantanés successifs chaque bloc mort est né. C’est ce qui rend la destruction d’un instantané peu coûteuse : les blocs que lui seul détenait sont des entrées entières de la deadlist du dataset suivant, libérées sans lire un seul pointeur de bloc. Un clone est un dataset modifiable qui part du ds_bp d’un instantané, avec le txg de cet instantané comme ds_prev_snap_txg : la même comparaison garde les blocs qu’il partage avec son origine et libère les siens.

En détail

La naissance. Le txg de naissance d’un bloc est fixé à son allocation : metaslab_alloc se termine par BP_SET_BIRTH(bp, txg, 0), et l’écriture lui passe le txg auquel elle appartient. Un pointeur de bloc a deux mots de naissance, logique et physique ; ils ne diffèrent que pour la déduplication, le clonage de blocs et les blocs réécrits, et la valeur comparée ci-dessous est BP_GET_BIRTH, la naissance logique pour un bloc ordinaire.

Libérer tout de suite, ou la deadlist. Voici toute la décision.

dsl_dataset_block_kill Extrait de module/zfs/dsl_dataset.c, lignes 294–316, OpenZFS zfs-2.4.4. Voir sur GitHub 
	if (BP_GET_BIRTH(bp) > dsl_dataset_phys(ds)->ds_prev_snap_txg) {
		int64_t delta;

		/*
		 * Put blocks that would create IO on the pool's deadlist for
		 * dsl_process_async_destroys() to find. This is to prevent
		 * zio_free() from creating a ZIO_TYPE_FREE IO for them, which
		 * are very heavy and can lead to out-of-memory conditions if
		 * something tries to free millions of blocks on the same txg.
		 */
		boolean_t defer = spa_version(spa) >= SPA_VERSION_DEADLISTS &&
		    (BP_IS_GANG(bp) || BP_GET_DEDUP(bp) ||
		    brt_maybe_exists(spa, bp));

		if (defer) {
			dprintf_bp(bp, "putting on free list: %s", "");
			bpobj_enqueue(&ds->ds_dir->dd_pool->dp_free_bpobj,
			    bp, B_FALSE, tx);
		} else {
			dprintf_bp(bp, "freeing ds=%llu",
			    (u_longlong_t)ds->ds_object);
			dsl_free(tx->tx_pool, tx->tx_txg, bp);
		}
  1. L294 La comparaison. ds_prev_snap_txg est le txg du dernier instantané du dataset. Le test est strict : un bloc né dans ce txg même est détenu par cet instantané.
  2. L304–L311 Les blocs gang, dédupliqués ou peut-être clonés sont mis dans la liste à libérer du pool au lieu d’être libérés sur place, parce que les libérer coûte des entrées-sorties. Le résultat est le même : aucun instantané ne les détient.
  3. L312–L315 Le cas ordinaire : dsl_free, dans ce txg. La figure grise le bloc sous « Libérés ».

Sinon, dans la branche else, le bloc va dans la deadlist. Trois appelants tuent des blocs, tous pendant la synchronisation d’un txg : dbuf_write_done quand un bloc de données ou un bloc indirect a été réécrit, dmu_objset_write_done pour le bloc d’objset sur lequel pointe ds_bp, réécrit à chaque txg où le dataset change, et free_blocks pour une suppression ou une troncature. La figure dessine cet objset et les blocs indirects comme une seule racine, tuée selon la même règle. Les deux rappels d’écriture mettent un bloc destiné à la deadlist dans une liste en attente que dsl_dataset_sync_done vide avant les tâches de synchronisation du txg : même résultat, quelques lignes plus loin.

Un instantané copie un pointeur de bloc.

dsl_dataset_snapshot_sync_impl Extrait de module/zfs/dsl_dataset.c, lignes 1760–1785, OpenZFS zfs-2.4.4. Voir sur GitHub 
	dsobj = dmu_object_alloc(mos, DMU_OT_DSL_DATASET, 0,
	    DMU_OT_DSL_DATASET, sizeof (dsl_dataset_phys_t), tx);
	VERIFY0(dmu_bonus_hold(mos, dsobj, FTAG, &dbuf));
	dmu_buf_will_dirty(dbuf, tx);
	dsphys = dbuf->db_data;
	memset(dsphys, 0, sizeof (dsl_dataset_phys_t));
	dsphys->ds_dir_obj = ds->ds_dir->dd_object;
	dsphys->ds_fsid_guid = unique_create();
	(void) random_get_pseudo_bytes((void*)&dsphys->ds_guid,
	    sizeof (dsphys->ds_guid));
	dsphys->ds_prev_snap_obj = dsl_dataset_phys(ds)->ds_prev_snap_obj;
	dsphys->ds_prev_snap_txg = dsl_dataset_phys(ds)->ds_prev_snap_txg;
	dsphys->ds_next_snap_obj = ds->ds_object;
	dsphys->ds_num_children = 1;
	dsphys->ds_creation_time = gethrestime_sec();
	dsphys->ds_creation_txg = crtxg;
	dsphys->ds_deadlist_obj = dsl_dataset_phys(ds)->ds_deadlist_obj;
	dsphys->ds_referenced_bytes = dsl_dataset_phys(ds)->ds_referenced_bytes;
	dsphys->ds_compressed_bytes = dsl_dataset_phys(ds)->ds_compressed_bytes;
	dsphys->ds_uncompressed_bytes =
	    dsl_dataset_phys(ds)->ds_uncompressed_bytes;
	dsphys->ds_flags = dsl_dataset_phys(ds)->ds_flags;
	rrw_enter(&ds->ds_bp_rwlock, RW_READER, FTAG);
	dsphys->ds_bp = dsl_dataset_phys(ds)->ds_bp;
	rrw_exit(&ds->ds_bp_rwlock, FTAG);
	dmu_buf_rele(dbuf, FTAG);
  1. L1760–L1761 Un nouvel objet dans le MOS, les métadonnées propres du pool : l’enregistrement de dataset de l’instantané.
  2. L1770–L1773 Il prend le lien de la tête vers l’instantané précédent et son ds_prev_snap_txg, pointe vers la tête, et commence avec un enfant, son successeur.
  3. L1775 Son txg de création est le txg en cours de synchronisation.
  4. L1776 La deadlist de la tête devient celle de l’instantané, telle quelle.
  5. L1783 Le pointeur de bloc racine est copié. Cette seule copie fait que l’instantané partage tous ses blocs avec la tête. Rien n’est lu ni écrit dans l’arbre : la figure ne montre aucun nouveau bloc pour un instantané.

La nouvelle deadlist de la tête. Plus bas dans la même fonction, la tête reçoit une deadlist à elle.

dsl_dataset_snapshot_sync_impl Extrait de module/zfs/dsl_dataset.c, lignes 1830–1839, OpenZFS zfs-2.4.4. Voir sur GitHub 
	dmu_buf_will_dirty(ds->ds_dbuf, tx);
	dsl_dataset_phys(ds)->ds_deadlist_obj =
	    dsl_deadlist_clone(&ds->ds_deadlist, UINT64_MAX,
	    dsl_dataset_phys(ds)->ds_prev_snap_obj, tx);
	dsl_deadlist_close(&ds->ds_deadlist);
	VERIFY0(dsl_deadlist_open(&ds->ds_deadlist, mos,
	    dsl_dataset_phys(ds)->ds_deadlist_obj));
	dsl_deadlist_add_key(&ds->ds_deadlist,
	    dsl_dataset_phys(ds)->ds_prev_snap_txg, tx);
	dsl_bookmark_snapshotted(ds, tx);
  1. L1831–L1833 dsl_deadlist_clone sans limite : une entrée vide pour chaque clé de la deadlist que l’instantané vient de prendre.
  2. L1837–L1838 Plus une clé : le ds_prev_snap_txg de la tête, qui vaut encore ici le txg de l’instantané précédent. Il ne prend le txg de cet instantané qu’ensuite.

Ainsi, après des instantanés aux txg t1 < t2 < … < tn, la deadlist de la tête a ses clés de départ plus t1 à t(n−1), et son ds_prev_snap_txg vaut tn. Chaque instantané garde la deadlist que la tête avait jusqu’à lui : les blocs tués entre l’instantané précédent et celui-ci. Autrement dit, des blocs que l’instantané précédent détient et que celui-ci ne détient pas ; la deadlist d’un instantané n’est pas « les blocs qui n’appartiennent qu’à lui ».

Où va un bloc mort.

dsl_deadlist_insert Extrait de module/zfs/dsl_deadlist.c, lignes 487–501, OpenZFS zfs-2.4.4. Voir sur GitHub 
	dle_tofind.dle_mintxg = BP_GET_BIRTH(bp);
	dle = avl_find(&dl->dl_tree, &dle_tofind, &where);
	if (dle == NULL)
		dle = avl_nearest(&dl->dl_tree, where, AVL_BEFORE);
	else
		dle = AVL_PREV(&dl->dl_tree, dle);

	if (dle == NULL) {
		zfs_panic_recover("blkptr at %p has invalid BLK_BIRTH %llu",
		    bp, (longlong_t)BP_GET_BIRTH(bp));
		dle = avl_first(&dl->dl_tree);
	}

	ASSERT3P(dle, !=, NULL);
	dle_enqueue(dl, dle, bp, bp_freed, tx);
  1. L487–L492 Une deadlist est un arbre d’entrées, chacune une liste de pointeurs de bloc rangée sous une clé, un txg qui « n’est pas inclus ». On cherche la naissance : si elle tombe exactement sur une clé, on prend l’entrée d’avant, sinon l’entrée la plus proche avant. Dans les deux cas, l’entrée dont la clé est la plus grande strictement en dessous de la naissance.
  2. L494–L498 Une naissance inférieure ou égale à toutes les clés ne peut pas arriver sur un pool sain : elle est signalée, et le bloc va dans la première entrée.

D’où partent les clés. Un système de fichiers est créé à partir de l’instantané $ORIGIN du pool, créé à partir d’un dataset vide avec le txg de création 1. En suivant les extraits, un nouveau système de fichiers part avec un ds_prev_snap_txg de 1 et une deadlist à une clé, 0, et son premier instantané ajoute la clé 1. Tout bloc écrit par un utilisateur naît après le txg 1 : l’entrée 0 reste vide, l’entrée 1 recueille ce qui est né avant le premier instantané. Ce sont les entrées > 0 et > 1 de la figure.

Le même txg. Un instantané est une tâche de synchronisation, et le txg écrit d’abord ses données.

dsl_pool_sync Extrait de module/zfs/dsl_pool.c, lignes 747–760, OpenZFS zfs-2.4.4. Voir sur GitHub 
	/*
	 * Sync the datasets again to push out the changes due to
	 * userspace updates.  This must be done before we process the
	 * sync tasks, so that any snapshots will have the correct
	 * user accounting information (and we won't get confused
	 * about which blocks are part of the snapshot).
	 */
	rio = zio_root(dp->dp_spa, NULL, NULL, ZIO_FLAG_MUSTSUCCEED);
	while ((ds = txg_list_remove(&dp->dp_dirty_datasets, txg)) != NULL) {
		objset_t *os = ds->ds_objset;

		ASSERT(list_link_active(&ds->ds_synced_link));
		dmu_buf_rele(ds->ds_dbuf, ds);
		dsl_dataset_sync(ds, rio, tx);
  1. L747–L753 Chaque dataset modifié est écrit avant que les tâches de synchronisation ne s’exécutent, pour ne pas se tromper sur les blocs qui font partie de l’instantané (we won’t get confused about which blocks are part of the snapshot). Les tâches s’exécutent à la fin.

Deux conséquences, toutes deux dans la figure. Un bloc écrit dans le même txg qu’un instantané est dans cet instantané : né au txg T, détenu par l’instantané du txg T, d’où le test strict. Et un bloc tué dans le txg d’un instantané n’y est pas : sa mort a été décidée par rapport à l’instantané précédent. Un seul instantané d’un dataset par txg : un second est refusé, EAGAIN.

Un clone part du pointeur de bloc d’un instantané.

dsl_dataset_create_sync_dd Extrait de module/zfs/dsl_dataset.c, lignes 1213–1227, OpenZFS zfs-2.4.4. Voir sur GitHub 
	} else {
		dsl_dataset_t *ohds; /* head of the origin snapshot */

		dsphys->ds_prev_snap_obj = origin->ds_object;
		dsphys->ds_prev_snap_txg =
		    dsl_dataset_phys(origin)->ds_creation_txg;
		dsphys->ds_referenced_bytes =
		    dsl_dataset_phys(origin)->ds_referenced_bytes;
		dsphys->ds_compressed_bytes =
		    dsl_dataset_phys(origin)->ds_compressed_bytes;
		dsphys->ds_uncompressed_bytes =
		    dsl_dataset_phys(origin)->ds_uncompressed_bytes;
		rrw_enter(&origin->ds_bp_rwlock, RW_READER, FTAG);
		dsphys->ds_bp = dsl_dataset_phys(origin)->ds_bp;
		rrw_exit(&origin->ds_bp_rwlock, FTAG);
  1. L1216–L1218 L’instantané précédent du clone est son origine, et son ds_prev_snap_txg le txg de création de l’origine.
  2. L1225–L1227 Son ds_bp est celui de l’origine : comme un instantané, un clone commence par un pointeur de bloc copié.

Ensuite l’origine gagne un enfant, la deadlist du clone commence avec les clés inférieures au txg de l’origine, et l’origine est enregistrée dans le répertoire du clone (en mémoire, dd_origin_txg). Une écriture dans le clone passe par le même dsl_dataset_block_kill, avec le ds_prev_snap_txg du clone : un bloc écrit par le clone est né après l’origine et libéré quand le clone l’abandonne ; un bloc né avant l’origine ou pendant est partagé avec elle et va dans la deadlist du clone. Le clone diverge par txg de naissance, et rien n’est copié.

Détruire un instantané.

dsl_destroy_snapshot_sync_impl Extrait de module/zfs/dsl_destroy.c, lignes 387–424, OpenZFS zfs-2.4.4. Voir sur GitHub 
	dmu_buf_will_dirty(ds_next->ds_dbuf, tx);
	dsl_dataset_phys(ds_next)->ds_prev_snap_obj =
	    dsl_dataset_phys(ds)->ds_prev_snap_obj;
	dsl_dataset_phys(ds_next)->ds_prev_snap_txg =
	    dsl_dataset_phys(ds)->ds_prev_snap_txg;
	ASSERT3U(dsl_dataset_phys(ds)->ds_prev_snap_txg, ==,
	    ds_prev ? dsl_dataset_phys(ds_prev)->ds_creation_txg : 0);

	if (ds_next->ds_deadlist.dl_oldfmt) {
		process_old_deadlist(ds, ds_prev, ds_next,
		    after_branch_point, tx);
	} else {
		/* Adjust prev's unique space. */
		if (ds_prev && !after_branch_point) {
			dsl_deadlist_space_range(&ds_next->ds_deadlist,
			    dsl_dataset_phys(ds_prev)->ds_prev_snap_txg,
			    dsl_dataset_phys(ds)->ds_prev_snap_txg,
			    &used, &comp, &uncomp);
			dsl_dataset_phys(ds_prev)->ds_unique_bytes += used;
		}

		/* Adjust snapused. */
		dsl_deadlist_space_range(&ds_next->ds_deadlist,
		    dsl_dataset_phys(ds)->ds_prev_snap_txg, UINT64_MAX,
		    &used, &comp, &uncomp);
		dsl_dir_diduse_space(ds->ds_dir, DD_USED_SNAP,
		    -used, -comp, -uncomp, tx);

		/* Move blocks to be freed to pool's free list. */
		dsl_deadlist_move_bpobj(&ds_next->ds_deadlist,
		    &dp->dp_free_bpobj, dsl_dataset_phys(ds)->ds_prev_snap_txg,
		    tx);
		dsl_dir_diduse_space(tx->tx_pool->dp_free_dir,
		    DD_USED_HEAD, used, comp, uncomp, tx);

		/* Merge our deadlist into next's and free it. */
		dsl_deadlist_merge(&ds_next->ds_deadlist,
		    dsl_dataset_phys(ds)->ds_deadlist_obj, tx);
  1. L387–L391 Le dataset suivant, l’instantané suivant ou la tête, hérite de l’instantané précédent et du ds_prev_snap_txg de l’instantané détruit.
  2. L395–L397 Les pools d’avant les deadlists à clés appliquent le même test à chaque bloc. La figure suit le chemin à clés.
  3. L399–L413 Comptabilité de l’espace, non dessinée.
  4. L415–L418 Chaque entrée de la deadlist suivante à partir du ds_prev_snap_txg de l’instantané part dans la liste à libérer du pool. Ces blocs sont nés après l’instantané d’avant et ont été tués avant le suivant : cet instantané était le seul à les détenir. Les clés suffisent à le dire. Le thread de synchronisation libère cette liste dans les txg suivants ; la figure les libère tout de suite.
  5. L422–L424 La deadlist de l’instantané lui-même, des blocs que l’instantané d’avant détient encore, rejoint la suivante entrée par entrée, puis elle est libérée.

Enfin, la clé du txg de l’instantané est retirée, son entrée fusionnée avec la précédente : dans la tête quand le dataset suivant est un instantané, et dans chaque clone dont l’origine est plus récente que l’instantané, par dsl_dir_remove_clones_key. Un instantané qui a un clone a plus d’un enfant et ne peut pas être détruit, EEXIST : on ne détruit pas un point de branchement (Can’t delete a branch point).

À quel instantané appartient ce bloc. Rien dans ZFS ne stocke cette réponse : elle découle des txg de naissance. Un bloc de fs né au txg B et tué au txg K est détenu par les instantanés de fs pris du txg B au txg K − 1 : ceux d’avant B ont été figés avant qu’il existe, ceux de K ou après, une fois qu’il avait disparu. Un bloc encore vivant est détenu par tous les instantanés pris depuis B. La figure calcule cet intervalle à partir des nombres, et ses tests le comparent à l’arbre de dataset qui contient réellement le bloc, sur des milliers de séquences aléatoires.

Ce que la figure laisse de côté

La figure exécute les fonctions ci-dessus sur un système de fichiers de quatre blocs de données et jusqu’à quatre instantanés, et un clone qui ne peut lui-même être ni pris en instantané ni détruit. L’objset, les dnodes et les blocs indirects forment un seul bloc racine. Les libérations différées des blocs gang, dédupliqués et clonés, la comptabilité de l’espace et la livelist du clone sont laissées de côté ; aucune ne change le fait qu’un bloc soit libéré ou gardé. Les blocs de la liste à libérer du pool sont dessinés libérés tout de suite. Les holds, la destruction différée et les deadlists à l’ancien format ne sont pas montrés. Les signets (dsl_bookmark.c) et zfs promote, qui échange un clone et le système de fichiers de son origine, relèvent d’autres salles.