Стойкие (чисто функциональные) красно-черные деревья на диске

Я изучаю лучшие структуры данных для реализации простой временной базы данных с открытым исходным кодом, и в настоящее время я очень люблю использовать Persistent Red-Black деревья для этого.

Мои основные причины использования постоянных структур данных - это, прежде всего, минимизация использования блокировок, поэтому база данных может быть как можно более параллельной. Также будет проще реализовать транзакции ACID и даже возможность абстрагировать базу данных для параллельной работы в кластере. Самое замечательное в этом подходе заключается в том, что он позволяет практически временно создавать временные базы данных. И это очень приятно иметь, особенно для Интернета и для анализа данных (например, тенденции).

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

Вот моя мысль: - Поскольку все записи выполняются асинхронно, а использование постоянной структуры данных позволит не отменять предыдущую и в настоящее время действительную структуру, время записи на самом деле не является узким местом. - Есть литература по таким структурам, как это, которые предназначены именно для использования на диске. Но мне кажется, что эти методы добавят больше накладных расходов на чтение для достижения более быстрой записи. Но я думаю, что лучше всего наоборот. Кроме того, многие из этих методов действительно заканчиваются деревьями с несколькими версиями, но они не являются строго неизменными, что очень важно для оправдания постоянных накладных расходов. - Я знаю, что при добавлении значений в базу данных все еще будет какая-то блокировка, и я также знаю, что должна быть хорошая логика сбора мусора, если не все версии должны поддерживаться (в противном случае размер файла, безусловно, резко возрастет), Также можно подумать о системе дельта-сжатия. - Из всех структур деревьев поиска я действительно думаю, что Red-Blacks наиболее близки к тому, что мне нужно, поскольку они предлагают наименьшее количество вращений.

Но есть некоторые возможные подводные камни: - Асинхронная запись - может влиять на приложения, которые нуждаются в данных в реальном времени. Но я не думаю, что это относится к веб-приложениям в большинстве случаев. Также, когда нужны данные в реальном времени, можно было бы разработать другие решения, такие как система регистрации/проверки конкретных данных, которые необходимо будет обрабатывать более оперативно. - Также они могут привести к некоторым конфликтам с фиксацией, хотя я не думаю о хорошем примере того, когда это может произойти. Также могут возникать конфликты в нормальной СУБД, если два потока работают с одними и теми же данными, верно? - Накладные расходы на наличие неизменяемого интерфейса, подобного этому, будут расти экспоненциально, и все обречено на провал в ближайшее время, поэтому все это плохая идея.

изменить: Кажется, что возникает непонимание того, что такое постоянная структура данных: http://en.wikipedia.org/wiki/Persistent_data_structure

Ответы

Ответ 1

Если вы обнаружите, что получаете узкое место во время записи или что ваша долговременная гарантия бессмысленна без синхронной записи (hmm...), вы должны делать то, что делают большинство других баз данных: реализовать Write-Ahead Log (WAL) или повторный журнал.

Диски на самом деле довольно хороши при написании последовательно или, по крайней мере, в том, что лучше. Это случайные записи (например, в дереве), которые ужасно медленны. Даже флеш-накопители, избивающие черты дисков для случайной записи, по-прежнему значительно лучше при последовательной записи. Фактически, даже большая оперативная память лучше при последовательной записи, потому что задействовано меньше управляющих сигналов.

При использовании журнала записи вперед вам не о чем беспокоиться:

Torn пишет (вы написали половину дерева, прежде чем кошка съела ваш источник питания).
Потеря информации (вы фактически не смогли сохранить дерево, но Джо думает, что вы это сделали)
Огромные удары производительности от случайных, синхронных дисковых операций ввода-вывода.

Ответ 2

Моя мысль заключается в том, что у вас отличная идея. Теперь пойдите, постройте чертову вещь. Из всего, что вы написали, похоже, что вы страдаете от острого случая анализа паралича.

Ответ 3

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

Ответ 4

Интересно с кем-то подобным:-) Я фактически реализовал базу данных, которая использует постоянную структуру данных в качестве своей модели данных. Тип стойкого В2-дерева, я полагаю, его можно было бы назвать. Append-only хранение на диске и сбор мусора - не вся история должна храниться вечно. Можно установить конечный период сохранения, чтобы база данных могла забыть о ранней истории.

См. http://bergdb.com/