precisa de alto desempenho / bin / sort; alguma sugestão?

Question

Estou à procura de uma substituição de alto desempenho / bin / sort na substituição. Eu sei que há pbzip2 para usar múltiplos núcleos, mas existe um produto similar para / bin / sort?

Eu encontrei o distsort.sh, mas quero algo menos IO intensivo. Eu estou olhando para ordenar oh .. 60 shows de dados em uma base muito freqüente.

    

Answer 1

GNU sort tem -m que provavelmente pode ajudar você. Vamos supor que você tenha 200 arquivos .gz que deseja classificar e combinar. Então você poderia usar o GNU Parallel para fazer:

seq 1 200 | parallel mkfifo /tmp/{}
ls *.gz | nice parallel -j200 'zcat {} | sort >/tmp/$PARALLEL_SEQ' &
seq 1 200 | parallel -X sort -m /tmp/{} >/tmp/sorted

Se E / S é o problema e a memória não é um problema, use -S para o primeiro sort para garantir que tudo permaneça na memória. Além disso, você pode querer usar lzop toda vez que gravar em disco (--compress-program = lzop): Discos são muitas vezes o fator limitante, portanto lzopping on the fly pode lhe dar velocidade extra. Ou você pode criar um disco RAM e definir -T para esse diretório.

    

Answer 2

Hrm. Você vai se deparar com alguns problemas aqui, eu acho. Primeiro de tudo, seus dados de entrada terão um grande impacto no desempenho da classificação (diferentes algoritmos funcionam melhor ou pior dependendo da distribuição da entrada). No entanto, um problema maior na frente é simplesmente que 60GB é um monte de dados.

Além disso, a classificação não é paralelizada tão facilmente quanto a compactação porque não há garantias de proximidade. Em outras palavras, com compactação / descompactação, você pode dividir a entrada em blocos discretos e operá-los separadamente e de forma independente. Depois que cada pedaço é processado, eles são simplesmente concatenados juntos. Com a classificação, você tem vários passos envolvidos porque você não pode simplesmente concatenar os resultados (a menos que você faça algum pré-processamento), você tem que mesclar os resultados (porque uma entrada no início dos 60GB pode acabar adjacente a uma entrada no final dos 60 GB, após a classificação).

Basicamente, posso pensar em algumas soluções gerais aqui:

• Preparticione seus dados de uma maneira que seja amigável para classificar e recombinar. Por exemplo, se você estivesse fazendo uma classificação alfabética simples, poderia armazenar seus dados em 26 blocos, um para cada letra do alfabeto. Em seguida, você poderia classificar cada um deles individualmente e recombiá-los no final. As especificidades de como você pré-edita seus dados dependeriam dos dados em si, seu método de armazenamento atual, etc. Algumas configurações podem funcionar melhor para isso do que outras.
• Escreva seu próprio frontend de classificação que basicamente faz o que escrevi acima, mas na hora. Em outras palavras, você teria um script que lê a entrada e, com base em alguma operação muito rápida (como ler a primeira letra ou o que quer que funcione para seus dados), distribui essa parte de dados para o intervalo de classificação apropriado. Cada tipo opera de forma independente até que todos os dados tenham sido processados, então você reúne tudo de volta. Isso é muito semelhante a um caso especial de uso do MapReduce para classificação.
• Use uma solução de classificação baseada em MapReduce. Há um projeto Open Source chamado Hadoop que fornece vários subprojetos, um dos quais é uma implementação do MapReduce de código aberto. Eu nunca usei, no entanto, apenas li sobre isso. Não faço ideia se seria praticamente aplicável ao seu problema em particular.
• Você pode indexar os dados e depois ordenar isso? A parte inteira de 60 GB da chave de classificação? Ou há uma parte menor que você está classificando, e então um monte de dados adicionais para cada peça? Se for o último, indexar e classificar apenas algum tipo de valor-chave e, em seguida, procurar os dados adicionais conforme necessário, pode ser o caminho a ser seguido.
• Talvez você possa pré-classificar seus dados completamente e mantê-los em um estado classificado. Toda vez que você adiciona ou atualiza os dados, você os corrige de uma perspectiva ordenada. Essa solução seria altamente dependente de como você está armazenando seus dados e se o impacto no desempenho das atualizações de classificação seria aceitável.
• Por último, você poderia apostar na coisa toda. Dump seus dados em um RDBMS (eu gosto de PostgresSQL eu mesmo), e deixo o banco de dados lidar com sua classificação para você.

Sem saber muito mais sobre seus dados e as especificidades do que você está fazendo, é o melhor que posso oferecer para sugestões.

[Nota: eu não sou especialista em classificação, então alguém mais inteligente do que eu pode ser capaz de apontar erros na minha lógica, ou sugestões para melhorar isso.]

    

Answer 3

Pesquisando, encontrei muitas referências a artigos acadêmicos e um produto comercial chamado Nsort . Eu não sei nada sobre isso além de que o site deles afirma que:

Nsort is a sort/merge program that can quickly sort large amounts of data, using large numbers of processors and disks in parallel. Unique in its CPU efficiency, Nsort is the only commercial sort program to demonstrate:

• 1 Terabyte sorts (33 minutes)
• 1 Gigabyte/sec file read and write rates

Nsort has a long history of sorting massive, production data sets, such as:

• Web logs for high-traffic web sites
• Phone logs
• Government agency data

    

Answer 4

Perl?

Editar: Bem, este artigo é sobre Perl Sort Perf Tunning. Pelo que eu consigo entender, é basicamente mais um guia de boas práticas, comparando como um código de classificação ruim pode tornar seu programa muito lento, e o oposto, como torná-lo mais rápido.

Programação descuidada, desempenho desleixado.