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

Jun 10, 2016 11:48

  Originally posted by nanonews. at Российские учёные нашли способ быстрого восстановления данных

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

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

РАН, наука, информационные технологии

Previous post Next post
Up