50 años después, ¿sigue siendo Two-Phase Locking la mejor opción?

• Two-Phase Locking (2PL), presentado en 1976, ofrece Opacity, una propiedad más fuerte que la serializabilidad, pero casi 50 años después sigue teniendo límites en escalabilidad de lectura y garantías de progreso
• Con reglas simples para adquirir y liberar locks, permite manejar transacciones sobre múltiples registros con niveles de aislamiento fuertes, por lo que sigue usándose ampliamente en bases de datos transaccionales comerciales y estructuras de datos concurrentes
• El 2PL tradicional puede hacer que incluso las lecturas entre sí entren en conflicto por usar locks de exclusión mutua, y aun con un reader-writer lock aparecen contenciones del read-indicator en puntos con muchas lecturas, como la raíz de un árbol binario de búsqueda
• 2PLSF distribuye las marcas por reader en distintas líneas de caché para reducir la contención al adquirir locks de lectura, y aplica el fetch_and_add() de un contador atómico central solo a las transacciones que realmente entran en conflicto
• Variantes de 2PL como No-Wait, Deadlock-detection y Wait-Or-Die siguen teniendo problemas de live-lock o escalabilidad, mientras que 2PLSF apunta a mejorar a la vez la escalabilidad de lectura y las transacciones libres de inanición

---

Por qué 2PL sigue siendo importante

• Two-Phase Locking (2PL) fue uno de los primeros controles de concurrencia de propósito general en ofrecer serializabilidad, y en la práctica brinda un nivel de aislamiento aún más fuerte: Opacity
• 2PL fue publicado en 1976 en un artículo de Jim Gray y sus colegas, y es posible que la idea existiera desde antes, por lo que se trata como una técnica de casi 50 años
• Un control de concurrencia de propósito general se refiere a un algoritmo que permite transacciones con semántica all-or-nothing sobre varios objetos, registros, tuplas u otros elementos de datos
• La ventaja de 2PL está en su simplicidad y su fuerte aislamiento
  • Antes de leer o escribir un registro, primero se adquiere el lock que protege ese registro
  • Los locks adquiridos se mantienen hasta que la transacción termina, lo que permite construir una vista consistente

El aislamiento que producen reglas simples

• En 2PL, se adquiere un lock en cada acceso durante la transacción y todos los locks se liberan al final, cuando la transacción sabe que ya no hará más accesos
• En ese momento final, todos los locks de los datos accedidos están tomados, por lo que aparece un punto de linearización (linearization point) para esa transacción
• Hace 50 años, muchos investigadores de bases de datos pensaban que se podía liberar el lock inmediatamente después de terminar de acceder a un registro, pero ese tipo de control de concurrencia no es serializable
• Las bases de datos transaccionales comerciales conocidas usan 2PL o combinaciones con T/O y MVCC
• En el campo de las estructuras de datos concurrentes, linearizability es casi un estándar, y para escribir de forma consistente sobre múltiples nodos normalmente se necesita un enfoque como 2PL para los accesos de escritura
  • La excepción son las estructuras de datos lock-free, aunque se recalca que implementarlas correctamente es difícil

Los cuellos de botella de 2PL: escalabilidad de lectura y live-lock

• Las grandes debilidades de 2PL son la falta de escalabilidad en lectura y las garantías de progreso frente al live-lock
• El 2PL clásico está diseñado alrededor de locks de exclusión mutua, así que incluso si dos hilos solo leen el mismo registro, pueden entrar en conflicto y uno o ambos pueden abortar y reiniciar
• Si se cambia por un reader-writer lock, se reducen los conflictos entre lecturas, pero aumentan el costo del lock y el uso de memoria
  • Un lock de exclusión mutua puede implementarse con 1 bit que indique si está bloqueado o desbloqueado
  • Un reader-writer lock necesita, además de ese bit, un contador para llevar el número de readers que actualmente tienen el lock en modo lectura
  • Por ejemplo, un contador de 7 bits puede representar hasta 128 hilos, y cada lock podría ocupar 1 byte
  • Si una base de datos tiene miles de millones de registros, solo los locks pueden requerir miles de millones de bytes
• Un problema aún mayor es la contención del contador
  • En cargas de trabajo read-non-disjoint, muchas lecturas se concentran sobre los mismos datos
  • El nodo raíz de un árbol binario de búsqueda es un ejemplo típico, porque toda operación debe leerlo antes de bajar a nodos inferiores
  • En 2PL, cada acceso a la raíz requiere adquirir un lock, y aun usando reader-writer locks aparece una contención severa sobre el lock del nodo raíz

Enfoques previos y el read-indicator escalable

• TLRW fue un enfoque presentado por Dave Dice y Nir Shavit en SPAA 2010; usa reader-writer locks para mejorar el rendimiento frente a locks de exclusión mutua, aunque no llega a ser tan rápido como el control de concurrencia optimista
• Si, de forma similar a TLRW, se aplica a un árbol binario de búsqueda AVL relajado por ranking una implementación donde cada acceso de lectura compite sobre una única variable del reader-writer lock, la escalabilidad tiende a aplanarse tanto en transacciones de escritura como de lectura
• La contención del read-indicator puede aliviarse con un read-indicator escalable
  • La forma preferida es un reader-writer lock donde cada reader marca su llegada y salida en una línea de caché separada
  • Así, adquirir un lock de lectura deja de tener contención
  • El hilo que intenta obtener un lock de escritura debe escanear todas las líneas de caché para verificar si puede entrar, así que el costo de adquirir el lock de escritura aumenta
• Los NUMA Aware reader-writer locks estudian algoritmos de reader-writer lock que usan esta técnica
  • Dos de los tres algoritmos de reader-writer lock tienen alta escalabilidad, pero no son starvation-free

El diseño del reader-writer lock en 2PLSF

• Two-Phase Locking Starvation-Free (2PLSF) es un control de concurrencia implementado con un reader-writer lock que escala bien al adquirir locks de lectura y además tiene propiedades adicionales
• El reader-writer lock de 2PLSF reserva 1 bit por hilo para el read-lock
  • Esos bits se colocan en sus propias líneas de caché
  • Se ubican junto con los bits de read-indicator de locks adyacentes
• Igual que en el artículo sobre reader-writer locks NUMA-aware, el costo se desplaza hacia la adquisición del lock de escritura
  • El lock de escritura debe escanear múltiples líneas de caché
  • No es una solución mágica, sino un trade-off
• Este trade-off es útil porque la mayoría de las cargas de trabajo tienden a ser read-heavy, e incluso las cargas write-intensive pasan una parte considerable del tiempo en accesos de lectura, como la etapa de búsqueda de registros
• Con este reader-writer lock mejorado, 2PL puede escalar incluso en cargas read-non-disjoint, pero el problema del live-lock debe resolverse aparte

Los problemas de garantía de progreso que dejan las variantes de 2PL

• El 2PL clásico tiene variantes conocidas como No-Wait, Deadlock-detection y Wait-Or-Die, según cómo manejen la contención

• No-Wait

  • Si ocurre un conflicto, se aborta la transacción propia o la transacción opuesta y luego se vuelve a intentar
  • El reintento puede hacerse de inmediato o más tarde con backoff exponencial
  • Si una transacción quiere modificar el registro A y luego B, y otra quiere modificar B y luego A, ambas pueden seguir chocando y repetir abort-restart sin llegar a commit, por lo que solo tienen progreso tipo live-lock

• Deadlock-detection

  • Se mantiene una lista de hilos en espera en cada lock y se detectan ciclos, es decir, deadlocks
  • En un reader-writer lock, cada reader debe tener su propia lista, y también hace falta un lock de exclusión mutua para proteger cada lista
  • Como al tomar el lock en modo lectura hay que escanear todas las listas de readers, el costo crece
  • En teoría podría lograrse starvation-free, pero eso requeriría un lock starvation-free, y no existen reader-writer locks starvation-free de alta escalabilidad publicados, lo que entra en conflicto con ese objetivo
  • Además, tener una lista por reader puede aumentar mucho el uso de memoria

• Wait-Or-Die

  • Se asigna un orden a todas las transacciones y, cuando hay un conflicto de locks, se comparan el timestamp de la transacción y el timestamp del dueño del lock para decidir si espera o aborta
  • Con locks de exclusión mutua esto funciona bien porque puede guardarse el dueño dentro del lock como un identificador único de hilo
  • Para hacer lo mismo en un reader-writer lock, haría falta un thread-id por cada reader
  • Para soportar 256 hilos, se necesitarían 8 bits × 256 = 256 bytes por cada reader-writer lock

El cuello de botella del contador atómico central y la diferencia de 2PLSF

• El obstáculo más grande de Wait-Or-Die es que toda transacción debe tener un ID único de transacción
  • Por ejemplo, puede obtenerse un número usando fetch_and_add() sobre una variable atómica central para establecer el orden
• En la mayoría de los CPU modernos, es difícil realizar más de 40 millones de operaciones fetch_and_add() por segundo sobre una variable atómica en contención
  • Comparado con los aproximadamente 660 millones de transacciones diarias de Visa, puede sonar grande
  • Pero para un DBMS en memoria o para estructuras de datos concurrentes puede no ser suficiente
  • En una máquina de prueba, era difícil superar los 20 millones de fetch_and_add() por segundo
• Este fetch_and_add() se necesita no solo para transacciones de escritura, sino para todas las transacciones, incluidas las de lectura, y eso limita la escalabilidad
• TL2 hace lecturas optimistas sin que las transacciones de lectura usen un fetch_and_add() atómico
  • Puede escalar a cientos de millones de tps desde la perspectiva de las transacciones de lectura
  • En cambio, un 2PL basado en Wait-Or-Die no puede superar los 40M tps/sec
• 2PLSF asigna orden solo a las transacciones que realmente entran en conflicto
  • Se reduce el número de transacciones que hacen fetch_and_add() sobre la variable atómica central
  • Las transacciones sin conflicto no quedan atadas a la meseta de 40M tps
  • Por ejemplo, podrían ejecutarse 200M tps sin conflicto, mientras que solo 40M tps en conflicto quedarían limitados por el tope de fetch_and_add()
  • El algoritmo ofrece starvation-freedom

Materiales y evaluación final

• El algoritmo 2PLSF en sí no se explica en detalle, pero se lo evalúa como relativamente simple para tratarse de un algoritmo starvation-free
• Se ofrecen como referencia el paper y el código fuente
  • Paper: https://zenodo.org/record/7886718
  • Código fuente: https://github.com/pramalhe/2PLSF/blob/main/stms/2PLSF.hpp
• 2PLSF también aparece vinculado a un paper de ACM, y se resume como un algoritmo creado por Pedro Ramalhete, Andreia y Pascal Felber
• El objetivo de 2PLSF se acerca a las propiedades que 2PL debió haber tenido desde el principio
  • Escala bien incluso en situaciones read-non-disjoint donde las lecturas se superponen
  • Ofrece transacciones libres de inanición, la forma más fuerte de progreso dentro del blocking progress
  • Puede mantener escalabilidad incluso en algunos escenarios con conflicto
• 2PLSF no es perfecto, pero se lo considera mejor que TL2 en resolución de conflictos, y la diferencia frente al 2PL tradicional se compara con la diferencia entre un pico y un martillo neumático

[GN⁺]

Opiniones de Hacker News

• Soy principiante en este tema, pero me parece interesante, y me gustaría que hubiera una solución de consistencia fácil de desplegar.
  Me pregunto cuáles son las mejores prácticas de la industria para sincronizar varios almacenes de datos, o mantenerlos “consistentes”, en una arquitectura de microservicios distribuida.
  Hace unos días intenté resolver un problema de inconsistencias con un “settled timestamp”; se parece a un enfoque multiversión en el que, si pasa el tiempo sin reportes de error, se considera un guardado/commit válido. En un commit de dos fases, la segunda fase sería el tiempo.
  La idea era vigilar el reloj de otros servidores y, si no se actualiza, no confiar en el settled timestamp de ese servidor; y como en cada actualización no hay que esperar una respuesta, sino solo el siguiente intervalo de timestamp, la intención era escalar la consistencia a muchos servidores.
  Hice código Python multihilo y multiproceso para probar la no determinación con 10 hilos que se envían actualizaciones aleatorias entre sí: https://replit.com/@Chronological/InconsistencySimulation#ma...
  En esta simulación, una lectura es el mínimo de todos los timestamps reportados por todos los servidores; si después de 10 segundos se le pregunta a cada hilo por el valor del contador, a veces todos dan el mismo valor, pero con bastante frecuencia termina en estado de split-brain.
  Sé que, en sistemas distribuidos, los timestamps de wall clock no son adecuados para decidir el orden, y que hay que usar relojes lógicos o relojes vectoriales.
  Me gustaría poder hacer que, en cualquier momento dado, la simulación reporte el mismo número en todos lados. Bloomlang intenta resolver el problema de que, en la consistencia eventual, los valores que llegan tarde afectan el resultado y por eso no es linealizable.
  Me interesa especialmente escalar manteniendo la consistencia, pero parece un problema bastante difícil.
  • La mejor práctica de la industria es no usar una arquitectura de microservicios distribuida.
  • La idea central de los sistemas distribuidos es tener un journal central de orden de escrituras que cada nodo reproduce.
    Varios sistemas escriben de forma secuencial en el journal central, y el journal recibe solicitudes como si fuera un almacén clave-valor. Ese journal se replica en todos los nodos, y los nodos leen el journal para ejecutar la lógica compleja solicitada.
  • Conviene reevaluar si realmente necesitas tanto (a) almacenes de datos distribuidos como (b) consistencia sincrónica. Si abandonas cualquiera de las dos cosas, todo se vuelve mucho más simple.
  • Creo que en un plazo de 5 años TigerBeetle DB se convertirá en el estándar de la industria para bases de datos distribuidas consistentes, de alto throughput y tolerantes a fallos.
  • Mira el protocolo Raft. En general, el estándar no es intentar integrarlo directamente en la capa de protocolo, sino usar un almacén consistente como etcd, que implementa Raft, para la coordinación/datos que deben ser serializables.
    Como Kubernetes usa etcd, escala bastante bien como almacén clave-valor con consistencia fuerte.
    Como dijiste “varios almacenes de datos”, asumo que tienes datos heterogéneos y que opciones como CockroachDB no aplican.
    Si eres principiante, hacerlo tú mismo es riesgoso. https://aphyr.com/ es una especie de referencia para pruebas y también es excelente como material educativo. Puedes probar sistemas distribuidos con Jepsen, pero es mejor usar un almacén de datos que Kyle haya demostrado que es robusto.
• Me pregunto cómo se compara este nuevo enfoque con el aislamiento de snapshots serializable (SSI): https://wiki.postgresql.org/wiki/SSI
  No estoy familiarizado con estas técnicas, pero cuando estudié bases de datos, SSI se presentaba como el “mejor” bloqueo de dos fases del futuro. Me pregunto en qué se diferencia SSI de 2PLSF y por qué no se mencionó aquí.
  • Estoy creando el modelo de memoria de una nueva plataforma, y casi todo está diseñado alrededor de copy-on-write, snapshots y SSI.
    Pero para efectos distribuidos siguen siendo necesarios los locks, las transacciones de dos fases, etc. Personalmente, los veo más como funcionalidades complementarias que como sustitutos.
• Los algoritmos de bloqueo son excelentes, pero antes de aplicarlos es importante dar un paso atrás y preguntarse si de verdad tantos hilos tienen que pelear por el mismo recurso.
  Si se trata de una estructura de datos en memoria, es natural; pero si estás trabajando con una base de datos externa u otro recurso externo compartido, quizá haya una mejor forma.
  A menudo puedes procesar solicitudes en lotes para acceder al recurso externo con menor concurrencia y payloads más grandes. Si ese recurso maneja bien los lotes, la concurrencia y los locks necesarios se reducen mucho.
  Por ejemplo, si usas Postgres, puede disminuir el número de conexiones y quizá no tengas que agregar PgBouncer, que aumenta la complejidad.
  Dicho eso, el batching de solicitudes no encaja bien con la mayoría de los lenguajes de programación. Los lenguajes optimizados para alta concurrencia, como los canales de Go o los procesos de Elixir, pueden hacerlo bien, pero en lenguajes que manejan todo con hilos puede ser doloroso.
• El paper de 2PLSF donde el autor sostiene que 2PL debió haber sido así originalmente: https://zenodo.org/record/7886718
• De verdad necesitamos una nueva política que exija que todos los enlaces que se suben a HN sean enlaces HTTPS.
  • ¿Por qué tendría que ser así? Hay muchos sitios antiguos y útiles que funcionan bien con HTTP. Si te refieres a casos en los que el sitio soporta HTTPS pero se publica un enlace HTTP, estoy de acuerdo.
  • Me pregunto cuáles son las consecuencias de visitar un enlace HTTP en lugar de HTTPS en un sitio con el que solo interactúas en modo de lectura. ¿Es un problema de seguridad, o de privacidad?
  • Basta con ejecutar Firefox en modo solo HTTPS: https://support.mozilla.org/en-US/kb/https-only-prefs
    En los sitios que no se pueden actualizar a HTTPS aparece una advertencia, y los sitios que soportan ambos te llevan directamente a la versión HTTPS.
  • ¿Esa fue la observación no relacionada que te vino a la mente después de leer un artículo sobre algoritmos de concurrencia?
    Y si el enlace HTTP trata sobre un buen algoritmo de concurrencia, igual lo leería.
  • Todavía quedan algunos sitios web solo HTTP.
• ¿De verdad se necesita fetch_and_add para obtener un ID de transacción en Wait-Or-Die? Para empezar, incluso dudo que haga falta un ID de transacción.

El objetivo parece ser establecer un orden arbitrario pero consistente entre las transacciones activas para que, cuando haya un conflicto, puedan ponerse de acuerdo sobre quién espera y quién muere. Entonces, ¿no se podría usar el ID del hilo?
Un número aleatorio también podría servir. Si los empates se tratan como “muerte”, en el peor de los casos ambas transacciones se interrumpen innecesariamente y simplemente se reintentan con un nuevo número aleatorio.
No se menciona, pero parece que se busca dar prioridad a las transacciones más antiguas para que las de larga duración no sufran inanición frente a las cortas. Por ejemplo, si una transacción larga choca en promedio con tres transacciones cortas, y en cada conflicto el ganador es prácticamente aleatorio, la probabilidad de que la transacción larga gane las tres veces y haga commit es de solo 1/8.
Pero para evitar la inanición no hace falta priorizar siempre a la transacción más antigua; basta con hacerlo en la mayoría de los casos. Especialmente si es apenas un poco más antigua.
Por eso, algo similar a un timestamp o un cycle counter puede funcionar bien aunque haya desfases de reloj entre hilos u otras imprecisiones. Los empates pueden resolverse con el ID del hilo o, de nuevo, haciendo que ambas partes aborten.

• En vez del ID del hilo, usaría ULID: https://github.com/ulid/spec
  Encaja bien en este caso y en muchos otros.
• Es un excelente paper que ofrece un marco para comparar el enfoque de dos fases con Paxos: https://lamport.azurewebsites.net/video/consensus-on-transac...
  • Aunque el nombre se superpone, el bloqueo de dos fases es distinto del commit de dos fases.
    El commit de dos fases sí es comparable con Paxos, y ambos entran en la categoría de protocolos de consenso.
    El bloqueo de dos fases es un mecanismo de control de concurrencia.
• Sigue para siempre y tampoco es nunca perfecto.
  Cuando se pierde el primer mensaje de bloqueo, el problema es cómo saber que lo que se perdió no fue el mensaje de respuesta.
  En casos simples, se puede simplemente avanzar como GitHub o Dropbox y resolver los conflictos después. Si es una base de datos, buena suerte; y si es un banco, con más razón.
• No entiendo bien la última figura del relaxed AVL tree. En el extremo derecho, con 100% de consultas, el algoritmo TL2 debería escalar linealmente con la cantidad de hilos.
  En una transacción de solo lectura, TL2 solo tiene que muestrear la versión global y luego comprobar, para cada lectura, que la versión local sea menor o igual que la versión muestreada.
  Entonces cuesta entender por qué el gráfico es sublineal y por qué TL2 no es tan rápido como otras implementaciones de STM.
  • No veo un gráfico así para TL2. En cambio sí veo un gráfico de TLRW, y TLRW usa reader lock, así que tiene límites de escalabilidad.
• Esto podría resolverse simplemente agregando una cola aleatorizada.
  Por ejemplo, supongamos que normalmente hay 1000 tareas y entre 10 y 100 hilos de hardware.
  Se crea una sola lista ordenada con las 1000 tareas, se hace una copia para cada hilo y luego se aleatoriza el orden de cada copia cada vez.
  Entonces cada hilo lee su propia lista y ejecuta las tareas, y luego se suscribe a una lista implementada como una cola multihilo no bloqueante.
  En el peor de los casos, algunos hilos podrían repetir ciertas tareas.
  Con este enfoque, las operaciones atómicas podrían escalar hasta 1000 veces.