Избыточность сообщения для чего ее можно использовать

Избыточность источника сообщений

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

M – количество различных букв в алфавите;

H(X) – средняя энтропия на одну букву.

Избыточность источника R показывает на сколько хорошо используются буквы в данном источнике. Чем меньше R, тем большее количество информации вырабатывается источником на одну букву. Однако, не всегда необходимо стремиться к R = 0. С повышением избыточности повышается помехоустойчивость (надежность) источника. Выяснение количества избыточности важно потому, что мы должны вводить ее разумно, чтобы получить максимальный эффект помехозащищенности, а не полагаться на стихию. Например, избыточность любого языка оказывается порядка 50-70%, то есть если бы все буквы имели одинаковую вероятность использования и можно было бы использовать любые комбинации букв, то среднюю длину слова можно было бы значительно уменьшить. Однако разбираться в этой записи было бы значительно труднее, особенно при наличии ошибок (лектора или студента).

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

Колоссальная избыточность присуща телевизионным изображениям: естественно передавать не весь кадр, а только информацию соответствующую тому, чем отличается один кадр от другого. Этим можно существенно сократить требуемую (в среднем) полосу частот.

Различают две составляющие избыточности:

где H(X) – энтропия для букв, когда они неравновероятны и взаимосвязаны;

H₁(X) – энтропия для букв, когда они статистически не взаимосвязаны и неравновероятны.

Но статистические связи между элементами укрупненного алфавита падают R_с ≈ 0; следовательно возрастает неравномерность употребления отдельных букв алфавита M₂, то есть R_р2 >> R_р1; R_р2 ≈ R₁ ≈ R₂.

Доказательство, что R₁ ≈ R₂ сводится к следующему:

Из свойства аддитивности информации следует, что в одном элементе второго алфавита содержится столько же информации, сколько ее содержится в n элементах первичного алфавита. Среднее количество информации на один элемент первого алфавита – H₁; математическое ожидание на n элементов первого алфавита – n · H₁ равно информации на один элемент второго алфавита H₂(X) = n · H₁.

2. Избыточность второго алфавита

Избыточность языка подсчитывается по формуле:

где H_max = log M, а M – число букв в алфавите.

а 0; 1; 2… – количество букв между которыми учитываются взаимосвязи.

Примеры

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

Ответ. Для носителя языка среднее количество информации на одну букву определяется как H_языка ≈ H₃₀ = 1.35 бит ⁄_буква, а для иностранца, плохо знающего словарь и не учитывающему взаимосвязь букв между собой H = H₀ или H₁, что соответствует

бит ⁄_буква.

То есть на странице текста для носителя языка содержится информации в

раза меньше информации, чем для иностранца. http://peredacha-informacii.ru/ Частичное знание словаря и закономерностей языка уменьшает эту разницу.

2. Во сколько раз удлиняется текст в деловых бумагах, если их избыточность составляет 90÷95%?

Ответ. При такой избыточности энтропия на одну букву составляет:

;
;

В то время как в письменной речи: H_∞(X) = 0.87÷1.37 бит ⁄_буква.

Текст удлиняется в раз.

Источник

Избыточность информации, как средство повышения надежности её передачи

Онлайн-конференция

«Современная профориентация педагогов
и родителей, перспективы рынка труда
и особенности личности подростка»

Свидетельство и скидка на обучение каждому участнику

Тема: «Избыточность информации, как средство повышения надежности её передачи»

Цели: Дать понятие «избыточность», рассмотреть виды избыточности.

Развивать логико-алгоритмическое мышление, память, произвольное мышление, связную устную речь.

Тип урока: комбинированный.

Форма: индивидуальная, фронтальная.

Образовательные ресурсы: ПОЭВМ, наглядный материал (презентация), дидактический материал (карточки с заданием для организации опроса).

УУД: личностные, регулятивные, познавательные, коммуникативные.

Планируемые образовательные ресурсы:

— предметные- формирование информационной и алгоритмической культуры; формирование представлений об основных изучаемых понятиях – «избыточность» и её виды, «функциональная избыточность», «структурная избыточность», «временная избыточность», информационная избыточность», «избыточность сообщения».

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

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

I . Мотивационно-ориентировочный этап.

— Здравствуйте! Присаживайтесь (пауза, жду, когда все сядут и установится тишина).

— Сегодня урок информатики проведу у вас я, меня зовут……..

2. Организация внимания.

— На столе у вас должны лежать тетради, письменные принадлежности. Всё лишнее уберите. Начинаем урок!

3. Индивидуальная работа по карточкам.

Тест по прошлому материалу на тему: «Информационные процессы»

1. Каналы связи делятся на: ___________ ____________.

2. Канал связи — это:

а) совокупность устройств, обеспечивающих прием информации при ее передаче;

б) совокупность устройств, преобразующих исходное сообщение источника информации к виду, в котором это сообщение передается;

в) устройство кодирования и декодирования информации при передаче сообщений;

г) технические средства, позволяющие осуществлять передачу данных на расстоянии.

3. Расследование преступления представляет собой информационный процесс:

а) кодирования информации; б) поиска информации; в) хранения информации; г) передачи информации.

4. Пропускная способность – это …

а) объем данных, передаваемых модемом в единицу времени, без учета дополнительной служебной информации;

б) совокупность устройств, преобразующих исходное сообщение источника информации к виду, в котором это сообщение передается;

в) распространение новой информации, полученной в процессе научного познания.

5. Дуплексной передачи связи называется?

а) осуществляется передача сигналов в одной паре проводников в одном направлении;

б) осуществляется передача сигналов в одном направлении в четырехпроводной линии связи;

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

6. При телефонном разговоре в качестве источника информации следует рассматривать:

а) человека слушающего; б) телефонную трубку; в) человека говорящего; г) телефонную сеть;

7. Хранение информации невозможно без:

а) компьютера; б) носителя информации; в) библиотек, архивов; г) линий связи.

8. Что такое кабель?

1. Место соприкосновения проводников между собой.

2. Проводник, который служит для передачи электрического тока в земле, воде и воздухе.

3. Служит жестким неизолированным проводником.

1) список абонентов компьютерной сети;

2) программа, приводящая полученное сообщение к стандартной форме;

1. Перевод текста с английского языка на русский является процессом:

а) хранения информации; б) передачи информации; в) поиска информации; г) обработки информации.

2. Браузер – это … 1)техническое устройство; 2)программа создания web – страниц; 3)программа просмотра web – страниц.

3. Какой из следующих сигналов является аналоговым:

а) сигнал маяка; б) сигнал S0S; в) кардиограмма; г) дорожный знак; д) сигнал светофора.

4. Внутреннее представление информации в компьютере:

а) непрерывно; б) дискретно; в) частично дискретно, частично непрерывно;

г) нельзя описать с использованием терминов «дискретно», «непрерывно».

5. Какая система исчисления используется для передачи цифровых сигналов?

а) Восьмеричная; б) Двоичная; в) Шестнадцатеричная.

6. Записная книжка обычно используется:

а) при обработке информации; б) для хранения информации; в) для передачи информации; г) для защиты информации.

7. Сигналом называется:

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

8. Аналоговый сигнал — это:

а) сигнал, непрерывно изменяющийся по амплитуде и по времени;

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

г) любой процесс, несущий информацию.

4. Фронтальный устный опрос.

— Что называют каналами связи? (технические средства, позволяющие осуществлять передачу данных на расстоянии).

— Какие классификации компьютерных каналов связи вы знаете?

(по способу кодирования: цифровые и аналоговые;

по способу коммуникации: выделенные и коммутируемые;

по способу передачи сигнала: 1.Кабельные: витая пара, коаксиальные кабели, оптико-волоконные кабели; оптические, беспроводные, спутниковые. 2.Телефонные; 3.Радио: радиорелейные, спутниковые).

-Что такое протокол? (полный набор операций, который один объект может осуществлять над другим объектом вместе с правиль­ным порядком).

5. Подведение итога этапа.

— Итак, материал прошлого урока вы усвоили хорошо. Молодцы!

1. Формулирование темы и цели урока обучающимися.

— Прочитайте тему урока. Как вы думаете, о чём пойдёт речь на нашем уроке?

— Поставьте перед собой цель на данный урок.

— Сегодня на уроке мы рассмотрим такие понятия как «избыточность» и её виды, «функциональная избыточность», «структурная избыточность», «временная избыточность», информационная избыточность», «избыточность сообщения».

2. Изучение нового материала.

— Откройте тетради и подпишите число и тему урока.

Тема «Избыточность информации, как средство повышения надежности её передачи»

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

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

Временная избыточность – увеличение надёжности за счёт увеличения времени работы с информацией.

Информационная избыточность заключается в использовании слов, кодов, которые содержат как бы «излишние» элементы, что обеспечивает надёжность передачи сообщений.

Постановка задачи обеспечения надежности передачи

Все реальные каналы связи подвержены воздействию помех.

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

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

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

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

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

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

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

1. передача в контексте;

2. дублирование сообщений;

3. передача с переспросом.

Рассмотрим подробней каждый из этих способов.

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

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

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

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

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

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

3. Подведение итога этапа.

— Что такое избыточность?

— Какие бывают виды избыточности?

— Что такое избыточность сообщения?

III . Рефлексивно-оценочный этап.

-Давайте подведём итоги урока.

— Вам было легко работать на уроке?

— Как бы вы оценили свою работу?

— Что вы узнали сегодня нового?

2. Домашнее задание.

— Запишите домашнее задание: выучить лекцию в тетради.

Источник

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

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

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

Меня зовут Вадим, в Яндексе я занимаюсь разработкой внутреннего объектного хранилища 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 блоков данных. На схеме ниже X₁-X₆ — блоки данных, P₁–P₄ — блоки кодов избыточности.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выбор n и m

Как на практике выбрать n и m? На практике в системах хранения данных коды избыточности используют для экономии места, поэтому m выбирают всегда меньше 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. X₁–X₆ — 6 блоков данных, P₁, P₂ — 2 глобальных блока избыточности, P₃, P₄ — 2 локальных блока избыточности.

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

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

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

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

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

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

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

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

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

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

В 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.

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

Источник