Под термином «коды избыточности» я подразумеваю термин «erasure codes», причем как инженерный термин, а не строгое теоретическое понятие, имеющее четкое определение. Добавил это в начало статьи, чтобы не было терминологической путаницы.
Название «коды избыточности» прижилось у нас исторически.
Название «erasure codes», конечно, используется чаще. Но и «код(ы) избыточности» иногда употребляют.
Этому примеру посвящена короткая статья на Хабре. В ней как раз рассматривается поле из 8 элементов GF(2^3).
В качестве введения в тему также можно использовать другую статью.
Поля Галуа — достаточно сложная тема, которую не получится объяснить в двух словах, или привести короткий понятный пример.
Для использования на практике не обязательно глубоко погружаться в теорию полей Галуа, можно просто считать, что есть некоторые таблицы сложения, вычитания, умножения и деления, и все вычисления происходят с использованием этих таблиц.
Например, можно использовать популярную библиотеку Jerasure для построения кодов избыточности (кодирования) и восстановления данных (декодирования). Решение систем уравнений (которые представляются в виде матричных уравнений), арифметика полей Галуа — это будет выполняться на уровне библиотеки.
Время чтения зависит от способа записи данных и режима работы (нормальный, когда все блоки данных доступны, или восстановление, когда часть блоков данных недоступна).
1. Если каждый ключ с данными разбивать на части и записывать сразу на все диски, то для чтения ключа нужно будет читать сразу с n дисков. В нормальном режиме чтение будет с n дисков с блоками данных, в режиме восстановления — с n дисков, часть из которых — диски с блоками данных, а часть — диски с блоками кодов избыточности. Читать с разных дисков можно параллельно, поэтому время чтения всего ключа будет определяться временем чтения с самого медленного диска. Чем больше будет n, тем сильнее будет увеличиваться общее время чтения ключа с данными (в среднем).
2. Можно записывать ключи с данными по-другому: брать некоторое количество ключей, формировать из них последовательность, и уже эту последовательность разбивать на части, дополнять кодами избыточности и записывать на разные диски. В этом случае многие ключи будут целиком располагаться на 1 диске, и чтения будут в среднем выполняться быстрее. Однако, если диск, где хранятся данные, будет недоступен, то для восстановления данных придется делать восстановление, а для этого читать из n дисков (n/l в случае LRC). То есть время чтения будет больше, если нужно восстанавливать данные.
Обе схемы успешно используются на практике, а выбор схемы зависит сразу от ряда факторов. В первой схеме, например, ключи можно записывать независимо, а во второй нужно будет накапливать достаточное количество ключей, и записывать их пачками. С другой стороны, в первой схеме нужно хранить больше служебной информации на дисках, что может сильно увеличивать стоимость хранения маленьких ключей.
Эти два пункта объясняют, какие проблемы возникнут, если попробовать использовать целые числа. Из-за них нельзя использовать целые числа для кодов Рида — Соломона, а нужно использовать элементы поля Галуа. Об этом я пишу в тексте сразу за названными проблемами:
Эти проблемы не позволяют использовать для кодов Рида — Соломона целые числа
Теоретически с помощью кодов избыточности можно обнаружить ошибки, если сравнить исходный блок данных с блоком данных, полученным с помощью восстановления. Но для этого нужно определить, какой блок сравнивать.
На практике в системах хранения данных коды избыточности используют только для восстановления, а для обнаружения ошибок используют контрольные суммы. Например, вместе с каждым блоком может храниться его контрольная сумма (md5, sha256 и т.п.). Перед чтением данных контрольная сумма считается повторно. Если она не совпадает с сохраненной, значит данные повреждены.
Для передачи данных по сети, как правило, используется помехоустойчивое кодирование: вместе с данными отправляется корректирующий код, с помощью которого можно обнаружить и в некоторых случаях исправить ошибки.
Если над проектом работают хотя бы 10 человек хотя бы в двух разных городах — предлагаемый подход гарантированно ведет в тупик
Я говорил в первую очередь про проекты, разрабатываемые одной кроссфункциональной командой. И проекты, разрабатываемые несколькими кроссфункциональными командами, для которых строго распределены зоны ответственности.
Если говорить о создании крупного проекта с нуля, то, разумеется, только небольшое количество высококвалифицированных участников сможет выработать хорошую архитектуру. Если проектированием архитектуры будут заниматься неопытные разработчики, то… ничего хорошего из этого не выйден. Если же участников проектирования архитектуры будет слишком много, то они не смогут эффективно договариваться и много времени будет уходить в пустую.
Другое дело, если это устоявшийся проект с уже утвердившимися архитектурными решениями. Если это крупный востребованный проект, в его беклоге будут постоянно появляться новые фичи, в том числе и большие, требующие доработки архитектуры. Один-два самых опытных разработчика в команде физически не справяться со всеми ответственными моментами. В этом случае надежный выход — свести количество неопытных разработчиков к минимуму, т.е. просто не брать самых медленных верблюдов. Но по моему опыту, такой проект все-таки не движется со скоростью самого медленного разработчика. Просто менее опытные разработчики получают менее ответственные и сложные фичи.
Конечно, вышесказанное — точка зрения, сформированная из-за опыта работы в определенных проектах и командах. Я в основном работал над распределенными высоконагруженными системами в кроссфункциональных agile-командах. Работа в других проектах может приводить к другим точкам зрения.
Да, следить за согласованностью архитектуры конечно нужно. Один хороший способ этого добится — устраивать обсуждения архитектуры с участием опытных коллег. На них член команды, проработавший архитектуру, рассказывает, какую архитектуру он предлагает. Коллеги задают вопросы и предлагают улучшения. Если задуманная архитектура окажется «сырой», цикл проектирования и обсуждения повторяется.
Я встречал как системы, в которых спроектировать хорошую архитектуру сразу не удавалось, так и системы, в которых первоначальная архитектура достаточно продолжительное время не вызывала проблем.
Спроектировать архитектуру хорошо можно, если фиксирован скоуп фичей проекта. Грамотно выбранная архитектура будет подходящей, пока фичи будут браться из первоначального скоупа. Когда начнут появляться новые фичи, которых при разработке архитектуры не было даже в зародыше, текущая архитектура системы может вызывать проблемы. Со временем такие проблемы будут накапливаться, тогда архитектуру системы придется менять. Переделывать все с нуля — затея дорогая, поэтому и возникают проекты-чудовища с огромным техническим долгом.
По описанию похоже на разновидность half sync/half async. Операции выполняются в контексте зеленого потока, а каждая IO операция выполняет переключение на другой зеленый поток, который работает в том же потоке операционной системы. Минусы в появлении дополнительного уровня абстракции и возможности по ошибке заблокировать поток операционной системы, вызвав синхронную операцию.
Название «коды избыточности» прижилось у нас исторически.
Название «erasure codes», конечно, используется чаще. Но и «код(ы) избыточности» иногда употребляют.
В качестве введения в тему также можно использовать другую статью.
Поля Галуа — достаточно сложная тема, которую не получится объяснить в двух словах, или привести короткий понятный пример.
Для использования на практике не обязательно глубоко погружаться в теорию полей Галуа, можно просто считать, что есть некоторые таблицы сложения, вычитания, умножения и деления, и все вычисления происходят с использованием этих таблиц.
Например, можно использовать популярную библиотеку Jerasure для построения кодов избыточности (кодирования) и восстановления данных (декодирования). Решение систем уравнений (которые представляются в виде матричных уравнений), арифметика полей Галуа — это будет выполняться на уровне библиотеки.
1. Если каждый ключ с данными разбивать на части и записывать сразу на все диски, то для чтения ключа нужно будет читать сразу с n дисков. В нормальном режиме чтение будет с n дисков с блоками данных, в режиме восстановления — с n дисков, часть из которых — диски с блоками данных, а часть — диски с блоками кодов избыточности. Читать с разных дисков можно параллельно, поэтому время чтения всего ключа будет определяться временем чтения с самого медленного диска. Чем больше будет n, тем сильнее будет увеличиваться общее время чтения ключа с данными (в среднем).
2. Можно записывать ключи с данными по-другому: брать некоторое количество ключей, формировать из них последовательность, и уже эту последовательность разбивать на части, дополнять кодами избыточности и записывать на разные диски. В этом случае многие ключи будут целиком располагаться на 1 диске, и чтения будут в среднем выполняться быстрее. Однако, если диск, где хранятся данные, будет недоступен, то для восстановления данных придется делать восстановление, а для этого читать из n дисков (n/l в случае LRC). То есть время чтения будет больше, если нужно восстанавливать данные.
Обе схемы успешно используются на практике, а выбор схемы зависит сразу от ряда факторов. В первой схеме, например, ключи можно записывать независимо, а во второй нужно будет накапливать достаточное количество ключей, и записывать их пачками. С другой стороны, в первой схеме нужно хранить больше служебной информации на дисках, что может сильно увеличивать стоимость хранения маленьких ключей.
На практике в системах хранения данных коды избыточности используют только для восстановления, а для обнаружения ошибок используют контрольные суммы. Например, вместе с каждым блоком может храниться его контрольная сумма (md5, sha256 и т.п.). Перед чтением данных контрольная сумма считается повторно. Если она не совпадает с сохраненной, значит данные повреждены.
Для передачи данных по сети, как правило, используется помехоустойчивое кодирование: вместе с данными отправляется корректирующий код, с помощью которого можно обнаружить и в некоторых случаях исправить ошибки.
Я говорил в первую очередь про проекты, разрабатываемые одной кроссфункциональной командой. И проекты, разрабатываемые несколькими кроссфункциональными командами, для которых строго распределены зоны ответственности.
Если говорить о создании крупного проекта с нуля, то, разумеется, только небольшое количество высококвалифицированных участников сможет выработать хорошую архитектуру. Если проектированием архитектуры будут заниматься неопытные разработчики, то… ничего хорошего из этого не выйден. Если же участников проектирования архитектуры будет слишком много, то они не смогут эффективно договариваться и много времени будет уходить в пустую.
Другое дело, если это устоявшийся проект с уже утвердившимися архитектурными решениями. Если это крупный востребованный проект, в его беклоге будут постоянно появляться новые фичи, в том числе и большие, требующие доработки архитектуры. Один-два самых опытных разработчика в команде физически не справяться со всеми ответственными моментами. В этом случае надежный выход — свести количество неопытных разработчиков к минимуму, т.е. просто не брать самых медленных верблюдов. Но по моему опыту, такой проект все-таки не движется со скоростью самого медленного разработчика. Просто менее опытные разработчики получают менее ответственные и сложные фичи.
Конечно, вышесказанное — точка зрения, сформированная из-за опыта работы в определенных проектах и командах. Я в основном работал над распределенными высоконагруженными системами в кроссфункциональных agile-командах. Работа в других проектах может приводить к другим точкам зрения.
Спроектировать архитектуру хорошо можно, если фиксирован скоуп фичей проекта. Грамотно выбранная архитектура будет подходящей, пока фичи будут браться из первоначального скоупа. Когда начнут появляться новые фичи, которых при разработке архитектуры не было даже в зародыше, текущая архитектура системы может вызывать проблемы. Со временем такие проблемы будут накапливаться, тогда архитектуру системы придется менять. Переделывать все с нуля — затея дорогая, поэтому и возникают проекты-чудовища с огромным техническим долгом.
По описанию похоже на разновидность half sync/half async. Операции выполняются в контексте зеленого потока, а каждая IO операция выполняет переключение на другой зеленый поток, который работает в том же потоке операционной системы. Минусы в появлении дополнительного уровня абстракции и возможности по ошибке заблокировать поток операционной системы, вызвав синхронную операцию.