ijson

В Питоне для парсинга JSON обычно берут либо включённый в стандартную библиотеку simplejson, либо популярный в последнее время cjson. Обе библиотеки обрабатывают JSON одним куском: парсят всё целиком и возвращают нативный питоний объект. Мне же недавно понадобилось обрабатывать JSON потоком, в духе SAX. Это имеет смысл, когда размер данных начинает исчисляться мегабайтами, а обработка не требует хранения всего объекта в памяти целиком.

Оказывается, в мире эта задача решена библиотекой yajl (Саша, спасибо за наводку), и к ней есть два питоньих биндинга. Мне не понравились оба, поэтому я написал свой — ijson.

Название обыгрывает тот же принцип, что и функции из itertools: "imap", "ifilter" и т.д.

Существующие решения

py-yajl не понравился сразу, потому что он предоставляет интерфейс в виде функций "dumps" и "loads", а следовательно полностью скрывает всю потоковую природу yajl.

Следующий — yajl-py — оказался интересней. По использованию он похож на SAX-парсер: вы объявляете свой класс-обработчик, передаёте его в парсер, и он дёргает методы этого класса, обрабатывающие отдельные события из входного потока. Проблема этого подхода в том, что вызов парсера синхронный — он сам прокручивает цикл чтения входных данных, и этот процесс нельзя удобно остановить и продолжить. Мне же нужен был по сути питоний итератор, чтобы читать из него события самому. Такой итератор можно обернуть в собственный генератор-обработчик и вернуть его из приложения в WSGI-сервер.

ijson

Я подумал, что такой итератор сделать будет несложно, взял yajl-py и переделал его основную функцию с циклом парсинга на генератор. Потом посмотрел вокруг, немного порефакторил, потом ещё, и ещё, и в итоге теперь мой parse.py почти ничем не напоминает оригинальный yajl_parse.py :-). Тем не менее, я благодарен Хатему Нассрату — автору yajl-py — потому что если бы я не посмотрел в его код, я бы никогда не взялся делать обвязку к сишной библиотеке.

В итоге появился итератор basic_parse(file), который генерирует пары (event, value), соответствующие тому, что возвращает сишная библиотека (плюс приведение к удобным питоновым типам). Однако быстро стало ясно, что обрабатывать их неудобно, потому что события возвращаются вне контекста: вам пришло ('map_key', 'name'), но вы понятия не имеете, в каком объекте этот ключ. Поэтому я обернул базовый парсер в ещё один, сохраняющий контекст. Он генерирует уже не пары, а тройки, где первый параметр — путь, показывающий местоположение собтия в дереве объекта.

Вот для такого документа:

{
    "array": [1, 2],
    "map": {
        "key": "value"
    }
}

... парсер выдаст такую последовательность событий:

('',           'start_map',   None)
('',           'map_key',     'array')
('array',      'start_array', None)
('array.item', 'number',      1)
('array.item', 'number',      2)
('array',      'end_array',   None)
('',           'map_key',     'map')
('map',        'start_map',   None)
('map',        'map_key',     'key')
('map.key',    'string',      u'value')
('map',        'end_map',     None)
('',           'end_map',     None)

Префиксы пути (первый элемент) позволяют во многих случаях не писать сложной логики хранения состояния в пользовательском коде, а просто реагировать на события какого-то конкретного поддерева.

А буквально вчера я добавил ещё один итератор items(file, prefix), который отдаёт не голые события, а нативные питоновые объекты, расположенные по заданному префиксу:

from ijson import items

for item in items(file, 'docs.item.name'):
    do_something_with(item)

Это, конечно, самый удобный для обработки способ, но он должен быть помедленней из-за постоянно создающихся временных объектов.

Обработка корутинами

Классический способ обработки потокового парсинга — написать класс, состоящий из callback'ов, которые будут вызываться по соответствующим событиям. Всё полезное состояние при этом хранится в инстансе класса. Однако этот способ не отличается наглядностью. Кроме того, он совсем не работает, если вы хотите использовать при обработке конструкции с with, потому что в один оператор, очевидно, нельзя обернуть несколько разных вызовов callback'ов.

Моя текущая задача на работе — это генерация XML из JSON-данных. Я использую свою же elementflow, которая генерирует готовый XML, не требуя никакого промежуточного объектного представления. Соответственно, соединив событийный парсер ijson и событийный генератор elementflow, можно получить довольно быструю и очень экономную в памяти комбинацию. Проблема только в том, что elementflow как раз написана в расчёте на with.

Встречайте — корутины Дэвида Бизли (здесь фанфары)!

Базовая идея состоит в том, чтобы вместо класса с callback'ами использовать питоний генератор, в который через .send() можно передавать значения. Если вы не видели этих слайдов, то посмотрите прямо сейчас, там вся концепция объясняется очень хорошо, и я совсем не хочу излагать её своими словами.

Такие генераторы как раз позволяют использовать with, поскольку теперь все события парсера получает одна функция:

@coroutine
def converter(xml):
    while True:
        prefix, event, value == yield # get another event from parser

        if prefix == 'rows.item.id':
            # store the value in a local var
            id = value

        elif prefix == 'rows.item.value':
            # create another coroutine that knows how to process 
            # 'rows.item.value' contents
            target = value_coroutine(xml)

            # generate a containg XML element
            with xml.container('value', {'id': id}):

                # secondary loop cosuming 'rows.item.value'
                while (prefix, event) != ('rows.item.value', 'end_map'):
                    prefix, event, value == yield
                    # offload events into a target
                    target.send((prefix, event, value))

Поработав какое-то время с кодом в таком стиле, я заметил повторяющиеся паттерны, парочку из которых завернул в утилиты, которые теперь лежат в ijson.utils:

• foreach(coroutine_func). Умеет обрабатывать JSON-массив, создавая для каждого его элемента новый экземпляр coroutine_func, и скармливая ему содержимое элемента.

• dispatcher([(prefix, target), (prefix, target) ... ]). Принимает последовательность пар из префиксов и их обработчиков, и затем скармливает каждому обработчику только ту часть своего входного потока, который лежит под заданным префиксом.

В итоге весь код принимает вид дерева диспетчеров с листьями в виде генераторов конечных XML-элементов. Диспетчеры комбинируются каждый раз в соответствии со структурой входного JSON-дерева. Довольно непривычно, но вполне понятно на мой взгляд.

Последний момент — это организация одновременного парсинга и выдачи XML. Для этого пишется обычный генератор с очередью в памяти, который можно отдавать прямо в WSGI-сервер:

def generator(file):
    queue = elementflow.Queue()
    with elementflow.xml(queue, 'root') as xml:
        g = consumer_coroutine(xml)
        for event in ijson.parse(file):
            g.send(event)
            if len(queue) > BUF_SIZE:
                yield queue.pop()
    yield queue.pop()

Стоит ли оно того

Если по эффективности, то коротко — да. На реальной задаче выдача двухмегабайтного XML'а из примерно такого же JSON'а работает на 30% быстрее по сравнению с cjson даже под управлением форкающейся Django (то есть памяти тут не экономится). У меня под рукой пока нет жёстких данных, да и пост этот и так уже длинный, поэтому я хочу написать про тестирование отдельно.

Если говорить о размере и сложности кода, то тут всё очень субъективно. В любом случае надо понимать, что потоковый код обязательно будет немного больше и сложнее, чем "объектный".

Упражнение: ObjectBuilder

Хотите развлечься? :-)

Нужно написать код, создающий на основе событий от парсера нативный объект. Фактически — это то, что делают внутри так или иначе все непотоковые парсеры. В ijson такой есть — "ObjectBuilder" в модуле "parse" — но я предлагаю в его код пока не смотреть. Дело в том, что он у меня получился хоть и компактным, но довольно заумным. Было бы чудесно, если бы кто-нибудь написал решение проще, а в этом случае чужой код часто не даёт придумать что-то своё.