Рубрика «коды Рида-Соломона»

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

И так, я отвлёкся. В детстве-юношестве для помехоустойчивого кодирования можно было бы применить контроль чётности по матричному методу, но сейчас это не серьёзно. Полистав интернет я решил остановиться на кодировании по методу Рида-Соломона. Алгоритм не то, чтобы совсем новый, его ещё в первых CD применяли, но при этом, насколько мне известно, не потерявший своей актуальности и на данный момент. В этой статье о самих кодах Рида-Соломона я не буду сильно распространяться – это за меня на Хабре сделали много раз и много кто. Здесь я хочу описать реализацию алгоритма умножения в GF[256]. Тем не менее, чтобы не заставлять читателя прыгать по ссылкам, кратенько опишу зачем вообще приходится иметь дело
с полями Гаула.

Читать полностью »

На Хабре уже обсуждалось устройство QR-кодов и украшение их произвольными рисунками, но дизайнерская мысль до сих пор работала только в двух основных направлениях: замена квадратных модулей на более интересные формы, либо замена части кода рисунком. Такие художества возможны благодаря тому, что блоки данных в QR-коде дополняются кодами Рида-СоломонаЧитать полностью »

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

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

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

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

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

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

* В англоязычной литературе коды избыточности часто называют erasure codes.

Читать полностью »

Здравствуйте, друзья! В прошлый раз мы с вами начали говорить о том, как коды Рида-Соломона помогают обеспечивать необходимый уровень надежности хранения данных. Сегодня остановимся немного подробнее на арифметике полей Галуа, которая используется в расчётах.
Коды Рида-Соломона. Часть 2 — арифметика полей Галуа - 1

Читать полностью »

Добрый день! Меня зовут Максим, в YADRO, кроме всего прочего, я занимаюсь разработкой подсистемы, отвечающей за надежное хранение данных. Готовлю небольшой цикл статей про коды Рида-Соломона — теоретическую основу, практическую реализацию, применяемые на практике программные и аппаратные оптимизации. На Хабре и в остальной сети есть хорошие статьи по вопросам этой области — но по ним сложно разобраться, если ты новичок в теме. В этой статье я попытаюсь дать понятное введение в коды Рида-Соломона, а в следующих выпусках напишу, как все это запрограммировать.

Коды Рида-Соломона. Часть 1 — теория простым языком - 1

Читать полностью »

Яндекс, как и любая другая большая интернет-компания, хранит много, а точнее очень много данных. Это и пользовательские данные из разных сервисов, и намайненные сайты, и промежуточные данные для расчёта погоды, и резервные копии баз данных. Стоимость хранения ($/ГБ) — один из важных показателей системы. В этой статье я хочу рассказать вам про один из методов, который позволил нам серьезно удешевить хранилище.

Как применение кодов избыточности в SDS помогает Яндексу дёшево и надёжно хранить данные - 1

В 2015 году, как вы все помните, сильно вырос курс доллара. Точнее, расти-то он начал в конце 2014-го, но новые партии железа мы заказывали уже в 2015-м. Яндекс зарабатывает в рублях, и поэтому вместе с курсом выросла и стоимость железа для нас. Это заставило нас в очередной раз подумать о том, как сделать, чтобы в текущий кластер можно было положить больше данных. Мы такое, конечно, делаем регулярно, но в этот раз мотивация была особенно сильной. Кстати, если после поста у вас останутся вопросы, которые бы вы хотели обсудить лично, приходите на нашу встречу.

Каждый сервер кластера предоставляет для нас следующие ресурсы: процессор, оперативную память, жёсткие диски и сеть. Сеть здесь — более сложное понятие, чем просто сетевая плата. Это ещё и вся инфраструктура внутри дата-центра, и связность между разными дата-центрами и точками обмена трафиком. В кластере для обеспечения надёжности применялась репликация, и суммарный объём кластера определялся исключительно через суммарную ёмкость жёстких дисков. Нужно было придумать, как обменять оставшиеся ресурсы на увеличение места.

Читать полностью »

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

Странная вещь — любопытство. Вот на столе экземпляр CD — безнадёжно устаревшего в наш просвященный XXI век формата хранения данных; а все таки интересно, как же там хранятся данные?.. Каков сам стек хранения данных?.. Как исправляются ошибки?.. Какова избыточность кода?..

В детстве мне было достаточно знаний о лазерном луче, о какой-то головке, об «этой крутящийся штуки» и о таинственных питах.

Сказано — сделано. Проглядев стандарт ECMA-130 (есть, кстати и отечественный стандарт: ГОСТ 27667-88) обнаружил массу любопытных деталей. Например, я догадывался об избыточности, но я и подумать не мог, что для записи 700 Мб данных «в реальности» записывается 1943 Мб (То есть в 2.776 раз больше)…

Схематично весь стек можно представить картинкой:
ECMA-130 (Compact Disc) на пальцах - 1

Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js