He estado obsesionado con la corrección de algún código sin cerradura, y agradecería cualquier aporte que pueda obtener. Mi pregunta es acerca de cómo lograr la sincronización entre hilos requerida mediante la adquisición de la semántica de la versión & en el modelo de memoria de C++ 11. Antes de mi pregunta, algunos antecedentes ...Sincronización de lector/escritor sin cerradura en la implementación de MVCC
En MVCC, un escritor puede instalar una nueva versión de un objeto sin afectar a los lectores de versiones de objetos antiguos. Sin embargo, si un escritor instala una nueva versión de un objeto cuando un lector con una marca de tiempo de mayor numeración ya ha adquirido una referencia a una versión anterior, la transacción del escritor deberá revertirse & reintentada. Esto es para preservar el aislamiento de instantáneas serializables (por lo que es como si todas las transacciones exitosas se ejecutaran una tras otra en orden de fecha y hora). Los lectores nunca tienen que volver a intentarlo debido a las escrituras, pero los escritores pueden tener que revertirse & si su actividad "sacará el tapete" de los lectores con marcas de tiempo de mayor numeración. Para implementar esta restricción, se utiliza una marca de tiempo de lectura . La idea es que un lector actualice la marca de tiempo de lectura de un objeto a su propia marca de tiempo antes de adquirir una referencia, y un escritor verificará la marca de tiempo de lectura para ver si está bien proceder con una nueva versión de ese objeto.
Supongamos que hay dos transacciones: T1 (el escritor) y T2 (el lector) que se ejecutan en hilos separados.
T1 (el escritor) hace esto:
void
DataStore::update(CachedObject* oldObject, CachedObject* newObject)
{
.
.
.
COcontainer* container = oldObject->parent();
tid_t newTID = newObject->revision();
container->setObject(newObject);
tid_t* rrp = &container->readRevision;
tid_t rr = __atomic_load_n(rrp, __ATOMIC_ACQUIRE);
while (true)
{
if (rr > newTID) throw TransactionRetryEx();
if (__atomic_compare_exchange_n(
rrp,
&rr,
rr,
false,
__ATOMIC_RELEASE,
__ATOMIC_RELAXED)
{
break;
}
}
}
T2 (el lector) hace esto:
CachedObject*
Transaction::onRead(CachedObject* object)
{
tid_t tid = Transaction::mine()->tid();
COcontainer* container = object->parent();
tid_t* rrp = &container->readRevision;
tid_t rr = __atomic_load_n(rrp, __ATOMIC_ACQUIRE);
while (rr < tid)
{
if (__atomic_compare_exchange_n(
rrp,
&rr,
tid,
false,
__ATOMIC_ACQUIRE,
__ATOMIC_ACQUIRE))
{
break;
}
}
// follow the chain of objects to find the newest one this transaction can use
object = object->newest();
// caller can use object now
return object;
}
Se trata de un simple resumen de la situación que me preocupa:
A B C
<----*----*----*---->
timestamp order
A: old object's timestamp
B: new object's timestamp (T1's timestamp)
C: "future" reader's timestamp (T2's timestamp)
* If [email protected] reads [email protected], [email protected] must be rolled back.
Si T1 se ejecuta por completo antes de que comience T2 (y los efectos de T1 son completamente visibles para T2), entonces no hay problema. T2 adquirirá una referencia a la versión de objeto instalada por T1, que puede usar porque la marca de tiempo de T1 es menor que la de T2. (Una transacción puede leer objetos "del pasado" pero no puede "mirar hacia el futuro").
Si T2 se ejecuta por completo antes de que comience T1 (y los efectos de T2 son completamente visibles para T1), entonces no hay problema. T1 verá que una transacción "desde el futuro" potencialmente ha leído la versión anterior del objeto. Por lo tanto, se revertirá T1 y se creará una nueva transacción para volver a intentar el rendimiento del trabajo.
El problema (por supuesto) es garantizar un comportamiento correcto cuando T1 y T2 se ejecutan al mismo tiempo. Sería muy simple usar un mutex para eliminar las condiciones de carrera, pero solo aceptaría una solución con bloqueos si estuviera convencido de que no había otra manera. Estoy bastante seguro de que debería ser posible hacer esto con los modelos de memoria de liberación & de C++ 11. Estoy de acuerdo con cierta complejidad, siempre y cuando pueda estar satisfecho de que el código sea correcto. Realmente quiero que los lectores corran lo más rápido posible, que es una característica principal de venta de MVCC.
Preguntas:
1. mirar el código anterior (parcial), ¿cree que existe una condición de carrera, por lo que T1 podría dejar de ser revertido (a través de throw TransactionRetryEx()) en un caso donde T2 procede a usar la versión anterior del objeto?
2. Si el código es incorrecto, explique por qué y proporcione una guía general para hacerlo bien.
3. Incluso si el código parece correcto, ¿puede ver cómo puede ser más eficiente?
Mi razonamiento en DataStore::update() es que si la llamada a __atomic_compare_exchange_n() tiene éxito, significa que el "conflicto" hilo lector aún no ha actualizado la marca de tiempo de leer, y por lo tanto también no ha atravesado la cadena de versiones de objetos para encontrar la versión recién accesible que acaba de instalar.
Estoy a punto de comprar el libro "Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery", pero pensé que también te molestaría: DI creo que debería haber comprado el libro antes, pero también estoy bastante seguro de que no aprenderé nada que invalide una gran parte de mi trabajo.
Espero haber dado suficiente información para hacer posible una respuesta. Con mucho gusto editaré mi pregunta para dejarla más clara si recibo críticas constructivas al respecto. Si esta pregunta (o una muy similar) ya ha sido respondida &, sería genial.
Gracias!
¿Qué nivel de aislamiento de transacción está buscando realmente? –
Aislamiento serializable (no el nivel de aislamiento "read committed" como en PostgreSQL, por ejemplo). –
¿Cuál es exactamente el papel de COcontainer, contiene todos los objetos o solo todas las versiones de un objeto dado? ¿Qué tipo de bloqueo o manejo sin cerradura usa? ¿Cómo se generan los id. De transacción/marcas de tiempo, con un contador? –