问题:我经常需要查看特定日志的最后一天内最常重复的“模式”是什么。就像这里的一小部分 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(连同方法和 retcode)- 我会这样做:

[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 个日志文件，每个日志文件约 100 万行)

尝试解决: |sort|uniq -c 部分可以很容易地用 awk 1-liner 替换，将其变成:

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

但我没能找到“快速选择算法”(已讨论 here)的标准/简单且内存高效的实现来优化 |sort -rn|head -$N 部分。 正在寻找 GNU 二进制文件、rpm、awk 1 行或一些易于编译的 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 代码并将其移植为以上标准输入格式(顺便说一下 - 对核心 java 中缺少 .quickselect(...) 感到惊讶) - 但需要到处部署 java-runtime 并不吸引人。 我也许也可以获取它的示例(基于数组的)C 代码片段，然后将其调整为上述标准输入格式，然后测试并修复泄漏等一段时间。或者甚至在 awk 中从头开始实现它。 但是(!)——超过 1% 的人可能经常面临这个简单的需求——应该有一个标准的(预测试的)实现吗？ 希望...也许我使用了错误的关键字来查找...

其他障碍:还面临着解决大型数据集问题的几个问题:

• 日志文件位于约 100 台服务器的 NFS 挂载卷上 - 所以它 将工作并行化和拆分成更小的 block 是有意义的
• 上面的 awk '{S[$0]+=1}... 需要内存 - 我看到它死了 每当它吃掉 16GB(尽管有 48GB 的​​可用内存和 大量交换......也许我忽略了一些 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

最佳答案

我不确定您是否可以接受自己编写的小工具，但是您可以轻松地编写一个小工具来替换 |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

是的，我知道您要求的是开箱即​​用的解决方案，但我不知道有什么同样有效的解决方案。上面的内容非常简单，几乎没有任何错误余地(前提是您没有弄乱单个数字命令行参数:)

关于linux - "quick select"(或类似)在 Linux 上的实现？ (而不是 sort|uniq -c|sort -rn|head -$N)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19434405/