Aproximación de la expulsión LRU con un data sketch de cuantiles

El problema

Supongamos que tenemos un almacén de clave-valor residente en disco con algunos millones de entradas y un presupuesto de disco fijo de algunos GB. Cada entrada sabe cuándo fue tocada por última vez. Queremos expulsión LRU: cuando el almacén se acerque al límite, descartamos las entradas que no fueron tocadas durante más tiempo, hasta quedar por debajo del límite.

LRU es sencillo cuando los datos viven en memoria. Se mantiene una lista doblemente enlazada de claves ordenadas por tiempo de acceso, se mueve una clave al frente en cada acceso y se extrae del fondo cuando se necesita espacio. La receta estándar asume tres cosas:

Duplicar el almacenamiento de claves es barato (los punteros de la lista son insignificantes comparados con el valor).
Mover una clave es barato (un par de escrituras de punteros).
La estructura de datos que mantiene el orden puede mantenerse consistente con los datos en sí, porque la abstracción subyacente soporta actualizaciones atómicas.

Ninguna de esas condiciones se cumple en nuestro escenario:

Los datos son residentes en disco, así que duplicar cada clave en un índice de orden de acceso separado consumiría parte del presupuesto de disco que precisamente queremos respetar.
Mover claves implica escrituras en disco, lo que significa amplificación de escritura y desgaste del SSD. Y la atomicidad entre claves relacionadas requiere locks costosos que cualquier diseño razonable quiere mantener fuera del camino crítico.

Por lo tanto, necesitamos un LRU que no requiera mantener un orden LRU.

Primer intento: mantener los K mejores

Un primer intento natural es un GC acotado por cantidad de entradas. El contrato es: «cuando terminemos, la DB tiene a lo sumo $K$ entradas, y las que conservamos son las $K$ accedidas más recientemente». Un único recorrido sobre la DB activa, un min-heap de tamaño $K$ indexado por tiempo de acceso, y al final se expulsa todo lo que no estaba en el heap. Eso es $O (N lo g K)$ de trabajo y $O (K)$ de memoria, lo cual está bien.

Esto resuelve una versión real del problema, pero responde la pregunta equivocada. El presupuesto de disco está en bytes, no en entradas. Dos bases de datos con el mismo número de entradas pueden diferir en tamaño por un factor de 10 si una tiene algunos valores enormemente pesados. Para traducir «queremos estar por debajo de $B$ bytes» a «queremos a lo sumo $K$ entradas», tendríamos que conocer el tamaño promedio de entrada, que el heap no nos dice. Podríamos calcularlo sobre la marcha, pero entonces $K$ se convierte en un objetivo móvil y el heap deja de dar la respuesta correcta.

El otro problema (quizás menos obvio) es que $O (K)$ de memoria puede ser muchos GB, que puede que tengamos o no disponibles.

Data sketches de cuantiles en 60 segundos

Un data sketch de cuantiles es una estructura de datos pequeña que consume un flujo de números y responde «¿qué valor está en el cuantil $q$ de todo lo que vi?» con error acotado y memoria acotada. Son parientes de los más famosos Bloom filter , Count-Min y HyperLogLog , pero mientras esos hacen sketching de pertenencia a conjuntos, frecuencia y cardinalidad respectivamente.

Las estructuras de datos bien conocidas para data sketching de cuantiles son t-digest , Greenwald-Khanna y DDSketch . Las primeras dos ofrecen lo que se denomina garantías de error en rango: el valor devuelto está dentro de $ε$ del cuantil verdadero en espacio de rango. Así que con $q = 0.99$ y $ε = 0.01$ , la respuesta está en algún lugar entre el percentil 98 y el 99 verdaderos. Esa es una garantía excelente para distribuciones simétricas y una mala para distribuciones de cola pesada: cerca de la cola, un pequeño error de rango puede ser un enorme error de valor.

DDSketch ofrece un error relativo de valor: el $\tilde{x}_{q}$ devuelto satisface $∣ \tilde{x}_{q} - x_{q} ∣ \leq α \cdot x_{q}$ para un $α$ configurable. Lo logra poniendo muestras en buckets con espaciado exponencial: el bucket $i$ cubre $(γ^{i - 1}, γ^{i}]$ para $γ = (1 + α) / (1 - α)$ , y el cuantil se lee recorriendo los buckets. Esa propiedad es exactamente lo que queremos para edades que abarcan varios órdenes de magnitud.

Así se ve esto con un puñado pequeño de muestras para que se pueda ver cómo los valores individuales se mapean en buckets. Cada punto es una muestra, apilada verticalmente dentro de su bucket; las líneas verticales punteadas son los límites de los buckets $γ^{i}$ , igualmente espaciados en el eje logarítmico. Para leer el cuantil $q$ , el sketch recorre los buckets de izquierda a derecha y acumula conteos hasta que el total acumulado alcanza $⌈ q N ⌉$ ; ese bucket (resaltado) es la respuesta, y el valor devuelto se fija en algún lugar dentro de él. La línea roja punteada muestra el cuantil verdadero de la distribución subyacente; la garantía de error relativo dice que la línea verde está dentro de un factor $γ$ de la roja.

Un $α$ más pequeño significa buckets más estrechos (más de ellos, más memoria) y una banda más ajustada alrededor del valor verdadero. El sketch completo es simplemente un mapa disperso del índice de bucket al conteo, así que su memoria crece con el número de buckets ocupados, no con $N$ .

El algoritmo

La edad de una entrada es simplemente age = now - lastAccessTime, en alguna unidad. Si tuviéramos una lista ordenada de edades, expulsar la fracción $ρ$ más antigua sería trivial: leer la lista al revés y expulsar hasta liberar suficientes bytes. La lista ordenada es exactamente lo que no podemos costear. Pero lo único que realmente necesitamos de ella es un solo número: el umbral de edad $T^{*}$ por encima del cual las entradas deben eliminarse.

Entonces el algoritmo consiste en dos recorridos completos sobre la DB:

Ajustar el sketch. Recorrer la DB, e insertar la edad de cada entrada en un DDSketch. También se mantienen dos sumas acumuladas: el total de bytes en la DB, $B_{total}$ , y el total de bytes que queremos eliminar en esta ronda, $B_{remove}$ .
Leer el umbral y expulsar. Calcular la fracción a conservar: $f_{keep} = 1 - B_{remove} / B_{total}$ . Pedirle al sketch el cuantil de edad correspondiente: $T^{*} = sketch.Quantile (f_{keep})$ . Recorrer la DB nuevamente, y Remove cada entrada cuya edad supere $T^{*}$ .

Eso es todo. El sketch es el puente entre «queremos liberar X bytes» y «deberíamos expulsar cada entrada más vieja que Y minutos». Todo el proceso requiere $O (N)$ de trabajo y $O (sketch)$ de memoria, lo que en la práctica resulta ser muy poco (del orden de KB a MB, dependiendo de cuánta precisión se quiera).

Así se ve el estado del sketch en la práctica para una distribución de edades log-normal con forma $σ$ . Las barras azules son los conteos de buckets de DDSketch (nótese el espaciado constante en el eje x logarítmico, ya que el bucket $i$ cubre $(γ^{i - 1}, γ^{i}]$ ); la línea es la densidad subyacente. La línea roja punteada es el umbral verdadero $T^{*}$ ; la línea verde sólida es la estimación del sketch $\tilde{T}^{*}$ , leída recorriendo los buckets desde arriba hasta que el conteo acumulado alcanza $ρ \cdot N$ .

El error relativo impreso encima de $\tilde{T}^{*}$ combina dos efectos: la grilla de buckets de DDSketch (acotada por $α$ según la siguiente sección) y el ruido de muestra finita sobre en qué bucket cae el umbral. Reducir $α$ ajusta la grilla; aumentar $N$ reduce el ruido.

¿Por qué funciona esto?

Hay tres cosas que pueden salir mal: el sketch puede dar el $T^{*}$ incorrecto, la traducción de conteo a bytes en el paso 2 puede fallar porque el sketch está ponderado por edad pero el presupuesto está en bytes, y el sketch puede ser demasiado grande para que valga la pena. Acotemos cada una.

Error del sketch

La Proposición 3 del artículo de DDSketch es la clave aquí: para cualquier $q \in [0, 1]$ , el $\tilde{T}^{*}$ devuelto satisface

∣ \tilde{T}^{*} - T^{*} ∣ \leq α \cdot T^{*}

de manera determinista, donde $α$ es el parámetro de error relativo del sketch.

Eso da un error de edad. Lo que nos importa es el error resultante en la fracción de expulsión: apuntamos a una fracción $ρ = 1 - f_{keep}$ de entradas por encima del umbral, y obtenemos $\tilde{ρ} = 1 - F (\tilde{T}^{*})$ en cambio, donde $F$ es la CDF verdadera de las edades. En primer orden:

∣ \tilde{ρ} - ρ ∣ \approx f (T^{*}) \cdot ∣ \tilde{T}^{*} - T^{*} ∣ \leq α \cdot T^{*} f (T^{*})

donde $f$ es la densidad. La cantidad $T^{*} f (T^{*})$ es la densidad de $ln T$ en el umbral, que mide qué tan rápido se mueve la CDF por unidad de cambio relativo en la edad. Eso es exactamente a lo que se traduce la garantía de error relativo de DDSketch.

Para edades que son aproximadamente log-normales con forma $σ$ , que es el modelo correcto cuando la mayoría de las cosas se tocan en los últimos minutos y una cola larga pasa semanas sin ser accedida, la aproximación de cola normal estándar da

T^{*} f (T^{*}) \approx \frac{ρ 2 ln ( 1/ ρ )}{σ}

Entonces el error relativo en la fracción de expulsión está acotado por $α 2 ln (1/ ρ) / σ$ . Para $α = 0.01$ , $ρ = 0.1$ , $σ = 2$ , eso es aproximadamente $1%$ . Con $α = 0.01$ le pedimos al umbral que se desvíe no más de un 1% en unidades de edad, y obtenemos una desviación de no más del 1% en la fracción de expulsión.

Error de conteo a bytes

El sketch ve una observación por entrada, independientemente del tamaño, así que responde en términos de conteo: $ρ$ es la fracción de entradas por encima del umbral. Pero el presupuesto está en $B_{remove}$ bytes. La traducción solo es válida si los tamaños de las entradas son estadísticamente independientes de la edad, una suposición a la que volveremos en la siguiente sección.

Concedida la independencia: sean $S_{1}, \dots, S_{K}$ los tamaños de las $K \approx ρN$ entradas expulsadas. Por el teorema central del límite ,

i = 1 \sum K S_{i} \sim N (K μ_{S}, K σ_{S}^{2})

así que los bytes liberados tienen desviación estándar relativa $σ_{S} / (μ_{S} K) = (σ_{S} / μ_{S}) / ρN$ .

Si los tamaños tienen cola suficientemente pesada como para que $σ_{S} / μ_{S}$ sea alrededor de 1, con $N = 1 0^{6}$ y $ρ = 0.1$ eso es $1/ 1 0^{5} \approx 0.3%$ a una sigma, o sea alrededor de $1%$ a tres sigmas (¡es decir, comparable al error del sketch!).

Cota de memoria

DDSketch usa un bucket por cada paso multiplicativo de tamaño $γ = (1 + α) / (1 - α)$ . Para $α = 0.01$ , $γ \approx 1.0202$ y $ln γ \approx 0.02$ . Si las edades van desde un milisegundo hasta algunos días, eso son unos 9 órdenes de magnitud, así que

buckets \approx \frac{ln ( 1 0 ^{9} )}{ln γ} \approx \frac{20.7}{0.02} \approx 1 0^{3}

Unos pocos miles de buckets, cada uno almacenando un conteo entero, da tal vez 20 KB (¡gratis, genial!).

Juntando todo

Combinando los tres: el error del sketch da $\approx 1%$ de error relativo en el conteo de expulsión, el TCL da otro $\approx 1%$ en la traducción de conteo a bytes a 3 $σ$ , y el sketch en sí no cuesta nada. En total: con probabilidad $\geq 99%$ una sola ronda libera dentro de unos pocos puntos porcentuales del byte objetivo. Eso es suficientemente bueno para un GC que corre periódicamente, porque cualquier desvío en esta ronda lo corrige la siguiente.

Algunos problemas en el camino

Hay algunas cosas que merecen mencionarse:

Drift del snapshot. Ambos recorridos iteran sobre una DB, pero la DB activa sigue cambiando en el medio. El umbral calculado en el recorrido 1 puede estar ligeramente desactualizado para cuando el recorrido 2 expulse basándose en él, y el recorrido 2 puede intentar eliminar entradas que fueron tocadas recientemente entre medio. Si la ventana de GC es corta en relación con la cadencia de accesos, esto no importa demasiado; de lo contrario, el análisis anterior deja de aplicarse porque la distribución no es estacionaria a lo largo de la ejecución del GC. En la práctica, he visto este truco elegante funcionar incluso con diferencias de varias horas.

Tamaño independiente de la edad. La cota del TCL depende de que los tamaños no estén correlacionados con la edad. Eso es aproximadamente cierto cuando la causa relevante de «esto es viejo» es algo como un patrón de acceso dormido más que una propiedad de la entrada en sí. Esto se complica, por ejemplo, en un caché donde los archivos más grandes permanecen más tiempo porque son más costosos de volver a obtener. Si el tamaño y la edad correlacionan, la solución correcta es insertar en el sketch con peso igual al tamaño de la entrada: así los cuantiles del sketch son cuantiles de bytes directamente, y la traducción de conteo a bytes desaparece.

¿Pero podemos hacer esto más rápido?

El algoritmo paga por dos recorridos completos de la DB por ciclo de GC. Hay algunos trucos que podemos aplicar para ahorrar parte de ese costo:

El primer recorrido puede omitirse si se mantiene el sketch caliente entre ciclos (insertando en cada acceso, opcionalmente con un decaimiento). Si vale la pena depende de si el costo de lectura del disco domina el costo de mantenimiento por acceso (generalmente sí), y de cuán disciplinado se puede ser al actualizar el sketch en cada ruta de código que toca la DB (generalmente menos de lo que uno esperaría).
Se puede escanear menos que la totalidad de la DB. Por ejemplo, se podría usar muestreo por reservorio para mantener una muestra aleatoria de claves en memoria, y ajustar el sketch sobre esa muestra en lugar de toda la DB. El análisis de error del sketch sigue siendo válido, pero la traducción de conteo a bytes acumula una capa adicional de ruido de muestreo. Con una muestra suficientemente grande, ese ruido sería lo bastante pequeño como para no cambiar mucho las cotas de error globales.

Conclusión

La conclusión es el título: cuando la estructura de datos obvia es un índice ordenado y no podemos costear mantenerlo, conviene preguntarse qué necesitamos realmente de él. Si lo que necesitamos es un único umbral, un data sketch de cuantiles nos dará ese umbral con error acotado en memoria acotada.

Este mismo truco aplica en cualquier lugar donde un orden global alimentaría un umbral (limitación de tasa por presupuesto de latencia, planificación de capacidad por percentil de tamaño de solicitud, alertas sobre una métrica de cola sin ordenar todo). DDSketch resulta ser un excelente punto de partida cada vez que el valor de interés abarca varios órdenes de magnitud.