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

    Рассмотрим на примере он-лайн магазина, как с помощью ноутбука проанализировать миллион файлов.



    При наличии достаточно современного компьютера, обрабатывать данные «среднего размера» возможно с помощью разумного использования утилиты 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” синдрома, когда конвейерная обработка становится настолько длинной, что теряется всякий логический след. Но в конечном счете проблемы легко решаются при использовании других инструментов.
    ua-hosting.company
    571,00
    Хостинг-провайдер: серверы в NL / US до 100 Гбит/с
    Поделиться публикацией

    Комментарии 17

      +4
      Один мой клиент в подобных случаях просто загонял этот огромный CSV в табличку в mysql и уже там делал все нужные выборки.
        0
        Почти всегда так делаю, когда нужно анализировать не очень большое кол-во данных.
          +1
          Так и надо делать всегда. Индексы расставить и любая выборка в радость.
          0
          Лет 5 назад на собеседовании в nVidia мне задали подобный вопрос: "Как быстрее всего отсортировать данные из файла по определенному столбцу?". Я сразу сказал про реляционную БД и индексы. На что мне ответили: sort отрабатывает быстрее (а порой на много быстрее), чем перегонка данных в реляционную БД и последующая сортировка с выводом.
          А собеседования я завалил, о чем, впрочем, не жалею.
            0
            Если нужно просто отсортировать один раз — то и смысла заморачиваться с БД нет. Смысл есть, если нужно сделать несколько разных выборок.
              0
              Судя по вопросу, размер файла никак не обговаривался. А я, скажем, легко себе представляю файлик, который sort вместе с ОС загонит в грустную задумчивость по причине задумчивости машины. Тогда как вариант с БД, как бы он не был монстрообразен, сработает, хотя, может быть, и долго проработает.
            0
            Любопытно, сколько ресурсов (времени на настройку и обработку, места, памяти) потребуется, чтобы построить индекс по этим данным с помощью специализированных средств. Например, загнать это все в elasticsearch.
            Это определенно даст огромный выигрыш в анализе данных, но усложняет первоначальный процесс подготовки данных.
            При наличии современного ноутбука достаточно легко поднимается производительная виртуалка с нужным стеком.
              0
              В случае ES потребуется только большой диск / либо разумное использование store: false, чтобы хранились только индексы, но не исходные данные. А так особых навыков не надо. Я спокойной загонял весь текстовый массив flibusta в эластик на ноуте с 16 гигами памяти и hdd дисками. Ну да, индекс занимал гигов 50-60 (при том что исходные данные весили 350 гиг).
              +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?
                0
                Тот самый момент когда комментарии ценнее поста.
                Скажите, в чем магия использования "+"?
                  0
                  Для шелла + не несёт специального значения (если не внутри особых случаев, вроде арифметики $(( var+5)) ) и передаётся как есть аргументом запускаемому find.
                  Action -exec у find требует после терминировать список аргументов запускаемой команды. Это можно сделать либо с помощью аргумента ';', либо с помощью '+'. Поведение отличается: с плюсом запускаемой команде в аргументах будет передаваться по нескольку файлов, сколько влезает в ARG_MAX. См. man find

                  >Тот самый момент когда комментарии ценнее поста.
                  комментарий при этом получает +9, а карма автора комментария — -2. Типичный хабр.
                    0
                    Спасибо, тоже не знал про "+", хотя саму команду часто использую!
                    А карму вам нельзя поднять, т.к. статей нет (можно только опускать) :)
                –1
                ls | parallel -m -j $f «cat {} >> ../transactions_cat/transactions.csv»

                Даже удивительно, что это команда у вас отработала нормально. Стандартные потоки вывода разных экземпляров cat смешаются и получиться некорректный файл. И проблема не в том, что строки будут переставлены местами, а в том что из
                test1,test2,test3

                и
                abc1,abc2,abc3

                получится
                test1,test2,abc1,abc2,abc3
                test3
                  0
                  Интересно было бы Spark-ом попробовать. Ваши выборки, на первый взгляд, хорошо ложатся и не нужно в один файл сливать перед обработкой.
                    0
                    Что за бред я сейчас прочитал? Что это за ненормальный магазин, который сразу не хранит продажи в базе данных, откуда их потом можно как угодно сгруппировать, например с помощью SELECT xx WITH ROLLUP
                      +1
                      Статья не про магазин. Статься про Linux\Shell и его утилиты.
                        –2
                        Ну так и не надо тогда упоминать слово «магазин» и «транзакции» в тексте.

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое