company_banner

Коды избыточности: простыми словами о том, как надёжно и дёшево хранить данные


    Так выглядит избыточность


    Коды избыточности* широко применяются в компьютерных системах для увеличения надёжности хранения данных. В Яндексе их используют в очень многих проектах. Например, применение кодов избыточности вместо репликации в нашем внутреннем объектном хранилище экономит миллионы без снижения надёжности. Но несмотря на широкое распространение, понятное описание того, как работают коды избыточности, встречается очень редко. Желающие разобраться сталкиваются примерно со следующим (из Википедии):



    Меня зовут Вадим, в Яндексе я занимаюсь разработкой внутреннего объектного хранилища MDS. В этой статье я простыми словами опишу теоретические основы кодов избыточности (кодов Рида — Соломона и LRC). Расскажу, как это работает, без сложной математики и редких терминов. В конце приведу примеры использования кодов избыточности в Яндексе.


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


    * Под термином «коды избыточности» в статье подразумевается инженерный термин «erasure codes».


    1. Суть кодов избыточности


    Суть всех кодов избыточности предельно простая: хранить (или передавать) данные так, чтобы они не пропадали при возникновении ошибок (поломках дисков, ошибках передачи данных и т. д.).


    В большинстве* кодов избыточности данные разбиваются на n блоков данных, для них считается m блоков кодов избыточности, всего получается n + m блоков. Коды избыточности строятся таким образом, чтобы можно было восстановить n блоков данных, используя только часть из n + m блоков. Далее мы рассмотрим только блочные коды избыточности, то есть такие, в которых данные разбиваются на блоки.



    Чтобы восстановить все n блоков данных, нужно иметь минимум n из n + m блоков, так как нельзя получить n блоков, имея только n-1 блок (в этом случае пришлось бы 1 блок брать «из воздуха»). Достаточно ли n произвольных блоков из n + m блоков для восстановления всех данных? Это зависит от типа кодов избыточности, например коды Рида — Соломона позволяют восстановить все данные с помощью произвольных n блоков, а коды избыточности LRC — не всегда.


    Хранение данных


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


    Передача данных


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


    * Есть также коды избыточности, в которых данные не разбиваются на блоки, например коды Хэмминга и коды CRC, широко применяемые для передачи данных в сетях Ethernet. Это коды для помехоустойчивого кодирования, они предназначены для обнаружения ошибок, а не для их исправления (код Хэмминга также позволяет частично исправлять ошибки).


    2. Коды Рида — Соломона


    Коды Рида — Соломона — одни из наиболее широко распространённых кодов избыточности, изобретённые ещё в 1960-х и впервые получившие широкое применение в 1980-х для серийного выпуска компакт-дисков.


    Ключевых вопросов для понимания кодов Рида — Соломона два: 1) как создавать блоки кодов избыточности; 2) как восстанавливать данные с помощью блоков кодов избыточности. Найдем на них ответы.
    Для упрощения далее будем считать, что n=6 и m=4. Другие схемы рассматриваются по аналогии.


    Как создавать блоки кодов избыточности


    Каждый блок кодов избыточности считается независимо от остальных. Для подсчёта каждого блока используются все n блоков данных. На схеме ниже X1-X6 — блоки данных, P1–P4 — блоки кодов избыточности.



    Все блоки данных должны быть одинакового размера, для выравнивания можно использовать нулевые биты. Полученные блоки кодов избыточности будут иметь тот же размер, что и блоки данных. Все блоки данных разбиваются на слова (например, по 16 бит). Допустим, мы разбили блоки данных на k слов. Тогда все блоки кодов избыточности тоже будут разбиты на k слов.



    Для подсчёта i-го слова каждого блока избыточности будут использоваться i-е слова всех блоков данных. Они будут считаться по следующей формуле:



    Здесь значения x — слова блоков данных, p — слова блоков кодов избыточности, все альфа, бета, гамма и дельта — специальным образом подобранные числа, одинаковые для всех i. Сразу нужно сказать, что все эти значения — не обычные числа, а элементы поля Галуа, операции +, -, *, / — не привычные всем нам операции, а специальные операции, введённые над элементами поля Галуа.


    Зачем нужны поля Галуа



    Казалось бы, всё просто: разбиваем данные на блоки, блоки — на слова, с помощью слов блоков данных считаем слова блоков кодов избыточности — получаем блоки кодов избыточности. В целом это так и работает, но дьявол в деталях:


    1. Как сказано выше, размер слова — фиксированный, в нашем примере 16 бит. Формулы выше для кодов Рида — Соломона таковы, что при использовании обычных целых чисел результат вычисления p может быть не представим с помощью слова допустимого размера.
    2. При восстановлении данных формулы выше будут рассматриваться как система уравнений, которую нужно решить, чтобы восстановить данные. В процессе решения может появиться необходимость выполнить деление целых чисел друг на друга, результатом чего будет вещественное число, которое нельзя точно представить в памяти компьютера.

    Эти проблемы не позволяют использовать для кодов Рида — Соломона целые числа. Решение проблемы оригинальное, его можно описать следующим образом: давайте придумаем специальные числа, которые можно представить с помощью слов нужной длины (например, 16 бит), и результат выполнения всех операций над которыми (сложение, вычитание, умножение, деление) также будет представлен в памяти компьютера при помощи слов нужной длины.


    Такие «специальные» числа давно изучает математика, их называют полями. Поле — это множество элементов с определёнными для них операциями сложения, вычитания, умножения и деления.


    Поля Галуа* — это поля, для которых существует и единственен результат каждой операции (+, -, *, /) для любых двух элементов поля. Поля Галуа можно построить для чисел, являющихся степенью 2: 2, 4, 8, 16 и т. д. (на самом деле степенью любого простого числа p, но на практике нас интересуют только степени 2). Например, для слов размером 16 бит это поле, содержащее 65 536 элементов, для каждой пары которых можно найти результат любой операции (+, -, *, /). Значения x, p, альфа, бета, гамма, дельта из уравнений выше для расчётов будут считаться элементами поля Галуа.


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


    * Это не строгое определение, скорее описание.


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


    Восстановление нужно тогда, когда из n + m блоков часть блоков отсутствует. Это могут быть как блоки данных, так и блоки кодов избыточности. Отсутствие блоков данных и/или блоков кодов избыточности будет означать, что в уравнениях выше неизвестны соответствующие переменные x и/или p.


    Уравнения для кодов Рида — Соломона можно рассматривать как систему уравнений, в которых все значения альфа, бета, гамма, дельта — константы, все x и p, соответствующие доступным блокам, — известные переменные, а остальные x и p — неизвестные.


    Например, пусть блоки данных 1, 2, 3 и блок кодов избыточности 2 недоступны, тогда для i-й группы слов будет следующая система уравнений (неизвестные отмечены красным):



    Мы имеем систему из 4 уравнений с 4 неизвестными, значит можем решить её и восстановить данные!


    Из этой системы уравнений следуют ряд выводов про восстановление данных для кодов Рида — Соломона (n блоков данных, m блоков кодов избыточности):


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

    Что ещё нужно знать


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


    • Система уравнений для кодов Рида — Соломона должна иметь (единственное) решение при любых комбинациях неизвестных (не более m неизвестных). Исходя из этого требования подбираются значения альфа, бета, гамма и дельта.
    • Систему уравнений нужно уметь автоматически строить (в зависимости от того, какие блоки недоступны) и решать.
    • Нужно построить поле Галуа: для заданного размера слова уметь находить результат любой операции (+, -, *, /) для любых двух элементов.

    В конце статьи есть ссылки на литературу по этим важным вопросам.


    Выбор n и m


    Как на практике выбрать n и m? На практике в системах хранения данных коды избыточности используют для экономии места, поэтому m выбирают всегда меньше n. Их конкретные значения зависят от ряда факторов, в том числе:


    • Надёжность хранения данных. Чем больше m, тем большее количество отказов дисков можно пережить, то есть выше надёжность.
    • Избыточность хранения. Чем выше соотношение m / n, тем выше будет избыточность хранения, и тем дороже будет стоить система.
    • Время обработки запросов. Чем больше сумма n + m, тем дольше будет время ответа на запросы. Так как для чтения данных (во время восстановления) нужно прочитать n блоков, хранящихся на n разных дисках, то время чтения будет определяться самым медленным диском.

    Кроме того, хранение данных в нескольких ДЦ накладывает дополнительные ограничения на выбор n и m: при отключении 1 ДЦ данные всё ещё должны быть доступны для чтения. Например, при хранении данных в 3 ДЦ должно выполняться условие: m >= n/2, в противном случае возможна ситуация, когда данные недоступны для чтения при отключении 1 ДЦ.


    3. LRC — Local Reconstruction Codes


    Для восстановления данных с помощью кодов Рида — Соломона приходится использовать n произвольных блоков данных. Это очень существенный минус для распредёленных систем хранения данных, ведь для восстановления данных на одном сломанном диске придётся читать данные с большинства остальных, создавая большую дополнительную нагрузку на диски и сеть.


    Наиболее часто встречающиеся ошибки — недоступность одного блока данных из-за поломки или перегруженности одного диска. Можно ли как-то уменьшить избыточную нагрузку для восстановления данных в таком (наиболее частом) случае? Оказывается, можно: специально для этого существуют коды избыточности LRC.


    LRC (Local Reconstruction Codes) — коды избыточности, придуманные в Microsoft для применения в Windows Azure Storage. Идея LRC максимально проста: разбить все блоки данных на две (или более) группы и считать часть блоков кодов избыточности для каждой группы по отдельности. Тогда часть блоков кодов избыточности будет подсчитана с помощью всех блоков данных (в LRC они называются глобальными кодами избыточности), а часть — с помощью одной из двух групп блоков данных (они называются локальными кодами избыточности).


    LRC обозначается тремя числам: n-r-l, где n — количество блоков данных, r — количество глобальных блоков кодов избыточности, l — количество локальных блоков кодов избыточности. Для чтения данных при недоступности одного блока данных нужно прочитать только n/l блоков — это в l раз меньше, чем в кодах Рида — Соломона.


    Для примера рассмотрим схему LRC 6-2-2. X1–X6 — 6 блоков данных, P1, P2 — 2 глобальных блока избыточности, P3, P4 — 2 локальных блока избыточности.



    Блоки кодов избыточности P1, P2 считаются с помощью всех блоков данных. Блок кодов избыточности P3 — с помощью блоков данных X1–X3, блок кодов избыточности P4 — с помощью блоков данных X4–X6.


    Остальное делается в LRC по аналогии с кодами Рида — Соломона. Уравнения для подсчёта слов блоков кодов избыточности будут такими:



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


    Из системы уравнений для LRC следует ряд выводов:


    • Для восстановления любого 1 блока данных достаточно прочитать n/l блоков (n/2 в нашем примере).
    • Если недоступно r + l блоков, и при этом все блоки входят в одну группу, то данные восстановить нельзя. Это легко объяснить на примере. Пусть недоступны блоки X1–X3 и P3: это r + l блоков из одной группы, 4 в нашем случае. Тогда у нас есть система из 3 уравнений с 4 неизвестными, которую нельзя решить.
    • Во всех остальных случаях недоступности r + l блоков (когда из каждой группы доступен хотя бы один блок) данные в LRC можно восстановить.

    Таким образом, LRC выигрывает у кодов Рида — Соломона в восстановлении данных после одиночных ошибок. В кодах Рида — Соломона для восстановления даже одного блока данных нужно использовать n блоков, а в LRC для восстановления одного блока данных достаточно использовать n/l блоков (n/2 в нашем примере). С другой стороны, LRC проигрывает кодам Рида — Соломона по максимальному количеству допустимых ошибок. В примерах выше коды Рида — Соломона могут восстановить данные при любых 4 ошибках, а для LRC существует 2 комбинации из 4 ошибок, когда данные восстановить нельзя.


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


    4. Другие коды избыточности


    Помимо кодов Рида — Соломона и LRC, есть много других кодов избыточности. Разные коды избыточности используют разную математику. Вот некоторые другие коды избыточности:


    • Код избыточности с помощью оператора XOR. Операция XOR выполняется над n блоками данных, и получается 1 блок кодов избыточности, то есть схема n+1 (n блоков данных, 1 код избыточности). Используется в RAID 5, где блоки данных и кодов избыточности циклически записываются на все диски массива.
    • Алгоритм even-odd, основанный на операции XOR. Позволяет построить 2 блока кодов избыточности, то есть схема n+2.
    • Алгоритм STAR, основанный на операции XOR. Позволяет построить 3 блока кодов избыточности, то есть схема n+3.
    • Pyramide codes — ещё одни коды избыточности от Microsoft.

    5. Использование в Яндексе


    Ряд инфраструктурных проектов Яндекса применяет коды избыточности для надёжного хранения данных. Вот несколько примеров:


    • Внутреннее объектное хранилище MDS, о котором я писал в начале статьи.
    • YT — MapReduce-система Яндекса.
    • YDB (Yandex DataBase) — распределённая база данных newSQL.

    В MDS используются коды избыточности LRC, схема 8-2-2. Данные с кодами избыточности пишутся на 12 разных дисков в разных серверах в 3 разных ДЦ: по 4 сервера в каждом ДЦ. Подробнее об этом читайте в статье.


    В YT используются как коды Рида — Соломона (схема 6-3), которые были реализованы первыми, так и коды избыточности LRC (схема 12-2-2), причём LRC — предпочтительный способ хранения.


    В YDB используются коды избыточности, основанные на even-odd (схема 4-2). Про коды избыточности в YDB уже рассказывали на Highload.


    Применение разных схем кодов избыточности обусловлено разными требованиями, предъявляемыми к системам. Например, в MDS данные, хранимые с помощью LRC, размещаются сразу в 3 ДЦ. Нам важно, чтобы данные оставались доступными для чтения при выходе из строя 1 любого ДЦ, поэтому блоки должны быть распределены по ДЦ так, чтобы при недоступности любого ДЦ количество недоступных блоков было не больше допустимого. В схеме 8-2-2 можно разместить по 4 блока в каждом ДЦ, тогда при отключении любого ДЦ будет недоступно 4 блока, и данные можно будет читать. Какую бы схему мы ни выбрали при размещении в 3 ДЦ, в любом случае должно быть (r + l) / n >= 0,5, то есть избыточность хранения будет минимум 50%.


    В YT ситуация другая: каждый кластер YT целиком располагается в 1 ДЦ (разные кластеры в разных ДЦ), поэтому там нет такого ограничения. Схема 12-2-2 даёт избыточность 33%, то есть хранить данные выходит дешевле, при этом они также могут переживать до 4 одновременных отключений дисков, как и схема в MDS.


    Есть ещё много особенностей применения кодов избыточности в системах хранения и обработки данных: нюансы восстановления данных, влияние восстановления на время выполнения запросов, особенности записи данных и т. д. Я собираюсь отдельно рассказать об этих и других особенностях применения кодов избыточности на практике, если тема будет интересна.


    6. Ссылки


    1. Серия статей про коды Рида — Соломона и поля Галуа: https://habr.com/ru/company/yadro/blog/336286/
      https://habr.com/ru/company/yadro/blog/341506/
      В них доступным языком глубже рассматривается математика.
    2. Статья от Microsoft про LRC: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/LRC12-cheng20webpage.pdf
      В разделе 2 кратко объясняется теория, далее рассматривается опыт применения LRC на практике.
    3. Схема even-odd: https://people.eecs.berkeley.edu/~kubitron/courses/cs262a-F12/handouts/papers/p245-blaum.pdf
    4. Схема STAR: https://www.usenix.org/legacy/event/fast05/tech/full_papers/huang/huang.pdf
    5. Pyramid codes: https://www.microsoft.com/en-us/research/publication/pyramid-codes-flexible-schemes-to-trade-space-for-access-efficiency-in-reliable-data-storage-systems/
    6. Коды избыточности в MDS: https://habr.com/ru/company/yandex/blog/311806
    7. Коды избыточности в YT: https://habr.com/ru/company/yandex/blog/311104/
    8. Коды избыточности в YDB: https://www.youtube.com/watch?v=dCpfGJ35kK8
    Яндекс
    Как мы делаем Яндекс

    Комментарии 32

      0

      Забавно, очень много Азуры с закрытыми сырцами и ни слова про ceph, у которого всё это есть (включая локальные коды избыточности) и есть сырцы, которые можно почитать.

        0

        Правильно ли я понимаю, что в данном случае не только можно восстановить данные на сломавшемся носителе, но и задетектить случай, когда носитель как бы нормальный, работает, но данные испортил? Ну или если кто-то ещё подгадил: ошибка передачи по сети, глючное железо и т.д.

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

          На практике в системах хранения данных коды избыточности используют только для восстановления, а для обнаружения ошибок используют контрольные суммы. Например, вместе с каждым блоком может храниться его контрольная сумма (md5, sha256 и т.п.). Перед чтением данных контрольная сумма считается повторно. Если она не совпадает с сохраненной, значит данные повреждены.

          Для передачи данных по сети, как правило, используется помехоустойчивое кодирование: вместе с данными отправляется корректирующий код, с помощью которого можно обнаружить и в некоторых случаях исправить ошибки.
            +6
            Теоретически с помощью кодов избыточности можно обнаружить ошибки, если сравнить исходный блок данных с блоком данных, полученным с помощью восстановления. Но для этого нужно определить, какой блок сравнивать.
            Ну вот неправильно.
            Ниже я уже написал, в русском языке правильный термин «избыточное кодирование». Степень избыточности позволяет контролировать целостность данных и/или восстанавливать ошибки. Бит четности — тоже избыточное кодирование, позволяющее обнаружить наличие нечетного кол-ва битовых ошибок. Код Хемминга позволяет исправить одну и обнаружить две ошибки. А дальше, блочные, цикличиские…
            Для передачи данных по сети, как правило, используется помехоустойчивое кодирование: вместе с данными отправляется корректирующий код, с помощью которого можно обнаружить и в некоторых случаях исправить ошибки.

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

            Извините, но может математика у вас в статье и правильная, но теория у вас какая-то спутанная.
              –1
              Например, для слов размером 16 бит это поле, содержащее 65 536 элементов, для каждой пары которых можно найти результат любой операции (+, -, *, /). Значения x, p, альфа, бета, гамма, дельта из уравнений выше для расчётов будут считаться элементами поля Галуа.

              1. Не для каждой пары и любой операции можно найти результат.
              2. Нельзя просто взять значение и сказать, что оно принадлежит полю.
                0
                Под термином «коды избыточности» я подразумеваю термин «erasure codes», причем как инженерный термин, а не строгое теоретическое понятие, имеющее четкое определение. Добавил это в начало статьи, чтобы не было терминологической путаницы.

                Название «коды избыточности» прижилось у нас исторически.
                Название «erasure codes», конечно, используется чаще. Но и «код(ы) избыточности» иногда употребляют.
                  0
                  Если погуглить фразу «код избыточности», то высветится только одна единственная ссылка, которую вы почему приводите в качестве доказательства ее широкого использования. Т.е. человек то ли из-за косноязычия, то ли по незнанию, исковеркал стандартный термин «избыточные коды» и вы теперь с упорством, достойным лучшего применения, за ним повторяете и наглухо игнорируете многократные указания на некорректность этого новояза.

                  Если вы хотите, чтобы люди вас понимали, не используйте локально придуманные термины, даже если они прижились у вас в отделе.
                    +1
                    Странно, что 4 года назад к этому термину ни у кого вопросов не было :)
                      0
                      Мне кажется это обусловлено тем, что в данном человек замахнулся на то, чтобы «разжевать» серезную теорию с устояшейся терминологией. В конечном итоге, получилось, что человек нахватался чего-то по верхам, многого просто не понял, да еще и привнес какой-то своей доморощенной терминологии, в которой в итоге сам и запутался.
                      В старой статье человек сделал акцент на описании решений, применяемых в яндексе без претензии на популяризицию теории кодирования. В этом случае искажение терминологии выглядит как незначительный огрех, на который можно закрыть глаза.
                    0
                    В моей дипломной работе, я использовал термины «коды с коррекцией ошибок» и «самовосстанавливающиеся коды»
              +4
              Может все-таки «избыточное кодирование»?
                –2
                • Как сказано выше, размер слова — фиксированный, в нашем примере 16 бит. Формулы выше для кодов Рида — Соломона таковы, что при использовании обычных целых чисел результат вычисления p может быть не представим с помощью слова допустимого размера.
                • При восстановлении данных формулы выше будут рассматриваться как система уравнений, которую нужно решить, чтобы восстановить данные. В процессе решения может появиться необходимость выполнить деление целых чисел друг на друга, результатом чего будет вещественное число, которое нельзя точно представить в памяти компьютера.

                Простите, если вы не знаете, обратитесь к тому, кто знает.
                Зачем писать отсебятину?
                Как вы же сами и сказали, все 4 операции это не «классические» операции сложения/вычитания/умножения/деления, а операции над полем Галуа (которые, тем не менее, обладают почти всеми привычными нам с детства свойствами). Соответственно, слова «В процессе решения может появиться необходимость выполнить деление целых чисел друг на друга, результатом чего будет вещественное число, которое нельзя точно представить в памяти компьютера» никакого отношения к реальности в контексте кодов Рида-Соломона иметь не могут (как и слова про представимость с помощью слова допустимого размера)
                  +2
                  Эти два пункта объясняют, какие проблемы возникнут, если попробовать использовать целые числа. Из-за них нельзя использовать целые числа для кодов Рида — Соломона, а нужно использовать элементы поля Галуа. Об этом я пишу в тексте сразу за названными проблемами:

                  Эти проблемы не позволяют использовать для кодов Рида — Соломона целые числа


                    0

                    А приведите, может быть, пример тогда таких полей Галуа? Не обязательно для 65536 элементов, а вот, скажем, для 8. А то «ядра — чистый изумруд» получается.

                      +1
                      Этому примеру посвящена короткая статья на Хабре. В ней как раз рассматривается поле из 8 элементов GF(2^3).
                      В качестве введения в тему также можно использовать другую статью.

                      Поля Галуа — достаточно сложная тема, которую не получится объяснить в двух словах, или привести короткий понятный пример.

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

                      Например, можно использовать популярную библиотеку Jerasure для построения кодов избыточности (кодирования) и восстановления данных (декодирования). Решение систем уравнений (которые представляются в виде матричных уравнений), арифметика полей Галуа — это будет выполняться на уровне библиотеки.
                        0
                        Поля Галуа — достаточно сложная тема, которую не получится объяснить в двух словах, или привести короткий понятный пример.

                        Мда? Поля Галуа — это просто другое название для конечных полей. Берёте любое простое число (например, 3) и рассматривайте остатки по его модулю — т.е. числа 0, 1, 2. Операции сложения и умножения в этом поле — обычные операции над числами, только берутся по модулю 3.
                        Если брать не простой модуль то ситуация несколько сложнее.
                          0
                          Выше нужно было написать «нетривиальный пример» для полей GF(2^k), которые в основном используются.
                            –2

                            Поле Галуа устроено довольно просто:


                            1. Берется кольцо вычетов по простому модулю p. В Данном случае по модулю 2.
                            2. Берется неприводимый многочлен степени k над данным полем. Например x^3+x+1.
                            3. Берется кольцо вычетов по модулю данного многочлена.

                            Таким образов получается поле Галуа из 8 элементов.
                            Элементы поля — многочлены с коэффициентами из Z_2 степени не выше k.
                            Сложение и умножение многочленов выполняется по модулю x^3+x+1, а сложение и умножение их коэффициентов — по модулю 2.

                      0
                      1) Элементы поля Галуа и целые числа — это не взаимоисключающие понятия.
                      2) Поле Галуа определяется множеством элементов, набором операций и аксиомами поля. Так вот это множество как раз состоит из целых чисел, а операции сложения, умножения и деления в поле всегда дают точный результат в виде элемента этого же поля — целого числа.

                      И, кстати, операция XOR — это не какой-то отдельный метод кодирования, а простой
                      оператор, широко используемый во всех упомянутых вами методах.

                      Мне кажется вам стоит поглубже прокачаться в теории.

                        0
                        Да, этот момент я упустил — гнев застлил глаза и чтение статьи остановилось.
                        Прошу прощения!
                        Однако, выше другими собеседниками приводится более конструктивная критика этого фрагмента текста
                      0
                      Время обработки запросов. Чем больше сумма n + m, тем дольше будет время ответа на запросы. Так как для чтения данных (во время восстановления) нужно прочитать n блоков, хранящихся на n разных дисках, то время чтения будет определяться самым медленным диском.

                      Но ведь чем больше n, тем меньше блоков с каждого диска нужно прочитать. А значит среднее время чтения будет меньше.
                        +2
                        Время чтения зависит от способа записи данных и режима работы (нормальный, когда все блоки данных доступны, или восстановление, когда часть блоков данных недоступна).

                        1. Если каждый ключ с данными разбивать на части и записывать сразу на все диски, то для чтения ключа нужно будет читать сразу с n дисков. В нормальном режиме чтение будет с n дисков с блоками данных, в режиме восстановления — с n дисков, часть из которых — диски с блоками данных, а часть — диски с блоками кодов избыточности. Читать с разных дисков можно параллельно, поэтому время чтения всего ключа будет определяться временем чтения с самого медленного диска. Чем больше будет n, тем сильнее будет увеличиваться общее время чтения ключа с данными (в среднем).

                        2. Можно записывать ключи с данными по-другому: брать некоторое количество ключей, формировать из них последовательность, и уже эту последовательность разбивать на части, дополнять кодами избыточности и записывать на разные диски. В этом случае многие ключи будут целиком располагаться на 1 диске, и чтения будут в среднем выполняться быстрее. Однако, если диск, где хранятся данные, будет недоступен, то для восстановления данных придется делать восстановление, а для этого читать из n дисков (n/l в случае LRC). То есть время чтения будет больше, если нужно восстанавливать данные.

                        Обе схемы успешно используются на практике, а выбор схемы зависит сразу от ряда факторов. В первой схеме, например, ключи можно записывать независимо, а во второй нужно будет накапливать достаточное количество ключей, и записывать их пачками. С другой стороны, в первой схеме нужно хранить больше служебной информации на дисках, что может сильно увеличивать стоимость хранения маленьких ключей.
                        +1
                        IMHO более наглядно было бы представить операции кодирования-декодирования не в виде «ботвы» из систем уравнений — а виде умножений на порождающую и проверочную матрицы соответственно.
                          +1

                          В начале приводится скриншот с Википедии с этими формулами-кракозябрами. Ну, думаю, наконец объяснят на контрасте всё простым языком. И далее по тексту снова всякие формулы и скобки… -_-

                            0
                            Совсем без формул, к сожалению, не получится разобраться в теме.
                            +1
                            "* В англоязычной литературе коды избыточности часто называют erasure codes."

                            И тут вы неправы. Erasure Code — это всего лишь частный случай кодирования, который позволяет восстанавливать пакетные потери данных, когда известно положение этого «выпавшего» пакета.

                            На мой взгляд данная статья скорее вредна, чем полезна, т.к. формирует путаницу и дезинформацию в головах новичков.
                              +3
                              Да вроде нормальная статья, но её можно слегка сократить:
                              0. Коды избыточности занимают меньше места, чем цельная копия.
                              1. При помощи систем уравнений можно строить подходящее кол-во блоков избыточности.
                              2. Разбив данные на несколько пачек — можно считать для них коды избыточности отдельно.
                              3. Готовые библиотеки за вас всё посчитают, детали вам в принципе не нужны.
                              Детальные формулы есть на википедии.
                              +2
                              Возможно еще одна хорошая ссылка для желающих с любой степенью глубины познакомится с кодами:
                              «Коды, исправляющие ошибки» Питерсон У., Уэлдон Э. издательство Мир.
                                +1
                                Коды Хэмминга и Рида-Соломона, частные случаи БЧХ кода. Собственно большинство кодов Рида-Соломона с фиксированными размерами были получены подставляя те или иные коффициенты в БЧХ код.
                                Но чистый мат аппарат БЧХ кодов, это отдельная книга в целом.
                                Отдельно стоит упомянуть, что добавления блоков избыточности и их вычисление, куда более простая операция, чем восстановление превоначальных данных, имея на руках коды избыточности.
                                  –2
                                  Автор отвечает только на критику в той теме, где он что-то понимает. Ему не интересно, что «код избыточности» даже не гуглится. Он уверен в своей математике. И мы ему ничего не докажем. Он просто пришел в этот проект(в яндексе). Зачем тратиться.
                                  Отдельно стоит упомянуть, что добавления блоков избыточности и их вычисление, куда более простая операция, чем восстановление превоначальных данных, имея на руках коды избыточности.
                                  Стоит упомянуть, что это все относительно размера слова, на 8 битах все легко, но вот когда размер слова измеряется килобайтами становится весело.
                                  Просто, ТС не упомянул, что в любых системах хранениях данных HDD/SDD и так применяется избыточное кодирование на аппаратном уровне и им (в яндексе) нужно примемять что-то сверху, и собственно им нужно немного по-другому подходить к вопросу потому, что у них выпадают целые «железные» блоки (известного размера), и я думаю, что там можно упростить математику. Но, что я могу помнить из лекций, как связист…
                                    +2
                                    Выше ответил на Вашу критику. Насколько я понимаю, она касается терминологии.
                                  0

                                  Хорошая книга по теории помехоустойчивого кодирования с примерами:
                                  Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгортмы, применение.
                                  Моя настольная книга по ECC.

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                  Самое читаемое