Способ прогнозирования нагрузки при распределении трафика между серверами

Изобретение относится к сетям доставки контента, в частности, к распределению нагрузки между серверами. Техническим результатом является повышение эффективности распределения нагрузки между серверами и обеспечение восприимчивости к кратковременным всплескам активности клиентов. Предложен способ распределения и/или прогнозирования при распределении нагрузки между серверами, при котором получают информацию о выбранном сервере и информацию о текущей метрике M каждого сервера. Для каждого сервера сохраняют число N со значением 1, которое при каждом выборе данного сервера во время обработки клиентского запроса увеличивается на 1 и спустя T секунд уменьшается на 1. Для каждого сервера при обновлении метрики M сохраняют пары текущих значений M, N и производят линейный регрессионный анализ, в результате вычисляют: значения коэффициентов: корреляции, углового k и сдвига b. Если коэффициент корреляции не превышает порог P, производится удаление самой старой по времени добавления пары, после чего осуществляют повторный регрессионный анализ и сравнение его с порогом Р. Если перед выполнением анализа в наборе пар значений только одна пара, то к набору добавляется пара (0, 0). Вычисляют по формуле Nmax = k*Mmax+b, при превышении которого сервер не будет использоваться при выборе оптимального сервера для обслуживания запросов клиентов, где k - угловой коэффициент и b - коэффициент сдвига, Mmax - значение метрики для данного сервера, при превышении которого сервер прекращает обслуживать запросы клиентов. 1 ил.

 

ОБЛАСТЬ ТЕХНИКИ

Заявленное изобретение относится к области сетей CDN (сетей доставки контента), в частности, к способу распределения и/или прогнозирования при распределении нагрузки между серверами.

УРОВЕНЬ ТЕХНИКИ

Из уровня техники известен традиционный способ выбора сервера обслуживания клиента в сетях CDN, такой как выбор сервера из числа доступных на данный момент времени серверов, который является наилучшим для клиента с точки зрения какой-либо метрики, или комбинации нескольких различных метрик. При этом выбор сервера может осуществляться либо на этапе DNS-запроса, когда в качестве DNS-ответа клиенту сообщается IP-адрес наилучшего сервера, либо на этапе HTTP-запроса с последующей HTTP-переадресацией клиента на наилучший сервер.

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

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

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

Из уровня техники известен способ распределения и прогнозирования нагрузки между серверами (US 7441045 B2 «Method and system for balancing load distribution on a wide area network», F5 NETWORKS INC, опубл. 21.10.2008), в котором осуществляется сбор статистических данных, которые используются при выборе оптимального сервера.

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

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

Недостатком указанного способа является использование большого объёма исторических данных для учёта естественных суточных колебаний нагрузки, что делает систему недостаточно восприимчивой к кратковременным всплескам активности клиентов. Кроме того, данный способ исключает сервер из числа обслуживающих запросы клиентов прежде чем он достигнет максимальной нагрузки, что может привести к неоптимальному выбору сервера для обслуживания запроса клиента. Также данный способ осуществляет прогнозирование нагрузки только на основе загрузки полосы пропускания, и не использует другие часто используемые в сетях CDN метрики, например, загруженность процессора, или дисковой подсистемы сервера.

Задачей настоящего изобретения является преодоление указанных выше недостатков уровня техники.

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

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

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

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

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

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

Вычисленные в результате линейного регрессионного анализа коэффициенты линейной зависимости и заданное в системе распределения трафика максимальное значение метрики сервера используются для вычисления текущего максимального предела Nmax для величины N по формуле: Nmax = k*Mmax + b, при превышении которого сервер не будет использоваться при выборе оптимального сервера для обслуживания запросов клиентов. При этом k – угловой коэффициент и b – коэффициент сдвига.

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

Система распределения и/или прогнозирования при распределении нагрузки между серверами, которая служит для реализации способа прогнозирования при распределении нагрузки между серверами, состоит из следующих подсистем:

• Подсистема прогнозирования нагрузки.

• Подсистема выбора оптимального сервера.

• Подсистема вычисления текущей метрики серверов обслуживания клиентов.

• Подсистема конфигурации.

Подсистема прогнозирования нагрузки (фиг. 1, поз. 2) предусматривает программный модуль, выполняемый отдельно, или в составе системы выбора оптимального сервера для клиента, который хранит в оперативной памяти сервера, на дисковом накопителе или ином хранилище данных необходимые для работы подсистемы объекты, включая следующие объекты для каждого сервера, осуществляющего обслуживание запросов клиентов: целочисленная переменная N, первоначально равная единице, целочисленная переменная Nmax, первоначально равная максимальному значению, которое можно записать с помощью используемого для хранения этой переменной типа данных, и первоначально пустой массив A, элементами которого являются пары, состоящие из целочисленного значения и числа с плавающей точкой.

При получении данных от подсистемы выбора оптимального сервера (фиг. 1, поз. 1), содержащих информацию о том, какой сервер был выбран для клиента при обработке текущего клиентского запроса, происходит вычисление значения случайной величины T с экспоненциальным распределением с помощью генератора псевдослучайных чисел. Значение параметра экспоненциального распределения λ запрашивается у подсистемы конфигурации (фиг. 1, поз. 4). После вычисления значения T, к соответствующей выбранному серверу переменной N прибавляется единица, а также создаётся задача вычесть из данной переменной N единицу в момент времени C + T, где C — текущее время. Под созданием задачи здесь понимается любой программный, аппаратный, или иной способ обеспечить выполнение заданного вычисления в заданный момент времени. При каждом изменении значения N новое значение передаётся подсистеме выбора оптимального сервера.

При получении данных от подсистемы вычисления текущей метрики серверов обслуживания клиентов (фиг. 1, поз 3), содержащих новое значение метрики M одного из серверов, в конец соответствующего данному серверу массива A добавляется пара (M, N), если M больше нуля, либо пара (Md, N), если M равно нулю, где переменная N также соответствует данному серверу, а Md — это метрика по умолчанию, значение которой запрашивается у подсистемы конфигурации (фиг. 1, поз. 4). При этом если число элементов в массиве больше величины V, значение которой запрашивается у подсистемы конфигурации, то из массива A удаляется находящийся в начале массива элемент. Далее для значений, хранящихся в массиве A, производится линейный регрессионный анализ с использованием метода наименьших квадратов для зависимой переменной N, в результате которого вычисляются значения коэффициента корреляции, углового коэффициента k и коэффициента сдвига b. Если значение коэффициента корреляции не превышает порог P, значение которой запрашивается у подсистемы конфигурации, то из массива A удаляется находящийся в начале массива элемент, после чего для значений, хранящихся в обновлённом массиве A, вновь производится линейный регрессионный анализ с использованием метода наименьших квадратов. Этот процесс повторяется до тех пор, пока коэффициент корреляции не окажется больше порога P, причём если на очередной итерации число элементов в массиве A равно единице, то в начало массива добавляется пара (0, 0). Далее вычисляется значение переменной Nmax для данного сервера по формуле Nmax = k*Mmax + b, где Mmax — значение метрики для данного сервера, при превышении которого сервер перестаёт обслуживать запросы клиентов. Значение Mmax запрашивается у подсистемы конфигурации, или иной подсистемы, в зависимости от реализации системы распределения трафика. Наконец, полученное значение Nmax передаётся подсистеме выбора оптимального сервера (фиг. 1, поз. 1).

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

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

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

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

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

• Доступность.

• Загрузка процессора.

• Использование дискового пространства.

• Сетевой трафик и использование пропускной способности.

• Запущенные процессы и сервисы.

• Температура процессора/жесткого диска/материнской платы.

• Скорость и состояние вентилятора.

• Любые другие метрики, доступные по SNMP.

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

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

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

Анализ уровня техники показывает, что неизвестен способ распределения нагрузки между серверами сети доставки контента (CDN), которому присущи признаки, идентичные всем существенным признакам данного технического решения, что свидетельствует о его неизвестности и, следовательно, новизне.

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

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

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

Способ распределения и/или прогнозирования при распределении нагрузки между серверами, в котором получают информацию о выбранном сервере для каждого обработанного системой клиентского запроса, а также информацию о представленной неотрицательным числом текущей метрике M каждого сервера, вычисленной в соответствии с используемым в данной системе алгоритмом вычисления метрики так, чтобы меньшее число соответствовало более предпочтительному серверу, при этом для каждого сервера хранится число N с первоначальным значением единица, которое при каждом выборе данного сервера во время обработки клиентского запроса увеличивается на единицу и спустя T секунд уменьшается на единицу, где T является случайной величиной с экспоненциальным распределением, значение λ которого считывается из конфигурационного файла, при этом для каждого сервера при каждом обновлении метрики M происходит сохранение пары текущих значений (M, N), причём если количество сохранённых пар значений превышает заданный в конфигурационном файле порог, происходит удаление самой старой по времени добавления пары, причём если значение метрики M равно нулю, оно заменяется на значение по умолчанию, заданное в конфигурационном файле, также после сохранения текущей пары значений (M, N) производится линейный регрессионный анализ с использованием метода наименьших квадратов для имеющегося набора пар значений, в результате которого вычисляются значения коэффициента корреляции, углового коэффициента k и коэффициента сдвига b, причем если полученный коэффициент корреляции не превышает порог P, заданный в конфигурационном файле, производится удаление самой старой по времени добавления пары, после чего происходит повторное выполнение процедуры линейного регрессионного анализа и сравнение коэффициента корреляции с порогом P, причём если перед выполнением анализа в наборе пар значений содержится только одна пара, к набору добавляется пара (0, 0), которая считается старше по времени добавления уже имеющейся в наборе пары, при этом вычисленные в результате линейного регрессионного анализа коэффициенты линейной зависимости и заданное в системе распределения трафика максимальное значение метрики сервера используются для вычисления текущего максимального предела Nmax для величины N по формуле: Nmax = k*Mmax + b, при превышении которого сервер не будет использоваться при выборе оптимального сервера для обслуживания запросов клиентов, где k – угловой коэффициент и b – коэффициент сдвига, Mmax — значение метрики для данного сервера, при превышении которого сервер перестаёт обслуживать запросы клиентов.