Pedro Lamarão

Meu trabalho frequentemente trata de fornecer operadores para transformações peculiares que envolvem aplicar operadores primitivos de criptografia. Como os operadores de criptografia são muito esotéricos para a competência genérica das equipes de desenvolvimento, e a guarda da chave-privada é um problema muito sensível, nós somos trazidos como fornecedor especialista para dentro de grandes arquiteturas fornecidas por outras pessoas.

Isto gera uma responsabilidade difícil: não impedir o bom desempenho dessa arquitetura. Como não temos uma visão realista do que ela é, corremos sempre o risco de fornecer operadores convenientes para nós, mas, com propriedades que inadvertidamente têm má sinergia com aquela arquitetura.

Dito de forma mais clara, nós corremos o risco de por ingenuidade, sem perceber, impactar negativamente a arquitetura maior onde nossos componentes serão inseridos.

Neste artigo, vamos considerar a técnica de streaming. Para compreendê-la, vamos primeiro considerar sua circunstância. A seguinte definição em pseudo-código dá uma transformação.

transform : function (in : In, out : Out) → ()

Existem transformações cujo objeto pode ser descrito como uma sequência de partes independentes.

(p_0, p_1, p_2, p_3, ..., p_n)

Para tais objetos, a transformação significa, grosso modo, realizar esta sequência:

out0 = transform0(in_0)
out1 = transform1(in_1)
out2 = transform2(in_2)
out3 = transform3(in_3)
...
outn = transformn(in_n)

Caso transform_i seja para todo i exatamente o mesmo transform_p, então podemos encurtar a notação usando uma estrutura iterativa:

for i in [0, n) {
  out_i = transform_p(in_i)
}

Ora, esta notação sugere uma coisa curiosa: que esteja presente na memória, a cada etapa, apenas as partes envolvidas. Ou seja, que a quantidade de memória necessária para esta transformação seja constante no tamanho de uma parte, ao invés de variar com a quantidade de partes. Como seria isso?

Vamos definir source como um operador capaz de trazer uma parte e sink como um operador capaz de mandar uma parte embora. Com source e sink, podemos rascunhar uma definição alternativa para transform.

transform : function (in : source, out : sink) → () = {
  loop {
    x = in()
    y = transform(x)
    out()
  }
}

Adicionando a condição de parada, temos a forma geral do streaming: as partes fluem de in para transform e de transform para out, com a virtude de consumir uma quantidade constante de memória para transformar uma quantidade ilimitada de informação.

Muitas transformações se oferecem evidentemente para streaming. Algoritmos como a codificação base 64 transformam uma quantidade fixa de bytes por vez. Para transformar um arquivo gigantesco por base 64 é desnecessário reservar uma quantidade gigantesca de memória. Algumas operações não são facilmente identificadas como apropriadas para streaming por consequência do mau hábito. A prática de representar documentos XML como uma árvore integralmente presente na memória mascara o fato de a canonicalização XML se oferecer para streaming: é suficiente representar o documento como uma sequência de “partes XML” (como “open element” ou “text”) e processar cada parte por vez. Esse fato conduz ao fato de não ser necessário construir a árvore completa de um documento XML para aplicar nele uma transformação de segurança baseada em canonicalização XML.

Esta última observação, a de como o hábito mascara a streamability, nos tornou muito atentos a essa situação. Nós identificamos muitas transformações cuja forma óbvia e costumeira se revelou desnecessária.

Apesar de streaming não afetar o tempo de uma transformação, por afetar o seu consumo de memória, afeta indiretamente o paralelismo. Conhecer exatamente a necessidade de memória de um operador permite definir exatamente quantas transformações simultâneas essa máquina é capaz de realizar em paralelo, sem imprevistos.

Infelizmente, operadores definido como acima tem um problema. Somente os processos mais sem graça serão redutíveis a uma única operação. Processos interessantes são compostos por múltiplas etapas.

tmp_0 = transform_0(in)
tmp_1 = transform_1(tmp_0)
tm2_3 = transform_2(tmp_1)
...
out = transform_n(tmp_n-1)

Como visto acima, para obter streaming, é preciso definir source e sink, e ajustar os operadores para trabalhar com eles. Vamos supor que source_0 é capaz de fornecer os dados iniciais, sink_n é capaz de consumir os dados finais, e todos os outros source e sink intermediários são capazes de tratar os dados temporários apropriadamente.

process : function (source0, sinkn) → () = {
  transform0(source0, sink0)
  transform1(source1, sink1)
  transform2(source2, sink2)
  ...
  transformn(sourcen, sinkn)
}

Assim, cada operador é individualmente capaz de streaming. Agora, e o processo como um todo? Reavaliando, chamamos streaming um processo em que as etapas transformam uma parte da entrada em uma parte da saída, de modo que o operador exija uma quantidade fixa de memória para transformar quantidades arbitrárias de informação.

Isso não pode ser verdade sobre process se transform_0 completa antes de transform_1 começar: todo o resultado consumido por sink_0 deve ser armazenado em algum lugar para posteriormente ser fornecido por source_1. Para que process tenha a propriedade de streaming é preciso que a sequência como um todo transforme uma parte por vez.

process : function (source, sink) → () = {
  loop {
    tmp_0 = source()
    tmp_1 = transform_1(tmp_0)
    tmp_2 = transform_2(tmp_1)
    tmp_3 = transform_3(tmp_2)
    ...
    tmp_n = transformn(tmp_n-1)
    sink(tmp_n)
  }
}

Assim, para aplicar source e sink de modo a obter um process com a propriedade de streaming precisamos usar transform_i definido diretamente nas partes. Isto é uma consequência direta da propriedade de cada transform_i completar integralmente antes do seguinte começar. Quando este é o caso, a técnica de source/sink não é adequada para composição de operadores: não é possível obter streaming por composição de operadores streaming.

Esta é uma consequência direta de uma pressuposição implícita em nossa notação: a de que operadores são definidos fundamentalmente por sequências de etapas, cada uma completada integralmente antes de iniciar a etapa seguinte. Isso faz todo sentido quando estamos definindo os operadores mais simples, em particular, os operadores que transformam diretamente as partes. Quando estamos definindo processos complexos compostos por outros operadores, possivelmente estes mesmos construídos por operadores mais simples ainda, quando streaming se torna uma propriedade crucial, nossa necessidade de expressão é diferente, e a notação começa a nos faltar.

Esta realização nos ensinou o seguinte: ao trabalhar com linguagens imperativas, é muito importante oferecer streaming como um serviço para o cliente, mas, além disso, sempre, sempre definir operadores primitivos diretamente nas partes. Eventualmente será necessário criar uma nova composição, e essa necessidade não virá em uma hora conveniente.

Uma maneira de definir graficamente o que estamos procurando fazer é assim. Suponha que | seja algum tipo de operador de fluxo, cujo significado é juntar dois operadores de uma forma misteriosa capaz de streaming.

source |0 transform_1 |1 transform_2 |2 ... |n-1 transform_n |n sink

Ou seja, o significado de |k se resolve de alguma maneira para:

tmp_k-1 = magic
tmp_k = transform_k(tmp_k-1)

As linguagens funcionais, notavelmente o LISP, expressam esse tipo de relação naturalmente. Em tempos recentes, algumas novas construções estão sendo trazidas para linguagens imperativas, construções capazes de diminuir a impedância na expressão desse tipo de coisa. Em um próximo estudo, vamos considerar essas opções.