Для исследования и мониторинга распространения ipv6 сетей, а так же выполнения автоматическоего детектирование подсетей, необходимо хранить очень большое количество деревьев (деревья с высотой максимум 8 (сжатые)). В данной статье я расскажу про графовую базу данных и о том как в связке можно хранить доменные данные между двумя базами.
Про Neo4j:
Neo4j — open-source графовая база данных, история которой началась по инвестициям компании «Neo Technology» в 2003 году. С 2007 года стала публично доступной. В Neo4j присутствуют все характеристики баз данных, включая соблюдение ACID, поддержание разбиение на кластеры и восстановления после сбоя в системе. Сегодня является лидером среди графов баз данных.
Neo4j - данные хранит в собственном формате, специализированно приспособленном для представления графовой информации, такой подход в сравнении с моделированием графовой базы данных средствами реляционной СУБД позволяет применять дополнительную оптимизацию в случае данных с более сложной структурой. Также утверждается о наличии специальных оптимизаций для SSD-накопителей, при этом для обработки графа не требуется его помещение целиком в оперативную память вычислительного узла, таким образом, возможна обработка достаточно больших графов.
Компоненты графовой базы данных — узлы и ребра. Они могут быть дополнены собственным набором полей. Модель такой БД схематично изображена на рисунке.
Язык запросов:
Cypher — самый распространенный язык запросов к графовым базам данных, что обусловлено его использованием в СУБД Neo4j . Cypher является декларативным языком и позволяет создавать, обновлять и удалять вершины, ребра, метки и свойства, а также управлять индексами и ограничениями. Для извлечения данных из хранилища используется запрос, содержащий шаблон фильтрации, позволяющий получать
Примеры шаблонов:
1. (n)-->(m) — все направленные ребра из вершины n в вершину m;
2. (n:Person) — все вершины с меткой Person;
3. (n:Person:Russian) — все вершины, имеющие обе метки Person и Russian;
4. (n:Person {name:{value}}) — все вершины с меткой Person и отфильтрованные по дополнительному свойству;
5. (n:Person)-->(m) — ребра между вершинами n с меткой Person и m;
6. (n)--(m) — все ненаправленные ребра между вершинами n и m;
Возможности хранения данных в связке:
Для хранения обычно используют связку РСУБД и Neo4j, как правило сущности относяшиеся к доменной модели хранят в РСУБД, а вот связи между ними как раз в Neo4j. Для двух связанных БД пишется сервис прослойка, который умеет работать и с одной и с другой БД, и отдавать данные пользователю уже в виде заполненного графа.
В случае с мониторингом, данные об отдельных Ipv6 возможно хранить в Postgresql например, связи для алгоритма хранить в Neo4j.
Кратко расскажу сам алгоритм, идея хранения данных и подсчета такая - будем хранить лес, где каждое дерево будет отдельная подсеть 1-го октета в Ipv6 адресе. При добавлении адреса в нашу систему, мы будем считать попадания на каждом узле в дереве сети. Дальше есть много разных улучашний связанных с предсказанием выборки большой сети (как раз тех сетей которые мы хотим обнаружить и показать их пользователю), например это может быть алгоритм иммитации отжига, или локальный поиск сильной связности детей у родителя, и другие (их довольно много, все будет полность описано в научной работе).
Таким образом все деревья мы будем хранить в одном большом графе, у которого будут отдельные ссылки на подграфы в для каждой подсети, начиная с 0, собственно там же мы будем хранить и счетчики. Например сборку Ipv6 аддреса можно будет проводить простым dfs от родительсокого с 0 подсети к корню. Поиск наиболее заполненных подсетей тоже выходит простым, с точки зрения запросов на Cypher (https://neo4j.com/docs/graph-data-science/current/algorithms/dfs/) - пример алгоритма на данном языке.
Выводы:
Таким образом при использование графовой БД, мы получаем довольно большую гибкость и возможность применять графовые алгоритмы, без использования SQL , хотя язык так же остается декларативным, но более удобным. Есть так же и минус в данной связке:
1. Интеграция разного рода данных - увеличивается время обработки и выдаче данных
2. В графовых БД на узлах или на связях плохим решением будет хранить тяжелые данные - только связи и идентификаторы.
3. Небольшое дублирование данных выходит - сущность становится более размазанной и возникает потребность в дублировании.