Одним из самых известных и эффективных алгоритмов Pattern matching-а для продукционных систем является Rete_algorithm.
Тут я не буду рассказывать что это такое и с чем его едят, т.к. об этом написаны сотни книг и статей. Расскажу лучше о том как удалось написать собственную альтернативу этому подходу для специфического случая и специфических данных и этот подход дал очень заметный прирост производительности. Прирост в моем случае сравнивается с изначальной имплементацией сделанной на основе библиотеки drools - бесплатной реализации rete-algortihm-а от JBoss. Тут я конечно сильно утрирую, drools - на самом деле это не просто Pattern matching движок а полноценный rule-engine со встроенной поддержкой объектной модели ООП языка. То есть в нем изначально встроены понятия объекта, его класса, полей, наследования и тп. Выразительная мощь такого описания данных через объекты почти равносильна логике первого порядка(FOL), (и, сдается мне, внутри drools переводит высказывания объектной формы в равносильные им высказывания FOL)
Почти, т.к. использование функциональных символов весьма ограничено. Использование последних делает любой логический вывод в FOL настоящей головной болью (т.к., по сути, делает пространство моделей бесконечным), поэтому документация drools не рекомендует их использовать.
Впрочем, этот пост о более приземленных вещах.
Итак, задача состоит в следующем: есть древовидная структура данных, глубина обычно не превышает 5-10 уровней. Каждый узел содержит ссылки на дочерние узлы, кол-во которых произвольно но обычно не превышает 5-6 штук. Каждый узел также содержит 3-4 поля "полезной нагрузки" в виде строковых или числовых полей. Требуется находить в такой модели несколько десятков паттернов-правил, которые меняют это дерево и создают слегка модифицированную его копию которую надо сохранить и также применить к ней эти же правила, и так далее.
Функционально drools замечательно справляется с этой задачей, особенно в части простоты добавления новых правил (это одно из требований задачи). А вот в плане производительности и потребления памяти это решение совсем не устроило. После применения правил и постройки набора новых деревьев нужно иметь возможность применять правила заново к одному из этих новых деревьев. Это можно сделать двумя способами - либо ввести идентификаторы версии внутри дерева либо иметь отдельную сессию drools.
Оба варианта оказались плохими в большей или меньшей степени. Введение идентификаторов усложняет описание паттернов, т.к. нужно включать идентификатор по крайней мере для одного из узлов в запросе, да и держать кучу версий (а их надо обрабатывать желательно не менее 4-6 тысяч в секунду) в памяти, когда в любой момент времени мы нуждаемся в pattern-matching-е только для одного дерева, крайне нежелательно. Создание новой сессии drools также довольно дорогостоящая операция. В итоге оба варианта потребляли около 100-150 MB хипа JVM для обработки одного запроса состоящего примерно из 4-6 тысяч вызовов матчинга правил и выполнялось непозволительно долго.
Напрашивалась возможность каким то образом сократить потребление памяти. Как можно хранить большое количество версий деревьев? Каждое из правил-паттернов в большинстве случаев изменяло лишь небольшую часть дерева, то есть большая часть узлов просто была клоном узлов дерева на котором применялись правила. Поэтому напрашивалась идея создавать новые объекты только для измененных узлов копируя ссылки на остальные. Но при этом может возникнуть ситуация когда мы поменяли узел в дереве (например добавили дочерний узел в его список ссылок) а ссылка на него есть в нескольких других деревьях, которые не должны меняться.
Вариант решения - сделать объекты узлы неизменяемыми (immutable) типами. В этом случае, чтобы опять таки не копировать все дерево, придется отказаться от ссылки на родительский узел.
Вообще, одним из традиционных недостатков immutable типов считается именно потребление памяти - мы вынуждены сделать полную копию даже если хотим поменять сколь угодно малую часть его данных. В случае же, если мы делаем составной неизменяемый объект из неизменяемых объектов то ситуация оказывает много лучшей - мы меняем только измененные объекты. В случае деревьев, мы просто создаем новые версии родительских узлов вплоть до корневого узла. То есть нам например понадобилось изменить узел N6 (см картинку)
Для этого мы просто создаем новый родительский узел N3, копируя старый список ссылок и изменяя в нем лишь ссылку на новый N6. И так далее до корня.
Таким образом мы можем пере-использовать узлы не создавая полные копии деревьев.
Кстати именно таким образом обновляются B+ деревья в базах данных в модели MVCC - обновив лишь log(N) элементов индекса для N записей мы имеем собственную, измененную копию, не мешая остальным.
Что же насчет самого матчинга ?
Простое сокращение объема потребляемой на узлы всех версий деревьев памяти не решило проблему, т.к. большинство ее потреблялось на структуры самой rete-сети. Длительность обработки также существенно не изменилась.
Было решено попробовать сделать собственный, заточенный именно под данную задачу механизм матчинга и неиспользовать drools совсем.
Исходя из данного и потенциального набора правил было замечено что все правила задают параметры узлов не больше 2-3 уровней относительно друг друга и почти все правила имеют фильтры по типам (классам) узлов. А также было очень мало правил которые бы задавали условия между узлами которые не являются предками друг друга или не имеют непосредственногообщего предка. То есть мой набор паттернов обладал по большей части свойством локальности - большинство (почти все) паттерны задавали соотношения между близкими в дереве узлами.
Поэтому попробовал сделать так - рекурсивно обходим узлы дерева, сохраняя цепочку родительских узлов в стеке, и параллельно создаем битовую маску типов родительских и текущего узлов глубиной в 3 уровня. Для каждого из правил задаем статическую битовую маску необходимых типов исходя из его паттерна. Конечно, поскольку было много правил которые определяли соотношения между узлами с общим предком, пришлось сделать дополнительный проход по потомкам, где, при срабатывании прочих критериев, внутри самих правил делался еще проход по предыдущим "братьям" до первого срабатывания. Естественно этот дополнительный проход запускался только в случае срабатывания критерия по одному из дочерних и родительским (обычно 1+2 уровня вверх) узлам и останавливался при первом же матче.
Мое решение стало работать на 2(!) порядка быстрей по сравнению с изначальным подходом.
Конечно сложность такого алгоритма гораздо больше rete-сети, но в моем случае, для данной специфической задачи, более простой подход оказался гораздо эффективней. То есть тот самый случай когда коэффициент перед N^2 оказался гораздо ниже чем перед N, и, в итоге, на данных объемах данных перевесил почти все плюсы drools.
Почти, так как в моем случае добавление новых правил требует написания дополнительного кода для правила(если есть какие то доп. условия помимо типа узла и его предков), вместо декларативного описания правил в drools.
Тут я не буду рассказывать что это такое и с чем его едят, т.к. об этом написаны сотни книг и статей. Расскажу лучше о том как удалось написать собственную альтернативу этому подходу для специфического случая и специфических данных и этот подход дал очень заметный прирост производительности. Прирост в моем случае сравнивается с изначальной имплементацией сделанной на основе библиотеки drools - бесплатной реализации rete-algortihm-а от JBoss. Тут я конечно сильно утрирую, drools - на самом деле это не просто Pattern matching движок а полноценный rule-engine со встроенной поддержкой объектной модели ООП языка. То есть в нем изначально встроены понятия объекта, его класса, полей, наследования и тп. Выразительная мощь такого описания данных через объекты почти равносильна логике первого порядка(FOL), (и, сдается мне, внутри drools переводит высказывания объектной формы в равносильные им высказывания FOL)
Почти, т.к. использование функциональных символов весьма ограничено. Использование последних делает любой логический вывод в FOL настоящей головной болью (т.к., по сути, делает пространство моделей бесконечным), поэтому документация drools не рекомендует их использовать.
Впрочем, этот пост о более приземленных вещах.
Итак, задача состоит в следующем: есть древовидная структура данных, глубина обычно не превышает 5-10 уровней. Каждый узел содержит ссылки на дочерние узлы, кол-во которых произвольно но обычно не превышает 5-6 штук. Каждый узел также содержит 3-4 поля "полезной нагрузки" в виде строковых или числовых полей. Требуется находить в такой модели несколько десятков паттернов-правил, которые меняют это дерево и создают слегка модифицированную его копию которую надо сохранить и также применить к ней эти же правила, и так далее.
Функционально drools замечательно справляется с этой задачей, особенно в части простоты добавления новых правил (это одно из требований задачи). А вот в плане производительности и потребления памяти это решение совсем не устроило. После применения правил и постройки набора новых деревьев нужно иметь возможность применять правила заново к одному из этих новых деревьев. Это можно сделать двумя способами - либо ввести идентификаторы версии внутри дерева либо иметь отдельную сессию drools.
Оба варианта оказались плохими в большей или меньшей степени. Введение идентификаторов усложняет описание паттернов, т.к. нужно включать идентификатор по крайней мере для одного из узлов в запросе, да и держать кучу версий (а их надо обрабатывать желательно не менее 4-6 тысяч в секунду) в памяти, когда в любой момент времени мы нуждаемся в pattern-matching-е только для одного дерева, крайне нежелательно. Создание новой сессии drools также довольно дорогостоящая операция. В итоге оба варианта потребляли около 100-150 MB хипа JVM для обработки одного запроса состоящего примерно из 4-6 тысяч вызовов матчинга правил и выполнялось непозволительно долго.
Напрашивалась возможность каким то образом сократить потребление памяти. Как можно хранить большое количество версий деревьев? Каждое из правил-паттернов в большинстве случаев изменяло лишь небольшую часть дерева, то есть большая часть узлов просто была клоном узлов дерева на котором применялись правила. Поэтому напрашивалась идея создавать новые объекты только для измененных узлов копируя ссылки на остальные. Но при этом может возникнуть ситуация когда мы поменяли узел в дереве (например добавили дочерний узел в его список ссылок) а ссылка на него есть в нескольких других деревьях, которые не должны меняться.
Вариант решения - сделать объекты узлы неизменяемыми (immutable) типами. В этом случае, чтобы опять таки не копировать все дерево, придется отказаться от ссылки на родительский узел.
Вообще, одним из традиционных недостатков immutable типов считается именно потребление памяти - мы вынуждены сделать полную копию даже если хотим поменять сколь угодно малую часть его данных. В случае же, если мы делаем составной неизменяемый объект из неизменяемых объектов то ситуация оказывает много лучшей - мы меняем только измененные объекты. В случае деревьев, мы просто создаем новые версии родительских узлов вплоть до корневого узла. То есть нам например понадобилось изменить узел N6 (см картинку)
Кстати именно таким образом обновляются B+ деревья в базах данных в модели MVCC - обновив лишь log(N) элементов индекса для N записей мы имеем собственную, измененную копию, не мешая остальным.
Что же насчет самого матчинга ?
Простое сокращение объема потребляемой на узлы всех версий деревьев памяти не решило проблему, т.к. большинство ее потреблялось на структуры самой rete-сети. Длительность обработки также существенно не изменилась.
Было решено попробовать сделать собственный, заточенный именно под данную задачу механизм матчинга и неиспользовать drools совсем.
Исходя из данного и потенциального набора правил было замечено что все правила задают параметры узлов не больше 2-3 уровней относительно друг друга и почти все правила имеют фильтры по типам (классам) узлов. А также было очень мало правил которые бы задавали условия между узлами которые не являются предками друг друга или не имеют непосредственногообщего предка. То есть мой набор паттернов обладал по большей части свойством локальности - большинство (почти все) паттерны задавали соотношения между близкими в дереве узлами.
Поэтому попробовал сделать так - рекурсивно обходим узлы дерева, сохраняя цепочку родительских узлов в стеке, и параллельно создаем битовую маску типов родительских и текущего узлов глубиной в 3 уровня. Для каждого из правил задаем статическую битовую маску необходимых типов исходя из его паттерна. Конечно, поскольку было много правил которые определяли соотношения между узлами с общим предком, пришлось сделать дополнительный проход по потомкам, где, при срабатывании прочих критериев, внутри самих правил делался еще проход по предыдущим "братьям" до первого срабатывания. Естественно этот дополнительный проход запускался только в случае срабатывания критерия по одному из дочерних и родительским (обычно 1+2 уровня вверх) узлам и останавливался при первом же матче.
Мое решение стало работать на 2(!) порядка быстрей по сравнению с изначальным подходом.
Конечно сложность такого алгоритма гораздо больше rete-сети, но в моем случае, для данной специфической задачи, более простой подход оказался гораздо эффективней. То есть тот самый случай когда коэффициент перед N^2 оказался гораздо ниже чем перед N, и, в итоге, на данных объемах данных перевесил почти все плюсы drools.
Почти, так как в моем случае добавление новых правил требует написания дополнительного кода для правила(если есть какие то доп. условия помимо типа узла и его предков), вместо декларативного описания правил в drools.
