LSM tree и иммутабельные данные

[metaclass]

Настолько я понимаю, LSM-tree является вариантом реализации MVCC, в которой обновления/удаления данных создают новые версии, разбитые на несколько слоев в памяти и на диске и по достижении некоего порога количества версий (или "слоев" в хранилище) включается сборщик мусора-компактификатор, который старые версии вычищает, уменьшая количество слоев и размер БД.

А существует ли схожий алгоритм для случая, когда старые версии должны быть доступны для приложения? Например, если мы хотим хранить всю предысторию изменений состояния системы, для аудита и/или репликации, мемоизации каких-нибудь хранимых аггрегатов с пересчетом по мере необходимости и прочего такого.
Причем, если по-хорошему, это дело должно еще поддерживать partitioning, инкрементальные бэкапы, и прочее такое БД-админство, чтобы когда это дело будет хранить историю жизни за 10-15 лет, обслуживание его не выродилось в кошмар.

Вообще, откуда возникла такая идея: если реализовывать "историю"(== аудит, репликацию, пересчеты мемоизированных агрегатов) триггерами в SQL базе (если СУБД сама не умеет логи изменений), если по сути бизнес-логики нужна история изменений/версионность данных (редактирование проводок, исторические атрибуты контрагентов, изменение структуры предприятия) и не дай бог, туда надо маппить какие-нибудь графы, это дело вырождается в какую-то откровенную чернь, которая на SQL выглядит очень грустно.

В принципе, используя описанное в этой книжке: http://www.assertedversioning.com/ http://www.amazon.com/Managing-Time-Relational-Databases-Temporal/dp/0123750415 и http://www.postgresql.org/docs/9.2/static/rangetypes.html можно было бы сделать более-менее эффективное решение, но SQL не очень хорошо умеет в реюз кода (т.е. вынести весь код управления версионностью в один модуль для всех таблиц, скорее всего, не выйдет). И вопросы с репликацией, а особенно историей редактирования каких-нибудь графов остаются - неудобно оно все.

Comments

[http://users.livejournal.com/_slw/]

с чего бы от репликации должны возникать проблемы?

[plumqqz.livejournal.com]

Мне, честно говоря, вся эта затея кажется довольно сомнительной - не очень понятно, как с этим богатством иметь дело, буде оно таки создано. Нет, в самом деле - ну предположим, можно сказать "а вот покажи мне базу по состоянию два года назад" - ну и, собственно, что дальше?

[ynot.livejournal.com]

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

[http://users.livejournal.com/_slw/]

в случае FS можно посмотреть на ZFS и сделать хотя бы так же.

[wizzard]

> если реализовывать "историю"(== аудит, репликацию, пересчеты мемоизированных агрегатов) триггерами в SQL базе (если СУБД сама не умеет логи изменений), если по сути бизнес-логики нужна история изменений/версионность данных (редактирование проводок, исторические атрибуты контрагентов, изменение структуры предприятия) и не дай бог, туда надо маппить какие-нибудь графы, это дело вырождается в какую-то откровенную чернь, которая на SQL выглядит очень грустно.

по-моему, это datomic называется

[ynot.livejournal.com]

"SQL не очень хорошо умеет в реюз кода"

Вдруг стало любопытно - не пробовали ли какие-нибудь особо безумные фрики в последнее время написать нормальный современный язык, заточенный на реляционные БД напрямую (не orm-говнища), но без безумных sql-идей о "почти естественном языке чтоб менеджеры писали запросы" и с учетом достижений прогресса.

Datalog-ом вдохновляясь или типа того.

[vit-r.livejournal.com]

Вообще-то не менеджеры даже. "Что там должно происходить, никто не знает, потому что отдел умеет работать только с Экселом"

[vit-r.livejournal.com]

А существует ли схожий алгоритм для случая, когда старые версии должны быть доступны для приложения?

Бекапы - это уровень администратора. Если приложение должно бегать по старым записям, то тут они ни при чём, и надо хранить историю в старых таблицах. Насколько понимаю, наиболее популярны - это пометки от и до какого времени данная запись была действительной. Хотя, я с базами работаю редко.

[permea-kra.livejournal.com]

Насколько я помню, штатное использование lsm-tree - это обновлять индекс к тайм-сериям.

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

[kosiakk.livejournal.com]

Почему-то ещё никто не упомянул Datomic, где многие фичи вроде как уже сделаны.

[aka-rider.livejournal.com]

Классический вариант LSM-tree - это дерево в памяти + данные в persistent хранилище http://en.wikipedia.org/wiki/Log-structured_merge-tree, MVCC и проч. делается уже поверх.
Готовых решений для вашей задачи я не встречал, из похожего вспомнился только Facebook Haystack https://www.facebook.com/note.php?note_id=76191543919

[manipulatedinfo.livejournal.com]

Из LSM не следует MVCC, ибо периодически в LSM запускается процедура под названием "compaction", которые сливает слои, т.е. 2 версии сливаются в одну не обязательно с сохранением обоих версий. Можно реализовать так, чтобы обе версии сохранялись, т.е. дописывать новую сразу после старой, но MVCC не следует из LSM автоматически, а просто удобно реализуется в рамках LSM наверное.