В этом блоге уже много написано о самом языке Haskell, и было несколько статей о его практическом применении. Сейчас я вдохновенно расскажу еще об одном реальном применении языка в производстве.
Я работаю в телекомах: фиксированная телефонная связь, интернет, IP-телефония. В задачи входит обработка трафика с АТС, с серверов IP-телефонии, поддержка текущего биллинга, написание софта и администрирование сетей, домена (да, «программист на все руки»). Недавно в моей организации было установлено новое оборудование, работающее совсем по другим принципам, и трафик, соответственно, тоже изменился. Теперь он поставляется в двух вариантах: со старых станций и с новых. Новый трафик дублируется в бинарном и текстовом форматах. Бинарники нам вообще не подходят (хотя кое-кто по незнанию говорил: «А чего там? Берешь их, и они сами в биллинг заскакивают!»), текстовый же занимает на порядок больше места, но именно с ним можно что-то сделать. Трафик со старого оборудования все еще идет, и его мы с напарником забрасываем с помощью отработанных схем, использующих сервисы местной СУБД. Можно было бы настроить эти же сервисы для трафика с новых станций, но обнаружилось несколько особенностей. Трафик на новых станциях пишется в отдельные файлы каждые 15 минут; всего таких файлов за месяц получается около 3000 (в идеале — 2976 за 31 день и 2880 за 30 дней). Каждый файл отдельно импортировать не будешь, ибо маразм. Слить в один их можно и даже нужно, благо они все текстовые, и записи о звонках расположены построчно. Ручное слияние выглядит так: выделяешь файлы только за прошлый месяц и добавляешь их в простейший скрипт слияния в командной строке. Формат имени файла фиксирован, следовательно, слияние можно автоматизировать, только придется парсить год и месяц. Линуксоиды бы использовали какой-нибудь Bash, Perl или Python, — дешево и сердито, но на Windows-машину их ради одной операции не поставишь, то же самое касается и PowerShell. А cmd — это извращение, о чем мы с вами хорошо знаем. ;) Наконец, в самом трафике тоже обнаружились сюрпризы, из-за которых даже после слияния и импорта с помощью средств СУБД требовалось много ручной SQL-работы. В общем, факторы как-то так удачно сложились в задачу для Haskell, который я в то время (апрель-май 2011) начал изучать.
Итак, ~ 3000 15-тиминутных файлов за месяц. На оборудовании можно изменить интервал и поставить не 15 минут, а любое другое значение: 5, 10, 30, 45… Количество файлов и их размеры, соответственно, изменятся. Пример имени файла (за 09.05.2011 09:30:00):
Абонентов становится больше, и каждый файл уверенно растет в размере. Сейчас у нас в среднем 240 строчек на файл, но было сезонное летнее проседание, люди разъехались по отпускам и звонили меньше. За сентябрь ждем увеличения активности в полтора-два раза.
Записи о звонках разнообразны. Есть несколько разных типов записей, у которых разное количество полей. Записи типа R210 попадаются очень редко, и что они значат, мы не стали выяснять (здесь и далее данные трафика заменены случайными):
Как нетрудно убедиться, здесь всего лишь 4 поля: идентификатор типа записи, дата начала, дата конца (формат ISO 8601/SQL) и, зачем-то, единичка. Поля разделяются вертикальной чертой, которая должна стоять и в начале записи, и в конце, так что реально полей на 1 больше, то есть, 5. Удобно считать, что поле с индексом 0 пустое, находится перед первой вертикальной чертой. Тогда отсчет значимых полей будет идти с 1.
Обычные звонки регистрируются в записях типа R200. Там уже 152 поля, причем это можно перенастроить на оборудовании: какие-то поля добавить, какие-то удалить, а у прочих, возможно, поменять формат.
Нас интересуют поля с индексами [7, 8, 9, 12, 14, 36, 112, 122], и в конечном результате хотелось бы отфильтровать всё ненужное, чтобы лишнего в СУБД не импортировать. Выбрав из сырых данных только нужное, получим строку:
Все остальные поля особо не нужны. Некоторые, как вы видите, вообще пустые, а смысл прочих — неизвестен. Разве что IP-адреса (изменены) принадлежат двум платам в инфраструктуре телефонной сети, между которыми пойдет RTP-трафик. Импортировав эти поля, можно было бы изучить нагрузку на платы. Возможно, в будущем пригодится.
Записи в трафике идут плотно, строка за строкой. Возможно, есть какие-то другие типы записей, но они нам не интересны. Для тарификации достаточно только записей типа R200. Однако, во время визуального исследования трафика выяснилось еще одно интересное обстоятельство. Иногда попадались звонки с одного номера, начавшиеся в одно и то же время, но длительность их была разная. Сначала, в условиях неполной информации я подумал, что это какой-то глюк, ведь не может же человек звонить параллельно с одного и того же номера. Потом стала просматриваться закономерность, и, наконец, я понял, в чем дело. Вот пример таких записей на один номер телефона, все лишние поля я для наглядности выбросил:
Вам-то сейчас видно, в чем соль, а тогда мне эти записи среди тысяч им подобных, среди кучи лишних полей, букв и цифр, найти было нелегко. В общем, это было или везение, или интуиция, или волшебство. :) А разгадка проста: оборудование каждые полчаса (1800 секунд) отмечает «веху разговора» на случай, если что-то произойдет. Даже если последние 29 минут разговора были почему-то утеряны, весь предыдущий трехчасовой дискурс был многажды зафиксирован — для пущей надежности. В последней записи будут актуальные данные. Возможно, на оборудовании длительность вех можно как-то изменить, а пока их ряд выглядит так: [1800, 3600, 5400, 7200, 9000, over 9000..] Здесь еще примечательно то, что запись-веха отличается в нескольких «неважных» полях от записи-результата. Возможно, стоит учесть это в будущем, чтобы более качественно отфильтровывать ненужное, а пока я принял решение все записи с длительностью из этого ряда просто выбрасывать. Теоретически, здесь какой-то малый процент нормальных звонков будет утерян, но для этого нужно, чтобы человек разговаривал полчаса в точности до секунды. Вероятность этого очень-очень маленькая, а объемы у нас не такие значительные, чтобы закон больших чисел как-то повлиял на выборку. Мы назвали это явление творчески: «Проблема 1800 секунд».
Всего я создал четыре программы, которые сливали нужные файлы и отфильтровывали полезную информацию. Первоначально это были parser и merger — две программы, написанные по отдельности и соединенные в третью, тоже названную merger. Все они работали крайне медленно и потребляли много памяти, хотя с задачами справлялись. Данные одного месяца (3000 файлов по 240 строк = 720000 строк) они могли обрабатывать, минимум, 10 минут с отжиранием 500 мб памяти (а то и больше, ведь работал своп). Очень, очень страшный результат. И хотя задачу надо было выполнять 1 раз в месяц, мой напарник презрительно морщил нос на Haskell. Правда, Haskell тут ну совершенно ни при чем; это я допустил в программах ряд типичных ошибок начинающего функциональщика, из-за чего кривые алгоритмы работали из рук вон плохо. Но работали! Даже больше: программы (а самая большая из них занимает всего лишь 150 полезных строк) можно было настроить из командной строки. Вот какие функции были доступны:
1. Работа в режиме без параметров. Поля берутся по умолчанию, берутся файлы прошлого месяца.
2. Работа в режиме с параметрами:
— Fields [<список индексов полей>] — какие поля взять (parser Fields [1, 24, 55]);
— (yyyy, mm) — какой месяц обрабатывать (merger (2011, 5));
-W — не закрывать консольное окно после отработки (от слова «wait»).
3. Получались три файла:
— yyyy.mm.txt — в него сливались все файлы с сырым трафиком за этот месяц;
— processed.txt — файл только с нужными полями за этот месяц;
— yyyy.mm.txt.log — файл-лог, где перечисляются задействованные сырые файлы и пишется сводная информация (количество строк, файлов, диапазон дат).
4. Программы выводят на экран статистику и примеры обработанного трафика.
Пару-тройку раз мы пользовались, чем было, но потом я, конечно, переписал программу с нуля. Уж очень в старом коде было много кривого кода, ненужных велосипедов, глупых алгоритмов и странных решений. В итоге четвертая программа, NgnParser, при той же функциональности и на том же наборе данных работает не 10 минут, а 10 секунд, потребляя всего лишь 10 мб памяти. По скорости разница составляет почти два порядка и, как минимум, один — по памяти! Что можно было такого намутить, чтобы так замедлить программу? Полагаю, есть люди, наступившие на те же грабли, что и я, которые поверили скорее в тормознутость языка, чем в свои кривые руки, — недаром в Интернете так много воплей по поводу и без повода… Haskell — замечательный язык. Мне было легко писать эти программы. На каждую я тратил не более двух рабочих дней. И всякий раз получал море удовольствия. Не представляю, сколько было бы мучений, если бы то же самое я делал на C.
Первую программу я начал с простого. Покамест я сливал нужные файлы в один (merged.txt) средствами командной строки, а задача parser'а была в парсинге трафика и отфильтровывании нужных записей с идентификатором R200. Для обработки большого количества текста целесообразнее использовать специальный тип строки ByteString. Но работать с ним не так удобно, как с обычным типом String. Если ByteString — это оптимизированная реализация строки как таковой, то String — это список символов, то есть, [Char]. String, благодаря своей природе, очень удобен, но на больших данных производительность любых списков резко падает. В первых версиях программы именно String и несколько глупых решений стали причиной сильных тормозов и большого пожирания памяти. Однако, меня тогда волновала скорость разработки, а не производительность. Прототип программы я написал очень быстро. Вот как он выглядит (ревизия 2):
Сразу можно заметить странную функцию replaceChars с типом Char -> Char -> Char -> Char. Идея была такая: берем строку-запись, заменяем вертикальную черту '|' на пробел и используем функцию words для разбиения строки на слова:
В результате выполнения sInWords получится следующее преобразование:
К сожалению, поле с датой-временем тоже разобьется на два отдельных поля. Позже, чтобы этого избежать, я еще больше усложнил конструкцию, изначально подменив пробел в этом поле звездочкой и потом его вернув. В итоге строка-запись проходила еще больше преобразований:
Замена ' ' -> '*';
Замена '|' -> ' ';
Разбиение на слова функцией words;
Обработка списка полей, получение полей с нужным индексом;
Слияние полей функцией unwords;
Замена ' ' -> '|'
Замена '*' -> ' '
Кроме того, после этих жутких преобразований количество полученных полей не совпадало с количеством исходных, — ведь пустые поля в итоге вообще исчезали (см. пример преобразования выше). Хорошо, что во всех записях пустые/заполненные поля были на одних и тех же местах, а не то б я получил неприятные артефакты. Код, как вы видите, не только избыточный, но и некрасивый. Я даже не берусь оценить его асимптотическую сложность; думаю, она далеко превысила O(n^2). Более того, ближе к ревизии 12 я понял, что надо что-то делать с полями, которые теряются из-за двойных вертикальных черт. И добавил еще одно преобразование:
Тем самым добавил еще один полный проход по каждой строке! Вот уж во истину — мартышкин труд. А ведь нужно было-то совсем немного: вместо всего этого использовать функцию split из модуля Data.String.Utils, или написать свой вариант. Тогда всего лишь за один проход по строке-записи я бы получил правильное разбиение на поля:
Что сказать…facepalm Слов нет, одни эмоции.
Опытные хаскеллисты уже заметили, что в коде не используется бесточечный стиль (я его еще не прочувствовал на тот момент), и case-конструкций, сопоставления с образцом или там каких-нибудь охранных выражений почти нет. В итоге даже такой простой код читать местами тяжело. Вот как лучше было бы записать несколько функций:
Функцию intercalate "\r\n" вообще нужно было заменить на unlines. Было бы и короче, и понятнее, да и в тестах unlines показал большую производительность — не менее 30%:
Но будучи еще неопытным, я плохо знал стандартные функции даже из модуля Prelude, из-за чего городил ненужные велосипеды. Хотя, я даже сейчас не очень понимаю, как можно минимальными усилиями выбрать элементы с нужными индексами из списка элементов. Сравним код из старой и новой программы:
В первом случае мы итерируем список индексов и вытаскиваем элемент с помощью небезопасной функции !!. Во втором случае используем аккумулятор одновременно с итерацией по списку полей, и если аккумулятор нашелся в списке индексов, берем текущее поле с индексом аккумулятора в коллекцию. И там, и там — хвостовая рекурсия. Хотя, по тестам, новый код оказался на 40% медленнее. Возможно, в данном случае стоит вернуть старый код, — еще больше ускорить новую программу.
Следующая программа — merger — должна была соединять все текстовые файлы за прошлый месяц в один. (Не хотелось каждый раз делать это вручную, а лень, как известно, движитель прогресса.) Возник вопрос: откуда узнать, какой у нас будет прошлый месяц? Да, в общем-то, это просто: берем текущую дату и отнимаем один месяц. Программа должна была использоваться исключительно в первых числах месяца, так что тут проблем не предвиделось. Текущая дата и вообще операции с датой-временем находятся в модуле Time. Операции со структурой файловой системы лежат в модуле System.Directory. И те, и другие функции, в основном, работают в монаде IO, а в то время я еще толком не умел причесывать монадный код, в итоге он выглядит жутко (merger, ревизия 14):
Что этот код делает — даже не рекомендую вникать… Но именно здесь закрался росток будущей огромной ошибки, из-за которой последняя версия старой программы пожирала огромное количество памяти. Рассмотрим функцию merge, которая вызывается из этого кода:
Она принимает список файлов, которые надо смержить, читает их и возвращает список их содержимого. В коде есть такие две строчки:
Ключевой момент — unlines fsContents. То есть, все сырое содержимое всех файлов соединялось в один присест и запихивалось в файл-результат. В последствии, когда parser и merger были объединены, именно этот огромный объем данных передавался в обработку parser-части, где, вы помните, есть целая куча замен, проходов и прочего оверхеда. Вот как выглядит эта часть кода в старой программе, собранной из parser и merger:
И это не простоfacepalm плохо, это грубейшее нарушение dataflow-концепции. Должно быть так:
А получилось так:
Разницу между последовательной обработкой частей и обработкой всего сразу я прочувствовал в полной мере. Теперь я знаю: не стоит брать весь объем работ сразу, лучше создать механизм, который выдает данные порциями, — так будет и по памяти эффективно, и по скорости лучше. И, кроме всего прочего, программу, сделанную по второй схеме, нельзя распараллелить. Ужас, одним словом…
Позже я пытался соптимизировать старую программу, — заменял почти везде String на ByteString. Выигрыш, конечно, был небольшой, но — веером тумана не разгонишь.
Надо ли говорить, что новую программу, NgnTraffic, я делал, имея уже нормальный запас знаний? В ней соблюдено многое. Программа разбита на модули: Main, Constants, DataProcess, FileListProces, Options, Tools, Types. Используется, конечно, схема 1. Вместо String изначально взят тип ByteString (Strict-вариант). Код более причесан, даже бесточечный стиль в наличии. И, главное, поменялся принцип действия. Сначала собирается список файлов, которые нужно обработать, — эта часть похожа на аналогичную из старой программы. Затем, однако, файлы не читаются все сразу в одну большую переменную, а каждый читается по отдельности. Его содержимое тут же обрабатывается, строки парсятся, записи фильтруются, нужные поля вытаскиваются. Результат дописывается в результирующий файл. В итоге имеем цикл «Чтение с диска (F(An)) — Обработка строк (G(Bn)) — Запись результата на диск (H(Cn))» — и так много раз по числу файлов. Плюс, конечно, нет никаких замен одного символа на другой, а есть простая функция split из модуля Data.ByteString.Char8, которая за один проход разбивает строку-запись на поля и сама по себе выигрывает чудовищную долю производительности. Вот как выглядят функции, удовлетворяющие схеме 1:
Здесь process принимает имя файла-результата, список файлов на обработку и индексы нужных полей. Индексы могут прийти из командной строки, поэтому они выведены как аргумент этой функции. process берет по очереди имя каждого файла и применяет к нему функцию process' (в строке mapM_ (process' resFile fieldIndexes) fs). Она уже занимается главной работой с файлами. Функция processData берет на себя обработку содержимого файла. Интересно то, что помимо фильтрования R200-записей в новой программе создан механизм предикатов: можно любое любую запись проверить по доступному предикату, а сами предикаты нетрудно дополнить нужным. Пока сделано два: поле с индексом x принадлежит списку полей и не принадлежит ему. Так выглядит тип предикатов:
А это заданные предикаты-константы:
Нетрудно догадаться, что предикатам будут удовлетворять только те записи, у которых поле 1 равно «R200», и поле 36 не содержится в списке «Проблемы 1800 секунд». Отсеивание происходит в функциях checkPredicate и examineFields:
Сейчас я вижу, что функцию examineFields вполне можно было сделать через foldr, но это так, мелочи.
В целом, я доволен проделанной работой. Такое бывает редко, — но код NgnTraffic мне даже нравится. А особенно нравится тот прогресс, который стал виден на примере одной и той же программы, написанной в разное время и с разными знаниями. А «еще особеннее» нравится то, что это реальная программа на Haskell, использующаяся в реальном производстве.
Кто бы что ни говорил, — Haskell — потрясающий язык, лучший из тех, с которым мне приходилось работать.
Исходники parser по ревизиям: [2], [6], [12]
Исходники merger (в том числе и объединенная программа merger): [13], [14], [16], [23]
Исходники NgnTraffic
P.S. Перевод следующей части Yet Another Monad Tutorial тоже скоро будет.
P.P.S. Поправил ссылки на программы, спасибо товарищу steck.
P.P.P.S. Исправил пару ошибок, спасибо товарищам goder и jack128.
Описание данных
Я работаю в телекомах: фиксированная телефонная связь, интернет, IP-телефония. В задачи входит обработка трафика с АТС, с серверов IP-телефонии, поддержка текущего биллинга, написание софта и администрирование сетей, домена (да, «программист на все руки»). Недавно в моей организации было установлено новое оборудование, работающее совсем по другим принципам, и трафик, соответственно, тоже изменился. Теперь он поставляется в двух вариантах: со старых станций и с новых. Новый трафик дублируется в бинарном и текстовом форматах. Бинарники нам вообще не подходят (хотя кое-кто по незнанию говорил: «А чего там? Берешь их, и они сами в биллинг заскакивают!»), текстовый же занимает на порядок больше места, но именно с ним можно что-то сделать. Трафик со старого оборудования все еще идет, и его мы с напарником забрасываем с помощью отработанных схем, использующих сервисы местной СУБД. Можно было бы настроить эти же сервисы для трафика с новых станций, но обнаружилось несколько особенностей. Трафик на новых станциях пишется в отдельные файлы каждые 15 минут; всего таких файлов за месяц получается около 3000 (в идеале — 2976 за 31 день и 2880 за 30 дней). Каждый файл отдельно импортировать не будешь, ибо маразм. Слить в один их можно и даже нужно, благо они все текстовые, и записи о звонках расположены построчно. Ручное слияние выглядит так: выделяешь файлы только за прошлый месяц и добавляешь их в простейший скрипт слияния в командной строке. Формат имени файла фиксирован, следовательно, слияние можно автоматизировать, только придется парсить год и месяц. Линуксоиды бы использовали какой-нибудь Bash, Perl или Python, — дешево и сердито, но на Windows-машину их ради одной операции не поставишь, то же самое касается и PowerShell. А cmd — это извращение, о чем мы с вами хорошо знаем. ;) Наконец, в самом трафике тоже обнаружились сюрпризы, из-за которых даже после слияния и импорта с помощью средств СУБД требовалось много ручной SQL-работы. В общем, факторы как-то так удачно сложились в задачу для Haskell, который я в то время (апрель-май 2011) начал изучать.
Итак, ~ 3000 15-тиминутных файлов за месяц. На оборудовании можно изменить интервал и поставить не 15 минут, а любое другое значение: 5, 10, 30, 45… Количество файлов и их размеры, соответственно, изменятся. Пример имени файла (за 09.05.2011 09:30:00):
999992011050909300081.txt
99999 - идентификатор, вшитый в оборудование (по понятным причинам, я его заменил на девятки)
2011 - год
05 - месяц
09 - день
09 - часы
30 - минуты
00 - секунды
81 - какое-то случайное число, возможно, десятые доли секунд.Абонентов становится больше, и каждый файл уверенно растет в размере. Сейчас у нас в среднем 240 строчек на файл, но было сезонное летнее проседание, люди разъехались по отпускам и звонили меньше. За сентябрь ждем увеличения активности в полтора-два раза.
Записи о звонках разнообразны. Есть несколько разных типов записей, у которых разное количество полей. Записи типа R210 попадаются очень редко, и что они значат, мы не стали выяснять (здесь и далее данные трафика заменены случайными):
|R210|2011-06-24 21:43:53|2011-06-24 01:43:52|1|
Как нетрудно убедиться, здесь всего лишь 4 поля: идентификатор типа записи, дата начала, дата конца (формат ISO 8601/SQL) и, зачем-то, единичка. Поля разделяются вертикальной чертой, которая должна стоять и в начале записи, и в конце, так что реально полей на 1 больше, то есть, 5. Удобно считать, что поле с индексом 0 пустое, находится перед первой вертикальной чертой. Тогда отсчет значимых полей будет идти с 1.
Обычные звонки регистрируются в записях типа R200. Там уже 152 поля, причем это можно перенастроить на оборудовании: какие-то поля добавить, какие-то удалить, а у прочих, возможно, поменять формат.
|R200|99999|111111|CR,CS,AM|1|1|3022|222222|333333|||2011-06-23 11:33:58|C|2011-06-23 11:34:22|S|0|16|1||||||1|1||||||3|162|17|1|12|24|||||||||||16|0||||||192.168.1.172||192.168.1.12||||||8|8|20|20|64|64|20|0|0|OS|7777|8888|555555|666666|0|8|9||||OS|19|||30|10|42|43||||||||||||1||||||1|1|0|3||222222|||||||2|1||333333|||||||||||||||||||||||||||||||
Нас интересуют поля с индексами [7, 8, 9, 12, 14, 36, 112, 122], и в конечном результате хотелось бы отфильтровать всё ненужное, чтобы лишнего в СУБД не импортировать. Выбрав из сырых данных только нужное, получим строку:
Запись: 3022|222222|333333|2011-06-23 11:33:58|2011-06-23 11:34:22|24|222222|333333 Индексы: 7 |8 |9 |12 |14 |36|112 |122 Индексы | Объяснение --------------------------- 7 | код города Читы 8, 112 | исходящий номер 9, 122 | входящий номер 12 | дата и время начала разговора 14 | дата и время конца разговора 36 | длительность разговора в секундах
Все остальные поля особо не нужны. Некоторые, как вы видите, вообще пустые, а смысл прочих — неизвестен. Разве что IP-адреса (изменены) принадлежат двум платам в инфраструктуре телефонной сети, между которыми пойдет RTP-трафик. Импортировав эти поля, можно было бы изучить нагрузку на платы. Возможно, в будущем пригодится.
Записи в трафике идут плотно, строка за строкой. Возможно, есть какие-то другие типы записей, но они нам не интересны. Для тарификации достаточно только записей типа R200. Однако, во время визуального исследования трафика выяснилось еще одно интересное обстоятельство. Иногда попадались звонки с одного номера, начавшиеся в одно и то же время, но длительность их была разная. Сначала, в условиях неполной информации я подумал, что это какой-то глюк, ведь не может же человек звонить параллельно с одного и того же номера. Потом стала просматриваться закономерность, и, наконец, я понял, в чем дело. Вот пример таких записей на один номер телефона, все лишние поля я для наглядности выбросил:
|7 |8 |9 |12 |14 |36 | |3022|222222|333333|2011-05-23 13:07:54|2011-05-23 13:37:54|1800| |3022|222222|333333|2011-05-23 13:07:54|2011-05-23 13:59:40|3106| |3022|444444|555555|2011-05-23 14:53:52|2011-05-23 15:23:52|1800| |3022|444444|555555|2011-05-23 14:53:52|2011-05-23 15:53:52|3600| |3022|444444|555555|2011-05-23 14:53:52|2011-05-23 16:00:50|4018| |3022|666666|777777|2011-05-23 19:15:55|2011-05-23 19:45:54|1800| |3022|666666|777777|2011-05-23 19:15:55|2011-05-23 20:15:54|3600| |3022|666666|777777|2011-05-23 19:15:55|2011-05-23 20:45:54|5400| |3022|666666|777777|2011-05-23 19:15:55|2011-05-23 20:47:17|5483|
Вам-то сейчас видно, в чем соль, а тогда мне эти записи среди тысяч им подобных, среди кучи лишних полей, букв и цифр, найти было нелегко. В общем, это было или везение, или интуиция, или волшебство. :) А разгадка проста: оборудование каждые полчаса (1800 секунд) отмечает «веху разговора» на случай, если что-то произойдет. Даже если последние 29 минут разговора были почему-то утеряны, весь предыдущий трехчасовой дискурс был многажды зафиксирован — для пущей надежности. В последней записи будут актуальные данные. Возможно, на оборудовании длительность вех можно как-то изменить, а пока их ряд выглядит так: [1800, 3600, 5400, 7200, 9000, over 9000..] Здесь еще примечательно то, что запись-веха отличается в нескольких «неважных» полях от записи-результата. Возможно, стоит учесть это в будущем, чтобы более качественно отфильтровывать ненужное, а пока я принял решение все записи с длительностью из этого ряда просто выбрасывать. Теоретически, здесь какой-то малый процент нормальных звонков будет утерян, но для этого нужно, чтобы человек разговаривал полчаса в точности до секунды. Вероятность этого очень-очень маленькая, а объемы у нас не такие значительные, чтобы закон больших чисел как-то повлиял на выборку. Мы назвали это явление творчески: «Проблема 1800 секунд».
Кратко о программах
Всего я создал четыре программы, которые сливали нужные файлы и отфильтровывали полезную информацию. Первоначально это были parser и merger — две программы, написанные по отдельности и соединенные в третью, тоже названную merger. Все они работали крайне медленно и потребляли много памяти, хотя с задачами справлялись. Данные одного месяца (3000 файлов по 240 строк = 720000 строк) они могли обрабатывать, минимум, 10 минут с отжиранием 500 мб памяти (а то и больше, ведь работал своп). Очень, очень страшный результат. И хотя задачу надо было выполнять 1 раз в месяц, мой напарник презрительно морщил нос на Haskell. Правда, Haskell тут ну совершенно ни при чем; это я допустил в программах ряд типичных ошибок начинающего функциональщика, из-за чего кривые алгоритмы работали из рук вон плохо. Но работали! Даже больше: программы (а самая большая из них занимает всего лишь 150 полезных строк) можно было настроить из командной строки. Вот какие функции были доступны:
1. Работа в режиме без параметров. Поля берутся по умолчанию, берутся файлы прошлого месяца.
2. Работа в режиме с параметрами:
— Fields [<список индексов полей>] — какие поля взять (parser Fields [1, 24, 55]);
— (yyyy, mm) — какой месяц обрабатывать (merger (2011, 5));
-W — не закрывать консольное окно после отработки (от слова «wait»).
3. Получались три файла:
— yyyy.mm.txt — в него сливались все файлы с сырым трафиком за этот месяц;
— processed.txt — файл только с нужными полями за этот месяц;
— yyyy.mm.txt.log — файл-лог, где перечисляются задействованные сырые файлы и пишется сводная информация (количество строк, файлов, диапазон дат).
4. Программы выводят на экран статистику и примеры обработанного трафика.
Пару-тройку раз мы пользовались, чем было, но потом я, конечно, переписал программу с нуля. Уж очень в старом коде было много кривого кода, ненужных велосипедов, глупых алгоритмов и странных решений. В итоге четвертая программа, NgnParser, при той же функциональности и на том же наборе данных работает не 10 минут, а 10 секунд, потребляя всего лишь 10 мб памяти. По скорости разница составляет почти два порядка и, как минимум, один — по памяти! Что можно было такого намутить, чтобы так замедлить программу? Полагаю, есть люди, наступившие на те же грабли, что и я, которые поверили скорее в тормознутость языка, чем в свои кривые руки, — недаром в Интернете так много воплей по поводу и без повода… Haskell — замечательный язык. Мне было легко писать эти программы. На каждую я тратил не более двух рабочих дней. И всякий раз получал море удовольствия. Не представляю, сколько было бы мучений, если бы то же самое я делал на C.
Первая программа
Первую программу я начал с простого. Покамест я сливал нужные файлы в один (merged.txt) средствами командной строки, а задача parser'а была в парсинге трафика и отфильтровывании нужных записей с идентификатором R200. Для обработки большого количества текста целесообразнее использовать специальный тип строки ByteString. Но работать с ним не так удобно, как с обычным типом String. Если ByteString — это оптимизированная реализация строки как таковой, то String — это список символов, то есть, [Char]. String, благодаря своей природе, очень удобен, но на больших данных производительность любых списков резко падает. В первых версиях программы именно String и несколько глупых решений стали причиной сильных тормозов и большого пожирания памяти. Однако, меня тогда волновала скорость разработки, а не производительность. Прототип программы я написал очень быстро. Вот как он выглядит (ревизия 2):
replaceChars :: Char -> Char -> Char -> Char
replaceChars whatC withC c = if c == whatC then withC else c
interestFields :: [String] -> [Int] -> [String]
interestFields s takeWhat = undefined -- Заглушка
isR200 :: [String] -> Bool
isR200 s = (head s) == "R200"
processLine :: String -> String
processLine s = if isR200 sInWords then unwords (interestFields sInWords [1,2,3] ) else [] -- [1,2,3] - тестовые поля
where sInWords = words ( map (replaceChars '|' ' ') s )
processString :: String -> [String]
processString s = map processLine (lines $ s)
main :: IO ()
main = do
str <- readFile "merged.txt"
putStrLn (intercalate "\r\n" (processString $ str))
Сразу можно заметить странную функцию replaceChars с типом Char -> Char -> Char -> Char. Идея была такая: берем строку-запись, заменяем вертикальную черту '|' на пробел и используем функцию words для разбиения строки на слова:
sInWords = words ( map (replaceChars '|' ' ') s )
В результате выполнения sInWords получится следующее преобразование:
"|R200|99999|111111|CR,CS,AM|1|1|3022|222222|333333|||2011-06-23 11:33:58|" -->
" R200 99999 111111 CR,CS,AM 1 1 3022 222222 333333 2011-06-23 11:33:58 " -->
["R200", "99999", "111111", "CR,CS,AM", "1", "1", "3022", "222222", "333333", "2011-06-23", "11:33:58"]
К сожалению, поле с датой-временем тоже разобьется на два отдельных поля. Позже, чтобы этого избежать, я еще больше усложнил конструкцию, изначально подменив пробел в этом поле звездочкой и потом его вернув. В итоге строка-запись проходила еще больше преобразований:
Замена ' ' -> '*';
Замена '|' -> ' ';
Разбиение на слова функцией words;
Обработка списка полей, получение полей с нужным индексом;
Слияние полей функцией unwords;
Замена ' ' -> '|'
Замена '*' -> ' '
Кроме того, после этих жутких преобразований количество полученных полей не совпадало с количеством исходных, — ведь пустые поля в итоге вообще исчезали (см. пример преобразования выше). Хорошо, что во всех записях пустые/заполненные поля были на одних и тех же местах, а не то б я получил неприятные артефакты. Код, как вы видите, не только избыточный, но и некрасивый. Я даже не берусь оценить его асимптотическую сложность; думаю, она далеко превысила O(n^2). Более того, ближе к ревизии 12 я понял, что надо что-то делать с полями, которые теряются из-за двойных вертикальных черт. И добавил еще одно преобразование:
-- Чтобы пустые поля, обозначенные как "||", обрабатывались корректно, между ними вставляется пробел.
refieldDoubles :: String -> String
refieldDoubles [] = []
refieldDoubles ('|':[]) = "|"
refieldDoubles ('|':'|':ss) = "| |" ++ (refieldDoubles ('|':ss))
refieldDoubles (s:[]) = [s]
refieldDoubles (s:ss) = s : (refieldDoubles ss)
Тем самым добавил еще один полный проход по каждой строке! Вот уж во истину — мартышкин труд. А ведь нужно было-то совсем немного: вместо всего этого использовать функцию split из модуля Data.String.Utils, или написать свой вариант. Тогда всего лишь за один проход по строке-записи я бы получил правильное разбиение на поля:
split "|" "|R200|99999|111111|CR,CS,AM|1|1|3022|222222|333333|||2011-06-23 11:33:58|" ->
["","R200","99999","111111","CR,CS,AM","1","1","3022","222222","333333","","","2011-06-23 11:33:58",""]
Что сказать…
Какие возможны улучшения
Опытные хаскеллисты уже заметили, что в коде не используется бесточечный стиль (я его еще не прочувствовал на тот момент), и case-конструкций, сопоставления с образцом или там каких-нибудь охранных выражений почти нет. В итоге даже такой простой код читать местами тяжело. Вот как лучше было бы записать несколько функций:
replaceSymbols s = map (replaceChar '|' ' ') (map (replaceChar ' ' '*') s)
-- -->
replaceSymbols = map (replaceChar '|' ' ' . replaceChar ' ' '*')
isR200 s = (head s) == "R200"
-- -->
isR200 ("R200":_) = True
isR200 _ = False
replaceChars whatC withC c = if c == whatC then withC else c
-- -->
replaceChars whatC withC c | c == whatC = withC
| otherwise = c
processLine s = if isR200 sInWords then unwords (interestFields sInWords [1,2,3] ) else []
where sInWords = words ( map (replaceChars '|' ' ') s )
-- -->
processLine s | isR200 sInWords = unwords (interestFields sInWords [1,2,3] )
| otherwise = []
where sInWords = words . map (replaceChars '|' ' ') $ s
processString s = map processLine (lines $ s)
-- -->
processString = map processLine . lines
Функцию intercalate "\r\n" вообще нужно было заменить на unlines. Было бы и короче, и понятнее, да и в тестах unlines показал большую производительность — не менее 30%:
ItemsCnt testUnlines(ns) testIntercalate(ns) Percent 10 23.84 34.05 29.9 100 22.70 34.62 34.4 1000 23.28 35.48 34.3 10000 22.17 35.48 37.5 50000 22.13 33.26 33.4 100000 21.06 35.47 40.6 200000 22.70 34.05 33.3
Но будучи еще неопытным, я плохо знал стандартные функции даже из модуля Prelude, из-за чего городил ненужные велосипеды. Хотя, я даже сейчас не очень понимаю, как можно минимальными усилиями выбрать элементы с нужными индексами из списка элементов. Сравним код из старой и новой программы:
-- Старый код:
-- Аргумент 1 - список сырых поелй
-- Аргумент 2 - список нужных индексов
takeInterest :: [String] -> [Int] -> [String]
takeInterest _ [] = []
takeInterest ss (n:ns) = [ss !! n] ++ takeInterest ss ns
-- Новый код:
-- Аргумент 1 - аккумулятор
-- Аргумент 2 - список нужных индексов
-- Аргумент 3 - список сырых полей
collectFields :: Int -> [Int] -> [String] -> [String]
collectFields _ _ [] = []
collectFields idx fis (s:ss) | idx `elem` fis = s : collectFields (idx+1) fis ss
collectFields idx fis (s:ss) | otherwise = collectFields (idx+1) fis ss
В первом случае мы итерируем список индексов и вытаскиваем элемент с помощью небезопасной функции !!. Во втором случае используем аккумулятор одновременно с итерацией по списку полей, и если аккумулятор нашелся в списке индексов, берем текущее поле с индексом аккумулятора в коллекцию. И там, и там — хвостовая рекурсия. Хотя, по тестам, новый код оказался на 40% медленнее. Возможно, в данном случае стоит вернуть старый код, — еще больше ускорить новую программу.
ItemsCnt takeInterest(ns) collectFields(ns) Percent 10 17.33 36.84 52.9 100 20.58 36.84 44.1 1000 21.67 37.92 42.8 10000 21.13 36.84 42.6 50000 21.67 37.92 42.8
Идем дальше
Следующая программа — merger — должна была соединять все текстовые файлы за прошлый месяц в один. (Не хотелось каждый раз делать это вручную, а лень, как известно, движитель прогресса.) Возник вопрос: откуда узнать, какой у нас будет прошлый месяц? Да, в общем-то, это просто: берем текущую дату и отнимаем один месяц. Программа должна была использоваться исключительно в первых числах месяца, так что тут проблем не предвиделось. Текущая дата и вообще операции с датой-временем находятся в модуле Time. Операции со структурой файловой системы лежат в модуле System.Directory. И те, и другие функции, в основном, работают в монаде IO, а в то время я еще толком не умел причесывать монадный код, в итоге он выглядит жутко (merger, ревизия 14):
main :: IO ()
main = do
args <- getArgs
curDir <- getCurrentDirectory
dirContents <- getDirectoryContents curDir
curTime <- T.getClockTime
monthAgoTime <- return $ T.addToClockTime (T.TimeDiff 0 (-1) 0 0 0 0 0) curTime
calendarMonthAgoTime <- T.toCalendarTime monthAgoTime
let maybeDateRange = case args of
(a:b:_) -> readDateRange (unwords [a, b])
_ -> Just $ defaultDateRange calendarMonthAgoTime
case maybeDateRange of
Just dr -> do
let fsToMerge = filesToMerge dirContents dr
let fsToMergeCountStr = show $ length fsToMerge
let mergeLog = (newFileName dr ++ ".log")
let dateRangeMsg = "DateRange: " ++ show dr
fsContents <- merge fsToMerge
writeFile (newFileName dr) (unlines fsContents)
writeFile mergeLog (unlines fsToMerge ++ printf "\n%s\nTotal files: %s" dateRangeMsg fsToMergeCountStr)
putStrLn (unlines fsContents)
putStrLn dateRangeMsg
--putStrLn ("Files to merge: " ++ unlines fsToMerge)
putStrLn (printf "Count of files: %s. See %s for file list." fsToMergeCountStr mergeLog)
Nothing -> putStrLn ("Invalid date range.")
Что этот код делает — даже не рекомендую вникать… Но именно здесь закрался росток будущей огромной ошибки, из-за которой последняя версия старой программы пожирала огромное количество памяти. Рассмотрим функцию merge, которая вызывается из этого кода:
merge :: [String] -> IO [String]
merge fsToMerge = mapM readFile fsToMerge
Она принимает список файлов, которые надо смержить, читает их и возвращает список их содержимого. В коде есть такие две строчки:
do
...
fsContents <- merge fsToMerge
writeFile (newFileName dr) (unlines fsContents)
...
Ключевой момент — unlines fsContents. То есть, все сырое содержимое всех файлов соединялось в один присест и запихивалось в файл-результат. В последствии, когда parser и merger были объединены, именно этот огромный объем данных передавался в обработку parser-части, где, вы помните, есть целая куча замен, проходов и прочего оверхеда. Вот как выглядит эта часть кода в старой программе, собранной из parser и merger:
do
...
fsContents <- readFilesToMerge fsToMerge
let mergedContents = unlines fsContents
writeFile (newFileName dr) mergedContents
let processedContentStr = unlines $ processData nedeedFields mergedContents
...
И это не просто
Схема 1
_____ _____ _____
| | | | | |
A1 -> |F(A1)| -> B1 -> |G(B1)| -> C1 -> |H(C1)| -> RESULT 1 -> SAVE
|_____| |_____| |_____|
_____ _____ _____
| | | | | |
A2 -> |F(A2)| -> B2 -> |G(B2)| -> C2 -> |H(C2)| -> RESULT 2 -> SAVE
|_____| |_____| |_____|
_____ _____ _____
| | | | | |
A3 -> |F(A3)| -> B3 -> |G(B3)| -> C3 -> |H(C3)| -> RESULT 3 -> SAVE
|_____| |_____| |_____|
...-> ... -> ... -> ... -> ... -> ... -> RESULT n -> SAVEА получилось так:
Схема 2
____________________ ____________________ ____________________
| | | | | |
| | | | | |
| | | | | |
A->| F(A) |->B->| G(B) |->С->| H(С) |->RESULT->SAVE
| | | | | |
| | | | | |
|____________________| |____________________| |____________________|Разницу между последовательной обработкой частей и обработкой всего сразу я прочувствовал в полной мере. Теперь я знаю: не стоит брать весь объем работ сразу, лучше создать механизм, который выдает данные порциями, — так будет и по памяти эффективно, и по скорости лучше. И, кроме всего прочего, программу, сделанную по второй схеме, нельзя распараллелить. Ужас, одним словом…
Позже я пытался соптимизировать старую программу, — заменял почти везде String на ByteString. Выигрыш, конечно, был небольшой, но — веером тумана не разгонишь.
Надо ли говорить, что новую программу, NgnTraffic, я делал, имея уже нормальный запас знаний? В ней соблюдено многое. Программа разбита на модули: Main, Constants, DataProcess, FileListProces, Options, Tools, Types. Используется, конечно, схема 1. Вместо String изначально взят тип ByteString (Strict-вариант). Код более причесан, даже бесточечный стиль в наличии. И, главное, поменялся принцип действия. Сначала собирается список файлов, которые нужно обработать, — эта часть похожа на аналогичную из старой программы. Затем, однако, файлы не читаются все сразу в одну большую переменную, а каждый читается по отдельности. Его содержимое тут же обрабатывается, строки парсятся, записи фильтруются, нужные поля вытаскиваются. Результат дописывается в результирующий файл. В итоге имеем цикл «Чтение с диска (F(An)) — Обработка строк (G(Bn)) — Запись результата на диск (H(Cn))» — и так много раз по числу файлов. Плюс, конечно, нет никаких замен одного символа на другой, а есть простая функция split из модуля Data.ByteString.Char8, которая за один проход разбивает строку-запись на поля и сама по себе выигрывает чудовищную долю производительности. Вот как выглядят функции, удовлетворяющие схеме 1:
process' :: ResFilePath -> FieldIndexes -> FilePath -> IO ()
process' resFile fis targetFile = do
fileContents <- C.readFile targetFile
let processResult = processData fis predicates fileContents
C.appendFile resFile processResult
process :: ResFilePath -> [FilePath] -> FieldIndexes -> IO String
process _ [] _ = return "No files to process."
process resFile fs fieldIndexes = do
C.writeFile resFile C.empty
mapM_ (process' resFile fieldIndexes) fs
return "All ok."
Здесь process принимает имя файла-результата, список файлов на обработку и индексы нужных полей. Индексы могут прийти из командной строки, поэтому они выведены как аргумент этой функции. process берет по очереди имя каждого файла и применяет к нему функцию process' (в строке mapM_ (process' resFile fieldIndexes) fs). Она уже занимается главной работой с файлами. Функция processData берет на себя обработку содержимого файла. Интересно то, что помимо фильтрования R200-записей в новой программе создан механизм предикатов: можно любое любую запись проверить по доступному предикату, а сами предикаты нетрудно дополнить нужным. Пока сделано два: поле с индексом x принадлежит списку полей и не принадлежит ему. Так выглядит тип предикатов:
data Predicate = NotInList [C.ByteString]
| InList [C.ByteString]
type PredicateMap = [(FieldIndex, Predicate)]
А это заданные предикаты-константы:
predicates :: PredicateMap
predicates = [(1, InList [C.pack "R200"]),
(36, NotInList (map C.pack ["1800", "3600", "5400", "7200", "9000", "10800", "12600", "14400", "16200", "18000", "19800", "21600", "23400"]) )]
Нетрудно догадаться, что предикатам будут удовлетворять только те записи, у которых поле 1 равно «R200», и поле 36 не содержится в списке «Проблемы 1800 секунд». Отсеивание происходит в функциях checkPredicate и examineFields:
checkPredicate :: Predicate -> C.ByteString -> Bool
checkPredicate (NotInList l) str = (not . elem str) l
checkPredicate (InList l) str = elem str l
examineFields :: Int -> PredicateMap -> Fields -> Bool
examineFields _ _ [] = True
examineFields idx preds (s:ss) = case L.lookup idx preds of
Just pred -> (checkPredicate pred s) && (examineFields (idx+1) preds ss)
Nothing -> examineFields (idx+1) preds ss
Сейчас я вижу, что функцию examineFields вполне можно было сделать через foldr, но это так, мелочи.
В целом, я доволен проделанной работой. Такое бывает редко, — но код NgnTraffic мне даже нравится. А особенно нравится тот прогресс, который стал виден на примере одной и той же программы, написанной в разное время и с разными знаниями. А «еще особеннее» нравится то, что это реальная программа на Haskell, использующаяся в реальном производстве.
Кто бы что ни говорил, — Haskell — потрясающий язык, лучший из тех, с которым мне приходилось работать.
Исходники parser по ревизиям: [2], [6], [12]
Исходники merger (в том числе и объединенная программа merger): [13], [14], [16], [23]
Исходники NgnTraffic
P.S. Перевод следующей части Yet Another Monad Tutorial тоже скоро будет.
P.P.S. Поправил ссылки на программы, спасибо товарищу steck.
P.P.P.S. Исправил пару ошибок, спасибо товарищам goder и jack128.
