Mas vamos recomeçar.
Em 2010, trabalhei no Google Wave, onde tentamos criar espaços editáveis colaborativos para substituir e-mail, Google Docks, fóruns, mensagens instantâneas e muitos outros aplicativos de tarefa única. Entre as minhas ferramentas, gosto especialmente do ambiente de uso geral, em nenhum outro lugar como no Wave, a funcionalidade não foi formulada naquela época. Ao contrário da maioria das outras ferramentas, o ambiente de propósito geral não impõe seu próprio fluxo de trabalho, portanto, você pode usá-lo para planejar feriados, criar wikis, jogar jogos de tabuleiro com amigos, agendar reuniões de trabalho e muito mais.
Internamente, a coedição do Wave funciona em cima de uma Transformação Operacional (OT) e já existe há dias: nosso algoritmo foi baseado em uma palestra de 1995 de Júpiter . Para cada documento, o algoritmo mantém uma lista cronológica separada de alterações, “Digite H na posição 0”, “Digite i na posição 1” e assim por diante. Na maioria dos casos, os usuários alteram a versão mais recente do documento, e o log parece uma sequência de alterações, porém, na coautoria, nos deparamos com edições simultâneas.
Nesse caso, a primeira edição que chega ao servidor é registrada normalmente e a próxima, se ficar desatualizada, é comparada com o log de eventos para determinar os objetivos iniciais do usuário. (Na maioria das vezes, tudo se resume à atualização das posições dos caracteres.) Então, o algoritmo, supostamente "este é o resultado que o usuário queria", adiciona uma nova operação, como git-rebase em tempo real.
Com o fechamento do Google Wave, transferi o modelo OT para o ShareJS . Na época, o node parecia novo e estranho e, se bem me lembro, iniciei o ShareJS antes mesmo do lançamento do npm. Um simples co-editor exigia apenas mil linhas de código e, na demonstração, coeditei o documento no navegador e no aplicativo.
Em sua essência, OT é um loop for () embelezadocom várias funções de ajuda para atualizar o deslocamento de caracteres. Na prática, o OT é simples, fácil de entender, colocado em operação rapidamente e funciona muito bem. (10-100 mil operações por segundo em javascript não otimizado , 1-20 milhões em C otimizado ). O log de eventos pode consumir mais memória do que o normal, mas você pode reduzi-lo se desejar, embora não seja capaz de combinar edições especialmente antigas. As operações de atribuição global exigirão um servidor centralizado, mas a maioria dos sistemas já possui esse servidor ou banco de dados, não é?
Servidores centralizados
Um problema significativo de OT é sua dependência de um servidor centralizado. Você já se perguntou por que, ao permitir o acesso a um documento do Google Docs via redes sociais, se deparou com uma mensagem estranha como "Este documento está sobrecarregado e sua edição está desativada"? O motivo (na minha opinião) é o seguinte: quando você abre um documento, um servidor específico é selecionado para processar todas as suas edições, e quando uma multidão de usuários ataca o documento, o sistema tem que se esforçar muito para não sobrecarregar o servidor.
Existem várias maneiras de contornar esse problema: além da fragmentação do subdocumento (como no Google Docks), você pode fazer edições por meio de um loop de repetição, ignorando as transações do banco de dados, de modo que o problema de serialização recaia sobre os ombros do mesmo banco de dados (é assim que o Firepad funcionae ShareDB ).
No entanto, OT não é perfeito. Queríamos substituir o e-mail pelo Wave, mas o e-mail oferece suporte à fusão, uma cadeia de cartas pode se estender por muitas empresas e, de alguma forma, tudo funciona com sucesso. Além disso, ao contrário das mensagens do Facebook, o e-mail pode ser enviado para empresas mencionadas na coluna “cópia”. Se quisermos que o Wave substitua o mail, ele também precisará da funcionalidade de envio de mensagens sem acesso à rede externa, por exemplo, quando mando uma carta para o meu colega da mesa ao lado. Mas como você pode implementar tudo isso em cima do OT? De alguma forma, conseguimos configurar esse processo, mas acabou sendo muito complexo e cheio de erros: criamos um diagrama, em que cada protocolo de onda configurou uma árvore de servidores de onda para transferir operações em ambas as direções, mas nunca funcionou totalmente. Há pouco menos de dez anos, no Wave Protocol Summit, fiz uma apresentação sobre como criar e configurar essa rede, mas apesar de toda a minha preparação e de todas as verificações preliminares, o cumprimento estrito de cada etapa da apresentação em si falhou e a rede nunca funcionou. Ainda não sei por que isso aconteceu, mas fossem quais fossem os bugs, quase nunca eram corrigidos na versão pública, era muito difícil.
CRTD de decolagem
Como já mencionei, o algoritmo principal do Wave foi criado há muito tempo, em 1995, e eu nem me lembro de ter Internet em casa naquela época. Desde então, os pesquisadores trabalharam incansavelmente para melhorar o desempenho do OT e, na direção mais promissora, eles usam os CRTD (tipos de dados replicados sem conflito). Esta abordagem é um pouco diferente da usual e permite editar arquivos em tempo real sem a necessidade de um servidor central. A apresentação de Martin descreve seu trabalho melhor do que eu poderia descrevê-los, então vou pular os detalhes.
As pessoas pedem minha opinião sobre o CRTD há anos, e minha resposta sempre soa assim:
Eles são legais e estou feliz que as pessoas estejam trabalhando neles, no entanto:
- . . , 100 Delta-CRTD . (: B4.)
- - CRTD , , 100 automerge master 83 . , , , , . ( automerge 1.1 .)
- Durante anos, a funcionalidade presente no OT esteve ausente no CRDT, por exemplo, ninguém ainda fez um CRDT com suporte para / movimento de objeto / (transferir algo de uma parte da árvore JSON para outra). Esses procedimentos são necessários para aplicativos como o Workflowy, e a OT faz um ótimo trabalho com eles .
- Os CRDTs são complexos em si mesmos e difíceis de raciocinar.
- Você provavelmente já tem um servidor / banco de dados centralizado.
Apesar de todas as minhas críticas, ignorei o CRDT, mas, ao fazê-lo, ignorei a literatura relevante e, para minha surpresa, perdi a melhoria silenciosa e imperceptível do CRDT. Em sua apresentação (que é mais do que digna de sua atenção), Martin aborda os pontos principais:
- : CRDT (Automerge / RGA Y.js / YATA) [log(n)] . ( .)
- : - , 54- . automerge , Y.js, Y.js 100 160 3 . .
- : , .
- : , CRDT OT. , automerge .
O raciocínio para velocidade não me convenceu, então, para testar a ideia, implementei e testei independentemente o CRDT no Rust por meio de uma árvore B usando ideias do automerge. Faltava funcionalidade (exclusão de caracteres, conflitos), mas era capaz de lidar com 6 milhões de edições por segundo . (Cada iteração fez 2.000 edições em um documento em branco por dois usuários alternados, o que levou 330 microssegundos no total, ou 6,06 milhões de edições por segundo.) Portanto, os CRDTs realmente melhoraram e a diferença de velocidade entre eles e OT agora é ainda menor do que entre Rust e Javascript.
Todas essas correções estão na seção "em breve" do branch de desempenho do automerge por um longo tempo, mas afinal o automerge não é o único CRDT. Y.js prova ser digno e facilmente ignora a versão atual do automerge em seus testes . Ele não tem a funcionalidade na qual estou interessado, mas em geral é certamente mais fácil corrigir a implementação existente do que criar um novo algoritmo.
Inventando o futuro
Estou muito preocupado em fazer progresso. O que seria estranho não ter em uso em cem anos? Obviamente, teremos edição em tempo real, mas não tenho mais certeza sobre sua implementação por meio da OT e de todo o trabalho que fiz a esse respeito, o que não pode deixar de me entristecer.
JSON e REST são onipresentes atualmente. Digamos que em 15 anos a coedição em tempo real seja onipresente. Qual seria a contrapartida JSON em termos de coautoria para facilitar a transferência para o seu projeto? Neste futuro glorioso, precisaremos de uma implementação de CRDT de alta qualidade, já que para alguns aplicativos OT simplesmente não funcionará, não funcionará para criar uma versão em tempo real do GIt por meio dele ou uma simples variação do Google Wave. Mas se já temos uma boa implementação de CRDT, também precisamos de uma implementação de OT? Acho que não, porque não será difícil transferir todas as funcionalidades do OT para o CRDT (incluindo, a propósito, operações de corte), enquanto o contrário não é verdadeiro. Pessoas inteligentes discordam de mim, mas, na minha opinião, visto que temos um CRDT bom e rápido para cada idioma,a necessidade de OT desaparecerá completamente.
Uma das vantagens do OT é que ele pode ser facilmente implementado em sistemas centralizados - como a maioria dos aplicativos modernos - mas os algoritmos distribuídos também são bem implementados. (Dê uma olhada no Github, por exemplo.) Em minha opinião, um CRDT de alta qualidade no wasm é mais rápido do que uma implementação OT em JS. E se você está preocupado apenas com sistemas centralizados, lembre-se: as restrições de OT levaram o Google a problemas de dimensionamento no Google Docs.
Portanto, parece-me que agora é a hora de mudar para um CRDT pequeno e rápido. Na maior parte, o trabalho acadêmico já foi feito, a questão permanece para implementações bem-sucedidas.
Qual é o próximo
Estou cada vez menos preocupado com o mundo dos aplicativos centralizados. Os aplicativos interagem com meus dados, em meus dispositivos, e já é hora de esses aplicativos reagirem a essas conexões de acordo. Quero que meu laptop e meu telefone sejam capazes de transferir dados um para o outro via wi-fi, e não através do upload de meus dados para servidores em outro país. Especialmente se esses servidores forem financiados por gigantes da publicidade competindo pela minha atenção .
Filosoficamente, quando edito um documento no Google Docs, meu computador pede ao Google permissão para editar o arquivo (porque se por algum motivo o servidor disser não, eu perco todas as minhas edições). Para comparação, quando
git pushestou no github, eu apenas notificogithub sobre edições em meu código. Meu repositório ainda pertence a mim, assim como todos os dados e hardware em que ele está, e é assim que meus aplicativos devem funcionar. Graças a pessoas como Martin, agora sabemos como fazer bons CRDTs. No entanto, antes que os aplicativos locais sejam aceitos como base, mais linhas de código terão que ser escritas.
Resumindo, é hora de dizer adeus à transformação operacional. Nós nos divertimos muito juntos, de tudo que escrevi, o código de transformação operacional foi um dos mais difíceis e interessantes. Você é um OT inteligente e incrível, mas o CRDT pode fazer algo que você nunca conseguirá. E eu preciso do CRDT. Acho que com algumas boas implementações podemos alcançar algo realmente especial.
Lamento todo o trabalho que coloquei na OT ao longo dos anos, mas a OT não se encaixa mais na minha visão do futuro. O CRDT nos permitirá reconstruir o Wave com mais facilidade e rapidez e criar aplicativos que tratem os usuários como cidadãos digitais, em vez de camponeses digitais. E isso é importante.
É hora de criar.