14.06.2016

Российские ученые нашли способ быстрого восстановления данных

Старший научный сотрудник Института проблем передачи информации Российской академии наук (ИППИ РАН), профессор Университета Мэрилэнда (США) Александр Барг вместе с Ицхаком Тамо из Университета Тель-Авива (Израиль) и старшим научным сотрудником ИППИ РАН Алексеем Фроловым предложили границы параметров для кодов с локальным восстановлением, применяемых в распределенных системах хранения данных.

Их статья вышла в журнале IEEE Transactions on Information Theory. Годом раньше за публикацию в том же издании Барг и Тамо получили одну из самых престижных премий в области теории информации и кодирования IEEE Information Theory Society Paper Award за обширное исследование кодов с локальным восстановлением.

Чтобы обезопасить пользователей от потери данных, любую информацию – как на персональных компьютерах, так и в виртуальных хранилищах (социальные сети, «облака») – распределяют на нескольких серверах или дисках. Ведь выход из строя дисков является частым явлением.

В современных распределенных системах существует 2 способа защиты данных:

1. Их дублирование (back-up) на нескольких дисках – если один из них выходит из строя, то для восстановления хранящейся на нем информации достаточно обратиться к одному диску с копией (или, по-другому, служебной информацией). Время восстановления минимальное, однако общий объём информации очень большой, например, если данные повторяются 3 раза, то объем служебной информации – 200 процентов.

2. Использование кодов Рида-Соломона. В этом случае объём служебной информации минимален, но восстановление происходит значительно дольше. К примеру, Facebook использует код Рида-Соломона с параметрами (14, 10). В этом случае объем служебной информации – 40 процентов, но для восстановления одного диска нужно считать данные с 10 других.

Поскольку чаще всего выходит из строя именно один диск, то возникает задача построения кодов со свойством локального восстановления. Такие коды должны «уметь» восстанавливать испорченный диск с минимальным числом обращений к другим дискам. Объем служебной информации также должен быть минимален.

Впервые коды с локальным восстановлением были предложены сотрудниками компании Microsoft П. Гопаланом, С. Еханиным и др. Они установили оценку минимального объёма служебной информации при таком кодировании.

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

В статье, опубликованной в июньском номере журнала IEEE Transactions on Information Theory, Тамо, Барг и Фролов исследовали обобщение кодов с локальным восстановлением и получили нижние и верхние границы для параметров кодов с многими восстанавливающими множествами, таких как объем служебной информации и минимальное расстояние.

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

Источники:

1. km.ru