El efecto de las barreras en los tiempos de finalización

Introducción

Muchos sistemas distribuyen trabajo entre varias subtareas y luego esperan a que todas terminen. Un build que compila varios miles de archivos .cc en paralelo y luego los enlaza. Una consulta scatter-gather que golpea 64 shards y une sus respuestas. Un paso de entrenamiento distribuido que espera el gradiente de cada worker antes de aplicar la actualización.

Eso se ve más o menos así:

await Task.WhenAll(files.Select(DoSomethingReallyCoolAsync));

El tiempo de finalización de todo el conjunto es el tiempo de finalización de la subtarea más lenta. Este artículo analiza qué tan costoso resulta eso a medida que $k$ crece, y qué podemos hacer al respecto.

Supuestos

Vamos a asumir, durante la mayor parte de este artículo, que hay $k$ subtareas con tiempos de finalización i.i.d. $N_{1}, \dots, N_{k}$ . Esto no siempre es cierto en la práctica, pero es un buen punto de partida para entender el problema. En sistemas reales, las subtareas correlacionadas son una razón por la que las cosas resultan mucho peores que en este mundo idealizado; los mutexes son quizás una de las formas más sencillas de ver cómo esto puede morderte.

También vamos a asumir $N_{i} \sim LogNormal (μ, σ^{2})$ (es decir, que el tiempo de finalización de las subtareas es log-normal ). Dos cosas hacen que esto sea un punto de partida razonable:

Las latencias de tareas y solicitudes medidas casi siempre tienen sesgo positivo: la mayoría termina rápido, unas pocas se extienden arbitrariamente («¡ugh, esta cosa aleatoria se colgó de nuevo!»). Una distribución simétrica como la normal no puede reproducir esa larga cola derecha.
Hay un mecanismo detrás del sesgo. La latencia de una subtarea es el producto de muchos efectos multiplicativos independientes: encolamiento, cache misses, jitter de red, contención de locks. Tomar logaritmos convierte ese producto en una suma, de modo que $ln N_{i} = \sum_{j} ln f_{j}$ es una suma de muchos términos independientes y es aproximadamente normal por el teorema central del límite . Eso es exactamente la afirmación de que $N_{i}$ es log-normal, un TCL multiplicativo que a veces se llama ley de Gibrat .

La log-normal se ubica entre la exponencial de cola ligera y las leyes de potencia genuinamente de cola pesada: lo suficientemente pesada como para lanzar de vez en cuando un rezagado brutal, lo suficientemente ligera como para que el máximo conserve todos sus momentos y obedezca el escalado limpio de $2 ln k$ que se deriva más adelante. El escalado sí depende de esa cola. Si las latencias reales de las subtareas siguen una ley de potencia en la cola (a veces es así), el máximo crece mucho más rápido de lo que predice este modelo, así que los números log-normales deben leerse como un caso optimista; subtareas con colas acotadas o más ligeras hacen que crezca más despacio. El panorama cualitativo (las barreras duelen a medida que $k$ crece, $σ$ domina a escala, las barreras parciales ayudan mucho) se traslada a cualquier elección razonable.

La diferencia se ve mejor con ambas densidades graficadas juntas. Abajo, la normal está ajustada a la media y varianza de la log-normal, de modo que solo difiere la forma: la normal es simétrica y asigna probabilidad real a tiempos de finalización negativos, mientras que la log-normal se mantiene positiva y se extiende en una larga cola derecha.

Las dos comparten media y desviación estándar, pero la media, la mediana y la moda de la log-normal difieren entre sí, la firma de una distribución sesgada a la derecha:

Ese sesgo se traslada a la CDF: la log-normal se arrastra hacia 1 a través de su larga cola derecha, mientras que la normal ya ha asignado probabilidad real a tiempos de finalización negativos antes de que el reloj arranque.

El efecto de los máximos

El máximo de $k$ variables aleatorias i.i.d. $N_{i}$ es también una variable aleatoria $M$ , y su distribución viene dada por:

F_{M} (x) = P (max (N_{1}, \dots, N_{k}) \leq x) = P (N_{1} \leq x, \dots, N_{k} \leq x) = P (N_{1} \leq x) \times \dots \times P (N_{k} \leq x) = F (x)^{k}

Donde $F$ es la función de distribución acumulada (CDF) de $N_{i}$ , de modo que $F_{M}$ es la CDF de $M$ . Ya desde aquí podemos ver por qué el máximo es problemático: para todo $x$ fijo con $F (x) < 1$ , $F (x)^{k} \to 0$ cuando $k$ crece, de modo que $M$ se concentra en valores cada vez más grandes. Cuantas más subtareas tenemos, más probable es que al menos una de ellas tarde demasiado y arrastre el máximo hacia arriba.

Esta igualdad nos permite obtener una expresión en forma cerrada para la CDF del máximo de $k$ variables aleatorias log-normales:

F_{M} (x) = [Φ (\frac{ln ( x ) - μ}{σ})]^{k}

Donde $Φ$ es la CDF de la distribución normal estándar. Así es como se ve eso:

Podemos usar esto para obtener la PDF del máximo de $k$ variables aleatorias log-normales diferenciando, pero es bastante engorroso y no ayuda para cosas que nos gustaría hacer, como calcular valores esperados. Indagar en esto me llevó por el agujero del conejo de la teoría de valores extremos , como verás a continuación.

Valor esperado del máximo

Resulta que la PDF es engorrosa y una expresión en forma cerrada para el valor esperado tampoco es elegante, pero podemos simularlo. A continuación se muestra una estimación de Monte Carlo de $E [M]$ junto con los rangos centrales del 68% y el 95% de la distribución de $M$ (los percentiles 16/84 y 2,5/97,5 de $M$ para cada $k$ ), con $k$ variando de 1 a $k_{m a x}$ :

Dos cosas a notar:

El valor esperado crece de forma monótona con $k$ , a una tasa decreciente.
La dispersión también crece con $k$ .

La teoría de valores extremos nos dice que la distribución log-normal pertenece al dominio de atracción de Gumbel , y que, tras un centrado y escalado adecuados, el máximo de $k$ muestras i.i.d. converge a una distribución de Gumbel cuando $k \to \infty$ (sí, ya sé, ¿wtf?).

La normal subyacente $X_{i} = ln N_{i} \sim N (μ, σ^{2})$ tiene una asintótica de orden dominante bien conocida El «orden dominante» fija qué tan rápido crece el máximo con $k$ , no su valor en el $k$ que realmente usás: el error relativo desaparece cuando $k \to \infty$ , pero la brecha absoluta no tiene por qué ser pequeña. En pocas palabras: es una estimación aproximada, no una aproximación exacta. para su máximo:

E [i max X_{i}] \approx μ + σ 2 ln k

Exponenciando, el valor típico de $M$ escala como

exp (μ + σ 2 ln k)

a orden dominante. $2 ln k$ es el nivel que se espera que supere una de $k$ normales estándar: se fija $k (1 - Φ (b)) = 1$ y se usa la cola gaussiana $1 - Φ (b) \approx φ (b) / b$ , lo que da $b = 2 ln k$ a orden dominante. Es la secuencia de centrado en el teorema de Fisher-Tippett-Gnedenko para la normal; la expansión completa resta los términos de $ln ln k$ mencionados arriba. Existen correcciones de $O (1/ ln k)$ que involucran $ln ln k$ (visibles en el gráfico de Monte Carlo de arriba como una brecha apreciable para $k$ finito), pero el escalado es lo que cuenta la historia.

El exponente crece como $ln k$ , de modo que el máximo crece sin cota en $k$ , aunque muy lentamente. Hay algunas conclusiones prácticas de esto:

La varianza es mucho más importante que la media: $σ$ domina el tiempo de finalización en cuanto $k$ es lo suficientemente grande como para que $σ 2 ln k > μ$ . En ese régimen, la misma reducción absoluta en $σ$ recorta $2 ln k$ veces más del exponente que la misma reducción en $μ$ , y la brecha crece con $k$ .
El máximo solo se mueve hacia arriba, y agregar más subtareas paralelas tiene retornos decrecientes en latencia.
Una sola subtarea lenta y rara lo arruina todo. El tiempo de finalización es extremadamente sensible a la cola de la distribución por tarea.

¿Qué pasa si no las necesitamos todas?

La barrera completa (esperar las $k$ subtareas) es el peor caso. En la práctica, a menudo no necesitamos que todas las subtareas terminen: podemos tolerar algún número $c$ de rezagados y usar solo los $k - c$ resultados más rápidos. Esta es la generalización de estadístico de orden del máximo.

Si ordenamos los tiempos de finalización de las subtareas $N_{(1)} \leq N_{(2)} \leq \dots \leq N_{(k)}$ , el tiempo para obtener los primeros $j$ es $N_{(j)}$ , cuya CDF es:

F_{(j)} (x) = i = j \sum k (i k) F (x)^{i} (1 - F (x))^{k - i}

Cuando $j = k$ esto colapsa de nuevo en $F (x)^{k}$ (el máximo). El caso $j < k$ es donde se pone interesante:

El gráfico de arriba muestra el tiempo de espera esperado en función de $k$ para tres «fracciones de barrera»: esperar el 100% de las subtareas (la barrera completa), esperar el 95% más rápido y esperar el 50% más rápido (la mediana):

La barrera completa crece aproximadamente como $exp (σ 2 ln k)$ , como se discutió arriba.
Tolerar una cola de rezagados del 5% limita la espera a un valor mucho menor: cada subtarea adicional brinda unas pocas «salidas» más, que en conjunto absorben la cola.
Tolerar una cola de rezagados del 50% hace que el tiempo de espera sea aproximadamente constante en $k$ . Cuando $k \to \infty$ , la mediana muestral converge a la mediana poblacional $e^{μ}$ , que no depende de $σ$ en absoluto.

Esta idea aparece en todas partes, con un caso famoso en el entrenamiento distribuido. El SGD síncrono espera los gradientes de los $N$ workers antes de dar un paso, de modo que el tiempo de paso es el máximo de $N$ y un worker lento detiene a todos. Chen et al. (2016) agregan $b$ workers de respaldo y dan el paso en cuanto los $N$ más rápidos de los $N + b$ reportan, descartando los $b$ más lentos. El tiempo de paso pasa a ser el estadístico de orden $N$ de $N + b$ en lugar del máximo de $N$ , y como aún se agregan exactamente $N$ gradientes, el batch efectivo (y su varianza) no cambia (al costo de los $b$ gradientes calculados y descartados en cada paso).

¿Qué podemos hacer al respecto?

Si el sistema tiene una barrera rígida sin $c$ de sobra, el truco anterior no está disponible. Aun así, hay algunas cosas que se pueden hacer.

Reducir σ

Como el máximo crece en $exp (σ 2 ln k)$ , recortar $σ$ tiene un impacto desproporcionado. Con $k = 10, 000$ tenemos $2 ln k \approx 4.3$ , de modo que cada $0.1$ que se le recorta a $σ$ divide el máximo típico por $e^{0.43} \approx 1.5$ , mientras que el mismo $0.1$ quitado de $μ$ solo lo divide por $e^{0.1} \approx 1.1$ .

Las causas comunes de varianza en los tiempos de finalización de subtareas incluyen pausas de GC, cachés frías, bloqueo de cabeza de línea, contención de mutex, jitter de red y vecinos ruidosos. Rastrearlas suele ser la acción de mayor impacto que se puede tomar Y una gran herramienta para esto es el Control Estadístico de Procesos . Disfruto mucho todo lo escrito por Donald J. Wheeler para aprender sobre este tema. .

Reducir k

Ya sea mediante batching (procesar muchos ítems por subtarea) o mediante fan-out jerárquico (dividir un fan-out de $k$ vías en un fan-out de $k$ vías de fan-outs de $k$ vías). El batching es el que realmente mueve el máximo, porque recorta $k$ directamente:

// One task per file becomes one task per batch of 16: k drops 16x,
// at the cost of each task now doing 16x the work.
await Task.WhenAll(files.Chunk(16).Select(CompileBatchAsync));

La jerarquía principalmente te compra organización contable (menos hijos por nodo, manejo de fallos más sencillo); para latencia pura solo ayuda cuando cada nodo intermedio realiza su propio trabajo no trivial, ya que el máximo global en un árbol de solo enrutamiento sigue siendo el máximo de las $k$ hojas sin importar la forma del árbol.

Solicitudes de cobertura

Si una subtarea puede ser atendida por múltiples réplicas, enviar la solicitud a $r$ de ellas y tomar la primera respuesta:

// Race r replicas, take the first answer, cancel the losers.
async Task<Response> HedgedAsync(IReadOnlyList<Replica> replicas)
{
    using var cts = new CancellationTokenSource();
    var inFlight = replicas.Select(r => r.QueryAsync(cts.Token)).ToList();
    var winner = await Task.WhenAny(inFlight);
    cts.Cancel();
    return await winner;
}

Suponiendo que las latencias por réplica son independientes, esto reemplaza la distribución por réplica $F$ con $1 - (1 - F)^{r}$ , lo que eleva al cuadrado (para $r = 2$ ) la probabilidad de cola. La desventaja es enviar $r \times$ la carga al sistema subyacente, lo que rara vez es gratis. Un compromiso habitual es esperar hasta algún cuantil (por ejemplo, p95) antes de emitir la solicitud de cobertura, lo que acorta drásticamente la cola mientras envía solo ~5% de carga extra:

// Cheaper: only hedge the requests that have already gone slow.
async Task<Response> HedgeAfterAsync(Replica primary, Replica backup, TimeSpan p95)
{
    var first = primary.QueryAsync();
    if (await Task.WhenAny(first, Task.Delay(p95)) == first)
        return await first;                 // primary beat the p95 deadline
    using var cts = new CancellationTokenSource();
    var second = backup.QueryAsync(cts.Token);
    var winner = await Task.WhenAny(first, second);
    cts.Cancel();
    return await winner;
}

El artículo de Dean y Barroso The Tail at Scale es la referencia canónica para esto. Simular las tres estrategias muestra cuánto se desplaza la barrera: la cobertura completa ( $r = 2$ ) la aplana casi por completo, y el compromiso p95 recupera la mayor parte de ese beneficio con una fracción de la carga extra.

Reemitir especulativamente los rezagados

Una variante de la cobertura para cuando las subtareas no están naturalmente replicadas. Si una subtarea tarda más de lo esperado (por ejemplo, supera algún cuantil de la distribución), reemitirla a un worker diferente y tomar cualquier respuesta que llegue primero. Es la misma carrera que en HedgeAfterAsync arriba, excepto que el respaldo va a un worker nuevo en lugar de a una réplica, de modo que el gráfico de cobertura también lo describe. Este es el truco que usa MapReduce para lidiar con las tareas rezagadas.

Conclusión

Las barreras convierten la latencia de cola por tarea en el costo dominante del fan-out, y ese costo crece con el número de subtareas. La matemática dice que el crecimiento es lento ( $ln k$ en el exponente para log-normal), pero en la práctica eso sigue siendo doloroso: duplicar $k$ empuja el máximo hacia arriba, y cualquier varianza adicional aparece amplificada en la barrera.

Las dos mejores mitigaciones que encontré en la práctica son (a) rastrear las fuentes de varianza en la distribución por tarea y (b) evitar la barrera completa siempre que sea posible. « $k - c$ de $k$ » suele ser suficiente y es dramáticamente más barato; todo lo demás (cobertura, rejecución especulativa, fan-out jerárquico) es derivado de esas dos.