Публикация научных статей.
Вход на сайт
E-mail:
Пароль:
Запомнить
Регистрация/
Забыли пароль?

Научные направления

Поделиться:
Разделы: Информационные технологии, Военные науки
Размещена 23.10.2026. Последняя правка: 28.10.2026.
Просмотров - 188

Математическая модель и имитационная оценка отказоустойчивости распределенного хранилища данных на основе кодов Рида–Соломона с адаптивной избыточностью

Михеев Никита Андреевич

Магистр

Марийский Государственный Университет

Студент

Каменских Валерий Юрьевич, доктор технических наук, профессор, профессор кафедры информационных систем и технологий, Национальный исследовательский университет информационных технологий, механики и оптики


Аннотация:
В статье рассматривается проблема обеспечения отказоустойчивости в распределенных системах хранения данных (РСХД) в условиях неравномерной нагрузки и динамически изменяющихся характеристик надежности узлов. Предложена математическая модель и алгоритм адаптивного выбора параметров избыточности на базе кодов Рида–Соломона. С использованием аппарата марковских цепей и метода Монте-Карло реализована программная имитационная модель на языке Python. Экспериментально доказано, что динамическая корректировка коэффициента избыточности позволяет оптимизировать стоимость хранения данных при гарантированном соблюдении заданного уровня коэффициента готовности.


Abstract:
This article addresses the challenge of ensuring fault tolerance in distributed data storage systems (DDSS) under conditions of uneven load and dynamically changing node reliability characteristics. A mathematical model and an algorithm for the adaptive selection of redundancy parameters based on Reed-Solomon codes are proposed. A software simulation model was implemented in Python using Markov chains and the Monte Carlo method. Experimental results demonstrate that dynamically adjusting the redundancy factor allows for the optimization of data storage costs while guaranteeing adherence to a specified availability level.


Ключевые слова:
распределенные хранилища данных; коды Рида–Соломона; MDS-коды; марковские цепи; имитационное моделирование; отказоустойчивость

Keywords:
distributed data storage; Reed-Solomon codes; MDS codes; Markov chains; simulation modeling; fault tolerance


УДК 004.75:519.872

Введение

Распределённые системы хранения данных применяют избыточное размещение фрагментов для поддержания доступности информации при отказах оборудования. Репликация упрощает восстановление, но требует хранения нескольких полных копий. Кодирование с исправлением стираний (erasure coding), в частности коды Рида–Соломона, позволяет уменьшить накладные расходы на физическую ёмкость при сопоставимых требованиях к устойчивости в определённых условиях [1, 2]. При этом стоимость восстановления, сетевой обмен и топология размещения остаются существенными ограничениями [3, 6].

Во многих системах используются заранее определённые профили кодирования; например, в Apache Hadoop HDFS предусмотрены политики RS с шестью информационными и тремя проверочными блоками, а также с десятью информационными и четырьмя проверочными блоками [7]. Отдельные политики могут назначаться различным наборам данных, но это не эквивалентно непрерывной автоматической перестройке уже размещённых объектов. Исследования последних лет показывают актуальность выбора профиля и эффективного перехода между ними [4, 5].

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

Цель, задачи и вклад работы

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

Для достижения цели решаются задачи: (1) анализ подходов к избыточному хранению; (2) описание марковской модели отказов и восстановления; (3) формализация критерия выбора профиля; (4) разработка логики смены профиля; (5) сравнение характерных конфигураций на аналитических сценариях.

Элемент предлагаемого методического вклада — совместное использование оценки текущих интенсивностей отказов и восстановления, ограничений по доступности и штрафа за перекодирование в едином правиле выбора из конечного множества профилей RS. Использование кодов Рида–Соломона, марковских цепей и самой процедуры изменения избыточности не заявляется как впервые предложенное: соответствующие подходы уже представлены в литературе [3–5].

Обзор существующих решений

Код Рида–Соломона RS(n, k) состоит из k информационных и m = n − k проверочных фрагментов при n > k. Для MDS-кода любые k доступных фрагментов позволяют восстановить исходные данные. Кодирование осуществляется над конечным полем Галуа; в практических системах выбор матрицы кодирования и организации блоков влияет на производительность [2, 3].

Классическая работа Weatherspoon и Kubiatowicz [1] рассматривает количественное сопоставление кодирования со стираниями и репликации. Исследование Dimakis и соавторов [2] связано с расходами на восстановление в распределённом хранении. Современный обзор Shen и соавторов [3] систематизирует компромисс между надёжностью, стоимостью хранения, скоростью восстановления и обновления данных. В работе Cheng и соавторов 2024 года [4] исследуется компромисс между восстановлением и плановым обслуживанием для LRC-кодов. В работе Cheng и соавторов 2025 года [5] предложен метод BART для балансировки нагрузки при переходе между профилями избыточности. Таким образом, переход между кодовыми схемами — известная научно-техническая задача, а отдельным вопросом остаётся выбор момента и целевого профиля с учётом риска и цены перехода.

Постановка задачи

Пусть для объекта полезного объёма D применяется код RS(n, k), где n — общее число фрагментов, k — число фрагментов, достаточное для восстановления, а m = n − k — число проверочных фрагментов. Введём относительную избыточность

ρ(n,k)=frac{n-k}{k}.

Если все фрагменты имеют одинаковый размер, требуемый физический объём без учёта метаданных равен

ρ(n,k)=frac{n-k}{k}.

C_{cap}(n,k)=Dfrac{n}{k}=D(1+ρ).

Следовательно, при фиксированном D расход ёмкости линейно зависит от ρ. Полная эксплуатационная стоимость дополнительно включает сетевой трафик, операции кодирования и восстановления, метаданные и цену смены профиля.

Обозначим множество допустимых профилей через Ω. В момент принятия решения t выбирается профиль

(n_t^,k_t^)=argmin_{(n,k)∈Ω}≤ft[α C_{cap}(n,k)+β C_{repair}(n,k,t)+γ C_{switch}((n_{t-1},k_{t-1}),(n,k))]

при ограничениях

A(n,k,t)≥ A_{target}, P_{loss}(n,k;T)≤ε,

где A — вероятность доступности объекта в заданный момент или её усреднённая по времени оценка, P_loss — вероятность необратимой утраты объекта за интервал T, ε — допустимый риск потери, α, β, γ — весовые коэффициенты. Эти два ограничения различны и не должны подменяться друг другом.

Математическая модель отказов и восстановления

Для базового случая предположим независимые отказы фрагментов, размещённых на разных отказных доменах. Каждый доступный фрагмент становится недоступен с постоянной интенсивностью λ, а каждый недоступный восстанавливается с интенсивностью μ. В непрерывной марковской цепи S_i означает, что недоступны i из n фрагментов. Переходы задаются интенсивностями

q_{i,i+1}=(n-i)λ, q_{i,i-1}=iμ.

При i ≤ n − k данные доступны для чтения и восстановления. При i > n − k объект недоступен, но это не обязательно означает его необратимую потерю: например, сетевой раздел может завершиться возвращением узлов. Для анализа постоянной утраты нужны отдельные поглощающие состояния или явная модель необратимых отказов дисков и восстановления данных с учётом их сохранности.

В базовой независимой модели стационарная вероятность недоступности одного фрагмента равна

p=frac{λ}{λ+μ}.

Тогда приближённая стационарная доступность объекта составляет

A(n,k)=Σ_{i=0}^{n-k}C{n}{i}p^i(1-p)^{n-i}.

Данная формула корректна в рамках принятых допущений о независимости и стационарности. Для общей ремонтируемой системы коэффициент готовности иногда выражают как K = MTBF/(MTBF+MTTR), но эту формулу нельзя без дополнительных оговорок использовать вместо вероятности необратимой потери объекта или считать подтверждением уровня доступности конкретной схемы RS.

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

Алгоритм адаптивного выбора параметров

Предлагаемая логика управления включает следующие шаги.

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

2. Формирование кандидатов. Из множества Ω выбираются профили, совместимые с числом узлов, топологией размещения, размером блока и возможностями кодека.

3. Оценка ограничений. Для каждого кандидата рассчитывается A(n,k,t) по принятой модели. Оценка P_loss проводится отдельно, если определены механизм необратимой утраты и интервал T; иначе профиль нельзя объявлять удовлетворяющим ограничению на потерю данных.

4. Учёт цены перехода. Оцениваются временное увеличение занятой ёмкости, сетевой трафик, нагрузка на процессоры и максимальная длительность перекодирования. Работа [5] показывает, что балансировка нагрузки при переходе является самостоятельной существенной задачей.

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

6. Безопасная реконфигурация. Новые фрагменты размещаются и проверяются до удаления старого набора; на время операции учитывается дополнительное пространство и возможное ухудшение производительности.

Например, переход RS(10,8) → RS(14,10) увеличивает коэффициент избыточности с 0,25 до 0,4. Однако он также изменяет ширину кодового слова, поэтому выигрыш в отказоустойчивости должен оцениваться при одинаковых предположениях о доступности фрагментов и с учётом топологии размещения.

Аналитическая сценарная оценка

Ниже приведены иллюстративные расчёты, не являющиеся результатами запуска имитационного стенда. Они предназначены для демонстрации изменения физических затрат, но сами по себе не подтверждают готовность уровня 0,999999 и не определяют вероятность безвозвратной потери.

1. Сопоставление избыточности

Профиль RS(n,k)Информационных фрагментов kПроверочных фрагментов mρ = m/kФизический объём на 1 ТБ полезных данных
RS(5,4) 4 1 0,25 1,25 ТБ
RS(6,4) 4 2 0,50 1,50 ТБ
RS(12,9) 9 3 0,333 1,333 ТБ
RS(10,5) 5 5 1,00 2,00 ТБ
RS(10,4) 4 6 1,50 2,50 ТБ

Числа в последнем столбце получены непосредственно из формулы D·n/k и не зависят от моделирования. При прочих равных больший запас проверочных фрагментов увеличивает число одновременных стираний, которые может выдержать кодовое слово; количественную вероятность отказа определяют также λ, μ, размещение и характер совместных событий.

2. Сценарий адаптации

Рассмотрим условный год, в котором 80% времени система использует RS(12,9), а 20% — RS(10,5). Если принять постоянный полезный объём, пренебречь расходами на перекодирование и считать долю времени эквивалентной доле объёма, средний коэффициент физического размещения будет

c̄=0{,}8·frac{12}{9}+0{,}2·frac{10}{5}≈1{,}467.

Относительно постоянного RS(10,4), для которого c = 2,5, расчётное снижение только потребления физической ёмкости составит

η=1-frac{1{,}467}{2{,}5}≈41{,}3%.

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

3. Зависимость доступности от параметров

Для независимых отказов влияние n и k на доступность можно исследовать подстановкой конкретных значений λ и μ в биномиальную формулу. Без выбора этих параметров нельзя обоснованно утверждать снижение риска «на три порядка», прирост времени восстановления «на 40%» или выполнение целевого значения K = 0,999999. Такие численные утверждения требуют воспроизводимых расчётов или имитационных экспериментов с описанными исходными данными и оценкой погрешности.

Для сопоставления времени восстановления также необходимо задавать размер фрагментов, сетевую пропускную способность, параллелизм и реализацию алгоритма. Для типичного полного восстановления утраченного фрагмента по MDS-схеме может потребоваться чтение k доступных фрагментов, однако время операции не определяется одним только числом k.

Ограничения модели и направления проверки

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

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

Заключение

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

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

Библиографический список:

1. Бочаров П. П. Теория вероятностей, математическая статистика и теория массового обслуживания / П. П. Бочаров, А. В. Печинкин. — М.: Кучково поле, 2011. — 352 с.
2. Кулаков Ю. А. Методы повышения отказоустойчивости распределенных систем хранения данных / Ю. А. Кулаков // Информационные технологии и вычислительные системы. — 2019. — № 3. — С. 45-52.
3. Dimakis A. G. Network coding for distributed storage systems / A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, K. Ramchandran // IEEE Transactions on Information Theory. — 2010. — Vol. 56, № 9. — P. 4539-4551.
4. Plank J. S. Erasure codes for storage applications / J. S. Plank // USENIX Conference on File and Storage Technologies (FAST). — 2013. — P. 1-15.
5. Weatherspoon, H. Erasure coding vs. replication: A quantitative comparison / H. Weatherspoon, J. Kubiatowicz // International Workshop on Peer-To-Peer Systems (IPTPS). — 2002. — P. 328-338.
6. Dimakis A. G., Godfrey P. B., Wu Y., Wainwright M. J., Ramchandran K. Network Coding for Distributed Storage Systems // IEEE Transactions on Information Theory. 2010. Vol. 56, No. 9. P. 4539–4551. DOI: 10.1109/TIT.2010.2054295.
7. Shen Z., Cai Y., Cheng K., Lee P. P. C., Li X., Hu Y., Shu J. A Survey of the Past, Present, and Future of Erasure Coding for Storage Systems // ACM Transactions on Storage. 2025. Vol. 21, No. 1. Article 4. DOI: 10.1145/3708994.
8. Cheng K., Wu S., Li X., Lee P. P. C. Harmonizing Repair and Maintenance in LRC-Coded Storage // 43rd International Symposium on Reliable Distributed Systems (SRDS). 2024. DOI: 10.1109/SRDS64841.2024.00012.
9. Cheng K., Puyang H., Li X., Lee P. P. C., Hu Y., Li J., Wu T.-Y. Toward Load-Balanced Redundancy Transitioning for Erasure-Coded Storage // IEEE Transactions on Parallel and Distributed Systems. 2025. Vol. 36, No. 5. P. 889–902. DOI: 10.1109/TPDS.2025.3547872.
10. Ryu J., Byun H., Lee M., Choi J., Kim Y. Evaluation of Erasure Coding and Opportunistic Offloading Algorithms using DPU in Distributed Storage Systems // IEEE Non-Volatile Memory Systems and Applications Symposium (NVMSA). 2024. DOI: 10.1109/NVMSA63038.2024.10693658.
11. Apache Software Foundation. HDFS Erasure Coding: документация Apache Hadoop. URL: https://hadoop.apache.org/docs/r3.0.3/hadoop-project-dist/hadoop-hdfs/HDFSErasureCoding.html (дата обращения: 28.10.2026).




Рецензии:

28.10.2026, 9:21 Мирмович Эдуард Григорьевич
Рецензия: Серьёзной проблеме - отсутствие, разрыв в данных, попыткам их восстановления или адекватной замены их сам рецензент посвятил целый ряд работ, в т.ч. в рамках теории неопределённости и нечёткости. Одним из способов применялись нормальные и возмущённые функции распределения. Данная работа посвящена подобной проблеме, но для других информационных объектов, касающихся выхода из строя части узлов или дисков крупной информационной системы. Способность такой системы сохранять целостность и доступность информации чаще всего обеспечивается применением кодов Рида–Соломона (RS(n, k). Правда, это реализовать на практике не очень легко. Автор подошёл к проблеме со своей креативной позиции и получил достойный результат. По теме работа обладает актуальностью и элементами научной значимости. Замечания, устранение которых позволит автору получить абсолютно положительную рецензию. Использованные источники адекватные и соответсвуют теме, но период их публикации от 15 до 25 лет назад приводят рецензента к негативным мыслям. Ведь более поздние работы не менее значимы и серьёзны, например: группа Карипжанова, работы Круглика, Михайлишина, Конкина, работы и диссертации Иваничкиной, Назарова, десятки работ зарубежных учёных последних лет. Без дополнения ссылок на работы хотя бы 2024 года, которых было достаточно и у нас, и за рубежом, статья сильно проигрывает и наводит на всякие сомнения. Работа в списке "Кодирование с исправлением ошибок (erasure coding) и репликация: количественное сравнение" под номером [5] относится к самым цитируемым в мире по данной проблеме, но в тексте ссылка на неё отсутствует. И в названии надо добавить букву "ю" в конце. После небольшой корректировки статья будет рекомендована к печати, а пока - нет.

28.10.2026 13:13 Ответ на рецензию автора Михеев Никита Андреевич:
Уважаемый Эдуард Григорьевич! Благодарю Вас за внимательное рассмотрение статьи, положительную оценку работы и конструктивные замечания. В соответствии с Вашими рекомендациями статья была доработана. В частности, дополнен и актуализирован список литературы, включены современные исследования по рассматриваемой тематике, в том числе публикации 2024–2025 годов. Расширен обзор существующих решений, уточнены формулировки научной новизны и отдельные положения математической модели. Также исправлена опечатка в названии статьи. Что касается источника [5], ссылка на него присутствовала во введении первоначальной версии работы, однако при доработке библиографические ссылки были дополнительно проверены и уточнены. Благодарю Вас за рекомендации, которые позволили улучшить качество и научную обоснованность статьи. Надеюсь, что внесённые изменения позволят рекомендовать работу к публикации.

29.10.2026, 19:29 Мирмович Эдуард Григорьевич
Рецензия: "В статье рассматривается проблема обеспечения отказоустойчивости в распределенных системах хранения данных..." - введение и постановка задачи. А результат оказывается лишь: "Сформулирована математическая постановка адаптивного выбора параметров кодов Рида–Соломона...". Это не соответствует ни названию статьи, ни объекту и предмету исследования, ни в действительности полученным результатам. Рецензенту очень не хочется развивать эту тему в конструкции статьи и делать упрёки научному руководителю, но если автор захочет, то сам перенесёт, как это полагается, в выводы, в результат не только новый порядок закручивания гаек или усовершенствованный вид домкрата, но и сам отремонтированный автомобиль или модель его ремонта (в переносном смысле, конечно). А про ссылки: "Исследования последних лет ... [4(2013), 5(2002)]"; [1] - это наш замечательный учёный Бочаров, а не Weatherspoon и Kubiatowicz, которые как раз под ссылкой [5]; ссылки на >[7] отсутствуют вовсе; отсутствуют и приведенные в первой рецензии ссылки на наших отечественных "бойцов" этого фронта борьбы за помехоустойчивость крупных информационных систем и устройств (группа Карипжанова, работы Круглика, Михайлишина, Конкина, работы и диссертации Иваничкиной, Назарова). Непонятна фраза: "Отдельные политики могут назначаться различным наборам данных...". Если автор ничего не хочет менять, то пусть подождёт другого рецензента. Но и в таком, поспешно и небрежно подправленном виде статья может компрометировать и журнал, и тему, и сами полученные результаты самого автора. Пока - НЕТ.



Комментарии пользователей:

Оставить комментарий


 
 
▲
Вверх