Магистр
Марийский Государственный Университет
Студент
Каменских Валерий Юрьевич, доктор технических наук, профессор, профессор кафедры информационных систем и технологий, Национальный исследовательский университет информационных технологий, механики и оптики
УДК 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 и не определяют вероятность безвозвратной потери.
| Профиль 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 и не зависят от моделирования. При прочих равных больший запас проверочных фрагментов увеличивает число одновременных стираний, которые может выдержать кодовое слово; количественную вероятность отказа определяют также λ, μ, размещение и характер совместных событий.
Рассмотрим условный год, в котором 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%.
Это арифметическая иллюстрация на специально заданных долях, а не измеренная экономия. При иной структуре нагрузки, существенных затратах на реконфигурацию или более строгих требованиях к отказоустойчивости результат изменится. Сопоставление корректно только при подтверждённой допустимости всех используемых профилей.
Для независимых отказов влияние n и k на доступность можно исследовать подстановкой конкретных значений λ и μ в биномиальную формулу. Без выбора этих параметров нельзя обоснованно утверждать снижение риска «на три порядка», прирост времени восстановления «на 40%» или выполнение целевого значения K = 0,999999. Такие численные утверждения требуют воспроизводимых расчётов или имитационных экспериментов с описанными исходными данными и оценкой погрешности.
Для сопоставления времени восстановления также необходимо задавать размер фрагментов, сетевую пропускную способность, параллелизм и реализацию алгоритма. Для типичного полного восстановления утраченного фрагмента по MDS-схеме может потребоваться чтение k доступных фрагментов, однако время операции не определяется одним только числом k.
Предложенная модель предназначена для предварительного выбора профилей и опирается на упрощения: независимые экспоненциальные отказы в базовом варианте, однородные фрагменты, стационарные интервалы наблюдения и известные затраты перекодирования. Для проверки применимости к промышленной системе целесообразно исследовать нестационарные интенсивности, совместные отказы стоек, очереди восстановления, сетевые ограничения, временную повышенную уязвимость при переходе между профилями, а также доверительные интервалы оценок.
Перспективная имитационная реализация может использовать дискретно-событийное моделирование и метод Монте-Карло, однако её результаты должны сопровождаться указанием параметров, числа независимых испытаний, горизонта наблюдения и способа определения потери данных. Само число прогонов без наблюдаемых событий недостаточно для доказательства крайне малых вероятностей.
Сформулирована математическая постановка адаптивного выбора параметров кодов Рида–Соломона для распределённого хранения данных. Показано, что снижение физической избыточности может уменьшать потребление ёмкости, но выбор профиля должен одновременно учитывать доступность, риски необратимой утраты и затраты на реконфигурацию. Предложенная марковская модель позволяет оценивать доступность при независимых отказах; для совместных отказов и оценки долговечности данных необходимы отдельные расширения.
Сценарные расчёты демонстрируют потенциальный выигрыш по ёмкости в заданных условиях и не являются экспериментальной проверкой целевого уровня готовности. Дальнейшая работа предполагает реализацию воспроизводимой имитационной модели и оценку предложенного правила управления при реалистичных отказах и нагрузке.
Рецензии:
28.10.2026, 9:21 Мирмович Эдуард Григорьевич
Рецензия: Серьёзной проблеме - отсутствие, разрыв в данных, попыткам их восстановления или адекватной замены их сам рецензент посвятил целый ряд работ, в т.ч. в рамках теории неопределённости и нечёткости. Одним из способов применялись нормальные и возмущённые функции распределения.
Данная работа посвящена подобной проблеме, но для других информационных объектов, касающихся выхода из строя части узлов или дисков крупной информационной системы. Способность такой системы сохранять целостность и доступность информации чаще всего обеспечивается применением кодов Рида–Соломона (RS(n, k). Правда, это реализовать на практике не очень легко. Автор подошёл к проблеме со своей креативной позиции и получил достойный результат. По теме работа обладает актуальностью и элементами научной значимости.
Замечания, устранение которых позволит автору получить абсолютно положительную рецензию.
Использованные источники адекватные и соответсвуют теме, но период их публикации от 15 до 25 лет назад приводят рецензента к негативным мыслям. Ведь более поздние работы не менее значимы и серьёзны, например: группа Карипжанова, работы Круглика, Михайлишина, Конкина, работы и диссертации Иваничкиной, Назарова, десятки работ зарубежных учёных последних лет. Без дополнения ссылок на работы хотя бы 2024 года, которых было достаточно и у нас, и за рубежом, статья сильно проигрывает и наводит на всякие сомнения. Работа в списке "Кодирование с исправлением ошибок (erasure coding) и репликация: количественное сравнение" под номером [5] относится к самым цитируемым в мире по данной проблеме, но в тексте ссылка на неё отсутствует. И в названии надо добавить букву "ю" в конце. После небольшой корректировки статья будет рекомендована к печати, а пока - нет.