Введение
До подобного момента надо ещё дожить, но однажды случается и такое. В один прекрасный день мне понадобилась БД с 1 триллионом записей. Причём, понадобилась на домашнем компьютере, где свободного места 700 гигабайт на двух дисках.
По счастью, моя БД не совсем обычная: размер записи всего 1 бит. В базе должны храниться данные о простых числах. Соответственно, вместо того, чтобы хранить сами числа, проще хранить один бит (1 - простое число, 0 - композитное). И тогда, чтобы хранить один триллион битов, нужно всего 116 ГБайт.
Однако сделав такой файл, мы получили только лишь хранилище, но не собственно БД. Нам нужен код, который будет записывать и считывать данные. Традиционный FileStream был отброшен сразу, по причине его медленности. Постоянное чередование Seek и чтения/записи по 1 байту даёт результат примерно в 100 раз худший, чем отображаемых на память файлы, опытом использования которых я и хочу поделиться в этой статье.
Отображаемые на память файлы
Отображаемые на память файлы (ОПФ) работают за счёт аппарата виртуальной памяти. По принципу работы они аналогичны файлу подкачки Windows (pagefile.sys) с той разницей, что доступ к последнему есть только у самой ОС, а ОПФ доступен владельцу и может разделяться между процессами.
Отображаемые на память файлы реализованы: в WinAPI – функцией MapViewOfFile, а в .NET – классами MemoryMappedFile, MemoryMappedViewAccessor и MemoryMappedViewStream.
Работают эти классы так. MemoryMappedFile открывает СПФ, подключая его к адресному пространству приложения. Для этого у него есть методы CreateFromFile, CreateNew, CreateOrOpen, OpenExisting. Открытие СПФ не влечёт значимых расходов памяти, т.к. распределяется виртуальная, а не физическая память.
Чтобы получить доступ к содержимому файла, необходимо использовать один из двух классов, которые его предоставляют. Прямой доступ предоставляется классом MemoryMappedViewAccessor, а последовательный – классом MemoryMappedViewStream.
Для своего приложения я использовал прямой доступ, соответственно основная часть этой статьи посвящена особенностям MemoryMappedViewAccessor, главным образом, выбору между затратами памяти или времени.
Этот выбор стал для меня критическим, когда я занялся заполнением БД при помощи алгоритма, известного как решето Эратосфена. Это крайне простой алгоритм. Исходный код приводится для того, чтобы показать, в каком окружении работает ОПФ и в каком месте делается выбор между расходом памяти или времени.
public void FindPrimes(long start, long interval, ref bool quit)
{
long upper = (long)Math.Sqrt(Registry.Header.Length);
long l = 0;
Console.WriteLine($"Eratosthenes Primer: iterating {start} to {upper}...");
for (long i = start; i <= upper; i ++)
if (Registry.Contains(i)) // если i - простое число
for (long n = i * i; n <= Registry.Header.Length; n += i)
{
// все числа кратные i - не простые
Registry.SetState(n, false);
l ++;
if (0 != l % interval)
continue;
// выбор между расходом памяти и времени
Registry.Flush(); // расход времени
// Registry.Flush(); расход памяти
if(quit)
goto quit;
}
quit: ;
}Функция FindPrimes реализует решето Эратосфена. Она устанавливает, что числа, кратные простым, сами простыми не являются, и последовательно исключает их.
В данном фрагменте Registry – это собственно БД на основе MemoryMappedViewAccessor. Её методы: Contains() – проверяет, является ли число простым; SetState() – устанавливает признак простого (True) или композитного (False) числа.
Метод Flush() сбрасывает сделанные изменения на диск (MemoryMappedViewAccessor.Flush()), избавляется от аксессора (MemoryMappedViewAccessor.Dispose()) и создаёт вместо него новый. Использование или неиспользование этого метода и определяет, что будет расходоваться сильнее – память или время.
Параметр interval (в моём случае 100 млн.) подобран таким, чтобы периодический отчёт о прогрессе (в коде выше отсутствует) происходил примерно раз в 5 секунд. Будучи запущенной, программа показала следующее поведение.
Изначально вызоваRegistry.Flush()в программе не было. В диспетчере задач программа занимает не более 3 МБ, но общий расход памяти очень быстро доходит до 99%. При этом, время отклика компьютера значимо не растёт, новые приложения запускаются, из чего можно сделать вывод, что Windows отдаёт моему СПФ всю доступную память, но не в ущерб другим приложениям.
Насколько быстро работает ОПФ? 100 млн. вызовов Registry.SetState()занимает примерно 4,5 - 5 секунд, таким образом, первая итерация по i=3 занимает в общей сложности 4 часа. Мой СПФ расположен на HDD, видимо, на SSD затраты времени были бы меньше.
Можно заметить, что с ростом i вложенный цикл выполняется всё быстрее и быстрее, т.к. как шагаем всё более длинными шагами. При i=3он занимает 4 часа, для i=5 3 часа, для i=72 часа с хвостом и т.д. (в данный момент ещё работает). Медлительный вначале, к концу алгоритм Эратосфена разгоняется как ракета.
Дальнейшая работа над программой была направлена на снижение расхода памяти. Для этого в конце интервала был добавлен вызов Registry.Flush(). Этот вызов возымел нужное действие, расход памяти растёт во вложенном цикле, но при вызове Flush() падает до исходного уровня. Таким образом, задача казалась решённой.
Начиная с i=3, вызов Flush()добавлял около 700 мс к 4,5 - 5 секундам, что казалось приемлемой ценой за экономию памяти. Однако, это время начало быстро расти с ростом i: при i=5 850 мс, при i=7 1 сек и так далее. При i=823 время на Flush()было уже порядка 40 секунд! В результате, рост скорости алгоритма был полностью съеден увеличивающимися затратами времени на Flush().
Этот результат показывает, что при отработке Flush(), MemoryMappedViewAccessor пишет на диск весь диапазон между собственно изменёнными байтами. И, поскольку с ростом i, мы "шагаем всё шире", этот диапазон становится больше.
Данная особенность MemoryMappedViewAccessor заставила отказаться от сброса аксессора и экономии памяти. К сожалению, упомянутые в статье классы не имеют каких-либо опций настройки использования памяти.
Выводы
Как следует из документации MSDN, класс MemoryMappedFile предназначен специально для работы с очень большими объёмами данных: "Memory-mapped files enable programmers to work with extremely large files". При использовании MemoryMappedViewAccessor прямой доступ к данным через ОПФ работает значительно быстрее, чем FileStream.
В то же время, при использовании описанных классов нужно помнить, что скорость записи данных на диск при использовании MemoryMappedViewAccessor зависит не только от объёма изменённых данных, но и от расстояния между ними.
