Хранилище данных на кодах Рида – Соломона

Компания Cleversafe объявила о намерении создать распределенную систему хранения данных емкостью 10 Эбайт, правда, для этого ей придется собрать воедино 4,5 млн дисков емкостью по 3 Тбайт каждый. Умножая на цену одного диска (примерно 300 долл.), получим, что только на диски уйдет больше 1 млрд. долл. К этой сумме следует прибавить затраты на проектирование и все остальные компоненты, однако итог не смущает ЦРУ США, которое через свой фонд In-Q-Tel инвестирует в подобные инновационные разработки.

Cleversafe — компания одного человека по имени Крис Гладвин, который ранее владел другой компанией, продал ее и в поисках нового поприща натолкнулся на книгу «Как поделиться секретом» («How to Share a Secret»), где Ари Шамир, один из основателей компании RSA Security, изложил идею безопасной передачи «распиленного» на части сообщения с последующей его сборкой на стороне получателя. Другим источником вдохновения стали работы в Калифорнийском университете Беркли под руководством Дэвида Паттерсона по проекту OceanStore, который поначалу выглядел совсем по-любительски — что-то вроде проекта SETI@Home, но не с целью объединения процессорной мощности для поиска внеземных цивилизаций, а для объединения в единое хранилище массы дисков отдельных ПК. Естественно, что проект строился на принципах Open Source, но Паттерсон недооценил начинание, назвав его «хранилище для хиппи» (hippie storage), а вот известный венчурный капиталист Стюарт Олсоп отнесся к проекту иначе: «Хранение данных в Интернете — один из самых многообещающих рынков. Но пока еще никто в полной мере не воспользовался этой возможностью».

Конечно, рекордные показатели будущего хранилища от Cleversafe впечатляют, но дело не столько в них, сколько в принципиально новом подходе к системной организации, на котором это хранилище построено. Не случайно название компании переводится как «умное хранение». Был найден принципиально новый подход, названный Distributed Storage («распределенное хранилище»), который может быть распространен и на экстремальные системы, как в случае с ЦРУ, и на системы существенно меньшего размера. Преимущества Distributed Storage складываются из нескольких составляющих, которые органично дополняют друг друга, образуя единую стройную систему:

• алгоритм фрагментации хранимых данных на отдельные «ломтики», известный как IDA (Information Dispersal Algorithm);
• распределение отдельных «ломтиков» по географически распределенным физическим хранилищам PD (Portable Datacenter), которых на данный момент у компании 16 (189 узлов хранения по 45 дисков емкостью 3 Тбайт в каждом);
• использование кодов Рида – Соломона для обеспечения надежности хранения.

Технологическое ноу-хау компании Cleversafe заключается в файловой системе dsgfs (Cleversafe Dispersed Storage Grid File System), которая служит архитектурной основой для создаваемого хранилища. Эта файловая система была создана в 2006 году по проекту с открытом кодом DSGrid и объединяет в себе три перечисленных составляющих. Важно подчеркнуть, что файловую систему следует рассматривать как одно из условий, она обеспечивает логику системы, а с технической точки зрения транспортировки данных создание уникального хранилища стало возможным благодаря достижениям в интернет-технологиях, когда скорость передачи данных по сети стала сравнима со скоростью обмена с дисками на уровне контроллеров дисков. Существующие скорости передачи являются необходимой предпосылкой к созданию распределенных систем хранения. На рисунке показана общая схема распределенного хранения данных DSGrid.

Схема распределенного хранения

Прежде чем углубиться в устройство распределенного хранилища, надо сказать про коды Рида – Соломона (RS), предложенные в 1960 году сотрудниками Линкольновской лаборатории Массачусетского технологического института Ирвином Ридом и Густавом Соломоном для использования в системах дальней космической связи. В 80-е годы началось широкое коммерческое применение RS — сначала в аудиодисках для обеспечения полной сохранности записи и чистоты воспроизведения, невзирая на внешние повреждения, а позже RS внедрили в DVD и Blu-ray. Кроме того, они нашли свое место в системах передачи данных DSL и WiMAX, в ленточных запоминающих устройствах, в контроллерах оперативной памяти и массе других приложений. Обычно эти коды используются в тех случаях, когда есть необходимость за счет избыточности обеспечить надежную передачу данных по ненадежным каналам.

Можно сказать, что коды Рида – Соломона являются логическим развитием известных кодов Хемминга, но они отличаются способностью исправлять большее количество одновременно возникающих ошибок. Математическая теория циклических кодов с исправлением ошибок RS достаточно сложна, но основные ее положения можно изложить, не прибегая к серьезной формалистике. Суть в том, что к последовательности из n символов в исходном сообщении добавляется некоторое количество (m) корректирующих символов, которые смешиваются по алгоритмам RS-кодирования. Заложенная в сообщение избыточность позволяет обнаруживать не одну, как в коде Хемминга, а m ошибок и исправлять до их половины. Число корректирующих символов может быть меньше или равно числу исходных, отношение (n/m) называют коэффициентом резервирования (Redundancy Rate). На рисунке передаваемый байт содержит пять содержательных битов, к которым прибавлено три контрольных. Каждый из байтов передается по одному из возможных восьми маршрутов, и если при передаче по трем любым каналам происходит сбой, то оставшихся пяти достаточно для восстановления исходных данных.

Заслуга инженеров из Cleversafe в том, что они смогли распространить корректирующий потенциал RS на системы хранения, что позволяет отказаться от классических технологий, используемых для обеспечения сохранности данных. При записи хранимые данные нарезаются на «ломтики» и средствами IDA распределяются по географически разнесенным PD, а чтение проводится теми же средствами IDA путем сбора данных из этих пунктов хранения. Если какая-то часть не ответит или передаст с ошибкой, то оставшихся должно хватить на восстановление данных. Способности к самоуправлению и самовосстановлению критически важны, когда дело касается больших объемов данных, а классические методы резервирования перестают работать, например при создании систем резервного копирования петабайтного и больше объема.

Все известные методы, нацеленные на сохранение данных, основаны в конечном счете на инженерных подходах к дублированию и зеркалированию, и, как следствие, требуют отведения для них заметных объемов на дисках или лентах, сложных и дорогостоящих процедур по перемещению на устройствах в зависимости от их востребованности, и при этом данные хранятся «одним куском», что упрощает их кражу. В случае Distributed Storage данные распределены — нет площадки, где бы лежал весь хранимый массив. Трудно представить себе бедствие, которое затронуло бы сразу все пункты хранения, распределенные по всему земному шару. А поскольку мы имеем дело с «нарезкой», кража одного из «ломтиков» лишена смысла — данные естественным образом защищены.

Хранилище Distributed Storage состоит из шлюзов (Gateway) и внутренних серверов (Internal Server), находящихся в PD. Пользователь имеет доступ лишь к одному из ближайших к нему шлюзов, а шлюзы через Интернет общаются с серверами. Логика хранения IDA реализуется шлюзами, осуществляющими разделку данных на «ломтики», распределение по удаленным серверам хранения и выполнение обратной операции сборки данных в единое целое из «ломтиков» с коррекцией в случае обнаружения ошибок. Шлюзы проверяют также сигнатуры пользователей и серверов. Коммуникация между клиентами и системой поддерживается по протоколу SSL, а шлюзы обращаются к серверам по интерфейсу Common Gateway Interface. Информация на тракте от клиента до сервера шифруется по алгоритму RSA с использованием цифровых сертификатов.

Использование IDA не только сокращает трудозатраты на администрирование, исключает окна на выполнение резервирования и в случае необходимости восстановления обеспечивает естественную защиту от катастроф, но и является вполне разумным с точки зрения соотношения надежность хранения / цена по сравнению с традиционными системами резервного копирования. При n-кратном резервировании обеспечивается сохранность при выходе из строя n-1 устройств, но зато и в n и более раз возрастают затраты. Простые массивы RAID дешевле, чем системы резервного копирования, но слишком ненадежны, а более сложные решения теряют преимущества в цене. В системе IDA емкостью 1 Пбайт из 16 узлов хранения допускается выход из строя до четырех из них. Разбиение на блоки занимает 12% дискового пространства, коэффициент избыточности равен n/(n-m), умножаем на 1 Пбайт и добавляем 12%, получаем всего 1,45 Пбайт. Чтобы создать такую же степень защиты в случае систем резервного копирования, потребовалось бы около 5 Пбайт.

Для взлома системы IDA злоумышленнику нужно войти как минимум в n — m узлов и суметь собрать все данные в нужной последовательности, что, учитывая логику RS, практически невероятно. Классические системы резервного копирования такой органичной защиты не имеют и полагаются только на традиционные меры информационной безопасности. Кроме того, чем больше резервных систем, тем больше уязвимость, поскольку растет охраняемый периметр, в то же время масштабирование IDA не влияет на защищенность.

Файловая система dsgfs поддерживается внутренними диспетчерами, связывающими между собой серверы хранения и обеспечивающими оптимальное заполнение серверов, процессы миграции данных между ними и синхронизацию со шлюзами. В результате практически все операции, связанные с хранением, автоматизированы, а масштабирование сводится к физическому наращиванию числа шлюзов и серверов. Таким же образом обеспечивается долговременность хранения данных: в случае замены одного сервера другим всегда остается возможность восстановить содержимое нового за счет избыточности — с использованием средств IDA.

***

Несмотря на наличие заказа со стороны спецслужб, компания Cleversafe, следуя своей ориентации на открытые коды, начала сотрудничать с университетами по программе Academic dsNet, и первым партнером стал Технологический институт штата Иллинойс. Задача этой программы состоит во внедрении технологии Information Dispersal Algorithm в гражданских отраслях.