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

Предположим, что система хранения состоит из n узлов. Рассмотрим файл, состоящий из B символов поля GF(q), который кодируется в n? символов над GF(q) и распределяется по узлам, так, что каждый узел хранит ? символов. Код построен таким образом, что данные могут быть целиком восстановлены по информации с k узлов. При этом для восстановления данных одного узла достаточно получить ? ? ? информации с d узлов [1,2], см. рис. 1. Величина ? = d? называется диапазоном восстановления (repair bandwidth).

В [2] показано, что размер данных B ограничен сверху:

$$

Рис 1. Регенерирующий код

Для фиксированных значений (B, k, d) существует множество пар (?, ?), удовлетворяющих этой границе, что дает возможность получения компромисса относительно этих параметров, с двумя крайними точками: минимизации величины общего хранилища n? (эта точка называется «восстановлением с минимальным хранилищем», или MSR, Minimum Storage Regeneration) и минимизации диапазона ? = d? (эта точка называется «восстановлением с минимальным диапазоном», или MBR, Minimum Bandwidth Regeneration). Коды, удовлетворяющие приведенной границе, называются регенерирующими кодами. Пример соответствующей границы приведен на рис. 2 [2].


Рис. 2. Кривая MSR-MBR для регенерирующих кодов

В последние годы значительное внимание было уделено как построению кодов в точках MSR и MBR, так и кодов, лежащих на промежуточных точках границы [3,6,7]. Различные конструкции регенерирующих кодов могут быть найдены также в [8-15]. Основной недостаток этих кодов — это плохая масштабируемость.

Мы оптимизировали одну из разновидностей регенерирующих кодов — «butterfly» [4] (данный код является систематическим, это очень важно для запросов типа случайное чтение) для быстрого восстановления одного диска и улучшили масштабируемость данной конструкции.

Butterfly-схема кодирования

Рассмотрим последовательность из $$ страйпов, где n — количество дисков с данными. Данные этого множества страйпов закодированы при помощи XOR-кодов. Первая контрольная сумма (h) рассчитывается по блокам с одним и тем же LBA на всех дисках с данными: $$. Вторая — по Butterfly-схеме, представленной на рисунке 3.


Рис. 3. Butterfly-схема кодирования

Например, расчет контрольной суммы $$ осуществляется как XOR блоков $$. Кроме того, значение имеет еще и цвет блока, который определяется так: если j-й бит в двоичном представлении числа i совпадает с его (j-1)-м битом, то блок $$ будет зеленым. Для нулевого компонента зелеными будут все четные блоки.

В случае, если в получившемся наборе есть блоки зеленого цвета, для каждого из них необходимо включить в набор блок справа от него. Иначе говоря, если блок $$ из основного набора — зеленого цвета, то в набор также включается блок $$. Для блоков, включенных в набор таким образом, цвет значения уже не имеет. Поэтому, формула расчета для $$ будет такова:

$$

Выбор именно такого способа кодирования обосновывается в работе [4]. Так гарантируется восстановление двух одновременно отказавших компонентов.

При использовании этого способа кодирования на восстановление компонента с данными чтений потребуется меньше. А именно, для восстановления $$ блоков отказавшего компонента системы хранения потребуется прочитать $$ блоков, что в пределе снижает количество чтений по сравнению с RAID-6 в 2 раза.

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

Также необходимо понимать, что регенерирующие коды имеют один существенный недостаток: строгое ограничение по количеству блоков в страйпе. Для дискового массива это несущественно, потому что размер кодируемого блока может варьироваться, а значит, может варьироваться и их количество. Но для кластерной конфигурации, в узле которой число дисков может быть ограничено, проблему масштабирования необходимо решать. Одно из возможных решений – разбиение страйпа на регенерирующие группы. Это повысит избыточность во столько раз, сколько групп будет, однако сами кодирующие множества станут экспоненциально меньше, см. рис. 4.


Рис. 4. Экспоненциальное уменьшение страйпов кодируемого множества

Наконец, последнее, что необходимо учитывать при применении регенерирующих кодов — это область, в которую информация с отказавшего диска будет восстанавливаться. Дело в том, что при восстановлении на hot-spare диск скорость восстановления будет ограничена скоростью записи на него, и уменьшение количества чтений не даст значимого выигрыша. Поэтому есть необходимость включить в страйп empty-блок.

Тестирование производительности

Для тестирования производительности мы создавали RAID из 22 дисков с определенными схемами размещения. RAID-устройство создавалось при помощи модификации device-mapper, которая меняла адресацию блока данных по определенному алгоритму. На RAID массив записывались данные, и для них выполнялся расчет контрольных сумм для последующего восстановления. Выбирался отказавший диск. Выполнялось восстановление данных либо на соответствующие empty blocks, либо на hot spare disk. Мы сравнили следующие схемы:

• RAID-6 — классический RAID-6 с двумя контрольными суммами, восстановление данных на hot spare disk.
• RAID-6E — RAID6 c empty блоком в конце страйпа, восстановление данных на empty blocks соответствующих страйпов.
• Classic LRC+E — LRC схема, в которой локальные группы идут последовательно и заканчиваются контрольной суммой, восстановление на empty block.
• LRC rand — для генерации каждого LRC-страйпа, его номер используется в качестве ядра генератора случайных числе, восстановление данных на empty block.
• Classic Regen — схема с тремя группами регенерирующих кодов.
• Regen rand — схема с тремя группами регенерирующих кодов и рандомизацией, восстановление данных на empty block.

Для тестирования использовались 22 диска со следующими характеристиками:

• MANUFACTURER: IBM
• PART NUMBER: ST973452SS-IBM
• CAPACITY: 73GB
• INTERFACE: SAS
• SPEED: 15K RPM
• SIZE FORM FACTOR: 2.5IN

При тестировании производительности большой эффект оказывает размер блоков страйпа. При восстановлении чтение с дисков ведется по возрастающим адресам (последовательно), но из-за декластеризации в случайных схемах расположения некоторые блоки пропускаются. Это значит, что если блоки имеют маленький размер, то позиционирование магнитной головки диска будет производиться очень часто, и это пагубно скажется на производительности. Поскольку конкретные значения скорости восстановления данных могут зависеть от модели жестких дисков, производителя, RPM, мы представили полученные результаты в относительных величинах. На рис 5. изображено то, какой прирост производительности дают схемы (b) – (f) по сравнению с классическим RAID-6.


Рис. 5. Относительная производительность различных алгоритмов размещения

При восстановлении данных на hot spare диск мы получали, что скорость восстановления ограничивается скоростью записи на диск для всех схем, использующих hot spare. Можно заметить, что как рандомизированная LRC-схема, так и регенерирующие коды дают достаточно высокий прирост скорости восстановления по сравнению с не оптимальной и RAID-6. Несмотря на то, что регенерирующие коды явно лидируют по скорости восстановления, нельзя не учитывать их основные минусы: ограничение по количеству блоков в кодируемом множестве и большая избыточность: c учетом empty-блока в проверяемой конфигурации избыточность была более 30% (рис. 6).


Рис. 6. Избыточность различных алгоритмов

Заключение

Регенерирующие Butterfly-коды были успешно опробованы в HDFS, Ceph[5].

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

Несмотря на то, что производительность этого решения оказалась наилучшей (см. рис 5), требования по избыточности (см. рис 6) могут повлечь большие затраты, поэтому этот алгоритм подойдет не везде. Таким образом, всегда нужно понимать, можно ли в конкретном случае пожертвовать местом ради надежности.

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