Хорошая снимковая структура данных для индекса в памяти

Я проектирую базу данных объектов в памяти для очень конкретного случая использования. Это один писатель, но должен поддерживать эффективное одновременное чтение. Чтения должны быть изолированными. Нет языка запросов, база данных поддерживает только:

получить объект / -ы по атрибуту / набору атрибутов (например, может быть поддержка выражений x.count < 5)
получить атрибут объекта

Запрос - это императивный скрипт, составленный из произвольного числа вышеуказанных операций. Размер данных будет << памятью, поэтому все объекты и индексы по большинству атрибутов должны удобно размещаться без замены.

Что мне нужно, так это структура данных для индекса атрибута объекта, которая может быть O (n) при записи, не поддерживать параллелизм записи, но должна идеально поддерживать O (1) снимки (возможно, копирование при записи) и доступ O (logN). В идеале это позволило бы обеспечить высокий параллелизм при чтениях с максимальным структурным разделением между версиями.

Я смотрел на CTries , Concurrent BST и Conclayrent Splay Trees, но я не уверен, действительно ли я смотрю в правильном направлении здесь. Вышеуказанные структуры уделяют большое внимание сложности вставок, которые меня не интересуют.

Вопрос : есть ли известная структура данных, которая хорошо подходит для моего варианта использования из коробки?

РЕДАКТИРОВАТЬ : после некоторых размышлений кажется, что устойчивое дерево BST / Splay будет работать. Автор обновляет «главную» копию, а запросы получают дерево с начала выполнения и выбрасывают его после завершения. Однако мне все еще интересно, есть ли лучшее решение.

data-structures concurrency databases дм3
источник

Вам нужны снимки в памяти, или вам нужно сохранить их на диск / сеть? Чисто функциональная структура данных автоматически дает вам снимки в памяти, поэтому, если это то, что вам нужно, это ваш лучший выбор.

Жиль "ТАК - перестань быть злым"

Это все в памяти. Мне было интересно, может быть, есть эффективная изменяемая версия с постоянным моментальным снимком (например, CTrie, только без одновременных записей).

dm3

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

Рафаэль

Вполне возможно, не могли бы вы подробнее остановиться на этом?

dm3

Ответы:

Используйте любую постоянную / неизменную (т. Е. Функциональную) древовидную структуру данных. Ключ получает правильную блокировку, как отметил @Raphael в комментариях.

Приятной особенностью функциональных / постоянных древовидных структур данных является то, что вы получаете «снимки» бесплатно. Предположим, вы используете treap (рандомизированное двоичное дерево поиска) для своей структуры данных. Вот пример того, что написано на Go: https://github.com/steveyen/gtreap . Автор описывает это так:

По неизменяемости любые обновления / удаления в трепе возвращают новый трепп, который может использовать внутренние узлы с предыдущим треппом. Все узлы в этой реализации доступны только для чтения после их создания. Это позволяет одновременным читателям безопасно работать с параллельными записывающими устройствами, так как модификации только создают новые структуры данных и никогда не изменяют существующие структуры данных. Это простой подход к достижению MVCC или управления несколькими параллельными версиями.

$O(\log n)$

Вы используете блокировку для защиты указателя на корень. Поскольку структура данных является неизменяемой, чтение может выполняться одновременно, и вы можете сохранять указатели на старые снимки. Чтение это:

lock
tmp = ptr_to_root
unlock
value = search(tmp, <value to search for>)
return value

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

Запись это:

lock
old_ptr_to_root = ptr_to_root
ptr_to_root = insert(old_ptr_to_root, <new key/value pair>)
unlock

В этой версии записи должны удерживать блокировку в течение всего процесса создания новой версии дерева. Вы можете улучшить производительность чтения (за счет иногда неудачной транзакции записи), изменив запись на что-то вроде этого:

top:
  lock
  old_ptr_to_root = ptr_to_root
  unlock
  new_ptr_to_root = insert(old_ptr_to_root, <new key/value pair>)
  lock
  if (ptr_to_root == old_ptr_to_root)   # make sure no other write happened in the interim
    ptr_to_root = new_ptr_to_root
    unlock
  else                                  # transaction fails, try again
    unlock
    goto top

Возможно, вам удастся добиться даже немного лучшего (сделать его «свободным от блокировки»), если ваш язык программирования имеет атомарные переменные с атомарной операцией сравнения и замены. (Например, используя C ++ 11. atomic<T*>)

Блуждающая логика
источник

Спасибо за подробный ответ. Я вроде знал, что, может быть, я не достаточно четко выразил это в самом вопросе. Тем не менее, ответ по-прежнему велик!

дм3

Ваша «улучшенная» версия зависит от модели памяти используемой системы. Вполне может потребоваться, чтобы в некоторых системах были объявлены переменные, а для правильного кодирования необходимы большие навыки.

Ян Рингроз

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

Например:

Джастин Левандоски, Дэвид Ломет и Судипта Сенгупта, Bw-Tree: B-дерево для нового оборудования, 2013 IEEE 29-я Международная конференция по проектированию данных (ICDE), Международная конференция по проектированию данных, 8 апреля 2013 г.

См. Http://research.microsoft.com/en-us/projects/main-memory_dbs/ для списка их публикаций.

Ян Рингроз
источник