YELP зарубежная сеть, которая помогает людям находить местные предприятия и услуги, основываясь на отзывах, предпочтениях и рекомендациях. В текущей статей будет проведен определенный ее анализ с использованием платформы Neo4j, относящаяся к графовым СУБД, а также язык python.
Что посмотрим:
как работать с Neo4j и объемными датасетами на примере YELP;
чем может быть полезен YELP dataset;
частично: какие особенности в новых версиях Neo4j и почему книга Графовые алгоритмы 2019 года от O'REILLY уже устарела.

Что такое YELP и yelp dataset.

Сеть YELP на текущий момент охватывает 30 стран, РФ пока не входит в их число. Русский язык сетью не поддерживается. Сама сеть содержит достаточно объемное количество сведений о различного рода предприятиях, а также отзывах о них. Также yelp можно смело назвать социальной сетью, так как в ней имеются данные о пользователях, оставлявших отзывы. Никаких персональных данных там нет, только имена. Тем не менее пользователи образуют сообщества, группы или же могут быть в дальнейшем в эти группы и сообщества объединены по различным признакам. Например по количеству звезд (stars), которые поставили той точке (ресторану, заправке и т.п.), которую посетили.
Сама себя YELP описывает следующим образом:
-8,635,403 отзывов
-160,585 предприятий
-200,000 картинок
-8 мегаполисов
1,162,119 рекомендаций от 2,189,457 пользователей
Более 1.2 миллиона бизнес-атрибутики: часы работы, парковка, доступность и т.п.

С 2013 года Yelp регулярно проводит конкурс Yelp Dataset, призывая всех желающих
исследовать и изучать открытый набор данных Yelp.
Сам датасет доступен по ссылке
Датасет достаточно объемный и после распаковки представляет из себя 5 файлов формата json:


Все бы ничего, да вот только YELP выкладывает сырые (raw), необработанные данные и, чтобы начать с ними работать, потребуется предобработка.

Установка и быстрая настройка Neo4j.

Для анализа будет использоваться Neo4j, используем возможности графовой СУБД и их незамысловатый язык cypher для работы с датасетом.
О Neo4j как графовой СУБД неоднократно писали на Habrе (здесь и здесь статьи для начинающих), поэтому повторно представлять ее нет смысла.
Для того, чтобы начать работу с платформой, необходимо скачать desktop версию (около 500Mb) либо поработать в online песочнице. На момент написания статьи доступна Neo4j Enterprise 4.2.6 for Developers, а также иные, более ранние версии для установки.
Далее будет использоваться вариант работа в desktop версии в среде Windows (версии 4.2.5, 4.2.1).
Не смотря на то, что самая свежая версия 4.2.6, лучше ее пока не устанавливать, так как для нее еще не актуализированы все плагины, использующиеся в neo4j. Достаточно будет предыдущей версии 4.2.5.
После установки скачанного пакета, необходимо будет:
создать новую локальную БД, указав пользователя neo4j и пароль 123 (почему именно их, объясню ниже),
установить плагины, которые понадобятся APOC, Graph Data Science Library.
проверить, запускается ли БД и открывается ли браузер при нажатии на кнопку старт.
*- включить offline режим, чтобы БД истово не пыталась предлагать новые версии.

Загружаем данные в Neo4j.

Если с установкой Neo4j все прошло гладко, можно двигаться дальше и тут есть два пути.

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

и итоговой схемой:


Чтобы пройти первый путь, лучше ознакомиться сперва со статьей на medium.
*Большое человеческое спасибо за это TRAN Ngoc Thach.
И воспользоваться готовым jupyter notebookом (адаптирован мною под windows) ссылка.
Процесс импорта не из простых и занимает достаточно продолжительное время

Проблем с памятью при этом не возникает даже при наличии всего лишь 8Гб Ram, так как используется пакетный импорт.
Однако потребуется создать swap файл размером на 10Гб, так как при проверке импортированных данных jupyter крашится, об этом моменте есть упоминание в вышеуказанной тетрадке jupyter.

Второй путь самый быстрый и был обнаружен случайно. Он подразумевает копирование уже готовой БД neo4j в существующую БД neo4j напрямую. Из минусов (пока обнаруженных) нельзя произвести backup БД средствами Neo4j (neo4j-admin dump --database=neo4j --to=D:\neo4j\neo4j.dump). Однако, это может быть связано с различиями в версиях в версии 4.2.1 была скопирована БД от версии 4.2.5.
Как реализуется этот метод:
открыть вкладку Manage БД, куда будет произведен импорт
перейти в папку с БД и скопировать туда папку data, перезаписав возможные совпадения.
При этом сама БД, куда произведено копирование не должна быть запущена.
перезапустить Neo4j.
И вот здесь пригодятся логин-пароль, которые ранее были использованы (neo4j,123) для избежания конфликтов.
После старта скопированной БД будет доступна БД c yelp-датасетом:

Смотрим YELP.

Изучать YELP можно как из Neo4j браузера, так и отправляя запросы в БД из того же jupyter notebook.
Благодаря тому, что БД графовая, в браузере будет сопровождать приятная наглядная картинка, на которой эти графы и будут отображаться.
Приступая к ознакомлению с YELP необходимо оговориться, что в БД будут только 3 страны US,KG и CA:

Посмотреть схему БД можно написав запрос на языке cypher в браузере neo4j:

CALL db.schema.visualization()

И вот здесь, если мы пошли по пути импорта БД путем прямого копирования (второй путь) нас ждет совсем иная картинка:

На работоспособность БД это не влияет.
Однако будем ориентироваться на оригинальную схему


Как читать эту схему? Выглядит все следующим образом. Вершина User имеет связь сама с собой типа FRIENDS, а также связь WROTE с вершиной Review. Rewiew в свою очередь имеет связь REVIEWS с Business и так далее. Посмотреть на это можно наглядно после нажатия на одной из вершин (node labels), например на User:

БД выберет любых 25 пользователей и покажет их:

Если нажать на соответствующий значок прямо на пользователе, то будут показаны все идущие от него прямые связи, а так как связи у User двух типов FRIENDS и REVIEW, то все они появятся:

Это удобно и неудобно одновременно. С одной стороны о пользователе можно посмотреть всю информацию одним кликом, но в то же время этим кликом нельзя убрать лишнее.
Но здесь нет ничего страшного, можно по id найти этого пользователя и только всех его друзей:

MATCH p=(:User {user_id:"u-CFWELen3aWMSiLAa_9VANw"}) -[r:FRIENDS]->() RETURN p LIMIT 25

Точно так же можно посмотреть какие отзывы написал данный человек:

YELP хранит отзывы аж от 2010 года! Сомнительная полезность, но тем не менее.
Чтобы почитать эти отзывы необходимо переключиться в вид текста, нажав на А

Посмотрим на место, о котором писала Sandy 10 лет назад и найдем его на yelp.com
Такое место действительно существует www.yelp.com/biz/cafe-sushi-cambridge,
а вот и сама Sandy co своим отзывом www.yelp.com/biz/cafe-sushi-cambridge?q=I%20was%20really%20excited

Запросы на python из jupyter notebook.

Здесь будут частично использованы сведения из упомянутой свободно распространяемой книги Графовые алгоритмы 2019 года от O'REILLY. Частично, потому как синтаксис из книги во многих местах устарел.
База, с которой мы будем работать должна быть запущена, при этом сам neo4j браузер запускать нет необходимости.
Импорт библиотек:

from neo4j import GraphDatabaseimport pandas as pdfrom tabulate import tabulateimport matplotlibmatplotlib.use('TkAgg')import matplotlib.pyplot as plt

Подключение к БД:

driver = GraphDatabase.driver("bolt://localhost", auth=("neo4j", "123"))

Подсчитаем количество вершин для каждой метки в БД:

result = {"label": [], "count": []}with driver.session() as session:    labels = [row["label"] for row in session.run("CALL db.labels()")]    for label in labels:        query = f"MATCH (:`{label}`) RETURN count(*) as count"        count = session.run(query).single()["count"]        result["label"].append(label)        result["count"].append(count)df = pd.DataFrame(data=result)print(tabulate(df.sort_values("count"), headers='keys',tablefmt='psql', showindex=False))

На выходе:
+----------+---------+
| label | count |
|----------+---------|
| Country | 3 |
| Area | 15 |
| City | 355 |
| Category | 1330 |
| Business | 160585 |
| User | 2189457 |
| Review | 8635403 |
+----------+---------+
Похоже на правду, в нашей базе 3 страны, как мы увидели ранее через neo4j браузер.
А этот код подсчитает количество связей (ребер):

result = {"relType": [], "count": []}with driver.session() as session:    rel_types = [row["relationshipType"] for row in session.run    ("CALL db.relationshipTypes()")]    for rel_type in rel_types:        query = f"MATCH ()-[:`{rel_type}`]->() RETURN count(*) as count"        count = session.run(query).single()["count"]        result["relType"].append(rel_type)        result["count"].append(count)df = pd.DataFrame(data=result)print(tabulate(df.sort_values("count"), headers='keys',tablefmt='psql', showindex=False))

Выход:
+-------------+---------+
| relType | count |
|-------------+---------|
| IN_COUNTRY | 15 |
| IN_AREA | 355 |
| IN_CITY | 160585 |
| IN_CATEGORY | 708884 |
| REVIEWS | 8635403 |
| WROTE | 8635403 |
| FRIENDS | 8985774 |
+-------------+---------+
Думаю, принцип понятен. В завершение напишем запрос и визуализируем его.

Результат должен получиться следующий

Ось X представляет рейтинг отеля в звездах, а ось Y общий процент каждого рейтинга.

Чем может быть полезен YELP dataset

.
Из плюсов можно выделить следующие:
достаточно богатое информационное поле по содержательной составляющей. В частности можно просто насобирать отзывы со звездами 1.0 или 5.0 и заспамить какой-либо бизнес. Гм. Немного не в ту сторону, но вектор понятен;
датасет объемен, что создает дополнительные приятные трудности в плане тестирования производительности различных платформ по анализу данных;
представленные данные имеют определенную ретроспективу и в принципе возможно понять, как менялось предприятие, исходя из отзывов о нем;
данные можно использовать как ориентиры по предприятиям, учитывая, что имеются адреса;
пользователи в датасете зачастую образуют интересные взаимосвязанные структуры, которые можно брать как есть, не формируя пользователей в искусственную соц. сеть и не собирая данную сеть из иных существующих соц. сетей.
Из минусов:
всего лишь три страны представлены из 30-ти и есть подозрение, что и то не полностью,
отзывы хранятся по 10 лет, что может искажать и зачастую портить характеристику существующего бизнеса,
о пользователях мало данных, они обезличены, поэтому, рекомендательные системы на базе датасета будут явно хромать,
в связях FRIENDS используются направленные графы, то есть Аня дружит -> Петей. Получается, что Петя не дружит с Аней. Это решается программно, но все равно это неудобно.
датасет выкладывается сырой и требуется значительные усилия для его предобработки.

Несколько слов об особенностях новых версий Neo4j

Neo4j динамично обновляется и новая версия интерфейса, используемого в 4.2.6 не совсем удобна, на мой взгляд. В частности не хватает наглядности в части сведений о количестве нод и связей в БД, что было в предыдущих версиях. Кроме того, интерфейс перемещения по вкладкам при работе с БД был изменен и к нему тоже необходимо привыкнуть.
Главная неприятность в обновлениях интеграция графовых алгоритмов в плагин Graph Data Science Library. Ранее они именовались neo4j-graph-algorithms
После интеграции многие алгоритмы значительно изменили синтаксис. По этой причине, изучение книги Графовые алгоритмы 2019 года от O'REILLY может быть затруднено.

Обработанная БД yelp для neo4j для прямого копирования и последующего анализа будет выложена позднее.

Часть 1. Начало

1.1 Введение и постановка задачи

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

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

Под сервисами ТС понимается любое проключение клиентского оборудования. Это могут базовые станции (БС), В2В клиенты (использующие ТС МТС для организации доступа в сеть Интернет и/или наложенных сетей VPN), клиенты фиксированного доступа (т.н. ШПД), и т.д. и т.п.

В нашем распоряжении две централизованные информационные системы:

Любая транспортная сеть по своей сути является ориентированным графом , в котором каждое ребро имеет неотрицательную пропускную способность. Потому с самого начала поиск решения указанных задач выполнялся в рамках теории графов.

Сначала вопрос сопоставления показателей качества ТС и сервисов с топологией ТС решался путем буквального объединения и представления данных топологии и качества в виде сетевого графа.

Просмотр сформированного по данным топологии и производительности графа был реализован на open source ПО Gephi. Это позволило решить задачу автоматического представления топологии, без ручной работы по её актуализации. Выглядит это так:


Здесь, узлы это, собственно узлы ТС (маршрутизаторы, коммутаторы) и базовые, рёбра каналы ТС. Цветовая маркировка, соответственно, обозначает наличие деградаций качества и статусы обработки этих деградаций.

Казалось бы вполне наглядно и можно работать, но:

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

Также, надо иметь ввиду, что в общем случае топология сети гораздо сложнее (выше приведенный фрагмент обведён красным):


И это не самый маленький сегмент есть гораздо больше и сложнее по топологии:


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

---

Часть 2. Автоматизация v1.0

Напоминаю, какие задачи мы решали:

1. Определение пути проключения сервиса через ТС Прямая задача.
2. Определение зависимых сервисов от канала ТС Обратная задача.

2.1. Транспортные сервисы для Базовых Станций (БС)

Обобщенно, организация транспорта от центрального узла (контроллера/шлюза) до БС выглядит так:


На сегментах агрегации и ядра ТС проключения выполняются через транспортные сервисы MPLS сети: L2/L3 VPN, VLL. На сегментах доступа проключения выполняются, как правило, через выделенные VLAN-ы.

Напоминаю, что у нас есть БД где лежит вся актуальная (в пределах определенного срока) параметрия и топология ТС.

2.2. Решение для коммутируемого сегмента (доступ)

Берем данные о VLAN логического интерфейса БС, и пошагово идём по связям, порты которых содержат этот Vlan ID, пока не дойдем до граничного маршрутизатора (МВН).


Для решения такой простой постановки задачи в итоге пришлось:

1. Написать алгоритм пошаговой трассировки распространения VlanID от БС по каналам сети агрегации
2. Учесть имеющиеся пробелы в данных. Особенно это касалось стыков между узлами на площадках.
3. Фактически написать SPF алгоритм для того чтобы отбросить в конце тупиковые ветки, которые не ведут к МВН маршрутизатору.

Алгоритм получился из одного основного процесса и семи подпроцессов. На его реализацию и отладку было потрачено недели 3-4 чистого рабочего времени.

Кроме того, особое удовольствие нам доставили

2.2.1. SQL JOIN

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

По понятным причинам не могу здесь приводить содержимое запросов к БД, но оцените каждый уступ в тексте запроса это подключение очередной таблицы, которая нужна для, в данном случае, получения в унифицированном виде соответствия Порт VlanID:


А этот запрос для получения, в унифицированном виде кросс-коннектов VlanID внутри коммутатора:


Учитывая, что кол-во портов составляло несколько десятков тысяч, а VLAN в 10 раз больше ворочалось всё это очень нехотя. А такие запросы нужно было сделать для каждого узла и VlanID. И выгрузить всё сразу и вычислить нельзя, т.к. это последовательное вычисление пути c с пошаговыми операциями, которые зависят от результатов предыдущего шага.

2.3. Определение пути сервиса в маршрутизируемых сегментах

Здесь мы начали с одного вендора МВН, система управления которого предоставляла данные о текущем и резервном LSP через сегмент MPLS. Зная Access интерфейс, который стыковался с доступом (L2 Vlan) можно было найти LSP а затем через серию запросов к NBI системы, получить путь LSP, состоящий из маршрутизаторов и линков между ними.

• Аналогично коммутируемому сегменту, описание выгрузки пути LSP MPLS сервиса вылилось в алгоритм с уже 17-ю подпрограммами.
• Решение работало только на сегментах, которые обслуживались данным вендором
• Нужно было решать определение стыков между сервисами MPLS (например, в центре сегмента был общий VPLS сервис, а от него расходились или EPIPE либо L3VPN)

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

Кроме этого, возникали дополнительные вопросы:

• Сеть МВН в общем случае мультивендорная, и на одном сегменте встречаются маршрутизаторы разных производителей, управляемых разными СУ. Т.е. у нас будут данные только о куске пути MPLS сервиса.
• СУ вендора, которая могла предоставлять данные об основном и резервном LSP, на деле прописывала и первый и второй по одному и тому же пути. Это мы видели очень часто. А нам бы хотелось знать про потенциальные пути обхода при анализе ограничений на сети.

2.4. Где и как хранить результаты. Как запрашивать данные

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

Вариант с хранением в реляционной БД сразу исключили: с таким трудом агрегировать данные из множества источников чтобы потом в итоге рассовать по очередным наборам таблиц? Это не наш метод. Тем более помним про многоэтажные джойны и их производительность.

Данные должны содержать информацию о структуре сервиса и зависимостях его составляющих: линках, узлах, портах и т.п.

В качестве тестового решения был выбран формат XML и Native-XML БД Exist.

Каждый сервис в результате записывался в БД в формате (подробности опущены для компактности записи):

<services><service> <id>,<description> Описание сервиса (например, наименование БС)<source> Интерфейс условной точки А<target> Интерфейс условной точки Z<<segment>> Сегменты L2/L3<topology> Информация о пути через сегмент (узлы, порты/интерфейсы, соединения)<<joints>> Стыки между сегментами (узлы, порты/интерфейсы, соединения)</service></services>

Запрос данных по прямой и обратной задачам выполнялся по протоколу XPath:


Всё. Теперь система заработала на запрос с наименованием БС возвращается топология проключения её через транспортную сеть, на запрос с наименованием узла и порта ТС возвращается список БС, которые от него зависят по подключению. Поэтому, выводы мы сделали следующие

2.5.

Вместо заголовка о выводах по части 2

2.5.1. Для коммутируемого сегмента (сети на L2 коммутаторах Ethernet)

• Обязательно нужны полные данные о топологии и соответствии Port VlanID. Если на каком-то линке нет данных о VlanID алгоритм останавливается, путь не найден
• Многоэтажные непроизводительные запросы к реляционной БД. При появлении нового вендора со своей спецификой параметрии добавление запросов на всех этапах работы

2.5.2. Для маршрутизируемого сегмента

• Ограничено возможностями СУ МВН по предоставлению данных о топологии LSP MPLS сервисов.
• Запросы конфигурации непосредственно с МВН потенциально опасны, т.к. счёт обслуживаемых LSP идет на тысячи.
• Резервные LSP часто прописываются системой по тому же маршруту что и основные нет информации о потенциальных альтернативных путях (в том числе и помимо тех, которые держит система).

2.5.3. Общее

• Чтобы решить, по сути, задачу в сетевом графе, мы постоянно собираем данные из табличных источников, чтобы представить их в виде графа ( визуально в голове, или в памяти программы), реализовать алгоритм, а потом разобрать обратно.
• Алгоритмизация решений и их реализация традиционными методами требует значительных трудозатрат. На реализацию данного этапа у нас ушло в целом 3-4 месяца.
• Масштабирование очень затруднено, т.к. любое изменение, в виде появления нового вендора либо MPLS сервиса ведёт за собой внесение изменений в структуру запросов к БД и в сам программный код.
• Приходится писать Дейкстра подобные алгоритмы, а не использовать готовые инструменты.

2.6. Чего всё-таки хотим

• Чтобы данные о сетевом графе ТС и хранились, и обрабатывались как сетевой граф, т.е. набор узлов и зависимостей.
• Чтобы использовались уже готовые алгоритмы работы с графами
• Чтобы модель данных была универсальной, а не вендорно-зависимой
• Чтобы трассировка была возможна и на неполных данных (например, частичное отсутствие данных о VlanID)

После того как мы провели оценку возможных вариантов реализации наших хотелок определились с классом систем, которые бы всё это обеспечили из коробки это т.н. графовые базы данных.

Хоть и читается последнее предложение как нечто линейное и простое, учитывая что ранее с таким классом БД никому из нас (и наших айтишников, как потом выяснилось тоже) сталкиваться не приходилось к решению пришли в некоторой степени случайно: подобные базы данных упоминались (но не разбирались) в обзорном курсе по Big Data. В частности, там упоминался продукт Neo4j. Мало того, что он, судя по описанию, удовлетворял всем нашим требованиям, у него ещё есть полностью бесплатная функциональная community-версия. Т.е. не 30-дневный триал, не обрезанный основной функционал, а полностью рабочий продукт, который можно не спеша изучить. Не последнюю (если не основную) роль в выборе сыграла широкая поддержка графовых алгоритмов.

---

Часть 3. Пример реализации прямой задачи в Neo4j

Чтобы не затягивать линейное повествование о том, как реализуется модель ТС в графовой БД Neo4j сразу покажем конечный результат на примере.

3.1. Трассировка пути проключения интерфейса Iub для БС 3G

Путь проключения сервиса проходит по двум сегментам маршрутизируемому МВН, и коммутируемому РРЛ (радиорелейные станции работают как Ethernet-коммутаторы). Путь через РРЛ сегмент определяется также, как было описано в части 2 по прохождению VlanID интерфейса БС по сегменту РРЛ до граничного маршрутизатора МВН. Сегмент МВН соединяет граничный (с сегментом РРЛ) маршрутизатор с маршрутизатором к которому подключен контроллер БС (RNC).

Изначально, из параметрии Iub, мы знаем точно какой МВН является шлюзом для БС (граничный МВН), и каким контроллером обслуживается БС.

Исходя из этих начальных условий, построим 2 запроса к БД для каждого из сегментов. Все запросы к БД строятся на языке Cypher. Чтобы сейчас не отвлекаться на его описание, воспринимайте его просто как SQL для графов.

3.1.1. Сегмент РРЛ. Путь по VlanID

Cypher-запрос трассировки пути сервиса по имеющимся данным о VlanID и топологии L2:

Как видно, путь получен, даже несмотря на частичный недостаток данных. В данном случае отсутствует информация о стыке порта БС с портом радиорелейной станции.

3.1.2. Сегмент РРЛ. Путь по L2 топологии

Допустим, попытка в п. 3.1.1. не удалась по причине полного или частичного отсутствия данных о параметрии VlanID. Другими словами подобная непрерывная цепочка, доходящая до узла МВН не выстраивается:

Тогда можно попробовать определить проключение сервиса как кратчайший путь до МВН по топологии L2:

Как видно, получен такой же результат. Здесь недостаток информации о стыке БС с РРС восполнен прохождением связи через объект (узел) площадки, на которой они находятся. Разумеется, точность такого метода будет меньше, т.к. в общем случае Vlan может быть прописан не по кратчайшему пути, предполагаемому алгоритмом Дейкстра. Зато запрос состоит из всего двух операций.

3.1.3 Сегмент МВН. Трассировка пути от граничного МВН до контроллера

Здесь так же используем алгоритм Дейкстра.

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

3.2. Трудозатраты

Реализация Прямой задачи, показанная сейчас, разительно отличается от подхода разработай алгоритм, программу, способ хранения и извлечения результатов здесь всё сводится к напиши запрос к БД. Забегая вперёд, отметим, что весь цикл от разработки простой модели графа, загрузки данных в Neo4j из реляционной БД, написания запросов, и до получения результата занял, в общей сложности, один день.

3-4 месяца vs 1 день!!! Это было последним доводом для окончательного ухода в графовую БД.

---

Часть 4. Графовая БД Neо4j и загрузка данных в неё

4.1. Сравнение реляционных и графовых БД

4.2. Модель данных

Базовая модель представления ТС до уровня L3 топологии включительно:


Разумеется, модель обширнее представленной, и содержит также и MPLS сервисы, и виртуальные интерфейсы, но для упрощения рассмотрим её ограниченный фрагмент.

В такой модели связь между двумя сетевыми элементами одного региона может быть представлена как:

4.3. Загрузка данных

Загрузку данных выполняем из БД параметрии и топологии ТС. Для загрузки в Neo4j из SQL БД используется библиотеки APOC apoc.load.jdbc, которая принимает на вход строку подключения к RDBMS и текст SQL запроса, и возвращает множество строк, которые через CYHPER выражения отображаются на узлы, связи, или параметры. Такие операции выполняются слой за слоем для каждого типа объектов модели.

Например, проход для загрузки/обновления узлов, представляющих сетевые элементы (Nodes):

И так далее по всем уровням модели ТС.

Поле Updated используется при контроле актуальности данных в графе не обновляемые дольше определенного периода объекты удаляются.

---

Часть 5. Решаем обратную задачу в Neo4j

Когда мы только начинали, выражение трассировка сервиса в первую очередь вызывало следующие ассоциации:


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

Это не совсем то, что мы имеем в графовой БД. В ГБД трассируется сервис по взаимосвязям объектов, определяющих его конфигурацию в каждом задействованном сетевом элементе. Т.е., в виде графовой модели представляется конфигурация, и результирующая трасса это проход по модели, представляющей эту конфигурацию.

Так как, в отличие от коммутируемого сегмента, фактические маршруты сервиса в сегменте mpls определяются динамическими протоколами, нам пришлось принять некоторые

5.1. Допущения для маршрутизируемых сегментов

Т.к. из данных конфигурации mpls сервисов нет возможности определить их точный путь прохождения через сегменты, управляемые динамическими протоколами маршрутизации (тем более, если используется Traffic Engineering) для решения используется алгоритм Дейкстры.
Да, есть системы управления, которые могут по NBI-интерфейсу предоставлять актуальный путь сервисных LSP, но пока у нас такой вендор только один, а вендоров на сегменте МВН больше чем один.

Да, есть системы анализа протоколов маршрутизации внутри AS, которые, слушая обмен IGP протоколов, могут определить текущий маршрут интересующего префикса. Но стоят такие системы как сбитый Боинг, а учитывая что такую систему нужно развернуть на всех AS того же мобильного бэкхола стоимость решения вместе со всеми лицензиями составит стоимость Боинга, сбитого чугунным мостом, привязанным к ракете Ангара при полной заправке. И это ещё при том что подобными системами не вполне решены задачи учета маршрутов через несколько AS c использованием BGP.

Поэтому пока так. Конечно, мы добавили несколько подпорок в условия стандартного алгоритма Дейкстра:

• Учёт статуса интерфейсов/портов. Отключенный линк повышается в стоимости и идет в конец возможных вариантов пути.
• Учёт резервного статуса линка. По данным системы Performance Monitoring вычисляется присутствие в mpls канала только трафика keepalive, соответственно, стоимость такого канала также увеличивается.

5.2. Как решить обратную задачу в Neo4j

Напоминание. Обратная задача получение списка сервисов, зависимых от конкретного канала или узла транспортной сети (ТС).

5.2.1. Коммутируемый L2 сегмент

Для коммутируемого сегмента, где путь сервиса и конфигурация сервиса это практически одно и то же, задачу ещё можно решить через CYPHER-запросы. Например, для радиолерейного пролета из результатов решения Прямой задачи в п 3.1.1., сделаем запрос от модема радиорелейного линка развернем все цепочки Vlan, которые проходят через него:

match (tn:node {name:'RRN_29_XXXX_1'})-->(tn_port:port {name:'Modem-1'})-->(tn_vlan:vlan)with tn, tn_vlan, tn_portcall apoc.path.spanningTree(tn_vlan,{relationshipFilter:"ptp_vlan>|v_ptp_vlan>", maxLevel:20}) yield path as ppwith tn_vlan,pp,nodes(pp)[-1] as last_node, tn_portmatch (last_node)-[:vlan]->(:port)-->(n:node)return pp, n, tn_port

Красным узлом обозначен модем, Vlan которого разворачиваем. Обведены 3 БС на которые в итоге вывело развертывание транзитных Vlan с Modem1.


У такого подхода есть несколько проблем:

• Для портов должны быть известны и загружены в модель сконфигурированные Vlan.
• Из-за возможного фрагментирования, цепочка Vlan не всегда выводит на терминальный узел
• Невозможно определить относится ли последний узел в цепочке Vlan к терминальному узлу или сервис, на самом деле, продолжается дальше.

То есть, сервис всегда удобнее трассировать между конечными узлами/точками его сегмента, а не из произвольной середины, и с одного уровня OSI.

5.2.2. Маршрутизируемый сегмент

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

5.3. Решение

Решение было принято следующее.

• Проводится полная загрузка модели ТС, включая БС и контроллеры
• Для всех БС выполняется решение прямой задачи трассировка сервисов Iub, S1 от БС до граничного МВН, а затем от граничного МВН до соответствующих контроллеров или шлюзов.
• Результаты трассировки записываются в обычную SQL БД в формате: Наименование БС массив элементов пути сервиса

Соответственно, при обращении к БД с уловием Узел ТС или Узел ТС + Порт, возвращается список сервисов (БС), в массиве пути которых есть нужный Узел или Узел+Порт.

---

Часть 6. Результаты и выводы

6.1. Результаты

В итоге система работает следующим образом:


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


Для получения списка сервисов, зависимых от узлов или каналов ТС (решение обратной задачи) разработан API для внешних систем (в частности Remedy).

6.2. Выводы

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

6.3. Планы

В планах у нас:

• расширение технологических сегментов, моделируемых в БД Neo4j
• разработка и внедрение алгоритмов трассировки сервисов ШПД
• увеличение производительности серверной платформы

Спасибо за внимание!