guide:glossary@es

Guías

Glosario

Todos los términos que el lector encuentra en el artículo de Zanzibar, en palabras sencillas, con una referencia a la página de la guía y a la sección del artículo que los explican.

Datos verificados el

Los términos siguen el orden alfabético de su nombre en inglés, que se indica entre paréntesis. Los nombres de código del lenguaje de configuración del artículo (_this, computed_userset, tuple_to_userset) se ordenan sin sus guiones bajos. Los ejemplos usan el ejemplo de referencia: Anne, Beto y Chen; doc:readme en folder:A; group:eng.

A–C

ACL
Lista de control de acceso (access control list): el conjunto de usuarios autorizados a hacer algo con un objeto. En Zanzibar, una ACL no se almacena como una sola lista, sino como muchas tuplas de relación. Más: Modelos de control de acceso, §1, §2.1.
aclserver
El tipo de servidor principal de Zanzibar. Responde a Check, Read, Expand y Write, y reparte el trabajo entre otros aclservers de su clúster. Más: Arquitectura, §3.
al menos tan reciente (at-least-as-fresh)
La regla de un zookie: Zanzibar puede evaluar en cualquier instantánea que no sea más antigua que la marca de tiempo del zookie, no solo en esa marca de tiempo exacta. Esta libertad es la que le permite servir la mayoría de las solicitudes desde réplicas locales. Más: Consistencia, §2.2.
desactualización acotada (bounded staleness)
Una lectura de instantánea puede ser anterior a “ahora”, pero no más antigua que una cota. En Zanzibar, la cota es el zookie que envía el cliente. Spanner lo ofrece directamente: el cliente da una cota superior de desactualización y Spanner elige la marca de tiempo (artículo de Spanner, §4.1). Más: Consistencia, §2.2.
estampida de caché (cache stampede)
Muchas solicitudes concurrentes de un mismo resultado que no está en caché van todas a la vez al almacenamiento antes de que la caché se rellene. Zanzibar lo evita con una tabla de bloqueos. El artículo cita el artículo de Wikipedia para el término (referencia [3]). Más: Arquitectura, §3.2.5.
registro de cambios (changelog)
Una base de datos Spanner que guarda el historial de actualizaciones de tuplas, escrita en la misma transacción que cada escritura de tuplas. Watch lee de ella. Más: Arquitectura, §3.1.2.
Check
La llamada de la API que pregunta si un usuario está en un userset ⟨object#relation⟩, por ejemplo “¿es Chen lector de doc:readme?”. Se evalúa en una instantánea no anterior al zookie dado. Más: Tuplas de relación, §2.4.4, §3.2.3.
computed_userset
Una hoja de una regla de reescritura que toma el userset de otra relación sobre el mismo objeto, por ejemplo “todo editor es lector”. Más: Tuplas de relación, §2.3.1.
hashing consistente (consistent hashing)
Una forma de asignar claves a servidores de modo que añadir o retirar un servidor solo mueva una pequeña fracción de las claves. Zanzibar lo utiliza para repartir las entradas de la caché entre los servidores de un clúster. Lo introdujeron Karger et al. (STOC 1997) para cachés web. Más: Arquitectura, §3.2.5.
comprobación de cambio de contenido (content-change check)
Una solicitud Check que se envía cuando un usuario está a punto de guardar contenido nuevo. No lleva zookie, se evalúa en la instantánea más reciente y devuelve un zookie que el cliente almacena con la nueva versión del contenido. Más: Consistencia, §2.2, §2.4.4.

D–H

desnormalización (denormalization)
Almacenar una copia precalculada de datos derivados, como la pertenencia aplanada de grupo a grupo, en lugar de calcularla a partir de las filas originales. Zanzibar la evita en el almacenamiento y solo la usa en Leopard. Más: Leopard, §3.2.4, §3.2.5.
exclusión (exclusion)
Un operador de las reglas de reescritura: los usuarios que están en un userset pero no en otro. Más: Tuplas de relación, §2.3.1.
Expand
La llamada de la API que devuelve el userset efectivo de ⟨object#relation⟩ como un árbol, siguiendo las reglas de reescritura. Las hojas son ID de usuario o usersets; los nodos internos son unión, intersección o exclusión. Más: Tuplas de relación, §2.4.5.
consistencia externa (external consistency)
Si la actualización x ocurre antes que la actualización y, x recibe una marca de tiempo menor que y, incluso cuando ambas se coordinan fuera del sistema. Zanzibar la obtiene de Spanner. El artículo cita para el término la tesis de Gifford de 1981 en Stanford (referencia [18]); Spanner la enuncia así: si T1 se confirma antes de que T2 empiece, la marca de tiempo de confirmación de T1 es menor que la de T2. Más: Consistencia, §2.2.
reparto (fan-out)
Una solicitud que se convierte en muchas subsolicitudes, por ejemplo un aclserver que envía partes de una comprobación a otros servidores de su clúster. Más: Arquitectura, §3, §3.2.5.
zookie de latido (heartbeat zookie)
Un zookie incluido en cada respuesta de Watch que marca hasta dónde ha llegado el flujo, para que el cliente pueda reanudar desde ahí. Más: §2.4.3.
solicitudes de cobertura (hedging)
Enviar la misma solicitud a un segundo servidor cuando ya se sabe que el primero es lento, usar la respuesta que llegue primero y cancelar la otra. Zanzibar aplica hedging a las llamadas a Spanner y a Leopard, no a las llamadas entre sus propios servidores. La técnica se describe en Dean y Barroso, “The Tail at Scale” (CACM, 2013). Más: Arquitectura, §3.2.7.
punto caliente (hot spot)
Una clave, un objeto o un grupo que recibe mucho más tráfico que los demás y puede sobrecargar el servidor que lo almacena, por ejemplo un grupo popular compartido por muchas ACL. Más: Arquitectura, §3.2.5.

I–N

intersección (intersection)
Un operador de las reglas de reescritura: los usuarios que están en todos y cada uno de varios usersets. Más: Tuplas de relación, §2.3.1.
Leopard
Un sistema de indexación para grupos profundamente anidados o muy anchos. Aplana la pertenencia a grupos en conjuntos de enteros, de modo que una comprobación de pertenencia se convierte en una intersección de conjuntos, y se mantiene al día mediante Watch. Más: Leopard, §3.2.4.
tabla de bloqueos (lock table)
Una tabla por servidor de las lecturas y comprobaciones en curso. De las solicitudes que comparten una clave de caché, solo se ejecuta una; el resto espera su resultado. Más: Arquitectura, §3.2.5.
tupla de bloqueo (lock tuple)
Una tupla de relación normal que los clientes tocan en cada escritura sobre un objeto, para que una escritura pueda condicionarse a que nadie más haya escrito desde la lectura. Más: §2.4.2.
espacio de nombres (namespace)
Un tipo de objeto definido por el cliente, como doc o folder. La parte anterior a los dos puntos en doc:readme. Las tuplas de cada espacio de nombres residen en su propia base de datos. Más: Tuplas de relación, §2.1, §2.3, §3.1.1.
configuración del espacio de nombres (namespace config)
La configuración de un espacio de nombres: sus relaciones, cada una con una regla de reescritura de usersets opcional, además de parámetros de almacenamiento como la fragmentación. Más: Tuplas de relación, §2.3, §3.1.3.
problema del “nuevo enemigo” (new enemy problem)
Mostrar contenido a alguien que fue eliminado de su ACL, porque la comprobación desatendió el orden de dos cambios de ACL o aplicó una ACL más antigua que el contenido. Más: Consistencia, §2.2.

O–R

objeto (object)
Lo que se protege, escrito ⟨namespace⟩:⟨object_id⟩, como doc:readme. Más: Tuplas de relación, §2.1.
Paxos
Un protocolo de consenso que permite a un grupo de réplicas ponerse de acuerdo sobre cada escritura aunque algunas fallen. El artículo sitúa las cinco réplicas con voto del almacenamiento de Zanzibar a menos de 25 ms entre sí para que las transacciones Paxos se confirmen con rapidez. Véase Lamport, “Paxos Made Simple” (2001). Más: Arquitectura, §3.1.4.
persecución de punteros (pointer chasing)
Responder a una comprobación siguiendo los usersets salto a salto: de los lectores del readme a group:eng#member, luego a los miembros de ese grupo, y así sucesivamente. Es lenta cuando los grupos son profundos o anchos. Más: Tuplas de relación, Leopard, §3.2.3, §3.2.4.
Read
La llamada de la API que devuelve las tuplas almacenadas que coinciden con uno o varios conjuntos de tuplas. No aplica las reglas de reescritura. Más: Tuplas de relación, §2.4.1.
solicitud Recent (Recent request)
Véase solicitudes Safe / Recent. Más: Consistencia, §4.1.
relación (relation)
Una relación con nombre entre un objeto y un usuario, o entre dos objetos (como parent enlaza un documento con su carpeta), como owner, viewer, member o parent. Se define en la configuración del espacio de nombres. Más: Tuplas de relación, §2.1, §2.3.
tupla de relación (relation tuple)
Un hecho almacenado, ⟨object⟩#⟨relation⟩@⟨user⟩, como doc:readme#owner@user:anne. El único tipo de dato de permisos que almacena Zanzibar. Más: Tuplas de relación, §2.1.
réplica (replica)
Una copia de los datos en una ubicación. Los datos de Zanzibar se replican en decenas de ubicaciones para que la mayoría de las lecturas puedan servirse cerca. Más: Arquitectura, §3.1.4.

S

solicitudes Safe / Recent (Safe / Recent requests)
La división que hace el artículo de las solicitudes según la antigüedad del zookie. Las solicitudes Safe llevan zookies de más de 10 segundos de antigüedad y normalmente pueden servirse dentro de la región; las solicitudes Recent llevan zookies más nuevos y a menudo necesitan un viaje de ida y vuelta entre regiones. Más: Consistencia, §4.1.
fragmento (shard)
Una porción de una base de datos o de un índice que se almacena y se sirve por separado. El ID de fragmento de una tupla suele proceder de su ID de objeto y, para grupos muy grandes, del ID de objeto y del usuario. Más: Arquitectura, §3.1.1, §3.2.4.
lectura de instantánea (snapshot read)
Una lectura que ve la base de datos exactamente tal como estaba en una marca de tiempo: todas las escrituras en esa marca de tiempo o antes, y ninguna posterior. Zanzibar evalúa cada comprobación en una única instantánea. Spanner la define como “a read in the past that executes without locking” (una lectura en el pasado que se ejecuta sin bloqueos) (artículo de Spanner, §4.1). Más: Consistencia, §2.2.
Spanner
La base de datos distribuida globalmente de Google. Zanzibar almacena en ella las tuplas, las configuraciones de los espacios de nombres y el registro de cambios, y depende de sus marcas de tiempo para la consistencia. Se describe en Corbett et al., OSDI 2012. Más: Consistencia, Arquitectura, §2.2, §3.

T

latencia de cola (tail latency)
La latencia de las solicitudes más lentas, como el percentil 99 o 99.9. Importa porque una sola página de resultados de búsqueda puede necesitar de decenas a cientos de comprobaciones. Véase Dean y Barroso, “The Tail at Scale” (CACM, 2013). Más: Arquitectura, §1, §3.2.7, §4.2, §4.5.
_this
La hoja de una regla de reescritura que devuelve los usuarios de las tuplas almacenadas para este objeto y esta relación, incluidos los usersets a los que apuntan esas tuplas. Es el valor predeterminado cuando una relación no tiene regla. Más: Tuplas de relación, §2.3.1.
cuantización de marcas de tiempo (timestamp quantization)
Redondear al alza las marcas de tiempo de evaluación a un paso grueso, como uno o diez segundos, para que muchas solicitudes compartan una marca de tiempo y, por tanto, entradas de caché. No debilita la consistencia: un zookie solo fija una cota inferior, y una lectura de instantánea de Spanner en una marca de tiempo futura espera hasta que TrueTime la haya rebasado (§3.2.5). Más: Arquitectura, Consistencia, §2.2, §3.2.5.
TrueTime
El mecanismo de reloj de Spanner, que da a cada escritura una marca de tiempo con resolución de microsegundos que refleja el orden causal. Es lo que da sentido a las marcas de tiempo de Zanzibar. TT.now() devuelve un intervalo que contiene con garantía el tiempo real; véase el artículo de Spanner (OSDI 2012), §3. Más: Consistencia, §2.2, §3.2.5.
conjunto de tuplas (tupleset)
Un selector de tuplas almacenadas: una única clave de tupla, o todas las tuplas de un ID de objeto o de un userset, opcionalmente limitadas a una relación. Lo usan Read y tuple_to_userset. Más: Tuplas de relación, §2.4.1.
tuple_to_userset
Una hoja de una regla de reescritura que lee algunas tuplas del objeto y calcula un userset a partir de cada una, por ejemplo “buscar la carpeta padre del readme y tomar sus lectores”. Más: Tuplas de relación, §2.3.1.

U–W

unión (union)
Un operador de las reglas de reescritura: los usuarios que están en cualquiera de varios usersets. Las tres ramas de viewer en la Figura 1 del artículo se combinan mediante unión. Más: Tuplas de relación, §2.3.1.
usuario (user)
La tercera parte de una tupla: un único ID de usuario o un userset. Más: Tuplas de relación, §2.1.
userset
Un par ⟨object⟩#⟨relation⟩ que representa a todos los usuarios que tienen esa relación con ese objeto, como group:eng#member. Permite que una tupla conceda acceso a un grupo, y que unos grupos contengan a otros. Más: Tuplas de relación, §2.1.
regla de reescritura de usersets (userset rewrite rule)
Parte de una configuración de relación: una función de un ID de objeto a un árbol de expresiones de usersets, construido a partir de _this, computed_userset y tuple_to_userset combinados mediante unión, intersección y exclusión. Más: Tuplas de relación, §2.3.1.
árbol de usersets (userset tree)
El resultado de Expand: las hojas son ID de usuario o usersets y los nodos internos son operadores de conjuntos. Más: Tuplas de relación, §2.4.5.
Watch
La llamada de la API que transmite los cambios de tuplas de uno o varios espacios de nombres en orden de marca de tiempo, a partir de un zookie. Se usa para mantener al día índices secundarios, como Leopard. Más: Arquitectura, §2.4.3.
watchserver
El tipo de servidor que responde a Watch siguiendo el final del registro de cambios. Más: Arquitectura, §3.
Write
La llamada de la API que añade o elimina tuplas. Los clientes que reescriben todas las tuplas de un objeto hacen una lectura y luego una escritura condicionada a que la tupla de bloqueo no haya cambiado. Más: Arquitectura (lo que toca una escritura), §2.4.2.

Z

zookie
Un token opaco que codifica una marca de tiempo. El cliente obtiene uno de una comprobación de cambio de contenido (las respuestas de Read y de Write también llevan zookies), lo almacena con el contenido y lo envía con las comprobaciones posteriores para que se evalúen en una instantánea al menos tan reciente. Más: Consistencia, §2.2, §2.4.

Fuentes

  • J. C. Corbett et al., “Spanner: Google’s Globally-Distributed Database”, OSDI ’12, PDF
  • D. Karger et al., “Consistent Hashing and Random Trees”, STOC ’97, PDF
  • J. Dean y L. A. Barroso, “The Tail at Scale”, CACM 56(2), 2013, research.google
  • L. Lamport, “Paxos Made Simple”, ACM SIGACT News 32(4), 2001, PDF
  • D. K. Gifford, “Information Storage in a Decentralized Computer System”, tesis doctoral, Stanford University, 1981 (referencia [18] del artículo; no se ha consultado ninguna copia en línea)
  • “Cache stampede”, Wikipedia, en.wikipedia.org (la fuente que cita el artículo)
  • Ruoming Pang et al., “Zanzibar: Google’s Consistent, Global Authorization System”, USENIX ATC ’19, usenix.org/conference/atc19/presentation/pang