"быстрый выбор" (или аналогичная) реализация в Linux? (вместо sort|uniq -c|sort -rn|head -$N)

ПРОБЛЕМА. Часто я сталкиваюсь с необходимостью увидеть, какие наиболее часто повторяющиеся "шаблоны" в последний день конкретных журналов. Как для небольшого подмножества логов tomcat здесь:

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
...

Если я хочу узнать наиболее часто используемые URL-адреса (вместе с методом и ретакодом) - я сделаю:

[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)

Если я захочу узнать наиболее часто встречающееся имя пользователя из того же файла, я сделаю:

[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

Выше очень хорошо работает на небольших наборах данных, но для больших наборов входных данных - производительность (сложность) sort|uniq -c|sort -rn|head -$N невыносимо (говорить о ~100 серверах, ~250 файлов журнала на сервер, ~1 млн строк на файл журнала)

Попытка решить: |sort|uniq -c деталь можно легко заменить на 1-й вкладыш awk, превратив его в:

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

но мне не удалось найти стандартную / простую и эффективную по памяти реализацию "алгоритма быстрого выбора" (обсуждаемого здесь) для оптимизации |sort -rn|head -$N часть. Искал бинарные файлы GNU, rpms, awk 1-liners или какой-нибудь легко компилируемый код Ansi C, который я мог бы переносить / распространять по центрам обработки данных, чтобы включить:

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

в (учитывая N=3):

225 magic balls
93  juicy melons
55  rusty ideas

Я, вероятно, мог бы взять образец Java-кода и перенести его для вышеупомянутого формата stdin (кстати - был удивлен отсутствием .quickselect(...) в ядре Java) - но необходимость развертывания java-среды выполнения везде не привлекательна. Возможно, я мог бы также взять образец (на основе массива) фрагмента C, затем адаптировать его к формату выше стандартного stdin, затем на некоторое время проверить и исправить утечки и т. Д. Или даже реализовать его с нуля в awk. НО (!) - с этой простой потребностью, вероятно, сталкиваются более 1% людей на регулярной основе - там должна была быть стандартная (предварительно протестированная) реализация этого?? Надежды... возможно, я использую неправильные ключевые слова, чтобы найти его...

ДРУГИЕ ПРЕПЯТСТВИЯ: Также столкнулся с парой проблем, чтобы обойти это для больших наборов данных:

  • файлы журналов расположены на смонтированных NFS томах ~100 серверов - поэтому имеет смысл распараллеливать и разбивать работу на более мелкие куски
  • выше awk '{S[$0]+=1}... требует памяти - я вижу, как он умирает всякий раз, когда он съедает 16 ГБ (несмотря на наличие 48 ГБ свободной оперативной памяти и большое количество подкачки... возможно, какой-то предел Linux я пропустил)

Мое текущее решение все еще не надежно и неоптимально (в процессе) выглядит так:

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
Источник

1 ответ

Я не уверен, что написание собственного маленького инструмента приемлемо для вас, но вы можете легко написать небольшой инструмент для замены |sort|uniq -c|sort -rn|head -$N-расставаться с |sort|quickselect $N, Преимущество инструмента заключается в том, что он читает выходные данные первого sort только один раз, построчно и без большого объема данных в памяти. На самом деле, ему нужна только память, чтобы держать текущую строку и верхнюю $N строки, которые затем печатаются.

Вот источник 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;
}

компилироваться с:

g++ -O3 quickselect.cpp -o quickselect

Да, я понимаю, что вы просили о готовых решениях, но я не знаю ничего, что было бы столь же эффективным. А вышесказанное настолько просто, что для ошибок едва ли есть запас (если вы не перепутаете один числовой параметр командной строки:)

Источник
Другие вопросы по тегам