The post has been translated automatically. Original language: Russian
The original is on the main technical channel (Edits and additions are possible).
Additional materials on the application of the Markov chain in the pg_expecto project
Development and testing of an algorithm for restoring the Markov model of DBMS performance transitions, including iterative correction of critical states, dynamic adjustment of the forgetting coefficient and selection of the forecast horizon based on empirical risk.
Annotation
The article presents an approach to the construction of a discrete Markov chain for predicting system failures based on historical data. A batch learning algorithm is proposed that simulates the step-by-step accumulation of transitions, followed by adaptive adjustment of the hyperparameters of the model (forgetting coefficient, incident half-life, forgetting interval and forecast horizon). The main contribution consists in the development of an iterative correction procedure for multiple absorbing (critical) conditions based on empirical risk assessment, as well as the use of calibration metrics (Brier score, ECE, MCE) to select the optimal horizon. Experiments on real-world relational database performance monitoring data demonstrate achieving the target percentage of incidents (≈15%) and obtaining a reliability rating of 4 out of 5 with stable calibration of probabilities.
1. Introduction
Predicting failures and anomalies in complex information systems is an urgent task. Markov chains with discrete time are one of the effective tools for modeling the evolution of system states.
However, their practical application runs into a number of problems:
- non-stationarity of distributions,
- sparsity of data for rare events,
- choosing the forecast time horizon,
- the need to adapt to changing conditions.
In this paper, we consider the problem of predicting the risk of a system going into a critical (emergency) state based on the observed performance metrics.
A comprehensive method is proposed, including:
- restoring the transition matrix based on historical data while maintaining the time structure;
- dynamic updating of the list of critical states based on the empirical frequency of incidents;
- adaptive forgetting to account for data aging;
- automatic selection of the forecast horizon based on the criterion of proximity of the percentage of incidents to the target value.
The main goal is to ensure high calibration of forecast probabilities and stability of the model when changing operating modes of the system.
2. Setting the task
3. Description of the model and algorithms
3.1. The basic apparatus of the Markov chain
A first-order Markov chain with a finite state space of size N=189 is used. The transition matrix is estimated by the transition frequencies accumulated in the markov_frequencies table.:
The predicted probability of hitting the critical set in k steps is calculated by iteratively propagating the distribution vector:
with zeroing out the probabilities of critical states at each step to account for only the first hit.
3.2. Learning from historical data
Since real learning takes place in streaming mode (every minute), a step-by-step learning simulation procedure is proposed for using historical records. The time range is divided into consecutive minutes; for each minute, metrics are extracted from the cluster_stat_median table, trends and correlation are calculated, a state identifier is generated, and transition logging is performed (if the previous state is determined). This process reproduces the natural accumulation of statistics while maintaining chronological order. To speed up processing, batch loading (portions of 60 minutes each) is used with periodic transaction logging.
3.3. Adaptive forgetting
To combat nonstationarity, a forgetting mechanism has been introduced that reduces all transition frequencies by a factor of:
3.4. Updating critical states
The set C is not fixed. To update it, the empirical risk for each condition is calculated.:
States with risk(i)>θ and with at least N min transitions are included in C. The threshold θ is dynamically increased at each iteration of adaptation in order to achieve the target percentage of incidents among forecasts.
3.5. Selection of the forecast horizon
The horizon H is selected from the range [5,120] minutes in increments of 5. For each candidate, the percentage of transitions is calculated, followed by an incident within H minutes (empirical frequency). The optimal value is H, at which this fraction is closest to the set target value (in our experiments, 0.15). This procedure is performed iteratively in conjunction with the C update.
3.6. Quality and calibration assessment
Standard probabilistic forecasting metrics are used for quality control.:
- Brier score – standard deviation;
- Log-loss – logistical loss;
- ROC-AUC – the area under the ROC curve (discrimination ability);
- Expected Calibration Error (ECE) – weighted average absolute deviation between the predicted probability and the observed frequency in 10 bins;
- Maximum Calibration Error (MCE) – maximum bean deviation.
Additionally, a confidence rating (0-5) is calculated based on the amount of data, probability stability, and coverage of frequent conditions, which allows you to automatically determine whether the model is ready for operation.
4. Software implementation
All algorithms are implemented as a set of stored functions in the PL/pgSQL language in the PostgreSQL DBMS. Main components:
- Storage tables: markov_frequencies (frequencies), transition_log (transition log), markov_probabilities (probability matrix), critical_states (list of critical states).
- The historical learning function mchain_initial_train_from_history – starts batch processing of minutes, logs transitions, periodically applies forgetting and collects forecasts.
- Adaptive configuration function adaptive_configure_markov_chain – calculates new hyperparameter values based on the frequency of incidents over the last retention period.
- The iterative optimization procedure (embedded in the script train_markov_chain.sh ) – cyclically adjusts the threshold θ, recalculates C, selects H, regenerates forecasts and estimates the proportion of incidents before reaching the target range.
All calculations are performed directly in the database, which allows efficient processing of large volumes without unloading data.
5. Experimental results
The experiment was conducted on real data from monitoring the performance of a DBMS cluster for the period from June 22 to July 1, 2026 (about 10.4 thousand transitions in total). The initial data contained minutes with measured values of operating speed and waiting time, as well as a table of recorded incidents.
5.1. The course of training
The initial adaptive setup (step 0.5) based on 97 incidents over 30 days established:
- horizon H=67 min,
- base alpha = 0.034,
- half-life = 36.4 days,
- forgetting interval = 134 min.
However, after full training, an iterative procedure was launched, which adjusted the parameters in two iterations.:
- in the first iteration (threshold θ=0.20) 4 critical conditions were added, the actual incident rate reached 0.259 (too high);
- In the second iteration (the threshold was increased to 0.25), four states were deleted, and the proportion of incidents decreased to 0.147, which fell within the target range of 0.15±0.03.
The final parameters were: H=5 minutes, α base=0.15, T 1/2=5 days, forgetting interval = 30 minutes, threshold for forgetting – 3000 transitions.
5.2. Quality of forecasts
According to the data for the period of June 24-30 (8,592 forecasts with a known outcome), the following metrics were obtained:
The Brier value (0.099) indicates a good calibration (as a rule, <0.1 is considered satisfactory). ECE = 0.058 indicates small systematic biases. A high ROC-AUC (0.864) indicates a good discriminative ability.
However, there is an overestimation of probabilities in the upper bin (0.9–1.0), where the observed frequency (0.704) is lower than the predicted frequency (1.0), which gives MCE = 0.296.
5.3. Stability and coverage
An assessment of the stability of probabilities over 7-day windows showed:
- max_prob_change = 0.2405 (moderate instability),
- disclosure of frequent conditions(freq >1% and >=50 transitions) = 100%,
- reliability rating = 4 out of 5.
The model is recognized as standard, forecasts are recommended to be used with caution (rating 4).
6. Discussion
The proposed approach successfully solves the problem of adapting the Markov chain to the changing operating conditions of the system. The key features are:
- Simulation learning based on history allows you to use all available data, preserving temporal dynamics and correctly accumulating frequencies.
- Dynamic updating of critical states makes the model sensitive to real-world incidents, not just to predefined thresholds.
- Iterative horizon selection ensures consistency between the predicted risk and the actual frequency of events, which is critical for practical interpretability.
- The use of ECE/MCE provides a more detailed calibration estimate than a single Brier score and helps to identify systematic errors (for example, in the upper bin).
However, there are still open questions:
- selection of the starting parameters for adaptive adjustment (they were obtained based on empirical formulas, but may require additional calibration);
- the impact of sparsity of data for rare states – despite high coverage, some states may have few transitions, which reduces the reliability of estimates;
- the need to periodically review the target percentage of incidents (0.15) depending on business requirements.
The proposed architecture is easily scaled and can be ported to other subject areas where discrete states and time series of incidents are available.
7. Conclusion
A comprehensive method for constructing an adaptive Markov chain for predicting the risk of system failures has been developed and tested.
Main results:
- Batch training based on historical data with simulation of streaming mode is implemented.
- A mechanism of adaptive forgetting has been introduced with a dynamic coefficient depending on the time since the last incident and the stability of probabilities.
- An iterative procedure for correcting multiple critical conditions and selecting a forecast horizon has been developed to ensure a targeted proportion of incidents.
- The calibration of forecasts has been experimentally confirmed (Brier ≈0.1, ECE ≈0.06) and a high reliability rating (4/5) has been achieved on real data.
Further research may be aimed at automatic selection of initial hyperparameters using Bayesian optimization and the introduction of a mechanism for detecting mode changes to restart adaptation.
Оригинал — на основном техническом канале (Возможны правки и дополнения).
Дополнительные материалы по исследованию применения цепи Маркова в проекте pg_expecto
Разработка и апробация алгоритма восстановления марковской модели переходов по временным рядам производительности СУБД, включающего итеративную корректировку критических состояний, динамическую настройку коэффициента забывания и подбор горизонта прогноза на основе эмпирического риска.
Аннотация
В статье представлен подход к построению дискретной цепи Маркова для прогнозирования аварийных состояний системы на основе исторических данных. Предложен алгоритм пакетного обучения, имитирующий пошаговое накопление переходов, с последующей адаптивной настройкой гиперпараметров модели (коэффициент забывания, период полураспада инцидентов, интервал применения забывания и горизонт прогноза). Основной вклад состоит в разработке процедуры итеративной коррекции множества поглощающих (критических) состояний, основанной на эмпирической оценке риска, а также в использовании метрик калибровки (Brier score, ECE, MCE) для выбора оптимального горизонта. Эксперименты на реальных данных мониторинга производительности реляционной СУБД демонстрируют достижение целевой доли инцидентов (≈15 %) и получение рейтинга достоверности 4 из 5 при устойчивой калибровке вероятностей.
1. Введение
Прогнозирование отказов и аномалий в сложных информационных системах является актуальной задачей. Одним из эффективных инструментов для моделирования эволюции состояний системы служат цепи Маркова с дискретным временем.
Однако их практическое применение наталкивается на ряд проблем:
- нестационарность распределений,
- разреженность данных для редких событий,
- выбор временного горизонта прогноза,
- необходимость адаптации к изменяющимся условиям.
В настоящей работе рассматривается задача прогнозирования риска перехода системы в критическое (аварийное) состояние на основе наблюдаемых метрик производительности.
Предлагается комплексный метод, включающий:
- восстановление матрицы переходов по историческим данным с сохранением временной структуры;
- динамическое обновление списка критических состояний по эмпирической частоте инцидентов;
- адаптивное забывание (форgetting) для учёта старения данных;
- автоматический подбор горизонта прогноза по критерию близости доли инцидентов к целевому значению.
Основная цель – обеспечить высокую калибровку прогнозных вероятностей и устойчивость модели при смене режимов работы системы.
2. Постановка задачи
3. Описание модели и алгоритмов
3.1. Базовый аппарат цепи Маркова
Используется цепь Маркова первого порядка с конечным пространством состояний размера N=189. Матрица переходов оценивается по частотам переходов, накопленным в таблице markov_frequencies:
Прогнозная вероятность попадания в критическое множество за k шагов вычисляется итеративным распространением вектора распределения:
с обнулением вероятностей критических состояний на каждом шаге для учёта только первого попадания.
3.2. Обучение на исторических данных
Поскольку реальное обучение происходит в потоковом режиме (каждую минуту), для использования исторических записей предложена процедура имитации пошагового обучения. Временной диапазон разбивается на последовательные минуты; для каждой минуты из таблицы cluster_stat_median извлекаются метрики, вычисляются тренды и корреляция, формируется идентификатор состояния, и выполняется логирование перехода (если предыдущее состояние определено). Этот процесс воспроизводит естественное накопление статистики, сохраняя хронологический порядок. Для ускорения обработки применяется пакетная загрузка (порции по 60 минут) с периодической фиксацией транзакций.
3.3. Адаптивное забывание
Для борьбы с нестационарностью введён механизм забывания, уменьшающий все частоты переходов с коэффициентом α:
3.4. Обновление критических состояний
Множество C не является фиксированным. Для его обновления вычисляется эмпирический риск для каждого состояния:
Состояния с risk(i)>θ и с числом переходов не менее Nmin включаются в C. Порог θ динамически увеличивается на каждой итерации адаптации, чтобы достичь целевой доли инцидентов среди прогнозов.
3.5. Подбор горизонта прогноза
Горизонт H выбирается из диапазона [5,120] минут с шагом 5. Для каждого кандидата вычисляется доля переходов, за которыми в течение H минут следует инцидент (эмпирическая частота). Оптимальным считается H, при котором эта доля наиболее близка к заданному целевому значению (в наших экспериментах – 0,15). Данная процедура выполняется итеративно совместно с обновлением C.
3.6. Оценка качества и калибровки
Для контроля качества используются стандартные метрики вероятностного прогнозирования:
- Brier score – среднеквадратичная ошибка;
- Log-loss – логистическая потеря;
- ROC-AUC – площадь под ROC-кривой (дискриминационная способность);
- Expected Calibration Error (ECE) – средневзвешенное абсолютное отклонение между предсказанной вероятностью и наблюдаемой частотой в 10 бинах;
- Maximum Calibration Error (MCE) – максимальное отклонение по бинам.
Дополнительно вычисляется рейтинг достоверности (0–5), основанный на объёме данных, стабильности вероятностей и покрытии частых состояний, что позволяет автоматически определять готовность модели к эксплуатации.
4. Программная реализация
Все алгоритмы реализованы в виде набора хранимых функций на языке PL/pgSQL в СУБД PostgreSQL. Основные компоненты:
- Таблицы-хранилища: markov_frequencies (частоты), transition_log (журнал переходов), markov_probabilities (матрица вероятностей), critical_states (список критических состояний).
- Функция исторического обучения mchain_initial_train_from_history – запускает пакетную обработку минут, логирует переходы, периодически применяет забывание и собирает прогнозы.
- Функция адаптивной настройки adaptive_configure_markov_chain – рассчитывает новые значения гиперпараметров на основе частоты инцидентов за последний период ретеншна.
- Процедура итеративной оптимизации (встроена в скрипт train_markov_chain.sh) – циклически корректирует порог θ, пересчитывает C, подбирает H, перегенерирует прогнозы и оценивает долю инцидентов до достижения целевого диапазона.
Все вычисления выполняются непосредственно в базе данных, что позволяет эффективно обрабатывать большие объёмы без выгрузки данных.
5. Экспериментальные результаты
Эксперимент проводился на реальных данных мониторинга производительности кластера СУБД за период с 22 июня по 1 июля 2026 года (всего около 10,4 тыс. переходов). Исходные данные содержали минуты с измеренными значениями операционной скорости и времени ожидания, а также таблицу зафиксированных инцидентов.
5.1. Ход обучения
Первоначальная адаптивная настройка (шаг 0.5) на основе 97 инцидентов за 30 дней установила:
- горизонт H=67 мин,
- базовый alpha = 0.034,
- период полураспада = 36.4 дня,
- интервал забывания = 134 мин.
Однако после полного обучения была запущена итеративная процедура, которая за две итерации скорректировала параметры:
- на первой итерации (порог θ=0.20) было добавлено 4 критических состояния, фактическая доля инцидентов достигла 0.259 (слишком высокая);
- на второй итерации (порог увеличен до 0.25) четыре состояния были удалены, и доля инцидентов снизилась до 0.147, что попало в целевой интервал 0.15±0.03.
Итоговые параметры составили: H=5 минут, αbase=0.15, T1/2=5 дней, интервал забывания = 30 минут, порог для забывания – 3000 переходов.
5.2. Качество прогнозов
По данным за период 24–30 июня (8 592 прогноза с известным исходом) получены следующие метрики:
Значение Brier (0.099) указывает на хорошую калибровку (как правило, <0.1 считается удовлетворительным). ECE = 0.058 говорит о небольших систематических смещениях. Высокий ROC-AUC (0.864) свидетельствует о хорошей дискриминационной способности.
Однако наблюдается завышение вероятностей в верхнем бине (0.9–1.0), где наблюдаемая частота (0.704) ниже предсказанной (1.0), что и даёт MCE = 0.296.
5.3. Стабильность и покрытие
Оценка стабильности вероятностей по 7-дневным окнам показала:
- max_prob_change = 0.2405 (умеренная нестабильность),
- покрытие частых состояний (freq >1% и >=50 переходов) = 100%,
- рейтинг достоверности = 4 из 5.
Модель признана штатной, прогнозы рекомендуются к использованию с осторожностью (рейтинг 4).
6. Обсуждение
Предложенный подход успешно решает проблему адаптации цепи Маркова к изменяющимся условиям работы системы. Ключевыми особенностями являются:
- Имитационное обучение на истории позволяет использовать все доступные данные, сохраняя временную динамику и корректно накапливая частоты.
- Динамическое обновление критических состояний делает модель чувствительной к реальным инцидентам, а не только к заранее заданным порогам.
- Итеративный подбор горизонта обеспечивает согласованность между прогнозным риском и фактической частотой событий, что критично для практической интерпретируемости.
- Использование ECE/MCE даёт более детальную оценку калибровки, чем один Brier score, и помогает выявить систематические ошибки (например, в верхнем бине).
Однако остаются открытые вопросы:
- выбор стартовых параметров для адаптивной настройки (они были получены на основе эмпирических формул, но могут требовать дополнительной калибровки);
- влияние разреженности данных для редких состояний – несмотря на высокое покрытие, некоторые состояния могут иметь мало переходов, что снижает надёжность оценок;
- необходимость периодического пересмотра целевой доли инцидентов (0.15) в зависимости от требований бизнеса.
Предложенная архитектура легко масштабируется и может быть перенесена на другие предметные области, где доступны дискретные состояния и временные ряды инцидентов.
7. Заключение
В работе разработан и апробирован комплексный метод построения адаптивной цепи Маркова для прогнозирования риска аварийных состояний системы.
Основные результаты:
- Реализовано пакетное обучение на исторических данных с имитацией потокового режима.
- Введён механизм адаптивного забывания с динамическим коэффициентом, зависящим от времени с последнего инцидента и стабильности вероятностей.
- Разработана итеративная процедура коррекции множества критических состояний и подбора горизонта прогноза, обеспечивающая целевую долю инцидентов.
- Экспериментально подтверждена калибровка прогнозов (Brier ≈0.1, ECE ≈0.06) и достигнут высокий рейтинг достоверности (4/5) на реальных данных.
Дальнейшие исследования могут быть направлены на автоматический выбор начальных гиперпараметров с использованием байесовской оптимизации и внедрение механизма обнаружения смены режимов для перезапуска адаптации.
Share
