Внедрение структуры данных без блокировки на диске

Question

У меня есть интересная задача для тех, у кого сильный фон в структурах без блокировки и на структурах данных на основе дисков.

Я ищу способ построить в C++ структуру данных для хранения различного количества объектов.

Ограничение таковы:

1. Структура данных должна находиться на диске.
2. Существует одна нить, записывающая структуру данных и многие другие, читающие ее.
3. Каждое чтение является атомарным. (давайте предположим, что я могу атомарно читать блок размером 32/64 КБ для этого и что все объекты невелики, чем размер.
4. Запись не должна блокировать чтение, поскольку можно предположить, что я могу писать в слитно блок 32/64KB, а также.
5. замки не могут быть использованы на всех.

Любые предложения?

Я думал об использовании нечто вроде B-Tree и, когда необходимо разделять узлы и записывать новые данные, чем переносить их на новые узлы в конце файла, а затем просто обновлять указатели на узлы, которые будут находиться, например, в некоторых других файлах le (исходные блоки будут отмечены как свободные и добавлены к freestore)

Однако у меня возникает проблема, если файл сопоставления больше 32/64Kb. Скажем, я хочу, чтобы он удерживал даже 1 миллион указатели объектов, чем на 4 байта/указатель. Я получаю до 4 миллионов байт, что составляет примерно 4 мегабайта ... (и на 1 миллиард объектов даже больше, чем это). Это означает, что файл сопоставлений не может быть написан атомным образом.

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

Насколько я знаю, все открытые/коммерческие реализации B-Tree используют блокировки, которые я не могу использовать.

Спасибо, Макс.

Answer 1

Вы не получите очень далеко, просто считая, что чтение/запись является атомарным - в основном потому, что это не так, и вы в конечном итоге эмулируете его таким образом, чтобы убить производительность.

Похоже, что вы хотите исследовать MVCC, что является довольно стандартным механизмом, который можно использовать при разработке базы данных без блокировки. Основная идея заключается в том, что каждый прочитанный получает «моментальный снимок» базы данных - обычно реализуется без блокировки, оставляя только старые страницы и выполняя любые изменения только на новых страницах. Когда старые страницы будут использоваться читателями, они, наконец, будут помечены для повторного использования.

В то время как MVCC значительно более активен, чем структура блокировки CPU/RAM, после того, как вы используете, многие из тех же оптимистичных шаблонов блокировки применимы к ее использованию.

Answer 2

LMDB будет делать все это без проблем. Это дерево MVCC B +, и читатели полностью заблокированы.