Рoссийскиe учeныe из Институтa прoблeм пeрeдaчи инфoрмaции им. А.А. Харкевича Российской академии наук (ИППИ РАН), в минувшем году удостоившиеся престижной международной премии за свои исследования эффективных методов восстановления данных в облачных и распределенных системах, в новой статье, опубликованной в начале июня, поделились свежими наработками.

В 2015 году старший научный сотрудник Института проблем передачи информации им. А.А. Харкевича Российской академии наук (ИППИ РАН), профессор Университета Мэрилэнда (США) Александр Барг вместе с Ицхаком Тамо из Тель-Авивского Университета (Израиль) получили одну из самых престижных премий в области теории информации и теории кодирования IEEE Information Theory Society Paper Award за статью в журнале IEEE Transactions on Information Theory, в которой были опубликованы результаты обширного исследования кодов с локальным восстановлением. В текущем году в том же журнале вышла совместная статья Тамо, Барга и старшего научного сотрудника ИППИ РАН Алексея Фролова, в которой предложены границы параметров для таких кодов, применяемых в распределенных системах хранения данных.

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

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

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

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

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

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

ИППИ РАН – один из «пионеров» мирового развития теории кодирования и главный российский центр, где в настоящее время ведутся фундаментальные исследования в этой области, которые успешно сочетаются с практическими разработками по применению помехоустойчивого кодирования в современных телекоммуникационных системах и устройствах.

Источник: пресс-релиз ИППИ РАН