Нужна библиотека приоритетной очереди на диске, желательно для C

Question

У меня есть механизм очередей в C на Unix. Он принимает транзакции XML. В некоторых транзакциях хранятся записи. Другие транзакции запрашивают эти транзакции. Транзакции сохраняются в файле, который является домашней очередью. Сначала во-первых, очень просто. Область заголовка в начале файла, отслеживает следующую позицию для чтения и следующую позицию для записи. Мы используем блокировку файлов, но не семафоров, поскольку поиск выполняется с удаленных систем. И есть только одна программа, которая обращается к очередям. Он находится в C. Должен работать отлично в течение многих лет.

Теперь мы должны расширить систему. Транзакции будут содержать дополнительный XML-тег. Мы должны выборочно извлекать данные на основе значений этого тега. Мы переходим от простой очереди к очереди приоритетов. В теге может быть много разных значений. Скажите AX, BX, CX, FL и TS. Транзакции добавляются в очередь в порядке поступления. Мы должны иметь возможность извлекать их либо для получения, либо получить следующую транзакцию, где тегом является FL. Или TS. Или (CS или FL). Или не AX.

Как лучше всего это сделать?

Простые и быстрые, что нам нужно. Несколько соображений:

1. Используйте что-то вроде Berkely DB, чтобы превратить очередь в базу данных.
2. Нажмите в базу данных PostgreSQL, создайте таблицу, которая может использоваться в качестве очереди приоритетов.
3. Найдите библиотеку C, которая будет делать то, что мы хотим.
4. Напишите нашу собственную очередь приоритетов на диске.

У нас есть некоторые ограничения. Время тикает, и это нужно сделать через несколько недель. C для быстрой установки в систему. Возможно, Python, если мы сможем достаточно быстро подключиться, чтобы преобразовать всю другую бизнес-логику в программу, которая обращается к очереди. Предпочитайте не использовать PostgreSQL, поскольку у нас нет контроля над системой базы данных, и у администратора базы данных есть неприятные привычки по сравнению с тем, что он считает «своим», и у нас нет надежной работы, даже если это критическая система. Политика, да! DBA также сказал, что использование таблицы PostgreSQL не является эффективным способом ее выполнения. Мы предпочитаем то, что локализовано, чтобы мы могли его контролировать. Должно быть молниеносно, чтобы обрабатывать много транзакций в минуту.

Я открыт для любых предложений, даже самых отдаленных. Чем больше предложений, тем лучше.

Answer 1

Похоже, все, что вам действительно нужно;

1. Способ перебора записей при проверке тега.
2. Способ записи записей как NULL, поэтому записи, выбранные вне порядка, пропускаются с помощью обычной обработки.

Я бы предположил, что самое быстрое изменение будет состоять в том, чтобы каждая запись содержала небольшой заголовок в файле, который включает эту информацию (длина записи, isValid, tag-info и т. Д.). Затем вы начинаете с первой записи в обычном режиме и повторяете все записи до тех пор, пока не столкнетесь с тегом, и если вы отметите эту запись недействительными, поэтому регулярная обработка будет игнорировать ее.

Долгосрочный вы можете рассмотреть что-то вроде sqllite, которое свободно доступно, работает с обычными файлами и может быть скомпилировано в ваш исполняемый файл.Для большинства типов поиска записей это, скорее всего, будет быстрее, чем что-то, что вы можете быстро катиться самостоятельно, и чертовски много более гибкое :)

Так что я бы пошел с быстрой заменой сейчас и подумал о переработке вашего формата данных в ближайшем будущем , будь то с sqllite или что-то еще. Похоже, требования к вашей очереди становятся все более сложными, и теперь настало время рассмотреть что-то, что может быть дополнительно расширено в будущем.

Answer 2

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