Динамически размещаемая база данных с топологической привязкой информации Российский патент 2022 года по МПК G06F13/14 G06F16/182 G06F16/27 

ОБЛАСТЬ ЗНАНИЙ

Изобретение относится к упорядоченным массивам информации, логически организованным в базы данных, хранимые на физических носителях, например, магнитных дисках, и к способам управления базами данных, реализуемым на основе программных средств, обрабатывающих информацию с помощью компьютеров.

База данных (далее - БД) характеризуется своей логической моделью и состоит из отдельных записей - данных, содержащих отличительные характеристики. Группы данных объединены в подмножества.

В состав информации входят собственно данные, описывающие объекты предметной области, и метаданные, систематизирующие объекты предметной области. Физическая структура данных обеспечивает хранение и обработку информации программными средствами.

Способ управления БД основан на выполнении операций записи, чтения, удаления, изменения, многопользовательского доступа к информации и восстановления внутренней непротиворечивости информации после нештатного завершения работы одного или нескольких пользователей БД. Операции с информацией выполняются в форме транзакций - групп последовательных действий, представляющих собой логические единицы работы с данными, и фиксируются в виде лога (transaction log, https://en.wikipedia.org/wiki/Transaction log), фиксирующего последовательность выполнения транзакций и их конкретное наполнение.

Заявляется архитектура распределенной базы данных, функционирующей как "рой" - совокупность из самостоятельных устройств. Каждое устройство работает с ограниченным фрагментом данных и периодически (по возможности чаще) синхронизирует состояние видимого ему фрагмента БД с другими (преимущественно "соседними") устройствами. Благодаря топологической (например, геометрической или топографической) N-мерной сегментации базы, логу транзакций, а также эффективной процедуре синхронизации между агентами, предлагаемая БД, реализованная на базе "роя" самостоятельных устройств, может эффективно работать с практически неограниченным объемом данных и операций по их изменению. Возможно, например, применять, в компьютерных играх, транспортных системах и т.д. Устройства обмениваются обновлениями БД между собой напрямую через Р2Р соединения, при посредничестве друг друга или сервера.

УРОВЕНЬ ТЕХНИКИ И ПРОТОТИП

Известен (патент США №8276084) способ доставки контента в область виртуального пространства (ВП), включающий: обнаружение (выявление) множества взаимодействий между участниками (устройствами); отслеживание множества выявленных взаимодействий; оценку степени загруженности сервера, поддерживающего область ВП для определения, превысила ли загрузка предварительно назначенный порог; формирование набора подгрупп устройств в области, если предварительно назначенный порог загрузки превышен, каждая из набора подгрупп содержащих одно или более устройств для которых выполняется выявление и отслеживание; и ответственный за превышение пред. назначенного порога нагрузки, если объем данных переданных на или от сервера превысит предварительно назначенный порог объема (широковещательного) трафика, передавая по крайней мере часть из объема данных ВП между устройствами одной конкретной подгруппе из списка подгрупп с использованием Р2Р обмена данными (широковещания), где все устройства в одной конкретной подгруппе из набора подгрупп передают по крайней мере часть данных ВП на или от сервера, где, если объем данных ВП ниже предварительно назначенного уровня (т.е. понижается) объема трафика, перестает передавать часть объема данных ВП между устройствами конкретной подгруппы из набора подгрупп.

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

Известен (патент США №10825024) способ, устройства и системы для платформ управления данными на базе DLT. Описаны несколько воплощений посвященных распределенным учетным (бухг.) системам (т.е. распределенные системы с применением фин. учетных технологий в децентрализованной компьютерной сети) которые могут использоваться для работы и управления распределением и доступом к данным так, чтобы сохранить преимущества распределенной учетной (финансовой) технологии позволяя также частный обмен данными. В особенности описанные распределенные учетные системы включают на платформу управления данными на основе технологии распределенного учета (DLT), которая может быть применена на узлах сети управления данными.

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

Известен (патент США №9571571 от 04.09.2012). В документе раскрывается способ создания сообществ в Р2Р сети.

В соответствии с Р2Р протоколом, Р2Р сеть включает множество клубов (сообществ) и множество устройств (рядовых участников), которые получают контент, рассылаемый средствами сети. Каждый из множества рядовых участников является частью по крайней мере 2-х сообществ. Объединяющий участник идентифицирует сообщество (клуб) Р2Р сети для присоединения (к какому хочет присоединиться) и получает идентификационную информацию для участника указанного сообщества (клуба). Присоединяющийся участник случайным образом выбирает среди участников выбранного сообщества (клуба) по крайней мере первого участника и второго участника, с кем осуществить соединения. Соединение является пропорционально взвешенным (средневзвешенным) от числа соединений первого участника с остальными участниками и числа соединений второго участника с остальными участниками. Присоединяющийся участник устанавливает первое соединение с первым участником, и второе соединение со вторым участником.

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

Известен (патент США №9210085 от 05.10. 2007). Раскрывается процедура Р2Р протокол, такой как BitTorrent, использован для помощи в потоковой передаче данных. Участники загружают потоковый контент из Р2Р сети, одновременно воспроизводя загружаемый контент. В то время, как поток проигрывается, конечная система загружает пропущенные части напрямую с сервера или другого инфраструктурного узла. Этот способ эквивалентен значительному увеличению (в квадрате) емкости сервера и может быть более точно настроен для достижения на в среднем 0 (1)-м сервере вне зависимости от числа конкурирующих пользователей. Таким образом BitTorrent помогает потоковому процессу лучше, чем традиционные сервер-клиентские и только-инфраструктурные решения, каждое из которых требует множество инфраструктурных узлов, которые увеличивают линейно к числу пользователей.

Недостатком данного способа является то, что он посвящен частной задаче односторонней передачи потокового контента, и решает задачу оптимизации и/или снижения потребности в вычислительных ресурсах и пропускной полосе сети при увеличении числа клиентов-получателей потока данных, но не обеспечивает клиентам возможность интерактивного чтения данных из БД и записи в БД.

Известен (патент США №9177328 от 21.06.2012 Раскрывается способ добавления участника в сообщество сети. Ближайший участник передает присоединяющемуся участнику информацию для присоединения (контактную информацию) о тех участниках, и присоединяющийся участник устанавливает с ними связь. Участники сообщества размещают объявления для чат-комнат, чтобы присоединиться к чат-комнате, участник выясняет, кто из участников ближе всего находится к чат-комнате по идентификатору чат-комнаты, и извещает его о том, что он участник чат-комнаты.

Основным сходством является способ организации сообщества и взаимодействия между узлами, в т.ч. напрямую, поддержка связного графа всех участников сети, создание и разрыв Р2Р подключений по инициативе участников для формирования ими прямых соединений нужной конфигурации. Недостатком данного способа является то, что он посвящен частной задаче способа присоединения к сообществу и перестройки сетевых соединений для формирования сообществ, но не решает задачу предоставления доступа всех подключенных устройств к единой для всех участников консистентной БД.

В качестве прототипа выбран патент США №8276084.

Техническим результатом, достигаемым настоящим изобретением является предоставление устройствам доступа к логически консистентной БД, а также сокращение потребности в вычислительных ресурсах и пропускной способности сетевого канала клиентов (и сервера, если он есть) при увеличении объема БД, числа пользователей и интенсивности записи.

Известные способы и устройства не позволяют достичь заявленный технический результат.

КРАТКОЕ ОПИСАНИЕ

Заявленный технический результат достигнут предлагаемым способом сбора, хранения, обновления и обработки динамически размещаемой информации с топологической привязкой мест хранения данных.

Заявляемый способ сбора, хранения, обновления и обработки информации об n-мерном пространстве, заранее разбитом на топологические (например, геометрические) области, включает сбор информации средствами сбора, находящимися на устройствах, имеющих координаты в описываемом пространстве и способных обмениваться информацией между собой, всех вместе образующих сообщество, где каждое устройство может обмениваться информацией с каждым напрямую или при посредничестве других устройств (связный граф), размещение информации, относящейся к топологической области, на средствах хранения информации, расположенных на указанных (подключенных к сообществу) устройствах, имеющих в этот момент координаты в пределах этой области и соседних (смежных) областей, обмен информацией с устройствами, имеющими координаты в этой или других, преимущественно смежных, областях, удаление информации касающейся топологической области, при изменении координат устройства на другие, удаленные от данной области.

Заявляется динамическая система сбора, обработки и размещения информации об n-мерном пространстве, включающая

- n-мерное пространство, предварительно разбитое на сегменты, формирующие замощение (паркет) с полным покрытием пространства.

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

Средство хранения информации может дополнительно включать средство хранения статуса информации, фрагмент общего распределенного лога транзакций (DLT).

В логе операций (DLT) могут храниться отдельные операции. При этом каждая операция изменяет данные только о заранее фиксированном наборе указанных выделенных областей n-мерного пространства.

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

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

Информация о каждой области пространства может включать перечень всех подключенных к сообществу (графу) устройств, имеющих координаты в данной области.

Информация (транзакция), в том числе о текущей области (затрагивающая текущую область), может быть записана в локальную память (средство хранения) устройством-инициатором (устройством-источником) первоначально в статусе "не согласована", затем после подтверждения - в статусе "согласована".

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

Новая информация (транзакция) о текущей области может быть записана в локальную память (средство хранения) устройство-инициатор (устройство-источник) первоначально в статусе "принята".

Возможно дополнительно наличие одного и более устройства с функциями сервера для первичной авторизации устройств, проксирования информации и организации Р2Р взаимодействия между агентами (например, для организации UDP/IP punch hole), не принадлежащего сообществу и не имеющему координат в указанном n-мерном пространстве.

Заявляется программный продукт размещенный на компьютерном читаемом устройстве хранения для сбора, хранения, обмена, перемещения контента в геометрической области n-мерного пространства, компьютерно читаемое устройство хранения, содержащее программный код, позволяющий компьютеру выполнять следующие действия: собирать информацию информации средствами сбора, находящимися на устройствах, имеющих координаты в описываемом пространстве, размещение информации, относящейся к геометрической области, на средствах хранения информации, расположенных на указанных устройствах, имеющих в этот момент координаты в пределах этой области, обмен информацией с устройствами имеющими координаты в этой или других, преимущественно смежных, областях.

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

Заявляемый программный продукт может дополнительно позволять компьютеру устройства выполнять процедуры записи данных внутри области в следующем порядке:

• каждому устройству хранить у себя информацию о последней операции, затрагивающей свою и любую из смежных областей, ранее которой устройству известны все операции, совершенные всеми устройствами в сообществе для своей и смежных областей;

• каждому устройству записывать в локальную память (средство хранения) устройства в статусе "принята" новую информацию (транзакцию) о своей области;

• каждому устройству отслеживать все изменения (транзакции), вносимые другими устройствами, имеющими координаты в той же области, где находится устройство, и в смежных областях, а также периодически рассылать всем соседним устройствам информацию о том, какая транзакция была записана этим устройством последней или информацию о том, что запись не осуществлялась;

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

Заявляемый программный продукт может дополнительно позволять компьютеру устройства выполнять процедуры записи данных внутри области в следующем порядке

- первичной записи в локальную память (средство хранения) одного устройства,

- назначение первичной записи статуса "не согласована",

- рассылки (прямой или посредством пересылки) данных другим устройствам в этой же области (соседям) по области в смежных областях,

- получение ответа от всех соседних устройств в пределах области и смежных областей, что данные приняты,

- назначение первичной записи статуса "согласована".

Заявляется размещенная на компьютере система для обмена, хранения, доставки информации в области n-мерного пространства включающая информационную шину, присоединенный к инф. шине процессор, устройство сбора информации, устройство памяти (хранения информации), содержащая инструкции: для сбора информации, обмена данными с другими устройствами, находящимися в n-мерном пространстве.

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

Заявляемая размещенная на компьютере система может дополнительно содержать инструкции, что каждая процедура записи данных в область состоит из

- первичной записи в локальную память (средство хранения) одного устройства,

- назначения первичной записи статуса "не согласована",

- рассылки (прямой или посредством пересылки) данных другим устройствам в этой же области (соседям) по области в смежных областях,

- получения ответа от всех соседних устройств в пределах области и смежных областей, что данные приняты,

- назначения первичной записи статуса "согласована".

Заявляемая размещенная на компьютере система может дополнительно содержать инструкции: назначить одному из устройств функции сервера по учету взаимодействия устройств или обмена информацией в указанном n-мерном пространстве.

ОПИСАНИЕ ГРАФИЧЕСКОГО МАТЕРИАЛА

На Фиг. 1 показана схема размещения объектов на карте и их адресации в БД (пример).

ПОДРОБНОЕ ОПИСАНИЕ

Заявленный технический результат достигнут предлагаемым способом сбора, хранения, обновления и обработки динамически размещаемой информации с топологической привязкой мест хранения данных.

Заявляемый способ сбора, хранения, обновления и обработки информации об n-мерном пространстве, заранее разбитом на геометрические области, включает следующие шаги.

Сбор информации средствами сбора, находящимися на устройствах, имеющих координаты в описываемом пространстве и способных обмениваться информацией между собой.

Средствами сбора информации могут быть, например, средства фото- и видеофиксации, аудио приборы чтения и записи, датчики контроля излучений, температурные датчики, датчики силы и направления ветра, устройства ручного ввода данных (например, клавиатура) и др.

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

Размещение информации, относящейся к геометрической области, происходит на средствах хранения информации (устройствах памяти), расположенных на указанных (подключенных к сообществу) устройствах, имеющих в этот момент координаты в пределах этой и соседних (смежных) областей.

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

Удаление информации касающейся геометрической области, происходит при изменении координат устройства на другие, удаленные от данной области.

Запись и изменение информации может осуществляться через распределенный лог операций (Distributed ledger, DLT) https://en.wikipedia.org/wiki/Distributed ledger, где каждая операция изменяет данные только о заранее фиксированном наборе указанных выделенных областей n-мерного пространства.

Полный лог всех операций возможно хранить в виде набора выборок из этого полного лога, где каждая выборка состоит из полного перечня операций, относящихся к конкретной геометрической области.

Каждое устройство может хранить у себя информацию о каждой области пространства и может включать перечень всех подключенных к сообществу (графу) устройств, имеющих координаты в этой же (своей) данной области пространства.

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

Информацию (транзакцию) затрагивающую текущую область устройство-инициатор (устройство-источник) может записывать в локальную память (средство хранения) первоначально в статусе "не согласована", затем устройство-инициатор (устройство-источник) рассылать информацию прямо или посредством пересылки всем "соседям" - остальным устройствам, имеющим координаты в той же области, что и устройство-инициатор (устройство-источник) и в смежных областях, и указанной информации устройство-инициатор (устройство-источник) может назначать статус "согласована" после того, как все остальные устройства из той же и смежных областей пришли к "консенсусу" (см. https://en.wikipedia.org/wiki/Consensus (computer science)) о том, что запись (транзакция) успешно зарегистрирована, т.е. получена всеми устройствами-адресатами.

При обмене сообщениями между устройствами ими может осуществляться ассиметричное шифрование сообщений (см. например, https://docs.cntd.ru/document/1200004855).

При обмене сообщениями между устройствами сообщения могут снабжать подписью, позволяющей гарантировать подлинность сообщений.

Каждое устройство может хранить у себя информацию о последней операции, затрагивающей свою и любую из смежных областей, ранее которой устройству известны все операции, совершенные всеми устройствами касательно своей и смежных областей.

Новую информацию (транзакцию) о своей области возможно записывать в локальную память (средство хранения) устройства сразу в статусе "принята".

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

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

Каждая процедура записи данных в область может включать следующие шаги. Запись в локальную память (средство хранения) одного устройства. Назначение этим устройством записи статуса "не согласована". Рассылку записывающим данные устройством (прямую или посредством пересылки) данных другим устройствам в этой же области и в смежных областях. Получение ответа от всех устройств в пределах измененной области и смежных областей, что данные приняты (согласованы). Назначение записи статуса "согласована".

Информацию (транзакцию) о текущей области возможно записывать в локальную память (средство хранения) устройства сразу в статусе "принята". А затем уже оповещать о ней другие устройствам в этой же области и в смежных областях

Может существовать одно и более устройство с функциями сервера для первичной авторизации устройств, проксирования информации и организации Р2Р взаимодействия между агентами (например, для организации UDP/IP punch hole), не принадлежащее сообществу и не имеющему координат в указанном n-мерном пространстве.

Любое из устройств при подключении к сообществу (рою) может проходить процедуру авторизации.

Любому из устройств могут быть назначены дополнительно более широкие или урезанные права доступа к данным, расширенные или сокращенные обязанности, другие доп. обязанности или ограничения по равнению с другими устройствами-участниками сообщества.

Заявлена динамическая система сбора, обработки и размещения информации об n-мерном пространстве.

Система включает:

- n-мерное пространство, предварительно разделенное на геометрические области,

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

Средство хранения информации может дополнительно включать средство хранения статуса информации, частичный лог общего распределенного лога транзакций.

В частичном логе операций (DLT https://en.wikipedia.org/wiki/Distributed ledger) каждой операцией могут изменяться данные только о заранее фиксированном наборе указанных выделенных областей n-мерного пространства.

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

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

Информация о каждой области пространства может включать перечень всех подключенных к сообществу (графу) устройств, имеющих координаты в данной области.

Новая информация (транзакция) о текущей области может быть записана в локальную память (средство хранения) устройством - инициатором (устройством - источником) первоначально в статусе "не согласована", затем после подтверждения - в статусе "согласована".

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

Информация (транзакция) о текущей области может быть записана в локальную память (средство хранения) устройство-инициатор (устройство-источник) первоначально в статусе "принята".

Возможно дополнительно наличие одного и более устройства с функциями сервера для первичной авторизации устройств, проксирования информации и организации Р2Р взаимодействия между агентами (например, для организации UDP/IP punch hole), не принадлежащее сообществу и не имеющему координат в указанном n-мерном пространстве.

Заявлен программный продукт, размещенный на компьютерном читаемом устройстве хранения, для сбора, хранения, обмена, перемещения контента в топологической области n-мерного пространства, компьютерно читаемое устройство хранения, содержащее программный код, позволяющий (заставляющий) компьютер выполнять следующие действия: собирать информацию информации средствами сбора, находящимися на устройствах, имеющих координаты в описываемом пространстве, размещение информации, относящейся к топологической области, на средствах хранения информации, расположенных на указанных устройствах, имеющих в этот момент координаты в пределах этой области, обмен информацией с устройствами имеющими координаты в этой или других, преимущественно смежных, областях.

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

Дополнительно указанный программный продукт может позволять компьютерному устройству выполнять процедуры записи данных внутри области в следующем порядке:

- первичную запись в локальную память (средство хранения) одного устройства,

- назначение первичной записи статуса "не согласована",

- рассылку (прямую или посредством пересылки) данных другим устройствам в этой же области (соседям) по области и в смежных областях,

- получение ответа от всех соседних (в пределах области и смежных областей) устройств в пределах области и смежных областей, что данные приняты,

- назначение первичной записи статуса "согласована".

Дополнительно указанный программный продукт может позволять компьютерному устройству выполнять процедуры записи данных внутри области в следующем порядке:

• каждому устройству хранить у себя информацию о последней операции, затрагивающей свою и любую из смежных областей, ранее которой устройству известны все операции, совершенные всеми устройствами в сообществе для своей и смежных областей;

• каждому устройству записывать в локальную память (средство хранения) устройства в статусе "принята" новую информацию о своей области;

• каждому устройству отслеживать все изменения, вносимые другими устройствами, имеющими координаты в той же области, где находится устройство, и в смежных областях? а также периодически рассылать всем соседним устройствам информацию о том, какая транзакция была записана этим устройством последней или информацию о том, что запись не осуществлялась;

• каждому устройству отслеживать полноту своего лога операций и запрашивать пропущенные транзакции, если о них узнает, либо обновлять для себя информацию об операции, перед которой этому устройству все операции известны;

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

Заявлена также размещенная на компьютере система для обмена, хранения, доставки информации в области n-мерного пространства включающая информационную шину, присоединенный к инф. шине процессор, устройство сбора информации, устройство памяти (хранения информации), содержащее инструкции для сбора информации, обмена данными с другими устройствами, находящимися в n-мерном пространстве.

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

Также размещенная на компьютере система для обмена, хранения, доставки информации в области n-мерного пространства включающая информационную шину, присоединенный к инф. шине процессор, устройство сбора информации, устройство памяти (хранения информации) может дополнительно содержать инструкции назначить первоначально статус "не согласована" ("на согласовании"), информации (транзакции), которую агент записал в свою локальную память (средство хранения) области, указанной информации впоследствии назначить статус "согласована" (в том числе агенту-автору) только после того, как все обитатели области и смежных областей приняли и подтвердили агенту-инициатору ее получение.

Также размещенная на компьютере система для обмена, хранения, доставки информации в области n-мерного пространства включающая информационную шину, присоединенный к инф. шине процессор, устройство сбора информации, устройство памяти (хранения информации) может дополнительно содержать инструкции, что каждая процедура записи данных в область состоит из:

- первичной записи в локальную память (средство хранения) одного устройства,

- назначения первичной записи статуса "не согласована",

- рассылки (прямой или посредством пересылки) данных другим устройствам в этой же области (соседям) по области в смежных областях,

- получения ответа от всех соседних (в пределах области и смежных областей) устройств в пределах области и смежных областей, что данные приняты,

- назначения первичной записи статуса "согласована".

Также размещенная на компьютере система для обмена, хранения, доставки информации в области n-мерного пространства включающая информационную шину, присоединенный к инф. шине процессор, устройство сбора информации, устройство памяти (хранения • каждому устройству хранить у себя информацию о последней операции, затрагивающей свою и любую из смежных областей, ранее которой устройству известны все операции, совершенные всеми устройствами в сообществе для своей и смежных областей;

• каждому устройству хранить у себя информацию о последней операции, затрагивающей свою и любую из смежных областей, ранее которой устройству известны все операции, совершенные всеми устройствами в сообществе для своей и смежных областей;

• каждому устройству записывать в локальную память (средство хранения) устройства в статусе "принята" новую информацию о своей области;

• каждому устройству отслеживать все изменения, вносимые другими устройствами, имеющими координаты в той же области, где находится устройство, и в смежных областях? а также периодически рассылать всем соседним устройствам информацию о том, какая транзакция была записана этим устройством последней или информацию о том, что запись не осуществлялась;

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

ДОПОЛНИТЕЛЬНЫЕ РАЗЪЯСНЕНИЯ ПО ТЕМЕ.

Тип используемой в заявляемом способе базы данных - может быть разным, но лучший результат получается с БД типа "Ключ-Значение" (https://en.wikipedia.org/wiki/Key%E2%80%93value database) с поддержкой иерархической адресации или без. В базах такого типа "Ключ" - это последовательность байт произвольной длины, "адрес", "Значение" - сохраняемые данные произвольного типа, последовательность байт произвольной длины.

Каждый "Ключ" БД содержит (однозначно вычисляемый или явно хранимый в виде последовательности из N целых чисел) адрес области в N-мерном пространстве. При этом к одной области могут относиться множество различных ключей.

Любая БД/язык программирования предлагает множество операций над данными. Из этого множества операций для заявляемой БД применимы только те, что соответствуют приведенным ниже критериям, что несколько сужает стандартное значение выражения "операция над данными".

Так же у предлагаемой БД есть ограничения по характеристикам выполняемых задач. Это означает, что предлагаемая БД не дает преимущества при решении задач, где отсутствует зона обзора, привязка к области (в n-мерном пространстве) и клиент может равновероятно читать/писать вообще любые данные. Неограниченное масштабирование БД без линейного роста нагрузки на сеть и вычислительные ресурсы проявит себя только на задачах, бизнес-логика которых соответствует приведенным критериям.

Описывают N-мерное пространство, всем данным присваивают координаты в этом пространстве, потом пространство разбивают на сегменты (топологическое замощение N-мерной поверхности). Далее обрабатывают данные каждого сегмента (каждой плитки) отдельно. Топологические термины "замощения", "мозаики", "паркеты" описывают процедуру применяемой сегментации пространства.

Области (сегменты) БД образуют дискретное N-мерное пространство, и обладают стандартными топологическими свойствами "соседства", т.е. каждая одна область соседствует с одной или несколькими другими, и "удаленности", т.е. может быть вычислена сравнительная дистанция между любыми областями в N-мерном пространстве.

Информацию о каждой области хранят в памяти ЭВМ и обновляют независимо от других областей.

Для изменения записи в БД используют специальные последовательности байт - "операции". Операция - это набор данных, описывающих вносимые в БД изменения (тип операции, адрес данных, новое значение и т.д.). Ближайший аналог - SQL запрос, но не все операции, доступные в SQL, годятся для заявляемой БД.

Подходят только операции, соответствующие следующим критериям:

• операция описывает изменения в фиксированном наборе областей,

• перечень затронутых операцией областей не зависит от состояния БД,

• операция должна описывать детерминистические изменения и при исполнении на идентичной БД всегда давать идентичный результат,

• операция должна быть "обратима", то есть для каждой операции должна существовать "обратная" операция (операция "отмены", обратная функция), применение которой после операции вернет БД к состоянию "до начала выполнения операции",

• операция атомарна, т.е. может либо быть целиком успешно применена к БД, либо полностью "провалиться", частичный вариант недопустим. Успешная операция может осуществить запись в БД, провалившаяся операция оставляет БД неизменной.

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

Транзакции, применяемые к БД, помещаются в "лог транзакций": однозначно упорядоченный по фиксированным правилам список транзакций. Удобно упорядочивать транзакции в логе сортировкой по убыванию по уникальному сочетанию времени создания транзакции и ID создателя.

Опираясь на однозначную сортировку транзакций, пользователи БД помещают в лог новые транзакции в произвольной очередности. Благодаря тому, что порядок транзакций в логе зависит только от описания транзакций, а не от очередности их добавления, из идентичного перечня транзакций на выходе всегда будет получаться идентичный лог.

ЗАДАЧИ, КОТОРЫЕ РЕШАЕТ БАЗА ДАННЫХ

Решается задача, когда в некотором пространстве, предварительно разделенном на области, множество независимых агентов - устройств, одновременно и несогласованно читают и записывают информацию в единую базу данных (далее "БД"). Агенты могут выполнять, например, такие задачи:

• Автомобили (агенты) при движении по дороге с помощью датчиков анализируют дорожную обстановку и помещают в БД информацию о встреченных помехах, качестве дорожного полотна, припаркованных автомобилях, собственном местоположении и другие сведения, полезные для других автомобилей и/или для систем управления движением. Также каждый автомобиль считывает из БД информацию, записанную другими автомобилями, для поиска свободных парковок, выбора режима движения и т.п.

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

• Участники компьютерной игры, подключившись к общей игровой базе, совершают конкурентные действия в игровой вселенной - перемещаются в пространстве (обновляют запись "позиция в пространстве космического корабля №1"), наносят урон другим игрокам (обновляют запись "очки прочности корабля №2" других игроков) и игровым объектам, создают и/или уничтожают постройки, обмениваются предметами с другими игроками и прочее.

Вышеописанные ситуации характеризуются следующими ключевыми особенностями:

1. БД описывает размещенные в n-мерном пространстве объекты, т.е. база хранит описания объектов. Размерность такого пространства может быть любой, главное, чтобы пространство однозначно разбивалось на, желательно, непересекающиеся топологические (геометрические, топографические) области (или просто "области") и для каждой такой области пространства можно было бы найти конечное число соседних областей. В простейшем случае это фрагмент плоскости (область на местности), разбитый на квадраты (например, 1 км × 1 км). В качестве примеров собираемой в области информации:

• Размещение и свойства построек, растительности и дорог на местности (карту местности можно рассматривать, как двухмерное пространство)

• В компьютерной игре размещение игроков и внутриигровых объектов на игровом поле (двумерном или трехмерном)

• Положение звезд и звездных систем во вселенной (трехмерное пространство).

2. Агент, осуществляющий доступ к базе данных (будь то запись или чтение), имеет относительно устойчивую и явно очерченную зону интереса - перечень топологических областей (часто соприкасающихся друг с другом, но не обязательно). Зона интереса может быть произвольной формы и размера (наиболее часто можно ожидать n-мерную сферу). Относительно устойчивая зона интереса подразумевает, что подавляющее большинство операций чтения/записи ведется без изменения зоны интереса, а операции изменения зоны интереса проводятся редко. Чем меньше операций смены зоны интереса на одну операцию чтения/записи, тем больший выигрыш по производительности и используемым ресурсам ЭВМ дает предлагаемая архитектура. В качестве примеров, иллюстрирующих зону интереса, можно привести следующие:

• Автомобиль, ищущий место для парковки, нуждается в информации о свободных парковках в радиусе ~500 м,

• Наводчику БМП (боевая машина пехоты) полезно знать о позициях ПЗРК (зенитно-ракетный комплекс) в радиусе нескольких (например, 4-х) километров. Что происходит на дистанции далее 4-х км (для примера) уже не так важно, но полезно. За пределами радиуса 10 км информация не нужна.

• Игрок в компьютерной игре может торговать и обмениваться ударами только с игроками и неигровыми персонажами в непосредственной близости от себя, как правило в поле своего зрения. На достаточно обширной игровой карте зона, "видимая" игроку в каждый момент времени, может составлять доли процента от общей игровой территории

• Зону интереса определяют в каждом случае индивидуально, например игрок, подключившийся в сетевую игру с полноценного компьютера, может иметь большую зону видимости, чем игроки, подключившиеся с мобильных телефонов, а машина, не нашедшая парковку в радиусе 200 метров, может расширить область обзора парковок до 4 00 или 600 метров.

• С базой может работать и агент, чья зона интереса покрывает всю БД. Например, штаб дивизии, имея мощный компьютер и сети связи, может собирать информацию с обширной территории, в то время, как бойцу может быть остаточно доступа к небольшому фрагменту радиусом в полтора километра.

3. Каждая операция чтения или записи гарантированно и однозначно может быть соотнесена с определенной областью пространства, описанного в БД. Поэтому каждая серия операций также будет иметь конечный список затронутых областей. Глобальные операции (распространяющиеся на все области одновременно) либо вовсе не используют, либо являются исключением (их выполняют посредством иного инструментария, не описываемого здесь).

• Если машина отчитывается о занятом парковочном месте, это означает, что точно известна локация парковочного места, и какую "область карты" нужно обновить, а какие области (все остальные области) останутся неизменными.

• Если игроку нужен перечень всех аватаров других игроков (участников) в определенном радиусе от его аватара, то возможно точно определить конечный перечень областей "на карте", то есть разделов БД, которые необходимо и достаточно осмотреть, чтобы получить исчерпывающий перечень соседних аватаров.

4. Данные и/или изменение происходящие вне "зоны интереса" данных, агенту (устройству) не нужны. Это так же означает, что изменения, вносимые в БД агентом, не требуются другим агентам, чья зона интереса не покрывает изменяемую область. Фактически, в каждый момент времени каждый агент работает с "выделенным фрагментом" базы, при этом остальная база существует полностью вне зоны его видимости.

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

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

5. Агенты имеют возможность (самостоятельно или по воле других авторизованных агентов) изменять "зону интереса". Крайне важна реализация, при которой зона интереса храниться прямо в БД, обновляется там же агентами (возможно, назначенными авторизованными агентами) и публична, то есть агенты будут информированы о зоне интереса друг друга, что открывает широкие возможности оптимизации.

• По мере того, как машина движется по городу, необходимость в обзоре и сборе/обработке информации одной области пропадает, но возникает необходимость осмотреть (собирать/обрабатывать информацию) другую область.

• Игрок (агент) может перемещаться по игровому миру: в данный момент ему нужно видеть северную сторону континента и противников на ней, через пять минут - восточную, а потом он полетит в космос. Или игрок может, например, сменить оружие "нож" на "снайперская винтовка", что потребует предоставить ему право записи на существенно расширенную область "пространства".

6. Возможно обеспечить, не обязательно прямую, связь между агентами, чьи "зоны интереса" перекрываются и/или соприкасаются

• Игроки при посредничестве сервера и/или напрямую, через Р2Р соединения могут обмениваться информацией с игроками, оказавшимися поблизости от них в игровой вселенной.

• Автомобили могут устанавливать радиосвязь с находящимися поблизости автомобилями напрямую или через, например, сотовые ретрансляторы.

7. База данных должна иметь встроенные средства контроля доступа и верификации изменений: первичная авторизация пользователя (например, по логину/паролю и/или открытому ключу), определение разных прав на доступ к различным слоям/областям БД разным пользователям и другие стандартные функции управления доступом к БД.

• БД городской дорожной сети может предоставлять городской администрации права на позиционирование на карте парковочных мест (запись) и на просмотр позиций запаркованных автомобилей (чтение). Встроенным же компьютерам автомобилей БД позволит перемещать метку своего автомобиля (и только своего) и читать расположение парковочных мест. Устанавливать расположение парковок автомобиль не имеет права.

• Игроку должно быть доступно изменение скорости и направления движения его аватара, но не аватаров других игроков. Администрация игры будет видеть все области БД, в том числе полностью скрытые от игроков (например, содержимое секретных сундуков, которое можно узнать только подойдя к сундуку вплотную).

8. Базе данных необходимо (от базы данных требуется) (должна) полноценно функционировать и сохранять логическую целостность, в том числе и в условиях интенсивных, одновременных и несогласованных обновлений данных в БД множеством участвующих устройств (агентов) (См. также https://en.wikipedia.org/wiki/Database_transation). При этом базе необходимо (от базы данных требуется) оставаться достоверной, защищенной от несанкционированного доступа (безопасной), целостной и доступной всем агентам, то есть предоставлять стандартный для server-based БД (SQL или NoSQL) уровень надежности и отзывчивости.

• Даже на относительно небольшой парковке машины могут прибывать и убывать ежеминутно. Обстановка на нескольких парковках в мегаполисе может меняться ежесекундно, а данные пятиминутной давности ценности уже не представляют. В масштабах города тысячи машин будут ежесекундно обновлять данные о своей позиции, о занятых парковках и т.д.

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

Дополнительные пояснения следующие. Целостность подразумевает, что (условно) если автомобиль может быть либо на дороге, либо на парковке, то никогда не окажется ситуации, когда тот же автомобиль будет и на дороге, и на парковке. То есть в каждый момент времени автомобиль существует (целостность не нарушена - ничего не выпало) и пребывает в консистентном, адекватном состоянии (либо там, либо там). Достигается за счет репликации и применения не отдельных операций (автомобиль убрать, автомобиль добавить), а за счет транзакций (либо убрать + добавить в базу приедет, либо не приедет ничего, никаких обломков и частичных обновлений).

Таким образом информация не теряется, пока это не сделают намеренно.

Если необходимо область БД сделать рабочей и хранящей данные даже тогда, когда в области не осталось агентов - назначают хранителя "области" принудительно, например в область помещается выделенный "агент", контролируемый сервером, и агент остается в области до тех пор, пока требуется сохранять данные из этой области.

9. База данных должна полноценно функционировать и сохранять целостность при нарушениях связности отдельных агентов и групп агентов, при произвольном подключении и отключении агентов, в том числе нештатном и/или принудительном. Например, рой "раздающих контент" в BitTorrent (https://en.wikipedia.org/wiki/Glossary_of_BitTorrent_terms#Peer или https://patents.justia.com/assignee/bittorrent-inc) может расширяться или сжиматься, отдельные узлы могут разрывать связь, но рой как целое по-прежнему предоставляет контент.

• Игрок, подключившийся в игру через мобильную сеть, может иметь неустойчивую связь: спонтанные изменения скорости, потери пакетов, временные обрывы связи, полный обрыв связи. При этом другие игроки не должны получать задержек и/или ошибок.

• На поле боя любое устройство может быть в любой момент выведено из строя, а связь может быть недоступна из-за помех и повреждений проводных линий. Уцелевшие устройства должны при этом продолжать работать, обмениваться (по возможности) данными, адекватно отображать обстановку по тем данным, которыми они располагают и пытаться восстановить синхронизацию.

10. База может состоять из нескольких отдельных "слоев", часть из которых видна одним агентам и невидима для других. Для слоев можно, например, использовать "Тип", как в примере выше.

• Грузовые автомобили могут игнорировать места парковок, предназначенных только для легковых машин.

• БПЛА (беспилотный летающий аппарат) может получать только данные, относящиеся к целеуказанию для него, а целеуказания для минометов будут передаваться в другом "слое".

Древовидная база данных и топологическая (топографическая) адресация

Возможно представить предлагаемую базу объектов в виде древовидной структуры, где адрес каждого узла состоит из последовательности токенов, например из чисел. Первое число может обозначать тип данных, например "1 - постройки, 2 - деревья". Затем в адресе последовательность N чисел (для двумерного пространства - два числа) указывает на принадлежность к определенной области в пространстве. Для двумерного пространства получим [/Тип/КоординатаХ/КоординатаУ]. Например, по адресу [/1/3/2] у нас может храниться перечень построек, размещенных на квадратном километре, удаленном на 3 километра к востоку и на два километра к югу от точки 0:0. По адресу [2/3/2] при этом будут храниться деревья на том же квадратном километре 3:2. А по адресу [/1/2/2] в базе будут доступны постройки на соседнем квадратном километре с координатами 2:2 (2:2 прилегает к квадрату 3:2 слева).

Пример размещения объектов на карте и их адресации в БД (фиг. 1).

Адресация вида

[/Тип/КоординатаХ/КоординатaY/ПорядковыйНомер]

Адресацию таких "областей пространства" возможно делать разными способами: [/Тип/КоординатаХ/КоординатаУ], [/КоординатаУ/КоординатаХ/Тип] или вообще [/КоординатаУ/КоординатаХ] и т.д. Подойдет любой адрес, соответствующий критериям:

1. В адресе любой записи БД должен присутствовать адрес топологической области (например, N-мерный вектор), к которой относится объект

2. Каждому объекту, хранимому в БД, гарантированно можно сопоставить его топологическую область (желательно, однозначно)

3. Для каждой области можно подобрать адреса всех соседних (прилегающих) областей

Внутри каждой области пространства можно адресовать объекты так же, численно (что дает простую сквозную числовую адресацию вида /#/#/#/#/… для всей базы) либо как-то иначе (вплоть до использования SQL), что немного усложняет реализацию, но в отдельных случаях может оказаться полезно. Глубина ветвления полученного "дерева" (и, соответственно, длина адресов) может быть любой.

Примеры возможных адресов для полей из такой БД:

• [/Тип/КилометрХ/КилометрУ/МиллиметрХ/МиллиметрУ/ПорядковыйНомер]

• [/КилометрХ/КилометрТ/Тип/Уникальный1Б]

• [/КилометрХ/КилометрУ/ID Группы/ID Подгруппы/УникальныйID]

Таким образом, возможно разместить в единой древовидной базе описание любой, сколь угодно обширной, "территории", имеющей (желательно однородные) координаты, и адресовать объекты этой базы, зная, к какой области N-мерного пространства они относятся и, зная адрес объекта, устанавливать область, в которой объект хранится.

Запись на примере БД древовидной адресации, лог транзакций

Предположим, что БД целиком доступна некоему агенту для чтения и записи. Агент, имея адрес, может читать хранимые в базе объекты (либо удостоверяться, что в базе объекта по указанному адресу нет). Так же агент может создавать в базе новые объекты, удалять их и изменять, опираясь на адрес.

Операции записи в такую БД агент будет осуществлять посредством трех иерархически связанных объектов:

1. "Операций"

2. Состоящих из операций "транзакций"

3. Состоящего из транзакций "лога транзакций". ОПЕРАЦИЯ

"Операция" описывает минимальное изменение объектов в БД и может быть применена к (выполнена на) БД. Операция включает тип, адрес целевого объекта(или объектов) и данные, необходимые для выполнения операции. Примером операций может быть:

• Создание объекта. Данные при этом - содержимое объекта, который надо создать, например "создать целое число 8 по адресу [/5/8/12/8]".

• Удаление объекта. Данные при этом - пустое поле, например "удалить объект по адресу [/5/8/12/8]"

• Перенос объекта с адреса А на адрес Б. Данные при этом - адрес Б, на которые надо перенести данные с адреса А. Например, "перенести объект с адреса [/5/8/12/8] на адрес [/5/7/12/8]".

• Сравнение объекта на равенство. Данные при этом - значение, с которым надо сравнить объект. Например "проверить, что по адресу [/5/8/12/8] хранится целое число 8"

Типов такого рода операций может быть множество, от самых простых (создание/удаление, арифметические операции, операции "больше/меньше", операции смены типа с "целое" на "число с плавающей точкой" и т.п.) до более сложных, если объект представляет из себя сложную структуру (перестроить 3D модель звездной системы по адресу [/98585/9982157/6654781] с учетом текущих гравитационных полей).

Операции могут быть различными, но они должны соответствовать следующим критериям:

1. Затрагивать конечное, жестко детерминированное число топологических областей БД. Операция может читать или вносить изменения в один конкретный объект или в группу объектов, но перечень затронутых областей должен определяться однозначно и не зависеть от состояния БД. В идеальном случае операция затрагивает либо один объект в БД (изменение объекта), либо два (перенос объекта), но могут быть и более сложные случаи.

Например, операция вида "перенести объект, на который ссылается объект БД по адресу…" не является, в общем случае, допустимой. Дело в том, что в этом случае, в зависимости от состояния БД на момент исполнения операции, затронутые области могут отличаться.

2. Быть детерминистической, то есть, будучи выполненной на содержащей те же данные БД, операция должна всегда давать один и тот же результат. Если операция "записать случайное число" будет записывать заново сгенерированное (то есть, как правило, новое) случайное число при каждом исполнении на той же самой БД (на одном агенте или на разных), то это некорректная операция.

3. Операция может быть выполнена успешно, а может - неуспешно ("провалиться").

Пример неуспешных (провальных) операций:

а. Операция "арифметически прибавить к объекту "строка “try’" объект "целое число 5" невозможна - со строкой нельзя производить арифметические операции.

b. Операция переноса несуществующего объекта. Если в БД нет объекта [/1/8/9/9/8] то операция "перенести объект [/1/8/9/9/8] на новый адрес [/1/8/9/9/5]" не будет выполнена, поскольку невозможна.

c. Операция сравнения, если сравнение вернуло "ложь" ("false"). Например, если объект у нас "целое число 5" и мы применим к нему операцию "проверить равенство целому числу 8", такая операция будет неуспешна.

4. Операция должна быть "откатываемой" назад. Если мы заменили значение "целое число 5" на "целое число 8", мы можем запомнить прежнее значение, и потом сможем вернуть БД к состоянию "до исполнения операции". Так и с любой другой операцией должна быть возможность "откатить" назад, вернув БД к состоянию "до исполнения операции" (операции "сравнения", поскольку они в БД изменений не вносят, не нуждаются в особой процедуре отката).

ТРАНЗАКЦИЯ

Для внесения изменений в БД отдельные операции возможно объединять в "транзакции". Транзакция может состоять из одной и более операций. Транзакции логически выполняют на БД последовательно, а не параллельно, то есть пока состояние БД меняет одна транзакция, другие транзакции БД не меняют (это требование "логическое", то есть фактическая реализация, отслеживающая области, затрагиваемые транзакциями, может де-факто исполнять параллельно непересекающиеся транзакции для повышения производительности). Операции в транзакции выполняют в заданной последовательности, что, благодаря свойствам операций, позволяет как выполнить транзакцию на БД (при этом все операции выполняются в прямом порядке, до первой неуспешной операции), так и "откатить" (при этом выполненные операции откатывают в обратном порядке и, таким образом, БД гарантированно возвращают в состояние до транзакции).

Опираясь на возможности выполнять откат отдельных операций, возможно сделать все транзакции атомарными. То есть операции транзакции либо все исполняют, либо все не исполняют. Провал (неуспех) любой из операций, входящих в транзакцию, приводит к провалу всей транзакции, при этом выполняют откат всех уже выполненных операций в обратном порядке, а БД по итогу неуспешного исполнения транзакции остается неизменной.

Атомарность, помимо исключения неконсистентных и непредсказуемых изменений БД, полезна для реализации базовой логики "если… то" встроенной в транзакцию, что крайне полезно для работы в условиях неопределенности актуального состояния БД на каждом отдельном агенте. Например, при сочетании операций сравнения с операциями записи, транзакция может выглядеть так:

1. Проверить, что по адресу [/1/2/2/8/7] хранится целое число 12

2. Присвоить целому числу по адресу [/1/2/2/8/7] значение 6

3. Присвоить целому числу по адресу [/1/2/2/8/9] значение 3

4. Проверить, что сумма [/1/2/2/8/7] и [/1/2/2/8/1] равна 8

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

Благодаря тому, что для каждой операции точно известны затронутые в ней топографические области, можно и для каждой транзакции (просто осмотром операций) установить перечень областей БД, которые затронет транзакция.

ЛОГ ТРАНЗАКЦИЙ

Изменения в БД предлагается вносить путем последовательного исполнения транзакций. В простейшем случае первоначально БД будет абсолютно пустой, и на этой БД сначала исполняют транзакции с операциями "создать объект", затем любые другие транзакции.

Общий, безусловно упорядоченный перечень таких последовательно исполняемых транзакций, определим как "лог транзакций".

Транзакции (на каждом агенте и на уровне глобального лога БД) будут помещаться в "лог транзакций" в фиксированном порядке. Порядок можно, например, установить следующий:

1. для каждой транзакции будет сгенерирован уникальный ID,

2. ID будет включать текущее время и ID агента, создавшего транзакцию,

3. также возможно добавить в ID транзакции счетчик транзакций данного агента, что позволит другим акторам обнаруживать "пропущенные" транзакции,

4. поскольку каждая следующая транзакция будет создана позже предыдущей, получится у каждой транзакции уникальный ID,

5. если отсортировать все транзакции, опираясь на такой ID (транзакции), сначала по возрастанию времени, а затем по возрастанию ID агента, и затем счетчика (если его используют, что снижает требования к точности счетчика времени), то получается простой и однозначный способ расположить все транзакции по порядку.

ИСПОЛНЕНИЕ ЛОГА ТРАНЗАКЦИЙ

Полученный лог (упорядоченный список) транзакций может быть исполнен (выполняют все транзакции в прямом порядке, от самых старых к самым новым) и "отменен" (откатываются все транзакции в обратном порядке, от самых новых к самым старым). Лог может быть выполнен (и отменен) полностью или частично.

При добавлении новой транзакции в лог, она может попасть не только в конец списка, но и в произвольное место. Например, если агент А создал транзакцию пять минут назад, но, из-за проблем сетевой связности, смог передать ее для помещения в лог агенту Б только что (т.е. с задержкой), а другие агенты к этому времени уже внесли в лог свои транзакции. При этом, если транзакции, оказавшиеся в списке после ("за") новой транзакции уже были исполнены на БД, их следует "откатить" (вернуть назад), затем выполнить "новую" (а на самом деле старую) транзакцию, а затем заново выполнить все последующие транзакции, которые были только что отменены. Функционально это эквивалентно возврату БД в стартовое состояние и последовательному применению всех транзакций из итогового лога, но выполняется несравненно быстрей, особенно, если лог большой, включает много транзакций.

Поскольку лог транзакций выстроен так, чтобы быть после завершения обмена данными идентичным у всех агентов а все операции детерминистичные, итоговое состояние БД на всех агентах так же будет идентично. Если некоторые операции, добавленные агентами, не будут совместимы с итоговым состоянием БД, они одновременно не будут успешными и не выполнятся у всех агентов, не породив никакой неконсистентности.

Отслеживая затронутые ветви рассматриваемой в примере древовидной адресации БД, можно даже откатывать и выполнять заново не все транзакции, а только те, на результаты которых вновь добавленная транзакция могла повлиять (если таковые есть), что даст еще большую производительность.

Благодаря возможности помещать транзакции в лог в произвольной очередности, множество агентов могут асинхронно и несогласованно добавлять в лог новые транзакции. При этом всегда возможно:

1. однозначно определить, последовательность выполнения транзакций в логе,

2. детерминистически применить к БД имеющийся у агента лог транзакций,

3. получить новые транзакции, вставить их в лог транзакций (в том числе "задним числом") и корректно применить итоговый лог транзакций приведя БД к состоянию, последовательного исполнения итогового лога целиком

4. опираясь на пункты 1-3 выше, возможно участие неограниченного количества агентов, работающих каждый со своей локальной копией БД, при этом получающих идентичные состояния БД, при условии, что они успешно обмениваются своими транзакциями и каждый агент в итоге получает полный перечень транзакций, причем обмен транзакциями между агентами может проходить в любой очередности.

5. опираясь на атомарность транзакций, возможно рассчитывать, что даже в процессе продолжающегося сбора и исполнения лога транзакций каждый агент будет иметь, возможно, уникальное состояние БД, но это состояние будет консистентно и в целом будет пригодно для чтения/записи в каждый момент времени, вне зависимости от скорости и регулярности обмена транзакциями с другими агентами.

6. побочным негативным следствием такого способа является невозможность гарантировать успешное выполнение транзакции в момент помещения ее в лог агентом. Точно определить, была ли транзакция исполнена или провалилась, можно только в момент наступления "ясности", об этом см. далее.

Следует отметить, что использование для распределенной работы с данными технологии "БД + Лог Транзакций" (DLT, Distrit ledger) является общеизвестной и широко используемой в многих системах хранения, например, в Р2Р-криптовалютах, таких как Bitcoin. Новизна заявляемого решения (подробно описанная ниже) состоит в том, что общий лог транзакций разбивают на сегменты благодаря и в связи с "топологической (топографической) сегментацией БД" и агенты, в каждый момент времени работая только с выбранными сегментами, могут быстро интегрировать изменения и в результате взаимодействовать с единой БД произвольного объема располагая крайне ограниченными ресурсами.

РАСПРЕДЕЛЕННОЕ ХРАНЕНИЕ БД

ЛОКАЛЬНАЯ КОПИЯ ФРАГМЕНТА БД

Предлагается на компьютерном устройстве агента хранить БД (целиком или частично) в виде набора независимых объектов, например, в виде файлов на диске, и/или объектов в памяти ЭВМ. На каждую топологическую область должно приходиться по одному изолированному объекту хранения. Каждый такой объект хранения может, в свою очередь, сам состоять из нескольких объектов, в зависимости от реализации, но в данном случае важно, что локальный объект, относящийся к одной области, может быть изменен, удален или скопирован агенту извне, полностью независимо от объектов, относящихся к другим областям. Объект, хранящий данные по отдельной области, на соседние объекты не влияет, а соседние объекты не влияют на него.

Дополнительно можно делить объекты по "слоям" (например, типам), чтобы агент мог загрузить себе один слой для области, но не загружать данные по другим слоям.

В простейшем виде (удобном для пояснения) база может храниться на жестком диске агента в виде прямого указания пути к файлу и адреса объекта. При этом объект по адресу [/1/2/1/1] будет (например) храниться в файле "/storage/1/2/1/1.dat", а объект по адресу [/1/3/2/3/15] в файле "/storage/1/3/2/3/15.dat". Чтение/запись из такой базы реализуется тривиально и данные, относящиеся к одному слою одной топологической области, представлены папкой на диске. Такую папку можно легко удалить, изменить ее содержимое или скопировать у другого агента и это никак не затронет папки, в которых хранятся данные соседних областей.

Более реалистичная реализация может использовать berkleydb (или аналогичную технологию хранения ключ-значение, например, https://ru.wikipedia.org/wiki/%D0%91%D0%B0%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85%C2%AB%D0%BA%D0%BB%D1%8E%D1%87-%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D0%B5%C2%BB) в качестве хранилища данных области. Если объем данных велик, а интенсивность записи высока, можно использовать несколько berkleydb-хранилищ, по одному для каждого "слоя". Если объем данных невелик и частичные обновления редки, можно использовать стандартные средства сериализации/ десериализации, например https://habr.com/ru/post/4 7 9462/. Для сессионных приложений, не требующих долговременного хранения данных, такие как "сессионные игры", где данные по окончании партии не нужны, можно ограничиться хранением данных по каждой области в памяти приложения, в виде динамически создаваемых ООП-объектов или иных, ориентированных на хранение данных в используемом языке программирования, структур (например struct в С++ https://en.wikipedia.org/wiki/Struct (С programming language))

ЗОНА ВИДИМОСТИ

Каждый агент может иметь (заданную самим агентом или установленную ему извне) произвольную зону видимости. Например, компьютер автомобиля, разыскивающий место для парковки, нуждается в информации о свободных парковках в радиусе 500 м, а информация о парковочных местах на другом конце города ему не нужна. Зона видимости может со временем меняться - перемещаться, изменять охват и т.д.

В большинстве случаев информацию о зоне видимости агента стоит хранить в БД.

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

По мере изменения "зоны видимости", агент будет удалять (или архивировать) у себя объекты, не относящиеся к его новой "зоне видимости" и получать извне (от соседних агентов или от сервера) данные по областям, которые в зоне видимости появились.

В результате, каждый агент в каждый момент времени будет хранить и обновлять у себя фрагмент базы, представляющий собой несколько областей из общей "мозаики".

СЕГМЕНТИРОВАННЫЙ ЛОГ ТРАНЗАКЦИЙ

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

Как уже зафиксировано при описании объектов "транзакция", для каждой транзакции всегда точно известен перечень затронутых этой транзакцией топологических областей. Таким образом, возможно хранить (идеологически "единый" для всей БД) лог транзакций в виде набора "локальных" логов транзакций, относящихся к конкретным топологическим областям. При этом, если транзакция затрагивает (изменяет) несколько областей, возможно хранить несколько копий этой транзакции, по одной на каждую затронутую область. Дублирующиеся транзакции возможно обнаружить, поскольку каждой транзакции присвоен уникальный ID, что позволяет избавиться от повторов при объединении логов транзакций нескольких областей в единый лог транзакций.

В этом случае каждый агент хранит лог транзакций в виде набора независимых логов, относящихся к отдельным областям. Например, для слоя 1 и области 2:1 лог можно хранить в файле "/storage/1/2/1/1.log".

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

Единственным исключением в этом случае может оказаться наличие операций типа копирования/переноса объектов из областей, не входящих в зону видимости агента, в область, находящуюся в зоне видимости. Эту проблему можно решить выборочным хранением в логе развернутой версии таких транзакций. Например, в целевой области [/2/3/4] вместо "копировать число с адреса [/1/1/1/4] на адрес [/2/3/4/5]" будет операция "создать число 5 адресу [/2/3/4/5]", а вместо "перенести" "перенести либо, если источник недоступен, создать"). Также возможно создать протокол обмена данными между агентами, чтобы агент мог запросить необходимый ему фрагмент данных у соседей и осуществить копирование недоступных объектов с полученного фрагмента. Оба решения, предполагают, что область-донор находится в состоянии "ясности" (полной определенности) (подробнее см. ниже), то есть транзакций "задним числом" уже не будет и агент точно знает финальное состояние копируемого объекта на момент копирования.

ЕДИНАЯ БД КАК СУММА ЛОКАЛЬНЫХ КОПИЙ

Если имеется множество независимых агентов, использующих одну базу данных и обменивающихся данными между собой (например, через сеть интернет, подробности см. ниже), такая "мозаичная" база может не быть доступна целиком ни одному агенту и может не храниться целиком нигде. При этом каждый агент будет работать со своим фрагментом и сможет, при необходимости, получать необходимые фрагменты от других агентов.

Для отдельных применений (или для отдельных слоев более сложной БД) такая "мозаичная БД" из разбросанных по агентам фрагментов является уже полностью функциональной. Такой БД не требуется сервер или выделенный агент, хранящий всю БД целиком. Она как целое физически не существует ни на одной отдельной ЭВМ, каждый агент-пользователь видит и хранит только свой фрагмент. Если у фрагмента не остается ни у одного "хранителя" - значит это просто пустой фрагмент.

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

Аналогичная реализация может работать для базы, данные в которой стремительно устаревают - данные с датчиков, обновляемые ежесекундно и т.п. Как только датчик перестанет обслуживать свою область (выйдет из строя, потеряет связь) соответствующая ему топологическая область станет "недоступна", но это вполне точно отражает положение вещей, так что можно считать, что БД со своей работой справилась.

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

СВЯЗЬ МЕЖДУ АГЕНТАМИ

Для того, чтобы описываемая БД успешно функционировала, каждый агент должен иметь возможность:

1. Идентифицировать (желательно всех) агентов, чья зона видимости пересекается с зоной видимости данного агента (далее "соседей")

2. Устанавливать связь и/или обмениваться данными с некоторыми (или всеми) соседями

3. Связь между соседями должна обеспечивать связь каждого с каждым, опосредованно (сосед моего соседа связан со мной) или напрямую. Иными словами, все соседи, имеющие перекрытия зон видимости, должны формировать (сформировать, образовать) связный граф.

Например, в случае автомобилей, связь и идентификация соседей может осуществляться напрямую, посредством WiFi соединений между агентами, либо посредством стандартной сотовой сети. При использовании стандартной сотовой сети для передачи данных идентифицировать соседей агенты самостоятельно не смогут, сведения о соседях должны будут предоставить либо сотовая сеть, либо какой-то другой провайдер.

В случае военного подразделения, перечень подключенных к сети узлов может быть задан заранее и/или извне, так как произвольным узлам доступ в такую сеть не нужен. Связность между узлами здесь будет, вероятно, достаточно разнородна и может обеспечиваться с учетом особенностей имеющегося в наличии оборудования и обстановки - какие-то каналы будут проводные, какие-то радио-, где-то можно использовать оптическую передачу. Но логика работы описываемой БД не чувствительна к природе и разнородности каналов постольку, поскольку агенты смогут систематически обмениваться сообщениями, содержащими транзакции и т.п. (см. ниже). Связь "каждый с каждым" не требуется, достаточно чтобы граф агентов был связным.

В сетевой игре соединения так же будут часто разнородны: выделенный сервер может потребоваться на этапе подключения агента к сообществу, в дальнейшем, в зависимости от требовательности игры к безопасности и отзывчивости, клиенты могут либо вовсе не прибегать к услугам сервера, либо прибегать в крайних ситуациях (например, для создания Р2Р каналов между агентами, подключенными через NAT (Network Address Translation), либо (оптимально) передавать максимально возможный объем данных через Р2Р каналы, а то, что невозможно обработать через прямые соединения (из-за требований безопасности и/или из-за невозможности создать Р2Р соединение) обрабатывать с привлечением сервера.

ОБМЕН ИНФОРМАЦИЕЙ МЕЖДУ АГЕНТАМИ

Обмен данными между агентами будет, по крайней мере, состоять из следующих шагов:

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

• агент может рассылать всем соседям "пульс" (синхронизирующие сообщения), содержащий текущее время и ID последней выписанной агентом транзакции (см. ниже раздел "ясность"),

• агент может заверять полученные от соседей транзакции (например, заверять секретным ключом время и/или выполнимость транзакции) и рассылать отдельное заверение и/или уже заверенную "А выписал, Б одобрил" транзакцию,

• агент может пересылать полученные транзакции (и заверения транзакций) дальше, другим соседям (функционально выступая "транзитным шлюзом"). При этом агент может просто пересылать транзакции дальше всем соседям, которые не прислали транзакцию с этим ID, или использовать оптимизационные алгоритмы опираясь на знания состояния "сети" соседей,

• агент может по запросу передавать соседу "снимок" известной ему области БД (см. ниже) и/или фрагмент лога транзакций, относящихся к известной ему области БД; снимок может быть подписан электронной подписью, чтобы удостоверить целостность и авторство "снимка БД" и "снимка лога транзакций",

• Агент может, по запросу соседа, передавать ему транзакцию с определенным ID (например, полезно, если транзакция не была доставлена из-за сетевых проблем, а сосед из пульса знает, что она существует).

СОСТОЯНИЕ ОБЛАСТИ - ОБМЕН МЕЖДУ АГЕНТАМИ

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

1. агент находит соседа, уже имеющего нужную область у себя в зоне интереса (и авторизованного (обладающего правами) отдавать по запросу "снимок" информации области),

2. агент посылает этому соседу запрос "требуется снимок области",

3. сосед, если он не располагает информацией по интересующей области, может переслать такой запрос далее или вернуть отказ; если информация у него есть, сосед удовлетворяет запрос; для этого:

a. сосед выясняет последнюю известную транзакцию, перед которой уже новых транзакций точно не будет (т.е. "момент ясности") (см. ниже раздел «ЯСНОСТЬ»)

b. откатывает (в простейшем случае) вообще все исполненные после "момента ясности" транзакции, либо (чуть сложней) транзакции, относящиеся к нужной области и размещенные в логе после "момента ясности" плюс транзакции, от которых зависят эти транзакции,

c. снимает слепок с области (в простом примере с файлами, это может быть zip-архив с содержимым папки области),

d. передает запросившему полученный слепок,

e. передает запросившему ID последней исполненной на слепке транзакции,

f. передает запросившему перечень агентов-соседей с состоянием их счетчиков (в случае расчета "ясности" на основе счетчиков транзакций),

g. передает запросившему все известные транзакции, относящиеся к запрошенной области и имеющиеся у отдающего в логе после "момента ясности",

h. все вместе или по отдельности может быть перед передачей подписано секретным ключом,

4. получив и разместив этот набор данных, агент получает полноценный рабочий раздел БД, отвечающий за область, и может дальше штатно работать (в т.ч. предоставлять "слепок" другим соседям, если он авторизован на такие операции),

5. если первый сосед не вернул запрошенный снимок агент запрашивает снимок у другого соседа, затем у следующего, и так далее,

а. Если ни один сосед, авторизованный отдавать "снимки" (включая соседей, выступающих роли выделенных агентов-архивариусов, агентов-серверов и пр., если такие имеются) не вернул требуемый снимок, агент может действовать так же, как если бы его соединение с сообществом было физически разорвано.

Последующие транзакции агент штатно получает из рассылок (либо явно запрашивает, если из пульса становится ясно, что какие-то транзакции, добавленные другими агентами в лог после момента "снимка", у него отсутствуют).

РОЛИ АГЕНТОВ

В зависимости от требований конкретного приложения, агенты (устройства-участники), составляющие сообщество, могут быть полностью идентичны и равноправны, либо могут иметь явно выраженное разделение функций. Роли агентов могут меняться от структуры "все равны" до многоуровневой переплетенной схемы, где разные агенты имеют разные права на разные слои БД, разные типы транзакций, etc.

Разделение, например, может выглядеть так:

• агент может выступать в роли "недоверенного актора" (недоверенного участника сообщества): имеет право создавать транзакции, которые другие агенты должны проверить и заверить либо отвергнуть,

• агент может выступать в роли "арбитра", не имеющего права создавать транзакции, но имеющего право заверять транзакции; такого "арбитра" может, например, принудительно назначать каждому агенту-актору сервер,

• часть агентов, контролируемых администрацией, может выступать в роли "сервера" с исключительными правами подписывать и заверять собственные транзакции, с правом записи в слой БД "реестр пользователей".

• роли агентам может выдавать выделенный агент-сервер,

например, занося данные о статусе каждого агента в БД в раздел, доступный на запись только серверу, и все остальные агенту будут ориентироваться на эту информацию.

Агенты - арбитры

Стоит также иметь в виду, что на одной ЭВМ (с одной и той же БД) может одновременно работать несколько агентов в разных ролях (или даже в разных ролях на разных БД). Например, подключившись к серверу авторизации компьютерной сетевой игры программа, помимо подключения к БД для управления аватаром игрока в роли "недоверенного актора", может получить роль "арбитра" в той же (или другой) БД. При этом агент будет проверять и заверять действия другого игрока, случайно подобранного сервером, чтобы исключить мошеннические, запрещенные игрой, действия.

Такая валидация "на стороне случайного игрока" не является абсолютно надежной защитой от несанкционированных изменений БД, валидация на стороне сервера позволяет добиться большей надежности. Но полноценная валидация на стороне сервера крайне ресурсоемка и потому редко используется. К тому же ресурсоемкость серверной валидации линейно возрастает с числом игроков, что часто делает ее совершенно неприменимой. Валидация же одним игроком другого игрока масштабируется бесконечно, параллельно с ростом числа игроков. Назначив каждому игроку двух случайных "арбитров" из числа игроков, получают вероятность "сговора" арбитров и игрока 0,01% в игровой вселенной, где присутствует всего 100 игроков. С ростом числа игроков привлекательность взлома линейно растет, но при этом нелинейно (обратно пропорционально квадрату числа игроков) падает и вероятность "сговора" игрока и арбитров, что дает прекрасный баланс безопасности и простоты реализации.

ЯСНОСТЬ

В БД, функционирующей в описываемом режиме из-за непредсказуемых задержек доставки, обрывов связности и перестроек структуры сети, агент может столкнуться с вопросом: куда в имеющийся лог транзакций все еще могут добавиться новые транзакции, а где лог уже зафиксирован и новых транзакций гарантированно не будет?

Это важно, например, при передаче "снимка" области БД, так как снимок должен состоять из собственно снимка данных в БД и лога транзакций, которые были добавлены после снятия снимка. Если сделать снимок по состоянию на некоторый момент времени Т и передать такой снимок (слепок) соседу, и потом окажется, что появилась новая транзакция, датированная временем Т-1, то сосед, не имея полноценного лога для периода, предшествовавшего Т, не сможет применить такую транзакцию к своей БД.

В описанном выше варианте сортировки лога транзакций по ID, состоящего из времени и ID актора, вопрос звучит как: "какой минимальный ID транзакции, который мы еще можем получить от других соседей?"

Для установления "ясности" можно использовать следующие способы.

КОНСЕНСУС

Каждую транзакцию заверяют каждым агентом, имеющим право записи в область, большинством или отобранным по другим правилам множеством агентов, или даже просто сервером. Возможно, например, использовать алгоритм BLS (https://ru.wikipedia.org/wiki/BLS), позволяющий компактно хранить серию подписей, или использовать другой способ. Подход консенсуса не эффективен, плюс он потенциально допускает "отмену" транзакций, когда часть агентов, не успевших "проголосовать", вынуждены отменять транзакцию. Но в некоторых приложениях БД требуется консенсус/заверение/подпись в любом случае, например, при работе с криптовалютами, чтобы убедиться, что транзакция соответствует всем критериям безопасности, допустимости и т.п. Например, если это денежный перевод и мы хотим быть уверены, что и "плательщик" и "получатель" согласны с операцией и у нас есть достаточное число "свидетелей" и т.д. При этом консенсус по транзакции Б может быть выпущен только после того, как был достигнут консенсус по транзакции А (например, подпись каждой следующей транзакции должна включать заверяющую подпись предыдущей, стандартный blockchain), что автоматически даст и заверение транзакции, и отслеживание "ясности".

ПУЛЬС + СЧЕТЧИКИ (Как достигается "ясность": как обнаружить пропущенные в локальном логе транзакции)

1. ID транзакции включает инкрементальный счетчик транзакций каждого агента. Агент увеличивает значение счетчика на 1 в каждой следующей созданной транзакции (счетчик можно ротировать, например увеличивать до 255 и затем сбрасывать в 0),

2. каждый агент имеет публичную (видимую в БД остальным агентам) "активную область", то есть перечень областей, в которые агент может вести запись, т.е. размещать новые транзакции,

3. с заданной периодичностью агенты рассылают "пульс", содержащий информацию о текущем времени и о последнем ID транзакции, которую данный агент поместил в лог (а в этом ID присутствует описанный выше счетчик),

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

5. если счетчик пульса больше, чем счетчик последней транзакции соседа, или если последняя полученная транзакция соседа увеличила счетчик более, чем на 1, это означает, что сосед создал транзакцию, которой у агента нет и он запрашивает ее повтор у соседей,

6. когда пульс и/или свежие транзакции от всех соседей с правом записи получены, агент точно будет знать, где находится "точка ясности" (меньше какого ID все помещенные в лог транзакции агенту уже известны).

Способ отличается простотой, но потенциальной проблемой является непредвиденное "выпадение" отдельных агентов, например из-за обесточивания, которое создаст задержку в установлении "точки ясности" из-за отсутствия пульса и, следовательно, информации о последней транзакции "отключенных" агентов. Но "точка ясности" необходима, в основном, для оптимизации обмена снимками между агентами и система остается полностью работоспособной даже в ситуации, если аварийное событие случится и точка ясности "застрянет" после (не продвинется дальше) первой транзакции в логе. При нештатном отключении агентов, как вариант, сервер или другой авторизованный агент, обнаружив потерявшего связь "агента", может выпустить "задним числом" транзакцию, удаляющую выпавшего агента из числа "активных агентов" в момент, когда была потеряна связь, после чего процедура установления ясности штатно продолжит работать.

Так же "узким местом" такой системы является появление соседей. Если, по каким-то причинам, агент не узнает, что у него появился новый сосед, агент не будет отслеживать его пульс и не узнает о том, что пропустил транзакции. Эту проблему можно решить принудительной рассылкой транзакций типа "смена активной зоны", например, через выделенный агент-сервер, гарантирующий доставку всех транзакций типа "появление соседа". Возможно принудительно ничего не рассылать, а считать все дальние области "неясными" и определять ясность для них не слушая пульс, а слушая подтверждения ясности, включающее "ID прошлой транзакции" от агентов, имеющих право записи в область. При этом можно дополнительно принудительно рассылать транзакции для "пустых областей" (при входе агента в область, где никого нет и при выходе "последнего" агента из области). Этот способ (сочетание "ясности, определяемой агентами, имеющими право записи в область и принудительной рассылки транзакций для пустых областей) хорошо работает, если каждый агент имеет зону видимости (область, данные из которой агент читает) с запасом покрывающую "активную зону", например если агент может писать только в одну область 2-х мерной БД, то читать может в эту область и в 8 прилегающих областей.

СПОСОБ ДИСТРИБУЦИИ БД

Предлагаемая БД может существовать как в виде библиотеки, так и в виде отдельного приложения, доступного в форме "сервера" простым NOSQL-клиентам, например по протоколу memcached (https://github.com/memcached/memcached/blob/master/doc/protocol.txt).

При настройке администратор БД описывает (в конфигурационном файле или в программном коде) размерность и структуру БД, типы и полномочия агентов, методы (либо произвольные программные процедуры) валидации (удостоверения) транзакций и другие параметры, после чего либо интегрирует библиотеку в свое программное обеспечение, где работа с БД является частью другого функционала, либо запускает БД на своей ЭВМ.

Изобретение относится к вычислительной технике. Технический результат заключается в сокращении потребности в вычислительных ресурсах и пропускной способности сетевого канала при увеличении объема БД. Способ сбора, хранения, обновления и обработки информации об n-мерном пространстве, заранее разбитом на топологические, в том числе геометрические, топографические области, включающий сбор информации средствами сбора, находящимися на устройствах, имеющих координаты в описываемом пространстве и способных обмениваться между собой информацией, всех вместе образующих связный граф, размещение информации, относящейся к топологической области, на средствах хранения информации, расположенных на указанных подключенных к сообществу устройствах, имеющих в этот момент координаты в пределах этой области и соседних областей, обмен информацией с устройствами, имеющими координаты в этой или других, преимущественно смежных, областях, удаление информации, касающейся топологической области, при изменении координат устройства на другие, удаленные от данной области. 3 н. и 14 з.п. ф-лы, 1 ил.

1. Способ сбора, хранения, обновления и обработки информации об n-мерном пространстве, заранее разбитом на топологические, в том числе геометрические, топографические, области, включающий сбор информации средствами сбора, находящимися на устройствах, имеющих координаты в описываемом пространстве и способных обмениваться между собой информацией, всех вместе образующих связный граф, размещение информации, относящейся к топологической области, на средствах хранения информации, расположенных на указанных подключенных к сообществу устройствах, имеющих в этот момент координаты в пределах этой области и соседних областей, обмен информацией с устройствами, имеющими координаты в этой или других, преимущественно смежных, областях, удаление информации, касающейся топологической области, при изменении координат устройства на другие, удаленные от данной области,

причем запись и изменение информации осуществляют через распределенный лог операций (DLT), где каждая операция изменяет данные только о заранее фиксированном наборе указанных выделенных областей n-мерного пространства,

причем полный лог всех операций хранят в виде набора выборок из этого полного лога, где каждая выборка состоит из полного перечня операций, относящихся к конкретной топологической области,

причем каждое устройство хранит у себя перечень всех подключенных к сообществу устройств, имеющих координаты в своей и смежных областях пространства,

причем устройства, имеющие координаты внутри топологической области, передают другим устройствам, имеющим координаты внутри этой же области и/или в прилегающих областях, информацию в процессе записи,

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

2. Способ сбора, хранения, обновления и обработки информации об n-мерном пространстве по п. 1, в котором "консенсус" фиксируется после подтверждения получения информации от всех устройств в той же и смежных областях.

3. Способ сбора, хранения, обновления и обработки информации об n-мерном пространстве по п. 1, в котором при обмене сообщениями между устройствами осуществляют ассиметричное шифрование сообщений.

4. Способ сбора, хранения, обновления и обработки информации об n-мерном пространстве по п. 1, в котором при обмене сообщениями между устройствами сообщения снабжают электронной подписью, позволяющей гарантировать подлинность сообщений.

5. Способ сбора, хранения, обновления и обработки информации об n-мерном пространстве по п. 1 или 2, в котором

- каждое устройство хранит у себя информацию о последней операции, затрагивающей свою и любую из смежных областей, ранее которой устройству известны все операции, совершенные всеми устройствами в сообществе для своей и смежных областей;

- новую транзакцию о своей области записывают в локальную память каждого устройства в статусе "принята";

- при этом каждое устройство отслеживает все изменения, вносимые другими устройствами, имеющими координаты в той же области, где находится устройство, и в смежных областях, а также периодически рассылает всем соседним устройствам информацию о том, какая транзакция была записана этим устройством последней, или информацию о том, что запись не осуществлялась;

- каждое устройство отслеживает полноту своего лога операций и запрашивает пропущенные транзакции, если о них узнаёт, либо обновляет для себя информацию об операции, перед которой этому устройству все операции известны.

6. Способ сбора, хранения, обновления и обработки информации об n-мерном пространстве по п. 1, в котором существует одно и более устройство с функциями сервера, которое выполняет по крайней мере первичную авторизацию устройств, проксирование информации и организацию P2P взаимодействия между агентами.

7. Способ сбора, хранения, обновления и обработки информации об n-мерном пространстве по п. 6, в котором указанный сервер не принадлежит сообществу и не имеет координат в указанном n-мерном пространстве.

8. Способ сбора, хранения, обновления и обработки информации об n-мерном пространстве по п. 1, в котором любое из устройств при входе в указанную n-мерную область проходит процедуру авторизации.

9. Способ сбора, хранения, обновления и обработки информации об n-мерном пространстве по п. 1, в котором любому из устройств назначают дополнительно более широкие или урезанные права доступа к данным, расширенные или сокращенные обязанности, другие доп. обязанности или ограничения по сравнению с другими устройствами-участниками сообщества.

10. Динамическая система сбора, обработки, обмена и размещения информации об n-мерном пространстве, включающая

- n-мерное пространство, предварительно разделенное на топологические области;

- одно или более устройство, которому присвоены координаты в n-мерном пространстве, снабженное одним или более средством сбора информации, средством хранения информации, средством связи с другими устройствами, с возможностью перемещения как внутри одной топологической области, так в любую из смежных топологических областей,

причем указанная информация, содержит в том числе логический адрес,

причем средство хранения информации дополнительно включает средство хранения статуса информации, частичный лог - выборку из общего распределенного лога транзакций,

причем в частичном и полном логе операций каждой операцией изменяются данные только о заранее фиксированном наборе указанных выделенных областей n-мерного пространства,

причем полный лог всех операций хранится в виде набора выборок из этого полного лога, и каждая указанная выборка состоит из полного перечня операций, относящихся к конкретной топологической области,

причем информация о текущей области записана в локальную память устройство-инициатор первоначально в статусе "не согласована", затем после подтверждения - в статусе "согласована".

11. Динамическая система сбора, хранения, обновления и обработки информации об n-мерном пространстве по п. 10, в которой в логическом адресе каждого фрагмента информации обязательно присутствует уникальный идентификатор, однозначно определяющий область, к которой принадлежит данная запись.

12. Динамическая система сбора, хранения, обновления и обработки информации об n-мерном пространстве по п. 10, в которой информация о каждой области пространства включает перечень всех подключенных к сообществу устройств, имеющих координаты в данной области.

13. Динамическая система сбора, хранения, обновления и обработки информации об n-мерном пространстве по п. 10, в которой транзакция о текущей области записана в локальную память устройство-инициатор первоначально в статусе "принята".

14. Динамическая система сбора, хранения, обновления и обработки информации об n-мерном пространстве по п. 10, в которой существует одно и более устройство с функциями сервера для первичной авторизации устройств, проксирования информации и организации P2P взаимодействия между агентами, не принадлежащее сообществу и не имеющее координат в указанном n-мерном пространстве.

15. Размещенная на компьютере система для сбора, обработки, обмена и размещения информации в области n-мерного пространства, включающая информационную шину, присоединенный к информационной шине процессор, устройство сбора информации, устройство памяти,

- содержащая инструкции для сбора информации, обмена данными с другими устройствами, находящимися в n-мерном пространстве,

- дополнительно содержащая инструкции устройствам, имеющим координаты внутри топологической области передавать другим устройствам, имеющим координаты внутри этой же области и смежных областях, информацию в процессе записи,

- дополнительно содержащая инструкции, что каждая процедура записи данных в область состоит из

• первичной записи в локальную память одного устройства,

• назначения первичной записи статуса "не согласована",

• рассылки (прямой или посредством пересылки) данных другим устройствам в этой же области, соседям в смежных областях,

• получения ответа от всех соседних устройств в пределах области и смежных областей, что данные приняты,

• назначения первичной записи статуса "согласована".

16. Размещенная на компьютере система по п. 15, дополнительно содержащая инструкции: назначить одному из устройств функции сервера для первичной авторизации устройств, проксирования информации и организации P2P взаимодействия между агентами, не принадлежащего сообществу и не имеющему координат в указанном n-мерном пространстве.

17. Размещенная на компьютере система по п. 15, дополнительно содержащая инструкции:

• каждому устройству хранить у себя информацию о последней операции, затрагивающей свою и любую из смежных областей, ранее которой устройству известны все операции, совершенные всеми устройствами в сообществе для своей и смежных областей;

• каждому устройству записывать в локальную память (средство хранения) устройства в статусе "принята" новую информацию о своей области;

• каждому устройству отслеживать все изменения, вносимые другими устройствами, имеющими координаты в той же области, где находится устройство, и в смежных областях, а также периодически рассылать всем соседним устройствам информацию о том, какая транзакция была записана этим устройством последней, или информацию о том, что запись не осуществлялась,

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