Быстрый и частый доступ к файлам при выполнении кода C ++

Question

Я ищу предложения о том, как наилучшим образом реализовать мой код для следующих требований.Во время выполнения моего кода на C ++ мне часто требуется доступ к данным, хранящимся в словаре, который сам хранится в текстовом файле.Словарь содержит 100 миллионов записей, и в любой момент мой код будет запрашивать данные, соответствующие некоторой конкретной записи среди этих 100 миллионов записей.Не существует конкретного шаблона, в котором бы выполнялись эти запросы, и, кроме того, в течение всего времени выполнения программы запрашиваются не все записи в словаре.Кроме того, словарь останется неизменным в течение всей жизни программы.Данные, соответствующие каждой записи, не имеют одинаковую длину.Размер файла моего словаря составляет ~ 24 ГБ, а у меня всего 16 ГБ оперативной памяти.Мне нужно, чтобы мое приложение было очень быстрым, поэтому я хотел бы знать, как лучше реализовать такую ​​систему, чтобы время доступа для чтения можно было минимизировать.

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

1. Если я сохраню смещение строки для каждой записи в моем словаре с начала файлаЗатем, чтобы прочитать данные для соответствующей записи, я могу сразу перейти к соответствующему смещению.Есть ли способ сделать это, используя, скажем, ifstream без циклического прохождения всех линий до линии смещения?Быстрый поиск в Интернете, кажется, показывает, что это невозможно по крайней мере с ifstream, есть ли другие способы, которыми это можно сделать?
2. Другая крайняя мысль заключалась в создании одного файла для каждой записи в словаре,поэтому у меня будет 100 миллионов файлов.Этот подход имеет очевидный недостаток при открытии и закрытии файлового потока.

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

Answer 1

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

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

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

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

Answer 2

Как только вы решите использовать структуру данных на диске, это станет не столько вопросом C ++, сколько вопросом разработки системы. Вы хотите реализовать дисковый словарь. С этого момента вы должны учитывать следующие факторы: каковы параметры вашего диска? это SSD? HDD? какова ваша средняя скорость поиска в секунду? У вас нормально с задержкой в ​​20 мсек - 10 мс для вашего метода Lookup()?

Для дисковых словарей требуется случайный поиск диска. Такие поиски имеют задержку в десятки микросекунд для SSD и 3-10 мс для HDD. Кроме того, существует ограничение на количество таких запросов, которые вы можете совершить за секунду. Вы можете прочитать эту статью например. Процессор перестает быть узким местом, и IO становится важным.

Если вы хотите следовать этому направлению - есть современные библиотеки C ++, которые предоставляют хранилище значений ключей на диске (нет необходимости во внешней базе данных) или вы можете сделать что-то еще просто.

Если ваше приложение представляет собой пакетный процесс, а не серверную / пользовательскую программу, т.е. у вас есть еще один конечный поток элементов, которые вы хотите объединить со своим словарем, тогда я рекомендую прочитать о внешних алгоритмах, таких как Hash Join или MapReduce. В этих случаях можно организовать ваши данные таким образом, чтобы вместо одного огромного словаря по 24 ГБ вы могли иметь 10 словарей размером 2,4 ГБ и последовательно загружать каждый из них и присоединяться. Но для этого мне нужно понять, какую проблему вы пытаетесь решить.

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