Yo estaba equivocado. Los CRDT son el futuro.

 (josephg.com)
24 puntos por xguru 2020-10-05 | 10 comentarios | Compartir por WhatsApp

La historia de los Conflict-free Replicated Data Types contada por un desarrollador de Google Wave

→ CRDT: estructura de datos que permite la edición simultánea en herramientas de colaboración en tiempo real

  • Wave estaba basado en OT (Operational Transform): guarda una lista cronológica de todos los cambios. Es como un git rebase en tiempo real

  • Uno de los problemas de OT es que necesita un servidor/DB centralizado

→ ¿Quizá por eso, cuando se llena de gente un documento de Google Docs (también basado en OT), aparece el mensaje “este documento está sobrecargado y no se puede editar”?

→ Se puede evitar dividiendo el documento o usando un bucle de reintentos en las transacciones de la DB (trasladando el problema de serialización a la DB)

→ Pero no es perfecto. Wave permitía que varias personas editaran al mismo tiempo y funcionaba, pero tenía muchos bugs. Era demasiado complejo

  • El auge de CRDT

→ El algoritmo que usaba Wave fue inventado en 1995. Se siguió investigando para que OT funcionara bien, pero CRDT parece mucho más prometedor

→ CRDT toma otro enfoque y permite edición en tiempo real sin una DB central

→ Lo que antes se señalaba como problemas de velocidad/capacidad/funcionalidad/complejidad ahora ha mejorado en todos los frentes

  • Velocidad: los CRDT actuales (Automerge / RGA o y.js / YATA) permiten consultas de nivel log(n)

  • Capacidad: la codificación columnar de Martin permite guardar documentos en alrededor de 1.5 a 2 veces el tamaño del documento

  • Funcionalidad: en teoría es posible hacer rewinding y replaying. Claro, todavía nadie lo ha implementado

  • Complejidad: el tamaño de una implementación de CRDT quizá sea mayor que el de OT, pero no hay una gran diferencia

→ Estas mejoras estarán disponibles pronto en Automerge

  • En edición en tiempo real, aunque suene triste, OT y los trabajos relacionados probablemente ya no serán necesarios

→ Todo lo que OT puede hacer puede incorporarse en CRDT, pero al revés no es posible

→ La ventaja de OT es que encaja bien con software centralizado, pero los algoritmos distribuidos también funcionan bien en esquemas centralizados

→ Un CRDT de alta calidad ejecutándose en WASM será más rápido que una implementación de OT en JS

  • Ya es momento de crear CRDT ligeros y rápidos.

→ La parte académica está casi terminada, y ahora hace falta el momento de las implementaciones realmente excelentes

Lecturas relacionadas

10 comentarios

 
hackerwins 2020-10-05

Soy Hong Young-taek y estoy desarrollando el proyecto Yorkie.

El almacén de documentos Yorkie para aplicaciones de edición colaborativa también está hecho sobre la base de CRDT.

https://github.com/yorkie-team/yorkie
 
iolothebard 2020-10-05

Con OT, undo/redo se puede sacar prácticamente gratis, pero... con CRDT no hay otra forma más que snapshot...
 
xguru 2020-10-05

En el caso de Automerge, la propia biblioteca sí ofrece soporte para undo/redo. Implementarlo probablemente sea difícil, pero desde la perspectiva de quien usa la biblioteca, pues bueno, jaja
 
ffdd270 2020-10-05

https://www.notion.so/sihawn/CRDT-1dc1af26d60144c09eadd178e0ae6e0d

Había hecho una traducción completa, pero se me olvidó subirla ;_; La releí una vez basándome en Papago y solo corregí las partes que sonaban raras. Si quieren ver cómo quedó en general o leerla, por favor revisen el enlace de arriba~

Para publicarla en la ventana de comentarios... era demasiado larga ;_; Así que se las dejo en un enlace de Notion.
 
ffdd270 2020-10-05

Pensándolo bien, ¡puede que Notion también esté usando CRDT!
 
xguru 2020-10-05

Los que usan OT son Google Wave/Google Docs/MS Office365

Los que usan CRDT son Figma/Apple Notes y también Riak/Redis, entre otros
 
xguru 2020-10-05

Estaba equivocado. CRDT es el futuro.

Cómo funciona la tecnología multiusuario de Figma: https://es.news.hada.io/topic?id=814
 
xguru 2020-10-05

El video de Martin Kleppmann, desarrollador de Automerge, titulado "CRDTs: The Hard Parts" y enlazado en el artículo, realmente explica muy bien el tema.

Al principio compara y explica muy bien OT y CRDT. La parte final entra en una conversación más profunda sobre la implementación de CRDT.

https://www.youtube.com/watch?v=x7drE24geUw

Una biblioteca de CRDT que se usa para crear herramientas colaborativas con JS
 
xguru 2020-10-05

Estaba equivocado. CRDT es el futuro.

Towards collaboration system: del algoritmo OT al sistema CRDT

https://deview.kr/2013/detail.nhn?topicSeq=66

Entre las presentaciones nacionales, este es casi el único contenido que trata sobre CRDT.
 
hackerwins 2020-10-06

Hyun-geol, quien dio esta presentación, creó el RGA del que se habla en el texto.

Yorkie también implementó su tipo de dato de lista basándose en RGA.

https://github.com/yorkie-team/yorkie/issues/2