Quais são as implicações de desempenho para milhões de arquivos em um sistema de arquivos moderno?

Question

Digamos que estamos usando o ext4 (com dir_index habilitado) para hospedar arquivos em torno de 3M (com uma média de 750 KB) e precisamos decidir qual esquema de pastas usaremos.

Na primeira solução , aplicamos uma função hash ao arquivo e usamos a pasta de dois níveis (sendo 1 caractere para o primeiro nível e 2 caracteres para o segundo nível): portanto, sendo filex.for hash é igual a abcde1234 , nós vamos armazená-lo em /path/a/bc/abcde1234-filex.for.

Na segunda solução , aplicamos uma função hash ao arquivo e usamos a pasta two levels (sendo 2 caracteres para o primeiro nível e 2 caracteres para o segundo nível): portanto, sendo filex.for o hash é igual a abcde1234 , nós o armazenaremos em /path/ab/de/abcde1234-filex.for.

Para a primeira solução, teremos o seguinte esquema /path/[16 folders]/[256 folders] com uma média de 732 arquivos por pasta (a última pasta, onde o arquivo residirá).

Enquanto na segunda solução teremos /path/[256 folders]/[256 folders] com uma média de 45 arquivos por pasta .

Considerando que vamos escrever / desassociar / ler arquivos ( mas principalmente ler ) deste esquema muito (basicamente o sistema de cache nginx), ele é melhor, em um desempenho sentido, se escolhemos uma ou outra solução?

Além disso, quais são as ferramentas que poderíamos usar para verificar / testar essa configuração?

    

Answer 1

A razão pela qual se criaria este tipo de estrutura de diretórios é que os sistemas de arquivos devem localizar um arquivo dentro de um diretório, e quanto maior o diretório, mais lenta é a operação.

Quanto mais lento depende do design do sistema de arquivos.

O sistema de arquivos ext4 usa um B-tree para armazenar entradas de diretório. Espera-se que uma pesquisa nesta tabela leve o tempo O (log n) , que na maioria das vezes é menor que a ingênua tabela linear usada pelos sistemas de arquivos ext3 e anteriores (e quando não é, diretório é muito pequeno para que realmente importe).

O sistema de arquivos XFS usa uma árvore B + em vez disso. A vantagem disso sobre uma tabela de hash ou árvore B é que qualquer nó pode ter vários filhos b , onde em XFS b varia e pode ser tão alto quanto 254 (ou 19 para o nó raiz e esses números podem estar desatualizados). Isso lhe dá uma complexidade de tempo de O (log _b n) , uma grande melhoria.

Qualquer um desses sistemas de arquivos pode lidar com dezenas de milhares de arquivos em um único diretório, com o XFS sendo significativamente mais rápido que o ext4 em um diretório com o mesmo número de inodes. Mas você provavelmente não quer um único diretório com 3M inodes, pois mesmo com uma árvore B +, a pesquisa pode levar algum tempo. Isso é o que levou à criação de diretórios dessa maneira em primeiro lugar.

Quanto às estruturas propostas, a primeira opção que você deu é exatamente o que é mostrado nos exemplos do nginx. Ele funcionará bem em qualquer sistema de arquivos, embora o XFS ainda tenha uma vantagem. A segunda opção pode ser um pouco melhor ou um pouco pior, mas provavelmente será bem próxima, mesmo em benchmarks.

    

Answer 2

Na minha experiência, um dos fatores de escala é o tamanho dos inodes, dada uma estratégia de particionamento de nome de hash.

Ambas as opções propostas criam até três entradas de inode para cada arquivo criado. Além disso, 732 arquivos criarão um inode que ainda é menor que o usual 16KB. Para mim, isso significa que qualquer uma das opções executará o mesmo.

Eu aplaudo em seu curto hash; Os sistemas anteriores em que trabalhei usaram o sha1sum do arquivo fornecido e os diretórios unidos com base nessa sequência, um problema muito mais difícil.

    

Answer 3

Certamente, qualquer uma das opções ajudará a reduzir o número de arquivos em um diretório para algo que pareça razoável, para xfs, ext4 ou qualquer outro sistema de arquivos. Não é óbvio qual é melhor, teria que testar para contar.

Benchmark com seu aplicativo simulando algo como a carga real de trabalho é ideal. Caso contrário, crie algo que simule muitos arquivos pequenos especificamente. Falando nisso, aqui está um open source chamado smallfile . Sua documentação faz referência a algumas outras ferramentas.

hdparm fazendo E / S sustentada não é tão útil. Ele não mostrará as muitas entradas de E / S pequenas ou entradas de diretório gigantes associadas a muitos arquivos.

    

Answer 4

Um dos problemas é a maneira de digitalizar a pasta.

Imagine o método Java que executa a varredura na pasta.

Terá que alocar grande quantidade de memória e desalocá-la em um curto período de tempo que é muito pesado para a JVM.

A melhor maneira é organizar a estrutura de pastas da mesma forma que cada arquivo está em uma pasta dedicada, por exemplo ano / mês / dia.

A maneira como a varredura completa é feita é que, para cada pasta, há uma execução da função, para que a JVM saia da função, desaloque a RAM e execute-a novamente em outra pasta.

Este é apenas um exemplo, mas mesmo assim ter uma pasta tão grande não faz sentido.