El artículo de 2019: dos décadas sin que nadie mirase

Los fallos famosos de la informática suelen tener una fecha de nacimiento y una de defunción muy próximas: alguien introduce un error, alguien lo encuentra, alguien lo corrige. Este no. La intercalación estuvo presente en algoritmos publicados, revisados por pares, implementados en bibliotecas de uso general y desplegados en productos con muchos usuarios, durante un periodo que se mide en décadas y no en versiones. No se ocultaba: cualquiera que hubiese hecho la prueba de la primera lección la habría visto en dos minutos. Lo que faltaba no era capacidad de observación sino algo bastante más difícil de echar en falta, que es el enunciado que convierte una observación incómoda en un defecto reportable. En 2019, en un taller de una jornada, Martin Kleppmann y sus colegas presentaron ese enunciado bajo el título Interleaving anomalies in collaborative text editors, y a partir de ahí lo que antes era una rareza que la gente arreglaba a mano pasó a ser un fallo con nombre.

Un artículo corto en un taller de una jornada

Conviene empezar por el envase, porque dice algo sobre la naturaleza del hallazgo. PaPoC es un taller dedicado a los principios y la práctica de la consistencia en datos distribuidos, se celebra junto a una conferencia mayor de sistemas y su formato favorece las contribuciones breves y las discusiones abiertas por encima de los resultados cerrados. No es el lugar donde se anuncian teoremas monumentales: es el lugar donde alguien pone sobre la mesa un problema que la comunidad debería estar mirando y no está mirando.

El detalle del formato no es anecdótico. Un resultado como este no encaja bien en el circuito principal de publicación, porque no propone ni mejora nada y su contribución consiste enteramente en señalar. Los talleres existen en buena medida para dar cabida a ese tipo de intervención, y su existencia es lo que hace que la comunidad tenga algún canal por el que puedan circular las malas noticias sobre sus propios supuestos. Un campo sin ese canal no deja de tener anomalías: deja de enterarse de ellas.

Ese es exactamente el tipo de aportación que el artículo hace, y por eso resulta tan instructivo. Lo que se presenta no es un algoritmo nuevo, ni una optimización, ni una demostración de imposibilidad. Es la documentación cuidadosa de un comportamiento que las implementaciones existentes ya tenían, acompañada de la observación de que ese comportamiento no está prohibido por ninguna de las propiedades que esas implementaciones enuncian y demuestran. Toda la novedad reside en haber convertido una molestia difusa en una anomalía con nombre, con condiciones de aparición y con la constatación explícita de que la teoría vigente la permitía.

La palabra que da título al trabajo hace, ella sola, buena parte del trabajo. Anomalía es un término técnico con historia en las bases de datos: designa un comportamiento que un sistema exhibe, que su especificación permite y que sin embargo nadie desea, y que por tanto solo puede eliminarse fortaleciendo la especificación y no corrigiendo la implementación. Elegir esa palabra en lugar de hablar de un error sitúa el problema exactamente donde está, en el nivel de lo que se prometió, y descarta de antemano la respuesta que habría sido natural y estéril, que es buscar la línea de código culpable.

No hay que subestimar cuánto trabajo intelectual hay en ese gesto, aunque sobre el papel parezca un movimiento pequeño. Nombrar un fallo es lo que permite buscarlo sistemáticamente en otros sistemas, compararlo entre algoritmos, cuantificar su gravedad y, sobre todo, exigirle a un diseño futuro que no lo tenga. Antes del nombre, cada aparición era un incidente aislado que cada equipo resolvía o ignoraba por su cuenta y que no se acumulaba con las demás en ninguna parte. Después del nombre, todas las apariciones son instancias de lo mismo.

Conviene también fijar el tamaño de la sorpresa. Lo asombroso no es que un algoritmo tuviera un comportamiento indeseable; eso ocurre a diario y se corrige. Lo asombroso es que ese comportamiento fuese observable por cualquiera, estuviese presente en implementaciones muy usadas y aun así careciera durante décadas de un nombre bajo el que reunir sus apariciones. La sorpresa no es sobre los algoritmos: es sobre el proceso colectivo que decide qué cuenta como un problema.

Hay una asimetría de prestigio que conviene tener presente al leer historias como esta, porque distorsiona la percepción de dónde está el trabajo valioso. Un artículo que presenta un algoritmo nuevo se mide por lo que añade; un artículo que documenta una anomalía se mide por lo que quita, y quitar no tiene métrica. Nadie puede publicar una tabla comparativa donde la columna sea el número de supuestos falsos que ha retirado de la circulación. Y sin embargo, en un campo que lleva décadas acumulando resultados sobre una base común, retirar un supuesto falso de esa base tiene un efecto multiplicador sobre todo lo construido encima que ningún algoritmo individual alcanza.

Por qué la transformación operacional tampoco se salva

El punto del artículo con más consecuencias es probablemente el que menos titulares habría dado, y es que la anomalía no pertenece a una técnica sino a un planteamiento. La transformación operacional es la otra gran familia de algoritmos de edición colaborativa, con una genealogía distinta y anterior a la de los tipos de dato replicados, y también intercala.

La relevancia de ese dato se aprecia mejor sabiendo cómo se discutía el asunto por entonces. Las dos familias competían, y la comparación entre ellas era un tema recurrente: cuál escala mejor, cuál necesita menos metadatos, cuál es más fácil de verificar. En ese clima, cualquier defecto encontrado en una tendía a leerse como un argumento a favor de la otra. Constatar que ambas comparten esta anomalía desactiva la comparación de golpe y obliga a mirar más abajo, hacia el supuesto común que ninguna de las dos había cuestionado.

El mecanismo es fácil de ver una vez se sabe dónde mirar. La transformación operacional no fusiona estados sino que ajusta operaciones: cuando llega una inserción concurrente, se recalculan sus índices para tener en cuenta lo que las otras operaciones ya insertaron o borraron antes de ella. Ese recálculo se apoya en una función de transformación que recibe dos operaciones sueltas y decide cuál queda antes cuando ambas apuntan a la misma posición. Mira la firma de esa función con atención: recibe dos inserciones de un carácter, y ninguno de sus argumentos le informa de que ese carácter pertenece a una palabra que alguien tecleó de un tirón. La noción de secuencia contigua escrita por una persona no existe en su vocabulario, así que difícilmente puede protegerla.

Compáralo con el mecanismo de la primera lección y verás que la coincidencia es más profunda de lo que el parecido superficial sugiere. En la familia de los identificadores densos, el orden final se decide carácter a carácter al ordenar claves independientes. En la transformación operacional, el orden final se decide carácter a carácter al aplicar la función de desempate a pares de operaciones. Los formalismos no tienen nada que ver, el vocabulario tampoco, y la estructura del fallo es idéntica: la decisión que determina el resultado se toma tantas veces como caracteres hay, y en ninguna de esas veces se dispone del contexto que haría falta para tomarla bien.

Según qué criterio se use para deshacer el empate —la identidad del sitio, una marca lógica, alguna propiedad del propio carácter— el entrelazado resultará sistemático o aparecerá solo bajo ciertas configuraciones de las operaciones. Pero la variación es de grado y no de fondo: en ninguna de esas variantes hay un mecanismo cuya función sea mantener unido lo que se escribió unido, porque la unidad sobre la que todo el aparato razona es el carácter individual.

Hay además una circunstancia agravante en esta familia que merece mención. Buena parte del esfuerzo teórico de la transformación operacional se dedicó durante años a las condiciones que deben cumplir las funciones de transformación para que el resultado sea independiente del orden de aplicación, y varios algoritmos publicados resultaron no cumplirlas. Esa discusión, larga y difícil, era enteramente sobre convergencia. Es decir: la comunidad pasó dos décadas afinando la propiedad que ya tenía y ninguna afinando la que no tenía, lo cual no es un reproche moral sino la descripción de cómo se comporta cualquier campo que dispone de un criterio de éxito bien definido.

flowchart TB
P[el problema comun es fusionar inserciones concurrentes] --> O[transformacion operacional desde finales de los ochenta]
P --> C[tipos de dato replicados para secuencias desde los dos mil]
O --> U1[la unidad de razonamiento es la operacion suelta]
C --> U2[la unidad de razonamiento es el caracter con identificador]
U1 --> I[ninguna de las dos familias representa la secuencia contigua]
U2 --> I
I --> A[la intercalacion alcanza a ambas]
style O fill:#f9e2af,color:#11111b
style C fill:#cba6f7,color:#11111b
style A fill:#f38ba8,color:#11111b

Ese resultado descarta de entrada la explicación más cómoda, que habría sido atribuir el defecto a la juventud de los CRDT frente a la madurez de la técnica anterior, o al revés. Dos linajes independientes, con veinte años de distancia entre sus orígenes, con comunidades que apenas se citaban y con formalismos incompatibles, llegaron al mismo agujero. Cuando eso ocurre, el agujero no está en ninguna de las dos construcciones sino en la pregunta que ambas se hicieron al empezar.

Y la pregunta compartida se puede reconstruir sin dificultad, porque está escrita en la unidad de trabajo que ambas eligieron. Las dos familias decidieron que la operación elemental de un editor es insertar o borrar un carácter en una posición, lo cual es una descripción exacta de lo que hace un teclado y una descripción muy pobre de lo que hace una persona. Una persona escribe palabras, frases y párrafos; el hecho de que esa intención llegue al sistema descompuesta en pulsaciones es un accidente del dispositivo de entrada, no una propiedad del acto de escribir. Al adoptar la unidad del teclado como unidad de razonamiento, ambas familias perdieron la única información que habría bastado para evitar el problema, que es qué caracteres formaban parte de la misma aportación.

Cómo sobrevive un fallo visible durante veinte años

La pregunta interesante deja de ser técnica en este punto y se vuelve casi forense, y merece tratarse con seriedad porque las respuestas son transferibles a cualquier proyecto propio. El fallo se reproduce en dos minutos, no requiere condiciones exóticas y produce un resultado que cualquiera identifica como malo. ¿Cómo se sostiene algo así durante dos décadas de investigación activa? Hay al menos cuatro razones y ninguna de ellas es la incompetencia.

Antes de entrar en ellas conviene descartar la explicación que primero se le ocurre a cualquiera, que es suponer que nadie había mirado. Sí se había mirado, y mucho: esta materia atrajo durante décadas a investigadores excelentes, generó discusiones técnicas de gran finura y produjo implementaciones que millones de personas usaron a diario. La pregunta no es por qué nadie prestó atención, sino por qué una atención tan intensa y tan competente se dirigió íntegramente a una sola de las dos propiedades que hacían falta.

La primera y la tercera se refuerzan entre sí de un modo especialmente eficaz, y conviene verlo con claridad porque el mecanismo se reproduce en cualquier proyecto con buena cobertura de pruebas. Cuando el criterio de corrección coincide exactamente con el oráculo de las pruebas, el sistema entra en un bucle cerrado: se prueba lo que se demostró, se demuestra lo que se prueba, y todo el aparato de verificación queda orientado hacia el interior. El resultado es una sensación de solidez perfectamente fundada dentro de ese perímetro y perfectamente vacía fuera de él. Un proyecto con una cobertura del cien por cien sobre la propiedad equivocada no está mejor situado que uno sin pruebas: está peor, porque tiene además una razón para no mirar.

La segunda merece un párrafo más, porque es la que mejor explica la duración. La comunidad de la transformación operacional venía enunciando desde finales de los noventa una terna de propiedades deseables en la que, junto a la convergencia y a la preservación de la causalidad, figuraba la preservación de la intención. Es decir: el hueco estaba señalado, tenía nombre y todo el mundo estaba de acuerdo en que hacía falta. Lo que no tenía era definición. Al no existir un enunciado formal, cada autor podía afirmar de buena fe que su algoritmo preservaba la intención sin que nadie pudiese contrastarlo, y ninguna implementación podía fallar esa propiedad porque no había manera de fallarla. Un requisito sin predicado no es un requisito débil: es una casilla que se marca sola.

Merece la pena apurar la ironía, porque es aleccionadora. De las tres propiedades de aquella terna, dos estaban formalizadas y una no, y precisamente la que no lo estaba era la única que hablaba de las personas. Las dos formalizadas se demostraron, se compararon entre algoritmos y se convirtieron en el eje de veinte años de literatura; la tercera se citaba en la introducción de cada artículo y desaparecía antes de la primera definición. No es que nadie la considerase importante: es que no había forma de trabajar con ella, y en una disciplina que avanza demostrando, lo que no se puede demostrar no se puede debatir y acaba funcionando como decoración.

Y hay un efecto perverso adicional que conviene nombrar. Tener la propiedad enunciada en prosa fue, probablemente, peor que no tenerla en absoluto. Su presencia en los textos daba la impresión de que la cuestión estaba contemplada y de que alguien, en algún sitio, la estaba vigilando. Un hueco declarado y no cubierto se comporta como un hueco tapado con una lona: desde arriba parece suelo, y por eso nadie mira dónde pisa.

Conviene además notar que la falta de definición no era un descuido subsanable con un poco más de esfuerzo. Formalizar la preservación de la intención en su forma general es genuinamente difícil, porque exige decir qué es la intención de alguien, y eso no es una noción matemática. El avance de 2019 consistió en parte en abandonar esa ambición: en lugar de definir la intención, se identificó un comportamiento concreto que la contradice de forma manifiesta y se le puso nombre. Rebajar la pregunta fue lo que la volvió respondible.

La cuarta razón es sociológica y no debería descartarse por serlo. La intercalación tiene la propiedad desafortunada de parecerse mucho a un accidente de coordinación entre personas. Quien encuentra el texto revuelto no piensa en la función de fusión de la biblioteca de secuencias: piensa que su compañero estaba escribiendo ahí a la vez, se encoge de hombros, lo reescribe y sigue trabajando. El fallo tiene, por así decirlo, una tapadera humana perfecta, y esa tapadera impidió durante años que los incidentes se agregaran en ningún sitio donde alguien pudiera contarlos.

Puestas las cuatro razones en orden temporal, la historia se lee como una cadena en la que cada eslabón tapa al siguiente:

1989-1998   se define el problema como fusionar operaciones de un caracter
1998        se enuncia la preservacion de la intencion sin darle predicado
2000s       llegan los tipos de dato replicados con demostraciones de convergencia
2010s       las implementaciones se despliegan y los usuarios arreglan a mano
2019        se nombra la anomalia y se constata que ninguna teoria la prohibia

Léela de abajo arriba y verás que ninguna etapa fue negligente: cada una hizo bien lo que la anterior le había dejado planteado. Lo que no hizo ninguna fue volver al primer renglón y preguntar si el problema estaba bien recortado, porque para cuando la duda habría sido productiva, ese renglón ya era el suelo sobre el que todos caminaban.

Hay un detalle en esa cronología que conviene no pasar por alto y que es el más incómodo de todos. El renglón de 2010, el de los usuarios arreglando el texto a mano, no describe una etapa fallida sino una etapa de éxito comercial: son los años en que la edición colaborativa se volvió una función esperada en cualquier herramienta y en que estas técnicas demostraron su valor práctico a gran escala. El fallo convivió sin fricción con la adopción masiva, y lo hizo porque su coste se pagaba en un sitio donde nadie lo estaba midiendo, que es el tiempo de las personas rehaciendo trabajo.

Lo que quedó sobre la mesa

El efecto inmediato del artículo no fue arreglar nada, y esto es importante para entender qué tipo de progreso supuso. Un taller de una jornada no despliega correcciones en las bibliotecas del mundo. Lo que hizo fue mover una cuestión de sitio: sacar la ausencia de intercalación del terreno de las expectativas informales sobre lo que un editor debería hacer y meterla en el terreno de las propiedades que un algoritmo tiene o no tiene, y que por tanto se pueden enunciar, comparar y exigir.

Ese traslado cambia además quién carga con la prueba, que es probablemente su efecto más duradero. Antes, quien encontraba el texto revuelto tenía que argumentar que aquello era un fallo, y le costaba, porque el algoritmo cumplía todo lo que decía cumplir y el interlocutor podía responder con una demostración. Después, quien publica un algoritmo de secuencias tiene que decir si respeta la contigüidad de las aportaciones concurrentes, y el silencio sobre ese punto pasa a ser informativo. La misma situación de hecho, con la carga de la prueba invertida, produce comportamientos opuestos en toda la comunidad.

A partir de ahí surgen tres preguntas que antes ni siquiera estaban bien planteadas, y que ocupan el resto de este nivel y el siguiente. La primera es de diagnóstico: qué algoritmos concretos intercalan, bajo qué condiciones y con qué gravedad, que es lo que verá la lección cuarta. La segunda es de especificación: cómo se enuncia formalmente que dos secuencias concurrentes no deben entrelazarse, sin que el enunciado sea tan fuerte que ningún algoritmo pueda satisfacerlo ni tan débil que no prohíba nada. La tercera es de construcción: qué algoritmos satisfacen ese enunciado y a qué precio. Las tres son ahora preguntas técnicas ordinarias, con respuestas comprobables y con criterios para comparar candidatos, y esa normalidad es justamente lo que el artículo aportó: antes de él, ninguna de las tres se podía formular sin empezar explicando qué se quería decir.

Fíjate en el orden, porque no es arbitrario y es el reverso exacto de cómo se había trabajado hasta entonces. Durante veinte años la secuencia fue construir primero, demostrar después y descubrir el requisito al final, por la vía de que a los usuarios les pasara algo raro. La secuencia que el artículo hace posible es la inversa: enunciar primero qué es inaceptable, comprobar después qué algoritmos existentes lo respetan y construir por último los que hagan falta. No es un detalle de método. Un requisito descubierto al final solo puede atenderse con parches sobre una arquitectura que no lo contemplaba; un requisito enunciado al principio participa en las decisiones de diseño que lo harían fácil de cumplir.