Система надежного облачного хранения с регулируемой избыточностью данных
RELIABLE CLOUD STORAGE SYSTEM WITH ADJUSTABLE DATA REDUNDANCY

Изобретение относится к вычислительным модулярным системам и предназначено для выполнения подготовки исходных файлов для надежного облачного хранения, посредством перевода в полиномиальную систему классов вычетов и используя код проверки четности.
Известны система и способ взаимодействия пользователей с облачными объектными хранилищами данных (патент RU2656836, опубл. 06.06.2018), которые относятся к технологиям сетевой связи. Изобретение позволяет повысить безопасность хранения данных. Шлюз содержит: три последовательно соединенных блока, где каждый блок содержит в себе один или более модулей, где: первый блок предназначен для осуществления взаимодействия шлюза с пользовательским терминалом, в котором модули являются одним или более вариантами из: программного web-сервера; интерфейса взаимодействия с web-сервером; второй блок предназначен для обработки запросов и данных, поступающих от пользовательского терминала в первый блок, в котором модули являются одним или более вариантами из: шифрования данных; дешифрования данных; сжатия данных; восстановления данных; кеширования данных; дедупликации и данных; кодирования данных; расщепления данных по n,k-схеме; восстановления данных по n,k-схеме; третий блок, состоящий из модулей взаимодействия с облачными хранилищами, предназначенный для реализации взаимодействия с облачными службами хранения данных через интерфейс взаимодействия с облачным хранилищем.
Недостатком является ограниченная надежность и адаптивность избыточности алгоритмов.
Известен механизм координации для выбора облака (патент RU2628902, опубл. 22.08.2017), который относится к средствам выбора и управления публичной сетью облачных вычислений для размещения учетной информации клиента и заключается в автоматическом выборе публичного облака, которое удовлетворяет набору критериев, определенных администраторами, и обеспечении упрощенного взаимодействия с выбранным публичным облаком. Результат обеспечивается выполнением способа распределения нагрузки по одной или более публичным вычислительным сетям, при этом: принимают выданный пользователем частной корпоративной сети запрос на обновление учетной информации; идентифицируют, с использованием средства координации, целевую вычислительную сеть из упомянутых одной или более публичных вычислительных сетей; переводят упомянутые одну или более команд в формат, совместимый с языком правил, соблюдаемым целевой вычислительной сетью при взаимодействии с внешним источником; и инициируют распределение этих одной или более переведенных команд по вычислительным ресурсам, связанным с целевой вычислительной сетью, которые предназначены для выполнения упомянутого обновления учетной информации.
Недостатком данного способа является отсутствие информации о корректирующих свойствах и избыточности используемых алгоритмов.
Известно многоканальное адаптивное устройство кодирования и передачи данных на основе системы остаточных классов (Патент UA105430, опубл. 12.05.2014), которое содержит модуль разделения данных в системе остаточных классов, модуль определения состояния канала связи; модуль адаптивного распределения частей сообщений; модуль передачи данных, модуль приема данных, модуль обнаружения и исправления ошибок в системе счисления остатков, модуль адаптивного изменения корректирующих баз системы счисления остатков, причем распределение частей сообщения между доступными путями происходит адаптивно в зависимости от размера сообщения и характеристики путей. Предлагаемый метод позволяет повысить надежность и емкость передачи данных.
Недостатком является сложность реализации алгоритмов адаптации избыточности.
i
i
i
Известны способ и устройство для выполнения вычислений с использованием арифметики вычетов (Патент US7523151, опубл. 21.04.2009), которые могут использовать логические вентили для выполнения таких вычислений, как умножение на константу, вычисление теоретико-числового логарифма остатка для заданного основания α и модуля p, а также вычисление произведения двух остатков по модулю p. Использование логических вентилей может дать преимущества по сравнению с использованием ПЗУ для функций поиска таблиц в интегрированных реализациях системы остаточных чисел цифровых сигнальных процессоров.
Недостатком является ограниченная надежность и адаптивность избыточности алгоритмов.
Известно устройство для преобразования числа из системы остаточных классов в позиционный код (патент RU2293437, опубл. 22.08.2017), которое относится к вычислительной технике и предназначено для использования в вычислительных устройствах, функционирующих в системе остаточных классов (СОК), а также технике связи для передачи информации кодами СОК. Технический результат данного изобретения – сокращение объема оборудования и повышение быстродействия при преобразовании числа из СОК в позиционный код. Для этого устройство содержит группу постоянных запоминающих устройств, группу регистров, разрядно-параллельный сумматор по модулю.
Сущность данного устройства основана на группировке при сложении по два произведения и вычисления остатка по большому модулю, однако данный метод не обладает достаточной адаптивностью избыточности и надежностью.
M
m
x
M
x
M
x
m
m
M
x
y
x
y
M
M
x
y
M
x
,y
Z
Z
i
i
i
j
j
j
i
i
j
j
j
j
j
i
i
i
i
i
i
Известно электронное вычислительное устройство (RU2019121710, опубл. 20.03.2021), выполненное с возможностью вычисления произведения целых чисел, причем устройство содержит: - хранилище, выполненное с возможностью хранения целых чисел в представлении многослойной системы остаточных классов (СОК), причем представление многослойной СОК имеет по меньшей мере СОК верхнего слоя и СОК нижнего слоя, причем СОК верхнего слоя является системой остаточных классов для последовательности нескольких верхних модулей , причем СОК нижнего слоя является системой остаточных классов для последовательности нескольких нижних модулей , причем целое число  представляется в хранилище посредством последовательности нескольких верхних вычетов  по модулю последовательности верхних модулей , причем верхние вычеты  для по меньшей мере одного конкретного верхнего модуля  дополнительно представляются в хранилище посредством последовательности нескольких нижних вычетов  верхнего вычета  по модулю последовательности нижних модулей , при этом по меньшей мере один из нескольких нижних модулей  не делит модуль из нескольких верхних модулей ; схему процессора выполненную с возможностью вычисления произведения первого целого числа  и второго целого числа , причем первое и второе целое число хранится в хранилище в соответствии с представлением многослойной СОК, причем процессор сконфигурирован c по меньшей мере нижней процедурой умножения и верхней процедурой умножения, причем нижняя процедура умножения вычисляет произведение двух дополнительно представленных верхних вычетов ,, соответствующих одному и тому же верхнему модулю , по модулю упомянутого верхнего модуля , верхняя процедура умножения вычисляет произведение первого и второго целого числа посредством покомпонентного умножения верхних вычетов первого целого числа  и соответствующих верхних вычетов второго целого числа  по модулю соответствующего модуля , при этом верхняя процедура умножения вызывает нижнюю процедуру умножения для умножения верхних вычетов, которые являются дополнительно представленными, при этом верхняя процедура умножения выполнена с возможностью приема верхних вычетов , которые меньше предварительно определенного коэффициента расширения, умноженного на соответствующий модуль  и выполнена с возможностью создания верхних вычетов  произведения принятых верхних вычетов , которые меньше предварительно определенного коэффициента расширения, умноженного на соответствующий модуль
Недостатком данного изобретения является использование двухуровневой СОК, что приводит к алгоритмической сложности, также в данном изобретении не раскрыты корректирующие возможности СОК.
Известна нейронная сеть для обнаружения ошибок в симметричной системе остаточных классов (патент RU2374678, опубл. 27.11.2009), которая относится к вычислительной технике и может быть использована для построения модулярных нейрокомпьютеров, функционирующих в симметричной системе остаточных классов. Техническим результатом данного изобретения является уменьшение аппаратной сложности. Заявленная нейронная сеть содержит блок нейронной сети конечного кольца формирования старшего коэффициента обобщенной позиционной системы счисления, блок сдвига полярности, блок определения ошибки, шины «есть ошибки».
Недостатком данного изобретения является отсутствие корректирующих свойств неизбыточной СОК.
Известно устройство для преобразования двоичного кода в код системы остаточных классов (патент RU2413279, опубл. 27.02.2011), которое относится к области вычислительной техники и может быть использовано в вычислительных системах для преобразования двоичных кодов в коды системы остаточных классов. Техническим результатом данного изобретения является увеличение разрядности преобразуемых в СОК двоичных кодов. Устройство содержит входной регистр, коммутатор, мультиплексор, схему коррекции, два сумматора по модулю, два регистра для фиксации промежуточных результатов суммирования по модулям, три выходных регистра.
Недостатком данного изобретения являются ограниченные корректирующие возможности используемой СОК.
Известно устройство для обнаружения переполнения динамического диапазона, определения ошибки и локализации неисправности вычислительного канала в ЭВМ, функционирующих в системе остаточных классов (патент RU2483346, опубл. 27.05.2013), которое относится к вычислительной технике и может быть использовано при диагностике вычислительных систем для обнаружения переполнения динамического диапазона, определения ошибки и локализации неисправного канала в ЭВМ, функционирующих в системе остаточных классов. Техническим результатом является повышение скорости определения функциональных характеристик и сокращения аппаратурных затрат. Устройство содержит входные регистры, схемы формирования проекций, блоки памяти, сумматоры, схему анализа, логические элементы «И», триггер, счетчик проекций.
Недостатком данного изобретения является использование приближенной Китайской теоремы об остатках, что может привести к ошибкам округления коэффициентов и большое количество проекций при обнаружении ошибок.
p
p
p
n
n
n-1
B
p
n
1
2
n
i
1
Известно устройство для перевода чисел из системы остаточных классов и расширения оснований (патент RU2744815, опубл. 16.03.2021), которое относится к вычислительной технике и может быть использовано в системах связи и обработки информации, функционирующих в системе остаточных классов. Техническим результатом данного изобретения является расширение функциональных возможностей, а именно возможность получить остаток от деления по произвольному дополнительному модулю, а также восстановленное число в позиционной системе счисления. Данный технический результат достигается тем, что в устройство для перевода чисел из системы остаточных классов и расширения оснований с модулями , , …, , содержащее  входов остатков, выход остатка по расширенному основанию,  регистров хранения остатков,  модулярный сумматор по модулю, треугольную матрицу из  умножителей, где умножители производят умножение на коэффициенты  ортогональных базисов  системы остаточных классов (СОК), где  – мультипликативная инверсия,  - рабочий диапазон СОК, представленных в обобщенной позиционной системе счисления (ОПСС) с основаниями  дополнительно ввели модулярный сумматор по модулю ,  умножителей на основания ОПСС  сумматор с выходом восстановленного числа и модулярный сумматор с входом расширенного основания.
Недостатком данного изобретения является использование обобщенной позиционной системы счисления, что в большинстве случаев исключает параллельную реализацию алгоритмов.
Известна нейронная сеть для обнаружения, локализации и исправления ошибок в системе остаточных классов (патент RU2301442, опубл. 20.06.2007), которая относится к вычислительной технике и может быть использована в модулярных нейрокомпьютерных системах. Техническим результатом является повышение скорости коррекции ошибок, сокращение оборудования, а также расширение функциональных возможностей. Для этого нейронная сеть содержит входной слой, нейронные сети конечного кольца для определения синдрома ошибок, блок памяти для хранения констант, нейронные сети для вычисления правильного результата и элемент ИЛИ для определения наличия ошибки.
Недостатком данного изобретения является сложность определения оснований СОК, по которым возникли ошибки.
Известна нейронная сеть конечного кольца (патент RU2759964, опубл. 19.11.2021), которая относится к нейрокомпьютерной технике и предназначено для классификации классов чисел по заданному модулю р. Техническим результатом является повышение быстродействия нейронной сети при классификации вычетов. Устройство содержит входной, скрытый и выходной слои нейронов, два регистра, группу блоков элементов И и группы элементов И.
Недостатком данного изобретения является алгоритмическая сложность, связанная с вычислением индексов чисел.
Известен многоканальный систолический процессор для вычисления полиномиальных функций (патент RU2737236, опубл. 26.11.2020), который относится к вычислительной технике и может быть использован в специализированных системах многоканальной цифровой обработки сигналов и в измерительно-вычислительных системах. В данном изобретении реализуются вычисления с использованием параллельного непозиционного кода СОК. В данной системе вычисления осуществляются параллельно над малоразрядными остатками, определяемыми основаниями системы остаточных классов, что позволяет использовать ПЗУ для выполнения операций сложения и умножения, при этом время выполнения этих операций будет определяться временем выборки из ПЗУ. Таким образом, распараллеливание на уровне арифметических операций и независимая обработка данных по основаниям СОК, реализуемая выборками из ПЗУ, повышает скорость цифровой обработки сигналов с использованием полиномиальных функций без аддитивных и мультипликативных ошибок. Изобретение направлено на повышение скорости и точности многоканальной цифровой обработки сигналов за счет применения системы остаточных классов.
Недостатком данного изобретения являются ограниченные корректирующие возможности используемой СОК.
v
Известно устройство для коррекции ошибок в полиномиальной системе классов вычетов с использованием псевдоортогональных полиномов (патент RU2393529, опубл. 27.06.2010), которое относится к вычислительной технике для контроля и исправления ошибки при передаче информации и для проведения арифметических операций в расширенных полях Галуа GF(2). Техническим результатом является снижение схемных затрат. Устройство содержит регистр, сумматор и блок вычисления синдрома ошибки, который является трехслойной нейронной сетью, содержащей нейроны, образующие первый, второй и третий слой нейронов.
Недостатком данного изобретения является сложность алгоритмов, связанная с использование псевдоортогональных полиномов.
Наиболее близким по технической сути является устройство для вычисления сумм парных произведений в полиномиальной системе классов вычетов (патент RU2622881, опубл. 20.06.2017), выбранное в качестве прототипа. Изобретение относится к вычислительной технике и может быть использовано в процессорах обработки сигналов, в цифровых фильтрах для обнаружения и коррекции ошибки. Техническим результатом, достигнутым при осуществлении данного изобретения, является сокращение аппаратных затрат. Указанный технический результат достигается за счет того, что число переходов за пределы рабочего диапазона определяется только значениями остатков по рабочим основаниям ПСКВ, которые можно заранее просчитать и учесть в структуре нейронной сети блока коррекции. Это позволяет отказаться от счетчика числа переходов и дополнительного слоя нейронной сети, находящихся в блоке коррекции ошибки.
Недостатком данного изобретения является сложность коррекции ошибки, связанная с большим объемом хранимых данных и сложность определения ошибочного разряда.
Техническим результатом данного изобретения является улучшение коррекционных свойств кода полиномиальной системы классов вычетов (полиномиальной СОК) и возможность регулирования избыточности.
i
i
i
i
2
i
i
i
i
i
i
i
15
a
P(x)
p
(x)
Технический результат достигается тем, что система надежного облачного хранения с регулируемой избыточностью данных, состоящая из блоков нахождения остатков по модулю p(x), блока коррекции ошибок и блока перевода в позиционную систему счисления, содержит k+r блоков нахождения остатков по модулю p(x),  где p(x) – взаимно простые трехчлены вида p(x)=x+x+1 над полем F, где a=[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 14] и 2≤k≤11, (k+r)<12, входы которых связаны с входом исходного числа, а выходы соединены с входом соответствующего блока XOR передающей половины и старшими битами регистрахранения передаваемых частей по модулю p(x), младший бит которого соединен с выходом соответствующего блока XOR передающей половины, выходы регистровхранения передаваемых частей по модулю p(x) передаются в облачную инфраструктуру для хранения и/или обработки, данных из облачной инфраструктуру поступают на регистры хранения получаемых частей по модулю p(x), все биты выходов которых соединены с входами блоков XOR принимающей половины, а старшие биты выходов соединены с четными входами блока коррекции ошибок, нечетные входы которого соединены с выходами блоков XOR принимающей половины, блока коррекции ошибок анализирует количество принятых без ошибок значений и подает на выходы значения принятого остатка  по модулю p(x),   где  – произведение модулей  по которым не возникло ошибок, а принятых с ошибкой данные , ,  обнуляются, значения , ,  с выходов блока коррекции ошибок поступают на входы блока перевода в позиционную систему счисления, выход которого является информационным выходом устройства, при этом блок перевода в позиционную систему счисления содержит k+r умножителей многочленов по модулю p(x), k+r умножителей многочленов и сумматор многочленов, при этом на входы умножителей многочленов по модулю p(x)поступают соответствующие значения ,  и производятся вычисления  результаты которых перемножаются с  в соответствующих умножителях многочленов, выходы которых соединены с входами сумматора многочленов, выход которого является выходом блока перевода в позиционную систему счисления.
F(x)
Сущность изобретения основана на следующем математическом аппарате. В полиномиальной системе классов вычетов любой полином  представляется как набор остатков
F(x)=(f
(x), f
(x),…, f
(x), f
(x),.., f
(x))
1
2
k
k
+1
k
+r
(1),
f
(x)=rest(F(x)/p
(x)),
p
(x)
p
(x)=x
+x
+1
a=[1,2,3,4,5,6,7,8,9,11,13,14].
k,n
k
r
n=k+r
x
+x+1
F
i
i
i
i
2
2
2
2
15
a
3
где остаток от деления многочленов;  – взаимно простые трехчлены вида  над полем F, где При этом в данной () системе используется  рабочих оснований и  контрольных, . Для перехода от двоичного представления к полиномиальному будем ставить в соответствие числу в двоичной системе счисления 1011 многочлен  над , т.е. 1 соответствует 1 перед соответствующей степенью. Вычисления над полем F соответствуют операции XOR, суммирования по модулю 2.
F(x)
F(x)=x
=
p
(x)=x
+x+1, p
(x)=x
+x
+1, p
(x)=x
+x
+1, p
(x)=x
+x
+1
16
14
13
11
10
8
7
5
4
2
15
15
2
15
3
15
4
2
1
2
3
4
Рассмотрим представления многочлена  заданного в двоичной системе счисления +x+x+x+x+x+x+x+x+x+x+110110110110110111 в избыточной полиномиальной системе остаточных классов (3,4) с модулями, получим:
в двоичной системе счисления  представляется в виде:
в двоичной системе счисления  представляется в виде:
в двоичной системе счисления  представляется в виде:
в двоичной системе счисления  представляется в виде:
Одним их простейших механизмов помехоустойчивого кодирования является коды проверки четности, который равен сумме по модулю 2 всех бит исходного числа. Проверка осуществляется аналогично суммированием по модулю 2. Добавим к полученным значениям бит четности:
где “|” – конкатенация.
f
i
Таким образом, получено закодированное число, которое может быть передано в одно или несколько облаков для хранения или обработки, поскольку коды системы остаточных классов позволяют производить вычисления над разрядами  независимо и результат будет сравним с искомым результатом.
Рассмотрим процесс декодирования. Пусть ошибка в третьей проекции и вместо  мы получили  где  сложение по модулю 2. Следовательно на вход системы мы получаем:
Проверим корректность, каждой коррекций используя код четности, получим:  - не содержат ошибок, а  – содержит ошибку. Следовательно, для восстановления искомого значения мы будем использовать . Отбросив от значений  младший бит проверки на четность, получим значения разрядов  в полиномиальной системе классов вычетов.
Используя Китайскую теорему об остатках, вычислим значение
Вычислим  получим:
Вычислим  получим:
Вычислим веса  получим:
Вычислим
F(x)
Очевидно, что полученное восстановленное значение  совпадает с исходным  несмотря на возникновение ошибки по одному из оснований.
Изобретение поясняется фигурами 1 и 2.
F(x)
p
(x),
p
(x)
p
(x)=x
+x
+1
a=[1,2,3,4,5,6,7,8,9,11,13,14].
p
(x)
i
i
i
2
i
15
a
На фигуре 1 изображена общая схема системы надежного облачного хранения с регулируемой избыточностью данных. Исходное значение  поступает на входы блоков 1.i нахождения остатков по модулю где  – взаимно простые трехчлены вида  над полем F, где  При этом при построении системы может быть использовано 12 многочленов, таким образом 2≤k≤11, (k+r)<12. Блоки 1.i нахождения остатков по модулю  могут быть выполнены как с использованием вычислительных устройств, например, интегральных схем или FPGA, так и в виде памяти, которая в ответ на значение исходного числа F(x) подает на выход блока 1.i нахождения остатков по модулю pi(x) остаток fi(x) от деления на модуль pi(x).
f
(x)
p
(x)
f
(x),
p
(x),
f
(x)
p
(x)
p
(x)
i
i
i
i
i
i
i
Значения остатков с выходов блоков 1.i нахождения остатков по модулю  поступают на блоки XOR 2.i передающей половины, в которых находится сумма по модулю 2 всех бит остатка  результаты с выходов блоков XOR 2.i передающей половиныпоступают на младший битрегистрахранения 3.i передаваемых частей по модулю  на старшие биты которого передаются значения остатков  с выходов блоков 1.i нахождения остатков по модулю , таким образом выполняется конкатенация значений для проверки на четность, т.е. в регистраххранения 3.i передаваемых частей по модулю  всегда хранятся значения  с четным количеством единиц в двоичном представлении.
p
(x)
i
Данные с выходов регистровхранения 3.i передаваемых частей по модулю  передаются в облачную инфраструктуру 4, которая может быть использована как для хранения, так и обработки данных, поскольку особенностью системы остаточных классов является возможность выполнения арифметических операций сложения и умножения независимо по каждому модулю. При этом облачная инфраструктура может быть представлена как одним, так и несколькими облачными провайдерами, что позволит распределить данные при хранении, тем самым повысить надежность восстановления данных в случае выхода из строя одного или нескольких облаков за счет избыточной структуры полиномиальной системы классов вычетов.
p
(x),
p
(x).
i
i
После обработки или хранения данные поступают на регистры 5.i хранения получаемых частей по модулю  откуда полные принятые значения  поступают на входы блоков XOR 6.i принимающей половины, выходы которых поступают на нечетные входы блока коррекции ошибок 7, на четные входы которого поступают значения  старших бит выходов регистров 5.i хранения получаемых частей по модулю
Таким образом, на нечетные входы блока коррекции ошибок 7 поступают значения, указывающие на наличие одиночной ошибки по каждому основанию, а на четные входы как ошибочные, так и истинные значения . Данный блок анализирует количество принятых без ошибок значений, и если их меньше k, то восстановление числа невозможно и на 3(k+r)+4-й выход блока коррекции ошибок 7 поступает значение «коррекция невозможна».
P(x)
p
(x)
i
В остальных случаях на выходы блока коррекции ошибок 7 поступают значения  где – произведение модулей  по которым не возникло ошибок. Для принятых с ошибкой данных значения  обнуляются.
Значения  с выходов блока коррекции ошибок 7 поступают на входы блока 8 перевода в позиционную систему счисления, выход которого является информационным выходом устройства.
p
(x)
i
На фигуре 2 раскрыта схема блока 8 перевода в позиционную систему счисления. На входы умножителей 9.i многочленов по модулю  поступают значения  умножители 9.i производят вычисления  Результаты поступают на умножители 10.i многочленов, в которых происходит умножение результата на  Затем результаты поступают на сумматор многочленов 11, выход которого является выходом блока 8 перевода в позиционную систему счисления.
Преимуществом данного устройства является улучшение коррекционных свойств кода полиномиальной системы классов вычетов и возможность регулирования избыточности. Поскольку коды проверки на четность легко определяют ошибочные принятые значения, то в используемом блоке коррекции ошибок отпадает необходимость строить n-1 проекцию числа и проводить сложные вычисления по восстановлению числа. Варьирование же значений k и r позволит обеспечить достаточных уровень избыточности и надежности хранения и обработки данных облачной инфраструктурой.
Реализация всего устройства возможна с использованием программируемых логических интегральных схем (ПЛИС), специализированных интегральных схем, а также в виде алгоритма работы ЭВМ и может использоваться как отдельное устройство, так и как сопроцессор для выполнения надежного облачного хранения с регулируемой избыточностью данных.