ЭФФЕКТИВНОЕ ЛОГИЧЕСКОЕ СЛИЯНИЕ ФИЗИЧЕСКИ РАСХОДЯЩИХСЯ ПОТОКОВ Российский патент 2017 года по МПК G06F17/30 

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

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

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

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

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

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

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

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

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

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

Фиг. 2 показывает краткий обзор одного применения модуля логического слияния, показанного на фиг. 1.

Фиг. 3 показывает краткий обзор другого применения модуля логического слияния, показанного на фиг. 1.

Фиг. 4 показывает физическое представление потока.

Фиг. 5 показывает логическое представление входных потоков в виде экземпляра временной базы данных (TDB).

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

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

Фиг. 8 - процедура, которая дает краткий обзор одного способа работы модуля логического слияния, показанного на фиг. 1.

Фиг. 9 показывает одну реализацию модуля логического слияния, показанного на фиг. 1.

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

Фиг. 11 - процедура для обработки элементов во входных потоках с использованием модуля логического слияния, показанного на фиг. 9.

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

Фиг. 13-16 показывают разные алгоритмы для обработки входных потоков с использованием модуля логического слияния, показанного на фиг. 9.

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

Фиг. 18 - процедура, которая показывает различные применения модуля логического слияния, показанного на фиг. 17.

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

Одинаковые номера используются в раскрытии и на фигурах для ссылки на аналогичные компоненты и признаки. Числа из серии 100 относятся к признакам, первоначально найденным на фиг. 1, числа из серии 200 относятся к признакам, первоначально найденным на фиг. 2, числа из серии 300 относятся к признакам, первоначально найденным на фиг. 3, и так далее.

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

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

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

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

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

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

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

A. Краткий обзор модуля логического слияния

Фиг. 1 показывает краткий обзор функциональных средств 100 для использования модуля 102 логического слияния для создания выходного потока, который является логически совместимым с физически расходящимися потоками (последующее объяснение разъяснит понятие "физический" и "логический", например, со ссылкой на фиг. 4 и 5). Более определенно, модуль 102 логического слияния принимает два или более цифровых входных потоков из нескольких соответствующих физических источников. Входные потоки семантически передают одинаковую информацию, но могут выражать эту информацию разными физическими способами (по причинам, которые будут изложены ниже). Модуль 102 логического слияния динамически формирует выходной поток, который логически представляет каждый из физически расходящихся входных потоков. Иными словами, выходной поток обеспечивает объединенный способ выражения логической сущности входных потоков, который является совместимым с каждым из входных потоков. Использовать выходной поток может потребляющий объект любого типа.

Любая среда 104 реализации может использовать модуль 102 логического слияния. В наиболее показательных примерах среда 104 реализации соответствует системе управления потоками данных (системе DSMS). Система DSMS может применять модуль 102 логического слияния как по меньшей мере один компонент в непрерывном запросе. (В качестве справочной информации, непрерывным запросом называется потоковый аналог запроса базы данных. Вместо того чтобы выполнять одно отдельное исследование информационного содержания статической базы данных, непрерывный запрос работает длительный период времени, чтобы динамически преобразовать один или более входные потоки в один или более выходные потоки.) Более определенно, система DSMS может рассматривать модуль 102 логического слияния как примитивный оператор. Кроме того, система DSMS может применять модуль 102 логического слияния отдельно или в комбинации с любыми другими операторами. Однако применение модуля 102 логического слияния к средам DSMS является иллюстративной, а не ограничивающей; модуль 102 логического слияния могут использовать другие среды, такие как различные среды обработки сигналов, среды коррекции ошибок и так далее.

Фиг. 2 показывает краткий обзор одного применения модуля 202 логического слияния. В этом случае несколько блоков (М₁, M₂, …, M_N) подают несколько соответствующих входных потоков в модуль 202 логического слияния. Например, блоки (М₁, M₂, …, M_N) могут представлять вычислительные машины (или потоки команд на одной машине, или экземпляры виртуальных машин и т.д.), которые обеспечивают данные измерений модулю 202 логического слияния (например, без ограничения данные измерений использования центрального процессора и/или памяти, научные данные измерений и т.д.) В другом случае блоки (М₁, M₂, …, M_N) могут представлять разные вычислительные машины (или потоки команд, или экземпляры виртуальных машин и т.д.), которые реализуют один и тот же запрос, возможно, используя разные соответствующие планы выполнения запросов. Блоки (М₁, M₂, …, M_N) могут быть локальными или удаленными по отношению к модулю 202 логического слияния. Если они являются удаленными, одна или более сетей (не показаны) могут соединять блоки (М₁, M₂, …, M_N) с модулем 202 логического слияния.

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

Фиг. 3 показывает краткий обзор одного способа, которым модуль 302 логического слияния может быть объединен с другими операторами для реализации непрерывного запроса в системе DSMS. Эти операторы могут представлять примитивы операторов другого типа, в том числе агрегатные операторы, которые выполняют функцию агрегации, селекторные операторы, которые выполняют функцию фильтрации, операторы сортировки, которые выполняют операцию сортировки, операторы объединения, которые выполняют физическое объединение двух или больше потоков данных, и так далее. В дополнение, или в качестве альтернативы, модуль 302 логического слияния может быть объединен с другими модулями логического слияния.

Например, в одном случае входные потоки, которые подаются в модуль 302 логического слияния, могут представлять выходные потоки, сформированные одним или более другими операторами 304. В дополнение, или в качестве альтернативы, выходной поток, сформированный модулем 302 логического слияния, может быть подан в один или более других операторов 306.

Фиг. 4 показывает одно представление потока, который может подаваться в модуль 102 логического слияния, показанный на фиг. 1, или поток, который может быть выдан модулем 102 логического слияния. Поток (s) включает в себя последовательность элементов (e₁, e₂, …). Эти элементы могут предоставлять информацию полезной нагрузки в сочетании с командами, которые управляют тем, каким образом информация, извлеченная из входного потока, передается в выходной поток (это будет подробно изложено ниже). Префикс S(i) входного потока представляет часть входного потока, например, S(i)=e₁, e₂, …, e_i.

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

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

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

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

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

Разные планы выполнения запросов. В качестве альтернативы, или в дополнение, два разных источника могут использовать разные планы выполнения запросов для исполнения семантически эквивалентной функции обработки. Эти два источника производят выходные потоки, которые логически представляют один и тот же результат, но потенциально по-разному. Например, первый источник может выполнять трехстороннее соединение, объединяя поток A данных с потоком B данных, и затем объединяя полученный промежуточный результат с потоком C данных. Второй источник может сначала объединить поток B данных с потоком C данных и затем объединить полученный промежуточный результат с потоком A данных. Поток, выданный первым источником, может физически отличаться от потока, выданного вторым источником вследствие использования разных стратегий обработки этими источниками.

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

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

Входной поток (или выходной поток) может включать в себя различные типы команд, соответствующие различным типам составляющих элементов. В одной иллюстративной среде поток включает в себя элементы вставки, элементы коррекции и элементы стабилизации. Элемент вставки insert (p, V_s, V_e) добавляет событие в выходной поток с полезной нагрузкой p, время жизни которого представляет собой интервал (V_s, V_e). Как указано, V_e может быть оставлен открытым (например, +∞). Для краткости элемент вставки иногда будет обозначаться ниже как insert().

Элемент коррекции adjust(p, V_s, V_old, V_e) заменяет ранее выданное событие (p, V_s, V_old) на (p, V_s, V_e). Если V_e=V_s, событие (p, V_s, V_old) будет удалено (например, отменено). Например, последовательность элементов insert(A, 6, 20) → adjust(A, 6, 20, 30) → adjust(A, 6, 30, 25) эквивалентна единственному элементу insert(A, 6, 25). Для краткости элемент коррекции иногда будет обозначаться ниже как adjust().

Элемент стабилизации stable(V_c) фиксирует часть выходного потока, который происходит до времени V_c. Это означает, что не может быть будущего элемента insert(p, V_s, V_e) добавляет с элемент с V_s<V_c, и не может быть элемента коррекции с V_old<V_c или V_e<V_c. Другими словами, элемент stable(V_c) может быть рассмотрен как "замораживание" некоторых частей выходного потока. Событие (p, V_s, V_c) является наполовину замороженным (HF) если V_s<V_c≤V_e, и полностью замороженным (FF), если V_e<V_c. Если событие (p, V_s, V_e) является полностью замороженным, никакое будущее элементы adjust() не могут изменить его, и, таким образом, событие появится во всех будущих версиях выходного потока. Любое событие выходного потока, которое не является ни наполовину замороженным, ни полностью замороженным, называется размороженным (UF). Для краткости элемент стабилизации иногда будет обозначаться ниже как stable().

Логическое представление физического потока (например, либо входного потока, либо выходного потока) представляет логическую сущность потока. Более определенно, каждый физический поток (и каждый префикс физического потока) соответствуют экземпляру логической временной базы данных (TDB), который захватывает сущность физического потока. Экземпляр TDB включает в себя совокупность событий без временного порядка таких событий. В одной реализации каждое событие в свою очередь включает в себя полезную нагрузку и интервал допустимости. Полезная нагрузка (p) соответствует реляционному кортежу, который переносит данные (такие как данные измерений и т.д.). Интервал допустимости представляет промежуток времени, в котором событие является активным и вносит вклад в вывод. Говоря более формально, интервал допустимости определен относительно времени начала (V_s) и времени окончания (V_e), где время окончания может являться заданным конечным временем или открытым параметром (например, +∞). Время начала также может рассматриваться как метка времени события.

Функция отображения преобразовывает элементы в потоках в экземпляры (например, события) экземпляра TDB. Таким образом, функция отображения tdb(S, i) производит экземпляр TDB, соответствующий префиксу потока S[i]. Фиг. 5 показывает пример такого отображения физических потоков в экземпляр TDB. Таким образом, первый физический поток (вход 1) обеспечивает первую временную последовательность элементов, и второй физический поток (вход 2) обеспечивает вторую временную последовательность событий. Элемент "a", a(value, start, end) представляет собой краткую нотацию для описанного выше элемента insert(). Таким образом, элемент "a" добавляет новое событие со значением value в качестве полезной нагрузки и продолжительностью от начала start до конца end. Элемент "m", m(value, start, newEnd) представляет собой краткую нотацию для описанного выше элемента adjust(). Таким образом, элемент "m" изменяет существующее событие с заданным значением value и началом start, чтобы оно имело новое время окончания end. Элемент "f", f(time), представляет собой краткую нотацию для описанного выше элемента stable(). Таким образом, элемент "f" элемент финализирует (например, замораживает для дополнительных модификаций) каждое событие, текущий конец end которого является более ранним, чем время time. Как можно видеть, первый физический поток и второй физический поток физически отличаются, поскольку они имеют разные последовательности элементов. Но эти два входных потока выполняют одну и ту же цель и, таким образом, семантически (логически) эквивалентны. Правая часть фиг. 5 показывает экземпляр TDB с двумя событиями, который логически описывает оба входных потока. Например, первое событие в экземпляре TDB указывает, что полезная нагрузка A существует (или вносит вклад в поток) в течение интервала допустимости, который длится от момента времени 6 до момента времени 12, что является логическим выводом, совместимым с последовательностью элементов в обоих физических потоках. По мере того как прибывают новые физические элементы, соответствующая логическая база TDB может соответствующим образом видоизменяться (например, превращаясь в другую совокупность событий каждый раз, когда добавляется элемент). Следует отметить, что префиксы любых двух физических потоков могут быть не всегда логически эквивалентны, но они являются совместимыми, поскольку они все еще могут стать эквивалентными в будущем.

Принимая во внимание упомянутое выше разъяснение понятий "физический" и "логический", работа и свойства модуля 102 логического слияния теперь могут быть выражены более точно. Модуль 102 логического слияния рассматривает физические входные потоки как логически эквивалентные, что означает, что потоки имеют логические представления TDB, которые в конечном счете будут одинаковыми. Модуль 102 логического слияния производит выходной поток, который логически эквивалентен его входным потокам, что означает, что выходной поток имеет представление TDB, которое в конечном счете будет таким же, как у входных потоков.

Выражаясь более формально, префиксы потоков {I₁[k₁], …, I_n[k_n]} считаются взаимно согласующимися, если существуют такие конечные последовательности E_i и F_i, 1≤i≤n, что E₁:I₁[k₁]:F₁≡…≡E_i:I_i[k_i]:F_i≡…≡E_n:I_n[k_n]:F_n (где нотация A:B представляет конкатенацию A и B). Входные потоки {I₁, …, I_n} являются взаимно согласующимися, если все их конечные префиксы являются взаимно согласующимися. Префикс выходного потока O[j] считается совместимым с префиксом входного потока I[k], если для расширения I[k]:E входного префикса существует расширение O[j]:F выходной последовательности, которая эквивалентна ему. Префикс потока O[j] совместим с взаимно согласующимся множеством префиксов входных потоков I={I₁[k₁], …, I_n[k_n]}, если для любого множества расширений extensions E₁, …, E_n, которые делают I₁[k₁]:E₁, …, I_n[k_n]:E_n эквивалентными, существует расширение O[j]:F выходной последовательности, которая эквивалентна им всем.

Фиг. 6 показывает пример работы модуля 102 логического слияния, показанного на фиг. 1. В этом случае два входных потока (вход 1 и вход 2) могут быть отображены в первый выходной поток (выход 1), или второй выходной поток (выход 2), или третий выходной поток (выход 3). Выходные потоки являются физическими потоками, которые все логически эквивалентны двум входным потокам (это означает, что они имеют такую же базу TDB, как входные потоки). Но выходные потоки производят эту эквивалентность физически по-разному. Более определенно, первый выходной поток (выход 1) представляет агрессивную политику вывода, поскольку он передает каждое изменение из входных потоков, с которыми он встречается. Второй выходной поток (выход 2) представляет консервативную политику, поскольку он задерживает элементы вывода, пока он не принимает гарантию, что элементы являются заключительными. Следовательно, второй выходной поток производит меньше элементов, чем первый выходной поток, но он производит их в более позднее время, чем первый выходной поток. Третий выходной поток (выход 3) представляет посредническую политику между первым выходным потоком и вторым выходным потоком. Таким образом, третий выходной поток выдает первый встречающийся ему элемент с данной полезной нагрузкой и началом, но сохраняет любые модификации, пока не будет подтверждено, что они являются заключительными.

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

Фиг. 7 показывает другой пример работы 102 модуля логического слияния, показанного на фиг. 2. В этом случае модуль 102 логического слияния отображает два входных потока (вход 1, вход 2) в три возможных выходных потока, причем в этом случае и входные, и выходные потоки описаны их базами TDB. Для каждой из баз TDB "последний" параметр в этом примере относится к самому последнему значению V, которое встретилось в элементе stable(). Самый правый столбец представляет статус заморозки каждого элемента, например UF для размороженного, HF для наполовину замороженного и FF для полностью замороженного элемента.

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

Напротив, третий выходной поток не является совместимым с двумя входными потоками по двум причинам. Во-первых, хотя событие (A, 2, 12) соответствует событию во втором входном потоке, оно противоречит информационному содержанию первого входного потока (который определяет, что время окончания будет составлять не менее 14). Поскольку это событие полностью заморожено в третьем выходном потоке, нет последующего потокового элемента, который может его скорректировать. Во-вторых, у третьего выходного потока нет события (B, 3, 10), которое полностью заморожено во входных потоках, но не может быть добавлено к третьему выходному потоку в силу его точки стабилизации.

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

Фиг. 8 показывает процедуру 900, которая обобщает описанную выше работу модуля 102 логического слияния. На этапе 902 модуль 102 логического слияния принимает несколько физически расходящиеся входных потоков из любых соответствующих источников. Как объяснено выше, источники могут соответствовать объектам, которые предоставляют необработанные данные (такие как необработанные данные измерений). В качестве альтернативы, или в дополнение, источники могут соответствовать одному или более операторам, которые выполняют обработку и обеспечивают результирующие выходные потоки. На этапе 904 модуль логического слияния производит выходной поток, который является логически совместимым с каждым из входных потоков. Как описано выше, это означает, выходной поток имеет представление TDB, которое в конечном счете будет таким же, как представления TDB входных потоков.

B. Иллюстративная реализация модуля логического слияния

Фиг. 9 показывает одну реализацию модуля 102 логического слияния, показанного на фиг. 1. Модуль 102 логического слияния, показанный на фиг. 9, реализует алгоритм, выбранный из набора возможных алгоритмов. Каждый алгоритм в свою очередь выполнен с возможностью обрабатывать коллекцию входных потоков, которые подчинены классу ограничений. Таким образом, этот раздел начнется с описания иллюстративных классов ограничений, которые могут влиять на коллекцию входных потоков. В одном случае предполагается, что все элементы коллекции входных потоков подчинены одному и тому же классу ограничений. Однако другие реализации могут до некоторой степени ослабить эту характеристику.

В первом случае (случай R0) входные потоки содержат только элементы insert() и stable(). Другими словами, у входных потоков нет возможности изменить предшествующие элементы во входном потоке. Кроме того, времена V_s в элементах строго возрастают. Таким образом, поток проявляет детерминированный порядок без дублирующих меток времени. Много упрощающих предположений может быть выведено относительно потока, который подчинен ограничениям типа R0. Например, когда время продвинулось до точки t, модуль 102 логического слияния может без риска предположить, что он наблюдал все полезные нагрузки с V_s<t.

Во втором случае (случай R1) входные потоки снова содержат только элементы insert() и stable(). Кроме того, времена V_s являются не уменьшающимися. Кроме того, теперь может быть несколько элементов с одинаковыми временами V_s, но порядок среди элементов с равными временами V_s детерминирован. Например, элементы с равными временами V_s могут быть отсортированы на основе информации идентификатора в полезной нагрузке p.

В третьем случае (случай R2) входные потоки снова содержат только элементы insert() и stable(). Однако в этом случае порядок элементов с одинаковым временем V_s может отличаться среди входных потоков. Кроме того, для любого префикса потока S[i] комбинация полезной нагрузки (p) и времени V_s формирует ключ для определения местоположения соответствующего события в представлении TDB выходного потока. Выражаясь более формально, комбинация (p, V_s) формирует ключ для tdb(S, i). Например, такое свойство может возникнуть, если p включает в себя информацию об идентификаторе и запись, причем никакой источник не обеспечивает более одной записи в период времени. Как будет описано ниже, это ограничение упрощает сопоставление соответствующих событий среди входных потоков.

В четвертом случае (случай R3) входные потоки могут теперь содержать все типы элементов, в том числе элементы adjust(). Кроме того, этот случай не накладывает ограничений на порядок элементов, кроме элементов stable(). Подобно случаю R2, для любого префикса потока S[i] комбинация (p, V_s) формирует ключ для определения местоположения соответствующего элемента в выходном потоке. Выражаясь более формально, комбинация (p, V_s) формирует ключ для tdb(S, i).

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

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

Модуль 902 определения случая представляет функциональные средства, которые анализируют набор входных потоков и определяют его характеристики с целью определения, какие ограничения могут применяться к коллекции входных потоков. Модуль 902 определения случая может сделать это определение по-разному. В одном случае модуль 902 определения случая полагается на информацию, извлеченную во время предварительного анализа среды обработки, в которой используется модуль 102 логического слияния, например, посредством исследования характеристик функциональных средств, которые формирует входные потоки. Этот предварительный анализ может быть выполнен во время компиляции или в любой другой предварительный момент. Например, рассмотрим первый пример, в котором среда обработки включает в себя оператор переупорядочения или очистки, который принимает разупорядоченные входные потоки, буферизует эти потоки и выдает упорядоченные по времени потоки модулю 102 логического слияния. Модуль 902 определения случая может предположить, что входные потоки при таких обстоятельствах включают в себя упорядоченные времена V_s (например, вследствие присутствия описанного выше типа оператора переупорядочения или очистки). К этим входным потокам применяется случай R0.

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

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

На основе определения случая применения (R0, R1 и т.д.) модуль 102 логического слияния может выбрать соответствующий алгоритм для обработки коллекции входных потоков. А именно, для случая R0 модуль 102 логического слияния выбирает алгоритм R0; для случая R1 модуль 102 логического слияния выбирает алгоритм R1 и так далее. Выбор зависящего от контекста алгоритма для обработки ограниченного множества входных потоков может быть полезным для улучшения производительности модуля 102 логического слияния, в связи с этим алгоритм может усилить встроенные предположения, соответствующие применимому случаю. В качестве альтернативы, модуль 102 логического слияния может проявить консервативный подход и использовать алгоритм более общего назначения, такой как алгоритм для случая R3, для обработки коллекций входных потоков, имеющих отличающиеся уровни ограничений (например, множества входных потоков, подчиненных ограничениям R0, R1, R2 или R3).

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

Модуль 906 определения типа элемента идентифицирует тип каждого элемента. В одной иллюстративной реализации один тип элемента представляет собой описанный выше элемент insert(); этот элемент обеспечивает команду передачи новой выходной информации, например, посредством инициирования нового интервала допустимости в метке времени V_s. Другой тип элемента представляет собой описанный выше элемент adjust(); этот элемент корректирует информацию, переданную предыдущим элементом, например, предоставляя новое значение V_e для предыдущего элемента. Другой тип элемента представляет собой описанный выше элемент stable(); этот элемент предоставляет информацию о маркере хода работы, который отмечает время, до которого никакие дальнейшие изменения не могут быть произведены в выходном потоке (например, с использованием элемента insert() или элемента adjust()).

Модуль 908 обработки элементов определяет для каждого элемента, следует ли передавать событие в выходной поток. Например, для элемента insert() модуль 908 обработки элементов может определить, уместно ли добавить событие вставки в выходной поток. Для элемента adjust() модуль 908 обработки элементов может определить, уместно ли добавить элемент коррекции в выходной поток. И для элемента stable() модуль 908 обработки элементов может определить, уместно ли добавить элемент стабилизации в выходной поток. Кроме того, для некоторых алгоритмов некоторые элементы, которые появляются во входных потоках, могут побуждать модуль 908 обработки элементов вносить другие корректировки в выходной поток. Например, для случая алгоритмов R3 и R4 (которые будут описаны ниже) модуль 908 обработки элементов может передать элементы коррекции в выходной поток при определенных обстоятельствах, после приема элемента stable() во входных потоках; эта операция выполняется, чтобы гарантировать логическую совместимость между входными потоками и выходным потоком.

В более общем смысле модуль 908 обработки элементов пытается создать выходной поток, который выражает логическую сущность каждого из входных потоков, например, производя выходной поток, имеющий экземпляр TDB, который соответствует экземплярам TDB входных потоков (когда экземпляры TDB входных потоков считаются эквивалентными). Модуль 908 обработки элементов динамически выполняет этот анализ на основе элементов потоков, которые были приняты до любого заданного момента времени. Этот анализ имеет дело с целым рядом сложностей, в том числе: жесткие ограничения, например, когда элемент определяет конечное значение V_e; открытые ограничения, например, когда элемент определяет открытое значение V_e; и относящиеся к закрытию ограничения, например, когда элемент stable() создает часть выходного потока, не подлежащую дальнейшим изменениям, перед идентифицированным временем V_c. Эти сложности представляют собой две общие проблемы. Во-первых, модуль 908 обработки элементов просят сформировать выходной поток, который непосредственно не противоречит ни одному из ограничений, которые уже были наложены коллекцией входных потоков, например, когда такое противоречие является явным, а не гипотетическим. Во-вторых, в любой данный момент модуль 908 обработки элементов просят выполнить анализ "что если", то есть, посредством формирования выходного потока, который принимает во внимание элементы потоков, которые предположительно могли бы быть приняты в будущем, ввиду ограничений (и свобод), соответствующих элементам потоков, которые до сих пор были приняты. (Это справедливо потому, что общая цель модуля 102 логического слияния состоит в том, чтобы сформировать выходной поток, имеющий экземпляр TDB, который в конечном счете станет эквивалентным экземплярам TDB входных потоков.)

Модуль 910 управления состоянием хранит информацию состояния в одной или более структурах данных в пределах хранилища 912 данных. Информация состояния захватывает информацию, имеющую отношение к входным потокам, и в некоторых случаях информацию, которая была передана в выходной поток. Более определенно, разные алгоритмы поддерживают разные типы информации состояния в зависимости от ограничений, которые применяются к входным потокам. Например, фиг. 12 обобщает структуры данных, которые могут использоваться алгоритмами R0, R1, R2 и R3. Как можно видеть, по мере того как ограничения удаляются из входного потока, модуль 910 управления состоянием увеличивает количество информации состояния, которую он хранит. Структуры данных, показанные на фиг. 12, будут описаны более подробно в контексте объяснения алгоритмов для случаев R0-R4.

Фиг. 10 показывает процедуру 1000, которая обобщает описанную выше работу модуля 902 определения случая. На этапе 1002 модуль 902 определения случая анализирует входные потоки, чтобы определить их характеристики, в частности определить, применяются ли к входным потокам одно или более ограничений. На этапе 1004 модуль 902 определения случая выбирает случай, соответствующий ограничениям, оцененным на этапе 1202. На этапе 1006 модуль 902 определения случая дает модулю 102 логического слияния команду вызывать конкретный алгоритм для обработки случая, определенного на этапе 1004.

Фиг. 11 показывает процедуру 1100, которая обобщает работу модуля 102 логического слияния, изложенную на фиг. 9, относительно конкретного элемента. На этапе 1102 модуль 102 логического слияния определяет тип рассматриваемого элемента (например, элемент insert(), элемент adjust() или элемент stable()). На этапе 1104 модуль 102 логического слияния определяет, какой элемент (элементы) должен быть передан в выходной поток в ответ на рассматриваемый элемент. Например, модуль 102 логического слияния может: (a) воздержаться от передачи какой-либо информации в выходной поток; (b) передать новую выходную информацию, например, с использованием элемента insert(); (c) скорректировать предыдущую выходную информацию, например, с использованием элемента adjust(); или (d) предоставляют информацию маркера хода работы (который частично или полностью замораживает некоторые события в выходном потоке), например, с использованием элемента stable().

Фиг. 13-16 описывают иллюстративные алгоритмы для соответствующей обработки случаев R0, R1, R2 и R4. Эти фигуры будут разъяснены со ссылкой на соответствующие структуры данных, показанные на фиг. 12. Кроме того, эти алгоритмы описаны относительно обработки двух входных потоков; но алгоритмы могут быть применены к сценарию, в котором имеется более двух входных потоков.

Алгоритм логического слияния для случая R0

Для случая R0 входные потоки имеют элементы со строгим возрастанием значений V_s, без элементов adjust(). Следовательно, нет дублирующихся меток времени. В этом случае модуль 910 управления состоянием поддерживает только два элемента информации. Во-первых, модуль 910 управления состоянием хранит максимальное значение V_s (MaxV_s), которое встретилось во входных потоках. Во-вторых, модуль 910 управления состоянием хранит максимальную метку времени стабилизации (MaxStable), замеченную среди всех входных потоков.

Фиг. 13 показывает алгоритм для обработки случая R0. На этапе 1302 модуль 102 логического слияния инициализирует значения MaxV_s и MaxStable.

На этапе 1304 модуль 102 логического слияния обрабатывает элемент insert(), если рассматриваемый элемент фактически является элементом insert(). Таким образом, модуль 102 логического слияния передает элемент insert() в выходной поток, если значение V_s этого элемента больше преобладающего значения MaxV_s. Далее, модуль 102 логического слияния обновляет значение MaxVs, чтобы оно соответствовало значению V_s элемента. Иначе (если V_s не больше, чем MaxV_s), модуль 102 логического слияния не передает этот элемент в выходной поток. Следует отметить, что символ "s" обозначает идентификатор (например, целое число), который соответствует конкретному входному потоку.

На этапе 1306 модуль 102 логического слияния обрабатывает элемент stable(), если рассматриваемый элемент фактически является элементом stable(). Таким образом, модуль 102 логического слияния выдает элемент stable(), если его метка времени t (также называемая V_c в примерах выше) больше, чем MaxStable.

Алгоритм логического слияния для случая R1

Для случая R1 входные потоки имеют элементы с не уменьшающимися значениями V_s, без элементов adjust(). При этом входные потоки могут иметь дублирующиеся метки времени V_s, но такие элементы представлены в детерминированном порядке (например, отсортированы по полю в полезной нагрузке). В этом случае модуль 910 управления состоянием, как и раньше, поддерживает значения MaxVs и MaxStable (для случая R0). Кроме того, модуль 910 управления состоянием поддерживает массив со значением счетчика для каждого входного потока. Значение счетчика для конкретного входного потока отражает количество элементов в этом потоке, в которых V_s=MaxVs.

Фиг. 14 показывает алгоритм для обработки случая R1. На этапе 1402 модуль 102 логического слияния инициализирует значения MaxVs и MaxStable. Модуль 102 логического слияния также инициализирует значения массива счетчиков.

На этапе 1404 модуль 102 логического слияния обрабатывает элемент insert(), если рассматриваемый элемент фактически является элементом insert(). Таким образом, модуль 102 логического слияния обнуляет массив значений счетчиков, если значение V_s элемента insert() больше текущего значения MaxV_s, и затем устанавливает MaxV_s равным V_s. В строке 8 модуль 102 логического слияния определяет, увеличивает ли элемент insert() в потоке s счетчик для s за пределы максимального значения счётчиков среди всех потоков; если это так, модуль 102 логического слияния передает элемент insert() в выходной поток. Другими словами, модуль 102 логического слияния выдает элемент вставки, если элемент вставки представляет новый элемент детерминировано упорядоченной группы возможных элементов, которые имеют одинаковое значение V_s. Например, предположим, что каждый поток включает в себя три элемента insert() для каждого значения V_s (например, соответствующие трем разным идентификаторам датчика), представленные в фиксированном порядке. Далее предположим, что в конкретной точке анализа второй элемент вставки был принят в конкретном потоке s. Модуль 102 логического слияния выдаст элемент insert(), если никакой другой поток уже не принял свой соответствующий второй элемент для этого значения V_s.

На этапе 1406 модуль 102 логического слияния обрабатывает элемент stable(), если рассматриваемый элемент фактически является элементом stable(). Модуль 102 логического слияния обрабатывает элемент stable() таким же образом, как алгоритм R0.

Алгоритм логического слияния для случая R2

Для случая R2 входные потоки имеют элементы с не уменьшающимися значениями V_s, без элементов adjust(). Кроме того, входные потоки могут иметь дублирующиеся метки времени V_s, и для этого случая такие элементы не обязательно должны быть представлены в детерминированном порядке. В этом случае модуль 910 управления состоянием, как и раньше, поддерживает значения MaxV_s и MaxStable. Кроме того, модуль 910 управления состоянием поддерживает таблицу поиска, имеющую полезную нагрузку (p) в качестве ключа. Каждый элемент в таблице для конкретного ключа (p) полезной нагрузки хранит элементы с V_s=MaxV_s. См. фиг. 12 для иллюстрации этой структуры данных.

Фиг. 15 показывает алгоритм для обработки случая R2. На этапе 1502 модуль 102 логического слияния инициализирует значения MaxV_s и MaxStable. Модуль 102 логического слияния также создает таблицу поиска.

На этапе 1504 модуль 102 логического слияния начинает обрабатывать элемент insert(), если рассматриваемый элемент фактически является элементом insert(). Таким образом, модуль 102 логического слияния сначала сверяется с таблицей поиска (с использованием полезной нагрузки p, заданной в элементе, в качестве ключа). Если таблица показывает, что конкретная комбинация полезной нагрузки и V_s уже существует (поскольку она была принята от некоторого другого потока), модуль 102 логического слияния не выполняет дополнительного действия. Иначе модуль 102 логического слияния обновляет таблицу поиска и выдает элемент вставки.

На этапе 1506 модуль 102 логического слияния очищает таблицу поиска, если он встречает элементом, который увеличивает V_s за пределы MaxV_s. Модуль 102 логического слияния также обновляет значение MaxV_s, чтобы оно соответствовало значению V_s.

На этапе 1508 модуль 102 логического слияния обрабатывает элемент stable(), если рассматриваемый элемент фактически является элементом stable(). Модуль 102 логического слияния обрабатывает элемент stable() тем же образом, как и прежде.

Алгоритм логического слияния для случая R3

Для случая R3 элементы во входных потоках теперь могут включать в себя любой тип элементов, в том числе элементы insert(), элементы adjust() и элементы stable(). Кроме того, элементы могут быть представлены в любом временном порядке. В качестве остающегося ограничения алгоритм для случая R3 предполагает, что комбинация значения V_s и полезной нагрузки (p) может служить ключом для определения соответствующего элемента в выходном потоке. Более определенно, как показано на фиг. 12, модуль 910 управления состоянием может поддерживать основную структуру данных, которая индексирует записи посредством ключа (V_s, Payload). Каждая запись состоит из события (e) (например, и Payload) и маленькой таблицы поиска, которая содержит для каждого входного потока s, текущее значение V_e для этого потока, индексированное посредством ключа s. Таблица поиска также содержит запись (OutV_e) с ключом α, которая обеспечивает вывод V_e (соответствующего выходному событию, которое было передано в выходной поток).

Фиг. 16 показывает алгоритм для обработки случая R3. На этапе 1602 модуль 102 логического слияния инициализирует значения MaxV_s и MaxStable. Модуль 102 логического слияния также создает основную структуру данных. В одном случае модуль 102 логического слияния может создать красно-черное дерево для реализации основной структуры данных.

На этапе 1604 модуль 102 логического слияния начинает обрабатывать вставку элемент insert(), если рассматриваемый элемент фактически является элементом insert(). Таким образом, модуль 102 логического слияния выполняет поиск в основной структуре данных, чтобы найти запись с такой же комбинацией (V_s, Payload), соответствующей рассматриваемому элементу insert(). Если такая запись не существует в основной структуре данных, модуль 102 логического слияния добавляет запись и производит вывод. В таблице поиска, соответствующей записи (V_s, Payload), модуль 102 логического слияния добавляет запись V_e для потока s, а также для вывода, который был передан в выходной поток. Однако модуль 102 логического слияния не выполняет эту операцию обновления, если определено, что V_s меньше, чем MaxStable (как оценено в строке 6); это указывает, что соответствующая запись ранее существовала в основной структуре данных, но с тех пор была удалена.

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

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

На этапе 1610 модуль 102 логического слияния обрабатывает элемент stable(), если рассматриваемый элемент фактически является элементом stable(). Как обозначено в строке 18, модуль 102 логического слияния выполняет возврат, не выполняя действия, если метка времени t не больше, чем MaxStable. Если это условие соблюдено, модуль 102 логического слияния сначала находит записи в основной структуре данных, которые станут наполовину замороженными в результате передачи элемента stable(). Таким образом, это записи, значения V_s у которых меньше, чем метка времени элемента stable(). Для каждой такой записи модуль 102 логического слияния определяет экземпляры, в которых имеется несоответствие между вводом и выводом, когда произойдет нарушение совместимости, если элемент e stable() будет передан в выходной поток.

Более определенно, в одной реализации модуль 102 логического слияния рассматривает три обстоятельства, в которых произойдут нарушения совместимости. В первом случае нет входного события для комбинации (V_s, Payload) в потоке s, но имеется выходное событие (вследствие вклада некоторого другого входного потока). Во втором случае в настоящий момент выходное событие станет полностью замороженным вследствие передачи элемента e stable(), но соответствующий ввод не полностью заморожен. В третьем случае входное событие станет полностью замороженным, но текущий вывод не полностью заморожен. Во всех этих случаях в соответствии с одной возможной политикой модуль 102 логического слияния корректирует вывод таким образом, чтобы он соответствовал вводу (что происходит в строках 24-27). Он выполняет эту операцию посредством передачи соответствующих элементов adjust() в выходной поток и соответствующего обновления основной структуры данных.

Далее, в строках 28-29, если ввод становится полностью замороженным, модуль 102 логического слияния может удалить соответствующую запись из основной структуры данных. Наконец, в строках 30-31, модуль логического слияния обновляет значение MaxStable и выдает элемент stable().

В итоге, этап 1610 включает в себя изменение выходного потока, чтобы гарантировать, что передача рассматриваемого элемента stable() не вызовет будущие логические несовместимости между входными потоками и выходным потоком. Модуль 102 логического слияния тогда может без риска выдать элемент stable().

Алгоритм логического слияния для случая R4

Потоки данных для случая R4 имеют все те же самые свободы случая R3. Но теперь несколько элементов в потоке данных могут иметь одинаковые комбинации (V_s, Payload) с разными значениями V_e. Кроме того, входной поток может включать в себя дублирующиеся записи. Чтобы обратиться к этой ситуации, основная структура данных для случая R3 может быть изменена для учета наличия разных значений V_e. Рассмотрим таблицу поиска, соответствующую конкретной записи (payload, V_s) в основной структуре данных. Единственное значение V_e для элемента (как предусмотрено в случае R3) теперь заменено небольшой структурой данных V_e, которая индексирована на основе уникальных значений V_e, которые встретились, наряду с количеством этих комбинаций (V_s, Payload) в этом входном потоке.

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

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

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

В соответствии с третьим соображением для конкретной комбинации (V_s, Payload), если некоторое V_e становится полностью замороженным в результате входящего элемента stable(), модуль 102 логического слияния пытается гарантировать, что выходной поток содержит такое же количество событий с этой комбинацией (Vs, Payload, V_e), прежде чем передавать элемент stable(). Если соответствующий V_s был уже наполовину заморожен, этот процесс просто включает в себя коррекцию V_e у событий, выданных ранее с той же самой комбинацией (V_s, Payload).

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

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

Например, рассмотрим политику, принятую модулем 102 логического слияния при обработке элементов adjust() в алгоритме R3 (например, на этапе 1608). Модуль 102 логического слияния выполнен с возможностью никогда не выдавать события adjust(). Модуль 102 логического слияния гарантирует, что выходной поток является совместимым с входными потоками, только когда он обрабатывает элемент stable().

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

Затем рассмотрим обработку, которую модуль 102 логического слияния выполняет в алгоритме R3 в строке 10. В этот момент при обработке первого элемента insert() для конкретного V_s модуль 102 логического слияния сразу передает его в выходной поток. Эта политика гарантирует, что вывод является максимально отзывчивым. Но эта политика может быть модифицирована различным образом, чтобы удовлетворить другим целям политики.

Например, в другом случае модуль 102 логического слияния может выдавать элемент insert(), только если он произведен входным потоком с максимальной меткой времени элемента stable() или имеющим максимальное количество размороженных элементов. В другом случае модуль 102 логического слияния может воздержаться от отправки элемента в качестве вывода, пока он не становится наполовину замороженным на некотором входном потоке. Эта политика гарантирует, что модуль 102 логического слияния никогда полностью не удаляет элемент, который помещен в вывод, за счет более высокой задержки. В другом случае модуль 102 логического слияния может принимать гибридный выбор, ожидая, пока некоторая часть входных потоков не произведет элемент для каждого V_s, прежде чем отправить элемент на вывод. Если входные потоки физически отличаются, эта политика может уменьшить вероятность создания ложного вывода, который позже требует полного удаления.

В качестве заключительной темы в этом разделе следует отметить, что описанные выше алгоритмы являются устойчивыми к пропускам элементов во входных потоках, например, вызванным повреждением входных потоков или любым другим явлением. Например, алгоритмы для случаев R0, R1 и R2 могут выдавать элементы, которые отсутствуют в некотором потоке s, если некоторый другой поток доставляет недостающие элементы модулю 102 логического слияния, прежде чем поток s доставит элемент с более высоким V_s. Алгоритмы для случаев R3 и R4 выдают элемент e, если поток, который увеличивает MaxStable за пределы V_s (для того элемента) производит элемент s.

C. Иллюстративные применения модуля логического слияния

Как отмечено в разделе A, различные среды могут использовать модуль 102 логического слияния для различных применений. Этот раздел излагает неисчерпывающий набор иллюстративных применений.

Рассмотрим фиг. 17. Здесь среда 1702 любого типа включает в себя один или более модулей логического слияния, упоминаемые для простоты как один модуль 1704 логического слияния. Модуль 1704 логического слияния принимает несколько входных потоков от нескольких соответствующих блоков (например, блоков 1706, 1708 и 1710). В одном случае блоки (1706, 1708, 1710) могут соответствовать вычислительным машинам (или отдельным процессам в пределах одной машины). Модуль 1704 логического слияния затем производит выходной поток, который является логически совместимым с каждым из входных потоков.

Высокая доступность. В первом применении среда 1702 может использовать модуль 1704 логического слияния, чтобы гарантировать высокую доступность. Рассмотрим, например, случай, в котором непрерывный запрос полагается на длинное окно обработки для получения выходного потока. Поэтому будет соответственно требоваться много времени, чтобы перезапустить такой непрерывный запрос при его отказе. Чтобы решить эту проблему, среда 1702 может установить избыточные копии непрерывного запроса на различных блоках (1706, 1708, 1710), каждый из которых обеспечивает входной поток для модуля 1704 логического слияния. Среда 1702 может тогда применить модуль 1704 логического слияния, чтобы получать из него результаты, какой бы входной поток ни перестал работать в конкретный момент вовремя, даже в случае, когда вплоть до n-1 из n входных потоков перестали работать. Кроме того, среда 1702 может использовать модуль 1704 логического слияния 1704, чтобы включить в состав новый входной поток, если непрерывный запрос должным образом "раскручен" после перезапуска или недавнего ввода в строй (способом, описанным ниже).

В другом применении блоки (1706, 1708, 1710) могут представлять машины, которые расположены удаленно от среды 1702, доставляющие свои потоки через сеть любого типа (такую как Интернет). В этом случае среда 1702 может положиться на модуль 1704 логического слияния, чтобы уменьшить эффекты сетевой перегрузки, которая может вызвать задержки или другое ухудшение в одном или более входных потоках. Как в вышеупомянутом случае, модуль 1704 логического слияния может выполнить эту задачу, выборочно вытягивая элементы из одного или более входных потоков, которые проявляют удовлетворительную производительность.

Быстрая доступность. В другом применении среда 1702 может использовать модуль 1704 логического слияния, чтобы гарантировать быструю доступность, то есть, обеспечивая возможность для потребителя получить выходные результаты как можно скорее. Чтобы достигнуть этой цели, среда 1702 может установить разные (но семантически эквивалентные) планы выполнения запросов на блоках (1706, 1708, 1710). Среда 1702 может тогда использовать модуль 1704 логического слияния, чтобы вытягивать результаты из какого угодно блока (или блоков), который обеспечивает самые своевременные результаты в любое определенное время. Одни планы выполнения запросов могут проявлять более удовлетворительную производительность, чем другие планы выполнения запросов, по бесчисленным зависящим от среды причинам. Например, конкретный план выполнения запросов может лучше подойти для обработки конкретного типа набора данных по сравнению с другим планом выполнения запросов. В качестве альтернативы, или вместо этого, блок, который выполняет конкретный план выполнения запросов, может обеспечить лучшую производительность, чем другие блоки, например, вследствие конкуренции за ресурсы и/или других задержек обработки, которые влияют на блоки по-разному.

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

Ускорение плана. Различные факторы могут заставить один план выполнения запросов отставать от других планов выполнения запросов. Если это происходит, среда 1702 не может выполнить эффективное использование выходного потока, сформированного этим отстающим планом выполнения запросов, что делает его работу фактически бесполезной. Чтобы обратиться к этой ситуации среда 1702 может включать в себя модуль 1712 обратной связи, который помогает обновить отстающий план выполнения запросов относительно других планов выполнения запросов. При работе модуль 1704 логического слияния 1704 может уведомлять модуль 1712 обратной связи о том, что один или более выходных потоков не обеспечивают полезных результатов, например, поскольку они отстают от результатов других потоков и поэтому предоставляют устаревшую информацию, которая уже была предоставлена другими потоками. В ответ модуль 1712 обратной связи может отправить информацию обратной связи блоку (блокам), который исполняет ненадлежащим образом выполняющийся план (планы). В одном случае информация обратной связи может сообщить блоку (блокам), что операции до назначенного времени t не нужны модулю 1704 логического слияния. В дополнение, или в качестве альтернативы, модуль 1712 обратной связи может передать информацию относительно состояния более удовлетворительно выполняющихся планов. При приеме информации обратной связи блоки могут выполнить различные виды корректирующих действий, такие как очистка бесполезной (устаревшей) информации состояния, включение в состав более своевременной информации состояния, отказ от бесполезных операций по обработке, переход вперед к более актуальным операциям по обработке и так далее.

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

Быстрый старт запроса. В другом применении среда 1702 может использовать модуль 102 логического слияния, чтобы обеспечить возможность введения нового непрерывного запроса, который производит новый входной поток. Например, на фиг. 17 предположим, что введен новый блок 1714 для выполнения нового экземпляра непрерывного запроса. Как указано выше, некоторые непрерывные запросы работают, накапливая информацию состояния за относительно длительный период времени, прежде чем они смогут произвести приемлемые результаты для потребления. Чтобы решить эту проблему, среда 1702 может «дать затравку» («seed»)состояния запроса вновь введенного непрерывного запроса, например, на основе информации контрольной точки, сохраненной на диске или обеспеченной другой выполняющейся копией запроса. Среда 1702 может тогда применить модуль 1704 логического слияния, чтобы легко объединить недавно введенный поток с другими текущими потоками, делая вывод недавно введенного потока доступным для потребления как можно скорее.

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

В более широком смысле, различные применения, изложенные выше, включают в себя введение или удаление потоков. Модуль 1704 логического слияния может включать в себя соответствующий механизм для обеспечения возможности этих задач. Например, когда поток удаляется как ввод в модуль 1704 логического слияния, модуль логического слияния может пометить поток как удаленный. В итоге, описанные выше алгоритмы (для случаев R0-R4) больше не будут рассматривать поток, который был удален.

Для соединения присоединяющийся поток обеспечивает метку времени t, которая гарантирует производство приемлемого вывода для каждой точки, начинающейся от t (то есть, каждое событие в выводе с V_e≥t). Модуль 1704 логического слияния может пометить поток как "присоединенный", как только MaxStable достигает t, поскольку, начиная с этой точки, модуль 1704 логического слияния может допустить одновременный отказ или удаление всех других потоков.

Фиг. 18 показывает процедуру 1800, которая обобщает выбранные применения, описанные выше. На этапе 1802 модуль 1704 логического слияния принимает два или более потоков из любых соответствующих источников. На этапе 1804 модуль 1704 логического слияния выполняет одну или более зависящих от применения операций над входными потоками. Такие применения могут включать в себя выбор среди входных потоков, чтобы гарантировать высокую доступность и/или быструю доступность, обеспечение возможности введения или удаления потоков, уведомление модуля 1712 обратной связи о наличии нестандартно ненадлежащим образом выполняющегося потока (при котором модуль 1712 обратной связи может отправить информацию обратной связи соответствующему источнику) и так далее.

D. Иллюстративные вычислительные функциональные средства

Фиг. 19 показывает иллюстративные вычислительные функциональные средства 1900, которые могут использоваться для реализации любого аспекта описанных выше функций. Например, вычислительные функциональные средства 1900 могут использоваться для реализации любого аспекта модуля 102 логического слияния, показанного на фиг. 1. В одном случае вычислительные функциональные средства 1900 могут соответствовать любому типу вычислительного устройства, которое включает в себя одно или более устройств обработки. Вычислительное устройство дополнительно может быть элементом кластера таких вычислительных устройств.

Вычислительные функциональные средства 1900 могут включать в себя энергозависимую и энергонезависимую память, такую как оперативное запоминающее устройство (RAM) 1902 и постоянное запоминающее устройство (ROM) 1904, а также одно или более устройств 1906 обработки (например, один или более центральных процессоров (CPU и/или один или более графических процессоров (GPU) и т.д.). Вычислительные функциональные средства 1900 также дополнительно включают в себя различные устройства 1908 для работы с носителями, такими как модуль жесткого диска, модуль оптического диска и т.д. Вычислительные функциональные средства 1900 могут выполнять различные операции, идентифицированные выше, когда устройство (устройства) 1906 обработки исполняет команды, которые хранятся в памяти (например, в оперативном запоминающем устройстве 1902, в постоянном запоминающем устройстве 1904 или в другом месте).

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

Вычислительные функциональные средства 1900 также включают в себя модуль 1912 ввода/вывода для приема различного ввода (через входные модули 1914) и для обеспечения различного вывода (через выходные модули). Один конкретный выходной механизм может включать в себя модуль 1916 представления и соответствующий графический пользовательский интерфейс (GUI) 1918. Вычислительные функциональные средства 1900 также могут включать в себя один или более сетевых интерфейсов 1920 для обмена данными с другими устройствами через один или более каналов 1922 связи. Одна или более шин 1924 связи соединяет вместе описанные выше компоненты с возможностью взаимодействия.

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

В качестве альтернативы, или в дополнение, любая из функций, описанных в разделах A-C, может быть выполнена по меньшей мере частично одним или более аппаратными логическими компонентами. Например, но без ограничения, иллюстративные типы аппаратных логических схем, которые могут использоваться, включают в себя программируемые пользователем вентильные матрицы (FGPA), специализированные интегральные схемы (ASIC), специализированные стандартные продукты (ASSP), "системы на микросхеме" (SOC), сложные программируемые логические интегральные схемы (CPLD) и т.д.

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

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

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

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

принимают множество физически расходящихся входных потоков из соответствующих источников;

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

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

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

при этом выходное действие выбирается среди следующих действий:

обеспечение нулевого вклада в выходной поток,

обеспечение новой выходной информации в выходной поток,

корректировка предыдущей выходной информации в выходном потоке и

предоставление информации маркера хода работы в выходной поток; и

корректируют состояние, соответствующее модулю логического слияния.

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

3. Способ по п. 2, в котором модуль логического слияния представляет собой оператор, комбинируемый с одним или более другими операторами.

4. Способ по п. 1, дополнительно содержащий этапы, на которых:

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

выбирают случай, ассоциированный с этими одним или более ограничениями; и

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

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

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

7. Способ по п. 6, в котором упомянутые несколько соответственных блоков исполняют непрерывный запрос с использованием разных соответственных планов выполнения запросов.

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

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

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

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

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

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

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

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

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

обеспечение нулевого вклада в выходной поток,

обеспечение новой выходной информации в выходной поток,

корректировка предыдущей выходной информации в выходном потоке и

предоставление информации маркера хода работы в выходной поток; и

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

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

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

15. Компьютерное устройство, выполненное с возможностью объединения потоков данных, при этом компьютерное устройство содержит:

процессор; и

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

принимать множество физически расходящихся входных потоков из соответствующих источников;

идентифицировать множество элементов в данном множестве входных потоков;

определять выходное действие, которое должно быть предпринято в ответ на каждый идентифицированный элемент;

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

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

тип 'элемент вставки', которым добавляется новая выходная информация в выходной поток,

тип 'элемент коррекции', которым корректируется предыдущая выходная информация в выходном потоке, и

тип 'элемент маркера хода работы', которым задается время, до которого не разрешены никакие дополнительные модификации; и

корректировать состояние, соответствующее модулю логического слияния.

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

(a) элементы потока, разупорядоченные во времени;

(b) правки, внесенные в отношении предшествующих элементов потока; и

(c) отсутствующие элементы потока.

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