Слияние кода завершено, страница обновится автоматически
Постоянный однопоточный движок, основанный на оптимизированном для чтения дереве B+. По умолчанию отключён. Его можно включить в CMake с помощью опции ENGINE_TREE3.
Конфигурация:
Конфигурация должна указывать путь к постоянному пулу PMDK, который может быть файлом (в файловой системе DAX), устройством DAX или файлом набора пулов PMDK.
Для более подробного описания конфигурации см. раздел cmap в libpmemkv(7).
Внутреннее устройство:
Tree3 использует гибридную реализацию дерева B+ с использованием отпечатков пальцев. Вместо того чтобы хранить внутренние и листовые узлы дерева в постоянной памяти, tree3 использует гибридную структуру, где внутренние узлы хранятся в DRAM, а листовые — только в постоянной памяти. Хотя tree3 должен восстанавливать все внутренние узлы при запуске движка, поиск выполняется в DRAM за исключением окончательного чтения из постоянной памяти.
Листовые узлы в tree3 содержат несколько пар ключ-значение, индексированных с использованием однобайтовых отпечатков пальцев (хешей Пирсона), которые ускоряют поиск заданного ключа. Модификации листа ускоряются с помощью обновлений с нулевым копированием.
Предварительные требования:
Никаких дополнительных пакетов не требуется.
Постоянный, параллельный и отсортированный движок, поддерживаемый списком пропусков. По умолчанию отключён. Может быть включён в CMake с помощью параметра ENGINE_CSMAP (требуется поддержка C++14).
Все методы csmap являются потокобезопасными. Put, get, count_* и get_* масштабируются в зависимости от количества потоков. Метод remove в настоящее время реализован так, что берёт глобальную блокировку — он блокирует все остальные потоки.
Конфигурация:
Более подробное описание конфигурации см. в разделе cmap в libpmemkv(7).
Предварительные требования:
Никаких дополнительных пакетов не требуется. Отключено по умолчанию. Можно включить в CMake с помощью параметра ENGINE_RADIX.
Для более подробного описания конфигурации см. раздел cmap в libpmemkv(7).
Дополнительные пакеты не требуются.
Постоянное, однопоточное и отсортированное ядро, поддерживаемое B+ деревом. Отключено по умолчанию. Может быть включено в CMake с использованием параметра ENGINE_STREE.
Для более подробного описания конфигурации см. раздел cmap в libpmemkv(7).
(TBD)
Дополнительные пакеты не требуются.
Постоянное и параллельное ядро, поддерживаемое хеш-таблицей с хешированием Робин Гуда (некоторое представление об алгоритме). Использует только ключи и значения фиксированного размера (8 байт). Отключено по умолчанию. Может быть включено в CMake с использованием параметра ENGINE_ROBINHOOD.
Есть два параметра, которые можно дополнительно изменить с помощью переменных среды:
Дополнительные пакеты не требуются.
Постоянный и параллельный движок, поддерживаемый списком пропуска, реализованным с использованием Persistent Compare and Swap (PCAS), предоставленным 4Paradigm Inc.. Структура данных списка пропуска впервые представлена в статье VLDB ("Оптимизация механизма базы данных в памяти для интеллектуального онлайн-дополнения решений с использованием постоянной памяти". Чен Чен, Цзюнь Ян, Мянь Лу, Тайцзе Ван, Чжао Чжэн, Юйцян Чен, Вэньюань Дай, Биншэн Хэ, Уэн-Фай Вонг, Гоань Ву, Юпинг Чжао, Энди Рудофф). Его можно включить в CMakeLists.txt с помощью опции ENGINE_PSKIPLIST.
(TBD)
Дополнительные пакеты не требуются.
pmse
tree3 имеет много общего с pmse — обе реализации внутренне полагаются на PMDK, хотя внешне они предоставляют разные API. И pmse, и tree3 основаны на реализации B+ дерева. Самое большое различие заключается в том, что дерево pmse хранит внутренние и листовые узлы в постоянной памяти, а tree3 хранит внутренние узлы в DRAM, а листовые — в постоянной памяти. (Это означает, что tree3 должен восстанавливать все внутренние узлы при запуске движка).
FPTree
В этой исследовательской статье описывается гибридная конструкция дерева DRAM/NVM (похожая на механизм хранения tree3), но в этой статье нет кода, и она опускает некоторые важные детали реализации.
Помимо предоставления чистой реализации, дизайн tree3 отличается от FPTree в нескольких важных областях:
tree3 написан с использованием привязок C++ PMDK, которые влияют на его дизайн и реализацию. tree3 использует общие транзакции PMDK (т. е. замыкания transaction::run()), нет необходимости в структурах микрологирования, как описано в статье FPTree, чтобы сделать внутренние операции удаления и разделения безопасными. tree3 также корректирует размеры структур данных (чтобы соответствовать примитивным типам PMDK) для оптимальной оптимизации кэш-строки.tree3 использует хэш Пирсона (RFC 3074).tree3 придерживается другого подхода и использует сами хеш-ключи для отслеживания видимости. Это зависит от специально модифицированной функции хэширования Пирсона, где нулевое значение хеш-функции всегда указывает на то, что слот не используется. Эта оптимизация устраняет затраты на использование и обслуживание битовых карт видимости, а также позволяет разместить больше хешей в одной кэш-линии и влияет на реализацию каждой примитивной операции в дереве.tree3 кэширует хеш-ключи в DRAM (в дополнение к их хранению в виде части постоянного листа). Это ускоряет операции с листьями, особенно на более медленных носителях, что кажется приемлемым увеличением использования DRAM.tree3 объединяет хеш, ключ и значение в один тип слота (KVSlot). Это приводит к улучшенной производительности разделения листьев и снижению усиления записи, поскольку разделение может быть выполнено путём замены указателей на слоты без копирования каких-либо данных ключа или значения, хранящихся в слотах. KVSlot внутренне сохраняет ключ и значение в одном постоянном буфере, что минимизирует количество постоянных выделений и повышает эффективность хранения с большими ключами и значениями.cpp_map
Использование привязок PMDK C++ в tree3 было заимствовано из этого примера программы. Большое спасибо @tomaszkapela за предоставление отличного примера для подражания!
caching
Он присутствовал в выпусках <=
Вы можете оставить комментарий после Вход в систему
Неприемлемый контент может быть отображен здесь и не будет показан на странице. Вы можете проверить и изменить его с помощью соответствующей функции редактирования.
Если вы подтверждаете, что содержание не содержит непристойной лексики/перенаправления на рекламу/насилия/вульгарной порнографии/нарушений/пиратства/ложного/незначительного или незаконного контента, связанного с национальными законами и предписаниями, вы можете нажать «Отправить» для подачи апелляции, и мы обработаем ее как можно скорее.
Опубликовать ( 0 )