Локально восстанавливаемые коды

Локально восстанавливаемые коды (LRC, Locally Recoverable Codes) — это класс корректирующих кодов, используемых в системах распределённого хранения данных, которые позволяют восстановить утерянный фрагмент информации (например, при отказе одного диска или узла в кластере) путём обращения к небольшому фиксированному числу других узлов (локальной группе), не требуя для этого полного декодирования всего закодированного массива. Основное отличие от классических кодов коррекции ошибок (например, кодов Рида — Соломона) заключается в минимизации объёма сетевого трафика и вычислительных затрат при восстановлении отдельных блоков данных, что критически важно для современных распределённых файловых систем и облачных хранилищ.

История

Концепция локально восстанавливаемых кодов была впервые формально предложена в 2012 году группой исследователей из Microsoft Research и Калифорнийского университета в Беркли (Патрик Гопала, Ли Хуан, Сергей Ятченко, Александр Варшавский и др.) в контексте оптимизации работы системы хранения Azure Storage. До этого в распределённых системах применялись либо простые схемы репликации (создание нескольких копий данных), либо классические коды коррекции ошибок, такие как коды Рида — Соломона (RS). Репликация обеспечивала высокую скорость восстановления, но требовала значительного избыточного объёма (например, трёхкратное увеличение занимаемого места). Коды RS, напротив, были экономичны по избыточности, но при отказе одного узла для восстановления требовали чтения данных с большого числа (k) других узлов, что создавало высокую сетевую нагрузку и задержки.

LRC стали компромиссным решением: они позволяют снизить количество узлов, участвующих в восстановлении, до 2–4 (вместо 10–20), сохраняя при этом умеренную избыточность. Первая промышленная реализация LRC была внедрена в системе Microsoft Azure Storage (известна как Azure LRC, позднее — Windows Azure Storage). Впоследствии LRC были адаптированы и в других системах: Facebook (ныне Meta — организация признана экстремистской и запрещена в РФ) использовала аналогичные коды в своей платформе хранения f4, а также в системах Apache Hadoop и Ceph.

Определение и основные понятия

Пусть исходные данные разбиты на k информационных блоков (фрагментов). Код LRC добавляет к ним m избыточных (чётных) блоков, формируя кодовое слово длины n = k + m. Ключевой характеристикой LRC является локальность (r) — минимальное количество блоков, которые необходимо прочитать для восстановления одного утерянного блока. В классическом коде Рида — Соломона локальность равна k (для восстановления одного блока нужно прочитать все k информационных блоков). В LRC локальность обычно составляет 2, 3 или 4, что существенно меньше k.

Дополнительно LRC обладают свойством локальной восстанавливаемости: для каждого блока данных существует некоторое подмножество других блоков (локальная группа) размером не более r, линейная комбинация которых даёт исходный блок. Код называется r-локально восстанавливаемым, если для любого из n блоков существует такое подмножество.

Классификация и виды

По структуре локальных групп

1. Коды с простой локальностью (Simple LRC) — каждый блок входит ровно в одну локальную группу, внутри которой используется простой код (например, XOR). Восстановление блока происходит по одному избыточному блоку группы.
2. Коды с перекрывающимися локальными группами (Overlapping LRC) — один блок может принадлежать нескольким группам, что повышает устойчивость к множественным отказам, но усложняет структуру.
3. Иерархические LRC — локальные группы объединяются в более крупные кластеры с дополнительными глобальными проверками, что позволяет балансировать между локальностью и избыточностью.

По типу используемых кодов

• XOR-базированные LRC — используют только операцию «исключающее ИЛИ» (XOR), что обеспечивает высокую скорость вычислений. Пример: коды с чётностью по строкам и столбцам (product codes).
• Коды на основе кодов Рида — Соломона — для глобальных проверок применяются коды RS, а для локальных — простые XOR-связки. Такая гибридная схема используется в Azure LRC.

По параметрам

Коды LRC характеризуются тройкой (k, r, d), где:

• k — число информационных блоков;
• r — локальность;
• d — минимальное кодовое расстояние (максимальное число отказов, которое код может гарантированно исправить).

Устройство и принцип работы

Структура кодового слова

Рассмотрим типичную схему LRC, используемую в Azure Storage. Исходные данные разбиваются на k блоков (например, k=6). К ним добавляются:

• m_local локальных избыточных блоков (по одному на каждую локальную группу). Например, если k=6 разбить на 2 группы по 3 блока, то добавляется 2 локальных чётных блока (каждый — XOR блоков своей группы).
• m_global глобальных избыточных блоков, вычисленных по всем k информационным блокам с помощью кода Рида — Соломона (например, 2 блока).

Общее число избыточных блоков m = m_local + m_global. В примере m=4, n=10. Локальность r = 3 (для восстановления блока из группы нужно прочитать 2 других блока группы и локальный чётный блок — всего 3 блока).

Процесс восстановления

1. При отказе одного узла (например, блока A1) система определяет его локальную группу.
2. Считываются все остальные блоки этой группы (A2, A3) и локальный чётный блок (P_A).
3. Вычисляется A1 = A2 XOR A3 XOR P_A.
4. Если отказало более одного блока в одной группе, используется глобальный избыточный блок (RS) для восстановления.

Параметры и границы

Существует теоретическая граница для LRC, называемая границей Синглтона для локально восстанавливаемых кодов: \[ d \le n - k - \left\lceil \frac{k}{r} \right\rceil + 2 \] Эта граница показывает, что при заданных n, k, r максимально возможное кодовое расстояние d ограничено. Коды, достигающие этой границы, называются оптимальными LRC.

Применение

Распределённые файловые системы

LRC активно применяются в крупных облачных хранилищах и распределённых файловых системах для снижения затрат на хранение и ускорения восстановления данных:

• Microsoft Azure Storage — использует LRC с параметрами (k=6, r=3, m_local=2, m_global=2) для хранения данных пользователей. Это позволило сократить избыточность с 200% (трёхкратная репликация) до 67% (коэффициент избыточности 1.67), при этом время восстановления одного блока уменьшилось в 5–10 раз по сравнению с кодами RS.
• **Facebook (продукт Meta, признанной экстремистской и запрещённой в РФ) f4 (Meta — организация признана экстремистской и запрещена в РФ)** — система хранения фотографий и видео использует LRC-подобные коды с локальностью 2 для быстрого восстановления блоков при отказах.
• Ceph — начиная с версии 12.0.0 (Luminous) поддерживает LRC в качестве одной из схем кодирования (erasure coding profile). Пользователь может задать параметры (k, m, l) где l — размер локальной группы.
• Apache Hadoop HDFS — в версии 3.0.0 добавлена поддержка LRC (коды с локальностью 2 и 3) для экономии места по сравнению с репликацией.

Сети хранения данных (SAN, NAS)

В системах хранения корпоративного уровня LRC используются для защиты данных на RAID-массивах нового поколения (например, RAID 6 с локальными чётностями). Это позволяет восстанавливать данные при отказе двух дисков без чтения всех дисков массива.

Системы резервного копирования

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

Преимущества и недостатки

Преимущества

• Низкая сетевая нагрузка при восстановлении — количество блоков, передаваемых по сети для восстановления одного отказа, мало (обычно 2–4), что уменьшает задержки и нагрузку на сеть.
• Экономия дискового пространства — по сравнению с репликацией (3x) LRC обеспечивает избыточность 1.5–2x, что даёт экономию 25–50% ёмкости.
• Высокая скорость восстановления — восстановление одного блока занимает миллисекунды, что критически важно для систем реального времени.
• Масштабируемость — LRC хорошо работают в кластерах с тысячами узлов.

Недостатки

• Сложность реализации — требуется точное проектирование локальных групп и глобальных проверок, а также учёт границ кодового расстояния.
• Ограниченная устойчивость к множественным отказам — при отказе более чем d блоков (минимальное кодовое расстояние) данные могут быть потеряны безвозвратно.
• Вычислительные затраты на кодирование — хотя локальные операции (XOR) быстры, глобальные (RS) требуют умножения в полях Галуа, что может быть ресурсоёмко при больших k.
• Необходимость в метаданных — для каждого блока нужно хранить информацию о его локальной группе и глобальных проверках, что увеличивает накладные расходы на управление.

Интересные факты

• Первое практическое применение LRC в Azure Storage позволило сократить количество сетевых запросов при восстановлении данных с 15–20 (для кодов RS) до 3–4, что снизило задержки восстановления с десятков секунд до нескольких миллисекунд.
• Существуют обобщения LRC, называемые кодами с локальностью и доступностью (Locally Recoverable Codes with Availability), где каждый блок может быть восстановлен несколькими непересекающимися наборами блоков, что повышает надёжность.
• В 2018 году группа исследователей из России (МГУ, ИППИ РАН) предложила новый класс LRC — коды с циклической локальностью, которые позволяют строить оптимальные коды для произвольных параметров.
• LRC являются частным случаем более общего класса кодов с локальностью (LRC), которые изучаются в теории кодирования с 2010-х годов. За последние 10 лет опубликовано более 500 научных статей по этой теме.

Критика и ограничения

Несмотря на широкое распространение, LRC не лишены критики. Основные замечания:

• Избыточность при малых k — для небольших файлов (например, менее 1 МБ) накладные расходы на метаданные и кодирование могут превышать выгоду от сжатия.
• Сложность обновления данных — при изменении одного блока приходится пересчитывать все локальные и глобальные проверки, что может быть затратно.
• Зависимость от топологии сети — эффективность LRC сильно зависит от того, как узлы сгруппированы физически (в одной стойке, в одном дата-центре). Неправильное размещение локальных групп может свести на нет преимущества.

Тем не менее, LRC остаются одним из наиболее эффективных инструментов для балансирования между стоимостью хранения и скоростью восстановления в современных распределённых системах.

Источники

1. Gopalan, P., Huang, L., Yatchenko, S., Varshavsky, A. (2012). On the Locality of Codeword Symbols. IEEE Transactions on Information Theory, 58(11), 6925–6934.
2. Huang, L., et al. (2012). Erasure Coding in Windows Azure Storage. Proceedings of the 2012 USENIX Annual Technical Conference.
3. Dimakis, A. G., et al. (2011). Network Coding for Distributed Storage Systems. IEEE Transactions on Information Theory, 57(7), 4539–4561.
4. Tamo, I., Barg, A. (2014). A Family of Optimal Locally Recoverable Codes. IEEE Transactions on Information Theory, 60(8), 4661–4676.
5. Microsoft Azure Documentation. Azure Storage Erasure Coding. (2016).
6. Ceph Documentation. Erasure Code Profiles. (2018).
7. Facebook Engineering Blog. f4: Facebook’s Warm BLOB Storage System. (2014).