Zanzibar es un conjunto de servidores situado delante de un conjunto de bases de datos Spanner. Esta página nombra las piezas, sigue luego una solicitud Check a través de ellas y después examina cómo se disponen los datos en disco. Las cifras del final son las que el artículo da para producción en 2018.
Las piezas
¿Qué cajas hay y en qué sentido fluyen los datos entre ellas? El artículo responde con su Figura 2. La versión siguiente conserva sus colores (clientes en azul, servidores en amarillo, bases de datos Spanner en verde) y prescinde del detalle.
Obsérvese que los clientes hablan con dos tipos de servidor. Los aclservers responden a los cuatro tipos de solicitud; los watchservers solo transmiten cambios. En palabras del artículo, los aclservers “are organized in clusters and respond to Check, Read, Expand, and Write requests” (están organizados en clústeres y responden a solicitudes Check, Read, Expand y Write), mientras que los watchservers “tail the changelog and serve a stream of namespace changes to clients in near real time” (siguen el final del registro de cambios y sirven a los clientes un flujo de cambios de los espacios de nombres casi en tiempo real) (§3). Leopard es un índice para grupos grandes y profundamente anidados; tiene su propia página.
La canalización fuera de línea produce “dumps of the relation tuples in each namespace at a known snapshot timestamp” (volcados de las tuplas de relación de cada espacio de nombres en una marca de tiempo de instantánea conocida) y elimina “tuple versions older than a threshold configured per namespace” (las versiones de tuplas más antiguas que un umbral configurado por espacio de nombres) (§3).
Una comprobación, paso a paso
La solicitud que se va a seguir: ¿es Beto lector del readme? En el ejemplo de referencia, los lectores del readme incluyen a los miembros de group:eng, y Beto es uno de ellos, así que la respuesta es sí. Zanzibar tiene que averiguarlo leyendo dos objetos, doc:readme y group:eng.
Llega a cualquier servidor, que reparte el trabajo
¿Qué servidor hace el trabajo? Cualquiera de ellos puede aceptar la solicitud, y el trabajo se reparte después por objeto.
El servidor A no necesitaba ser responsable de ninguno de los dos objetos. El artículo describe exactamente esta forma: “Requests arrive at any server in a cluster and that server fans out the work to other servers in the cluster as necessary. Those servers may in turn contact other servers to compute intermediate results. The initial server gathers the final result and returns it to the client.” (Las solicitudes llegan a cualquier servidor de un clúster y ese servidor reparte el trabajo entre otros servidores del clúster según sea necesario. Esos servidores pueden, a su vez, contactar con otros servidores para calcular resultados intermedios. El servidor inicial reúne el resultado final y lo devuelve al cliente.) (§3)
El hashing consistente elige al servidor par
¿Cómo supo A que debía preguntar a B por el readme? Los servidores de un clúster forman una única caché distribuida: “Cache entries are distributed across Zanzibar servers with consistent hashing” (las entradas de la caché se distribuyen entre los servidores de Zanzibar mediante hashing consistente) (§3.2.5). El esquema procede de Karger et al. (STOC ’97), que el artículo cita como [20]. Para la mayoría de los espacios de nombres, la clave de reenvío se calcula a partir del ID de objeto (§3.2.5).
Obsérvese que viewer y owner sobre el readme coinciden en el mismo servidor. Ese es el sentido de usar el objeto como clave: “processing a check on ⟨object#relation⟩ often involves indirect ACL checks on other relations of the same object and reading relation tuples of the object. These checks and reads can be processed by the same server since they share the same forwarding key with the parent check request.” (procesar una comprobación sobre ⟨object#relation⟩ suele implicar comprobaciones de ACL indirectas sobre otras relaciones del mismo objeto y la lectura de tuplas de relación del objeto. Esas comprobaciones y lecturas puede procesarlas el mismo servidor, ya que comparten la misma clave de reenvío con la solicitud de comprobación padre.) (§3.2.5) Karger et al. diseñan el hashing consistente de modo que, cuando se añade o se retira una caché, solo tenga que moverse la fracción mínima de objetos necesaria para mantener la carga equilibrada, y por eso resulta adecuado para una caché.
Para las claves calientes, el artículo añade que utiliza Slicer “to help distribute hot keys to multiple servers” (para ayudar a distribuir las claves calientes entre varios servidores) (§3.2.5).
Ambos extremos de una llamada guardan la respuesta en caché
¿Qué ocurre cuando muchos servidores preguntan a la vez a C por group:eng, por ejemplo porque una página de resultados de búsqueda comprueba decenas de documentos compartidos todos con eng?
Las cachés de los llamantes y la del llamado se apilan en un árbol: “To handle hot forwarding keys, we cache results at both the caller and the callee of internal RPCs, effectively forming cache trees.” (Para gestionar las claves de reenvío calientes, almacenamos en caché los resultados tanto en el llamante como en el llamado de las RPC internas, con lo que, en la práctica, se forman árboles de cachés.) (§3.2.5) Las claves de caché incluyen la marca de tiempo de la instantánea, y las marcas de tiempo están “rounded up to a coarse granularity, such as one or ten seconds” (redondeadas al alza a una granularidad gruesa, como uno o diez segundos), de modo que la mayoría de las solicitudes recientes comparten entradas (§3.2.5). En producción, la caché de comprobaciones tenía “a 10% hit rate on the delegate’s side” (una tasa de aciertos del 10% en el lado del delegado) y “a 2% hit rate” (una tasa de aciertos del 2%) en el lado del delegante; el artículo señala que, por bajas que parezcan estas tasas, “they prevent 500K internal RPCs per second from creating hot spots” (evitan que 500K RPC internas por segundo creen puntos calientes) (§4.4).
La tabla de bloqueos agrupa las solicitudes idénticas
Una caché solo ayuda cuando ya contiene la respuesta. Si llegan muchas solicitudes idénticas antes de que termine la primera, todas fallarían en la caché e irían todas a Spanner: una estampida de caché (la referencia [3] del artículo). ¿Cómo lo evita C?
El artículo: “we maintain a lock table on each server to track outstanding reads and checks. Among requests sharing the same cache key only one request will begin processing; the rest block until the cache is populated.” (mantenemos una tabla de bloqueos en cada servidor para registrar las lecturas y comprobaciones en curso. De entre las solicitudes que comparten la misma clave de caché, solo una empezará a procesarse; el resto se bloquea hasta que la caché se rellena.) (§3.2.5) En las comprobaciones, la tabla de bloqueos ahorró “an additional 12%” (un 12% adicional) en el lado del delegado y “an additional 3%” (un 3% adicional) en el lado del delegante (§4.4).
Más tarde llegaron dos mejoras (§3.2.5). Para un objeto muy popular, Zanzibar lee y almacena en caché todas las tuplas de ⟨object#relation⟩ de una vez, “trading read bandwidth for cacheability” (cambiando ancho de banda de lectura por capacidad de caché). Y como una subcomprobación cancelada deja vacía su clave de caché, retrasa la “eager cancellation when there are waiters on the corresponding lock table entry” (cancelación anticipada cuando hay solicitudes en espera en la entrada correspondiente de la tabla de bloqueos).
Las lecturas a Spanner se agrupan
Tómese ahora una comprobación que afecta a varias relaciones de un mismo objeto: ¿es Chen lector del readme? Con la configuración de la Figura 1 del artículo, viewer incluye editor, editor incluye owner, y los lectores de la carpeta parent son lectores del documento. Así que el servidor B tiene que leer cuatro conjuntos de tuplas del readme.
Las hojas se ejecutan de forma concurrente: “we evaluate all leaf nodes of the boolean expression tree concurrently. When the outcome of one node determines the result of a subtree, evaluation of other nodes in the subtree is cancelled.” (evaluamos concurrentemente todos los nodos hoja del árbol de expresiones booleanas. Cuando el resultado de un nodo determina el resultado de un subárbol, se cancela la evaluación de los demás nodos del subárbol.) (§3.2.3) Sus lecturas se agrupan: “We apply a pooling mechanism to group reads for the same ACL check to minimize the number of read RPCs to Spanner.” (Aplicamos un mecanismo de agrupación para reunir las lecturas de una misma comprobación de ACL y minimizar el número de RPC de lectura a Spanner.) (§3.2.3) La tupla parent apunta entonces a folder:A, y folder:A#viewer se reenvía al servidor responsable de folder:A, donde se encuentra a Chen. El artículo no dice en cuántas RPC se convierte un grupo; no va más allá de “menos”.
La disposición de las tuplas lo abarata: el orden de la clave primaria “allows us to look up all relation tuples for a given object ID or (object ID, relation) pair” (nos permite buscar todas las tuplas de relación de un ID de objeto o de un par (ID de objeto, relación) dado) (§3.1.1, véase Almacenamiento más abajo).
Las lecturas lentas de Spanner se cubren con hedging
Algunas lecturas serán lentas por motivos que nada tienen que ver con la solicitud. Para las llamadas a Spanner y a Leopard, Zanzibar utiliza solicitudes de cobertura (hedging), según Dean y Barroso, “The Tail at Scale” (CACM, 2013), la referencia [16] del artículo. ¿Cuándo sale la segunda solicitud?
El hedging consiste en que “we send the same request to multiple servers, use whichever response comes back first, and cancel the other requests” (enviamos la misma solicitud a varios servidores, utilizamos la respuesta que llegue primero y cancelamos las demás solicitudes) (§3.2.7). La segunda solicitud espera: “we first send one request and defer sending hedged requests until the initial request is known to be slow” (primero enviamos una solicitud y diferimos el envío de las solicitudes de cobertura hasta que se sabe que la solicitud inicial es lenta), con un retardo fijado por un estimador de la “Nth percentile latency based on recent measurements” (latencia del percentil N basada en mediciones recientes) (§3.2.7). En producción, “1% of Spanner reads, or 200K reads per second, benefit from hedging” (el 1% de las lecturas de Spanner, o 200K lecturas por segundo, se benefician del hedging) (§4.4).
Cada cliente tiene sus límites
Un servicio compartido tiene que impedir que un cliente ralentice a los demás. §3.2.6 enumera cuatro límites:
- CPU: el coste de cada RPC se mide en “generic cpu-seconds” (segundos de CPU genéricos); cada cliente tiene un límite global de CPU, y “its RPCs will be throttled if it exceeds the limit and there is no spare capacity in the overall system.” (sus RPC se limitarán si supera el límite y no hay capacidad sobrante en el sistema en su conjunto).
- RPC en curso: cada servidor limita el total y el número por cliente.
- Spanner: “the maximum number of concurrent reads per (object, client) and per client on each Spanner server.” (el número máximo de lecturas concurrentes por (objeto, cliente) y por cliente en cada servidor de Spanner).
- Tablas de bloqueos: “different lock table keys for requests from different clients” (claves distintas de la tabla de bloqueos para las solicitudes de clientes distintos), de modo que la limitación que Spanner aplica a un cliente no bloquee a otro.
La ruta de Watch
Las escrituras alimentan también un flujo. ¿Adónde va un cambio después de que Anne escriba una tupla?
“Every Zanzibar write is committed to both the tuple storage and the changelog shard in a single transaction.” (Cada escritura de Zanzibar se confirma tanto en el almacenamiento de tuplas como en el fragmento del registro de cambios en una única transacción.) El servidor de Spanner que aloja el fragmento del registro de cambios actúa como coordinador de la transacción “to minimize blocking of changelog reads on pending transactions” (para minimizar el bloqueo de las lecturas del registro de cambios por transacciones pendientes) (§3.1.2). Leopard es uno de los consumidores de este flujo: su indexador incremental “calls Zanzibar’s Watch API to receive a temporally ordered stream of Zanzibar tuple modifications” (llama a la API Watch de Zanzibar para recibir un flujo ordenado temporalmente de modificaciones de tuplas de Zanzibar) (§3.2.4).
Almacenamiento
¿Qué bases de datos hay y qué aspecto tiene una fila? Hay tres tipos (§3).
Bases de datos de tuplas. “We store relation tuples of each namespace in a separate database, where each row is identified by primary key (shard ID, object ID, relation, user, commit timestamp).” (Almacenamos las tuplas de relación de cada espacio de nombres en una base de datos separada, donde cada fila se identifica mediante la clave primaria (ID de fragmento, ID de objeto, relación, usuario, marca de tiempo de confirmación).) (§3.1.1) Como la marca de tiempo de confirmación forma parte de la clave, las versiones antiguas se conservan en sus propias filas, “so that we can evaluate checks and reads at any timestamp within the garbage collection window” (para que podamos evaluar comprobaciones y lecturas en cualquier marca de tiempo dentro de la ventana de recolección de basura). Las tuplas del ejemplo de referencia quedarían en las bases de datos doc y group así:
| Base de datos | ID de fragmento | ID de objeto | relación | usuario | marca de tiempo de confirmación |
|---|---|---|---|---|---|
doc |
s(readme) | readme |
owner |
user:anne |
t₁ |
doc |
s(readme) | readme |
parent |
folder:A#... |
t₂ |
doc |
s(readme) | readme |
viewer |
group:eng#member |
t₃ |
group |
s(eng) | eng |
member |
user:beto |
t₄ |
Las filas de un mismo objeto se ordenan juntas; el artículo dice que este orden de la clave “allows us to look up all relation tuples for a given object ID or (object ID, relation) pair” (nos permite buscar todas las tuplas de relación de un ID de objeto o de un par (ID de objeto, relación) dado). “Usually the shard ID is determined solely by the object ID” (normalmente, el ID de fragmento se determina únicamente a partir del ID de objeto); para los grupos con muchísimos miembros puede estar “computed from both object ID and user” (calculado a partir tanto del ID de objeto como del usuario) (§3.1.1). El artículo no da la función de fragmentación, así que s(…) es un marcador de posición, y tampoco se describe la codificación exacta de la columna de usuario.
Registro de cambios. Una base de datos para todos los espacios de nombres, con clave (ID de fragmento del registro de cambios, marca de tiempo, ID único de actualización), “where a changelog shard is randomly selected for each write” (donde se selecciona al azar un fragmento del registro de cambios para cada escritura) (§3.1.2).
Configuraciones de los espacios de nombres. Una base de datos con dos tablas: las configuraciones, “keyed by namespace IDs” (con los ID de los espacios de nombres como clave), y “a changelog of config updates” (un registro de cambios de las actualizaciones de configuración), “keyed by commit timestamps” (con las marcas de tiempo de confirmación como clave). Un servidor carga todas las configuraciones al arrancar y después sigue ese registro de cambios (§3.1.3).
Replicación. “Replicas exist in dozens of locations around the world, with multiple replicas per region. The 5 voting replicas are in eastern and central United States, in 3 different metropolitan areas to isolate failures but within 25 milliseconds of each other so that Paxos transactions commit quickly.” (Hay réplicas en decenas de ubicaciones de todo el mundo, con múltiples réplicas por región. Las 5 réplicas con voto están en el este y el centro de Estados Unidos, en 3 áreas metropolitanas distintas para aislar los fallos, pero a menos de 25 milisegundos entre sí para que las transacciones Paxos se confirmen con rapidez.) (§3.1.4) Spanner se describe en Corbett et al. (OSDI ’12), la referencia [15] del artículo.
Cifras operativas
El §4 del artículo da estas cifras. Los picos por API y las latencias proceden de periodos de 7 días de diciembre de 2018 (§4, §4.2); el artículo no vincula las demás cifras a un periodo concreto. Cada celda se cita tal como está escrita.
| Qué | Las palabras del artículo | § |
|---|---|---|
| Tiempo en producción | “more than 5 years” (más de 5 años) | 4 |
| Espacios de nombres | “more than 1,500 namespaces defined by hundreds of client applications” (más de 1,500 espacios de nombres definidos por cientos de aplicaciones cliente) | 4 |
| Tuplas | “more than 2 trillion relation tuples that occupy close to 100 terabytes” (más de 2 billones de tuplas de relación que ocupan cerca de 100 terabytes) | 4 |
| Replicación | “fully replicated in more than 30 locations around the world” (totalmente replicados en más de 30 ubicaciones de todo el mundo) | 4 |
| Carga de los clientes | “more than 10 million client queries per second (QPS)” (más de 10 millones de consultas de clientes por segundo) | 4 |
| Pico por API | “Check requests peak at roughly 4.2M QPS, Read at 8.2M, Expand at 760K, and Write at 25K” (las solicitudes Check alcanzan un pico de unas 4.2M QPS, Read de 8.2M, Expand de 760K y Write de 25K) | 4 |
| Servidores | “more than 10,000 servers organized in several dozen clusters around the world” (más de 10,000 servidores organizados en varias decenas de clústeres de todo el mundo) | 4 |
| Servidores por clúster | “from fewer than 100 to more than 1,000, with the median near 500” (de menos de 100 a más de 1,000, con una mediana cercana a 500) | 4 |
| Latencia de Check Safe | “At the 50th, 95th, 99th, and 99.9th percentiles it peaks at roughly 3, 11, 20, and 93 msec, respectively.” (En los percentiles 50, 95, 99 y 99.9 alcanza picos de unos 3, 11, 20 y 93 ms, respectivamente.) | 4.2 |
| Disponibilidad | “above 99.999% over the past 3 years of operation at Google” (superior al 99.999% durante los últimos 3 años de funcionamiento en Google) | 4.3 |
| RPC internas | “22 million internal “delegated” RPCs per second, split about evenly between reads and checks” (22 millones de RPC internas “delegadas” por segundo, repartidas casi a partes iguales entre lecturas y comprobaciones) | 4.4 |
| Búsquedas en caché | “approximately 200 million lookups per second at peak, 150 million from checks and 50 million from reads” (aproximadamente 200 millones de búsquedas por segundo en el pico, 150 millones procedentes de comprobaciones y 50 millones procedentes de lecturas) | 4.4 |
| Lecturas a Spanner | “only 20 million read RPCs per second to Spanner” (solo 20 millones de RPC de lectura por segundo a Spanner) | 4.4 |
| Latencia de lectura de Spanner | “0.5 msec at the median, and 2 msec at the 95th percentile” (0.5 ms en la mediana y 2 ms en el percentil 95) | 4.4 |
| Lecturas con hedging | “1% of Spanner reads, or 200K reads per second, benefit from hedging” (el 1% de las lecturas de Spanner, o 200K lecturas por segundo, se benefician del hedging) | 4.4 |
Obsérvese la proporción de las últimas filas: 200 millones de búsquedas en caché por segundo frente a 20 millones de RPC de lectura a Spanner, unas diez búsquedas en memoria por cada lectura enviada al almacenamiento.
Fuentes
- Pang et al., “Zanzibar: Google’s Consistent, Global Authorization System”, USENIX ATC ’19, §3, §3.1, §3.2.3, §3.2.5–§3.2.7, §4: https://www.usenix.org/conference/atc19/presentation/pang
- Karger et al., “Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web”, STOC ’97 (ref. [20] del artículo): https://people.csail.mit.edu/karger/Papers/web.pdf
- Dean y Barroso, “The Tail at Scale”, Communications of the ACM 56(2), 2013 (ref. [16] del artículo): https://research.google/pubs/the-tail-at-scale/
- “Cache stampede”, Wikipedia, citada por el artículo (ref. [3]): https://en.wikipedia.org/wiki/Cache_stampede
- Adya et al., “Slicer: Auto-sharding for datacenter applications”, OSDI ’16 (ref. [12] del artículo): https://www.usenix.org/conference/osdi16/technical-sessions/presentation/adya
- Corbett et al., “Spanner: Google’s globally-distributed database”, OSDI ’12 (ref. [15] del artículo): https://www.usenix.org/system/files/conference/osdi12/osdi12-final-16.pdf