Суть задачи и этапы ее решения

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

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

Вид со стороны пользователя

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

Сценарий работы пользователя (человека) с системой состоит в следующем:

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

Примерами команд могут быть:

FIND FROM "Moscow" TO "Barcelona" DURATION < 48H AND LEGS <= 3 AND AIRLINE IN ("AirFrance", "Iberia") END
PRINT ID, LEGNO, FROM, AIRLINE, TO, TIME ORDER ID, LEGNO END
ADD FLIGHT FROM="Moscow" TO="Berlin" AIRLINE="Aeroflot" DEPARTURE="12:30" DURATION="3:10" END

Первый запрос просит найти все варианты перелетов из Москвы в Барселону, которые потребуют не более 48 часов в пути и двух пересадок (или трех сегментов), и будут выполняться только компаниями Iberia или Airfrance. Второй запрос распечатывает найденные варианты. Здесь перечисляются имена полей, которые необходимо вывести, а также порядок сортировки строк. Третий — добавляет информацию о новом рейсе (мы рассматриваем упрощенную задачу, в частности, рейсы выполняются ежедневно).

Результатом выполнения второй команды может быть таблица вида

1  1  Moscow          AirFrance  Paris           09:40
1  2  Paris           AirFrance  Barcelona       14:20
2  1  Moscow          AirFrance  Paris           09:40
2  2  Paris           AirFrance  Rio de Janeiro  13:10
2  3  Rio de Janeiro  Iberia     Barcelona       23:45

Первый столбец является номером варианта перелета, второй — порядковым номером рейса в рамках этого варианта (вариант 1 с одной стыковкой в Париже, вариант 2 со стыковкам в Париже и Рио-де-Жанейро). Далее идут город вылета, авиакомпания, город прилета и время вылета.

Для пользователя это все. Он вводит команду (хочу в Барселону) на относительно простом формальном языке и получает ответ в заданной форме. Желательно быстро (в плане времени обработки запроса; увидев возможность перелета через Рио пользователь может выбрать именно этот, далеко не самый короткий маршрут, но это лежит за рамками разработки системы).

Клиент-серверная архитектура

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

На самом верхнем уровне можно выделить:

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

В клиент-серверной архитектуре (которая неявно была выбрана при описании сценария работы с системой) программа-клиент должна быть максимально простой. Задачей клиента является ввод запросов от пользователя, передача запроса на сервер, получение и вывод результата выполнения запроса. Вся содержательная обработка выполняется на стороне сервера. Клиенты могут отличаться формой представления результатов. Одна программа может выводить разультаты в виде текста, другая — в виде HTML таблицы, третья — в виде документа LaTeX, и т.д. В любом случае это не выглядит пугающе сложно: достаточно уметь считывать и печатать строчки (еще потребуется передавать данные по сети, но это, как мы увидим позже, не намного сложнее записи данных в файл).

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

Можем ли мы реализовать программу-клиент, если еще не знаем, как будет устроен сервер? Да, если мы определим протокол передачи данных между клиентом и сервером (что и в какой последовательности будет передаваться между этими программами по каналу связи). Наличие протокола является важным шагом на пути разделения сложной системы на части и обеспечивает заменяемость этих частей. Например, протокол IMAP позволяет позволяет почтовому клиенту получать электронную почту с сервера, независимо от того, кто этот сервер разработал. Нам наличие пртокола позволит смотреть на сервер как на черный ящик. Его реализация может быть прстой или очень сложной, но независимо от этого мы знаем как с ним нужно общаться. Кроме того, наличие протокола позволит разрабатывать новые виды клиентов (например, который выводит данные в виде файла PDF) без изменения исходного кода сервера.

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

Не углубляясь в детали, рассмотрим возможную схему такого протокола на примере обработки последовательности двух команд: FIND FROM "Moscow" TO "Paris" LEGS = 1 END (найти прямые рейсы из Москвы в Париж) и PRINT FROM, FROM, TO END (распечатать результаты поиска, повторив город вылета дважды).

Клиент является инициатором каждой операции и с его стороны все сообщения имеют вид "команда, которую ввел пользователь". Поскольку клиент максимально прост, то команда — это просто строка в том виде, как ее ввел пользователь. Результатом выполнения команды может быть либо сообщение об успехе (спасибо, данные о новом рейсе добавлены), либо данные (Вы можете долететь до Барселоны следующими рейсами), либо сообщение об ошибке (Вы вот сейчас что ввели? Такой команды нет.) Зафиксируем некоторые кодовые значения статуса обработки запроса. Например, 0 - команда выполнена успешно, 1 - была выполнена команда PRINT, далее будут отправлены результаты, 2 - команда содержала ошибку, далее передается текст ошибки, и т.д. Тогда сервер сначала отправляет значение статуса, а потом, если это необходимо, дополнительную информацию. Получатель (программа-клиент) знает, что означает тот или иной код статуса и может определить, что сервер должен передать в следующем сообщении (и должен ли он что-то передавать).

Клиент                             Сервер
-->  42            // длина команды FIND, sizeof(int) байт
-->  FIND FROM ... // первая команда, строка 42 байта
<--  0             // статус, sizeof(int) байт. значение 0 = выполнено

-->  24            // длина команды PRINT ... END
-->  PRINT ...     // строка "PRINT FROM, FROM, TO END", 24 байта
<--  1             // статус. 1 = "Была выполнена команда PRINT. Передаю данные!"
                   // Передаем описание таблицы. Сколько будет столбцов,
                   // какого они типа (например, 1 - строка, 2 - целое и т.д.)
                   // и как они называются
<--  3             // число столбцов (FROM, FROM, TO)
<--  1             // тип первого столбца
<--  4             // длина названия столбца
<--  FROM          // байты названия столбца
<--  1             // тип второго столбца
<--  4             // длина названия столбца
<--  FROM          // байты названия столбца
<--  1             // тип третьего столбца
<--  2             // длина названия столбца
<--  TO            // байты названия столбца
                   // ** конец описания таблицы **
<--  1             // количество строк ответа. Пусть найден один вариант
<--  6             // Длина города FROM
<--  Moscow        // Название города FROM
<--  6             // Длина города FROM (еще раз, мы просили PRINT FROM, FROM)
<--  Moscow        // Название города FROM
<--  5             // Длина города TO
<--  Paris         // Название города (5 байт)

Пусть sizeof(int) равно 4. Сначала клиент посылает 46 = 4+42 байт, которые содержат двоичное представление длины текста запроса и текст запроса. В ответ передается 4 байта статуса. На этом обработка перавой команды завершается. Далее клиент отправляет 28 = 4+24 байт второй команды. В ответ приходит 75 байт, которые логически можно представить в виде следующей последовательности:

<статус> <описание заголовка> <число строк таблицы> <данные первой строки>

Описание заголовка таблицы, формируемой командой PRINT, и данные строк этой таблицы являются сообщениями со своей внутренней структурой.

При проектировании и реализации протокола необходимо гарантировать, что оба участника всегда будут находяться в "согласованных" состояниях. Если, например, клиент получил сообщение со статусом 1 (был PRINT, передаю данные), а сервер неожиданно перешел в состояние ожидания следующей команды от клиента, не передав клиенту никаких данных, то система находится в тупиковой ситуации: клиент ничего не отправит, до тех пор пока не получит от сервера сообщение с данными, а сервер уже ничего не собирается отправлять, но готов обработать следующую команду (которая никогда не поступит).

Сервер

Разработка сервера является самой сложной и трудоемкой частью задачи. Для достижения цели необходимо:

опеределить схему данных (какая информация будет храниться в системе);
опеределить структуры данных, которые будут использоваться для хранения данных в оперативной памяти;
опеределить типы запросов;
составить грамматику языка запросов;
реализовать синтаксический анализатор для языка запросов;
реализовать систему выполнения запросов;
определить структуру индексов, которые будут использоваться для ускорения выполнения некоторых, в идеале — наиболее распространенных, запросов.

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

Схема данных

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

название   тип      комментарий
FROM       STRING   название города вылета
TO         STRING   название города назначения
AIRLINE    STRING   название авиакомпании
DEPARTURE  INTEGER  время вылета. в минутах
DURATION   INTGER   время полета. в минутах

(При реализации реальных систем следует создать отдельные таблицы для городов и авиакомпаний.)

Типы запросов и их синтаксис

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

Добавление рейса: ADD FLIGHT TO="куда" FROM="откуда" DURATION="2:30" TIME="12:30" AIRLINE="KLM" END

Команда имеет вид ADD FLIGHT, после чего перечисляются пары название поля/значение в произвольном порядке. Слово END заканчивает запрос. Заметим, что время указывается в виде, удобным для человека.
Поиск рейса: SELECT FROM="Moscow" DURATION < "3:40" TIME > "16:00" END

Команда имеет вид SELECT, после чего перечисляются условия поиска в виде название поля, отношение, значение. Слово END заканчивает запрос. Все условия объединяются неявным логическим И. Могут использоваться "естественные" отношения. В приведенном примере выбираются все "короткие" рейсы из Москвы после 16 часов. Имя поля может встречаться несколько раз. Например, TIME > "10:00" TIME < "12:00".
Удаление рейса: DELETE FROM="откуда" DURATION < "3:40" TIME > "16:00" END

Аналогично SELECT. Удаляются все рейсы, которые подходят под условие поиска.
Изменение рейса: UPDATE SET AIRLINE="KLM" WHERE AIRLINE="AirFrance" TO="Amsterdam" END

Аналогично SELECT. Для всех записей, которые подходят под условие поиска, изменяется значение указанного атрибута. В примере у всех рейсов авиакомпании AirFrance в Амстердам название компании меняется на KLM.
Поиск маршрута: FIND AIRLINE="AirFrance" FROM="Moscow" LEGS=3 END

Поиск сложного маршрута. В дополнение к ограничениям на отдельные поля, аналогичных команде SELECT, может использоваться ограниеничение LEGS на число сегментов.

Структуры данных для хранения данных в памяти

Информация о рейсе естественным образом представляется в виде структуры:

struct FlightInfo {
    std::string from;
    std::string to;
    std::string airline;
    unsigned int departure;
    unsigned int duration;
};

Все записи заносятся в односвязый список:

typedef std::list<FlightInfo> Flights;
Flights all_flights;

Синтаксический анализ запроса

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

Заметим, что команды имеют много общего. У команды есть название. условия поиска в виде поле/отношение/константа и т.п. В результате синтаксического анализа будем создавать структуры такого вида.

typedef enum {ADD, SELECT, DELETE, UPDATE, FIND} CommandType;
typedef enum { FROM, TO, TIME, DURATION, AIRLINE } Field;
typedef enum { GT, LT, EQUAL, IN } Relation;
struct Cond { // Одно условие вида поле/отношение/константа
    Field field;
    Relation relation;
    union {
      int i;
      std::string s;
      double d;
    } value; // Значение константы
};
typedef std::list<Cond> SearchConditions;
struct Command {
    CommandType cmd;
    SearchConditions conditions;
};

Command parse(const std::string& query);

В случае обнаружения синтаксической ошибки функция parse может создавать исключительную ситуацию.

Проверка соответсвия рейса условиям поиска

Для выполнения "простых" запросов по работе с рейсами (кроме FIND) реализуем функцию

bool match(const FlightInfo& flight, const SearchConditions& sc);

которая проверяет, что заданная запись о рейсе соответсвует условиям поиска.

Выполнение запросов: последовательный поиск

void process_command(const Flights& all_flights, const Command& command) {
    for(Flights::const_iterator i = all_flights.begin();
        i != all_flights.end();
        i++) 
    {
        if( match(*i, command.conditions) ) {
            std::cout << "Flight " << i->from << "-" << i->to << " match!" << std::endl;
        }
    }
}

Быстрое выполнение запросов: индексы

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

std::map< std::string, std::list<FlightInfo*> > by_airline;
// Разбиение на группы
for(Flights::const_iterator i = all_flights.begin(); i != all_flights.end(); i++) {
    by_airlines[i->airline].push_back(&(*i));
}

Теперь, в случае поступления запроса, который содержит условие вида AIRLINE="KLM" можно сразу получить список всех рейсов KLM вычислив by_airline["KLM"].