Bulat_Ziganshin
Silver Member | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
О защите метаинформации:
К примеру, мы добавляем в архив 1% RR. Казалось бы, это означает, что это даёт нам защиту от потери любых 1% данных - например 1% самого архива если RR полностью цела, или 0.5% в теле архива плюс 0.5% в RR. Но на самом всё не так хорошо
Для того, чтобы определить, какие данные целы, а какие нужно восстанавливать, мы сохраняем в RR контрольные суммы (будем условно называть их CRC) секторов данных (т.е. тела архива). Если мы потеряли CRC сектора данных, то мы не знаем, жив он или мёртв, и соответственно не можем использовать его содержимое для восстановления других секторов. А поскольку у нас избыточность данных всего 1%, это означает, что если мы потеряли CRC более чем 1% секторов данных, то мы просто не имеем достаточно информации для восстановления архива. Т.е. информацию в виде ECC секторов мы можем и иметь, а вот информацию о том, к восстановлению чего их собственно применить - нет. Это ключевой момент
Итак, у нас есть 1% RR, в который включены CRC секторов данных. Допустим, эти метаданные мы защищаем более тщательно, чем сами данные - для них мы вычисляем и храним 10% ECC. Допустим, что защита этих метаданных организована идеально - т.е. мы эти записи с CRC + их ECC равномерно размазали по всей RR. И даже при такой идеальной организации выходит вот что - пока мы теряем меньше 10% всей RR, мы (в силу идеального размазывания) теряем меньше 10% этой метаинфы, и следовательно можем полностью её восстановить используя её ECC данные. Но как только потери превысили 10% - ECC метаинфы превращается в тыкву, и всё что у нас остаётся - это сами выжившие CRC секторов данных. Но поскольку метаданные у нас идеально размазаны - то при потере больше 10% всей RR, мы теряем и больше 10% этих CRC, т.е. у нас есть CRC для менее 90% тела архива. И теперь возвращаемся к предыдущему параграфу - поскольку мы имеем CRC для <90% секторов архива, этого недостаточно для запуска процедуры восстановления с имеющейся 1% RR
Таким образом, имея 1% RR, и храня в ней CRC секторов архива с 10% ECC, мы можем восстановить данные после потери 1% в самом архиве при целой RR, или при потере 0.9% в самом архиве и 0.1% в RR, но не сможем ничего восстановить как только в RR пропадёт больше 0.1%. Или например, если мы храним CRC секторов архива с 100% ECC, то не сможем ничего восстановить после потери половины всей RR. Таким образом, возникает асимметрия - потери данных в RR более чувствительны, чем потери в самом архиве, потому что метаинформация хранится только здесь, и потеряв каких-то 8 байт это метаинформации, мы уже не можем использовать для восстановления данных целый сектор архива.
Мы можем пойти ещё дальше и обратить внимание, что критичная метаинформация может быть и в защищаемых данных - например, оглавление в архиве, заголовки файла/фреймов в медиафайлах и т.д. В идеале, вся эта метаинформация нуждается в более тщательной защите, чем остальные данные, поэтому можно вообразить наследника faecc/multipar/..., анализирующего формат защищаемых файлов, и дающего дополнительную защиту метаинформации. Мечтать не вредно 
Теперь о том, как собственно можно решить эту проблему:
1. Математический подход. В теории ECC сектора, про которые точно известно что они потеряны (поскольку не совпадает CRC) называют erasures, а сектора, которые потеряны, но программе о этом неизвестно (в виду отсутвия/пропажи CRC), называют errors. Наши программы традиционно восстанавливают только erasures, но можно их переделать и на работу с errors. Теоретический недостаток этого - что каждый 1% ECC позволяет восстановить 1% erasures, но только 0.5% errors. Практический - алгоритмы такого восстановления более сложны, и я лично не берусь их освоить.
2. Brute force подход. В RAR5 afair каждая группа защиты включает ровно 200 секторов данных. При 10% избыточности, например, это получается 20 секторов ECC. И при каждом секторе ECC сохранены CRC всех секторов данных из этой группы - т.е. при 10% избыточности данных получается 1900% избыточность метаинфы! Зато 100% гарантия, что если жив сектор ECC, то живы и CRC всех секторов данных из его группы. Ну и банально, выбранная Евгением стратегия защиты на порядок проще в реализации других альтернатив. Так что RAR5 уже давно работает, а остальное мы только обсуждаем 
3. Теоретически-идеальный подход - для того, чтобы уравнять в значимости RR и тело архива, необходимо распределить эту метаинфу по всему архиву, а не только RR. Т.е. в самом архиве после каждого сектора данных резервировать несколько байт для записи CRC (других) секторов данных и ECC от этих CRC. Это то, что я упомянул как 4-й пункт в своём плане. Недостатки - объёмная реализация, отказ от концепции "RR просто добавляется в конце архива и от неё легко избавиться, обрезав архив", изменение формата архива - он должен предусматривать вставку посторонних данных внутрь солид-блоков.
Наконец, если вспомнить вышеупомянутую проблему с метаинформацией самого архива (т.е. его оглавлением), то логично включить её в состав этой особо защищаемой информации и точно так же размазать по всему архиву с добавлением ECC. Получится суперзащита. Опять же, zip/rar5 худо-бедно решают эту проблему куда более простыми средствами - дублированием оглавления и размазыванием по архиву одной из копий. Другим архиваторам было бы полезно начать хотя бы с этого |
