Como faço para percorrer rapidamente um sistema de arquivos ao extrair / extrapolar vários dados e fornecer feedback do usuário?

5

Estou trabalhando em um scanner de arquivos do sistema que revela informações sobre vários arquivos (por exemplo, tamanho, último uso, duplicatas etc.). Atualmente, estou percorrendo o sistema de arquivos apenas uma vez para obter uma boa medida dos arquivos que estarei processando e, em seguida, realizo o processamento real (informações de tamanho, informações de hash etc.). Obviamente, isso cria imediatamente uma camada inteira de processamento "extra", mas permite que eu use as informações obtidas anteriormente para fornecer ao usuário alguns "dados de progresso".

Estou procurando um bom mecanismo para usar, a fim de acelerar o processo, enquanto ainda mostro dados de progresso para os usuários finais. Pensei em criar encadeamentos separados (um para anexar arquivos a uma pilha e outro para ler da pilha à medida que eles se tornassem disponíveis), mas isso pode ficar fora de controle por meio de programação rapidamente.

No interesse de acelerar a varredura inicial, eu atualmente executo um "caminho de localização" (ou o equivalente dependendo do sistema operacional que está sendo usado) e pego toda a saída. Isso, no entanto, me impede de negar subpastas inteiras (se o usuário desejar), pois ele simplesmente lista recursivamente tudo. Alguns sistemas operacionais têm opções de linha de comando para negar diretórios, etc., mas eu preciso de uma solução de plataforma cruzada.

Então, aaaaaaall disse, alguém tem alguma sugestão algorítmica para ser rápida enquanto fornece progresso de qualidade? Eu não sou fundamentalmente ligado a qualquer idioma específico. Eu estou procurando mais por uma visão de alto nível do que precisa acontecer.

Melhor.

    
por humble_coder 02.06.2011 / 04:30
fonte

7 respostas

6

Você tem um problema de E / S. Isso significa que você terá que ajustar o cálculo para corresponder ao I / O. Você provavelmente está lidando com discos rígidos físicos, o que significa que as buscas são dominantes. Portanto, "rapidamente" se traduz em "número mínimo de pesquisas".

Podemos, portanto, listar os seguintes princípios: 1. Digitalize diretórios inteiros (largura primeiro). Não fique tentado a inserir subdiretórios antes de verificar o diretório pai; voltar leva outra busca. 2. Salve todos os dados possíveis de um diretório. Ter que voltar leva outra busca.

Agora, alguns sistemas de arquivos (por exemplo, NTFS) salvam o conteúdo de arquivos pequenos dentro das entradas do diretório. Em tais sistemas, você deve fazer o hash desses conteúdos de arquivo imediatamente depois de ter verificado o diretório. Caso contrário, realmente não importa quando você faz. Pode ser aconselhável verificar primeiro os subdiretórios para poder relatar a contagem de arquivos em execução e atrasar a leitura de arquivos grandes.

Quando você deseja realmente enviar E / S assíncronas de alto desempenho, a solução adequada. Isso não será necessário em PCs normais, até mesmo um SSD não é tão rápido, mas os servidores de arquivos high-end podem sobrecarregar um único thread. Em tais sistemas, uma solução como Boost ASIO pode escalar. Você apenas lançará solicitações de leitura para o Boost ASIO e retornará os resultados algum tempo depois, à medida que eles forem recebidos. Possivelmente em outros threads, se necessário. Isso dá ao O / S subjacente mais flexibilidade para manipular as solicitações de leitura.

    
por 15.07.2011 / 13:27
fonte
2

'Se Maomé não vier para a montanha, a montanha deve chegar a Maomé.'

Você não pode sempre fazer isso rápido. Às vezes você precisa fazer com que pareça ser rápido.

Velocidade da barra de progresso falsa. O usuário quer saber que algo está acontecendo, o usuário quer um feedback rápido. Existem alguns estudos que mostram como fazer a barra de progresso parecer mais fluida e mais rápida, mas não me lembro dos artigos.

Existe um estudo sobre como fazer a barra de progresso parecer mais rápida . Alguns outros links para mais pesquisas sobre como fazer com que a barra de progresso apareça seja mais rápido .

    
por 14.06.2011 / 17:37
fonte
0

Não vinculado a um idioma específico? Erm. A maior parte do que vem à mente é evitar o máximo de trabalho de comparação de arquivos possível (com um aumento correspondente nos dados mantidos na memória) em vez de tentar otimizar os percursos.

  1. Mantenha uma estrutura de dados / mapa que use contagens de bytes como chaves e uma lista de identificadores de arquivos como as cargas úteis. Sempre que você adiciona um arquivo à estrutura de dados, se ele entra em uma lista e tem "vizinhos" do mesmo tamanho de arquivo, você sabe que pode precisar compará-lo mais profundamente a esses vizinhos.
  2. Não crie hash de arquivos inteiros, a menos que você realmente precise. Em vez disso, considere hashing "pedaços" sequenciais do arquivo. Dois arquivos idênticos exigirão que você os misture na íntegra, mas dois arquivos que diferem muito no início precisarão de menos trabalho. Se puder, armazene esses fragmentos de hash na memória para tornar as verificações futuras mais rápidas.
  3. Não exagere nos threads, apenas mantenha as coisas de E / S de arquivos separadas de sua interface de usuário ou thread principal. Considere o uso de uma estrutura (em Java, que poderia ser Executors ) para que, se você precisar ajustar o número de threads que você executa, você pode.
  4. Para um programa GUI, considere a idéia de informar aos usuários que as verificações de duplicação nos arquivos têm um status "pendente". Isso significa que você mostra imediatamente ao usuário tudo exceto duplicação-cheques, e apenas os preenche conforme o tempo permitir.
por 06.06.2011 / 08:44
fonte
0

Eu posso não entender o que você está tentando fazer com os dados, mas ... Isso não é um problema de redução de mapa? Para cada pasta, use a função map para extrair os dados necessários (desde que você possa distribuir o número de diretórios para qualquer número de encadeamentos / processos que possam executar a função de mapeamento, eles podem ser executados "em paralelo" e como eles você recebe um conjunto de indicações de progresso. Em seguida, reduza o conjunto de dados para fornecer as informações específicas que você deseja fornecer ao usuário.

Além disso, você entende onde está o tempo limite para esse problema? Se você fizer essa função para um sistema de arquivos inteiro, talvez não consiga ler todas as informações de diretório / arquivo do cache, portanto, pode estar limitado a tempos de pesquisa do disco rígido para criar sua lista. Se você acabar esperando pela unidade, pode não fazer sentido otimizar o uso da CPU / exibição.

    
por 14.06.2011 / 19:33
fonte
0

Como regra geral

Threads provavelmente atrasarão seu aplicativo se ambos estiverem fazendo acesso IO simultâneo à mesma interface física (rede ou disco).

Estratégias

Mapear / Reduzir pode ser aplicado para estatísticas e outras coisas que se encaixam nesse modelo e podem ser atualizados incrementalmente conforme os arquivos são processados.

Ter um sistema acionado por evento permitirá um feedback em tempo real para o usuário, mas não permitirá que ele saiba a porcentagem completa de todo o processo, apenas do evento atual. inotify é um bom lugar para começar, se você estiver no Linux, outras plataformas de sistema operacional têm APIs nativas equivalentes para fazer a mesma coisa.

Armazenar em cache a lista de arquivos , para obter totais para o progresso de tarefas muito grandes, provavelmente será uma coisa boa, mesmo que isso acrescente ao tempo geral, o usuário saberá quanto tempo levar quebrar enquanto o trabalho funciona.

Uma solução híbrida de armazenamento em cache de algumas coisas e a criação de eventos a serem processados em um mapa reduzem o tamanho do caminho que você pode esperar, respondendo a eventos que ocorrem em tempo real usando alguma plataforma específica mecanismo de notificação será sua melhor solução.

Lembre-se de que IO é limitado pela física, o encadeamento só aumentará a contenção de recursos físicos já estressados.

    
por 14.06.2011 / 18:37
fonte
0

Apenas digitalizando sua pergunta, só posso dar alguns conselhos gerais.

O multithreading definitivamente ajudará no desempenho, dependendo de quanto processamento você está fazendo. Tente separar componentes de E / S do processamento de componentes em seu design de software e, em seguida, você pode escrever a primeira versão de forma síncrona, depois voltar mais tarde e modificar o software para fazer essas coisas em paralelo.

Em segundo lugar, sei que o uso de recursão para percorrer um sistema de arquivos é tentador. Você verá uma melhoria de desempenho se você usar loops ao invés de recursão, embora o tamanho de uma melhoria dependerá do tamanho da sua entrada.

O que você pode considerar é que um thread lide com o I / O e passe os resultados para outro thread para processamento. Dessa forma, sua CPU não está esperando por E / S lenta com o disco.

Além disso, se este sistema tiver uma interface com o usuário, você com certeza irá querer, no mínimo, colocar a interface do usuário em um thread separado de execução. Isso definitivamente aumentará o desempenho, especialmente considerando a operação de longa duração e uso intensivo de recursos que você executará em segundo plano com todo o processamento de E / S e os metadados do arquivo.

Eu usaria um thread para percorrer continuamente diretórios no sistema de arquivos e ler os metadados em uma estrutura de dados que seja thread-safe. Então, eu teria outro thread processando esses dados e extraindo as informações que você deseja fornecer ao usuário e armazenando essas informações em outra estrutura de dados segura de thread. Por fim, sua interface do usuário deve estar em seu próprio encadeamento de execução e atualizar-se sempre que os dados na segunda estrutura de dados seguros do encadeamento forem modificados.

Apenas uma observação, o .NET Framework tem uma classe "FileSystemWatcher" que efetivamente lida com tudo, menos com a UI para você. Se você não quiser usar o .NET, você pode pelo menos considerar a leitura da documentação dessa classe para dar uma vantagem inicial. Dê uma olhada no Mono for .NET se estiver interessado em plataformas cruzadas.

    
por 14.06.2011 / 19:44
fonte
0

Eu escrevi uma biblioteca para fazer algo parecido, mas ela é realmente adequada apenas para sistemas de arquivos que têm muitos cabeçotes (como o brilho ou panfs). Nós coletamos informações sobre centenas de milhões de arquivos (cerca de 20PB de dados) regularmente. Dê uma olhada no o artigo que escrevemos e a biblioteca para distribuir a carga de trabalho e ferramentas para analisar os dados .

Se você tem um sistema de arquivos menor, o CEA escreveu um programa chamado Robinhood para fazer algo semelhante.

    
por 09.02.2013 / 00:36
fonte