Реализация структуры данных без блокировки на диске
У меня есть интересная задача для тех, кто имеет большой опыт работы со структурами данных без блокировок и структурами данных на основе дисков.
Я ищу способ построить в C ++ структуру данных для хранения различного количества объектов.
Ограничения таковы:
- Структура данных должна находиться на диске.
- Один поток записывает в структуру данных, а многие другие читают из нее.
- Каждое чтение атомарно. (Допустим, я могу атомарно прочитать блок размером 32/64 КБ для этого и что все объекты имеют меньший размер, чем тот.
- Запись не должна блокировать чтение, для этого можно предположить, что я могу написать атомарным способом также блок размером 32/64 КБ.
- Замки не могут быть использованы вообще.
Какие-либо предложения?
Я думал о том, чтобы использовать что-то вроде B-дерева, и когда необходимо разделить узлы и записать новые данные, а затем переместить их на новые узлы в конце файла, а затем просто обновить указатели на узлы, которые будут находиться, например, в некоторых других файл (исходные блоки будут помечены как свободные и добавлены в свободное хранилище)
Однако я сталкиваюсь с проблемой, если размер моего файла сопоставления превышает 32/64 КБ. Допустим, я хочу, чтобы он содержал хотя бы 1 миллион указателей на объекты, чем при 4 байтах / указатель. Я получаю 4 миллиона байтов, что составляет примерно 4 мегабайта. .. (и на 1 миллиард объектов даже больше, чем это ..) Это означает, что файл отображений не может быть записан атомарным способом.
Так что, если у кого-то есть лучшее предложение относительно того, как реализовать вышеизложенное, или даже какое-то направление, это будет с благодарностью.
Насколько мне известно, во всех реализациях B-Tree с открытым исходным кодом и в коммерческих целях используются блокировки, которые я не могу использовать.
Спасибо,
Максимум.
Решение
Вы не добьетесь большого успеха, просто предполагая, что операции чтения / записи являются атомарными — главным образом потому, что это не так, и вы в конечном итоге будете эмулировать это так, что это снизит производительность.
Похоже, вы хотите исследовать MVCC, который является довольно стандартным механизмом для использования при разработке базы данных без блокировки. Основная концепция заключается в том, что при каждом чтении создается «снимок» базы данных, который обычно реализуется без блокировки, оставляя старые страницы в покое и выполняя любые изменения только для новых страниц. Как только старые страницы будут использованы читателями, они, наконец, будут помечены для повторного использования.
Несмотря на то, что MVCC значительно более сложен, чем структура без блокировок ЦП / ОЗУ, при его использовании многие из тех же оптимистичных шаблонов без блокировок применимы к его использованию.
Другие решения
LMDB сделает все это без проблем. Это дерево MVCC B +, и считыватели полностью не блокируются.