Оптимизация работы алгоритма распыления информации в системе распределенного хранения
Рассматривается задача оптимизации работы алгоритмов распыления информации и ее последующего восстановления в системе распределенного хранения. К системе хранения информации предъявляется требование надежности и конфиденциальности. Приводятся результаты тестирования предложенных алгоритмов. Розгляда...
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2013 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/85052 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Оптимизация работы алгоритма распыления информации в системе распределенного хранения / В.В. Бойко, В.В. Горин, В.Н. Кузьменко // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 113-118. — Бібліогр.: 3 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-85052 |
|---|---|
| record_format |
dspace |
| spelling |
Бойко, В.В. Горин, В.В. Кузьменко, В.Н. 2015-07-18T17:04:00Z 2015-07-18T17:04:00Z 2013 Оптимизация работы алгоритма распыления информации в системе распределенного хранения / В.В. Бойко, В.В. Горин, В.Н. Кузьменко // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 113-118. — Бібліогр.: 3 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/85052 519.85 Рассматривается задача оптимизации работы алгоритмов распыления информации и ее последующего восстановления в системе распределенного хранения. К системе хранения информации предъявляется требование надежности и конфиденциальности. Приводятся результаты тестирования предложенных алгоритмов. Розглядається задача оптимізації роботи алгоритма розпилення інформації та її наступного відновлення у системі розподіленого зберігання. До системи зберігання інформації висуваються вимоги надійності та конфіденційності. Наводяться результати тестування запропонованих алгоритмів. The problem of information dispersal algorithm optimization in distributed data storage is discussed. Necessary security, reliability and confidentiality requirements are claimed. Testing results for algorithms proposed provided. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Оптимизация работы алгоритма распыления информации в системе распределенного хранения Оптимізація роботи алгоритма розпилення інформації у системі розподіленого зберігання Information dispersal algorithm optimization in a distributed storage system Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Оптимизация работы алгоритма распыления информации в системе распределенного хранения |
| spellingShingle |
Оптимизация работы алгоритма распыления информации в системе распределенного хранения Бойко, В.В. Горин, В.В. Кузьменко, В.Н. |
| title_short |
Оптимизация работы алгоритма распыления информации в системе распределенного хранения |
| title_full |
Оптимизация работы алгоритма распыления информации в системе распределенного хранения |
| title_fullStr |
Оптимизация работы алгоритма распыления информации в системе распределенного хранения |
| title_full_unstemmed |
Оптимизация работы алгоритма распыления информации в системе распределенного хранения |
| title_sort |
оптимизация работы алгоритма распыления информации в системе распределенного хранения |
| author |
Бойко, В.В. Горин, В.В. Кузьменко, В.Н. |
| author_facet |
Бойко, В.В. Горин, В.В. Кузьменко, В.Н. |
| publishDate |
2013 |
| language |
Russian |
| container_title |
Теорія оптимальних рішень |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Оптимізація роботи алгоритма розпилення інформації у системі розподіленого зберігання Information dispersal algorithm optimization in a distributed storage system |
| description |
Рассматривается задача оптимизации работы алгоритмов распыления информации и ее последующего восстановления в системе распределенного хранения. К системе хранения информации предъявляется требование надежности и конфиденциальности. Приводятся результаты тестирования предложенных алгоритмов.
Розглядається задача оптимізації роботи алгоритма розпилення інформації та її наступного відновлення у системі розподіленого зберігання. До системи зберігання інформації висуваються вимоги надійності та конфіденційності. Наводяться результати тестування запропонованих алгоритмів.
The problem of information dispersal algorithm optimization in distributed data storage is discussed. Necessary security, reliability and confidentiality requirements are claimed. Testing results for algorithms proposed provided.
|
| issn |
XXXX-0013 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/85052 |
| citation_txt |
Оптимизация работы алгоритма распыления информации в системе распределенного хранения / В.В. Бойко, В.В. Горин, В.Н. Кузьменко // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 113-118. — Бібліогр.: 3 назв. — рос. |
| work_keys_str_mv |
AT boikovv optimizaciârabotyalgoritmaraspyleniâinformaciivsistemeraspredelennogohraneniâ AT gorinvv optimizaciârabotyalgoritmaraspyleniâinformaciivsistemeraspredelennogohraneniâ AT kuzʹmenkovn optimizaciârabotyalgoritmaraspyleniâinformaciivsistemeraspredelennogohraneniâ AT boikovv optimízacíârobotialgoritmarozpilennâínformacííusistemírozpodílenogozberígannâ AT gorinvv optimízacíârobotialgoritmarozpilennâínformacííusistemírozpodílenogozberígannâ AT kuzʹmenkovn optimízacíârobotialgoritmarozpilennâínformacííusistemírozpodílenogozberígannâ AT boikovv informationdispersalalgorithmoptimizationinadistributedstoragesystem AT gorinvv informationdispersalalgorithmoptimizationinadistributedstoragesystem AT kuzʹmenkovn informationdispersalalgorithmoptimizationinadistributedstoragesystem |
| first_indexed |
2025-11-26T18:39:58Z |
| last_indexed |
2025-11-26T18:39:58Z |
| _version_ |
1850768708155211776 |
| fulltext |
Теорія оптимальних рішень. 2013 113
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Рассматривается задача опти-
мизации работы алгоритмов рас-
пыления информации и ее после-
дующего восстановления в сис-
теме распределенного хранения. К
системе хранения информации
предъявляется требование на-
дежности и конфиденциально-
сти. Приводятся результаты те-
стирования предложенных алго-
ритмов.
В.В. Бойко, В.В. Горин,
В.Н. Кузьменко, 2013
ÓÄÊ 519.85
Â.Â. ÁÎÉÊÎ, Â.Â. ÃÎÐÈÍ, Â.Í. ÊÓÇÜÌÅÍÊÎ
ÎÏÒÈÌÈÇÀÖÈß ÐÀÁÎÒÛ ÀËÃÎÐÈÒÌÀ
ÐÀÑÏÛËÅÍÈß ÈÍÔÎÐÌÀÖÈÈ
 ÑÈÑÒÅÌÅ ÐÀÑÏÐÅÄÅËÅÍÍÎÃÎ
ÕÐÀÍÅÍÈß
Введение. Алгоритмы распыления (распреде-
ления) информации – одна из основных ком-
понент в системах распределенного хранения,
с помощью которых решаются такие задачи
обработки и хранения информации как на-
дежность, безопасность, защищенность, ско-
рость доступа и другие. Распределенное хра-
нение информации может применяться как в
компьютерной сети, так и на отдельном носи-
теле информации для ее более эффективной
обработки. Вопрос надежности передачи ин-
формации возникает при параллельной ее об-
работке, при параллельных и распределенных
вычислениях, при использовании облачных
технологий [1–3].
В общем задача ставится следующим об-
разом. Необходимо обеспечить надежное
хранение конфиденциальной информации на
распределенных носителях, а также быстрый
доступ к ней и обработку.
Простейший вариант решения задачи – это
шифрование файлов и хранение нескольких
копий зашифрованных файлов на различных
носителях. Однако такой вариант решения
задачи является самым затратным по объе-
мам хранения и передачи данных и избыточ-
ным по надежности. Если зашифрованный
файл F хранится в k копиях и вероятности
потери одной копии независимы и равны 1p ,
то общий объем хранения равен Fk ⋅ , а ве-
роятность сохранения информации равна
k
sf pp 11 −= , где F – размер файла.
В.В. БОЙКО, В.В. ГОРИН, В.Н. КУЗЬМЕНКО
114 Теорія оптимальних рішень. 2013
Другой вариант решения – это распределить информацию, хранящуюся в
файле, на n файлов niFi ,...,1, = меньшего размера FF <i таким образом,
чтобы исходный файл можно было восстановить по любым nk < частям, а об-
щий объем хранения ∑
= ni
iF
,...,1
был меньше, чем в первом варианте
FFFk
ni
i >>⋅ ∑
= ,...,1
. Вероятность сохранения полной информации в этом случае
определяется биноминальным распределением
∑∑
−
=
−
−
=
−
−−=−=
1
0
11
0
11 )1(1)1(
k
t
ttnt
n
kn
t
tntt
nsf ppCppCp .
При хранении и передаче информации наиболее уязвимым этапом является
передача файлов или его частей по каналам связи. Поэтому при потере некото-
рых передаваемых частей исходного файла возможно его восстановление, но
для этого необходимо выполнить передачу дополнительных частей или повто-
рить передачу не прошедших частей.
Для первого варианта, когда файл хранится целиком, математическое ожи-
дание времени передачи файла при повторных попытках передается до тех пор
пока файл не пройдет и оценивается так:
)1()1(
1
)1()1()1(
1
2
1
1
1
1
1
11
1
1
1 p
t
p
ptpsptppstt F
F
s
s
F
s
s
FF
−
=
−
−=⋅−=−⋅=
−
∞
=
−
∞
=
∑∑ ,
где Ft – время передачи файла; s – попытка, с которой удалось передать файл;
1p – вероятность не прохождения передачи.
При распределенном хранении файла возможна параллельная передача его
частей с пропорциональным уменьшением времени. В этом случае будем счи-
тывать все n частей. Если будет удачно считано k частей и больше из n , то
файл будет восстановлен, если удачно считанных частей будет меньше, то эти
части параллельно будут считаться еще раз. Для такого варианта время считы-
вания оценим следующим образом. Пусть td – это доля файла, считанная при
условии, что nt ,...,0= частей не были считаны. Для knt −= ,...,0 файл может
быть восстановлен, следовательно 1=td , для nknt ,...,1+−= ktnd t /)( −= .
Математическое ожидание доли файла, которая будет считана за первую
попытку считывания равно
∑∑∑
+−=
−
−
=
−
=
−
−
−
+−=−=
n
knt
tntt
n
kn
t
tntt
n
n
t
tntt
nt ppC
k
tn
ppCppCdd
1
11
0
11
0
11 )1()1()1( .
Среднее время считывания файла в этом случае оценим как dtt
ii FF /= ,
где
iFt – время считывания одной части, одинаковое для всех частей.
ОПТИМИЗАЦИЯ РАБОТЫ АЛГОРИТМА РАСПЫЛЕНИЯ ИНФОРМАЦИИ В СИСТЕМЕ …
Теорія оптимальних рішень. 2013 115
Дадим формальное определение алгоритму распыления информации. Алго-
ритм распыления информации (Information dispersal algorithm – IDA) – это алго-
ритм разделения секрета, который используется для побитовой «нарезки» дан-
ных таким образом, что когда данные передаются по сети либо сохраняются на
носителях информации, то невозможно определить исходную последователь-
ность бит, не имея соответствующего ключа. При наличии ключа информация
может быть восстановлена. Таким образом, можно сказать, что IDA – это функ-
ция, принимающая, как минимум, два аргумента – исходное сообщение m и не-
который секретный ключ kS . Результат работы данной функции – набор сооб-
щений im одинаковой длины, сумма длин которых равна длине исходного со-
общения. Сообщения im состоят из тех же блоков (битов, байтов и т. д.), что и
исходное сообщение, но в другой последовательности, которая однозначно оп-
ределяется ключом kS .
Для последующего восстановления исходного сообщения необходимо ис-
пользовать алгоритмы восстановления или коды восстановления. Код восста-
новления от потерь (erasure code – EC) – это разновидность кодов прямой кор-
рекции ошибок (forward error correction – FEC), который преобразует сообщение
из k символов в более длинное сообщение (кодовое слово), состоящее из n
символов таких, что исходное сообщение может быть восстановлено из некого
подмножества этих n символов.
В литературе алгоритмы распыления и восстановления не всегда описыва-
ются как самостоятельные алгоритмы. Некоторые авторы оба вышеописанных
понятия объединяют в одно и в зависимости от того, чему уделяется больше
внимания, называют объединенный алгоритм как IDA, так и EC [1, 2]. В данной
работе эти алгоритмы разделяются.
Рассматривается использование оптимальных кодов восстановления. Опти-
мальные коды восстановления потерь обладают тем свойством, что любых k из
n кодовых слов достаточно для восстановления исходного сообщения.
Оба алгоритма IDA и EC могут быть эффективно применены: 1) при пере-
даче данных по небезопасному каналу с возможной потерей части информации;
2) при сохранении данных на массив запоминающих устройств (storage array,
далее – массив). Рассмотрим более подробно пункт 2).
Постановка задачи. Необходимо хранить исходные данные на массив так,
чтобы:
1) потенциальный злоумышленник не смог восстановить исходные данные,
даже при наличии у него доступа ко всем устройствам (storage nodes);
2) выход из строя некоторого количества устройств не привел к потере ис-
ходных данных и не нарушил требования пункта 1).
Будем считать, что у нас есть исходное сообщение m длины s бит, которое
мы сохраним на n устройств так, чтоб любых k устройств было достаточно для
восстановления исходного сообщения.
В.В. БОЙКО, В.В. ГОРИН, В.Н. КУЗЬМЕНКО
116 Теорія оптимальних рішень. 2013
Для достижения поставленных целей последовательно применяются алго-
ритмы IDA и EC (рисунок) следующим образом:
1) с помощью IDA исходное сообщение m разбивается на k сообщений
im . На этом шаге выбирается секретный ключ kS , который необходим для об-
ратной сборки исходного сообщения;
2) с помощью EC генерируется дополнительно kn − кодовых сообщений
jm . Для создания оптимального кода восстановления потерь здесь используется
алгоритм, основанный на алгоритме Рида – Соломона [3];
3) полученные сообщения im и jm объединяются в одно множество и
записываются на устройства хранения данных.
РИСУНОК. Схема последовательной работы алгоритмов IDA и EC
Выполнение перечисленных пунктов позволяет достичь поставленной зада-
чи и гарантировать выполнение свойств пп. 1) и 2). К тому же хранение исход-
ного сообщения в таком виде имеет некоторые дополнительные преимущества.
Поскольку для получения исходного длинного сообщения нужно прочесть k
коротких сообщений im c разных устройств, то операцию чтения можно распа-
раллелить, уменьшив в k раз время чтения с массива запоминающих устройств.
Таким образом к заданным свойствам пп. 1) и 2) добавляются следующие свой-
ства, касающиеся обработки информации:
ОПТИМИЗАЦИЯ РАБОТЫ АЛГОРИТМА РАСПЫЛЕНИЯ ИНФОРМАЦИИ В СИСТЕМЕ …
Теорія оптимальних рішень. 2013 117
4) операцию чтения можно ускорить в k раз по сравнению с операцией
чтения одного длинного сообщения с одного устройства. Аналогичное свойство
справедливо и для операции записи на устройства.
Алгоритм оптимального кода восстановления потерь можно выбрать так,
чтобы при необходимости сгенерировать дополнительное кодовое слово (сооб-
щение) не нужно было повторять генерацию предыдущих слов. Таким образом
получаем еще одно важное свойство:
5) уровень избыточности kn / можно менять, не затрагивая уже сохранен-
ные на запоминающих устройствах сообщения.
Рассмотрим подробнее, как можно построить необходимые алгоритмы.
Для построения IDA можно воспользоваться криптостойким генератором
псевдослучайных чисел на базе AES (Advanced Encryption Standard). Ключ kS
можно использовать как инициализирующее случайное число (random seed) ге-
нератора. Числа, получаемые на выходе генератора, можно использовать в каче-
стве номера сообщения i , в которое записывается следующий блок
(бит/байт/…) из исходного сообщения m .
Для оптимизации работы IDA могут быть использованы различные крите-
рии и, в частности, те, которые описаны в начале статьи – оптимизация по мате-
матическому ожиданию времени записи-считывания информации, по объему
хранимой информации, по надежности ее хранения и передачи.
Результаты тестирования. Тестирование проводилось для проверки и под-
тверждения работоспособности и эффективности применения алгоритма распы-
ления информации. Было проведено измерение скорости передачи данных с ис-
пользованием IDA/EC алгоритма и без него. Тестовое приложение разворачива-
лось на серверах Windows Azure (один сервер на восточном побережье США,
один – на западном). Тестовый файл «распылялся» на сервера Amazon S3 (три
точки в США), Google Cloud (одна точка в США), Windows Azure (две точки в
США) с избыточностью 50% так, чтоб его можно было собрать при потере со-
единения с любым из трех провайдеров. По результатам, представленным далее,
можно видеть, что скорость «распыления» данных выше, чем наибольшая из
прямых скоростей (raw speed) доступа Azure/Amazon/Google и более чем в 10
раз больше наименьшей. В табл. 1 приведена скорость закачки файла на сервер,
в табл. 2 – скорость скачивания файла с сервера. Скорость в таблицах указана в
мегабитах в секунду.
ТАБЛИЦА 1. Скорость закачки (upload speed) файла объемом 1Гб
Test
Application
Location
Raw Speed IDA/EC
Algorithm
Speed
Google Cloud Amazon S3 Windows
Azure
US East 8,46 Mbps 72,72 Mbps 97,68 Mbps 119,19 Mbps
US West 2,68 Mbps 44,98 Mbps 70,54 Mbps 78,66 Mbps
В.В. БОЙКО, В.В. ГОРИН, В.Н. КУЗЬМЕНКО
118 Теорія оптимальних рішень. 2013
ТАБЛИЦА 2. Скорость загрузки (download speed) файла объемом 1Гб
Test
Application
Location
Raw Speed IDA/EC
Algorithm
Speed
Google Cloud Amazon S3 Windows
Azure
US East 113,77 Mbps 34,27 Mbps 95,35 Mbps 162,01 Mbps
US West 85,53 Mbps 44,88 Mbps 105,02 Mbps 156,49 Mbps
Заключение. В результате выполненной работы построены алгоритмы рас-
пыления и восстановления информации, которые показали высокие скорости
записи и считывания. Дальнейшее развитие работы будет направлено на улуч-
шение эффективности работы алгоритмов и оптимизации их работы по другим
критериям.
В.В. Бойко, В.В. Горін, В.М. Кузьменко
ОПТИМІЗАЦІЯ РОБОТИ АЛГОРИТМА РОЗПИЛЕННЯ ІНФОРМАЦІЇ
У СИСТЕМІ РОЗПОДІЛЕНОГО ЗБЕРІГАННЯ
Розглядається задача оптимізації роботи алгоритма розпилення інформації та її наступного
відновлення у системі розподіленого зберігання. До системи зберігання інформації висува-
ються вимоги надійності та конфіденційності. Наводяться результати тестування запропоно-
ваних алгоритмів.
V.V. Boyko, V.V. Gorin, V.M. Kuzmenko
INFORMATION DISPERSAL ALGORITHM OPTIMIZATION IN A DISTRIBUTED STORAGE
SYSTEM
The problem of information dispersal algorithm optimization in distributed data storage is
discussed. Necessary security, reliability and confidentiality requirements are claimed. Testing
results for algorithms proposed provided.
1. Lin S.J., Chung W.H. An efficient (n, k) information dispersal algorithm for high code rate
system over fermat fields // IEEE Communications Letters. – 2012. – Vol. 16, 12. –
P. 2036–2039.
2. Weatherspoon H., Kubiatowicz J.D. Erasure coding vs. replication: A quantitative comparison
// Lecture Notes in Computer Science. – 2002. – Vol. 2429. – P. 328–337.
3. Горин В.В., Лютенко В.М. Имплементация и оптимизация алгоритма Рида-Соломона для
создания кодов восстановления потерь в данных // Теорія оптимальних рішень. – 2012. –
С. 126–135.
Получено 13.03.2013
|