Что такое структурная избыточность компьютерных ресурсов
Поскольку программное обеспечение и компьютерные базы данных являются результатом высококвалифицированного интеллектуального труда специалистов- профессионалов, а от надежной работы компьютерных систем и прикладных программ зависит деятельность огромного количества людей, трудящихся в самых разных сферах приложения компьютерных технологий, с самого начала вхождения компьютерной техники в жизнь человеческого сообщества возникла необходимость защиты информации от несанкционированного ее использования, опасности утраты или порчи. Возникновение и глобальное распространение общедоступных компьютерных сетей поставило новые задачи перед разработчиками средств обеспечения защиты информации и оказало определяющее влияние на всю сферу обеспечения информационной безопасности.
Нарушения безопасного функционирования компьютерной техники принято называть информационными угрозами. Все виды информационных угроз, с которыми сталкивается пользователь современных вычислительных устройств, можно разделить на две основные группы:
1) технологические сбои, т.е. невозможность выполнения каких-либо операций и другие нарушения работоспособности используемых программных и технических средств;
2) преднамеренные вредоносные действия злоумышленников, способные помешать рабочим процессам и (или) разрушить само вычислительное устройство.
При информационных угрозах первого типа возникает опасность нарушения физической и логической целостности хранящихся в оперативной и внешней памяти структур данных из-за старения или износа ее носителей либо из-за некорректного использования возможностей компьютера; возможна потеря данных и другой важной для пользователя информации из-за неправильного использования программного обеспечения; разрушающего воздействия разного рода ошибок в программных средствах, не выявленных в процессе отладки и испытаний программ, а также ошибок, оставшихся в аппаратных средствах после их разработки, и т.п.
Основными способами защиты от информационных угроз первого типа являются обеспечение структурной, временной, информационной и функциональной избыточности компьютерных ресурсов, использование специальных программных средств, предупреждающих или купирующих неправильные действия пользователя информационной системы (защита от дурака), а также выявление и своевременное устранение ошибок на этапах разработки программно-аппаратных средств.
Структурная избыточность компьютерных ресурсов обеспечивается за счет постоянного текущего контроля за работоспособностью всех компонентов вычислительного устройства и своевременной замены вышедших из строя или устаревших узлов, а также обновления используемого программного обеспечения.
Временная избыточность обеспечивается периодическим или постоянным (идущим в фоновом режиме) копированием и сохранением (резервированием) данных на основных и резервных носителях, что обеспечивает восстановление случайно или преднамеренно уничтоженной и искаженной информации.
Функциональная избыточность компьютерных ресурсов обеспечивается дублированием ключевых функций компьютера или внесением дополнительных функций в программно-аппаратные ресурсы вычислительной системы для повышения ее защищенности от сбоев и отказов. Примером таких действий является, в частности, периодическое обязательное тестирование, самотестирование, восстановление и самовосстановление разрушенных или испорченных компонентов компьютерной системы.
Информационная избыточность обеспечивается постоянным предоставлением пользователю доступа к контекстным и общим справочно-информационным ресурсам, эффективному, интуитивно понятному и дружественному учебно-справочному интерфейсу, постоянным запросам на подтверждение потенциально опасных пользовательских действий, которые генерирует система, и другими действиями такого рода.
Второй тип информационных угроз является в настоящее время наиболее распространенным и менее изученным. К таким угрозам относятся целенаправленные вредоносные действия других людей (несанкционированное копирование информации, нарушение работоспособности программною и аппаратного обеспечения, стороннее несанкционированное использование ресурсов вычислительного устройства с целью нанесения вреда другим пользователям компьютерной техники, находящимся в общей компьютерной сети, и т.д.).
Этот вид угроз безопасности использования вычислительной техники можно разделить на две основные группы:
1) вредоносные действия, которые выполняются при постоянном непосредственном участии человека;
2) вредоносные действия, которые выполняются без непосредственного участия человека специально разработанным для этих целей программным обеспечением (вирусные программы, или программы – компьютерные вирусы).
Основные приемы защиты от угроз такого рода одинаковы и заключаются в обеспечении запрета несанкционированного доступа к ресурсам компьютера, а также к подключенным к нему устройствам; невозможность несанкционированного использования ресурсов компьютера после получения к ним доступа; своевременное обнаружение факта несанкционированных действий и устранение их причин и последствий.
Основным способом запрещения несанкционированного доступа к ресурсам вычислительных систем является подтверждение подлинности пользователей и разграничение их нрав на доступ к определенным информационным ресурсам. Подтверждение подлинности пользователя обеспечивается выполнением процедуры его идентификации, проверкой аутентичности идентифицируемого лица и осуществлением контроля за всеми действиями, определяемыми приписанными данному пользователю полномочиями доступа.
Идентификация пользователя включает в себя регистрацию в системе безопасности вычислительного устройства уникального регистрационного имени пользователя (логина) и соответствующего этому пользовательскому имени – пароля. Установление подлинности пользователя (аутентификация) заключается в проверке истинности его полномочий. Для особо надежного опознания при идентификации и аутентификации пользователя иногда используются специальные технические средства, фиксирующие и распознающие индивидуализирующие человека физические и лингвистические характеристики (голос, отпечатки пальцев, структура зрачка, речевые особенности и т.д.). Однако такие методы требуют значительных затрат и поэтому используются редко, так что основным и наиболее массовым средством идентификации остается парольный доступ.
В ряде случаев при необходимости обеспечить высокую степень защиты информации, которая находится в компьютере либо обрабатывается каким- либо вычислительным устройством, используются также специальные криптографические методы защиты информации (шифрование, цифровая подпись, цифровые водяные знаки и т.д.). При шифровании информации происходит ее обратимое преобразование в некоторую кажущуюся случайной последовательность знаков, которая называется шифротекстом, или криптограммой. Для создания и работы с криптограммой требуется знание алгоритма и ключа шифрования. Алгоритм шифрования представляет собой последовательность преобразований обрабатываемых данных в соответствии с ключом шифрования, ключ шифрования обеспечивает шифрование и дешифрование информации.
В настоящее время все большую популярность приобретает такое криптографическое средство защиты информации, как электронная цифровая подпись (ЭЦП). Она уже стала достаточно часто используемым способом идентификации и аутентификации пользователя в банковской и других сферах деятельности. Электронная цифровая подпись представляет собой присоединенное к какому-либо тексту его криптографическое (зашифрованное определенным способом) преобразование, которое позволяет проверить получателю текста подлинность его авторства и аутентичность самого текста. К такому же типу технологической защиты можно отнести и цифровые водяные знаки (англ.digital watermark), которые сегодня чаще всего используются против несанкционированного копирования мультимедийных файлов как один из эффективных способов защиты авторских прав.
Цели: Дать понятие «избыточность», рассмотреть виды избыточности.
Развивать логико-алгоритмическое мышление, память, произвольное мышление, связную устную речь.
Воспитывать информационную культуру , интерес к изучаемому предмету.
Тип урока: комбинированный.
Форма: индивидуальная, фронтальная.
Образовательные ресурсы: ПОЭВМ, наглядный материал (презентация), дидактический материал (карточки с заданием для организации опроса).
УУД: личностные, регулятивные, познавательные, коммуникативные.
Планируемые образовательные ресурсы:
-метапредметные- развивать познавательный интерес, речь и внимание обучающихся, формировать у них информационную культуру и потребность в приобретении знаний; расширение кругозора; развитие коммуникативных качеств личности; развитие навыков самообразования с использованием информационных и коммуникационных технологий;
-личностные- способность увязать учебное содержание с собственным жизненным опытом; п онять значимость подготовки в области информатики в условиях развития информационного общества; способность и готовность к общению и сотрудничеству со сверстниками и взрослыми в процессе образовательной деятельности.
I . Мотивационно-ориентировочный этап.
- Здравствуйте! Присаживайтесь (пауза, жду, когда все сядут и установится тишина).
- Сегодня урок информатики проведу у вас я, меня зовут……..
2. Организация внимания.
- На столе у вас должны лежать тетради, письменные принадлежности. Всё лишнее уберите. Начинаем урок!
3. Индивидуальная работа по карточкам.
Тест по прошлому материалу на тему: «Информационные процессы»
1. Каналы связи делятся на: ___________ ____________.
2. Канал связи — это:
а) совокупность устройств, обеспечивающих прием информации при ее передаче;
г) технические средства, позволяющие осуществлять передачу данных на расстоянии.
3. Расследование преступления представляет собой информационный процесс:
а) кодирования информации; б) поиска информации; в) хранения информации; г) передачи информации.
4. Пропускная способность – это …
а) объем данных, передаваемых модемом в единицу времени, без учета дополнительной служебной информации;
в) распространение новой информации, полученной в процессе научного познания.
5. Дуплексной передачи связи называется?
а) осуществляется передача сигналов в одной паре проводников в одном направлении;
б) осуществляется передача сигналов в одном направлении в четырехпроводной линии связи;
в) одновременной передачи сигналов между абонентами в обоих направлениях, т.е. канал связи должен быть двустороннего действия.
6. При телефонном разговоре в качестве источника информации следует рассматривать:
а) человека слушающего; б) телефонную трубку; в) человека говорящего; г) телефонную сеть;
7. Хранение информации невозможно без:
а) компьютера; б) носителя информации; в) библиотек, архивов; г) линий связи.
8. Что такое кабель?
1. Место соприкосновения проводников между собой.
2. Проводник, который служит для передачи электрического тока в земле, воде и воздухе.
3. Служит жестким неизолированным проводником.
9. Протокол – это:
1) список абонентов компьютерной сети;
3) полный набор операций, который один объект может осуществлять над другим объектом вместе с правильным порядком, в котором эти операции вызываются .
1. Перевод текста с английского языка на русский является процессом:
а) хранения информации; б) передачи информации; в) поиска информации; г) обработки информации.
2. Браузер – это … 1)техническое устройство; 2)программа создания web – страниц; 3)программа просмотра web – страниц.
3. Какой из следующих сигналов является аналоговым:
а) сигнал маяка; б) сигнал S0S; в) кардиограмма; г) дорожный знак; д) сигнал светофора.
4. Внутреннее представление информации в компьютере:
а) непрерывно; б) дискретно; в) частично дискретно, частично непрерывно;
г) нельзя описать с использованием терминов «дискретно», «непрерывно».
5. Какая система исчисления используется для передачи цифровых сигналов?
а) Восьмеричная; б) Двоичная; в) Шестнадцатеричная.
6. Записная книжка обычно используется:
а) при обработке информации; б) для хранения информации; в) для передачи информации; г) для защиты информации.
7. Сигналом называется:
8. Аналоговый сигнал — это:
а) сигнал, непрерывно изменяющийся по амплитуде и по времени;
б) сигнал, который может принимать лишь конечное число значений в конечное число моментов времени; в) сигнал, несущий текстовую информацию;
г) любой процесс, несущий информацию.
9 . Какой кабель обеспечивает скоростью передачи данных до 10 Мбит/с?
1) коаксиальный; 2) витая пара; 3) оптоволокно.
4. Фронтальный устный опрос.
- Что называют каналами связи? (технические средства, позволяющие осуществлять передачу данных на расстоянии).
- Какие классификации компьютерных каналов связи вы знаете?
(по способу кодирования: цифровые и аналоговые;
по способу коммуникации: выделенные и коммутируемые;
по способу передачи сигнала: 1.Кабельные: витая пара, коаксиальные кабели, оптико-волоконные кабели; оптические, беспроводные, спутниковые. 2.Телефонные; 3.Радио: радиорелейные, спутниковые).
-Что такое протокол? (полный набор операций, который один объект может осуществлять над другим объектом вместе с правильным порядком).
5. Подведение итога этапа.
- Итак, материал прошлого урока вы усвоили хорошо. Молодцы!
II . Поисковый этап.
1. Формулирование темы и цели урока обучающимися.
- Прочитайте тему урока. Как вы думаете, о чём пойдёт речь на нашем уроке?
- Поставьте перед собой цель на данный урок.
2. Изучение нового материала.
- Откройте тетради и подпишите число и тему урока.
Тема «Избыточность информации, как средство повышения надежности её передачи»
Виды избыточности:
Функциональная избыточность – это меры обеспечивающие сохранение работоспособности системы при выходе некоторых параметров за пределы допусков. К числу таких средств относятся адаптация системы за счёт введения дополнительных обратных связей.
Структурная избыточность заключается в дублировании систем, элементов, деталей машин, живых организмов.
Временная избыточность – увеличение надёжности за счёт увеличения времени работы с информацией.
Постановка задачи обеспечения надежности передачи
Все реальные каналы связи подвержены воздействию помех.
Задача была сформулирована в виде теоремы, которая затем получила строгое математическое доказательство. Ранее была представлена первая теорема Шеннона, касающаяся кодирования информации при передаче по идеальному каналу связи. Критерием оптимальности кодирования служила избыточность кода.
Вторая теорема Шеннона касается реальных каналов связи и гласит:
Последняя часть определения, относится и к идеальному каналу – в любом случае, если скорость передачи превышает пропускную способность канала, происходит потеря информации.
Рассмотрим некоторые методы повышения надежности передачи данных. Широко известными методами борьбы с помехами являются следующие:
1. передача в контексте;
3. передача с переспросом.
Рассмотрим подробней каждый из этих способов.
Коды избыточности* широко применяются в компьютерных системах для увеличения надёжности хранения данных. В Яндексе их используют в очень многих проектах. Например, применение кодов избыточности вместо репликации в нашем внутреннем объектном хранилище экономит миллионы без снижения надёжности. Но несмотря на широкое распространение, понятное описание того, как работают коды избыточности, встречается очень редко. Желающие разобраться сталкиваются примерно со следующим (из Википедии):
Меня зовут Вадим, в Яндексе я занимаюсь разработкой внутреннего объектного хранилища 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 блоков данных. На схеме ниже X1-X6 — блоки данных, P1–P4 — блоки кодов избыточности.
Все блоки данных должны быть одинакового размера, для выравнивания можно использовать нулевые биты. Полученные блоки кодов избыточности будут иметь тот же размер, что и блоки данных. Все блоки данных разбиваются на слова (например, по 16 бит). Допустим, мы разбили блоки данных на k слов. Тогда все блоки кодов избыточности тоже будут разбиты на k слов.
Для подсчёта i-го слова каждого блока избыточности будут использоваться i-е слова всех блоков данных. Они будут считаться по следующей формуле:
Здесь значения x — слова блоков данных, p — слова блоков кодов избыточности, все альфа, бета, гамма и дельта — специальным образом подобранные числа, одинаковые для всех i. Сразу нужно сказать, что все эти значения — не обычные числа, а элементы поля Галуа, операции +, -, *, / — не привычные всем нам операции, а специальные операции, введённые над элементами поля Галуа.
Зачем нужны поля Галуа
Казалось бы, всё просто: разбиваем данные на блоки, блоки — на слова, с помощью слов блоков данных считаем слова блоков кодов избыточности — получаем блоки кодов избыточности. В целом это так и работает, но дьявол в деталях:
- Как сказано выше, размер слова — фиксированный, в нашем примере 16 бит. Формулы выше для кодов Рида — Соломона таковы, что при использовании обычных целых чисел результат вычисления p может быть не представим с помощью слова допустимого размера.
- При восстановлении данных формулы выше будут рассматриваться как система уравнений, которую нужно решить, чтобы восстановить данные. В процессе решения может появиться необходимость выполнить деление целых чисел друг на друга, результатом чего будет вещественное число, которое нельзя точно представить в памяти компьютера.
Эти проблемы не позволяют использовать для кодов Рида — Соломона целые числа. Решение проблемы оригинальное, его можно описать следующим образом: давайте придумаем специальные числа, которые можно представить с помощью слов нужной длины (например, 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. 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, перевешивает чуть меньшую надёжность хранения.
Помимо кодов Рида — Соломона и 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.
Есть ещё много особенностей применения кодов избыточности в системах хранения и обработки данных: нюансы восстановления данных, влияние восстановления на время выполнения запросов, особенности записи данных и т. д. Я собираюсь отдельно рассказать об этих и других особенностях применения кодов избыточности на практике, если тема будет интересна.
Проектирование баз данных. Информационная избыточность. Избыточность данных в базе данных. Проблемы возникающие из-за информационной избыточности
Как и обещал, эта статья и следующая тоже будут посвящены проектированию баз данных, моделированию баз данных или созданию баз данных, как хотите, так и называйте. Данная публикация посвящена проблемам, которые могут возникнуть при проектирование базы данных, точнее одной из проблем.
Попытаюсь рассказать, как обычно на пальцах, что такое информационная избыточность и избыточность данных в базе данных. Также попытаюсь рассказать о проблемах обработки данных, которые могут возникнуть из-за избыточности информации, затрону тему целостности данных в базе данных. Немного затрону тему нормализации базы данных и нормальных форм, нормальные формы – это тема следующей публикации. Какие нормальные формы бывают и как привести базу данных к нормальной форме. Всё это вы найдете в следующей публикации.
Избавиться от избыточности данных, а следовательно и от аномалий баз данных – это вопрос проектирования баз данных. И решать вопрос устранения избыточности в базе данных следует до того, как вы начали ее реализовывать программно, то есть, до того как начали создавать базу данных в той или иной СУБД, в нашем случае СУБД MySQL.
Чтобы избавиться от информационной избыточности, а вместе с тем решить проблему модификации, удаления и добавления данных вам не потребуется каких-либо специальных программ, достаточно будет представлять структуру проектируемого объекта(заметьте, пока еще не структуру базы данных), иметь под рукой несколько чистых листов бумаги, карандаш или ручку. Но, чтобы начать от чего-то избавляться, нужно знать суть самой проблемы, из-за чего эта проблема возникает и так ли она для вас критична.
Из-за избыточности информации в базе данных возникают не только проблемы модификации, добавления и удаления данных из базы данных, но и остро встает вопрос экономии места на диске, согласитесь глупо хранить одну и ту же информацию в разных местах. Избыточность баз данных тесно связана с нормальными формами. Точнее, информационная избыточность – это отрицательный фактор, влияющий на целостность базы данных, вынуждающий нас приводить свои базы данных к нормальной форме.
Данная публикации как раз и предназначена для тех, кто хочет быстро разобраться с тем, что такое информационная избыточность и избыточность данных в базе данных, а так же тем, кто хочет разобраться с вопросом, как избавиться от избыточности данных.
Информационная избыточность. Избыточность базы данных. Что такое избыточность.
Начнем мы с информационной избыточности и избыточности реляционных баз данных в частности. Поскольку, эта самая избыточность и заставляет нас нормализовывать базы данных.
Для начала напишу умное определение избыточности, а затем постараюсь объяснить его по-русски.
Давайте начнем разбираться с определением избыточности и начнем с термина информационная энтропия.
Информационная энтропия – это мера неопределенности информации, неопределенность появления какого-либо символа. Данное определение появилось в теории электросвязи. Для администратора баз данных информационную энтропию следует интерпретировать немного по-другому: информационная энтропия всё также мера неопределенности информации, но, какая информационная неопределенность может возникнуть в базе данных?
Например, у нас есть база данных, в которой хранится библиотека и есть писатель Иванов И.И., сколько книг написал Иванов И.И.? Бог его знает. Может одну, а может и сто. И сколько раз появится этот Иванов И.И. в нашей таблице, мы не знаем. Такая вот неопределенность информации.
Любая база данных предназначена для хранения информации. И при проектирование базы данных следует учесть то, что какая-то информация может повторяться несколько раз. А каждая повторяющаяся запись – это занятое место на диске. То есть превышение количества информации необходимого для хранения данных.
Конечно, можно сказать, что сейчас, с появлением терабайтных накопителей отпала необходимость экономить место на диске. Но информационная избыточность ведет не только к увеличению требуемого объема памяти для хранения информации содержащейся в базе данных.
Избыточность данных в базе данных – это нежелательное явление еще и потому, что при работе с таблицами базы данных (которые еще называют отношениями), содержащими избыточные данные возникают проблемы связанные с обработкой информации, эти проблемы называются аномалии. Про аномалии баз данных читайте в следующем разделе.
Последствия информационной избыточности в базе данных. Избыточность данных. Аномалии (проблемы) в базе данных.
Как мы уже выяснили, избыточность информации ведет не только к тому, что требуется увеличение объема накопителей, но и приводит к аномалиям в базе данных.
Аномалии в базе данных – это проблемы связанные с обработкой информации, а точнее с удаление данных из базы данных, с модификацией данных в таблице базы данных и аномалия добавления данных в базу данных.
Как вы поняли, в базе данных есть три аномалии:
- Аномалия включения – это проблема, связанная с добавлением данных в базу данных
- Аномалия модификации – это проблема, связанная с изменением данных в базе данных
- Аномалия удаления – это проблема, связанная с удаление данных в базе данных
Все эти проблемы связаны с целостностью баз данных, а именно с избыточностью данных в базе данных. Давайте остановимся подробней на каждой аномалии.
Давайте посмотрим на примере приближенном к реальности, что такое избыточность данных. Допустим, у нас есть таблица, в которой хранятся данные список преподавателей и список предметов, которые они ведут. Естественно, в это таблице присутствует информационная избыточность.
Таблица с информационной избыточностью
Избыточность данных в этой таблице заключается в том, что любой преподаватель может вести несколько предметов, как преподаватель Иванов и для каждого нового предмета приходится добавлять новые записи в таблицу.
Один преподаватель может вести разные предметы, а разные предметы могут вести разные преподаватели. Давайте посмотрим, какие аномалии могут произойти в данном конкретном случае и как можно избавиться от аномалий в конкретном случае.
Аномалия включения. Проблема добавления данных в базу данных.
Избыточность данных очевидна, поскольку произошло дублирование информации, преподаватель Иванов ведет два предмета и его пришлось вписать дважды в таблицу. Но это еще не всё. Допустим, в нашей школе появился новый предмет и мы хотим его добавить в существующую таблицу базы данных, но мы еще не нашли преподавателя для этого предмета. А вписать в таблицу предмет нужно уже сейчас.
В этом случае мы должны присвоить значение NULL каждому атрибуту преподавателя, но делать это никак нельзя, так как атрибут «Код преподавателя» является первичным ключом отношения (первичным ключом таблицы). Результатом попытки создания такой записи будет нарушение целостности данных базы данных, а любая СУБД, в том числе и СУБД MySQL отклонит подобную попытку создания такой записи.
Все вышеописанное является аномалией включения. Чтобы избавиться от аномалии включения нужно разбить таблицу на две: таблица преподавателей и таблица предметов. Примерно это будет выглядеть так:
Избавляемся от избыточности данных в базе данных.
Здесь мы разделили общую таблицу, тем самым избавились от аномалии включения и от возникшей информационной избыточности, то есть от дублирования в базе данных. В принципе то, что мы сделали в данный момент – привели базу данных ко второй нормальной форме.
Вторая нормальная форма позволяет нам избавиться от аномалии включения, а также от дублирования информации в базе данных, то есть мы избавляемся от избыточности информации.
Аномалия модификации. Проблема изменения базы данных.
Следующая проблема, которая может возникнуть из-за избыточности базы данных – это проблема внесения изменений в таблицы базы данных или как ее еще называют – аномалия модификации.
В нашем примере проблема модификации могла бы возникнуть при попытке изменения фамилий преподавателей, например, если бы в этом списке была незамужняя женщина с фамилией Сидорова, то возможно, когда-нибудь она вышла бы замуж и поменяла фамилию, а оператору пришлось бы для каждой записи, в которой имелась фамилия Сидорова заменить на новую фамилию. Это довольно нудная работа. Каждая такая запись или строка таблицы базы данных называется кортежем.
Чтобы избавиться от аномалии модификаций и все связанные с ней проблемы мы можем прибегнуть к предыдущему способу, просто разбиваем одну большую таблицу на две маленьких. То есть, приводим базу данных ко второй нормальной форме или просто нормализуем.
И опять же, таким образом мы избавляемся от дублирования данных в базе данных. Все довольно просто.
Аномалия удаления. Проблема удаления данных из базы данных.
Проблема удаления данных из базы данных – это еще одна проблема, которая появляется, если данные в базе избыточны ее еще называют аномалия удаления. Проблема удаления данных из базы данных заключается в том, что при удаление одной записи или кортежа из таблицы, относящейся к какому-либо из преподавателю, вместе с записью о преподавателе, из базы данных удалится вся информация о предмете, который вел этот преподаватель.
Решается проблема удаления данных из базы данных очень просто, нормализуем базу данных до второй нормальной формы, то есть разделяем таблицу на две, как это показано в разделе посвященном аномалии включения.
Обратите внимание: типы данных у различных СУБД могут быть разными, у MySQL типы данных одни, у какой-либо другой СУБД могут быть другие типы данных, как и у языков программирования. У JavaScript типы данных одни, а у PHP типы данных другие.
Читайте также: