Cloud Spanner: TrueTime y coherencia externa

Beneficios de TrueTime para Cloud Spanner

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.

Cloud 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 que Cloud Spanner considera que se produjo. Debido a que Cloud Spanner usa el control de simultaneidad de varias versiones, la garantía de orden en las marcas de tiempo permite que los clientes de Cloud Spanner realicen lecturas coherentes en una base de datos completa (incluso en varias regiones de Cloud) sin bloquear escrituras.

Coherencia externa

Cloud 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 Cloud Spanner las ejecuta en varios servidores (y posiblemente en varios centros de datos) para mejorar el rendimiento y la 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, la semántica de Cloud Spanner no es diferente a la de una base de datos de una sola máquina. A pesar de que ofrece garantías tan sólidas, Cloud 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 mayor rendimiento). Por ejemplo, como las bases de datos que admiten el aislamiento de instantáneas, Cloud Spanner permite que las escrituras procedan sin bloquearse mediante transacciones de solo lectura, 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 Cloud Spanner y que 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 el bloqueo de dos fases estricto proporciona coherencia externa. Por desgracia, en este tipo de sistema, cada vez que tu aplicación quiere leer los datos más recientes (lo que llamamos “lectura sólida”), el sistema adquiere un bloqueo de lectura, lo que bloquea las escrituras en los datos leídos.

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

Para leer sin bloquear las escrituras, Cloud 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). Es más difícil lograr esto de manera eficiente en un sistema tan distribuido, como Cloud Spanner, en el que los servidores de todo el mundo necesitan asignar marcas de tiempo.

Cloud Spanner depende de TrueTime para generar marcas de tiempo que aumentan de forma monotónica. Cloud 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 proporciona Cloud Spanner?

Cloud Spanner proporciona coherencia externa, que es la propiedad de coherencia más estricta para los sistemas de procesamiento de transacciones. Todas las transacciones en Cloud Spanner satisfacen esta propiedad de coherencia, no solo las de una partición. La coherencia externa indica que Cloud Spanner ejecuta transacciones de un modo que no se distingue de un sistema en el que las transacciones se ejecutan en serie y, además, que el orden de la serie es coherente con el orden en que se observa su confirmación. 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.

¿Cloud Spanner proporciona instrucción atómica?

Sí. De hecho, Cloud Spanner proporciona coherencia externa, que es una propiedad más sólida que la instrucción atómica, porque esta última 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.

¿Cloud Spanner proporciona serialización?

Sí. De hecho, Cloud 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. Cloud Spanner también garantiza que el orden de la serie sea coherente con el orden en el 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.

¿Cloud Spanner proporciona coherencia sólida?

Sí. De hecho, Cloud Spanner proporciona coherencia externa, que es una propiedad más sólida que la coherencia sólida. El modo predeterminado de lectura en Cloud Spanner es “sólido”, lo que garantiza que se observen los efectos de todas las transacciones confirmadas antes del inicio de la operación, sin importar qué réplica recibe 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.

¿Cloud Spanner proporciona coherencia eventual (o diferida)?

Cloud 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). Cloud 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.