guide:consistency@es

Guías

Consistencia, instantáneas y zookies

Por qué un sistema de autorización tiene que respetar el orden de los cambios de ACL y de contenido, y cómo lo hace Zanzibar con las marcas de tiempo de Spanner y los zookies.

Datos verificados el Secciones del artículo §2.2, §2.4, §2.4.4, §3.2.1, §3.2.5, §4.1

Una comprobación de ACL responde a “¿puede este usuario hacer esto, ahora?”. En un sistema replicado por todo el mundo, “ahora” es lo difícil: servidores distintos han visto escrituras distintas. Esta página explica qué orden promete respetar Zanzibar, cómo Spanner hace que cumplir esa promesa resulte barato y cómo el zookie permite a un cliente fijar la frescura mínima que necesita una comprobación.

El problema del “nuevo enemigo”

El artículo abre §2.2 con una regla: “ACL checks must respect the order in which users modify ACLs and object contents to avoid unexpected sharing behaviors.” (Las comprobaciones de ACL deben respetar el orden en que los usuarios modifican las ACL y el contenido de los objetos para evitar comportamientos de compartición inesperados.) Al fallo lo llama el problema del “nuevo enemigo” (“new enemy”): un usuario al que se acaba de eliminar de una ACL sigue viendo contenido que la eliminación pretendía ocultar.

El artículo da dos ejemplos. Para estos dos, esta página conserva los nombres del propio artículo, Alice, Bob y Charlie, para que puedan leerse junto a §2.2; en todas las demás partes usa el ejemplo de referencia de Anne, Beto y Chen.

¿Qué puede salir mal si una comprobación ve el segundo cambio pero no el primero? La viñeta de la izquierda es un sistema sin orden; la de la derecha es la misma historia con Zanzibar.

Ejemplo A sin ordenAlice elimina a Bob de la ACL de la carpeta (A1) y luego se lo pide a Charlie, que mueve documentos nuevos a la carpeta (A2). La comprobación de Bob se evalúa con datos que incluyen A2 pero no A1, así que a Bob se le permite leer los documentos nuevos. Esta es la violación.tiempoT_A1T_A2AliceCharlieBobpideA1: elimina a Bobde la carpetaA2: mueve docsnuevos a la carpetala comprobaciónve A2 pero no A1Bob ve losdocs nuevos
Violación: la comprobación aplica A2 sin A1, y Bob lee los documentos nuevos.
Ejemplo A con ZanzibarA1 y A2 reciben las marcas de tiempo T_A1 menor que T_A2. Una comprobación en una instantánea anterior a T_A2 no ve los documentos en la carpeta. Una comprobación en una instantánea en T_A2 o posterior ve también A1, así que a Bob se le deniega el acceso en ambos casos.tiempoT_A1T_A2AliceCharlieBobpideA1: elimina a Bobde la carpetaA2: mueve docsnuevos a la carpetacomprobación enT < T_A2los docs aún noestán en la carpetacomprobación enT ≥ T_A2ve A1:Bob denegado
Zanzibar: toda instantánea que contiene A2 contiene también A1.

Obsérvese que no hay ninguna instantánea que contenga A2 pero no A1. Esa es toda la garantía: §2.2 explica que, si una comprobación se ejecuta en T < T_A2, “the document ACLs will not include the folder ACL” (las ACL de los documentos no incluirán la ACL de la carpeta), y si se ejecuta en T ≥ T_A2 > T_A1, “will observe update A1, which removed Bob from the folder ACL” (observará la actualización A1, que eliminó a Bob de la ACL de la carpeta).

El Ejemplo B difiere en un detalle: el segundo cambio afecta al contenido del documento, que reside en el almacenamiento de la aplicación cliente, no en Zanzibar. Zanzibar nunca ve esa escritura. ¿Cómo puede saber que una comprobación sobre el contenido nuevo tiene que ser lo bastante reciente?

Ejemplo B sin ordenAlice elimina a Bob de la ACL del documento (B1) y luego se lo pide a Charlie, que añade contenido nuevo (B2). La comprobación de Bob se evalúa en una instantánea obsoleta anterior a B1, así que sigue permitiendo el acceso a Bob, y Bob lee el contenido nuevo. Esta es la violación.tiempoT_B1T_B2AliceCharlieBobpideB1: elimina a Bobde la ACL del docB2: añadecontenido nuevocomprobación enT < T_B1 obsoletaBob ve elcontenido nuevo
Violación: se aplica una ACL antigua a contenido nuevo.
Ejemplo B con ZanzibarAlice elimina a Bob (B1). El cambio de contenido de Charlie recibe un zookie que codifica su marca de tiempo T_B2, almacenado con el contenido nuevo. La comprobación de Bob lleva ese zookie, así que se evalúa en una instantánea en T_B2 o posterior, que incluye B1, y a Bob se le deniega el acceso.tiempoT_B1T_B2AliceCharlieBobpidezookieB1: elimina a Bobde la ACL del docB2 + zookie(T_B2)la comprobaciónlleva el zookieve B1:Bob denegado
Zanzibar: el zookie almacenado con B2 obliga a usar una instantánea en T_B2 o posterior.

La flecha discontinua es la solución. El zookie viaja con el contenido, así que la comprobación sobre B2 no puede ejecutarse en una instantánea anterior a B2, y toda instantánea así ya contiene B1. El resto de la página explica las dos propiedades en las que se apoya esto y el protocolo que hace circular el zookie.

Marcas de tiempo con significado causal

§2.2 nombra dos propiedades: la consistencia externa y las lecturas de instantánea con desactualización acotada. Para la consistencia externa, el artículo cita la tesis de Gifford de 1981. El artículo de Spanner enuncia la misma propiedad para las transacciones: “if a transaction T1 commits before another transaction T2 starts, then T1’s commit timestamp is smaller than T2’s” (si una transacción T1 se confirma antes de que empiece otra transacción T2, la marca de tiempo de confirmación de T1 es menor que la de T2), y señala que esto es, “equivalently, linearizability” (de forma equivalente, linealizabilidad), citando a Herlihy y Wing (1990).

En palabras de Zanzibar (§2.2), dos actualizaciones causalmente relacionadas x ≺ y reciben marcas de tiempo con T_x < T_y. Una lectura de instantánea en la marca de tiempo T “observes all updates with timestamps ≤ T” (observa todas las actualizaciones con marcas de tiempo ≤ T). En conjunto: si una lectura ve y, ve también todo lo que ocurrió antes de y. Esto funciona porque el almacén es multiversión: Spanner define una lectura de instantánea como “a read in the past that executes without locking” (una lectura en el pasado que se ejecuta sin bloqueos) (Spanner §4.1), y en un almacén multiversión “each write on a data item produces a new copy (or version)” (cada escritura sobre un dato produce una nueva copia, o versión) (Bernstein y Goodman, 1983).

¿Qué ve un lector con esa regla, y qué puede ver el lector de una réplica con consistencia eventual? En esta variante, el readme empieza fuera de folder:A. Anne primero elimina a Chen como lector de folder:A (x, confirmada en T=10) y luego mueve doc:readme a folder:A (y, en T=20).

Lecturas de instantánea frente a una réplica con consistencia eventualLa escritura x elimina a Chen de folder:A en la marca de tiempo 10; la escritura y mueve doc:readme a folder:A en la marca de tiempo 20, y x ocurre antes que y. Una lectura de instantánea en T=15 solo ve x; una lectura de instantánea en T=25 ve x e y. Una réplica con consistencia eventual aplica y antes que x, y en ese intervalo Chen puede ver el readme.tiempoT=10T=20escrituras de ACLlectura de instantánearéplica eventualx ≺ yx: elimina a Chende folder:Ay: mueve el readmea folder:Ainstantánea en T=15:solo ve xla réplica tiene y,aún no xinstantánea en T=25:ve x e yChen ve el readme(x sin aplicar)
Una instantánea en cualquier T es un prefijo del orden causal. Una réplica eventual puede exponer y sin x hasta que se pone al día.

Obsérvese que las dos lecturas de instantánea difieren en cuánto ven, pero nunca en el orden: cada una es un prefijo de la historia. La réplica eventual también convergerá, pero hasta entonces puede mostrar un estado que nunca existió. El propio artículo establece este contraste en §5: TAO “offers eventual global consistency with asynchronous replication” (ofrece consistencia global eventual con replicación asíncrona), mientras que Zanzibar “provides external consistency and snapshot reads with bounded staleness” (proporciona consistencia externa y lecturas de instantánea con desactualización acotada).

De dónde vienen las marcas de tiempo: TrueTime

Zanzibar no calcula estas marcas de tiempo por sí mismo. Almacena las ACL en Spanner, cuyo “TrueTime mechanism assigns each ACL write a microsecond-resolution timestamp, such that the timestamps of writes reflect the causal ordering between writes” (mecanismo TrueTime asigna a cada escritura de ACL una marca de tiempo con resolución de microsegundos, de modo que las marcas de tiempo de las escrituras reflejan el orden causal entre ellas) (§2.2). El esquema de su funcionamiento está en §3, §4.1.2 y §4.2.1 del artículo de Spanner (OSDI ’12).

  • TT.now() devuelve un intervalo [earliest, latest] que contiene con garantía el tiempo absoluto en el que se llamó. La incertidumbre ε es la mitad de la anchura del intervalo; en el entorno de producción de Google era “typically a sawtooth function of time, varying from about 1 to 7 ms over each poll interval” (normalmente una función en diente de sierra del tiempo, que varía entre aproximadamente 1 y 7 ms en cada intervalo de sondeo).
  • Inicio: el líder asigna a una escritura una marca de tiempo de confirmación s no menor que TT.now().latest.
  • Espera de confirmación (commit wait): los clientes no pueden ver la escritura hasta que TT.after(s) sea verdadero, es decir, hasta que s haya pasado con certeza en todas partes. Spanner señala que “the expected wait is at least 2 ∗ ε̄” (la espera prevista es de al menos 2 ∗ ε̄), donde ε̄ es la cota de error media (§4.2.1).

¿Cómo hace la espera que las marcas de tiempo sean causales?

La espera de confirmación en SpannerUna escritura llega al líder, que llama a TT.now() y obtiene un intervalo de earliest a latest, de anchura 2 épsilon. El líder elige s igual a latest. Después espera hasta que TT.after(s) es verdadero, lo que lleva unos 2 épsilon, y solo entonces hace visible la escritura y responde. Toda transacción que empiece después de la respuesta llama a TT.now() más tarde, así que su latest, y por tanto su marca de tiempo, es mayor que s.earliestlatestllega la escrituraTT.now()s = latestTT.after(s)is trueescritura visible,cliente avisadosiguiente escritura:marca > sincertidumbre: 2εregla de inicioelige sespera deconfirmacióncausa
El tiempo avanza de izquierda a derecha y luego hacia abajo, hasta la siguiente escritura. Esperar a que pase la incertidumbre significa que s ya está en el pasado antes de que nadie pueda actuar a partir de la escritura.

Obsérvese el último paso: todo lo causado por la escritura empieza después de que se avisara al cliente, lo que ocurre después de que s hubiera pasado con certeza, así que su propio TT.now().latest, y su marca de tiempo, es mayor que s. Eso es la consistencia externa, pagada con unos pocos milisegundos de espera por escritura. El §5 del artículo de Zanzibar lo resume: Zanzibar “builds on Spanner’s TrueTime abstraction” (se basa en la abstracción TrueTime de Spanner) para “provide linearizable commit timestamps encoded as zookies” (proporcionar marcas de tiempo de confirmación linealizables codificadas como zookies).

El mismo artículo explica por qué Zanzibar no puede usar en su lugar un reloj lógico: los relojes de Lamport “require explicit participation of all ‘processes’, where in Zanzibar’s use cases some of the ‘processes’ can be external clients or even human users” (requieren la participación explícita de todos los “procesos”, cuando en los casos de uso de Zanzibar algunos de los “procesos” pueden ser clientes externos o incluso usuarios humanos) (§5). En el Ejemplo A, la flecha “pide” es Alice hablando con Charlie, un canal que ningún reloj ve.

El protocolo de zookies

Las lecturas de instantánea en una marca de tiempo bien ordenada resuelven el Ejemplo A. El Ejemplo B necesita además que la comprobación sea lo bastante reciente. Una forma sería evaluar cada comprobación en la instantánea más reciente, pero §2.2 lo descarta: “would require global data synchronization with high-latency round trips and limited availability” (requeriría una sincronización global de los datos, con viajes de ida y vuelta de alta latencia y una disponibilidad limitada). En su lugar, el propio cliente lleva la frescura necesaria, en forma de zookie: “an opaque byte sequence encoding a globally meaningful timestamp that reflects an ACL write, a client content version, or a read snapshot” (una secuencia de bytes opaca que codifica una marca de tiempo con significado global que refleja una escritura de ACL, una versión de contenido del cliente o una instantánea de lectura) (§2.4).

¿Quién tiene el zookie en cada paso? En la figura, Anne guarda una edición de doc:readme y, más tarde, Beto lo abre.

El protocolo de zookies1. Anne guarda una edición; la aplicación cliente envía una comprobación de cambio de contenido a Zanzibar, que la evalúa en la instantánea más reciente de Spanner. 2. Zanzibar responde permitido con un zookie cuya marca de tiempo es posterior a todas las escrituras de ACL anteriores. 3. La aplicación escribe el contenido nuevo y el zookie en su propio almacenamiento en una escritura atómica. 4. Más tarde, Beto abre el readme; la aplicación carga el contenido y su zookie. 5. La aplicación envía una comprobación que lleva el zookie. 6. Zanzibar la evalúa en una instantánea al menos tan reciente como el zookie y devuelve la respuesta.tiempoapp clientealmacén del clienteZanzibarSpannersin zookiezookie zatómicacarga v2, zlleva zAnne guardauna edicióncomprobación decambio de contenidoevalúa en laúltima instantáneaúltima instantáneapermitido +zookie zrecibe zescribe v2 + zreadme v2, zBeto abreel readmecheck(Beto, z)evalúa eninstantánea ≥ zlee enT ≥ zrespuesta enesa instantáneamuestra uoculta v2
El zookie lo emite la comprobación de cambio de contenido, se almacena junto al contenido y se devuelve con cada comprobación posterior de esa versión.

Paso a paso, según §2.2 y §2.4.4:

  1. Comprobación de cambio de contenido. Cuando un usuario está a punto de guardar un cambio, el cliente envía una comprobación de cambio de contenido. Esta “does not carry a zookie and is evaluated at the latest snapshot” (no lleva zookie y se evalúa en la instantánea más reciente) (§2.4.4).
  2. Emisión del zookie. Si el cambio está permitido, la respuesta incluye un zookie. Zanzibar “encodes a current global timestamp in the zookie and ensures that all prior ACL writes have lower timestamps” (codifica una marca de tiempo global actual en el zookie y garantiza que todas las escrituras de ACL anteriores tengan marcas de tiempo menores) (§2.2).
  3. Almacenado con el contenido. “The client stores the zookie with the content change in an atomic write to the client storage” (El cliente almacena el zookie junto con el cambio de contenido en una escritura atómica en el almacenamiento del cliente) (§2.2). La comprobación en sí no tiene por qué estar en la misma transacción que la escritura del contenido.
  4. Llevado por las comprobaciones posteriores. Cada comprobación posterior de esa versión del contenido envía el zookie almacenado.
  5. Evaluación al menos tan reciente. “A check is always evaluated at a consistent snapshot no earlier than the given zookie” (Una comprobación se evalúa siempre en una instantánea consistente no anterior al zookie dado) (§2.4.4).

En el Ejemplo B, el zookie almacenado con el contenido nuevo codifica T_B2, y T_B2 > T_B1, así que la comprobación de Bob del paso 5 tiene que ver su eliminación.

El zookie es opaco a propósito. El artículo usa “an opaque cookie instead of the actual timestamp to discourage our clients from choosing arbitrary timestamps and to allow future extensions” (una cookie opaca en lugar de la marca de tiempo real para disuadir a nuestros clientes de elegir marcas de tiempo arbitrarias y para permitir extensiones futuras) (§2.4). §5 añade que el protocolo “does not let clients read or evaluate ACLs at an arbitrary snapshot” (no permite a los clientes leer ni evaluar ACL en una instantánea arbitraria), y eso es lo que deja la elección a Zanzibar.

Por qué “al menos tan reciente” y no “exactamente en”

Un zookie es una cota inferior. Zanzibar puede evaluar una comprobación en la marca de tiempo del zookie o en cualquier otra posterior. §2.2 llama a esto la “at-least-as-fresh semantics” (semántica de “al menos tan reciente”) del protocolo y dice que “allow[s] Zanzibar to choose any timestamp fresher than the one encoded in a zookie” (permite a Zanzibar elegir cualquier marca de tiempo más reciente que la codificada en un zookie). Esta libertad se usa de tres maneras.

  • Desactualización predeterminada (§3.2.1). Sin zookie, el servidor elige “a default staleness chosen to ensure that all transactions are evaluated at a timestamp that is as recent as possible without impacting latency” (una desactualización predeterminada elegida para garantizar que todas las transacciones se evalúen en una marca de tiempo tan reciente como sea posible sin afectar a la latencia). Cada servidor registra con qué frecuencia las lecturas con una desactualización dada tuvieron que salir de la zona y desplaza el valor predeterminado a “the lowest ‘safe’ value” (el valor “seguro” más bajo). El artículo señala que esto “is purely a performance optimization” (es puramente una optimización del rendimiento) porque “Zanzibar always respects zookies when provided” (Zanzibar siempre respeta los zookies cuando se proporcionan).
  • Cuantización (§3.2.5). Las marcas de tiempo de evaluación se “rounded up to a coarse granularity, such as one or ten seconds, while respecting staleness constraints from request zookies” (redondean al alza a una granularidad gruesa, como uno o diez segundos, respetando a la vez las restricciones de desactualización de los zookies de las solicitudes). Redondear al alza nunca rompe una cota inferior.
  • Cachés compartidas (§3.2.5). Las claves de caché contienen la marca de tiempo de la instantánea, así que nunca se mezclan resultados de instantáneas distintas. Gracias al redondeo, “the vast majority of recent checks and reads” (la gran mayoría de las comprobaciones y lecturas recientes) se evalúan en las mismas marcas de tiempo y “share cache results” (comparten resultados de caché).

¿Qué se gana redondeando al alza cuando llegan tres comprobaciones con zookies separados por unos cientos de milisegundos?

Redondeo al alza de las marcas de tiempo de evaluaciónTres comprobaciones, de Anne, Beto y Chen sobre doc:readme, llevan zookies con marcas de tiempo distintas, en microsegundos, dentro del mismo segundo. Zanzibar redondea cada una al alza a la misma marca de tiempo gruesa T_q, que es mayor o igual que todos los zookies, así que las tres se evalúan en una sola instantánea y comparten entradas de caché con clave T_q. Cualquier marca de tiempo posterior, hasta los datos más recientes en el líder, también estaría permitida.comprobación de Annezookie 12.104 scomprobación de Betozookie 12.380 scomprobación de Chenzookie 12.911 sevalúa enT_q = 13 sla clave de cachéincluye T_qdatos másrecientes (líder)redondeoredondeocompartidatambiénpermitido
Los tres zookies son cotas inferiores; 13 s las satisface todas. Las marcas de tiempo son ilustrativas, no proceden del artículo.

Obsérvese que T_q puede incluso estar ligeramente en el futuro. §3.2.5 cubre ese caso: Spanner “ensures that a snapshot read at timestamp T will observe all writes up to T—this holds even if T is in the future, in which case the read will wait until TrueTime has moved past T.” (garantiza que una lectura de instantánea en la marca de tiempo T observará todas las escrituras hasta T; esto se cumple incluso si T está en el futuro, en cuyo caso la lectura esperará hasta que TrueTime haya rebasado T.)

Solicitudes Safe y Recent

El precio de la frescura es la distancia. “When a zookie timestamp is higher than that of the most recent data replicated to the region, the storage reads require cross-region round trips to the leader replica” (Cuando la marca de tiempo de un zookie es posterior a la de los datos más recientes replicados en la región, las lecturas de almacenamiento requieren viajes de ida y vuelta entre regiones hasta la réplica líder) (§4.1). El almacenamiento se replica con “replication heartbeats with 8-second intervals” (latidos de replicación a intervalos de 8 segundos), así que §4.1 divide las solicitudes en el umbral de 10 segundos:

  • Las solicitudes Safe “have zookies more than 10 seconds old and can be served within the region most of time” (tienen zookies de más de 10 segundos de antigüedad y la mayor parte del tiempo pueden servirse dentro de la región).
  • Las solicitudes Recent “have zookies less than 10 seconds old and often require inter-region round trips” (tienen zookies de menos de 10 segundos de antigüedad y a menudo requieren viajes de ida y vuelta entre regiones).

Los 8 segundos coinciden con el artículo de Spanner, donde “a leader by default advances MinNextTS() values every 8 seconds” (un líder avanza por defecto los valores de MinNextTS() cada 8 segundos), de modo que las réplicas “can serve reads at timestamps greater than 8 seconds old in the worst case” (pueden servir, en el peor caso, lecturas en marcas de tiempo de más de 8 segundos de antigüedad) (Spanner §4.2.1).

La Tabla 2 del artículo (§4.2) da la latencia de cada tipo, en milisegundos, como media (desviación típica) a lo largo de un periodo de 7 días de diciembre de 2018:

API Percentil 50 Percentil 95 Percentil 99
Safe Check 3.0 (0.091) 9.46 (0.3) 15.0 (1.19)
Safe Read 2.18 (0.031) 3.71 (0.094) 8.03 (3.28)
Safe Expand 4.27 (0.313) 8.84 (0.586) 34.1 (4.35)
Recent Check 2.86 (0.087) 60.0 (2.1) 76.3 (2.59)
Recent Read 2.21 (0.054) 40.1 (2.03) 86.2 (3.84)
Recent Expand 5.79 (0.224) 45.6 (3.44) 121.0 (2.38)
Recent Write 127.0 (3.65) 233.0 (23.0) 401.0 (133.0)

Las medianas son parecidas; las colas, no. El percentil 95 de una comprobación Recent es de 60.0 ms frente a 9.46 ms para una Safe: el coste del viaje entre regiones. Las escrituras son las más lentas porque “always require distributed coordination among Spanner servers” (siempre requieren coordinación distribuida entre los servidores de Spanner) (§4.2); en Spanner, esa coordinación incluye la espera de confirmación. Según §4.1 y la Figura 3, las solicitudes Safe superan a las Recent en “about two orders of magnitude” (unos dos órdenes de magnitud), “which allows Zanzibar to serve the vast majority of ACL checks locally” (lo que permite a Zanzibar servir localmente la gran mayoría de las comprobaciones de ACL). La mayoría de las solicitudes pueden ser Safe porque un zookie es solo una cota inferior: una comprobación de contenido más antiguo puede usar datos más antiguos, ya replicados.

Fuentes