ФЭНДОМ


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

Venti

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

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

Tree1

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

Прямой выигрыш от использования контент-адресации в том, что она без ущерба удаляет дубликаты. Если два разных человека записали одни и те же данные, 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 больше раз повезет выиграть в национальную лотерею США или быть пораженным молнией, чем обнаружить такого типа ошибку в файловой системе.