Papers
The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processing
Tyler Akidau, Robert Bradshaw, Craig Chambers, Slava Chernyak, Rafael J. Fernández-Moctezuma, Reuven Lax, Sam McVeety, Daniel Mills, Frances Perry, Eric Schmidt, Sam Whittle · Proceedings of the VLDB Endowment (PVLDB), vol. 8, no. 12, 2015
O problema: dados sem fim, fora de ordem, e a falsa escolha entre batch e streaming
O artigo parte da observação de que conjuntos de dados globais, ilimitados e desordenados (logs web, uso de apps móveis, redes de sensores) viraram comuns, e de que os consumidores desses dados exigem ordenação por tempo do evento, janelas definidas pelas características dos próprios dados e respostas cada vez mais rápidas. Os autores argumentam que ninguém consegue otimizar ao mesmo tempo correção, latência e custo, e que os profissionais acabam com implementações díspares para reconciliar essas tensões. O exemplo motivador é um provedor de vídeo que precisa cobrar anunciantes pelo tempo de anúncio assistido, calcular estatísticas agregadas e rodar experimentos offline sobre histórico, tudo com o mínimo de atraso, mas com correção primordial porque há dinheiro em jogo. Sistemas batch (MapReduce e variantes, FlumeJava, Spark) sofrem com a latência de coletar toda a entrada antes de processar. Muitos sistemas de streaming ficam aquém em expressividade ou em correção, por exemplo sem semântica exactly-once ou com janelas limitadas a contagem de tuplas ou tempo de processamento. A tese central é que o erro está em tentar transformar dados ilimitados em pacotes finitos que um dia ficarão completos: é preciso assumir que nunca se saberá se ou quando todos os dados foram vistos, que dados novos chegam e que dados antigos podem ser retratados. Por isso o artigo prefere os termos ilimitado/limitado a streaming/batch, reservando estes últimos para os motores de execução.
Tempo do evento versus tempo de processamento, e a marca d'água
O modelo se apoia em dois domínios de tempo. O tempo do evento é o momento em que o evento de fato ocorreu, e para um dado evento ele essencialmente nunca muda. O tempo de processamento é o momento em que o evento é observado dentro do pipeline, segundo o relógio do sistema, e avança continuamente. Atrasos de comunicação, escalonamento e serialização fazem com que exista uma defasagem (skew) dinâmica entre os dois domínios, e o artigo ilustra isso com um gráfico que plota a marca d'água real contra a ideal, em que a ideal teria inclinação um e defasagem zero. A marca d'água (watermark), nos moldes da do MillWheel, é um limite inferior sobre os tempos de evento já processados pelo pipeline. Na maioria dos conjuntos reais ela é definida heuristicamente, porque o sistema não sabe, por exemplo, quando um celular que ficou sem conexão voltará a enviar visualizações. Por isso os autores insistem que noções de completude em geral são incompatíveis com correção, e que a marca d'água serve como estimativa útil de progresso e para monitorar a saúde do sistema, não como garantia de que todos os dados chegaram. Alterar o timestamp de um elemento para trás da marca d'água o torna atrasado em relação a ela.
Janelas: fixas, deslizantes e sessões, e os dois passos que as generalizam
Janelamento fatia um conjunto de dados em pedaços finitos para processar em grupo, e é necessário para dados ilimitados em operações como agregação e junções externas. O artigo descreve três padrões comuns. Janelas fixas (também chamadas tumbling) têm tamanho estático, como janelas horárias, e em geral valem para todos os dados do período. Janelas deslizantes têm tamanho e período de deslizamento, como janelas de uma hora que começam a cada minuto; as fixas são o caso particular em que tamanho e período coincidem. Sessões capturam um período de atividade sobre um subconjunto dos dados, em geral por chave, delimitado por um tempo limite de inatividade; são janelas não alinhadas, e o suporte a elas é apontado como a principal contribuição do modelo de janelamento. Para generalizar tudo, o modelo trata todas as estratégias como não alinhadas e divide o janelamento em duas operações: AssignWindows, que atribui cada elemento a zero ou mais janelas, e MergeWindows, que funde janelas no momento do agrupamento, permitindo janelas guiadas pelos dados, como sessões que se unem quando eventos intermediários chegam. Para isso, os elementos passam a ser tuplas (chave, valor, tempo do evento, janela), e o agrupamento vira GroupByKeyAndWindow.
Gatilhos e modos de acumulação: quando emitir e como refinar
Janelas dizem onde, no tempo do evento, os dados são agrupados; faltava dizer quando, no tempo de processamento, os resultados são emitidos. O artigo mostra que a marca d'água sozinha é insuficiente por duas razões: às vezes é rápida demais, deixando dados atrasados para trás, e às vezes é lenta demais, porque por ser uma métrica global um único dado lento pode segurar todo o pipeline e elevar a latência. Daí os gatilhos (triggers), que estimulam a produção do resultado de uma janela em resposta a sinais internos ou externos e podem emitir vários painéis (panes) por janela. Há gatilhos por estimativa de completude (inclusive marcas d'água percentuais), por tempo de processamento e por chegada de dados (contagem, bytes), além de composição lógica (e, ou, sequências, laços) e gatilhos definidos pelo usuário. Os modos de refinamento relacionam painéis sucessivos. No modo descartante (discarding), o conteúdo é descartado após o disparo e os resultados seguintes são independentes. No acumulante (accumulating), o conteúdo fica no estado persistente e cada resultado refina o anterior, como em sistemas Lambda que sobrescrevem valores. No acumulante e retratante (accumulating and retracting), emite-se antes uma retratação do valor anterior e depois o novo, necessário quando vários agrupamentos em série fariam resultados parciais acabarem em chaves diferentes mais adiante.
As quatro perguntas e a crítica à arquitetura Lambda
A contribuição conceitual é um único modelo que decompõe a implementação de um pipeline em quatro dimensões: o que (what) está sendo calculado, onde (where) no tempo do evento, quando (when) no tempo de processamento os resultados se materializam e como (how) resultados anteriores se relacionam com refinamentos posteriores. Isso separa a noção lógica de processar dados da implementação física, de modo que escolher entre batch, micro-batch ou streaming vira uma escolha de correção, latência e custo. Os exemplos do artigo, todos somando inteiros por chave, mostram o mesmo conjunto de dez valores com saídas distintas variando apenas janela, gatilho e modo: uma soma global de 51 no batch clássico, somas globais periódicas acumulantes ou descartantes, janelas por contagem de elementos, janelas fixas de dois minutos em motores batch, micro-batch e streaming, e sessões com retratação. Sobre a arquitetura Lambda, os autores reconhecem que ela atinge muitos dos requisitos, mas falha em simplicidade por exigir construir e manter dois sistemas. Observam ainda que o Lambda não resolve a completude: apenas entrega a melhor estimativa de baixa latência do streaming, com a promessa de consistência eventual quando o batch rodar, e que esse batch só é correto se a entrada estiver completa quando ele executa.
Implementação, princípios de projeto e experiências que motivaram o modelo
O modelo foi implementado internamente no FlumeJava, usando o MillWheel como motor de execução em modo streaming, e há uma reimplementação externa para o Google Cloud Dataflow, com SDK de código aberto. Boa parte do código de janelamento e gatilhos é compartilhada entre as implementações batch e streaming. Os princípios de projeto listados são: nunca depender de qualquer noção de completude, ser flexível para casos de uso conhecidos e futuros, não só fazer sentido mas agregar valor em cada motor de execução, incentivar clareza de implementação e apoiar análise robusta dos dados no contexto em que ocorreram. As experiências reais moldaram o desenho. Um grande pipeline de junção de logs rodava em streaming no MillWheel, mas tinha implementação batch separada em FlumeJava para backfills, o que motivou a unificação. Um cliente que usava streaming de consistência fraca com um MapReduce noturno para gerar a verdade perdeu a confiança dos usuários e migrou para consistência forte. Sessões foram a motivação central do janelamento. Pipelines de cobrança motivaram gatilhos, acumulação e retratação; cálculo de estatísticas motivou gatilhos de marca d'água; detecção de abuso motivou marcas d'água percentuais; recomendações motivaram gatilhos de tempo de processamento; e detecção de anomalias motivou gatilhos guiados por dados e compostos.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.