efeito da organização de arquivos na eficiência do acesso a arquivos

Question

A organização de arquivos em uma estrutura de diretórios pode afetar significativamente a eficiência do acesso a arquivos ( ref ). Por exemplo, considere dois diretórios, A e B , cada um contendo 10 ^ 6 arquivos, organizados em um diretório no primeiro caso e em 10 ^ 3 subdiretórios no segundo. Contar ou listar todos os arquivos é reprodutivelmente mais lento no primeiro caso. No meu sistema:

Crie arquivos:

$ mkdir A; pushd A; seq -w 1E6 | xargs touch; popd
$ mkdir B; pushd B; seq -w 1E3 | xargs mkdir; for d in *; do pushd "$d"; seq -w 1E3 | xargs touch; popd; done; popd

Listar arquivos:

$ for d in A B; do
    time for i in {1..100}; do
        {
            echo 3 | sudo tee /proc/sys/vm/drop_caches
            find "$d" -type f
        }
    done >/dev/null
done

# case A (0 subdirectories)
real    4m49.805s
user    1m43.696s
sys     1m13.540s

# case B (1000 subdirectories)
real    3m32.338s
user    0m40.824s
sys     1m13.176s

A diferença é reproduzível, independente do cache de disco, e não é específica do comando find (ou seja, uma diferença da mesma magnitude é encontrada usando ls -RU ). A quantidade de tempo no espaço do kernel é a mesma em ambos os casos, exonerando o kernel (e provavelmente a mecânica do sistema de arquivos também). Embora eu não tenha feito nenhum perfil, os principais syscalls sendo feitos são quase certamente readdir() e getdents() e uma vez que o número de inodes é o mesmo em ambos os casos (para dentro de 0.1%), assim como o tamanho dos arquivos , a quantidade de tempo necessária para a execução dessas chamadas pelo kernel não seria diferente. A diferença no tempo de execução é, portanto, atribuível ao código de espaço do usuário.

O suporte ao thread foi adicionado a alguns dos utilitários do GNU (por exemplo, sort ). Como meu sistema tem quatro threads de hardware e não tenho certeza se o GNU find (a versão do meu sistema é 4.7.0-git) foi imbuído de recursos multithreaded, verifiquei a persistência da discrepância com processos que estavam explicitamente ligados a uma única thread de hardware:

$ cat find.sh
#!/bin/bash
for i in {1..100}; do
  {
    echo 3 | sudo tee /proc/sys/vm/drop_caches
    find "$1" -type f
  }
done >/dev/null

$ for d in A B; do time taskset -c 0 ./find.sh "$d"; done

# case A (0 subdirectories)
real    4m7.827s
user    1m31.080s
sys     0m55.660s

# case B (1000 subdirectories)
real    2m53.059s
user    0m33.256s
sys     0m52.772s

Assim, minha pergunta original pode ser refinada da seguinte maneira: quais são as ineficiências do espaço do usuário que estão por trás da disparidade nos tempos de acesso decorrente puramente das diferenças na organização do sistema de arquivos? O conhecimento dessas ineficiências deve permitir melhores implementações de rotinas de acesso a arquivos.

Editar: Eu estou usando um sistema de arquivos ext4 em uma máquina rodando o kernel do linux 4.9.0-4-amd64 , embora eu esteja interessado em saber até que ponto a resposta depende do sistema de arquivos escolhido.

    

Answer 1

Sem muita evidência, eu vou adivinhar que find acaba invocando realloc e copiando os dados do diretório várias vezes enquanto ele é executado de espaço em uma alocação inicial no caso de diretório único. Mas, no caso de vários diretórios, a memória que suporta cada leitura de subdiretório não requer o mesmo número de cópias ou reallocs. Você pode verificar o uso geral de memória do find (de alguma forma?) Para verificar.