Введение
До подобного момента надо ещё дожить, но однажды случается и такое. В один прекрасный день мне понадобилась БД с 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=7
2 часа с хвостом и т.д. (в данный момент ещё работает). Медлительный вначале, к концу алгоритм Эратосфена разгоняется как ракета.
Дальнейшая работа над программой была направлена на снижение расхода памяти. Для этого в конце интервала был добавлен вызов 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
зависит не только от объёма изменённых данных, но и от расстояния между ними.