¿Qué algoritmos / lectura le recomendarías para resolver transacciones / bloqueos de lectura-escritura?

10

Una transacción de base de datos clásica simplificada se puede ver como:

  • leyendo artículos M
  • realizar algunos cálculos basados ​​en esas lecturas
  • escribir algunos resultados de N basados ​​en estos cálculos, que pueden incluir los elementos leídos originalmente.

Al realizar estas transacciones (simultáneamente), las propiedades ACID deben mantenerse.

Exactamente los mismos requisitos (N actualizaciones basadas en M lecturas transaccionales) existen en otros sistemas concurrentes no DBMS.

Estoy interesado en descubrir qué algoritmos existen para realizar / resolver estas transacciones, y cuáles son las fortalezas y debilidades relativas de estos algoritmos. ¿Me puede recomendar alguna lectura? Esto podría ser libros o referencias / tutoriales en línea.

Aclaración:

Entonces, por ejemplo, un algoritmo ingenuo podría ser que cada transacción tome un solo bloqueo global, en efecto forzando un solo subproceso y eliminando la concurrencia. Un algoritmo un poco más complicado sería el bloqueo de lectura / escritura de elementos individuales, con una orden para evitar el punto muerto). Etc, etc. ¿Existe una buena fuente que documente varios algoritmos para resolver este problema? Incluso una respuesta que solo apuntara a un algoritmo único con sus fortalezas y debilidades sería útil.

Nick Fortescue
fuente
3
Esta pregunta ciertamente cae dentro del alcance de este sitio. Recomendaría escribir un poco más sobre el contexto en el que está trabajando. En la actualidad es bastante general y abierto.
Dave Clarke
¿Crees que vale la pena reformular, por lo que es precisamente la pregunta de la base de datos? Es decir, algo como "Tengo una base de datos que se puede leer y escribir, y quiero poder leer y escribir transaccionalmente con propiedades ACID. Qué algoritmos existen para garantizar estas propiedades"
Nick Fortescue
Reformular la pregunta puede dar como resultado respuestas más cercanas a lo que está buscando, como dar más detalles del problema que está tratando de resolver; actualmente solo das pistas. En cualquier caso, parece que está pidiendo algoritmos clásicos de transacción de base de datos.
Dave Clarke
@Dave - gracias, he editado. ¿Mejor?
Nick Fortescue el
1
¿Ya estás familiarizado con los libros de texto DBMS como el de Ramakrishnan y Gehrke? Y si no está preguntando sobre los aspectos internos de un DBMS, ¿puede aclarar la pregunta para hacernos saber la diferencia entre un DBMS y lo que le interesa?
Maverick Woo

Respuestas:

10

El libro Sistemas de información transaccional de Weikum y Vossen cubre gran parte del área, tanto en términos teóricos como prácticos, desde diferentes perspectivas, no solo transacciones. Tiene aproximadamente 1000 páginas, por lo que lo mantendrá ocupado durante un fin de semana o dos. Por otro lado, tiene casi 10 años, por lo que puede haber algo más actualizado disponible. Otros libros en la línea incluyen Control de concurrencia y recuperación en sistemas de bases de datos de Bernstein, P., Hadzilacos, V. y Goodman, N, Addison-Wesley, 1987, Procesamiento de transacciones: conceptos y técnicas de Jim Gray y Andreas Reuter, y Principios de procesamiento de transaccionespor Philip A. Bernstein y Eric Newcomer, 2009. No he visto el último, pero al ser el más reciente, podría ser un buen lugar para comenzar, aunque su solución puede encontrarse en textos anteriores. Un viaje a la biblioteca puede valer la pena.

Un texto monumental en esta área es Atomic Transactions por Nancy Lynch et al. Presenta una cuenta formal y pruebas de varios de los tipos de algoritmos que le interesan. Es bastante formal y tedioso, por lo que puede no ser de su agrado.

Una gran cantidad de trabajo reciente se dedica a la memoria transaccional de software , que aplica las ideas de transacción a aplicaciones de subprocesos múltiples. Hay decenas de publicaciones sobre este tema cada año: la página de wikipedia ofrece muchas referencias.

Dave Clarke
fuente
1
gracias, especialmente por la frase "Memoria transaccional de software", no me había encontrado con este nombre
Nick Fortescue el
1
STM es un tema muy candente en la investigación de lenguajes de programación en estos días. Hay una carrera para ver si los modelos de programación basados ​​en STM o Actor serán la base de futuros lenguajes de programación concurrentes (= todos).
Dave Clarke el
1
Además de STM, una palabra clave particular para buscar dentro de estas referencias es MVCC. Se usa en la mayoría de los DBMS modernos: en.wikipedia.org/wiki/Multiversion_concurrency_control
Maverick Woo
@supercooldave No estoy seguro de que sea una carrera: creo que los futuros idiomas tendrán que admitir un poco de ambos en algún grado u otro.
Marc Hamann el
@Marc Harmann: hablando metafóricamente.
Dave Clarke