При наличии достаточно современного компьютера, обрабатывать данные «среднего размера» возможно с помощью разумного использования утилиты GNU Parallel и обработки потоков.
Шаг 1: Concatenating (cat * >> out.txt ?!)
Польза утилиты cat в Unix-системах известна большинству тех, кто когда-либо открывал Terminal. Достаточно выбрать все или некоторые файлы в папке и соединить их вместе в один большой файл. Но вот что выходит, как только файлов становится много:
$ cat * >> out.txt
-bash: /bin/cat: Argument list too long
Количество файлов превышает допустимое и компьютер не всегда может их отслеживать. Многие инструменты Unix принимают только около 10,000 аргументов; использование звездочки в команде cat расширяет управление и передает 1,234,567 аргументов утилите. В итоге появляется сообщение об ошибке.
Можно сделать следующее:
for f in *; do cat "$f" >> ../transactions_cat/transactions.csv; done
И спустя примерно 10,093 секунды образуется составной файл.
Шаг 2: GNU Parallel & Concatenation
Но можно улучшить процесс с помощью GNU Parallel:
ls | parallel -m -j $f "cat {} >> ../transactions_cat/transactions.csv"
Аргумент $f в коде выдвигается на передний план, поэтому можно выбрать уровень parallelism; но при этом линейная шкала не будет равномерной (как на рисунке ниже — graph code):
Шаг 3: Данные > RAM
После того, как миллион файликов преобразуется в один файл, возникает другая проблема. Объем данных 19.93 Гб не помещается в RAM (речь идет о ноутбуке 2014 MBP, 16 Гб RAM). Таким образом для проведения анализа нужна либо более мощная машина, либо обработка через стримминг. Или же можно воспользоваться chunked (Chunked transfer encoding).
Но продолжая говорить об использовании GNU Parallel, стоит ответить на ряд вопросов, касающихся операционных данных (на примере он-лайн магазина):
Как много уникальных продуктов было продано?
Как много сделок было проведено за день?
Как много товаров было продано в магазине за месяц?
Уникальные продукты
# Serial method (i.e. no parallelism)
# This is a simple implementation of map & reduce; tr statements represent one map, sort -u statements one reducer
# cut -d ' ' -f 5- transactions.csv | \ - Using cut, take everything from the 5th column and over from the transactions.csv file
# tr -d \" | \ - Using tr, trim off double-quotes. This leaves us with a comma-delimited string of products representing a transaction
# sort -u | \ - Using sort, put similar items together, but only output the unique values
# wc -l - Count number of unique lines, which after de-duping, represents number of unique products
$ time cut -d ' ' -f 5- transactions.csv | tr -d \" | tr ',' '\n' | sort -u | wc -l
331
real 292m7.116s
# Parallelized version, default chunk size of 1MB. This will use 100% of all CPUs (real and virtual)
# Also map & reduce; tr statements a single map, sort -u statements multiple reducers (8 by default)
$ time cut -d ' ' -f 5- transactions.csv | tr -d \" | tr ',' '\n' | parallel --pipe --block 1M sort -u | sort -u | wc -l
331
# block size performance - Making block size smaller might improve performance
# Number of jobs can also be manipulated (not evaluated)
# --500K: 73m57.232s
# --Default 1M: 75m55.268s (3.84x faster than serial)
# --2M: 79m30.950s
# --3M: 80m43.311s
Сделки за день
Если формат файла будет нежелательным для того, чтобы рассматриваться первым вопросом, то для второго он отлично подойдет. Так как каждая строка представляет операцию, все, что мы должны сделать — выполнить эквивалент SQL «Group By» в день и суммировать строки:
# Data is at transaction level, so just need to do equivalent of 'group by' operation
# Using cut again, we choose field 3, which is the date part of the timestamp
# sort | uniq -c is a common pattern for doing a 'group by' count operation
# Final tr step is to trim the leading quotation mark from date string
time cut -d ' ' -f 3 transactions.csv | sort | uniq -c | tr -d \"
real 76m51.223s
# Parallelized version
# Quoting can be annoying when using parallel, so writing a Bash function is often much easier than dealing with escaping quotes
# To do 'group by' operation using awk, need to use an associative array
# Because we are doing parallel operations, need to pass awk output to awk again to return final counts
awksub () { awk '{a[$3]+=1;}END{for(i in a)print i" "a[i];}';}
export -f awksub
time parallel --pipe awksub < transactions.csv | awk '{a[$1]+=$2;}END{for(i in a)print i" "a[i];}' | tr -d \" | sort
real 8m22.674s (9.05x faster than serial)
Общее количество продаж за день и за месяц
Для этого примера могло случиться так, что командная строка fu слабовата, но последовательный метод является одним из самых быстрых. Конечно в 14-минутное время пробега преимущества в реальном времени для «параллелизации» не настолько большие.
# Serial method uses 40-50% all available CPU prior to `sort` step. Assuming linear scaling, best we could achieve is halving the time.
# Grand Assertion: this pipeline actually gives correct answer! This is a very complex way to calculate this, SQL would be so much easier...
# cut -d ' ' -f 2,3,5 - Take fields 2, 3, and 5 (store, timestamp, transaction)
# tr -d '[A-Za-z\"/\- ]' - Strip out all the characters and spaces, to just leave the store number, timestamp, and commas to represent the number of items
# awk '{print (substr($1,1,5)"-"substr($1,6,6)), length(substr($1,14))+1}' - Split the string at the store, yearmo boundary, then count number of commas + 1 (since 3 commas = 4 items)
# awk '{a[$1]+=$2;}END{for(i in a)print i" "a[i];}' - Sum by store-yearmo combo
# sort - Sort such that the store number is together, then the month
time cut -d ' ' -f 2,3,5 transactions.csv | tr -d '[A-Za-z\"/\- ]' | awk '{print (substr($1,1,5)"-"substr($1,6,6)), length(substr($1,14))+1}' | awk '{a[$1]+=$2;}END{for(i in a)print i" "a[i];}' | sort
real 14m5.657s
# Parallelize the substring awk step
# Actually lowers processor utilization!
awksub2 () { awk '{print (substr($1,1,5)"-"substr($1,6,6)), length(substr($1,14))+1}';}
export -f awksub2
time cut -d ' ' -f 2,3,5 transactions.csv | tr -d '[A-Za-z\"/\- ]' | parallel --pipe -m awksub2 | awk '{a[$1]+=$2;}END{for(i in a)print i" "a[i];}' | sort
real 19m27.407s (worse!)
# Move parallel to aggregation step
awksub3 () { awk '{a[$1]+=$2;}END{for(i in a)print i" "a[i];}';}
export -f awksub3
time cut -d ' ' -f 2,3,5 transactions.csv | tr -d '[A-Za-z\"/\- ]' | awk '{print (substr($1,1,5)"-"substr($1,6,6)), length(substr($1,14))+1}' | parallel --pipe awksub3 | awksub3 | sort
real 19m24.851s (Same as other parallel run)
Эти три примера показали, что используя GNU Parallel за приемлемое время возможно обработать наборы данных, превышающие RAM. Однако примеры также показали, что работа с утилитами Unix способна усложняться. Сценарий командной строки помогает движению вне “one-liner” синдрома, когда конвейерная обработка становится настолько длинной, что теряется всякий логический след. Но в конечном счете проблемы легко решаются при использовании других инструментов.
Комментарии (17)
nitso
29.03.2016 14:05Любопытно, сколько ресурсов (времени на настройку и обработку, места, памяти) потребуется, чтобы построить индекс по этим данным с помощью специализированных средств. Например, загнать это все в elasticsearch.
Это определенно даст огромный выигрыш в анализе данных, но усложняет первоначальный процесс подготовки данных.
При наличии современного ноутбука достаточно легко поднимается производительная виртуалка с нужным стеком.
roller
30.03.2016 17:01В случае ES потребуется только большой диск / либо разумное использование store: false, чтобы хранились только индексы, но не исходные данные. А так особых навыков не надо. Я спокойной загонял весь текстовый массив flibusta в эластик на ноуте с 16 гигами памяти и hdd дисками. Ну да, индекс занимал гигов 50-60 (при том что исходные данные весили 350 гиг).
Self_Perfection
29.03.2016 14:41+10> Количество файлов превышает допустимое и компьютер не всегда может их отслеживать. Многие инструменты Unix принимают только около 10,000 аргументов; использование звездочки в команде cat расширяет управление и передает 1,234,567 аргументов утилите. В итоге появляется сообщение об ошибке.
Мне кажется тут автор слабо понимает, что вообще происходит в системе. Звёдочка при таком подходе используется не в cat, а в вашем шелле. Который звёздочку раскрывает и вызывает утилиту (полезно отличать внешние утилиты от встроенных команд шелла) cat с множеством аргументов. Убедиться для наглядности можно так:
cat * /proc/self/cmdline
При этом упираемся в предел максимальной длины аргументов, которые может ядро передать процессу. Посмотреть предел:
$ getconf ARG_MAX
524288
Это в байтах. ЕМНИП, выставляется он при компиляции ядра. Строки аргументов передаются в одном массиве, разделённом нулями (см. /proc/$PID/cmdline), при этом стоит иметь ввиду, что в ARG_MAX должны вписаться не только параметры командной строки, но и переменные окружения + ещё мелочи.
> for f in *; do cat «$f» >> ../transactions_cat/transactions.csv; done
Это ужасно. На каждый файл запускается свой экземпляр утилиты cat. Запуск нового процесса довольно дорогая операция, какой бы он ни был простой и маложрущий, не стоит ожидать, что система сможет запускать больше ~1000 процессов в секунду (на одном ядре).
> ls | parallel -m -j $f «cat {} >> ../transactions_cat/transactions.csv»
Знаете что у вас тут тормозит? ls :) Не забываем, что ls при вызове без аргументов сортирует вывод, а сложность сортировки n*log(n) и на миллионе файлов она становится медленной и печальной. Но можно сказать ls не заниматься лишней работой с сортировкой:
ls -U
Кстати, проблема с сортировкой есть и при использовании * шелла
Но вообще всё это фигня. Нужно просто вызвать несколько раз cat передав ему максимум аргментов, сколько можно передать за раз. Результат конечно зависит от средней длины имени файла, но можно легко ожидать, что один вызов cat приведёт к выводу примерно 1000 файлов. И ускорение будет значительно.
find -type f -exec cat {} +
Магия в использовании +
ЗЫ: а зачем вообще нестандартный parallel, если стандартный xargs умеет --max-procs и --max-args?
DuD
30.03.2016 15:08Тот самый момент когда комментарии ценнее поста.
Скажите, в чем магия использования "+"?Self_Perfection
30.03.2016 22:46Для шелла + не несёт специального значения (если не внутри особых случаев, вроде арифметики $(( var+5)) ) и передаётся как есть аргументом запускаемому find.
Action -exec у find требует после терминировать список аргументов запускаемой команды. Это можно сделать либо с помощью аргумента ';', либо с помощью '+'. Поведение отличается: с плюсом запускаемой команде в аргументах будет передаваться по нескольку файлов, сколько влезает в ARG_MAX. См. man find
>Тот самый момент когда комментарии ценнее поста.
комментарий при этом получает +9, а карма автора комментария — -2. Типичный хабр.chersanya
31.03.2016 00:51Спасибо, тоже не знал про "+", хотя саму команду часто использую!
А карму вам нельзя поднять, т.к. статей нет (можно только опускать) :)
ptomaine
29.03.2016 16:09-1ls | parallel -m -j $f «cat {} >> ../transactions_cat/transactions.csv»
Даже удивительно, что это команда у вас отработала нормально. Стандартные потоки вывода разных экземпляровcatсмешаются и получиться некорректный файл. И проблема не в том, что строки будут переставлены местами, а в том что из
test1,test2,test3
и
abc1,abc2,abc3
получится
test1,test2,abc1,abc2,abc3
test3
Stas911
29.03.2016 17:25Интересно было бы Spark-ом попробовать. Ваши выборки, на первый взгляд, хорошо ложатся и не нужно в один файл сливать перед обработкой.
DjOnline
30.03.2016 14:42Что за бред я сейчас прочитал? Что это за ненормальный магазин, который сразу не хранит продажи в базе данных, откуда их потом можно как угодно сгруппировать, например с помощью SELECT xx WITH ROLLUP
isden
Один мой клиент в подобных случаях просто загонял этот огромный CSV в табличку в mysql и уже там делал все нужные выборки.
Vurtatoo
Почти всегда так делаю, когда нужно анализировать не очень большое кол-во данных.
nikitasius
Так и надо делать всегда. Индексы расставить и любая выборка в радость.
kay
Лет 5 назад на собеседовании в nVidia мне задали подобный вопрос: "Как быстрее всего отсортировать данные из файла по определенному столбцу?". Я сразу сказал про реляционную БД и индексы. На что мне ответили: sort отрабатывает быстрее (а порой на много быстрее), чем перегонка данных в реляционную БД и последующая сортировка с выводом.
А собеседования я завалил, о чем, впрочем, не жалею.
isden
Если нужно просто отсортировать один раз — то и смысла заморачиваться с БД нет. Смысл есть, если нужно сделать несколько разных выборок.
achekalin
Судя по вопросу, размер файла никак не обговаривался. А я, скажем, легко себе представляю файлик, который sort вместе с ОС загонит в грустную задумчивость по причине задумчивости машины. Тогда как вариант с БД, как бы он не был монстрообразен, сработает, хотя, может быть, и долго проработает.