Что такое избыточность файла

Обновлено: 15.01.2025

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

Избыточность RAID-массива

Избыточность RAID-массива – пожалуй, самый распространённый вид избыточности. RAID расшифровывается как «redundant array of independent disks» (избыточный массив независимых дисков), это значит, что в большинстве конфигураций диски так или иначе зеркалируют друг друга.

Зеркальный массив RAID 1 – базовая реализация избыточности RAID. Он состоит из нескольких (как правило, двух) дисков, которые полностью копируют друг друга. Если один из дисков выходит из строя, вся поддержка, обслуживание и запись данных выполняется вторым диском. Такой массив позволяет ускорить операции чтения, поскольку система может читать данные с любого диска.

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

Блочная избыточность

Следующий вид избыточности – зеркалирование целых блочных структур. Для этого используется DRBD (distributed replicated block device).

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

Репликация SQL

При работе с базами данных SQL (MySQL, MariaDB, PostgreSQL и т.п.) можно использовать их встроенные функции репликации, чтобы обеспечить отказоустойчивость в случае сбоя основного сервера.

Репликация по типу Master-Slave

Это, пожалуй, самый базовый вид репликации данных SQL. В такой настройке есть один главный сервер, который называется ведущим, или master-сервером. Этот сервер отвечает за все операции записи и обновления данных. Затем данные с этого сервера копируются на ведомый сервер (или slave-сервер).

Эта настройка позволяет распределить операции чтения между несколькими машинами, что может значительно улучшить производительность приложения.

Конечно, увеличение производительности является важным преимуществом; однако не менее важно то, что такая репликация повышает отказоустойчивость. Если master-сервер по какой-либо причине недоступен, операции чтения могут выполняться на серверах slave. Более того, slave-сервер можно перенастроить в master-сервер в случае, если предыдущий master недоступен в течение длительного периода.

Именно на примере репликации master-slave можно увидеть, как репликация данных и резервное копирование могут дополнять друг друга. При такой настройке можно реплицировать данные от ведущего сервера к ведомому. Затем можно временно отключить репликацию, чтобы сохранить данные на slave-сервере в согласованном состоянии, и создать резервную копию базы данных при помощи любого удобного механизма

Примечание: Подробнее о настройке репликации данных по типу master-slave можно прочесть в руководствах:

Репликация по типу master-master

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

Таким образом, если один сервер выходит из строя, то другой может еще и принимать запросы. Конечно, такая конфигурация сложнее, зато она гораздо отказоустойчивее, ведь в случае сбоя не нужно перенастраивать серверы (как при репликации master-slave).

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

Примечание: Подробнее о настройке репликации master-master можно прочесть здесь.

Распределение как альтернатива избыточности

Распределенные системы обладают многими преимуществами традиционных настроек избыточности.

Ранее в данном руководстве упоминались RAID-массивы, в частности RAID 1. Ещё один распространённый массив – это RAID 5. Он распределяет данные между несколькими накопителями, а также ведёт контроль по чётности. Информация о чётности хранится на отдельном контрольном диске. Это означает, что в случае отказа одного из дисков любая транзакция может быть восстановлена путём объединения информации о четности на других дисках.

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

В качестве примера можно привести Riak; это распределенная база данных. Ноды Riak работают точно так же. Между ними нет отношений типа ведущий-ведомый. Объекты, хранящиеся в базе данных, реплицируются.

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

Другим хорошим примером этого подхода является распределённая БД Cassandra. Она основана на тех же принципах, что и Riak, но реализована немного иначе.

Примечание: В следующих статьях можно найти дополнительную информацию по распределённым БД:

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Каждый блок кодов избыточности считается независимо от остальных. Для подсчёта каждого блока используются все n блоков данных. На схеме ниже X₁-X₆ — блоки данных, P₁–P₄ — блоки кодов избыточности.

Все блоки данных должны быть одинакового размера, для выравнивания можно использовать нулевые биты. Полученные блоки кодов избыточности будут иметь тот же размер, что и блоки данных. Все блоки данных разбиваются на слова (например, по 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 ДЦ.

Для восстановления данных с помощью кодов Рида — Соломона приходится использовать 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. X₁–X₆ — 6 блоков данных, P₁, P₂ — 2 глобальных блока избыточности, P₃, P₄ — 2 локальных блока избыточности.

Блоки кодов избыточности P₁, P₂ считаются с помощью всех блоков данных. Блок кодов избыточности P₃ — с помощью блоков данных X₁–X₃, блок кодов избыточности P₄ — с помощью блоков данных X₄–X₆.

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

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

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

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

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

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

Помимо кодов Рида — Соломона и 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.

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

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

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

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

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

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

Обнаружение ошибок в технике связи — действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок) — процедура восстановления информации после чтения её из устройства хранения или канала связи.

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

Содержание

Способы борьбы с ошибками

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

В системах связи возможны несколько стратегий борьбы с ошибками:

• обнаружение ошибок в блоках данных и автоматический запрос повторной передачи повреждённых блоков — этот подход применяется в основном на канальном и транспортном уровнях;
• обнаружение ошибок в блоках данных и отбрасывание повреждённых блоков — такой подход иногда применяется в системах потокового мультимедиа, где важна задержка передачи и нет времени на повторную передачу;
• исправление ошибок (forward error correction) применяется на физическом уровне.

Коды обнаружения и исправления ошибок

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

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

Блоковые коды

Пусть кодируемая информация делится на фрагменты длиной k бит, которые преобразуются в кодовые слова длиной n бит. Тогда соответствующий блоковый код обычно обозначают . При этом число " width="" height="" />
называется скоростью кода.

Если исходные k бит код оставляет неизменными, и добавляет n − k проверочных, такой код называется систематическим, иначе несистематическим.

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

• способность исправлять как можно большее число ошибок,
• как можно меньшая избыточность,
• простота кодирования и декодирования.

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

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

Линейные коды общего вида

Линейный блоковый код — такой код, что множество его кодовых слов образует k -мерное линейное подпространство (назовём его C ) в n -мерном линейном пространстве, изоморфное пространству k -битных векторов.

Это значит, что операция кодирования соответствует умножению исходного k -битного вектора на невырожденную матрицу G , называемую порождающей матрицей.

Пусть " width="" height="" />
— ортогональное подпространство по отношению к C , а H — матрица, задающая базис этого подпространства. Тогда для любого вектора \in C" width="" height="" />
справедливо:

Минимальное расстояние и корректирующая способность

Расстоянием Хемминга (метрикой Хемминга) между двумя кодовыми словами " width="" height="" />
и " width="" height="" />
называется количество отличных бит на соответствующих позициях, ,\;\overrightarrow)=\sum_s<|u^-v^|>" width="" height="" />
, что равно числу «единиц» в векторе \oplus\overrightarrow" width="" height="" />
.

является важной характеристикой линейного блокового кода. Она показывает насколько «далеко» расположены коды друг от друга. Она определяет другую, не менее важную характеристику — корректирующую способность:

, округляем «вниз», так чтобы 2t < d_min .

Таким образом получив искажённый код из A_t декодер принимает решение, что был исходный код A , исправляя тем самым не более t ошибок.

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

Коды Хемминга

=\overrightarrowH^T" width="" height="" />
, где " width="" height="" />
— принятый вектор, будет равен номеру позиции, в которой произошла ошибка. Это свойство позволяет сделать декодирование очень простым.

Общий метод декодирования линейных кодов

Любой код (в том числе нелинейный) можно декодировать с помощью обычной таблицы, где каждому значению принятого слова _i" width="" height="" />
соответствует наиболее вероятное переданное слово _i" width="" height="" />
. Однако, данный метод требует применения огромных таблиц уже для кодовых слов сравнительно небольшой длины.

Для линейных кодов этот метод можно существенно упростить. При этом для каждого принятого вектора _i" width="" height="" />
вычисляется синдром _i=\overrightarrow_i H^T" width="" height="" />
. Поскольку _i=\overrightarrow_i+\overrightarrow_i" width="" height="" />
, где _i" width="" height="" />
— кодовое слово, а _i" width="" height="" />
— вектор ошибки, то _i=\overrightarrow_i H^T" width="" height="" />
. Затем с помощью таблицы по синдрому определяется вектор ошибки, с помощью которого определяется переданное кодовое слово. При этом таблица получается гораздо меньше, чем при использовании предыдущего метода.

Линейные циклические коды

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

является кодовым словом, то его циклическая перестановка также является кодовым словом.

Слова циклического кода удобно представлять в виде многочленов. Например, кодовое слово =(v_0,\;v_1,\;\ldots,\;v_)" width="" height="" />
представляется в виде полинома x^" width="" height="" />
. При этом циклический сдвиг кодового слова эквивалентен умножению многочлена на x по модулю x n − 1 .

В дальнейшем, если не указано иное, мы будем считать, что циклический код является двоичным, то есть могут принимать значения 0 или 1.

Порождающий (генераторный) полином

Можно показать, что все кодовые слова конкретного циклического кода кратны определённому порождающему полиному g(x) . Порождающий полином является делителем x n − 1 .

С помощью порождающего полинома осуществляется кодирование циклическим кодом. В частности:

.

Коды CRC

Коды CRC (cyclic redundancy check — циклическая избыточная проверка) являются систематическими кодами, предназначенными не для исправления ошибок, а для их обнаружения. Они используют способ систематического кодирования, изложенный выше: «контрольная сумма» вычисляется путем деления x n − k u(x) на g(x) . Ввиду того, что исправление ошибок не требуется, проверка правильности передачи может производиться точно так же.

Таким образом, вид полинома g(x) задаёт конкретный код CRC. Примеры наиболее популярных полиномов:

название кода	степень	полином
CRC-12	12	x 12 + x 11 + x 3 + x 2 + x + 1
CRC-16	16	x 16 + x 15 + x 2 + 1
CRC-x 16 + x 12 + x 5 + 1
CRC-32	32	x 32 + x 26 + x 23 + x 22 + x 16 + x 12 + x 11 + x 10 + x 8 + x 7 + x 5 + x 4 + x 2 + x + 1

Коды БЧХ

Коды Боуза — Чоудхури — Хоквингема (БЧХ) являются подклассом циклических кодов. Их отличительное свойство — возможность построения кода БЧХ с минимальным расстоянием не меньше заданного. Это важно, потому что, вообще говоря, определение минимального расстояния кода есть очень сложная задача.

Математически полинома g(x) на множители в поле Галуа.

Коды коррекции ошибок Рида — Соломона

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

Математически коды Рида — Соломона являются кодами БЧХ.

Преимущества и недостатки блоковых кодов

Хотя блоковые коды, как правило, хорошо справляются с редкими, но большими пачками ошибок, их эффективность при частых, но небольших ошибках (например, в канале с АБГШ), менее высока.

Свёрточные коды

Свёрточный кодер ()

Свёрточные коды, в отличие от блоковых, не делят информацию на фрагменты и работают с ней как со сплошным потоком данных.

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

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

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

Преимущества и недостатки свёрточных кодов

Свёрточные коды эффективно работают в канале с белым шумом, но плохо справляются с пакетами ошибок. Более того, если декодер ошибается, на его выходе всегда возникает пакет ошибок.

Каскадное кодирование. Итеративное декодирование

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

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

Некоторые коды-произведения специально сконструированы для итеративного декодирования, при котором декодирование осуществляется в несколько проходов, каждый из которых использует информацию от предыдущего. Это позволяет добиться большой эффективности, однако, декодирование требует больших ресурсов. К таким кодам относят турбо-коды и LDPC-коды (коды Галлагера).

Оценка эффективности кодов

Граница Хемминга и совершенные коды

Пусть имеется двоичный блоковый (n,k) код с корректирующей способностью t . Тогда справедливо неравенство (называемое границей Хемминга):

Коды, удовлетворяющие этой границе с равенством, называются совершенными. К совершенным кодам относятся, например, коды Хемминга. Часто применяемые на практике коды с большой корректирующей способностью (такие, как коды Рида — Соломона) не являются совершенными.

Энергетический выигрыш

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

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

Применение кодов, исправляющих ошибки

Коды, исправляющие ошибки, применяются:

• в системах цифровой связи, в том числе: спутниковой, радиорелейной, сотовой, передаче данных по телефонным каналам.
• в системах хранения информации, в том числе магнитных и оптических.

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

Автоматический запрос повторной передачи

Системы с автоматическим запросом повторной передачи (ARQ — Automatic Repeat reQuest) основаны на технологии обнаружения ошибок. Распространены следующие методы автоматического запроса:

Запрос ARQ с остановками (stop-and-wait ARQ)

Идея этого метода заключается в том, что передатчик ожидает от приемника подтверждения успешного приема предыдущего блока данных перед тем как начать передачу следующего. В случае, если блок данных был принят с ошибкой, приемник передает отрицательное подтверждение (negative acknowledgement, NAK), и передатчик повторяет передачу блока. Данный метод подходит для полудуплексного канала связи. Его недостатком является низкая скорость из-за высоких накладных расходов на ожидание.

Непрерывный запрос ARQ с возвратом (continuous ARQ with pullback)

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

Непрерывный запрос ARQ с выборочным повторением (continuous ARQ with selective repeat)

При этом подходе осуществляется передача только ошибочно принятых блоков данных.

См. также

Литература

• Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979.
• Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.
• Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.: Техносфера, 2005. — ISBN 5-94836-035-0

Ссылки

Wikimedia Foundation . 2010 .

Полезное

Смотреть что такое "Избыточность данных" в других словарях:

избыточность данных — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN data redundancy … Справочник технического переводчика

избыточность — 03.01.05 избыточность (информация) [redundancy]: Характеристика информации, обеспечивающая повышение вероятности безошибочного считывания или передачи данных за счет их повтора1). 1Избыточность может также обеспечиваться добавлением функционально … Словарь-справочник терминов нормативно-технической документации

Избыточность информации — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете … Википедия

Сжатие данных — Возможно, эта статья содержит оригинальное исследование. Добавьте ссылки на источники, в противном случае она может быть выставлена на удаление. Дополнительные сведения могут быть на странице обсуждения. (26 мая 2012) … Википедия

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

Введение

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

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

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

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

Метод резервирования предназначен в качестве меры безопасности в режиме реального времени и представляет собой вариант защиты пользовательских данных на случай отказа жесткого диска по любой возможной причине, включая поломку и не устраняемую аппаратную неисправность. Для предотвращения потери данных в серверах и блоках «NAS-устройств» часто используется функция резервирования, являющаяся основой во многих уровнях программного построения и организации внутреннего взаимодействия общего объединения запоминающих устройств «RAID» (расшифровка аббревиатуры в переводе с английского означает: избыточный массив независимых (самостоятельных) дисков), который создает несколько отдельных копий файлов на различных жестких дисках. И если по какой-либо причине один из жестких дисков в представленном используемом массиве выходит из строя, то другие жесткие диски фиксируют отсутствие информации и позволяют восполнить пропажу без дополнительных задержек. Метод резервного копирования, с другой стороны, не обеспечивает защиту в режиме реального времени, а позволяет выполнить отдельную копию, отмеченных пользователями, данных на определенную дату, с последующей возможностью восстановить из созданного архива любой отсутствующий элемент. Но его актуальность будет представлена лишь датой сохранения копии, и все последующие изменения указанного оригинального объема данных, выполненные после создания резервной копии, в случае его повреждения, удаления или потери будут недоступны.

Что представляет собой понятие избыточности?

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

И это действительно главная цель избыточного хранения: надежность и время безотказной работы. В случае отказа жесткого диска, благодаря избыточности, утраченная информация, в зависимости от задействованного формата «RAID» , может быть извлечена из дублированного диска или быть вычислена из контрольной суммы, сохраненной на отдельном диске, пользуясь информацией с оставшихся накопителей. И будет задействоваться на резервном диске до тех пор, пока неисправный жесткий диск не будет заменен и не будет восстановлена его резервная копия.

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

Резервные копии защищают от всех типов потери данных

Существует множество способов потери данных: случайное непреднамеренное удаление, повреждение файла, системный или аппаратный сбой, вредоносное воздействие зловредного программного обеспечения, ошибки операционной системы, конфликты совместимости различных приложений и программ, кража или потеря данных, порча и многое другое. Избыточность, доступная в массивах «RAID» , защищает только от сбоя диска, в то время как истинное полноценное резервное копирование способно уберечь пользовательские данные от каждого из перечисленных факторов (или, по крайней мере, большинства из них).

Можно рассмотреть достоверность представленного выше утверждения на примере случайного удаления файла, являющимся одним из наиболее распространенных вариантов потери данных. Если пользователи непреднамеренно удалят определенный файл, то избыточность не убережет их от утраты, так как избыточная копия файла, доступная в настройке массива «RAID» , также будет удалена.

Однако, при резервном копировании, случайно удаленный файл остается неповрежденным и доступен для дальнейшего использования на совершенно отдельном, независимом носителе. Вот почему пользователи всегда должны выполнять резервное копирование своих данных, даже при задействовании серверов «NAS» , настроенных под любой приемлемый вариант формирования дискового массива «RAID» .

Какой способ лучше задействовать для создания резервной копии данных?

Если пользователи установили себе за правило и регулярно создают резервные копии всех своих файлов на отдельном жестком диске своего компьютера (жесткий диск «HDD» в сравнении с твердотельным накопителем «SSD» более предпочтителен для хранения архива, по причине большего объема внутреннего дискового пространства, непосредственно доступного для использования), озаглавливая готовую архивную копию датой ее воссоздания, то такой подход безусловно позволит существенно обезопасить данные от непредвиденной утраты. Однако не стоит ограничиваться лишь данным способом. И стоит рассмотреть возможность увеличения количества резервных копий.

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

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

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

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

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

Заключение

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

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

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

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

Читайте также:

  
• Coreldraw как работать с инструментом color
  
• Как подключить колонки к компьютеру без штекера
  
• Сканирование smart nod32 что это
  
• Расширение файла bmp указывает на то что тест
  
• Scratch disks are full photoshop что делать