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

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

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

Ограничения такие:

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

Какие-либо предложения?

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

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

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

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

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


c++ multithreading data-structures lock-free b-tree
person Max Shifrin    schedule 19.11.2013    source источник
comment
Но действительно ли вам нужно писать весь файл карты? Не будет ли достаточно обновить только тот блок, который изменился?   -  person Some programmer dude    schedule 19.11.2013
comment
Я не понимаю, как вы можете сделать это без блокировки...   -  person Johan    schedule 19.11.2013
comment
Это невозможно так, как вы описываете, потому что API доступа к файлам ОС неявно имеет тип блокировки чтения-записи, т.е. вы в основном используете мьютексы ОС вместо своих собственных.   -  person DarkWanderer    schedule 19.11.2013
comment
Как говорит @DarkWanderer, ОС будет использовать блокировки для предотвращения одновременного доступа к диску. Вероятно, вам следует использовать файл отображения памяти и изучить реализации B-Tree без блокировки. cs.umanitoba.ca/~hacamero/Research/BtreeTechrpt2011.pdf интересно читать. Кроме того, из любопытства, почему вам запрещено использовать замки?   -  person Jim Mischel    schedule 19.11.2013
comment
У меня проблемы с пониманием слов «lock free» и «disk» в одном предложении.   -  person Martin James    schedule 19.11.2013
comment
Давайте предположим в качестве аргумента, что МОЯ ОС или, в частности, файловая система позволяют мне выполнять одновременные операции чтения/записи. Это означает, что они не используют никаких блокировок, а являются атомарными только на уровне блока размером 32/64 КБ (поэтому я упомянул об этом)   -  person Max Shifrin    schedule 20.11.2013

Ответы (2)


arrow_upward
4
arrow_downward

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

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

Хотя MVCC требует гораздо больше усилий, чем структура без блокировки ЦП/ОЗУ, если она у вас есть, многие из тех же самых оптимистичных шаблонов без блокировки применяются к ее использованию.

person Cory Nelson    schedule 19.11.2013
comment
Как упоминалось выше, предположим, что в моей файловой системе они атомарны, ради дизайна. MVVC выглядит многообещающе, мне придется больше изучить его и посмотреть, как я могу адаптировать эту концепцию к моему дисковому хранилищу, а не к хранилищу в памяти. - person Max Shifrin; 20.11.2013
comment
Ну, на самом деле MVCC не решает мою проблему, так как моя структура данных должна быть сортируемой, поэтому позволяет выполнять следующие/предыдущие операции с данными. MVCC решает проблему для хешируемой таблицы, но не обеспечивает сортировку. - person Max Shifrin; 20.11.2013
comment
MVCC не имеет ничего общего с вашей структурой данных, кроме обеспечения работы без блокировки. Он обычно используется с B+деревьями в базах данных, но на самом деле может использоваться для чего угодно. - person Cory Nelson; 20.11.2013
comment
Я понимаю это более или менее, но использование MVCC с тем, что я пытаюсь сделать, требует огромных накладных расходов, насколько я понимаю. (если вам нужно повторять процесс управления версиями объекта для каждого прыжка в дереве B+, что неэффективно) - person Max Shifrin; 21.11.2013
comment
Кроме того, я пытаюсь оптимизировать свою атомарность чтения/записи, если для моего конца записи 32/64 КБ являются атомарными, это означает, что я потенциально могу попытаться кэшировать большие части отображения дерева для повышения производительности. (например, при использовании деревьев b+ вместо b-дерева я могу кэшировать ссылки на несколько элементов за одно чтение для оптимизации производительности) - person Max Shifrin; 21.11.2013

arrow_upward
1
arrow_downward

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

person hyc    schedule 17.08.2014