Spanner: TrueTime y coherencia externa

TrueTime es un reloj distribuido con alta disponibilidad que se proporciona a las aplicaciones en todos los servidores de Google1. TrueTime permite que las aplicaciones generen marcas de tiempo que aumentan de forma monotónica: una aplicación puede calcular una marca de tiempo T que se garantiza que será mayor que cualquier marca de tiempo T' si T' terminó de generarse antes de que T comenzó a hacerlo. Esta garantía se mantiene en todos los servidores y todas las marcas de tiempo.

Spanner usa esta función de TrueTime para asignar marcas de tiempo a las transacciones. En particular, a cada transacción se le asigna una marca de tiempo que refleja el instante en el que Spanner considera que ocurrió. Debido a que Spanner usa el control de simultaneidad de varias versiones, la garantía de orden en las marcas de tiempo permite a los clientes de Spanner realizar lecturas coherentes en toda la base de datos (incluso en varias regiones de Cloud) sin bloquear las escrituras.

Coherencia externa

Spanner proporciona a los clientes las garantías de control de simultaneidad más estrictas para las transacciones, lo que se denomina coherencia externa2. Con la coherencia externa, el sistema se comporta como si todas las transacciones se ejecutaran de forma secuencial, aunque Spanner en realidad las ejecuta en varios servidores (y posiblemente en varios centros de datos) para obtener un mayor rendimiento y disponibilidad. Además, si una transacción finaliza antes de que otra transacción comience a confirmarse, el sistema garantiza que los clientes nunca podrán ver un estado que incluya el efecto de la segunda transacción, pero no de la primera. De manera intuitiva, Spanner no se puede distinguir semánticamente de una base de datos de una sola máquina. A pesar de que ofrece garantías tan sólidas, Spanner permite que las aplicaciones alcancen un rendimiento comparable al de las bases de datos que ofrecen garantías más débiles (a cambio de un rendimiento mayor). Por ejemplo, al igual que las bases de datos que admiten el aislamiento de instantáneas, Spanner permite que las operaciones de escritura continúen sin que las transacciones de solo lectura las bloqueen, pero sin mostrar las anomalías que permite el aislamiento de instantáneas.

La coherencia externa simplifica en gran medida el desarrollo de aplicaciones. Por ejemplo, supongamos que creaste una aplicación bancaria en Spanner y uno de tus clientes comienza con $50 en su cuenta corriente y $50 en su cuenta de ahorro. La aplicación inicia un flujo de trabajo en el que primero confirma una transacción T1 para depositar $200 en la cuenta de ahorro y, luego, emite una segunda transacción T2 para debitar $150 de la cuenta corriente. Además, supongamos que, al final del día, los saldos negativos en una cuenta se cubren de manera automática con otras cuentas, y un cliente recibe en una multa si el saldo total en todas sus cuentas es negativo en cualquier momento durante ese día. La coherencia externa garantiza que debido a que T2 comenzó a confirmarse después de que T 1 finalizara, todos los lectores de la base de datos observarán que el depósito T1 tuvo lugar antes del débito T2. Dicho de otro modo, la coherencia externa garantiza que nadie verá un estado en el que T2 ocurra antes de T1; en otras palabras, el débito nunca incurrirá en una multa debido a fondos insuficientes.

Una base de datos tradicional que usa almacenamiento de una sola versión y el bloqueo estricto de dos fases proporciona coherencia externa. Desafortunadamente, en ese sistema, cada vez que tu aplicación desea leer los datos más recientes (lo que denominamos "lectura sólida"), el sistema adquiere un bloqueo de lectura en los datos, que bloquea las escrituras en los datos que se leen.

Marcas de tiempo y control de simultaneidad de varias versiones (MVCC)

Para leer sin bloquear las escrituras, Spanner y muchos otros sistemas de bases de datos mantienen varias versiones de datos inmutables (a menudo llamadas control de simultaneidad de varias versiones). Una escritura crea una nueva versión inmutable cuya marca de tiempo es la de la transacción de escritura. Una “lectura de instantánea” en una marca de tiempo muestra el valor de la versión más reciente anterior a esa marca de tiempo y no necesita bloquear las escrituras. Por lo tanto, es importante que las marcas de tiempo asignadas a las versiones sean coherentes con el orden en el que se observa la confirmación de las transacciones. Esta propiedad se denomina “marca de tiempo correcta”. Ten en cuenta que la existencia de una marca de tiempo correcta es equivalente a la coherencia externa.

Para ver por qué es importante la marca de tiempo correcta, considera el ejemplo del banco de la sección anterior. Sin la marca de tiempo correcta, se podría asignar una marca de tiempo a T2 anterior a la marca de tiempo asignada a T1 (por ejemplo, si un sistema hipotético usó relojes locales en lugar de TrueTime, y el reloj del servidor que procesa T2 se retrasó un poco). Una lectura de instantánea podría reflejar el débito de T2, pero no el depósito de T 1, aunque el cliente haya visto el depósito finalizado antes de iniciar el débito.

Lograr marcar el tiempo de forma correcta es trivial para una base de datos de una sola máquina (por ejemplo, puedes asignar marcas de tiempo desde un contador global que aumenta de forma monotónica). Lograrla en un sistema ampliamente distribuido como Spanner, en el que los servidores de todo el mundo necesitan asignar marcas de tiempo, es mucho más difícil de hacerlo de manera eficiente.

Spanner depende de TrueTime para generar marcas de tiempo que aumentan monótonamente. Spanner usa estas marcas de tiempo de dos maneras. En primer lugar, las usa como marcas de tiempo correctas para las transacciones de escritura sin la necesidad de una comunicación global. En segundo lugar, las usa como marcas de tiempo para lecturas sólidas, lo que permite ejecutar lecturas sólidas en una serie de comunicación, incluso lecturas sólidas que abarcan varios servidores.

Preguntas frecuentes

¿Qué garantías de coherencia ofrece Spanner?

Spanner proporciona coherencia externa, que es la propiedad de coherencia más estricta para los sistemas de procesamiento de transacciones. Todas las transacciones en Spanner satisfacen esta propiedad de coherencia, no solo las de una partición. La coherencia externa indica que Spanner ejecuta transacciones de una manera indistinguible de un sistema en el que las transacciones se ejecutan en serie y, además, que el orden en serie es coherente con el orden en que se observa que se confirman. Dado que las marcas de tiempo generadas para transacciones corresponden al orden de la serie, si algún cliente ve una transacción T2 que comienza a confirmarse después de que otra transacción T1 termine, el sistema le asignará una marca de tiempo a T2 que será mayor que la marca de tiempo de T 1.

¿Spanner proporciona linealización?

Sí. De hecho, Spanner proporciona coherencia externa, que es una propiedad más sólida que la linealización, ya que esta no indica nada sobre el comportamiento de las transacciones. La instrucción atómica es una propiedad de objetos simultáneos que admiten operaciones atómicas de lectura y escritura. En una base de datos, un “objeto” suele ser una sola fila o incluso una sola celda. La coherencia externa es una propiedad de los sistemas de procesamiento de transacciones, en los que los clientes sintetizan de manera dinámica transacciones que contienen varias operaciones de lectura y escritura en objetos arbitrarios. La instrucción atómica se puede considerar como un caso especial de coherencia externa, en el que una transacción solo puede contener una única operación de lectura o escritura en un solo objeto.

¿Spanner proporciona serialización?

Sí. De hecho, Spanner proporciona coherencia externa, que es una propiedad más estricta que la serialización. Un sistema de procesamiento de transacciones se puede serializar si ejecuta transacciones de una manera que no se distingue de un sistema en el que las transacciones se ejecutan en serie. Spanner también garantiza que el orden de la serie sea coherente con el orden en que se observa la confirmación de las transacciones.

Vuelve a considerar el ejemplo del banco presentado en la sección anterior. En un sistema que proporciona serialización pero no coherencia externa, aunque el cliente haya ejecutado T1 y luego T2 de forma secuencial, el sistema podría reordenarlos, lo que podría hacer que el débito incurra en una multa debido a fondos insuficientes.

¿Spanner proporciona coherencia sólida?

Sí. De hecho, Spanner proporciona coherencia externa, que es una propiedad más sólida que la coherencia sólida. El modo predeterminado para las lecturas en Spanner es “strong”, lo que garantiza que se observarán los efectos de todas las transacciones confirmadas antes del inicio de la operación, independientemente de qué réplica reciba la lectura.

¿Cuál es la diferencia entre la coherencia sólida y la coherencia externa?

Un protocolo de replicación muestra “coherencia sólida” si los objetos replicados tienen instrucción atómica. Al igual que la instrucción atómica, la “coherencia sólida” es más débil que la “coherencia externa”, ya que no indica nada sobre el comportamiento de las transacciones.

¿Spanner proporciona coherencia eventual (o diferida)?

Spanner proporciona coherencia externa, que es una propiedad mucho más sólida que la coherencia eventual. La coherencia eventual intercambia garantías más débiles por un rendimiento más alto. La coherencia eventual es problemática porque significa que los lectores pueden observar la base de datos en un estado que nunca fue verdadero (p. ej., una lectura puede observar un estado en el que la Transacción B se confirmó, pero la Transacción A no, a pesar de que A ocurrió antes de B). Spanner proporciona lecturas inactivas, que ofrecen beneficios de rendimiento similares a los de la coherencia eventual, pero con garantías de coherencia mucho más sólidas. Una lectura inactiva muestra datos de una marca de tiempo “antigua”, que no puede bloquear escrituras porque las versiones anteriores de datos son inmutables.

Lecturas adicionales

Notas

  • 1J. C. Corbett, J. Dean, M. Epstein, A. Fikes, C. Frost, J. Furman, S. Ghemawat, A. Gubarev, C. Heiser, P. Hochschild, W. Hsieh, S. Kanthak, E. Kogan, H. Li, A. Lloyd, S. Melnik, D. Mwaura, D. Nagle, S. Quinlan, R. Rao, L. Rolig, Y. Saito, M. Szymaniak, C. Taylor, R. Wang y D. Woodford. Spanner: Google's Globally-Distributed Database (Spanner: La base de datos de Google distribuida de forma global de Google). En el décimo simposio de USENIX sobre implementación y diseño de sistemas operativos (OSDI 12), págs. 261-264, Hollywood, CA, octubre de 2012.
  • 2Gifford, D. K. Information Storage in a Decentralized Computer System (Almacenamiento de información en un sistema de procesamiento descentralizado). Tesis doctoral, Universidad de Stanford, 1981.