Escanear un espacio de claves que no se queda quieto: cómo SCAN itera un clúster
Un GET de clave única es fácil de razonar: haz hash de la clave, encuentra su propietario, pregunta a ese único nodo. SCAN es el tipo de operación opuesto. No tiene clave —hace una pregunta sobre todo el espacio de claves: dame cada clave en este rango, una página a la vez. Y en un almacén particionado y replicado ese espacio de claves no es una sola cosa en un solo lugar. Está dividido en 256 segmentos repartidos sobre cuantos nodos ejecutes, cada nodo sosteniendo solo las porciones que posee actualmente, y todo el conjunto se está escribiendo mientras iteras. No hay índice ordenado global que recorrer. Entonces, ¿de dónde viene el orden, a qué apunta exactamente un token de reanudación, y qué le pasa a tu escaneo cuando una clave se escribe —o una partición se mueve— a mitad de camino?
Este artículo sigue un SCAN a través de las tres capas que realmente lo sirven: un solo segmento, un solo nodo, y el cliente que cose los nodos entre sí. Cada capa resuelve una pieza del problema, y los límites honestos de la operación caen de cómo esas piezas encajan.
La solicitud: un rango y un tamaño de página, no una clave
Un escaneo se describe con dos objetos pequeños. Un KeyRange dice qué claves —un inicio, un fin o un prefijo, cualquiera de ellos opcional:
public sealed class KeyRange
{
public string? Start { get; set; }
public string? End { get; set; }
public string? Prefix { get; set; }
}
Y ScanOptions dice cómo entregarlas —qué tan grande una página, si enviar valores o solo claves, un límite duro opcional, y un token de reanudación para continuar una llamada previa:
public sealed class ScanOptions
{
public int PageSize { get; set; } = 100;
public bool IncludeValues { get; set; } = true;
public bool IncludeMetadata{ get; set; } = false;
public string? ResumeToken { get; set; }
public int? LimitCount { get; set; }
}
Nada aquí nombra un nodo o un segmento. Ese es el punto: el llamador describe lo que quiere, y las tres capas de abajo calculan dónde vive y en qué orden entregarlo.
Capa uno: un segmento se escanea a sí mismo, sin locks y en orden
La unidad más pequeña que puede responder parte de un escaneo es un segmento —la unidad de almacenamiento particionado de Zaris, respaldada por un ConcurrentDictionary de registros vivos. Un diccionario no tiene orden, así que lo primero que un escaneo de segmento necesita es una vista ordenada de sus claves. Construir eso en cada página sería ruinoso, así que cada segmento mantiene una instantánea de claves ordenadas, cacheada e inmutable y la reconstruye solo cuando el conjunto de claves cambia:
// No lock held during scan — the snapshot is immutable once built.
var sortedKeys = GetOrBuildSortedKeys();
int startIdx = BinarySearchKey(sortedKeys, startKey, StringComparer.Ordinal);
if (startIdx < 0) startIdx = ~startIdx;
El arreglo se asigna una vez y nunca se muta; una reconstrucción concurrente simplemente produce un nuevo arreglo e intercambia la referencia. Eso significa que el recorrido del escaneo en sí no toma ningún lock en absoluto —hace búsqueda binaria hasta la clave de inicio y avanza en orden ordinal, leyendo registros vivos del diccionario concurrente a medida que avanza. Las lecturas y escrituras al segmento nunca bloquean el escaneo, y el escaneo nunca las bloquea a ellas.
Dos tipos de clave se pasan por alto silenciosamente mientras avanza:
if (!_data.TryGetValue(key, out var record)) continue; // vanished since snapshot
if (record.IsDeleted || ExpirationManager.IsExpired(record, now)) continue; // tombstone / TTL
Una clave eliminada es una tombstone (lápida) —un registro real marcado como IsDeleted, porque una eliminación tiene que ser un registro, no una ausencia, para que la replicación la lleve. El escaneo las filtra, junto con las claves cuyo TTL ha transcurrido pero cuyo barredor (sweeper) todavía no se ha disparado. Así que la instantánea de claves ordenadas es un superconjunto de lo que verás; la expiración y la eliminación se resuelven contra el registro vivo en el momento de lectura, no se congelan en la instantánea.
El recorrido se detiene en PageSize y devuelve un ResumeToken. Aquí está el primer detalle honesto: a nivel de segmento, el token es esencialmente un offset —un conteo de cuántas entradas coincidentes ya se devolvieron (ReturnedSoFar). Un escaneo de segmento reanudado vuelve a hacer búsqueda binaria hasta la misma clave de inicio y omite esa cantidad de coincidencias antes de emitir. Es una posición-por-conteo, no una búsqueda de posición-por-clave.
cursor.ReturnedSoFar += taken;
bool hasMore = results.Count >= pageSize && cursor.ReturnedSoFar < totalLimit;
Esa elección importa para lo que la operación promete, y volveremos a ella.
Capa dos: un nodo fusiona sus segmentos en un único stream ordenado
Un nodo posee muchos segmentos —no los 256, solo los mapeados a las particiones que sirve actualmente. Un escaneo a nivel de nodo tiene que presentar todos ellos como un único resultado ordenado, porque el llamador preguntó por un rango, no por el segmento 42. Este es un problema clásico de fusión: cada segmento puede producir sus claves en orden ordenado, y quieres la unión ordenada.
Así que la primera página de un escaneo de nodo hace exactamente eso. Reúne un fetcher para cada segmento poseído localmente y ejecuta una fusión k-vías sobre ellos con una cola de prioridad, comparando claves ordinalmente:
var heap = new PriorityQueue<(KvResult<ZarisEntry> Item, int Source), KvResult<ZarisEntry>>(comparison);
// seed with the head of each segment, then repeatedly pop the smallest
// key and pull the next from that segment's enumerator
El resultado fusionado y ordenado se materializa en un buffer sostenido por un RouterQueryCoordinator —una sesión del lado del servidor de corta vida registrada bajo un QueryId recién acuñado:
coord = new RouterQueryCoordinator();
await coord.InitScanAsync(fetchers, ct); // drains + merges every owned segment
var id = _coordManager.Register(coord);
cursor = new QueryCursor { QueryId = id, ReturnedSoFar = 0 };
Cada página subsiguiente es solo una porción de ese buffer, y el token de reanudación del nodo lleva el QueryId para que la siguiente llamada encuentre la misma sesión:
if (!string.IsNullOrEmpty(options?.ResumeToken))
{
cursor = QueryCursor.Deserialize(options.ResumeToken);
if (!_coordManager.TryGet(cursor.QueryId, out coord))
throw new InvalidOperationException($"Search session {cursor.QueryId} not found (expired or cleaned).");
}
Este es el segundo detalle honesto, y es un compromiso real. Un escaneo a nivel de nodo es con estado (stateful): la paginación es estable y el orden por nodo es exacto, pero el precio es que el nodo materializa todo su espacio de claves poseído y fusionado en un buffer cuando el escaneo comienza, y sostiene una sesión durante toda la vida de la iteración. Los escaneos son una herramienta administrativa y de iteración masiva, no un cursor de streaming de memoria constante sobre miles de millones de claves —y un token de reanudación solo es válido contra el nodo y la sesión que lo acuñaron. Deja que esa sesión expire, o intenta reanudarla en otro lugar, y obtienes un ruidoso "session not found" en lugar de una respuesta silenciosamente errónea.
Capa tres: el cliente hace fan-out e intercala a los propietarios
Un nodo responde por los segmentos que posee. Un escaneo de clúster tiene que cubrir a cada propietario, así que el ScanClusterClient del lado del cliente abre un escaneo contra cada nodo en paralelo e intercala sus páginas a medida que llegan, en lugar de drenar un nodo antes de empezar el siguiente:
var enumerators = clients
.Select(c => c.Scan.ScanAsync(range, options, ct).GetAsyncEnumerator(ct))
.ToList();
// advance all owners concurrently; yield whichever produces next
var finishedTask = await Task.WhenAny(pending.Select(p => p.Task));
Ese paralelismo es por qué LimitCount necesita cuidado. Cada nodo trata el límite como un tope por nodo; si el cliente no lo impusiera también, un LimitCount de 1.000 contra cuatro propietarios podría devolver hasta 4.000 filas una vez fusionadas. Así que la capa de clúster aplica el límite como un tope total duro y deja de entregar una vez que se alcanza —mientras sigue drenando la página en vuelo de cada propietario hasta completarla, porque desechar un enumerador asíncrono a mitad de movimiento no está permitido y los resultados por nodo ya están acotados de todos modos:
if (emitted < limit)
{
yield return enumerator.Current;
emitted++;
}
// keep draining siblings even past the cap; do not yield-break mid-move
La consecuencia a dejar clara: dentro de la contribución de cualquier nodo, las claves llegan en orden; entre nodos se intercalan por llegada, así que un escaneo de clúster completo no está ordenado globalmente a menos que lo pidas explícitamente. (La ruta relacionada Search sí lleva SortFields y fusiona con un comparador exactamente por esa razón.) Si necesitas cada clave del clúster en orden ordinal, ordena el resultado ensamblado; SCAN en sí garantiza el orden por propietario y la completitud, no un orden global.
Qué promete —y qué no promete— un SCAN
Junta las tres capas y el contrato real de la operación es visible, sin que nada de él esté oculto:
- No es una instantánea puntual del clúster. Cada nodo materializa su propio buffer fusionado cuando su escaneo comienza, y esos momentos no coinciden. Las escrituras que llegan a un nodo antes de que su buffer se construya se incluyen; las posteriores no. No hay congelación de todo el clúster.
- Las claves eliminadas y expiradas nunca aparecen. Las tombstones y los registros con TTL transcurrido se filtran contra el registro vivo a medida que se recorre el segmento, así que un escaneo refleja el contenido lógico, no el físico.
- La reanudación es posición-por-conteo dentro de una sesión. Como el cursor por segmento es un offset, una clave insertada o eliminada antes de la posición actual entre dos páginas puede desplazar la frontera —un escaneo concurrente con mutación intensa del rango escaneado puede, en principio, repetir u omitir una clave alrededor de la costura. Un escaneo de un rango inactivo es exacto. Esta es la misma familia de garantía que da
SCANde Redis —una iteración completa de mejor esfuerzo, no un nivel de aislamiento de instantánea— y es el compromiso correcto para un almacén no ordenado y escrito concurrentemente. - El espacio de claves puede moverse bajo tus pies. El cliente hace fan-out a los propietarios que existen cuando el escaneo comienza. Las particiones pueden migrar o hacer failover a mitad de iteración; un escaneo es un barrido de mejor esfuerzo de un clúster vivo, que es por qué es la herramienta para exportación masiva, reindexación y consultas administrativas en lugar de para lecturas transaccionales. Para read-your-writes sobre una sola clave, enruta al propietario en su lugar.
Ninguno de estos es un bug que empapelar; son la forma honesta de iterar un espacio de claves no ordenado, fragmentado y mutante sin detener el mundo. El diseño hace que el caso barato y común sea rápido —una instantánea ordenada sin locks y una fusión por nodo— y es explícito sobre los bordes.
Una nota sobre el front-end RESP
Los clientes de Redis alcanzan la misma maquinaria a través de KEYS y SCAN en el front-end RESP, que se mapean sobre el escaneo nativo. Una advertencia que vale la pena declarar sin rodeos: el SCAN de RESP hoy es de un solo disparo —drena el escaneo nativo y responde con el cursor 0 (iteración completa) en un viaje de ida y vuelta, en lugar de enhebrar el cursor incremental de Redis a través de cada llamada. Es honesto sobre la completitud, no todavía incremental. El cliente nativo es el que pagina con un token de reanudación.
Una operación, tres capas honestas
Un GET toca un propietario y una clave; un SCAN toca a cada propietario y pide a cada uno que produzca su porción de un todo ordenado. El trabajo se divide limpiamente: un segmento convierte un diccionario no ordenado en un recorrido ordenado y sin locks; un nodo fusiona sus segmentos en un único stream ordenado y paginado de forma estable detrás de un cursor de sesión; el cliente hace fan-out entre propietarios, intercala sus páginas, e impone el único tope que el fan-out de otro modo rompería. Cada capa es simple por sí sola, y las garantías de la operación —orden por propietario, completitud sobre un rango inactivo, sin aislamiento de instantánea, sin congelación global— son exactamente lo que esas tres capas simples pueden entregar honestamente juntas.