Федеральное государственное автономное образовательное учреждение
высшего образования
КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ
ВЫСШАЯ ШКОЛА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И
ИНФОРМАЦИОННЫХ СИСТЕМ
Направление подготовки: 09.03.03 Прикладная информатика
ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА
Разработка алгоритма поиска дешевых маршрутов для систем
бронирования авиабилетов
Работа завершена:
«___»_____________2017 г.
Студент группы 11-302
___________________М.А. Игнатьев
Работа допущена к защите:
Научный руководитель
Доцент кафедры программной инженерии
Высшей школы ИТИС
«___»_____________2017 г.
___________________И.Н. Голицына
Директор Высшей школы ИТИС
«___»_____________2017 г.
__________________ А.Ф. Хасьянов
Казань – 2017 г.
СОДЕРЖАНИЕ
СОДЕРЖАНИЕ
2
ТЕРМИНЫ И ОПРЕДЕЛЕНИЯ
3
ВВЕДЕНИЕ
4
Глава 1. ВЫБОР СИСТЕМЫ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ
6
1.1 Реляционная СУБД PostgreSQL
8
1.2 Документо-ориентированная СУБД MongoDB
9
1.3 Графовая СУБД Neo4j
11
1.4 Сравнение производительности выбранных СУБД
12
1.5 Анализ результатов
16
Глава 2. СТРУКТУРА РАЗРАБАТЫВАЕМОГО СЕРВИСА
19
2.1 Архитектура приложения
19
2.2 Структура базы данных
21
Глава 3. РАЗРАБОТКА ПРОГРАММНОЙ ЧАСТИ ПРИЛОЖЕНИЯ
3.1 Слой DAO
23
23
3.1.1 JCypherRepository
24
3.1.2 Neo4jDriverRepository
27
3.2 Наполнение базы данных
29
3.3 Поиск авиарейсов
31
3.3.1 Написание запроса Cypher
32
3.3.2 Разработка репозитория
34
3.4 Разработка публичного API
39
ЗАКЛЮЧЕНИЕ
43
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
44
2
ТЕРМИНЫ И ОПРЕДЕЛЕНИЯ
Sabre ®
SabreSonic
СУБД
DSL
API
Компания, предоставляющая ряд продуктов
и услуг для осуществления бронирования и
продажи авиабилетов, гостиниц, аренды
автомобилей.
SabreSonic Web. Система бронирования и
продажи авиабилетов, разрабатываемая
компанией Sabre.
Система управления базами данных.
Совокупность программных и
лингвистических средств общего или
специального назначения, обеспечивающих
управление созданием и использованием баз
данных.
Domain Specific Language. Язык или диалект
языка программирования,
специализированный для конкретной
области применения.
Application Programming Interface.
Программный интерфейс приложения.
Набор функций, предоставляемых
приложением для использования во внешних
программных продуктах.
3
ВВЕДЕНИЕ
В
настоящее
время
большая
часть
повседневных
процессов
автоматизирована. Хорошим примером подобной автоматизации являются
системы онлайн бронирований авиаперелетов. Они помогают клиентам искать
авиарейсы, указав лишь желаемые даты для путешествия, при этом оставляя
за собой выбор авиакомпании, основываясь на протяженности перелета,
количестве пересадок и цене билетов.
Основной проблемой подобных сервисов является тот факт, что у них
нет прямого доступа к списку всех авиарейсов. Эти данные хранятся у трех
крупных мировых компаний. Большинство российских предприятий для
получения информации об авиарейсах используют сервис SabreSonic1. Каждое
обращение к данному сервису авиакомпании оплачивают по заданным
тарифам, что, впоследствии, приводит к образованию наценок на авиабилеты.
Решение проблемы дорогостоящего поиска авиарейсов с увеличением
скорости поиска для авиакомпаний, предоставляющих подобные услуги для
пользователей, представляет собой актуальную задачу.
Следовательно, для того, чтобы создать систему быстрого, но в то же
время недорогого поиска авиарейсов, необходимо разработать подход,
существенно сокращающий количество обращений к SabreSonic, сохраняя при
этом высокие показатели скорости поиска.
Целью
дипломной работы
является разработка сервиса для поиска
авиарейсов, использующего подходы в хранении и получении информации
отличные от тех, что используются в современных авиакомпаниях.
Поиск авиарейсов должен производиться по максимально доступному
количеству параметров без утяжеления запросов к базе данных.
1
https://www.sabreairlinesolutions.com/
4
Разрабатываемый сервис должен предоставлять возможность для
доступа через программный интерфейс для легкого внедрения в уже
разработанные сайты и мобильные приложения,
На текущий
момент не существует общедоступных сервисов,
однозначно решающих данную проблему. Авиакомпании разрабатывают
подобные сервисы самостоятельно и не предусматривают их продажи
сторонним компаниям, т.к. это прямым образом влияет на прибыльность
предприятия.
Для достижения цели были решены следующие задачи:
1. Выбор максимально эффективной СУБД для использования в проекте
для поиска авиарейсов.
2. Разработка наиболее выгодного алгоритма для процедур получения
информации об авиарейсах и последующего поиска маршрутов.
3. Создание публичного API для взаимодействия с разработанным
сервисом сторонними клиентами.
В первой главе данной дипломной работе описана процедура выбора
СУБД
для
разрабатываемого
приложения.
Производится
сравнение
реляционных, документо-ориентированных и графовых систем управления
базами данных с последующим анализом производительности систем в
контексте поставленной задачи.
Во второй главе автор описывает архитектуру разрабатываемого
приложения. Обсуждается порядок взаимодействия компонентов системы, а
так же структура сущностей выбранной СУБД для последующей манипуляции
с данными.
В третьей главе дипломной работы описывается программная часть
приложения. Автор описывает основные моменты реализации каждого из
компонентов системы, а так же настройку их взаимодействия.
5
Глава 1. ВЫБОР СИСТЕМЫ УПРАВЛЕНИЯ БАЗАМИ
ДАННЫХ
Пожалуй, сердцем любого веб-приложения является его база данных.
Здесь хранятся важные бизнес-данные, представляющие наибольшую
ценность для разрабатываемого продукта.
От правильного выбора СУБД в большой мере будет зависеть
дальнейший процесс построения архитектуры приложения, так как разные
системы
отличаются
структурой
хранения
данных
и
алгоритмами
манипуляции с хранимой информацией. Рассмотрим три типа систем
управления базами данных:
1) Реляционные
В качестве реляционной СУБД была выбрана PostgreSQL2, которая занимает
лидирующее место среди бесплатных аналогов. На рис. 1 приведена таблица
популярности реляционных СУБД за 2016-2017гг.
Рис. 1. Рейтинг реляционных СУБД по версии http://db-engines.com/
2) NoSQL (документо-ориентированные) базы данных
Лидирующее место среди документно-ориентированных СУБД занимает
2
https://www.postgresql.org/
6
MongoDB3. На рис. 2 приведен рейтинг документо-ориентированных систем
управления базами данных.
Рис. 2. Рейтинг документо-ориентированных СУБД по версии http://db-engines.com/
3) Графовые базы данных
Самой популярной графовой базой данных, согласно рейтингу (рис. 3)
является Neo4j4.
Рис. 3. Рейтинг Графовых СУБД по версии http://db-engines.com/
3
4
https://www.mongodb.com/
https://neo4j.com/
7
1.1 Реляционная СУБД PostgreSQL
Реляционные системы управления базами данных появились очень
давно и на сегодняшний день используются в абсолютном большинстве
крупных проектов по разработке информационных систем.
Приведем пример решения поставленной задачи с использованием
реляционной СУБД PostgreSQL.
Создадим таблицы Airport(Аэропорт) и Flight(Авиаперелет) [1] с
помощью скрипта (рис. 4).
Рис 4. Скрипт для создания схемы PostgreSQL
Изобразим полученную структуру и отношения таблиц в виде схемы
(рис. 5):
Рис 5. Схема БД PostgreSQL.
8
1.2 Документо-ориентированная СУБД MongoDB
Документо-ориентированные СУБД предназначены для хранения
иерархических структур данных. Документные хранилища имеют структуру
дерева или леса. Структура дерева начинается с корневого узла и может
содержать несколько внутренних и листовых узлов. Такие базы данных
реализуют подход NoSQL5 (not only SQL), направленный на решение проблем
масштабируемости и доступности традиционных SQL СУБД.
Приведем пример решения поставленной задачи с использованием
документо-ориентированной СУБД MongoDB.
Для реализации данного примера может быть достаточно одной
коллекции документов – Flight(Авиаперелет), которая в свою очередь будет
содержать в себе данные об аэропортах внутри документов.
Пример команды для добавления рейса [2]:
db.flights.insert([{
departure: {code: "SVO"},
arrival: {code: "LED"},
departure_date: new ISODate("2017-02-8"),
arrival_date: new ISODate("2017-02-21"),
flight_number: 998
}])
Изобразим формат хранения данных MongoDB на рис. 6.
5
https://ru.wikipedia.org/wiki/NoSQL
9
Рис 6. Формат хранения данных MongoDB
10
1.3 Графовая СУБД Neo4j
Графовые системы управления базами данных предназначены для
хранения данных в виде графов. Такой подход в сравнении с построением
графовой
БД
средствами
реляционных
СУБД
позволяет
применять
дополнительные оптимизации в случае данных с более сложной структурой.
СУБД Neo4j предоставляет специальный язык запросов Cypher6 для
манипуляции с данными.
Например, следующей командой [3] можно добавить рейс МоскваКазань:
MATCH (a:AIRPORT{code:”SVO”}), (b:AIRPORT{code:”KZN}
CREATE ((a)-[f:FLIGHT{
departure_date: 61447237200000,
arrival_date: 61447323600000, flight_number: 0
}]->(b))
Изобразим структуру хранимых данных Neo4j в виде схемы (рис. 7).
Рис. 7. Граф перелетов между двумя городами.
6
https://neo4j.com/docs/developer-manual/current/cypher/
11
1.4 Сравнение производительности выбранных СУБД
Для сравнения производительности выбранных СУБД произведем
вставку 10000 случайных записей в базы данных PostgreSQL, MongoDB и
Neo4j.
Так же воспользуемся встроенными механизмами индексации данных,
для более быстрого поиска перелетов. Индексы построим по атрибутам «Дата
вылета» и «Дата прилёта»
PostgreSQL:
CREATE INDEX departure_index ON flight (departure_date);
CREATE INDEX arrival_index ON flight (arrival_date);
MongoDB:
db.flights.createIndex( { departure_date: 1 } )
db.flights.createIndex( { arrival_date: 1 } )
Neo4J:
CREATE INDEX ON :FLIGHT(departure_date)
CREATE INDEX ON :FLIGHT(arrival_date)
В качестве тестовых запросов будем использовать следующие примеры:
1) Выборка рейсов из аэропорта Шереметьево в аэропорт Пулково с 5
февраля по 7 февраля.
PostgreSQL:
SELECT
f.flight_number,
a.code,
f.departure_date,
12
b.code,
f.arrival_date
FROM flight f
JOIN airport a ON f.departure = a.id
JOIN airport b ON f.arrival = b.id
WHERE a.code = 'SVO' AND b.code = 'LED'
AND f.departure_date >= '2017-02-05' AND f.departure_date
< '2017-02-07';
MongoDB:
db.flights.find({
departure: {
code: "SVO"
},
arrival: {
code: "LED"
},
departure_date: {
$gte: ISODate("2017-02-05T00:00:00Z"),
$lt: ISODate("2017-02-07T00:00:00Z")
}
})
Neo4j:
MATCH
(a:Airport{code:"SVO"})
-[f:FLIGHT]->
(b:Airport{code: "LED"})
WHERE f.departure_date > 61446805200000
AND f.arrival_date < 61446978000000
RETURN f
2) Выборка рейсов из аэропорта Казань в аэропорт Пулково с
пересадкой в аэропорту Шереметьево, где дата вылета – 5 февраля и
13
пересадка займёт менее 2 суток.
PostgreSQL:
SELECT
f1.flight_number,
a.code,
f1.departure_date,
b.code,
f1.arrival_date,
f2.flight_number,
f2.departure_date,
c.code,
f2.departure_date - f1.arrival_date
FROM flight f1
JOIN airport a ON f1.departure = a.id
JOIN airport b ON f1.arrival = b.id
JOIN flight f2 ON f1.arrival = f2.departure AND
f2.departure_date >= f1.arrival_date
JOIN airport c ON f2.arrival = c.id
WHERE a.code = 'KZN' AND b.code = 'SVO' AND c.code = 'LED'
AND f1.departure_date = '2017-02-05'
AND f2.departure_date - f1.arrival_date
< 2;
MongoDB:
Данная СУБД не поддерживает механизм JOIN, а также возможность
выполнять подзапросы. Следовательно, данную выборку можно выполнить
только двумя отдельными запросами с серьезным перебором данных, что, в
свою очередь, нам не подходит.
Neo4j:
MATCH
(a:Airport{code:"KZN"})
-[f1:FLIGHT]->
(b:Airport{code: "SVO"})
-[f2:FLIGHT]->
14
(c:Airport{code: "LED"})
WHERE f1.departure_date > 61446805200000
AND f1.arrival_date < 61446991600000
AND f2.departure_date > f1.arrival_date
AND f2.departure_date - f1.arrival_date <= 86400000
RETURN f1, f2
Стоит отметить, что нам в данном случае не так важна скорость вставки
данных, нежели скорость выборки по заданным условиям.
15
1.5 Анализ результатов
Замерим скорость выполнения запросов. Все замеры будем проводить
на машине со следующими характеристиками:
ОС Ubuntu 14.04 x64
16GB RAM
Intel Core i5-3340 4x(3.10Ghz)
HDD Seagate ST500DM002
Полученные результаты:
Выполним описанные ранее запросы по 100 раз для каждой СУБД и
вычислим время выполнения запросов.
PostgreSQL
1) 10ms
2) 12ms
MongoDB
1) 6ms
2) Нет, т.к. выборку невозможно реализовать одним запросом
Neo4j
1) 4ms
2) 13ms
Изобразим полученные результаты в виде графика (рис. 8):
16
14
12
10
8
Query 1
6
Query 2
4
2
0
PostgreSQL
MongoDB
Neo4j
Рис. 8. График полученных результатов. Синий и красный цвет – среднее значение
времени выполнения 1-го и 2-го запросов соответственно.
Проведя анализ производительности выбранных СУБД, мы можем
сделать следующие выводы.
Документо-ориентированная СУБД MongoDB оказалась самой быстрой
для выполнения простых запросов, однако она совершенно не подходит для
сложных запросов, в которых подразумевается выполнение операций JOIN
или SUBSELECT.
Реляционная PostgreSQL и графовая Neo4j СУБД показали достойный
результат, поиск простого маршрута в графовой базе данных производится в
2,5 раза быстрее, чем в реляционной. Поиск сложного маршрута занимает
примерно одинаковое время в обеих СУБД.
Стоит отметить, что язык запросов Cypher, который используется в
Neo4j, в данном контексте гораздо проще для написания и понимания, что
способствует
более
высокой
скорости
разработки
и
поддержки
с
использованием графовой БД против реляционной базы данных.
При
разработке
программных
продуктов,
для
обеспечения
максимальной производительности, следует сочетать несколько подходов в
построении баз данных. Принимая во внимание, что графовая СУБД не может
17
являться единственной для использования в подобном проекте, так как не все
данные приложения можно представить в виде графов, здесь и далее в рамках
дипломной работы мы разберем работу именно с графовой системой
управления базами данных Neo4j.
18
Глава 2. СТРУКТУРА РАЗРАБАТЫВАЕМОГО СЕРВИСА
2.1 Архитектура приложения
Структура
разрабатываемого
приложения
состоит
из
следующих
компонентов:
1. База данных Neo4j - графовая база данных, хранит информацию об
авиарейсах и ценах для дальнейшего поиска.
2. Сервис для поиска авиарейсов - формирует запросы и производит
обращения в БД Neo4, преобразует полученные результаты в
необходимый формат.
3. Сервис для получения данных об авиарейсах - загружает информацию
об авиарейсах из SabreSonic, преобразует и сохраняет результаты в базу
данных.
4. API - слой веб-сервисов для предоставления программного интерфейса
для доступа к сервису поиска авиабилетов по протоколам SOAP и REST.
Сервис для получения данных об авиарейсах запрашивает информацию
об авиарейсах от системы SabreSonic. Полученная информация преобразуется
в графовое представление и сохраняется в базу данных Neo4j. Данный процесс
производится один раз в сутки, что позволяет существенно сократить затраты
на обращения к Sabre. Такой период выполнения выбран с учетом периода
обновления баз данных SabreSonic, который равен одному дню, т.е. более
частое обновление в данном случае не имеет смысла.
Обновление базы данных происходит в асинхронном режиме и не
требует приостановки работы сервиса.
Взаимодействие клиента с разрабатываемым сервисом предполагает
обращение к слою веб-сервисов (API). Далее запрос переходит к сервису
поиска авиабилетов, который, на основании полученных данных строит
19
запрос к базе данных Neo4j. Полученный результат трансформируется в
необходимый формат и передается клиенту.
Изобразим описанный порядок взаимодействия компонентов системы в
виде схемы (рис. 9).
Рис 9. Взаимодействие компонентов системы
20
2.2 Структура базы данных
В СУБД Neo4j используется механизм графового представления
документов. Все объекты в базе данных делятся на 2 типа: вершины (Node) и
отношения (Relationship). Каждый объект имеет свой тип. Как вершины, так и
отношения имеют первичные ключи (ID), а также дополнительный набор
полей и свойств в формате JSON7.
Для хранения информации об авиаперелетах нам понадобятся
следующие сущности:
● Аэропорт
(Airport)
-
хранит
информацию
об
аэропорте
вылета/прилета
● Рейс (Flight) - хранит информацию об авиарейсе
Сущность Flight в данном случае можно представить как отношение [4], а
Airport как вершину графа авиаперелетов. Получим следующую структуру:
(departure: Airport) - [f: Flight] -> (arrival: Airport)
Рис. 10. Отношение Airport-Flight
Иногда при покупке авиабилетов для пользователя не так важны
аэропорты вылета и(или) прилета, сколько города, в которых они
7
http://www.json.org/json-ru.html
21
расположены. Для реализации поиска рейсов с указанием городов создадим
дополнительно сущности:
● City - хранит информацию о городе вылета/прилета
● Located - хранит принадлежность аэропорта к определенному
городу
Обновленная структура сущностей теперь выглядит так:
(departureCity: City) <- [l: Located] - (departure: Airport) - [f: Flight] -> (arrival:
Airport) - [l: Located] -> (arrivalCity: City)
Рис. 11. Отношение City-Located-Airport-Flight
Таким образом, разработана структура сущностей для базы данных
Neo4j, которая будет использована в дальнейшем для хранения информации
об авиарейсах и осуществления поиска маршрутов.
22
Глава 3. РАЗРАБОТКА ПРОГРАММНОЙ ЧАСТИ
ПРИЛОЖЕНИЯ
3.1 Слой DAO
Существует несколько способов для доступа к базе данных Neo4j с
помощью программных средств, наиболее распространенными из них
являются:
● Использование Neo4j REST API
● Подключение через Neo4j Java driver
● Реализация нативного Neo4j Java API
● Использование библиотеки JCypher
● Использование библиотеки Spring Data Neo4j
Для получения наиболее высокой скорости выполнения запросов с
сохранением удобства написания и читаемости кода был разработан подход,
комбинирующий доступ к БД Neo4j как посредством драйвера Neo4j Java
Driver, так и с помощью библиотеки открытого стека JCypher.
Реализованы два абстрактных класса-репозитория: JCypherRepository и
Neo4jDriverRepository.
23
3.1.1 JCypherRepository
JCypherRepository<T> - абстрактный класс-репозиторий для доступа к
БД Neo4j посредством библиотеки JCypher. Структуру класса можно
изобразить в виде схемы (рис. 12).
Рис. 12. Класс JCypherRepository
Ключевой особенностью библиотеки JCypher является возможность
использования встроенного DSL для построения запросов на языке Cypher, а
также встроенный механизм для маппинга объектов Neo4j в доменные Java
объекты.
Порядок
взаимодействия
изобразить на схеме (рис. 13).
24
компонентов
библиотеки
можно
Рис. 13. Структура взаимодействия JCypher
В качестве контекста для подключения к Neo4J JCypher использует
объект IDBAccess.
@Bean
public IDBAccess idba() {
Properties props = new Properties();
props.setProperty(DBProperties.SERVER_ROOT_URI, boltUrl);
AuthToken authToken = AuthTokens.basic(login, password);
return DBAccessFactory.createDBAccess(DBType.REMOTE, props,
authToken);
}
Далее, необходимо создать объект класса IDomainAccess. Данный
объект будет хранить информацию о контексте подключения, а также о типе
сущности Neo4j для последующего маппинга полей. Для этого, определим
аннотацию @Neo4jEntity. Классы, помеченные данной аннотацией, будут
считаться сущностями для маппинга с помощью JCypher.
После
инициализации
репозитория
воспользуемся
классом
GenerycTypeResolver [5], поставляемым с фреймворком Spring8, для
8
http://spring.io/
25
определения класса, переданного в репозиторий посредством механизма Java
Generics, и последующей инициализации объекта IDomainAccess (рис. 14).
Рис. 14. Инициализация IDomainAccess
Описанные
выше
действия
позволяют
нам
автоматически
инициализировать контекст для доступа к БД Neo4j посредством DSL JCypher.
Для этого воспользуемся следующими методами:
● query() - Данный метод создает объект DomainQuery, который
впоследствии может быть использован для выполнения запроса к
базе данных.
● match(query) - Метод принимает на вход созданный ранее объект
DomainQuery
и
создает
на
основе
него
объект
класса
DomainObjectMatch, который служит для построения запросов к
базе данных с использованием JCypher DSL.
26
3.1.2 Neo4jDriverRepository
Neo4jDriverRepository - абстрактный класс-репозиторий для доступа к
БД Neo4j посредством библиотеки JCypher. Изобразим структуру класса в
виде схемы (рис. 15).
Рис. 15. Класс Neo4jDriverRepository
Как можно понять из названия, данный класс использует для доступа к
базе данных нативный драйвер Neo4j [6]. Работа с драйвером Neo4j похожа на
работу с реляционными базами данных посредством драйвера JDBC9 и в
общем случае сводится к использованию объектов трех типов:
● Driver - объект для получения соединения с БД.
● Session - объект, представляющий сеанс взаимодействия с БД.
● StatementResult - объект-результат выполнения запроса на языке
Cypher.
Для работы с сессиями и запросами создан класс Neo4jStatement (рис. 16).
9
http://www.oracle.com/technetwork/java/javase/jdbc/index.html
27
Рис. 16. Класс Neo4jStatement
Данный класс содержит 1 метод - execute, который принимает на вход
функцию
Function<Session,
StatementResult>.
После
вызова
метода,
открывается сеанс взаимодействия с базой данных, выполняется переданная
функция и возвращается ее результат, после чего сессия автоматически
закрывается в методе close.
Класс Neo4jDriverRepository содержит два метода: executeQuery и
executeUpdate. Оба метода принимают на вход строку-запрос на языке Cypher,
а также массив параметров для данного запроса.
Метод executeQuery выполняет запрос с переданными параметрами и
возвращает объект класса StatementResult.
Метод executeUpdate аналогичен методу executeQuery, но выполняет
запрос в рамках транзакции.
28
3.2 Наполнение базы данных
Опишем процедуру наполнения базы данных. Класс SabreServiceImpl
(рис. 17) получает список всех авиарейсов, доступных авиакомпании, за
определенные даты.
Рис 17. Интерфейс SabreService
После чего происходит парсинг полученных данных и сохранение в базу
данных. Для сохранения рейса в базу данных используется метод createFlight
репозитория FlightRepositoryImpl (рис. 18).
Рис. 18. Сохранение рейса в БД
Стоит обратить внимание, что при записи рейса в базу данных
используется ключевое слово MERGE, а не CREATE, что позволяет избежать
дублирующихся записей в случае, если данный рейс уже находился в БД.
Процедура записи рейсов происходит асинхронно и выполняется
каждый день. Для организации выполнения асинхронных задач был
использован фреймворк Quartz10.
Класс SabreJob (рис. 19) реализует интерфейс Job и представляет собой
объект, описывающий задачу Quartz.
10
http://www.quartz-scheduler.org/
29
Рис. 19. Класс SabreJob
Для настройки выполнения задач Quartz в контексте приложения, был
использован специальный класс, входящий в состав фреймворка Spring JobDetailFactoryBean. Настройка объекта данного класса изображена на
рисунке (рис. 20).
Рис 20. Настройка фабрики задач для SabreJob
30
3.3 Поиск авиарейсов
Определим список критериев, по которым будет осуществляться поиск
авиарейсов:
1. Аэропорт(Город) вылета
2. Аэропорт(Город) прилета
3. Дата вылета
4. Максимальное количество пересадок
5. Минимальное время между пересадками
6. Минимальная стоимость перелета
7. Максимальная стоимость перелета
Полученные результаты должны быть отсортированы по одному из
следующих критериев:
1. Общая стоимость перелета
2. Общая продолжительность перелета
3. Количество пересадок
31
3.3.1 Написание запроса Cypher
В общем виде, запрос на поиск всех путей между двумя аэропортами
выглядит следующим образом:
MATCH (a:Airport{code:'SVO'})-[route:Flight*..3]->(b:Airport{code:'LED'}) RETURN route
В данном случае происходит поиск всех маршрутов между аэропортами
Шереметьево и Пулково, где длина пути не более 3 (не более 2 пересадок). К
сожалению, данный запрос учитывает также циклические пути, например,
SVO->LED->SVO->LED. Формально, данный маршрут является валидным
относительно поставленной задачи. Однако, следует исключить подобные
результаты из выборки. Для этого воспользуемся алгоритмом для поиска
только простых путей [7] (путей, где каждая вершина графа встречается не
более 1 раза) в графе. Данный алгоритм уже реализован в дополнительном
наборе функций Neo4j и распространяется в пакете “apoc.algo”11 под именем
allSimplePaths.
Функция allSimplePaths принимает 4 параметра: стартовая вершина,
конечная вершина, отношение и направление, максимальное количество ребер
в пути. Применим данный алгоритм для нашего запроса:
MATCH (from:Airport{code:'SVO'}),(to:Airport{code:'LED'})
CALL apoc.algo.allSimplePaths(from,to,'Flight>',3) YIELD path AS route
RETURN route
Для каждого пути посчитаем его стоимость и продолжительность. Для
этого воспользуемся функциями rels(для получения списка отношений в пути)
и reduce(функция свертки):
11
https://github.com/neo4j-contrib/neo4j-apoc-procedures
32
reduce(cost = 0, f in rels(route) | cost + f.cost) AS cost,
(rels(route)[length(rels(route))-1].arrivalDate - rels(route)[0].departureDate) AS duration,
rels(route) AS flights
Добавим условия в запрос. Первый вылет должен быть совершен в
определенную дату:
WHERE (length(flights) > 0)
AND (flights[0].departureDate >= 1495654020180)
AND (flights[0].departureDate < 1495654020180 + 86400000)
Каждый рейс должен быть позже предыдущего, разница между
временем прилета рейса и временем вылета следующего за ним рейса должна
быть больше заданного значения:
((length(flights) = 1) OR all(p in apoc.coll.pairs(flights)
WHERE p[1].departureDate > p[0].arrivalDate + (30* 60000)))
Запишем запрос целиком, с сортировкой по количеству пересадок (ребер
в пути):
MATCH (from:Airport{code:'SVO'}),(to:Airport{code:'LED'})
CALL apoc.algo.allSimplePaths(from,to,'Flight>',3) YIELD path AS route
WITH route, rels(route) AS flights,
reduce(cost = 0, f in rels(route) | cost + f.cost) AS cost, (rels(route)[length(rels(route))1].arrivalDate - rels(route)[0].departureDate) AS duration
WHERE (length(flights) > 0) AND (flights[0].departureDate >= 1495654020180)
AND (flights[0].departureDate < 1495654020180 + 86400000)
AND ((length(flights) = 1) OR all(p in apoc.coll.pairs(flights)
WHERE p[1].departureDate > p[0].arrivalDate + (30* 60000)))
AND cost >= 1000 AND cost <= 6000 AND duration < 20000000
RETURN flights, cost, duration
ORDER BY length(flights)
33
3.3.2 Разработка репозитория
Для
реализации
репозитория,
создадим
метод,
принимающий
следующие параметры:
● String departureAirport - код аэропорта вылета
● String arrivalAirport - код аэропорта прилета
● long date - дата вылета (мс)
● int maxFlightCount - максимальное кол-во сегментов
● int minPause - минимальное время межд пересадками
● int minCost - минимальная стоимость перелета
● int maxCost - максимальная стоимость перелета
● int maxDuration - максимальная длительность перелета
● String sorting - сортировка результатов
Рис 21. Интерфейс FlightRepository
Метод будет возвращать список объектов класса Route (рис. 22),
представляющих собой маршруты перелетов.
Рис 22. Классы Route, Flight и Airport
34
Для выполнения полученного ранее запроса Cypher из среды
выполнения Java, имплементируем класс Neo4jDriverRepository. Изобразим
полученную структуру классов в виде схемы (рис. 23).
Рис 23. реализация FlightRepositoryImpl.
В СУБД Neo4j включен встроенный механизм кэширования запросов,
т.е. план выполнения запроса не будет генерироваться при каждом обращении
к базе данных, что, в свою очередь, ускорит обработку запросов. Для
использования данного механизма, используется специальный синтаксис, где
знаком $(доллар) помечаются части запроса, которые являются переменными
параметрами, например:
MATCH (from:Airport{code:$dep}),(to:Airport{code:$arr})
Исправим разработанный запрос согласно приведенному синтаксису и
вызовем метод executeQuery класса Neo4jDriverRepository:
35
Optional<StatementResult> result = executeQuery(query,
"dep", departureAirport,
"arr", arrivalAirport,
"sort", sorting,
"cnt", maxFlightCount,
"minPause", minPause,
"minCost", minCost,
"maxCost", maxCost,
"maxDur", maxDuration,
"date", date);
Данный метод возвращает объект StatementResult. Вызвав метод list()
данного класса, можно получить список записей (Record), возвращенных
данным запросом. Напишем функцию-трансформер для преобразования
объектов Record в объекты Route.
@Component
@Scope("singleton")
public class RouteTransformer implements Function<Record, Route> {
@Autowired
private FlightTransformer flightTransformer;
@Override
public Route apply(Record record) {
Route route = new Route();
route.setTotalCost(record.get("cost").asInt());
route.setTotalDuration(record.get("duration").asInt());
record.get("route").asPath().forEach(segment ->
route.getFlights().add(flightTransformer.apply(segment)));
return route;
}
}
Разработанный запрос возвращает три объекта: cost, duration и route.
Типы объектов cost и duration - простые и содержат в себе числовые значения,
36
однако route представляет собой объект класса Path(Путь), хранящий в себе
список сегментов (Segment), которые в нашем случае представляют собой ни
что иное, как авиарейсы. Напишем ещё одну функцию-трансформер для
преобразования объектов Segment в объекты Flight:
@Component
@Scope("singleton")
public class FlightTransformer implements Function<Path.Segment, Flight> {
@Autowired
private AirportTransformer airportTransformer;
@Override
public Flight apply(Path.Segment segment) {
Flight flight = new Flight();
flight.setDeparture(airportTransformer.apply(segment.start()));
flight.setArrival(airportTransformer.apply(segment.end()));
Relationship relationship = segment.relationship();
flight.setCost(relationship.get("cost").asInt());
flight.setDuration(relationship.get("duration").asInt());
flight.setDepartureDate(new Date(relationship.get("departureDate").asLong()));
flight.setArrivalDate(new Date(relationship.get("arrivalDate").asLong()));
return flight;
}
}
Каждый сегмент хранит в себе ссылки на две вершины (Node) начальную и конечную. Получить доступ к этим вершинам можно,
соответственно вызвав метод start() или end() у объекта-сегмента. Данные
вершины в нашем случае представляют собой аэропорты вылета и прилета.
Напишем заключающую функцию-трансформер для преобразования объектов
Node в объекты Airport:
37
@Component
@Scope("singleton")
public class AirportTransformer implements Function<Node, Airport> {
@Override
public Airport apply(Node node) {
Airport airport = new Airport();
airport.setCode(node.get("code").asString());
airport.setName(node.get("name").asString());
return airport;
}
}
Таким
образом,
осуществления
поиска
разработан
необходимый
авиарейсов
и
набор
последующей
классов
для
трансформации
результатов. Программный код данных классов полностью представлен в
приложении № 1.
38
3.4 Разработка публичного API
Пожалуй, самая простая в реализации, но, тем не менее, очень важная
часть приложения - это его публичное API. С помощью него сторонние
сервисы, такие как веб-клиенты, настольные и мобильные приложения, смогут
использовать разработанный сервис для поиска авиарейсов.
Существует два основных подхода к разработке веб-сервисов - REST12 и
SOAP13 . Подход REST отличается простотой разработки и использования, в
то время как SOAP предоставляет больше возможностей для кастомизации и
ограничений безопасности. В рамках данной работы мы не будем разбирать
принципиальные
различия
между
данными
подходами,
однако
для
приложения подобного класса важно реализовать как REST, так и SOAP вебсервисы.
Создадим класс RouteSearchForm (рис. 24). Он будет использоваться в
качестве DTO для обоих веб-сервисов.
Рис 24. Класс RouteSearchForm
12
13
http://www.service-architecture.com/articles/web-services/representational_state_transfer_rest.html
http://www.service-architecture.com/articles/web-services/soap.html
39
Для разработки REST API воспользуемся средствами фреймворка
Spring. Создадим следующий контроллер:
@RestController
@RequestMapping("/routes")
public class RoutesController {
@Autowired
RouteService routeService;
@RequestMapping(method = RequestMethod.POST)
public List<Route> findRoutes(@RequestBody RouteSearchForm form) {
return routeService.findRoutesOneWay(form);
}
}
Отметим класс аннотацией @RestController, а входящий параметр form
аннотацией @RequestBody. Фреймворк Spring автоматически преобразует
тело запроса HTTP в формате JSON в объект класса RouteSearchForm.
Результат из класса Route будет трансформирован в тело ответа в формате
JSON и возвращен клиенту. В качестве трансформатора объектов Spring
использует библиотеку Jackson14, которая позволяет осуществлять маппинг
Java-объектов в форматы JSON и XML и обратно.
В общем случае маппинг происходит автоматически, однако, некоторые
типы полей, такие как дата, время, перечисления и т.п. требуют
дополнительной настройки с помощью аннотаций Jackson (рис. 25, 26).
14
https://github.com/FasterXML/jackson
40
Рис 25. Класс RouteSearchForm
Рис 26. enum RouteSortingMode
Для реализации SOAP веб-сервиса используем библиотеку Apache CXF,
так как она позволяет без особого труда интегрировать сервисы в контекст
фреймворка Spring, что невозможно сделать с использованием Java Servlet
API. Настроим endpoint [8]:
<jaxws:endpoint
id="RouteService"
implementor="ru.ignatyev.ws.WSRouteService"
address="/RouteService">
</jaxws:endpoint>
41
И реализуем сервис:
@WebService(name = "RouteService", serviceName = "PersonsService", portName =
"RouteServicePort")
@SOAPBinding(style = SOAPBinding.Style.RPC)
public class WSRouteService {
@Autowired
RouteService routeService;
@WebMethod(operationName = "findRoutes")
@WebResult(partName = "Route", name = "Route")
public List<Route> findRoutes(RouteSearchForm form) {
return routeService.findRoutesOneWay(form);
}
}
На этом разработку публичного API будем считать завершенной.
Полный листинг разработанных веб-сервисов представлен в приложении №1.
42
ЗАКЛЮЧЕНИЕ
В дипломной работе рассмотрена важная проблема большинства
авиакомпаний - дорогостоящая поддержка систем поиска авиарейсов.
Решение данной проблемы нацелено в первую очередь на помощь
авиакомпаниям, однако высокая скорость поиска важна также и для
пользователей систем подобного класса.
Результатом работы является готовый к использованию сервис, который
отвечает следующим требованиям:
1. Возможность
поиска
авиарейсов
по
широкому
спектру
параметров.
2. Поддержание высокой скорости поиска
3. Уменьшение количества обращений к Sabre
4. Возможность работы при отказе систем Sabre
Использованное
решение
существенно
сокращает
количество
обращений к базам данных SabreSonic, что позволяет авиакомпании
уменьшить затраты на обслуживание систем поиска авиарейсов.
Использование графовой БД дало сильный прирост к скорости выборки
данных по сравнению с реляционными базами данных, в то же время сохраняя
простоту разработки и поддержки программных средств для доступа к БД.
Описанное решение протестировано на тестовых данных авиакомпании
и сейчас находится на стадии внедрения в существующие механизмы поиска.
В данной работе были использованы передовые технологии открытого
стека Java: Spring Framework, Neo4j, Quartz, JAX-WS, Apache CXF, Tomcat 8.
Данные технологии обеспечивают кроссплатформенную совместимость.
43
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Официальная документация PostgreSQL [Электронный ресурс] /
The PostgreSQL Global Development Group, 2017. - Режим
доступа: https://www.postgresql.org/docs/9.5/static/index.html,
свободный - Яз. англ.
2. Официальная документация MongoDB [Электронный ресурс] /
MongoDB, Inc, 2017. - Режим доступа:
https://docs.mongodb.com/manual/, свободный - Яз. англ.
3. Официальная документация Neo4j [Электронный ресурс] / Neo
Technology, Inc., 2017. - Режим доступа: https://neo4j.com/docs/,
свободный - Яз. англ
4. Касьянов В. Н. Графы в программировании: обработка,
визуализация и применение / В.Н. Касьянов, В.А. Евстигнеев БХВ-Петербург, 2003. — 1104с
5. Walls C. Spring in Action / C. Walls - Manning, 2014. - 624c
6. Robison I. Graph Databases /I. Robison, J. Webber, E. Eifrem. –
O’Relly, 2013. -224c
7. Оре О. Теория графов /О. Оре - Либроком, 2009. - 354с
8. Vora D. Java 7 JAX-WS Web Services /D. Vora - Packt Publishing,
2012. - 64с
44
