Эффективное логическое слияние физически расходящихся потоков

Эффективное логическое слияние физически расходящихся потоков

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

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

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

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

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

Фиг. 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) формирует ключ для определения местоположения соответствующего элемента в выходном потоке. Выра