"chọn nhanh" (hoặc tương tự) triển khai trên Linux? (thay vì sắp xếp | uniq -c | sắp xếp -rn | đầu - $ N)

Question

VẤN ĐỀ: Thường thì tôi phải đối mặt với nhu cầu xem "mẫu" lặp lại thường xuyên nhất trong ngày cuối cùng của nhật ký cụ thể là gì. Giống như đối với một nhóm nhỏ các bản ghi tomcat đây:

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

Nếu tôi muốn tìm hiểu các URL thường xuyên nhất được sử dụng (cùng với phương pháp và retcode) - Tôi sẽ thực hiện:

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

Nếu tôi muốn tìm hiểu nhiều nhất thường xuyên-tên truy nhập từ cùng một tập tin - tôi sẽ thực hiện:

[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 

trên hoạt động khá tốt trên một nhỏ dữ liệu bộ, nhưng đối với một bộ lớn hơn của đầu vào - hiệu suất (độ phức tạp) của.210 là không thể chịu đựng (nói về ~ 100 máy chủ, ~ 250 file log mỗi máy chủ, ~ dòng 1mln mỗi log file)

cố gắng giải quyết:|sort|uniq -c phần có thể dễ dàng thay thế bằng awk 1-liner, biến nó thành:

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

nhưng tôi không tìm thấy thực hiện tiêu chuẩn/đơn giản và bộ nhớ hiệu quả của "nhanh chọn thuật toán" (thảo luận here) để tối ưu hóa phần |sort -rn|head -$N. Đang tìm kiếm nhị phân GNU, RPM, awk 1-lót hoặc một số mã Ansi C dễ dàng-compilable mà tôi mới bế/trải khắp trung tâm dữ liệu, để biến:

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

vào (cho N = 3):

Tôi có thể lấy mã Java mẫu và cổng cho định dạng stdin ở trên (bằng cách này - đã ngạc nhiên khi thiếu .quickselect(...) trong lõi java) - nhưng nhu cầu triển khai java-runtime ở mọi nơi không hấp dẫn. Tôi có lẽ có thể lấy mẫu (mảng dựa trên) đoạn C của nó quá, sau đó thích ứng với định dạng trên stdin, sau đó kiểm tra và sửa chữa-rò rỉ & vv trong một thời gian. Hoặc thậm chí thực hiện nó từ đầu trong awk. NHƯNG (!) - nhu cầu đơn giản này có khả năng phải đối mặt với hơn 1% số người trên cơ sở thường xuyên - nên có được một tiêu chuẩn (trước khi thử nghiệm) thực hiện nó ra khỏi đó ?? Hy vọng ... có lẽ tôi đang sử dụng từ khóa sai lầm khi nhìn nó lên ...

chướng ngại vật khác: Cũng phải đối mặt với một vài vấn đề để làm việc xung quanh nó cho các bộ dữ liệu lớn:

• tệp nhật ký được đặt trên khối lượng được gắn trên NFS của ~ 100 máy chủ - do đó, nó có ý nghĩa song song và chia công việc thành các đoạn nhỏ hơn
• trên awk '{S[$0]+=1}... yêu cầu bộ nhớ - Tôi thấy nó chết bất cứ khi nào nó ăn lên 16GB (mặc dù có 48GB RAM miễn phí và ple nty của hoán đổi ...có thể một số giới hạn linux Tôi bỏ qua)

giải pháp hiện tại của tôi là vẫn không đáng tin cậy và không tối ưu (cơ bản dở dang) trông giống như:

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

Tôi không chắc chắn nếu văn bản công cụ nhỏ của riêng bạn được chấp nhận cho bạn, nhưng bạn có thể dễ dàng viết một công cụ nhỏ để thay thế |sort|uniq -c|sort -rn|head -$N -part với |sort|quickselect $N. Lợi ích của công cụ là, nó đọc đầu ra từ sort đầu tiên chỉ một lần, từng dòng và không giữ nhiều dữ liệu trong bộ nhớ. Trên thực tế, nó chỉ cần bộ nhớ để giữ dòng hiện tại và đầu trang $N dòng mà sau đó được in.

Đây là nguồ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; 
} 

được biên dịch với:

g++ -O3 quickselect.cpp -o quickselect 

Có, tôi nhận ra rằng mình đã yêu cầu cho out-of-the-box giải pháp, nhưng tôi không biết bất cứ điều gì có hiệu quả như nhau. Và ở trên là rất đơn giản, hầu như không có bất kỳ lề cho các lỗi (cho bạn không mess up tham số dòng lệnh số duy nhất :)