LINUX.ORG.RU
решено Форум — Development  

Быстрый локальный key-value и XML SAX парсер

 


0

3

1. Требуется key-value хранилище. И ключи, и значения строки (ключи до 100 символов, значения могут быть несколько тысяч символов). Несколько миллионов пар. Двухколоночная SQLite таблица весит 2.5 ГБ.

Хранилище заполняется данными один раз при создании, затем работает в режиме только чтения (важна персистентность между запусками приложения и возможность не держать в памяти всю БД).

SQLite тратит 250 секунд на заполнение таблицы данными и чуть меньше 1 миллисекунды на запрос одного элемента.

Есть ли более быстрые варианты хранилища (в первую очередь в плане скорости заполнения данными)? Язык программирования Rust, желательно что-то имеющее обвязки под него.

2. Данные беруться из XML документа простого формата типа:

<items>
    <item>
        <key>Ключ</key>
        <value>Значение</value>
    </item>
    ...
</items>

Так вот, парсинг этого документа занимает 700 секунд (это если закомментировать вставку в таблицу, иначе будет 950 секунд).

Для парсинга используется xml-rs в режиме потокового парсера.

Можете ли посоветовать более быструю библиотеку парсинга? Как я понимаю, xml-rs парсит всякие штуки типа неймспейсов, которые мне не нужны (а вот стандартные xml entity типа < и > мне нужны - они встречаются в ключах и значениях).

★★★★★

Последнее исправление: KivApple (всего исправлений: 2)

  • key-value : libmdbx. Он несколько пошустрей и поустойчивей lmdb. Привязки для rust есть (ниже по тексту в репе)
  • xml: популярный для SAX pugixml, вроде, довольно шустрый. Какой-то wrapper для него на rust, я видел (хз, как работает, не использовал).
SkyMaverick ★★★★★
()
Ответ на: комментарий от alex0x08

4-5 Гб даже с SSD читаются достаточно долго. Приложение короткоживущее. Каждый запуск ему нужна очень небольшая часть данных (какие именно зависит от параметров запуска задаваемых юзером). Отказавшись от подготовки данных я получу десятки или даже сотни секунд время старта. Это неприемлемо.

KivApple ★★★★★
() автор топика
Ответ на: комментарий от KivApple

Так это десктоп получается?
Тогда точно нужна какая-то база и отдельно запускаемый процесс ее генерации из XML, но точно не на каждый запуск.

Кнопка «обновить индекс» в интерфейсе, что-то такое.

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

alex0x08 ★★★
()
Ответ на: комментарий от alex0x08

Да, в этом и идея. Построить один раз базу, а затем много раз использовать. Иногда обновлять по запросу. Мне не нравится, что обновление занимает 15 минут, причём большая часть времени проводится в XML парсере (700 секунд) и вставке в SQLite (250 секунд).

Голый I/O (прочитать кусками в память 5 ГБ исходного XML) занимает меньше 100 секунд.

В целом, возможно, SQLite и не узкое место. Раз чтение 5 Гб занимает 100 секунд, то запись 2.5 Гб вполне может занимать 250. Скорее всего упирается в I/O.

А вот XML парсер явно узкое место. Да, эти 700 секунд с учётом I/O, но если вычесть 100 секунд, всё равно остаётся 10 минут.

KivApple ★★★★★
() автор топика
Последнее исправление: KivApple (всего исправлений: 1)
Ответ на: комментарий от KivApple

В целом, возможно, SQLite и не узкое место. Раз чтение 5 Гб занимает 100 секунд, то запись 2.5 Гб вполне может занимать 250.

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

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

При таком объеме индексация в любом случае будет занимать существенное время. Даже на key-value.

alex0x08 ★★★
()
Ответ на: комментарий от alex0x08

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

Я думал о том, вдруг построить индексы когда уже есть все данные - быстрее, чем обновлять индекс по мере вставки.

Но с другой стороны алгоритимическая сложность хороших сортировок - O(NlogN), а алгоритмическая сложность вставки в BTree - O(logN). Соответственно, N вставок дадут в теории те же NlogN.

KivApple ★★★★★
() автор топика
Последнее исправление: KivApple (всего исправлений: 1)

Первое, что я бы сделал, это упростил структуру XML:

<item attribute="key">value</item>

или

<item>key|value</item>

и попробовать собственным парсером.

Как вариант, попробовать другие СУБД.

TechnoMag ★★
()
Последнее исправление: TechnoMag (всего исправлений: 1)
Ответ на: комментарий от TechnoMag

Не могу менять структуру XML, его создаю не я.

Более того, там есть лишние атрибуты и теги, но я их просто игнорирую. Единственное, что имена тегов уникальны на каждом уровне вложенности. И порядок одинаков.

KivApple ★★★★★
() автор топика
Последнее исправление: KivApple (всего исправлений: 1)
Ответ на: комментарий от KivApple

Практически все парсеры используют регулярные выражения, даже для XML и HTML. Другое дело, там регулярками просто выделяют лексемы, а не выполняют синтаксический анализ.

Скорее всего можно, но надо смотреть на реальное содержимое XML. Твой пример из ОП можно.

theNamelessOne ★★★★★
()
Последнее исправление: theNamelessOne (всего исправлений: 1)
Ответ на: комментарий от KivApple

иначе бы я мог просто записать все данные в какой-нибудь protobuf или даже CSV, чтобы убрать затраты на парсинг XML.

А, собственно, что мешает? CSV всяко парсить быстрее будет.

Я думал о том, вдруг построить индексы когда уже есть все данные - быстрее, чем обновлять индекс по мере вставки.

Не. Вставка обычно довольно быстро делается.

hateyoufeel ★★★★★
()
Последнее исправление: hateyoufeel (всего исправлений: 1)
Ответ на: комментарий от theNamelessOne

Практически все парсеры используют регулярные выражения, даже для XML и HTML. Другое дело, там регулярками просто выделяют лексемы, а не выполняют синтаксический анализ.

Эмм… що? Ну нет же ж ну.

hateyoufeel ★★★★★
()

Можете ли посоветовать более быструю библиотеку парсинга? Как я понимаю, xml-rs парсит всякие штуки типа неймспейсов, которые мне не нужны (а вот стандартные xml entity типа < и > мне нужны - они встречаются в ключах и значениях).

Enjoy your XML.

Чтобы быстро парсить это дерьмо, возьми ragel или руками простой конечный автомат напиши. Если не нужна валидация достаточно считать угловые скобки и помнить предыдущий символ чтобы отличить ke(y) от value(e). Останется только entity раскрыть.

slovazap ★★★★★
()
Development