Привет, Хабр! Я – Илья Усов, техлид из команды сервиса SunkeyToolkit для удаленного тестирования мобильных приложений. В этой статье расскажу о том, как мы попытались исследовать некоторые вероятностные характеристики, связанные с нагрузками на оборудование фермы мобильных устройств.

Про первый в РФ сервис для удаленного тестирования мобильных приложений MTS SunkeyToolkit мы кратко рассказывали здесь. База сервиса – ферма из более чем 300 мобильных устройств, это набор машин с разными ОС: MacOS и Ubuntu для устройств с ОС IOS и Android соответственно, к которым через хабы подключены устройства.

В реальности это выглядит так: 

Мы разработали весьма обширный функционал: 

• механизм резерваций (бронирования) устройств; 

• стриминг экрана мобильных телефонов; 

• взаимодействие с телефоном (swipe, tap, long tap и так далее) прямо из интерфейса нашего приложения и из любой точки страны; 

• сбор логов в реальном времени; 

• смена ориентации; 

• ввод текста (в том числе русского) с физической клавиатуры пользователя; 

• сервис сбора sms и многое другое. 

Кроме того, один пользователь может запустить до 4 устройств одновременно на разных вкладках.

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

Осторожно, далее будет математика! 

За основу берем следующие недавние исследования:

• Estimating the Rate of Convergence of the PH/M/1 Model by Reducing to Quasi-Birth-Death Processes, Ilya Usov, Yacov Satin and Alexander Zeifman;

• On the Study of Forward Kolmogorov System: the Corresponding Problems and Bounds for Inhomogeneous Continuous-time Markov Chains and Models, Alexander Zeifman, Yacov Satin, Ivan Kovalev, Anastasia Kryukova, Galina Shilova and Ilya Usov;

• "Оценка погрешности аппроксимации неоднородных марковских цепей с непрерывным временем и катастрофами", И. А. Усов, И. А. Ковалёв, А. И. Зейфман;

• Ergodicity Bounds and Limiting Characteristics for a Modified Prendiville Model, Ilya Usov , Yacov Satin, Alexander Zeifman and Victor Korolev.

Основные понятия

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

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

Заявка (требование) — объект обслуживания в СМО, для которого решается типовая задача обслуживания.

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

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

Поток характеризуется интенсивностью λ — частотой появления событий, то есть средним числом событий, происходящих в единицу времени, а μ — это интенсивность обслуживания требования.

Также мы будем использовать все основные обозначения и термины из “Марковские цепи и модели с непрерывным временем”, Зейфман А. И.

Описание подхода

Для того, чтобы посчитать вероятность пустой очереди и математическое ожидание среднего числа заявок на нодах фермы, рассмотрим самую простую ситуацию (без учета поломок машин и их восстановления) и возьмем за основу модель M/M/2. Для простоты будем считать, что Нод у нас всего 2 штуки. Изучение интересующих нас характеристик такой системы сводится к решению прямой системы Колмогорова (система обыкновенных дифференциальных уравнений) вида:

где А – это транспонированная матрица интенсивностей (зависимость от t не показана для краткости записи):

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

Теперь мы с помощью метода Рунге-Курта четвертого порядка будем решать прямую систему Колмогорова, в этом нам помогут язык Python, библиотеки: numpy, scipy, Matplotlib. Также мы построим график для среднего числа заявок в системе (мат. ожидания) и вероятность пустой очереди в этой системе массового обслуживания. Данные графики наглядно покажут поведение данных характеристик системы с течением времени.

 Итак, мы написали достаточно простой алгоритм для получения решения данной системы:

def calc_solve(start_vector, t_list, function):
	return solve_ivp(function, t_list, np.ravel(start_vector), method='RK45', atol=1e-12, rtol=1e-12)

"""Получаем решения с заданными нач. условиями (start_vector)"""
t_period = [0, t_end + 1]
start_vector = get_start_vector()
solution = calc_solve(start_vector, t_period, dot_function)

"""Считаем мат. ожидание"""
mean = calc_mean(solution.y)

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

plot_list = [
	# For p_0
	{
		'num': 1,
		'y_label': 'Вероятность',
		'x_label': 't',
		'lines': [
			{
				't': solution.t[:t_end_index],
				'sol': np.transpose(solution.y[0, :t_end_index]),
				'label': 'X(0) = 50',
			},
          ]
	},

	# For Mean
	{
		'num': 3,
		'y_label': 'Среднее',
		'x_label': 't',
		'lines': [
			{
				't': solution.t,
				'sol': mean,
				'label': 'X(0) = 50',
			},
			]
	},
]	

def build_charts(plots, legend='upper right'):
      for graph in plots:
            plt.figure(graph['num'])
        	fig, ax = plt.subplots()	
            for pl in graph['lines']:
                ax.plot(pl['t'], pl['sol'], label=pl['label'])
            ax.legend(loc=legend)
            plt.xlabel(graph['x_label'])
            plt.ylabel(graph['y_label'])
            plt.grid(True)
            plt.show()

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

2. среднее число заявок в системе.

Эти графики позволяют увидеть, как изменяется вероятность пустой очереди с течением времени и поведение среднего за 8 рабочих часов. 

Заключение

Мы описали один из подходов к исследованию характеристик системы, связанных с нагрузками на оборудование в рамках стохастического процесса, когда события происходят в случайный момент времени. Стоит отметить, что подход этот применим не ко всем системам и продуктам на практике. Вероятно, можно взять и более сложные модели, в которых, например, уже учитываются поломки, ремонт машин (на эту тему рекомендуем ознакомиться с моделью Прендевилля в Ergodicity Bounds and Limiting Characteristics for a Modified Prendiville Model, Ilya Usov , Yacov Satin, Alexander Zeifman and Victor Korolev). 

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

В целом, теория массового обслуживания имеет множество приложений на практике в реальной жизни, например, при моделировании систем сборки на заказ (Irvani, S.M.R., Luangkesorn, K.L., Simchi-Levi, D. 2010. On assemble to order systems with flexible customers. IIE Trans), производственных линий (Fadiloglu, M.M., Yeralan, S. 2002. Models of production lines as quasi-birth-death processes. Math. Comput. Model), беспроводных сетей (Kim, Y.Y., Li, S. 1999. Performance evaluation of packet data services over cellular voice networks. Wirel. Netw. 5:211–219) и многое другое. 

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

1. https://elar.urfu.ru/bitstream/10995/117140/1/978-5-7996-3539-8_2022.pdf

2. Jain, M., Maheshwari, S. 2004. N-policy for a machine repair systemwith spares and reneging. Appl. Math. Model. 28:513–531. 

3. Jain, M., Ghimire, R.P. 1997. Machine repair queueing system with non-reliable server and heterogeneous services discipline. J. MACT. 30:105–115. 

4. Wang, K. 1994. Profit analysis of the ?/?/? machine repair problem with spares and server breakdowns. J. Oper. Res. Soc. 45:539–548.