Тестирование кода для чрезмерно больших входов

При написании юнит-тестов мы в основном ориентируемся на корректность бизнеса. Мы прилагаем все усилия, чтобы осуществить счастливый путь и все крайние случаи. Мы иногда микробенчмаркируем и измеряем пропускную способность. Но один аспект, который часто упускается, — это как ведет себя наш код, когда ввод слишком велик? Мы проверяем, как мы обрабатываем обычные входные файлы, искаженные файлы, пустые файлы, отсутствующие файлы … но как насчет безумно больших входных файлов?

Давайте начнем с реального варианта использования. Перед вами была поставлена ​​задача реализовать преобразование GPX ( формат обмена GPS , в основном XML) в JSON. Я выбрал GPX без особой причины, это просто еще один формат XML, с которым вы могли столкнуться, например, при записи похода или поездки на велосипеде с помощью GPS-приемника. Также я подумал, что будет неплохо использовать какой-то стандарт, а не еще одну «базу данных людей» в XML. Внутри файла GPX находятся сотни плоских <wpt/> записей, каждая из которых представляет одну точку в пространстве-времени:

Полный пример: www.topografix.com/fells_loop.gpx . Наша задача — извлечь каждый отдельный элемент <wpt/> , отбросить элементы без атрибутов lat или lon и сохранить обратно JSON в следующем формате:

Это легко! Прежде всего я начал с создания классов JAXB с использованием утилиты xjc из схемы JDK и GPX 1.0 XSD . Обратите внимание, что GPX 1.1 является самой последней версией на момент написания этой статьи, но примеры, которые я получил, используют 1.0. Для сортировки JSON я использовал Джексона . Полная, работающая и протестированная программа выглядит так:

Выглядит довольно хорошо, несмотря на несколько ловушек, которые я оставил намеренно. Мы загружаем XML-файл GPX, извлекаем путевые точки в List , преобразуем этот список в легкие объекты LatLong , сначала отфильтровывая сломанные путевые точки. Наконец мы сбрасываем List<LatLong> обратно на диск. Однако однажды чрезвычайно длинная поездка на велосипеде OutOfMemoryError нашу систему с OutOfMemoryError . Ты знаешь, что случилось? Файл GPX, загруженный в наше приложение, был огромен, намного больше, чем мы ожидали получить. Теперь снова посмотрите на реализацию выше и посчитайте, сколько мест мы выделяем больше памяти, чем необходимо?

Но если вы хотите немедленно провести рефакторинг, остановитесь прямо здесь! Мы хотим практиковать TDD, верно? И мы хотим ограничить коэффициент WTF / мин в нашем коде? У меня есть теория, что многие «WTF» не вызваны небрежными и неопытными программистами. Часто это из-за производственных проблем в конце пятницы, совершенно неожиданных исходных данных и непредсказуемых побочных эффектов. Код получает все больше и больше обходных путей, сложный для понимания рефакторинг, более сложную логику, чем можно было ожидать. Иногда плохой код не предназначался, но требовал обстоятельств, которые мы давно забыли. Поэтому, если однажды вы увидите null проверку, которая не может произойти, или рукописный код, который мог бы быть заменен библиотекой — подумайте о контексте. При этом давайте начнем с написания тестов, доказывающих необходимость наших будущих рефакторингов. Если однажды кто-то «исправит» наш код, предполагая, что «этот глупый программист» усложнил задачу без веской причины, автоматические тесты точно скажут, почему .

Наш тест просто попытается преобразовать безумно большие входные файлы. Но прежде чем мы начнем, мы должны немного реорганизовать исходную реализацию, чтобы она вписывала InputStream и OutputStream а не входной и выходной File s — нет никаких оснований ограничивать нашу реализацию только файловой системой:

Шаг 0a: Сделайте это тестируемым

Шаг 0b: Написание входного (стресс) теста

Входные данные будут генерироваться с нуля с использованием утилиты repeat(byte[] sample, int times) разработанной ранее . Мы в основном будем повторять один и тот же элемент <wpt/> миллионы раз, обернув его заголовком и нижним колонтитулом GPX, чтобы он был правильно сформирован. Обычно я хотел бы поместить образцы в src/test/resources , но я хотел, чтобы этот код был автономным. Обратите внимание, что мы не заботимся ни о реальном входе, ни о выходе. Это уже проверено. Если преобразование выполнено успешно (мы можем добавить некоторое время ожидания, если захотим), все в порядке. Если происходит сбой с каким-либо исключением, скорее всего OutOfMemoryError , это тестовый сбой (ошибка):

Здесь фактически 7 тестов, выполняющих преобразование GPX в JSON для входных данных размером: 1 КБ, 1 МБ, 10 МБ, 100 МБ, 1 ГБ, 8 ГБ и 32 ГБ. Я запускаю эти тесты на JDK 8u11x64 со следующими параметрами: -XX:+PrintGCDetails -XX:+PrintGCTimeStamps -Xmx1g . 1 ГиБ памяти много, но явно не может вместить весь входной файл в памяти:

В то время как небольшие тесты проходят, входы выше 1 ГиБ быстро терпят неудачу.

Шаг 1: Избегайте хранения целых файлов в String

Трассировка стека показывает, в чем проблема:

loadWaypoints охотно загружает input файл GPX в String (см .: IOUtils.toString(input, UTF_8) ), чтобы позже проанализировать его. Это довольно глупо, тем более что JAXB Unmarshaller может легко читать InputStream напрямую. Давайте исправим это:

Точно так же мы исправили dumpJson как он сначала dumpJson JSON в String а затем копировал эту String в OutputStream . Результаты немного лучше, но снова 1 GiB терпит неудачу, на этот раз, входя в бесконечный цикл смерти Full GC и, наконец, выбрасывая:

Шаг 2: (плохо) замена JAXB на StAX

Мы можем подозревать, что основной проблемой сейчас является синтаксический анализ XML с использованием JAXB, который всегда охотно отображает весь XML-файл в объекты Java. Легко представить, почему не удается преобразовать файл размером 1 ГБ в граф объектов. Мы хотели бы как-то взять больше контроля над чтением XML и его потреблением по частям. SAX традиционно использовался в таких обстоятельствах, однако модель push-программирования в SAX API очень неудобна. SAX использует механизм обратного вызова, который очень инвазивен и не очень удобочитаем. StAX (Streaming API for XML) , работающий на несколько более высоком уровне, предоставляет модель pull. Это означает, что клиентский код решает, когда и сколько потреблять входных данных. Это дает нам лучший контроль над вводом и обеспечивает большую гибкость. Чтобы познакомить вас с API, вот почти эквивалентный код loadWaypoints() , но я пропускаю атрибуты <wpt/> которые позже не нужны:

Посмотрите, как мы явно запрашиваем XMLStreamReader для получения дополнительных данных? Однако тот факт, что мы используем более низкоуровневый API (и намного больше кода), не означает, что он должен быть лучше, если используется неправильно. Мы продолжаем строить огромный список waypoints , поэтому неудивительно, что мы снова видим OutOfMemoryError :

Именно там, где мы ожидали. Хорошей новостью является то, что тест 1 ГиБ пройден (с кучей 1 ГиБ), поэтому мы как бы движемся в правильном направлении. Но это заняло 1 минуту, чтобы закончить из-за чрезмерного GC.

Шаг 3: StAX реализован правильно

Обратите внимание, что реализация с использованием StAX в предыдущем примере будет столь же хороша с SAX. Однако причина, по которой я выбрал StAX, заключалась в том, что теперь мы можем превратить файл XML в Iterator<Gpx.Wpt> . Этот итератор будет использовать XML-файл кусками, лениво и только по запросу. Позже мы также можем использовать этот итератор лениво, что означает, что мы больше не храним весь файл в памяти. Итераторы, хотя и неуклюжи для работы, все же намного лучше, чем работа с XML напрямую или с обратными вызовами SAX:

Это становится сложным! Я использую AbstractIterator из Guava для обработки утомительного состояния hasNext() . Каждый раз, когда кто-то пытается Gpx.Wpt следующий элемент Gpx.Wpt из итератора (или вызвать hasNext() ), мы потребляем немного XML, и этого достаточно, чтобы вернуть одну запись. Если XMLStreamReader встречает конец XML ( </gpx> ), мы сообщаем об окончании итератора, возвращая endOfData() . Это очень удобный шаблон, где XML читается лениво и подается через удобный итератор. Эта реализация сама по себе потребляет очень мало постоянного объема памяти. Однако мы изменили API с List<Gpx.Wpt> на Iterator<Gpx.Wpt> , что Iterator<Gpx.Wpt> изменения в остальной части нашей реализации:

toCoordinates() ранее принимал List<Gpx.Wpt> . Итераторы нельзя превратить в Stream напрямую, поэтому нам нужно это неуклюжее преобразование через Spliterator . Вы думаете, что все кончено? ! Тест GiB проходит немного быстрее, но более требовательные тесты не проходят, как и раньше:

Помните, что OutOfMemoryError не всегда выбрасывается из места, которое фактически потребляет большую часть памяти. К счастью, на этот раз это не так. Посмотрите внимательно на дно: collect(toList()) .

Шаг 4: Как избежать потоков и сборщиков

Это разочаровывает. Потоки и коллекторы были спроектированы с нуля, чтобы поддерживать лень. Однако практически невозможно реализовать сборщик (см. Также: Введение в написание пользовательских сборщиков в Java 8 и группирование, выборка и пакетирование — настраиваемые сборщики ) из эффективного потока в итератор, что является большим недостатком проекта. Поэтому мы должны полностью забыть о потоках и использовать простые итераторы до конца. Итераторы не очень изящны, но позволяют потреблять входной элемент за элементом, имея полный контроль над потреблением памяти. Нам нужен способ filter() входного итератора, отбрасывающего битые элементы и записи map() в другое представление. Guava, опять же, предоставляет несколько удобных утилит для этого, полностью заменив stream() :

Iterator<Gpx.Wpt> в, Iterator<LatLong> в. Обработка не производилась, файл XML почти не затрагивался, предельное потребление памяти. Нам повезло, Джексон принимает итераторы и прозрачно читает их, создавая JSON итеративно. Таким образом, потребление памяти также остается низким. Угадайте, что мы сделали это!

Потребление памяти низкое и стабильное, я думаю, мы можем с уверенностью предположить, что оно постоянно. Наш код обрабатывает около 40 МБ / с, поэтому не удивляйтесь, что почти 14 минут потребовалось для обработки 32 ГБ. О, и я упоминал, что я запускаю последний тест с -Xmx32M ? Правильно, обработка 32 ГиБ прошла успешно без потери производительности, используя в тысячи раз меньше памяти. И в 3000 раз меньше, по сравнению с первоначальной реализацией. По сути, последнее решение с использованием итераторов способно обрабатывать даже бесконечные потоки XML. Это не просто теоретический случай, представьте себе потоковый API, который создает бесконечный поток сообщений …

Окончательная реализация

Это наш код в целом:

Резюме (TL; DR)

Если вы недостаточно терпеливы, чтобы выполнить все шаги, вот три основных вывода:

1. Ваша первая цель — простота . Первоначальная реализация JAXB была идеальной (с небольшими изменениями), сохраните ее, если ваш код не должен обрабатывать большие входные данные.
2. Протестируйте свой код на безумно больших входных данных , например, используя сгенерированный InputStream , производя гигабайты ввода Огромный набор данных является еще одним примером крайнего случая. Не проверяйте вручную, один раз. Одно неосторожное изменение или «улучшение» может испортить вашу производительность в будущем.
3. Оптимизация не является оправданием для написания плохого кода . Обратите внимание, что наша реализация по-прежнему является составной и простой в использовании. Если бы мы прошли SAX и просто указали всю логику в обратных вызовах SAX, ремонтопригодность сильно пострадала бы.