December 2nd, 2012

medved

Обзор моих исследований (explorations) касательно прозрачного персистенса

1 Задача весьма близка к задаче сборки мусора: к примеру, в случае generational GC мы переносим выжившие юные объекты в старшнее поколнее, то тут же можно их засунуть в персистентное хранилище (и проапдейтить сцылы, что generational GC тоже делает). Небольшая разница в том, что изменения примитивных филдов тоже надо отслеживать, для соотв. апдейтов.
Такм образом, наиболее эффективный и в некотором смысле простой вариант - подхачить GC.

2 В силу родственности задачи GC, важной проблемой является масштабируемость на больших кучах. Как известно, обычные generational GC все время откладывают мажорные паузы, но когда она случается она может занять несколько минут на больших heap'ах. The same shit для прозрачного персистенса.
Возможен выриант сделать "real-time" GC, который использует read-barrier, в котором паузы будут ограниченны, однако так как reads обычно сильно больше writes (особливо для функ программ) read-barrier может существенно увеличить время обычной работы прилады. Вообще конечно с этим можно бороться, на уровне JIT, т.е. оверхед не такой уж и страшный. Кроме того, у современных процов много простаивающих дивайсов, так что можно разработать барьер который почти не напрягает обычное исполнение.

3 Поскольку прозрачный персистенс не обязательно совмещать с GC, то можно ограничивать размер persistent sub-heap на уровне прилады, короче не пихать в актора все что только можно :). Таким образом локальный persistent GC будет делаться шустро.

4 Для функциональных структур данных, т.е. immutable возможен крайне быстрый алгоритм для поиска новых объектов (ибо нет нужды делать обход подграфа для старых объектов). А вот сборку персистентного мусора по видимому лучше делать на уровне обычного GC - потому как там примерно те же проблемы с масштабируемостью. На самом деле, это не такая уж и проблема, мусор можно собирать на уровне самого персистентного хранилища.

5 Небольшие вкрапления mutable данных не очень страшны, ибо орешаются техниками наподобие используемых в GC, т.е. wite bariier, нужно помечать замьюченные объекты. Это однако может вызывать сложности в случае Жабы, если не интегрироваться с ее GC, поскольку хачить с помощью барьера все классы, включая стандартные Жабьи, не очень хотелось бы :).

6 Прозрачный персистенс удачно сочетается с Erlang-style actors, т.е. у которых маленькие независимые кучи, которые крайне быстро собираются. Учитывая что в Эрланг нет мутабельных структур данных - это идеальный фит для подхачивания в целях реализации прозрачного персистенса. Хотя возможно как раз для Эрланга в этом и нет особой нужды :).

7 Языки типа ML в которых есть возможность пометить данные как мутируемые также достаточно удачно вписываются в концепцию, ибо кол-во получается write-barrier'ов невелико. А некотоыре реализации поддерживают континюации, что полезно для реализации акторов.

8 Мне конечно инереснее всего реализация под JVM, но тут есть проблемы. Хачить GC не очень интересно, потому как мало кто на это решиться в реальных проектах. В случае реализации только на уровне языка или байткода, будут пробелмы с безопасностью. Т.е. несоблюдение определенных ограничений может привести к глюкам. Что тоже не есть гуд. Вполне возможно решить их на уровне статистического анализа кода и рантайм проверок (которые могут консервативно увеличивать время исполнения по сравнению с идеальным вариантом, например на уровне подхаченного GC). Впрочем для интересной мне сферы это не проблема.

9 Для Скалы есть интересный вариант - использовать могучие возможности Скалы (virtualized, плагины, macro) для того чтобы реализовать систему типов, которая бы предотвращала ошибки на уровне компиляции. Примерный аналог - continuation плагин.

10 Итого в целом, задача выглядит practical как в случае языков типа Эрланга, поддерживающих легковесных акторов нативно, так и в случае Жабы, не поддерживающих нативно (и даже делающих препятсвия на этом пути :))
medved

Особенности прозрачного vs обычного персистенса

Реализовал простенький прототип-алгоритмега для Скалы (вернее я его уже давно реализовал, чуть допилил), для immutable структур.
Уже есть некоторая интересная инфа.
Все крайне просто реализуется для Product'ов, включая List, Tuple и case class'ы.
Однако на практике важны еще Set и Map, плюс сюда можно добавить Vector (он реализуется также), ну и заодно тогда уж SortedSet/Map. Думаю без остального можно жить - имеется в виду не вообще, а только в случае прозрачно персистируемых объектов. Скала коллекции очень хороши. Тем более что традиционные Entity обычно ровно то же что и case class'ы, только мутабельные. Но для Скалы ближе иммутабельность.

В принципе, Set/Map/Vector так реализованы, что они хорошо подходят для целей прозрачного персистенса. Единственное, что diff в них не оптимизирован, хотя мог бы. А именно, они реализованы в виде Trie по 32 объекта на каждом узле, т.е. 6 уровней - мульярд. Соответсвенно, шаринг между апдейченными версиями коллекций должен быть весьма велик. Правда в глубине реализации они используют массивы (мутабельные), но пишут в них только при создании, вобщем все пучком, надо только специально это отслеживать с помощью рефлексии.

Теперь насчет разницы в создании кода для "прозрачного" персистенса. Несколько обескураживает, что там нет ключей :). В текущем моем подходе они кагбэ особо и не нужны: сохраняется весь граф объектов, ключем является адрес объекта. Т.е. понятие апдейта отсутствует - что не удивительно для immutable данных :). Хотя на самом деле, явные ключи есть в Map'ах, а неявные - в Set'ах а также в Seq'ах. Впрочем это актуально для маппинга на реляционную БД, а тут пока такой задачи не стоит. Но очевидно, что рано или поздно она встанет.

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

К примеру, рассмотрим такое простейшее расширение. У нас есть не один граф иммьютабл объектов, а несколько, и все они помечены ключами. Грубо говоря, состояние может храниться в пусть даже и мьютабл ХэшМапе - обойти ее будет нетрудно, но она ссылается на иммьютабл графы, т.е. скорость обхода практически не упадет.

Это кстати напоминает уже графовые и документарные NoSQL БД и Redis. Правда, графы не изолированные, а вообще говоря могут ссылаться друг на друга и на подгафы, т.е. это ближе к графовым БД, а не к документарным.

Вобщем получающаяся двух уровневая структура из мьютабл графа, в котором есть (deep) immutable подграфы, уже сильно гибче и интереснее, и будет масштабироваться, если следить за размером мьютабл графа (также возможны различные оптимизации). И к тому же легко мапиться на популярные персистентные хранилища, что тоже несомненный win.

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

Сие мне уже очень очень нравится, как вполне удобная и масштабируемая модель персистентности, с разумными ограничениями. Размеется, в идеале надо рассмотреть еще более гибкий вариант - когда immutable графы могут содержать mutable подграфы. В некоторых случаях можно оптимизировать и такие варианты.

К примеру, можно развязать их по ключу БД, т.е. (deep) immutable граф хранит ссылку не на сам объект, а его ключ в БД. Думаю такой подход уже подойдет во всех случаях жизни, по крайней мере, интересных мне. Т.е. mutable подграфы можно вообще исключить из модели. Это важно с точки зрения реализации в случае когда у нас нет возможность кооперироваться с GC.
medved

Прояснение целей для дальнейших поисков

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

1 Кооперация с существующим GC - требует внесение изменений в код GC.

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

Есть два подварианта - сделать свой язык/рантайм и модифицировать существующий. Первое не так уж и сложно на данный момент. Однако поскольку это вариант в целом носит исследовательский характер, то видимо все-таки лучше встроиться в существующий.

Тут мне интересны такие варианты:
1 Хак Jikes RVM ну или любой JVM, просто Jikes видимо самая удобная для экспериментов с GC
2 Хак Эрланга - по ряду причин это будет самая простая, возможно самая интересная, а возможно наоборот, самая ненужная реализация, в том смысле что может оказаться что для Эрланга это не актуально :)
3 Хак Rust - язык поддерживает конкурентность в стиле Эрланга, но есть мьютабл объекты

Менее интересные варианты: SML, Go, Scheme, Lua, Stackless Python - для них есть опенсорсные реализации с поддержкой легковесных потоков, так что тут возможны такие же хаки, но принципиально разницы с вышеперечисленными вариантами тут нет (Mono исключаем по той же причине). Есть еще Mercury - он напоминает Эрланг тем что там все иммутабельно и есть легковесные потоки, и он в частности может компилироваться в Эрланг :). Javascript'ы тоже не очень интересны, хотя тут возможен отдельные проект по прозрачному персистенсу для браузеров :).

2 Реализация в рамках нехаченной JVM/Scala

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

Подварианты:
2.1 только deep immutable структуры данных - все очень просто, по той же причине не очень интересно. Разве что сделать проверялку что персистируются только deep immutable данные.

2.2 набор помеченных ключами deep immutable графов соответственно, графы могут ссылаться друг на друга по ключу, а ассоциация объектов с ключом может менться. Что эмуилрует мутабельные подграфы, но позволяет отслеживать изменения.
Одна из основных проблем функциональных структур данных - это вложенные рекорды, ибо при изменении надо делать новые версии всех родителей. Соответственно, можно заменить рекорды к примеру иерархическими ключами.
Immutable подграфы можно в принципе хранить в относительно небольшой мутабельной структуре, хоть и в тех же мутабельных
рекордах. Обходить их будет несложно.
Есть еще две разновидности: графы могут быть изолированы (document oriented) и пересекаться (graph oriented).
Самый интересный вариант ибо достаточно гибок, просто в реализации и мапиться на NoSQL.

2.3 Более-менее общий случай. Immutable объекты могут ссылаться на mutable. При некоторых ограничениях на класс mutable объектов тоже все отнсительно несложно реализуемо, не очень понятно нужно ли это, если ссылки на мьютабл можно разявзать по ключу.
medved

Прозрачный персистенс и OODBMS, а также более общий контекст подхода

Похожесть на NoSQL навело меня на мысль, а нет ли "прозрачного" персистенса у какого-нить OODBMS. В принципе db4o чем-то напоминает, правда у него есть всякие проблемки, которые делают его не очень интересным.

Собсно, на мой взгляд прозрачный персистенс - это не есть База Данных в любом виде. Когда мы пишем код на Жабе или на Скале, мы там не делаем селекты. Хотя конечно обходим коллекции. Вот и такая же идея стоит за прозрачным персистенсом - работаем как обычно с обычными объектами и коллекциями. А прозрачный персистенс отслеживает изменения, при этом делает это в определенные моменты времени.

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

Сейчас в основном господствует Stateless идеология, т.е. перекладывание проблема на БД и кэши. В частности ее следствием является непрозрачный персистенс, т.е. необходимость все как-то пихать в БД/кэши.

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

При этом Stateful подход на порядки быстрее (т.е. существенно больше чем в 10 раз). Фактически Stateful подход делает тоже самое что и распределенные кэши, просто с более богатым функционалом и интерфейсом. Фактически, если дополнить его удобным персистенсом, то БД можно не сколько убрать, сколько избавиться от необходимости ее кластеризовать и масштабировать. По идее stateful компонент может быть привязан к своей собственной БД.

Общая идеология, в рамках которой это достижимо:
1 считаем что у нас есть акторы - компоненты, взаимодействующие через обмен сообщений (включая удаленный доступ)
2 каждый компонент обрабатывает сообщения в порядке поступления - FIFO
3 вместе это дает casual order для всех сообщений
4 соответственно, как следствие, мы можем восстанавливать консистентное состояние всей системы, при некоторых условиях:
- обработка событий детерминированна
- каждый компонент умеет делать снапшот состояния в нужный момент (между обработкой событий)
5 перед тем как сообщение становится видимым извне, инициируется координированный сброс инфы в персистентное хранилище гарантирующий восстановление консистетного состояния перед отправкой сообщения
6 для оптимизации, может логаться не сам снапшот, а инкременты, либо в виде сообщений, нужных для восстановления текущего состояния, либо инкрементальный апдейт снапшота

В целом это должно быть охуительно быстро и надежно по следующим причинам:
- casual order сообщений легко реплицируется
- запись в персистнтное хранилище идет в виде инсерта, либо отложенного bulk набора изменений, что быстро даже для жестких дисков, не говоря про использование SSD для логов
- данные храняться локально, в БД пишутся минимальные изменения (синхронно) и bulk апдейты (асинхронно). Чтение только при инициализации, либо при cache-miss.
- синхрится все только на выходе из системы, и опционально на входе. Т.е. один или два обязательных insert'а на сообщение, которые вообще говоря могут батчится с другими. Хотя в зависимости от особенностей системы, может потребоваться и асинхронные записи, например для освобождения кэшей, но тут какбэ мало что можно поделать, если памяти не хватает. В норме должно быть один-два инсерта. В случае размещения лога на SSD - это ультра-фаст, типичная задержка легко может быть меньше миллисекунды, и даже можно вести борьбу за меньше сотни мкс (в зависимости от стоимости SSDхи и сетевых интерфейсов).
- по пропускной способности - достижимы миллионы событий в секунду (для маленьких сообщений), хотя для веба вряд ли - в силу большо размера данных, которые нужно перекачать, т.е. тут уже другие боттлнеки

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