rm sur un répertoire contenant des millions de fichiers

Mise à jour août 2021

Cette réponse continue à attirer beaucoup d'attention et j'ai l'impression qu'elle est tellement dépassée qu'elle est en quelque sorte redondante maintenant.

Faire un find ... -delete va très probablement produire des résultats acceptables en termes de performances.

La seule chose qui, à mon avis, pourrait donner lieu à une meilleure performance est de s'attaquer à la partie "suppression" du problème plutôt qu'à la partie "énumération".

J'ai essayé et ça n'a pas marché. Mais j'ai pensé qu'il était utile d'expliquer ce que j'ai fait et pourquoi.

Dans les noyaux les plus récents, grâce à l'utilisation du sous-système de gestion des entrées/sorties dans le noyau (cf. man 2 io_uring_setup ) il est en fait possible de tenter d'effectuer des déliaisons de manière asynchrone - ce qui signifie que nous pouvons soumettre des demandes de déliaison sans attendre ou bloquer pour voir le résultat.

Ce programme lit essentiellement un répertoire, soumet des centaines de unlinks sans attendre le résultat, puis récolte les résultats plus tard, lorsque le système a fini de traiter la demande.

Il essaie de faire ce que dentls a mais utilise IO uring. Peut être compilé avec gcc -o dentls2 dentls2.c -luring .

#include <stdlib.h>
#include <stdint.h>
#include <unistd.h>
#include <stdio.h>
#include <string.h>
#include <err.h>
#include <sched.h>

#include <sys/stat.h>
#include <sys/types.h>
#include <dirent.h>

#include <linux/io_uring.h>
#include <liburing.h>

/* Try to keep the queue size to under two pages as internally its stored in
 * the kernel as contiguously ordered pages. Basically the bigger you make it
 * the higher order it becomes and the less likely you'll have the contiguous
 * pages to support it, despite not hitting any user limits.
 * This reduces an ENOMEM here by keeping the queue size as order 1
 * Ring size internally is rougly 24 bytes per entry plus overheads I haven't
 * accounted for.
 */
#define QUEUE_SIZE 256

/* Globals to manage the queue */
static volatile int pending = 0;
static volatile int total_files = 0;

/* Probes kernel uring implementation and checks if action is 
 * supported inside the kernel */
static void probe_uring(
    struct io_uring *ring)
{
  struct io_uring_probe *pb = {0};

  pb = io_uring_get_probe_ring(ring);

  /* Can we perform IO uring unlink in this kernel ? */
  if (!io_uring_opcode_supported(pb, IORING_OP_UNLINKAT)) {
    free(pb);
    errno = ENOTSUP;
    err(EXIT_FAILURE, "Unable to configure uring");
  }

  free(pb);
}

/* Place a unlink call for the specified file/directory on the ring */
static int submit_unlink_request(
    int dfd,
    const char *fname,
    struct io_uring *ring)
{
  char *fname_cpy = strdup(fname);
  struct io_uring_sqe *sqe = NULL;

  /* Fetch a free submission entry off the ring */
  sqe = io_uring_get_sqe(ring);
  if (!sqe)
    /* Submission queue full */
    return 0;

  pending++;
  /* Format the unlink call for submission */
  io_uring_prep_rw(IORING_OP_UNLINKAT, sqe, dfd, fname_cpy, 0, 0);
  sqe->unlink_flags = 0;

  /* Set the data to just be the filename. Useful for debugging
   * at a later point */
  io_uring_sqe_set_data(sqe, fname_cpy);

  return 1;
}

/* Submit the pending queue, then reap the queue
 * clearing up room on the completion queue */
static void consume_queue(
    struct io_uring *ring)
{
  char *fn;
  int i = 0, bad = 0;
  int rc;
  struct io_uring_cqe **cqes = NULL;

  if (pending < 0)
    abort();

  cqes = calloc(pending, sizeof(struct io_uring_cqe *));
  if (!cqes)
    err(EXIT_FAILURE, "Cannot find memory for CQE pointers");

  /* Notify about submitted entries from the queue (this is a async call) */
  io_uring_submit(ring);

  /* We can immediately take a peek to see if we've anything completed */
  rc = io_uring_peek_batch_cqe(ring, cqes, pending);

  /* Iterate the list of completed entries. Check nothing crazy happened */
  for (i=0; i < rc; i++) {
    /* This returns the filename we set earlier */
    fn = io_uring_cqe_get_data(cqes[i]);

    /* Check the error code of the unlink calls */
    if (cqes[i]->res < 0) {
      errno = -cqes[i]->res;
      warn("Unlinking entry %s failed", fn);
      bad++;
    }

    /* Clear up our CQE */
    free(fn);
    io_uring_cqe_seen(ring, cqes[i]);
  }

  pending -= rc + bad;
  total_files += rc - bad;
  free(cqes);
}

/* Main start */
int main(
    const int argc,
    const char **argv)
{
  struct io_uring ring = {0};
  struct stat st = {0};
  DIR *target = NULL;
  int dfd;
  struct dirent *fn;

  /* Check initial arguments passed make sense */
  if (argc < 2)
    errx(EXIT_FAILURE, "Must pass a directory to remove files from.");

  /* Check path validity */
  if (lstat(argv[1], &st) < 0)
    err(EXIT_FAILURE, "Cannot access target directory");

  if (!S_ISDIR(st.st_mode)) 
    errx(EXIT_FAILURE, "Path specified must be a directory");

  /* Open the directory */
  target = opendir(argv[1]);
  if (!target)
    err(EXIT_FAILURE, "Opening the directory failed");
  dfd = dirfd(target);

  /* Create the initial uring for handling the file removals */
  if (io_uring_queue_init(QUEUE_SIZE, &ring, 0) < 0)
    err(EXIT_FAILURE, "Cannot initialize URING");

  /* Check the unlink action is supported */
  probe_uring(&ring);

  /* So as of writing this code, GETDENTS doesn't have URING support.
   * but checking the kernel mailing list indicates its in progress.
   * For now, we'll just do laymans readdir(). These days theres no 
   * actual difference between it and making the getdents() call ourselves.
   */
  while (fn = readdir(target)) {
    if (fn->d_type != DT_REG)
      /* Pay no attention to non-files */
      continue;

    /* Add to the queue until its full, try to consume it
     * once its full. 
     */
    while (!submit_unlink_request(dfd, fn->d_name, &ring)) {
      /* When the queue becomes full, consume queued entries */
      consume_queue(&ring);
      /* This yield is here to give the uring a chance to 
       * complete pending requests */
      sched_yield();
      continue;
    }
  }

  /* Out of files in directory to list. Just clear the queue */
  while (pending) {
    consume_queue(&ring);
    sched_yield();
  }

  printf("Total files: %d\n", total_files);

  io_uring_queue_exit(&ring);
  closedir(target);
  exit(0);
}

Les résultats étaient ironiquement à l'opposé de ce que je soupçonnais, mais pourquoi ?

TMPFS avec 4 millions de fichiers

$ time ./dentls2 /tmp/many
Total files: 4000000

real    0m6.459s
user    0m0.360s
sys 0m24.224s

Utiliser trouver :

$ time find /tmp/many -type f -delete

real    0m9.978s
user    0m1.872s
sys 0m6.617s

BTRFS avec 10 millions de fichiers

$ time ./dentls2 ./many
Total files: 10000000

real    10m25.749s
user    0m2.214s
sys 16m30.865s

Utiliser trouver :

time find ./many -type f -delete

real    7m1.328s
user    0m9.209s
sys 4m42.000s

Il semble donc que les appels système groupés n'apportent pas d'amélioration en temps réel. La nouvelle dentls2 passe beaucoup plus de temps à travailler (quatre fois plus) pour une performance moindre. Il s'agit donc d'une perte nette d'efficacité globale et d'une aggravation de la latence. dentls2 est pire.

La cause de ce problème est que io_uring produit des threads répartiteurs de noyau pour effectuer le travail de déliaison en interne, mais l'inode du répertoire sur lequel on travaille ne peut être modifié que par un seul écrivain à la fois.

Fondamentalement, l'utilisation du uring nous créons beaucoup de petits fils mais un seul fil est autorisé à supprimer du répertoire. Nous venons de créer un tas de conflits et d'éliminer l'avantage de faire des entrées-sorties par lots.

En utilisant eBPF, vous pouvez mesurer les fréquences de déliaison et observer ce qui cause les retards.

Dans le cas de BTRFS, il s'agit de l'appel à la fonction du noyau. btrfs_commit_inode_delayed_inode qui acquiert le verrou lorsque unlink s'appelle.

Avec dentls2

# /usr/share/bcc/tools/funclatency btrfs_commit_inode_delayed_inode
    Tracing 1 functions for "btrfs_commit_inode_delayed_inode"... Hit Ctrl-C to end.

     nsecs               : count     distribution
         0 -> 1          : 0        |                                        |
         2 -> 3          : 0        |                                        |
         4 -> 7          : 0        |                                        |
         8 -> 15         : 0        |                                        |
        16 -> 31         : 0        |                                        |
        32 -> 63         : 0        |                                        |
        64 -> 127        : 0        |                                        |
       128 -> 255        : 0        |                                        |
       256 -> 511        : 18       |                                        |
       512 -> 1023       : 120      |                                        |
      1024 -> 2047       : 50982    |                                        |
      2048 -> 4095       : 2569467  |********************                    |
      4096 -> 8191       : 4936402  |****************************************|
      8192 -> 16383      : 1662380  |*************                           |
     16384 -> 32767      : 656883   |*****                                   |
     32768 -> 65535      : 85409    |                                        |
     65536 -> 131071     : 21715    |                                        |
    131072 -> 262143     : 9719     |                                        |
    262144 -> 524287     : 5981     |                                        |
    524288 -> 1048575    : 857      |                                        |
   1048576 -> 2097151    : 293      |                                        |
   2097152 -> 4194303    : 220      |                                        |
   4194304 -> 8388607    : 255      |                                        |
   8388608 -> 16777215   : 153      |                                        |
  16777216 -> 33554431   : 56       |                                        |
  33554432 -> 67108863   : 6        |                                        |
  67108864 -> 134217727  : 1        |                                        |

avg = 8533 nsecs, total: 85345432173 nsecs, count: 10000918

Utilisation de find ... -delete :

# /usr/share/bcc/tools/funclatency btrfs_commit_inode_delayed_inode
Tracing 1 functions for "btrfs_commit_inode_delayed_inode"... Hit Ctrl-C to end.
     nsecs               : count     distribution
         0 -> 1          : 0        |                                        |
         2 -> 3          : 0        |                                        |
         4 -> 7          : 0        |                                        |
         8 -> 15         : 0        |                                        |
        16 -> 31         : 0        |                                        |
        32 -> 63         : 0        |                                        |
        64 -> 127        : 0        |                                        |
       128 -> 255        : 0        |                                        |
       256 -> 511        : 34       |                                        |
       512 -> 1023       : 95       |                                        |
      1024 -> 2047       : 1005784  |****                                    |
      2048 -> 4095       : 8110338  |****************************************|
      4096 -> 8191       : 672119   |***                                     |
      8192 -> 16383      : 158329   |                                        |
     16384 -> 32767      : 42338    |                                        |
     32768 -> 65535      : 4667     |                                        |
     65536 -> 131071     : 3597     |                                        |
    131072 -> 262143     : 2860     |                                        |
    262144 -> 524287     : 216      |                                        |
    524288 -> 1048575    : 22       |                                        |
   1048576 -> 2097151    : 6        |                                        |
   2097152 -> 4194303    : 3        |                                        |
   4194304 -> 8388607    : 5        |                                        |
   8388608 -> 16777215   : 3        |                                        |

avg = 3258 nsecs, total: 32585481993 nsecs, count: 10000416

Vous pouvez voir sur l'histogramme que find passe en moyenne 3258 nanosecondes dans btrfs_commit_inode_delayed_inode mais dentls2 passe 8533 nanosecondes dans la fonction.

L'histogramme montre également que les threads io_uring passent au moins deux fois plus de temps à attendre le verrou, la majorité des appels prenant 4096-8091 nanosecondes contre la majorité en find prenant 2048-4095 nanosecondes.

Find est mono-thread et ne se dispute pas le verrou, alors que `dentls2 est multi-thread (à cause de l'uring) ce qui produit une contention du verrou et les délais qui sont expérimentés sont reflétés dans l'analyse.

Conclusion

Dans l'ensemble, sur les systèmes modernes (au moment où j'écris ces lignes), il y a de moins en moins de choses que l'on peut faire dans le logiciel pour que cela aille plus vite que ce qui est prévu.

Auparavant, en lisant un grand tampon sur le disque, vous pouviez combiner un appel IO coûteux en une grande lecture séquentielle, au lieu de l'IO douteuse que les petits tampons getdents() pouvaient typiquement devenir.

D'autres améliorations ont également permis de réduire les frais généraux liés à l'invocation des appels système et d'améliorer considérablement les temps d'accès aux entrées-sorties séquentielles et aléatoires, éliminant ainsi les goulots d'étranglement que nous connaissions auparavant.

Sur mes systèmes, ce problème est devenu lié à la mémoire et au processeur. Il y a un problème d'accès unique sur (au moins) BTRFS qui limite la vitesse à un seul processeur/programme de déliaison par répertoire à la fois. Essayer de regrouper les entrées-sorties n'apporte au mieux que des améliorations mineures, même dans les circonstances idéales d'utilisation de tmpfs, et c'est généralement pire sur un système de fichiers du monde réel.

Pour couronner le tout, nous n'avons plus vraiment ce problème - fini l'époque où il fallait 4 heures pour supprimer 10 millions de fichiers.

Faites quelque chose de simple comme find ... -delete . Aucune des optimisations que j'ai essayées n'a semblé produire des améliorations de performance majeures valant le codage (ou l'analyse) par rapport à une configuration simple par défaut.

Réponse originale

Bien qu'une cause majeure de ce problème soit la performance d'ext3 avec des millions de fichiers, la cause réelle de ce problème est différente.

Lorsqu'un répertoire doit être listé, readdir() est appelé sur le répertoire, ce qui donne une liste de fichiers. readdir est un appel Posix, mais le véritable appel système Linux utilisé ici est appelé 'getdents'. Getdents liste les entrées du répertoire en remplissant un tampon d'entrées.

Le problème est principalement dû au fait que readdir() utilise une taille de tampon fixe de 32Kb pour récupérer les fichiers. Comme un répertoire devient de plus en plus grand (la taille augmente avec l'ajout de fichiers) ext3 devient de plus en plus lent pour récupérer les entrées et les 32Kb supplémentaires de la taille du tampon de readdir sont seulement suffisants pour inclure une fraction des entrées dans le répertoire. Cela fait que readdir boucle encore et encore et invoque l'appel système coûteux encore et encore.

Par exemple, sur un répertoire de test que j'ai créé avec plus de 2,6 millions de fichiers à l'intérieur, l'exécution de "ls -1|wc-l" montre une grande sortie strace de nombreux appels système getdent.

$ strace ls -1 | wc -l
brk(0x4949000)                          = 0x4949000
getdents(3, /* 1025 entries */, 32768)  = 32752
getdents(3, /* 1024 entries */, 32768)  = 32752
getdents(3, /* 1025 entries */, 32768)  = 32760
getdents(3, /* 1025 entries */, 32768)  = 32768
brk(0)                                  = 0x4949000
brk(0x496a000)                          = 0x496a000
getdents(3, /* 1024 entries */, 32768)  = 32752
getdents(3, /* 1026 entries */, 32768)  = 32760
...

De plus, le temps passé dans ce répertoire a été important.

$ time ls -1 | wc -l
2616044

real    0m20.609s
user    0m16.241s
sys 0m3.639s

La méthode pour rendre ce processus plus efficace est d'appeler getdents manuellement avec un buffer beaucoup plus grand. Cela améliore considérablement les performances.

Maintenant, vous n'êtes pas censé appeler getdents vous-même manuellement, donc aucune interface n'existe pour l'utiliser normalement (vérifiez la page de manuel de getdents pour voir !), cependant vous peut l'appeler manuellement et rendre votre invocation d'appel système beaucoup plus efficace.

Cela réduit considérablement le temps nécessaire pour aller chercher ces fichiers. J'ai écrit un programme qui fait cela.

/* I can be compiled with the command "gcc -o dentls dentls.c" */

#define _GNU_SOURCE

#include <dirent.h>     /* Defines DT_* constants */
#include <err.h>
#include <fcntl.h>
#include <getopt.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/syscall.h>
#include <sys/types.h>
#include <unistd.h>

struct linux_dirent {
        long           d_ino;
        off_t          d_off;
        unsigned short d_reclen;
        char           d_name[256];
        char           d_type;
};

static int delete = 0;
char *path = NULL;

static void parse_config(
        int argc,
        char **argv)
{
    int option_idx = 0;
    static struct option loptions[] = {
      { "delete", no_argument, &delete, 1 },
      { "help", no_argument, NULL, 'h' },
      { 0, 0, 0, 0 }
    };

    while (1) {
        int c = getopt_long(argc, argv, "h", loptions, &option_idx);
        if (c < 0)
            break;

        switch(c) {
          case 0: {
              break;
          }

          case 'h': {
              printf("Usage: %s [--delete] DIRECTORY\n"
                     "List/Delete files in DIRECTORY.\n"
                     "Example %s --delete /var/spool/postfix/deferred\n",
                     argv[0], argv[0]);
              exit(0);                      
              break;
          }

          default:
          break;
        }
    }

    if (optind >= argc)
      errx(EXIT_FAILURE, "Must supply a valid directory\n");

    path = argv[optind];
}

int main(
    int argc,
    char** argv)
{

    parse_config(argc, argv);

    int totalfiles = 0;
    int dirfd = -1;
    int offset = 0;
    int bufcount = 0;
    void *buffer = NULL;
    char *d_type;
    struct linux_dirent *dent = NULL;
    struct stat dstat;

    /* Standard sanity checking stuff */
    if (access(path, R_OK) < 0) 
        err(EXIT_FAILURE, "Could not access directory");

    if (lstat(path, &dstat) < 0) 
        err(EXIT_FAILURE, "Unable to lstat path");

    if (!S_ISDIR(dstat.st_mode))
        errx(EXIT_FAILURE, "The path %s is not a directory.\n", path);

    /* Allocate a buffer of equal size to the directory to store dents */
    if ((buffer = calloc(dstat.st_size*3, 1)) == NULL)
        err(EXIT_FAILURE, "Buffer allocation failure");

    /* Open the directory */
    if ((dirfd = open(path, O_RDONLY)) < 0) 
        err(EXIT_FAILURE, "Open error");

    /* Switch directories */
    fchdir(dirfd);

    if (delete) {
        printf("Deleting files in ");
        for (int i=5; i > 0; i--) {
            printf("%u. . . ", i);
            fflush(stdout);
            sleep(1);
        }
        printf("\n");
    }

    while (bufcount = syscall(SYS_getdents, dirfd, buffer, dstat.st_size*3)) {
        offset = 0;
        dent = buffer;
        while (offset < bufcount) {
            /* Don't print thisdir and parent dir */
            if (!((strcmp(".",dent->d_name) == 0) || (strcmp("..",dent->d_name) == 0))) {
                d_type = (char *)dent + dent->d_reclen-1;
                /* Only print files */
                if (*d_type == DT_REG) {
                    printf ("%s\n", dent->d_name);
                    if (delete) {
                        if (unlink(dent->d_name) < 0)
                            warn("Cannot delete file \"%s\"", dent->d_name);
                    }
                    totalfiles++;
                }
            }
            offset += dent->d_reclen;
            dent = buffer + offset;
        }
    }
    fprintf(stderr, "Total files: %d\n", totalfiles);
    close(dirfd);
    free(buffer);

    exit(0);
}

Bien que cela ne combatte pas le problème fondamental sous-jacent (beaucoup de fichiers, dans un système de fichiers peu performant). Il est probable qu'il soit beaucoup, beaucoup plus rapide que la plupart des alternatives proposées.

Par précaution, on devrait supprimer le répertoire affecté et le refaire après. Les répertoires ne font qu'augmenter en taille et peuvent rester peu performants même avec quelques fichiers à l'intérieur en raison de la taille du répertoire.

Edit : Je l'ai un peu nettoyée. J'ai ajouté une option pour vous permettre de supprimer sur la ligne de commande au moment de l'exécution et j'ai supprimé un tas de trucs de treewalk qui, honnêtement, avec le recul, étaient au mieux discutables. Il a également été démontré que cela produisait une corruption de la mémoire.

Vous pouvez maintenant faire dentls --delete /my/path

Nouveaux résultats. Basé sur un répertoire de 1,82 millions de fichiers.

## Ideal ls Uncached
$ time ls -u1 data >/dev/null

real    0m44.948s
user    0m1.737s
sys 0m22.000s

## Ideal ls Cached
$ time ls -u1 data >/dev/null

real    0m46.012s
user    0m1.746s
sys 0m21.805s

### dentls uncached
$ time ./dentls data >/dev/null
Total files: 1819292

real    0m1.608s
user    0m0.059s
sys 0m0.791s

## dentls cached
$ time ./dentls data >/dev/null
Total files: 1819292

real    0m0.771s
user    0m0.057s
sys 0m0.711s

J'ai été un peu surpris que cela fonctionne toujours aussi bien !

Serait-il possible de sauvegarder tous les autres fichiers de ce système de fichiers dans un emplacement de stockage temporaire, de reformater la partition, puis de restaurer les fichiers ?

Il n'y a pas de limite de fichier par répertoire dans ext3 juste la limite d'inode du système de fichiers (je pense qu'il y a une limite sur le nombre de sous-répertoires cependant).

Il se peut que vous ayez encore des problèmes après avoir supprimé les fichiers.

Lorsqu'un répertoire contient des millions de fichiers, l'entrée du répertoire elle-même devient très grande. L'entrée du répertoire doit être analysée pour chaque opération de suppression, ce qui prend plus ou moins de temps pour chaque fichier, selon l'emplacement de son entrée. Malheureusement, même après que tous les fichiers aient été supprimés, l'entrée du répertoire conserve sa taille. Ainsi, les opérations ultérieures qui nécessitent l'analyse de l'entrée du répertoire prendront encore beaucoup de temps, même si le répertoire est maintenant vide. La seule façon de résoudre ce problème est de renommer le répertoire, d'en créer un nouveau avec l'ancien nom, et de transférer tous les fichiers restants dans le nouveau. Ensuite, supprimez le répertoire renommé.

Je ne l'ai pas testé, mais ce gars-là a fait :

rsync -a --delete ./emptyDirectoty/ ./hugeDirectory/