Implementazione "quick select" (o simile) su Linux? (invece di ordinare | uniq -c | sort -rn | head - $ N)

Question

PROBLEMA: Spesso mi trovo di fronte all'esigenza di vedere quali sono i "pattern" più frequenti durante l'ultimo giorno di log specifici. Come per un piccolo sottoinsieme di tronchi Tomcat qui:

GET /app1/public/pkg_e/v3/555413242345562/account/stats 401 954 5 
GET /app1/public/pkg_e/v3/555412562561928/account/stats 200 954 97 
GET /app1/secure/pkg_e/v3/555416251626403/ex/items/ 200 517 18 
GET /app1/secure/pkg_e/v3/555412564516032/ex/cycle/items 200 32839 50 
DELETE /app1/internal/pkg_e/v3/accounts/555411543532089/devices/bbbbbbbb-cccc-2000-dddd-43a8eabcdaa0 404 - 1 
GET /app1/secure/pkg_e/v3/555412465246556/sessions 200 947 40 
GET /app1/public/pkg_e/v3/555416264256223/account/stats 401 954 4 
GET /app2/provisioning/v3/555412562561928/devices 200 1643 65 
... 

Se voglio scoprire gli URL più-di uso frequente (insieme con metodo e retcode) - lo farò:

[root@srv112:~]$ N=6;cat test|awk '{print $1" "$2" ("$3")"}'\ 
|sed 's/[0-9a-f-]\+ (/%GUID% (/;s/\/[0-9]\{4,\}\//\/%USERNAME%\//'\ 
|sort|uniq -c|sort -rn|head -$N 
     4 GET /app1/public/pkg_e/v3/%USERNAME%/account/stats (401) 
     2 GET /app1/secure/pkg_e/v3/%USERNAME%/devices (200) 
     2 GET /app1/public/pkg_e/v3/%USERNAME%/account/stats (200) 
     2 DELETE /app1/internal/pkg_e/v3/accounts/%USERNAME%/devices/%GUID% (404) 
     1 POST /app2/servlet/handler (200) 
     1 POST /app1/servlet/handler (200) 

Se voglio scoprire la più frequente-username dalla stesso file - farò:

[root@srv112:~]$ N=4;cat test|grep -Po '(?<=\/)[0-9]{4,}(?=\/)'\ 
|sort|uniq -c|sort -rn|head -$N 
     9 555412562561928 
     2 555411543532089 
     1 555417257243373 
     1 555416264256223 

sopra funziona abbastanza bene su un piccolo data-set, ma per una più grande set di ingresso - le prestazioni (complessità) di sort|uniq -c|sort -rn|head -$N è insopportabile (parlando ~ 100 server, ~ 250 file di log per server, ~ righe 1mln per file di log)

tentativo di risolvere:|sort|uniq -c parte può essere facilmente sostituito con awk 1-liner, trasformandolo in:

|awk '{S[$0]+=1}END{for(i in S)print S[i]"\t"i}'|sort -rn|head -$N 

ma non sono riuscito a trovare implementazione standard/semplice e la memoria-efficiente di "Quick select algoritmo" (discusso here) per ottimizzare la parte |sort -rn|head -$N. cercava binari GNU, giri, awk 1-liners o qualche facilmente compilabile codice ANSI C che ho potuto portare/sparsi data center, girare:

3 tasty oranges 
225 magic balls 
17 happy dolls 
15 misty clouds 
93 juicy melons 
55 rusty ideas 
... 

in (dato N = 3):

225 magic balls 
93 juicy melons 
55 rusty ideas 

probabilmente potuto afferrare il codice Java di esempio e la porta è per il formato standard input sopra (tra l'altro - è stato sorpreso dalla mancanza di .quickselect(...) all'interno nucleo java) - ma la necessità di implementare java-runtime ovunque non è attraente. Magari potrei prendere anche un frammento di esempio di C (basato su array), quindi adattarlo al formato di stdin sopra, quindi alle perdite di test-and-fix & per un po 'di tempo. O addirittura implementarlo da zero in awk. MA (!) - questo semplice bisogno è probabilmente affrontato da più dell'1% delle persone su base regolare - ci dovrebbe essere stata una implementazione standard (pre-testata) là fuori ?? speranze ... forse sto usando le parole chiavi sbagliate di guardare in su ...

altri ostacoli: di fronte anche un paio di problemi a lavorare in giro per grandi insiemi di dati:

• log file si trovano sui volumi NFS montati su ~ 100 server - quindi reso senso per parallelizzare e dividere il lavoro in porzioni più piccole
• quanto sopra awk '{S[$0]+=1}... richiede memoria - sto vedendo morire ogni volta che mangia 16GB (nonostante abbia 48 GB di RAM libera e ple nty di swap ...forse qualche limite linux ho trascurato)

mia soluzione attuale non è ancora affidabile e non-ottimale (in corso) si presenta come:

find /logs/mount/srv*/tomcat/2013-09-24/ -type f -name "*_22:*"|\ 
# TODO: reorder 'find' output to round-robin through srv1 srv2 ... 
#  to help 'parallel' work with multiple servers at once 
parallel -P20 $"zgrep -Po '[my pattern-grep regexp]' {}\ 
|awk '{S[\$0]+=1} 
END{for(i in S)if(S[i]>4)print \"count: \"S[i]\"\\n\"i}'" 
# I throw away patterns met less than 5 times per log file 
# in hope those won't pop on top of result list anyway - bogus 
# but helps to address 16GB-mem problem for 'awk' below 
awk '{if("count:"==$1){C=$2}else{S[$0]+=C}} 
END{for(i in S)if(S[i]>99)print S[i]"\t"i}'|\ 
# I also skip all patterns which are met less than 100 times 
# the hope that these won't be on top of the list is quite reliable 
sort -rn|head -$N 
# above line is the inefficient one I strive to address 

Answer 1

non sono sicuro se la scrittura il proprio piccolo strumento è accettabile per te, ma puoi facilmente scrivere un piccolo strumento per sostituire la parte |sort|uniq -c|sort -rn|head -$N con |sort|quickselect $N. Il vantaggio dello strumento è che legge l'output dal primo sort una sola volta, riga per riga e senza conservare molti dati in memoria. In realtà, è sufficiente che la memoria tenga la linea corrente e le prime righe $N che vengono poi stampate.

Ecco la fonte quickselect.cpp:

#include <iostream> 
#include <string> 
#include <map> 
#include <cstdlib> 
#include <cassert> 

typedef std::multimap< std::size_t, std::string, std::greater<std::size_t> > winner_t; 
winner_t winner; 
std::size_t max; 

void insert(int count, const std::string& line) 
{ 
    winner.insert(winner_t::value_type(count, line)); 
    if(winner.size() > max) 
     winner.erase(--winner.end()); 
} 

int main(int argc, char** argv) 
{ 
    assert(argc == 2); 
    max = std::atol(argv[1]); 
    assert(max > 0); 
    std::string current, last; 
    std::size_t count = 0; 
    while(std::getline(std::cin, current)) { 
     if(current != last) { 
      insert(count, last); 
      count = 1; 
      last = current; 
     } 
     else ++count; 
    } 
    if(count) insert(count, current); 
    for(winner_t::iterator it = winner.begin(); it != winner.end(); ++it) 
     std::cout << it->first << " " << it->second << std::endl; 
} 

da compilare con:

g++ -O3 quickselect.cpp -o quickselect 

Sì, mi rendo conto che stavi chiedendo soluzioni out-of-the-box, ma io non so nulla che sarebbe ugualmente efficiente. E quanto sopra è così semplice, non c'è quasi nessun margine per gli errori (dato che non si incasina il singolo parametro numerico della riga di comando :)