CAMPO DE APLICAÇÃO

Esta invenção se aplica no campo dos processamentos de fluxo de dados em tempo real.

A presente invenção descreve um método capaz de interpretar consultas definidas pelo usuário, traduzi-las em um modelo de autómatos para processamento de fluxo de dados, planejar a distribuição da computação entre os nós de um sistema distribuído, identificar computações com alto potencial de consumo de memória, alocar estruturas de dados

apropriadas para cada computação, alocar o montante mínimo de memória necessária para atender a margem de erro especificada, distribuir a computação entre os nós ativos de um sistema distribuído e sincronizar os resultados parciais a cada momento definido e liberar o resultado final.

FUNDAMENTOS DA INVENÇÃO

Devido à popularidade dos dispositivos móveis, bem como a queda nos custos de armazenamento em meios digitais, que tornam os mesmos mais acessíveis, a quantidade de dados gerados ao redor do mundo aumentou de maneira exponencial.

Mesmo com a conhecida popularidade dos dispositivos móveis, podem-se citar diversos outros grandes geradores de dados, como sensores inteligentes que captam informações sobre algum ambiente determinado e são capazes de realizar algum tipo de decisão baseada nos dados de entrada ou operações no mercado financeiro, onde fórmulas e algoritmos matemáticos são utilizados para definir qual ativo pode se encaixar melhor no modelo proposto, detectando diversas variáveis necessárias e movimentando-se como o previsto. Também podemos citar medições de redes de computadores, registros telefónicos, páginas visitadas da Web, entre muitos outros. Tendo em vista a grande quantidade de dados gerados pelas mais variadas fontes, métodos para um melhor processamento dos mesmos se fazem necessários.

A utilização da análise de dados em tempo real é de bastante destaque para operações que necessitem de agilidade, autonomia, inovação, bem como o cuidado com as informações. A necessidade de se obter informações a partir de grandes quantidades de dados que são gerados com grande velocidade exigem estratégias computacionais adequadas. Uma plataforma de análise de dados em tempo real possui capacidade de identificar padrões nas operações em relação a certos fatores, como por exemplo, o tempo de espera em uma transação, número de compradores de um determinado produto, bem como alertar sobre uma anomalia para ser corrigida o mais rápido possível.

Essa análise de dados em tempo real permite, por exemplo, um melhor entendimento da interação de usuário, identificação de oportunidades, bem como o entendimento do comportamento da operação em tempo real, garantindo uma melhora imediata. Além disso, é possível monitorar e corrigir desvios nos processos operacionais, prever situações

indesejadas, aumentando assim, a segurança da operação.

ESTADO DA TÉCNICA

O documento americano US 20110314019 descreve um método de processamento de fluxo de dados, onde o mecanismo de consulta ocorre através da divisão em subconsulta, que é executada em pelo menos um nó. A configuração de cada nó, onde uma subconsulta é executada, compreende receber, periodicamente, os dados sobre a utilização de CPU e de memória em cada nó de todos os nós em que a consulta está sendo executada. Ainda, ocorre uma comparação dos dados de utilização através dos nós e, se a comparação excede um limite estabelecido, o nó reconfigura a partição de dados, bem como seleciona nós livres para receber a carga de outros nós. No documento WO 2013153027 é descrito um sistema de processamento de fluxo de dados contínuo, onde os nós do sistema distribuído são configurados para executar funções de reduce e produzir um estado na memória local do referido nó. O referido sistema realiza o processamento de dados através de uma fila de dados, que é executada

automaticamente quando não há dados de entrada disponíveis no respectivo nó e, sob a forma de dados da fila, utiliza os referidos estados de saída de cada nó, como entradas para as operações de reduce a serem realizadas pelos nós subsequentes. Os nós desse sistema compreendem um disco locai e memória locai para armazenamento e/ou recuperação.

SUMARIO DA INVENÇÃO

A presente invenção descreve um método capaz de (i) interpretar consultas definidas peio usuário, (ii) traduzi-las em um modelo de autómatos para processamento de fluxo de dados, (iii) planejar a distribuição da computação entre os nós do sistema distribuído (cluster), (iv) identificar computações com alto potencial de consumo de memória e, quando identificadas, (v) alocar estruturas de dados apropriadas para cada computação, (vi) alocar o montante de memória necessária para manter a margem de erro configurada, (vii) distribuir a computação entre os nós ativos de um sistema distribuído, (viii) sincronizar os resultados parciais a cada momento definido e (ix) liberar o resultado final.

O método aqui descrito representa uma mudança em relação aos métodos convencionais, pois identifica operações com alto potencial de consumo de memória e aplica estruturas de dados probabilísticas para manter o consumo de memória reduzido e controlado.

BREVE DESCRIÇÃO DAS FIGURAS

A invenção poderá ser mais bem compreendida através da breve descrição das figuras a seguir: A Figura 1 representa um diagrama ilustrativo do método para

processamento de fluxo de dados distribuído com otimização de consumo de memória.

A Figura 2 representa um diagrama ilustrativo da distribuição da computação entre nós do sistema distribuído e o uso de estruturas probabilísticas para otimização do consumo de memória

DESCRIÇÃO DETALHADA DA INVENÇÃO

A presente invenção descreve, conforme ilustrado na Figura 1 , um método capaz de: (i) interpretar consultas definidas pelo usuário, ou seja, respeitando a sintaxe de uma linguagem especificamente criada para a expressão de condições lógicas e temporais, o usuário poderá escrever livremente consultas que serão interpretadas para processamento, (ii) traduzi-la em um modelo de autómatos para processamento de fluxo de dados, (iii) planejar a distribuição da computação entre os nós do sistema distribuído, ou seja, criar o plano de execução de operações em cada nó, bem como a definição do nó que ficará responsável pela sincronização e obtenção de resultados, (iv) identificar computações com alto potencial de consumo de memória e, quando identificadas, (v) alocar estruturas de dados apropriadas para cada computação, (vi) alocar o montante de memória necessária para manter a margem de erro configurada, (vii) distribuir a computação entre os nós ativos de um sistema distribuído, ou seja, alocar para cada nó o processamento que precisará ser realizado localmente, (viii) sincronizar os resultados parciais a cada momento definido e (ix) liberar o resultado final, ou seja, enviar o resultado obtido a cada momento definido para a saída do método, podendo assim ser consumida e utilizada na prática.

No referido método, para uma melhor identificação de computações com alto potencial de consumo de memória, foram definidas três operações matemáticas que estão mapeadas para tratamento. São elas: a contagem de elementos únicos, o cálculo de percentil e o cálculo de mediana. Para cada nó do referido método que está envolvido no processamento de dados distribuído, é atribuída uma destas três operações e deve ativar seu mecanismo de controle.

Um nó do referido sistema pode realizar uma ou mais operações de qualquer tipo, a qualquer momento, de acordo com a consulta ou as expressões realizadas pelo usuário,

A consulta realizada pelo usuário pode gerar um ou mais cálculos de qualquer tipo a ser executado pelos nós do referido sistema.

Se em um nó no referido método, o número de elementos no conjunto gerenciado for acima de um limite pré-determinado, por exemplo, em torno de 1000 (mil) elementos, o referido nó deve abandonar o método tradicional e ativar uma estrutura de dados probabilística.

Para a operação de contagem de elementos únicos é utilizada as estruturas de dados probabilísticas HyperLogLog e Hashset. Já a estrutura Count-min Sketch é utilizada para o cálculo de percentil e para o cálculo de mediana.

A cada uma das operações matemáticas descritas anteriormente, com alto potencial de consumo de memória, é atribuída uma estrutura de dados probabilística pertinente.

As definições das estruturas de dados probabilísticas HyperLogLog, Hashset e Count-min Sketch estão descritas abaixo:

O HyperLogLog é um algoritmo criado para resolver o problema de contagem distinta de elementos. Seu papel é conseguir estimar de forma probabilística a cardinalidade de elementos em um multi-conjunto. Para tal, é feito o uso de uma função que codifica os elementos originais em números randômicos uniformemente distribuídos. Usando o tamanho do maior prefixo binário composto inteiramente de zeros entre todos os números observados é possível estimar a quantidade de elementos distintos.

Já a estrutura de dados probabilística Hashset aumenta o desempenho sem comprometer a correção do resultado final da operação, enquanto que a estrutura de dados probabilística HyperLogLog também aumenta o desempenho, porém aceitando um grau controlado de erro.

O Count-min Sketch é uma estrutura de dados probabilística que é capaz de calcular a frequência dos elementos em um multi-conjunto. É feito o uso de funções que codificam elementos originais em colunas de uma matriz. Quando um mesmo elemento é codificado novamente é realizado o incremento nas células da matriz em que ele impacta. Usando este mecanismo é possível estimar a frequência dos elementos no multi- conjunto.

Uma margem de erro é previamente configurada para o referido método e para que essa margem de erro seja tolerada, o referido método irá alocar o mínimo de espaço em memória possível para cada estrutura de dados. No presente método aqui descrito, ilustrado pela Figura 2, uma consulta é criada pelo usuário final e faz uso da função dcount - contagem de elementos distintos - que possui potencial de alto consumo de memória (1). A consulta é interpretada e enviada para um dos nós do sistema distribuído (2). Este nó irá distribuir a computação entre todos os nós ativos no sistema distribuído, ficando responsável também pela sincronização dos resultados (3) e, além disso, o nó em si também assume parte da computação (4). No caso, por estar com mais de mil elementos no conjunto, é utilizada uma estrutura de dados - HyperLogLog - para a computação.

Quando o nó não possui mais de mil elementos sendo processados, mantém uma estrutura de lista de elementos únicos - Hashset (5), onde o terceiro nó ativo no sistema distribuído também recebe a mesma computação, e, também por estar com mais de mil elementos sendo computados, faz uso da estrutura de HyperLogLog (6).

Dentro do período especificado, no caso, a cada segundo, todos os nós respondem com resultados parciais para o nó responsável pela sincronização - o nó máster. Este nó faz a combinação dos resultados individuais de cada nó (7). Ao sincronizar e consolidar os resultados de cada nó a cada instante definido, o referido método é capaz de identificar se algum nó fez uso de alguma estrutura de dados probabilística.

Se algum nó utilizou uma abordagem probabilística para o cálculo de resultados, o método transforma os cálculos de todos os nós, mesmo aqueles que não tenham utilizado nenhuma estrutura de dados probabilística. Esse processo se faz necessário para que a consolidação de resultados seja realizada e, então, seja transferido de volta para o usuário (8).

A presente invenção foi revelada neste relatório descritivo em termos de sua modalidade preferida. Entretanto, outras modificações e variações são possíveis a partir da presente descrição, estando ainda inseridas no escopo da invenção aqui revelada.