Gerando IDs exclusivos para indexação de conteúdo json

2

Estou procurando uma geração de ID simples e eficaz para o seguinte conteúdo usando o script bash:

{"name": "John", "surname": "Gates", "country": "Germany", "age": "20", "height": "180"}
{"name": "John1", "surname": "Gates", "country": "Germany", "age": "20", "height": "180"}
{"name": "John2", "surname": "Gates", "country": "Germany", "age": "20", "height": "180"}
{"name": "John3", "surname": "Gates", "country": "Germany", "age": "20", "height": "180"}


{"id": "XXX", "name": "John", "surname": "Gates", "country": "Germany", "age": "20", "height": "180"}
{"id": "XXX", "name": "John1", "surname": "Gates", "country": "Germany", "age": "20", "height": "180"}
{"id": "XXX", "name": "John2", "surname": "Gates", "country": "Germany", "age": "20", "height": "180"}
{"id": "XXX", "name": "John3", "surname": "Gates", "country": "Germany", "age": "20", "height": "180"}

Eu terei aproximadamente 5.000.000 de registros semelhantes e desejo gerar uma ID previsível e repetível. Como serei limitado pelo tempo para processar o seguinte arquivo, eu preciso fazê-lo em 20 minutos janela para banco de dados sql lite em uma máquina Linux.

MD5, o SHA1 é muito caro para ser usado, a menos que eu possa fazer algo como o GNU Parallel em 16 threads na CPU AMD Ryzen 1900X que conseguirá fazer isso em poucos minutos?

Eu tentei com o MD5, consegui 28.000 IDs calculados com 1 min e 45 segundos. Com o SHA1, demorei 2 minutos e 3 segundos.

Eu estava pensando em criar um ID muito simples:

JohnGatesGermany20180
John1GatesGermany20180
John2GatesGermany20180
John3GatesGermany20180

O que você poderia recomendar onde os seguintes requisitos devem ser atendidos:

  • bash
  • Linux
  • 5.000.000 de registros para processar
  • abaixo de 20 minutos
  • id tem que ser o mesmo para as mesmas linhas json

Testes realizados:

#!/usr/local/bin/bash

while IFS= read -r line
do
   uuid=$(uuidgen -s --namespace @dns --name "www.example.com" )
done < testfile1.txt

md5 hash de 1.000.000 linhas:

$time bash script.sh 

real    13m6.914s
user    10m24.523s
sys 2m56.095s

cksum fazendo crc em 1.000.000:

#!/usr/local/bin/bash

while IFS= read -r line
do
#    uuid=$(uuidgen -s --namespace @dns --name "www.example.com" )
    echo "$line $uuid"|cksum >> test3.txt
done < testfile1.txt

$time bash script.sh 

real    12m49.396s
user    12m23.219s
sys 4m1.417s
    
por Anna 02.08.2018 / 22:43

3 respostas

1

Quanto mais um experimento de pensamento eu queria ver até onde poderíamos usar as ferramentas CLI para resolver esse tipo de problema. Para esse fim, eu queria tentar usar a ferramenta de CLI hash rápido xxHash para fazer este trabalho.

xxHash is an extremely fast non-cryptographic hash algorithm, working at speeds close to RAM limits. It is proposed in two flavors, 32 and 64 bits.

Ele está disponível em todas as linguagens de programação, mas para este experimento, vou usar o sabor do CLI, xxhsum , especificamente o modo de 32 bits, então xxhsum -H0 .

Como você descobriu e como os outros afirmaram, chamar a ferramenta CLI da função hash, ou qualquer ferramenta, é geralmente onde esses tipos de abordagens caem. Chamar o xxhsum aqui 5M vezes seria uma maneira insuficiente de usá-lo. Sua força está no arquivo I / O, então e se fôssemos pegar as linhas de 5M e convertê-las em arquivos de 5M?

Essa tarefa é realmente trivial no Linux, usando o comando split :

split -l 1 afile

E quão rápido seria o hash, digamos 1M, desses arquivos, cada um com uma linha neles assim.

exemplo 1 arquivo de linha
$ cat datadir/xzeyw
{"name": "John4000", "surname": "Gates", "country": "Germany", "age": "20", "height": "180"} 
diretório com arquivos 1M
$ ls -l datadir | wc -l
1000002
tempo para hash eles
$ { time xxhsum -H0 * > ../nfile 2>&1 ;} |& awk '/real|user|sys/ {print $1": "$2"\t"}' | tr -d '\n'
real: 0m6.998s  user: 0m5.007s  sys: 0m1.569s

Sim, está correto, demorou ~ 7 segundos! Eu acho isso bastante impressionante. Usando xxhsum dessa maneira, só incorremos no custo de executá-lo uma vez e permitimos que ele passasse por arquivos 1M.

Desvantagens para este método

Então, uma das desvantagens de fazer isso dessa maneira é, claro, o split . Isso se torna nossas operações mais caras, como você pode imaginar. Já que estamos tendo que pegar um único arquivo com linhas X e explodi-lo no disco rígido como arquivos X com uma única linha.

Veja alguns desses dados:

./hashy.bash

make data
---------
real: 0m17.492s user: 0m12.434s sys: 0m4.788s

split data
----------
real: 2m15.180s user: 0m0.700s  sys: 2m4.443s

hash data
---------
real: 0m6.487s  user: 0m5.798s  sys: 0m0.459s

Aqui podemos ver que nossa operação split demorou ~ 2 minutos. NOTA: A primeira linha desta saída mostra o tempo para construir um arquivo com 1M linhas de JSON nele.

Outra desvantagem é o número de arquivos com os quais estamos lidando na linha de comando. Estou usando * em lugares e isso vai se expandir para nomes de arquivos de 1M ou 5M, o que pode ser considerado perigoso, é. Lembre-se de que, ao aumentar o número de arquivos, você corre o risco de exceder a quantidade de espaço alocado para os argumentos da linha de comando.

Refira estes links a respeito do comprimento da linha de comando:

Conclusão

Então, como você pode imaginar, resolver um problema como este usando arquivos de 1M ou arquivos de 5M parece quase ridículo. E eu teria que concordar. Mas ainda é uma experiência interessante, pois mostra que, se você alavancar as ferramentas CLI de maneira apropriada, poderá obter um excelente desempenho delas.

Código para hashy.bash

Se alguém estiver interessado no código:

$ cat hashy.bash
#!/bin/bash

echo ""
echo "make data"
echo "---------"
rm -f afile
{ time for i in {0..1000000};do echo "{\"name\": \"John${i}\", \"surname\": \"Gates\", \"country\": \"Germany\", \"age\": \"20\", \"height\": \"180\"}">> afile ;done ;} \
  |& awk '/real|user|sys/ {print $1": "$2"\t"}' | tr -d '\n'
echo ""
echo ""

rm -fr datadir && mkdir datadir && cd datadir

echo "split data"
echo "----------"
{ time split -l 1 ../afile ;} |& awk '/real|user|sys/ {print $1": "$2"\t"}' | tr -d '\n'
echo ""
echo ""

echo "hash data"
echo "---------"
{ time xxhsum -H0 * > ../nfile 2>&1 ;} |& awk '/real|user|sys/ {print $1": "$2"\t"}' | tr -d '\n'

cd - > /dev/null 2>&1
echo ""
echo ""

Referências

por 03.08.2018 / 09:29
3

Aposto que o motivo pelo qual seus scripts demoram tanto é a execução de uuidgen (ou cksum ) para cada linha. Muito tempo é desperdiçado simplesmente iniciando os processos para cada um deles.

Colocando 5M linhas do formulário {"name": "John%d", "surname": "Gates", "country": "Germany", "age": "20", "height": "180"} em um arquivo em um sistema de arquivos tmpfs, o seguinte script do Python foi concluído em segundos:

#! /usr/bin/env python3

import hashlib
import sys
for line in sys.stdin:
    print(hashlib.md5(line.rstrip('\n').encode('utf-8')).hexdigest())

Execução:

$ time ./foo.py < input > output
./foo.py < input > output  6.00s user 0.13s system 99% cpu 6.135 total
% wc -l input output
  5000000 input
  5000000 output
 10000000 total

Como esse é o Python, você também pode decodificar as linhas em JSON e inserir uma ID em cada uma delas. Mesmo código ineficiente como:

#! /usr/bin/env python3

import hashlib
import json
import sys
for line in sys.stdin:
    l = line.rstrip('\n').encode('utf-8')
    o = json.loads(line)
    o["id"] = hashlib.md5(l).hexdigest()
    print(json.dumps(o))

Terminado em menos de um minuto:

% time ./foo.py < input > output
./foo.py < input > output  42.11s user 0.42s system 99% cpu 42.600 total

% head output 
{"name": "John1", "surname": "Gates", "country": "Germany", "age": "20", "height": "180", "id": "2dc573ccb15679f58abfc44ec8169e52"}
{"name": "John2", "surname": "Gates", "country": "Germany", "age": "20", "height": "180", "id": "ee0583acaf8ad0e502bf5abd29f37edb"}
{"name": "John3", "surname": "Gates", "country": "Germany", "age": "20", "height": "180", "id": "a7352ebb79db8c8fc2cc8758eadd9ea3"}
{"name": "John4", "surname": "Gates", "country": "Germany", "age": "20", "height": "180", "id": "2062ad1b67ccdce55663bfd523ce1dfb"}
{"name": "John5", "surname": "Gates", "country": "Germany", "age": "20", "height": "180", "id": "5f81325c104c01c3e82abd2190f14bcf"}
{"name": "John6", "surname": "Gates", "country": "Germany", "age": "20", "height": "180", "id": "493e0c9656f74ec3616e60886ee38e6a"}
{"name": "John7", "surname": "Gates", "country": "Germany", "age": "20", "height": "180", "id": "19af9ef2e20466d0fb0efcf03f56d3f6"}
{"name": "John8", "surname": "Gates", "country": "Germany", "age": "20", "height": "180", "id": "2348bd47b20ac6445213254c6a8aa80b"}
{"name": "John9", "surname": "Gates", "country": "Germany", "age": "20", "height": "180", "id": "090a521b4a858705dc69bf9c8dca6c19"}
{"name": "John10", "surname": "Gates", "country": "Germany", "age": "20", "height": "180", "id": "fc3c699323cbe399e210e4a191f04003"}

Minhas especificações:

  • CPU Intel® Core ™ i7-8700 a 3.20GHz × 12
  • 2666MHz de memória DDR4

O script uuidgen -based mal conseguiu concluir 500k linhas em 4 minutos. Modificado para salvar a saída:

#!/usr/bin/bash

while IFS= read -r line
do
   uuidgen -s --namespace @dns --name "$line"
done < input > uuid

Execução:

% timeout 240 ./foo.sh
% wc -l uuid
522160 uuid
    
por 03.08.2018 / 04:08
1

Uma implementação da sua ideia de ID simples no awk, assumindo que as linhas JSON são as que você indicou - todas em uma linha:

awk -F'"' 'BEGIN{OFS=FS} {$1=$1"\"id\": \""$4$8$12$16$20"\", "; }1' < input

Eu não tenho um sistema comparável ao seu, então você terá que ver se o tempo é aceitável.

    
por 03.08.2018 / 03:48