Papers
Google Wave Operational Transformation
David Wang, Alex Mah, Soren Lassen · Google Wave Federation Protocol whitepaper series (versão 1.1, julho de 2010), 2010
O problema: edição ao vivo e concorrente sem bloquear o usuário
O whitepaper "Google Wave Operational Transformation" (versão 1.1, julho de 2010), de David Wang, Alex Mah e Soren Lassen, descreve como o Google Wave obtinha edição colaborativa ao vivo. Aqui, ao vivo e concorrente significa que um usuário vê as mudanças de outro enquanto são feitas, tecla a tecla, e que vários editores alteram o mesmo documento ao mesmo tempo. O Wave oferecia isso para texto rico, com negrito, itálico, marcadores e títulos, e sua tecnologia central permitia modificar de forma concorrente documentos estruturados em geral, inclusive dados de sistema compartilhados entre clientes e back-ends. Para isso o Wave usa Operational Transformation (OT), um arcabouço teórico de controle de concorrência estudado havia mais de dez anos no contexto de edição em grupo. O texto não reexplica a teoria básica e a supõe conhecida. Em resumo, o documento é replicado em todos os sites e qualquer usuário pode editar qualquer parte a qualquer momento. As operações locais são executadas sem atraso nem bloqueio, e as operações remotas são transformadas antes de serem executadas. Como não há locks nem bloqueio, o tempo de resposta local não depende da latência de rede. Isso sustenta a chamada interface otimista: a ação do usuário é executada e exibida localmente de imediato, sem esperar a resposta do servidor. O ponto de partida do OT do Wave foi o artigo sobre o sistema Jupiter (Nichols e outros, 1995), e o Wave também adota uma arquitetura com clientes e um servidor.
Extensão central: o cliente espera o reconhecimento do servidor
Na teoria básica de OT, um cliente pode enviar operações em sequência o mais rápido que conseguir, e o servidor também. Assim, cliente e servidor podem percorrer o espaço de estados por caminhos de OT diferentes, conforme o momento em que recebem as operações um do outro, e ainda chegar ao mesmo estado convergente. O problema é que, com vários clientes conectados, cada par cliente-servidor tem seu próprio espaço de estados. O servidor precisaria manter um espaço para cada cliente conectado, o que pode consumir muita memória, e ainda converter operações de clientes entre esses espaços, o que complica o algoritmo. Como um servidor simples e eficiente é importante para tornar as waves confiáveis e escaláveis, o Wave altera a teoria básica: o cliente deve esperar o reconhecimento do servidor antes de enviar mais operações. Reconhecer significa que o servidor transformou a operação do cliente, aplicou-a à sua cópia do wavelet e transmitiu a operação transformada aos demais clientes conectados. Enquanto espera, o cliente guarda as operações geradas localmente e as envia depois em bloco. Com o reconhecimento, o cliente consegue inferir o caminho de OT do servidor, chamado de caminho inferido do servidor, e só envia operações que já estão nesse caminho. Resultado: o servidor mantém um único espaço de estados, o histórico das operações aplicadas, e basta transformar cada operação recebida contra esse histórico, aplicá-la e transmiti-la. O custo é que um cliente vê blocos de operações de outro em intervalos de cerca de um tempo de ida e volta até o outro cliente.
Modelo de dados: wavelets, documentos e operações em fluxo
No modelo do Wave, uma wave é uma coleção de wavelets, e um wavelet contém uma coleção de documentos. Um documento é composto de um documento estruturado, semelhante a XML, e de anotações. O wavelet é o objeto sobre o qual o OT é aplicado e é onde ocorre a modificação concorrente. As operações de wavelet se dividem em operações de documento, que modificam documentos, e operações que não são de documento, como adicionar ou remover um participante do wavelet. Uma operação de documento tem uma interface de fluxo, parecida com um XMLStreamWriter ou um tratador SAX, e consiste em uma sequência ordenada de mutações aplicadas à medida que o documento é percorrido linearmente. Segundo o texto, projetar assim facilita escrever as funções de transformação e de composição. Cada caractere, tag de abertura ou tag de fechamento é um item, e as lacunas entre itens são posições, sendo a posição 0 anterior ao primeiro item. A mutação retain indica quantas posições pular antes da próxima mutação. As demais mutações são inserir caracteres, inserir início ou fim de elemento, apagar caracteres, apagar início ou fim de elemento, substituir atributos, atualizar atributos e marcar o limite de uma anotação. Um exemplo do próprio texto: reter 3, inserir um elemento p com os caracteres "Hi there!", reter 5, apagar 4 caracteres e reter 2. Um documento inteiro pode ser visto como uma única operação aplicável ao documento vazio.
Anotações, transformação e composição de operações
Além da estrutura, o Wave tem anotações: metadados associados a um intervalo de itens, definido por uma posição inicial e outra final. São úteis para descrever formatação de texto e sugestões ortográficas, sem complicar desnecessariamente o formato do documento estruturado subjacente. O desenho em fluxo também simplifica duas operações centrais. A primeira é a transformação: o transformador recebe duas operações em fluxo, processa-as simultaneamente de forma linear e produz duas operações em fluxo, o que mantém eficiente a transformação de um par de operações muito grandes. A segunda é a composição: as operações de documento foram projetadas de modo que a composição de quaisquer duas operações componíveis é, ela mesma, uma única operação de documento. A composição B∙A tem a propriedade (B∙A)(d) = B(A(d)) para todo documento d ao qual A possa ser aplicada, ou seja, aplicar a composta equivale a aplicar A e depois B. O algoritmo de composição também processa as operações como fluxos lineares e por isso é eficiente. Essa propriedade se liga à extensão do reconhecimento: enquanto aguarda o servidor, o cliente Wave compõe todas as suas operações pendentes, o que reduz o número de operações a transformar e a enviar. O whitepaper é breve e trata das extensões do Wave, não da teoria básica de OT, indicada nas duas referências do whitepaper: o verbete da Wikipédia sobre OT e o artigo do Jupiter.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.