Оглавление
1. Постановка задачи
Давайте рассмотрим ситуацию: Есть сервер, сервер имеет ограниченную вычислительную мощность. Есть набор запросов, каждый из которых требует определённое время на исполнение. Запросов от клиентов больше, чем сервер сможет обработать. Требуется обслужить всех, ответив на критические запросы.
Данная ситуация встречается повсеместно, она может возникать, когда вычислительная мощность сервера недостаточна, в следствии ошибки в клиентском коде или атаки на сервер.
Теперь рассмотрим как это можно решить.
Постановка подразумевает, что ответ на все запросы невозможен. Отсюда следует, что мы должны отсеять часть запросов, при этом сохранив критически важные запросы.
Также, сервер должен определять ошибки и отсеивать заведомо ошибочные запросы без обработки. Отсюда получается многослойный фильтр, где каждый слой отсеивает часть запросов.
2. Фильтрация по качеству и количеству
Итак, теперь осталось определиться с методами фильтрации. Для большинства видов потребуется построить структуру: ip-данные.
Первый и самый простой метод, фильтрация по количеству. Тогда для каждого ip адреса заводится счётчик, который увеличивается при получении пакета от пользователя, когда счётчик переполняется пакеты от пользователя больше не исполняются. Счётчик сбрасывается раз в заданный промежуток времени.
Второй метод это фильтрация по количеству и качеству. Тогда для каждого пользователя заводится счётчик, а для каждого запроса его "цена", дальнейшие действия аналогичны прошлый версии.
Возможна модификация, когда накопленный ресурс не зануляется, а уменьшается на фиксированное число. Также критические запросы могут иметь отдельный счётчик.
3. Буферизация
Прошлая модификация спокойно отсеет неисправные клиенты, отправляющие слишком много пакетов, но для дальней защиты требуется нечто большее.
В условиях перегрузки зачастую требуется выполнять запросы для многих пользователей параллельно. При нехватке вычислительной мощности, долгие запросы можно отложить.
Для этого используется такая структура данных, как очередь. Запросы, на которые нехватает "времени", откладываются в очередь.
Данная очередь выполняет роль буфера и называется "почтовым ящиком". Т.к. входящие "письма" помещаются в неё, а затем извлекаются, когда поток освобождается от остальных задач.
Теперь обсудим алгоритм помещения в очередь. Первый пункт, требуется оценить, что мощность недостаточна. Для этого требуется отслеживать количество пакетов относительно пропускной способности. Сделать это можно разделив процедуру считывания и фильтрации, а также процедуру анализа и обработки. Это звучит довольно сложно, поэтому приведу схему.
Самая важная часть данной схемы - обработка клиентов. Требуется выбрать каким-то образом клиента из списка и обработать его запрос. Оптимальные алгоритмы для данной процедуры давно написаны, посмотреть их можно например в книге "Современные операционные системы", автор: Таненбаум Э. С., Бос Х.
Используются алгоритмы преднозначенные для исполнения потоков в операционных системах. Требуется выбрать алгоритм, который не "обделит" ниодного клиента, справедливо выполняя запросы.
