Как лучше всего разбить файл на N частей с M избыточными частями, так что любой N из N + M частей достаточно, чтобы восстановить его?

Question

Ищите лучший алгоритм для взятия файла, разбивайте его на N частей, добавьте части M избыточности и затем сохраните файл в N + M разных местах. Обычно файлы будут большими.

Например: 1GB-файл можно разделить на 32-разрядные части (32), иметь (8) дополнительные 32MB части, а избыточную структуру 1.25GB хранить на 40 различных участках. Целью было бы воссоздать файл из любых (32) действительных частей. Независимый хеш оригинальной (32) части будет доступен для проверки правильности правильной реконструкции.

Если это выполнимо, я считаю, что это обеспечит функциональный эквивалент наличия 8 зеркальных копий для накладных расходов всего на 25% (плюс время вычисления), не так ли?

Я нашел алгоритм Рабина 1989 года, который, как представляется, делает это. Интересно, знал ли кто-нибудь о чем-то лучше/быстрее?

Я признаю, что это похоже на то, как работают Raid 5 и Raid 6 - ища такой подход, расширить его до 8 + блоков четности и выполнить его на уровне файла.

Answer 1

То, как вы определили проблему, действительно называется секретным совместным использованием, но с 1989 года были сделаны улучшения - нам больше не нужно указывать M заранее.

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

Это называется «фонтанным кодом»: https://en.wikipedia.org/wiki/Fountain_code. Я считаю, что «хищные коды» сегодня лучше всего: https://en.wikipedia.org/wiki/Raptor_code. Они первыми предоставили линейное кодирование и декодирование времени.

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

Если вам нужно быть абсолютно уверенным в том, что вы можете декодировать сообщение с минимальным количеством блоков, то я обнаружил этот секретный доступ с использованием китайской теоремы останова (описанной здесь: https://en.wikipedia.org/wiki/Secret_sharing#Using_the_Chinese_remainder_theorem), но используя неприводимые полиномы в GF (2^N) вместо простых целых чисел, легко распространяется на фонтанный код, но требует времени (N^2) для кодирования и декодирования.