Фэндом


Оригинал: http://research.swtch.com/2008/04/backups-heal-thyself.html
Автор: Russ Cox
Перевод: RapidFX

Venti.jpg

В 2000 году Sean Quinlan и Sean Dorward построили контент-адресуемую систему хранения, названную Venti. Их документ “Venti: a new approach to archival storage” был лучшим из представленных на конференции, посвященной системам хранения. Сегодня речь пойдет о том, как Venti может самостоятельно исцелять себя.

Venti именует объекты используя SHA1-хэши: вы записываете блок и получаете назад SHA-1-хэш. Вы показываете SHA-1-хэш - вам отдают блок. Объекты, большие чем блок, обычно разбиваются на блоки и затем хранятся как дерево. Каждый указатель этого дерева является хэшем SHA-1, который указывает на блок:

Tree1.png

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

Прямой выигрыш от использования контент-адресации в том, что она без ущерба удаляет дубликаты. Если два разных человека записали одни и те же данные, Venti сохранит их только один раз. Или если один человек архивирует одни и те же данные дважды, Venti сохранит их один раз. Моя исследовательская группа MIT запустила Venti-сервер для хранения образа диска основного сервера в файловой системе FFS. Запись одинаковых образов снова и снова сохраняла только измененные блоки, и если множество людей хранило один и тот же гигантский файл, он занимал место только на сервере, но не в Venti. Наша рабочая файловая система использовала около 600GB, однако инкрементальный бэкап в Venti составлял около 2GB за ночь. Все наши ночные бэкапы до 2005 года заняли 3TB или 1.7TB сжатые.

Другая выгода контент-адресации состоит в том, что если данные портятся, вы узнаете об этом. Вы можете проверить возвращенный вам SHA-1-хэш, чтобы убедиться что это тот самый блок, который вам нужен. Клиенты могут проверять данные, возвращаемые сервером, а сервер может проверять данные, возвращаемые ему собственными дисками. Фактически, позже у нас появились большие проблемы с установленным сервером Venti: диски стали выходить из строя.

Несколько лет назад, я скачал весь 6GB файл системной трассировки (http://plan9.bell-labs.com/who/seanq/p9trace.html), о котором говорится в документации Venti. Не все файлы были скачаны корректно: некоторые обрывались слишком рано. Оказалось что Venti-сервер теперь хранит трассировки Bell Labs на поврежденных дисках, и Venti-сервер сообщает об этом, потому что хэши SHA-1 не совпадают. Не проблема, просто используем ранний Venti-сервер с которого была скопирована информация. На этом сервере диск был так же поврежден. Так что трассировки не могли оттуда считаться. Хорошо, трассировки были записаны еще и на ленту. Но и оттуда трассировки не считывались. Разгребая их, оказалось что архивные ленты были неполными: два трассировочных файла все еще содержали пропущенные блоки. Однако существовали также и архивные ленты, на которых была оригинальная файловая система, из которой и была создана трассировка. Они оказались читаемыми, и мы смогли регенерировать поврежденные трассировки и воссоздать полный набор снова. Самая веселая часть. Оригинальные трассировочные файлы хранились в одном архиве Venti, в гигантском дереве хэшей, вроде того, что изображен на картинке выше. Не все файлы можно было прочитать из архива, однако у нас были указатели на недостающие блоки. Создав новый архив хранящий только два недостающий трассировочных файла привело к тому, что старый архив заработал. Теперь у Venti были блоки с нужными хэшами SHA-1, а указатели на недостающие блоки стали указывать на существующие блоки. После подсовывния верного сырого материала, поврежденный архив восстановился самостоятельно.

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

Рекомендуемая литература. Использование SHA1 вообще-то не столь важно, любая устойчивая к коллизиям хэш-функция может сделать это, но все же люди не соглашаются с таким подходом [1]. Запомните, что Venti начали использовать в ситуации, когда еще не было упоминаний о возможности коллизий.

Мы решили, что приемлимым будет использовать 160-битную функцию типа SHA-1 или RIPEMD-160. И тогда шансы на случайную коллизию будут в районе 2^-160. Это чрезвычайно малое число. Вам в 2^90 больше раз повезет выиграть в национальную лотерею США или быть пораженным молнией, чем обнаружить такого типа ошибку в файловой системе.

Обнаружено использование расширения AdBlock.


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

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

Также на Фэндоме

Случайная вики