Pull to refresh
205.14
ua-hosting.company
Хостинг-провайдер: серверы в NL до 300 Гбит/с

Миллион файлов и один ноутбук

Reading time 5 min
Views 13K
Рассмотрим на примере он-лайн магазина, как с помощью ноутбука проанализировать миллион файлов.



При наличии достаточно современного компьютера, обрабатывать данные «среднего размера» возможно с помощью разумного использования утилиты 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” синдрома, когда конвейерная обработка становится настолько длинной, что теряется всякий логический след. Но в конечном счете проблемы легко решаются при использовании других инструментов.
Tags:
Hubs:
+12
Comments 17
Comments Comments 17

Articles

Information

Website
ua-hosting.company
Registered
Founded
Employees
11–30 employees
Location
Латвия
Representative
HostingManager