Быстрый построчный эквивалент "grep -n" для структуры каталогов Unix

Question

Я пытаюсь создать веб-интерфейс для поиска по большому количеству огромных файлов конфигурации (около 60000 файлов, каждый размером от 20 КБ до 50 МБ). Эти файлы также часто обновляются (~ 3 раза в день).

Требования:

• параллелизм
• Необходимо указать номера строк для каждой совпадающей строки
• Хорошая производительность обновления

Что я изучил:

• Lucene : Чтобы определить номер строки, каждая строка должна храниться в отдельном документе Lucene, каждое из которых содержит два поля (номер строки и строка). Это делает обновления трудными / медленными.
• SOLR и Sphinx : оба, основанные на Lucene, имеют одинаковую проблему и не позволяют идентифицировать номер строки.
• Таблица SQL с полнотекстовым индексом : Опять нет способа показать номер строки.
• Таблица SQL с каждой строкой в ​​отдельной строке : протестировано это с SQLite или MySQL, и производительность обновления была худшей из всех возможных Обновление документа объемом 50 МБ заняло более часа.
• eXist-db : Мы преобразовали каждый текстовый файл в XML следующим образом: <xml><line number="1">test</line>...</xml>. Обновление занимает ~ 5 минут, что несколько работает, но мы все еще не довольны этим.
• Свист для Python: Очень похоже на Lucene. Я реализовал прототип, который вроде работает, удалив / повторно импортировав все строки данного файла. При использовании этого метода обновление документа объемом 50 МБ занимает около 2-3 минут.
• GNU id utils : По предложению sarnold, это невероятно быстро (документ объемом 50 МБ обновляется менее чем за 10 секунд на моей тестовой машине) и будет идеальным, если он имеет нумерацию страниц и API.

Как бы вы внедрили альтернативу?

Answer 1

Возможно, вы захотите изучить инструментарий GNU idutils . На локальной копии исходных кодов ядра Linux он может выдать такой код:

$ gid ugly
include/linux/hil_mlc.h:66:  * a positive return value causes the "ugly" branch to be taken.
include/linux/hil_mlc.h:101:    int         ugly;   /* Node to jump to on timeout       */

Восстановление индекса из холодного кэша достаточно быстро:

$ time mkid

real    1m33.022s
user    0m17.360s
sys     0m2.730s

Восстановление индекса из теплого кэша происходит намного быстрее:

$ time mkid

real    0m15.692s
user    0m15.070s
sys     0m0.520s

Индекс занимает только 46 мегабайт для моих 2,1 гигабайта данных - что крошечно по сравнению с вашими, но соотношение хорошее.

Нахождение 399 вхождений foo заняло всего 0.039 секунд:

$ time gid foo > /dev/null

real    0m0.038s
user    0m0.030s
sys     0m0.000s

Обновление

Ларсману было интересно узнать производительность git grep на исходных кодах ядра - это отличный способ показать, какой прирост производительности обеспечивает gid(1).

В холодном кэше git grep foo (который вернул 1656 записей, гораздо больше, чем idutils):

$ time git grep foo > /dev/null

real    0m19.231s
user    0m1.480s
sys     0m0.680s

Как только кеш прогрелся, git grep foo работает намного быстрее:

$ time git grep foo > /dev/null

real    0m0.264s
user    0m1.320s
sys     0m0.330s

Поскольку мой набор данных полностью помещается в ОЗУ, когда кэш нагревается, git grep довольно удивительно: он всего в семь раз медленнее, чем утилита gid(1), и, безусловно, будет более чем достаточно быстр для интерактивного использования. Если рассматриваемый набор данных не может быть полностью кэширован (что, вероятно, именно там на самом деле все становится интересным), то выигрыш в производительности индекса очевиден.

Две жалобы на idutils:

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

2. Нет API: правда, API нет. Но источник доступен; src/lid.c функция report_grep() принимает связанный список файлов, которые соответствуют выводу. Немного возиться с этой функцией должно даже предложить нумерацию страниц. (Это займет некоторое время.) В конце концов, у вас будет C API, который все еще может быть не идеальным. Но его настройка не выглядит ужасно.

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

Answer 2

На тот случай, если кому-то это понадобится, я создал Whooshstore , который, по сути, представляет собой чистый клон Python с утилитами GNU id на основе Whoosh, который обеспечивает инкрементные обновления, нумерацию страниц и API Python.

Клиент командной строки работает так:

ws-update -b --index my.idx datadir  # build the index
ws-update -b --append --index my.idx datadir  # incremental update
ws --index my.idx hello world     # query the index

(-b для пакетного обновления, которое быстрее, но требует больше памяти. Для полного синтаксиса CLI используйте --help.)

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