Cómo colaboramos con Meta (Facebook) para crear Shadow Cache

Con la colaboración entre Meta (Facebook), la Universidad de Princeton y Alluxio, hemos desarrollado "Shadow Cache", un componente ligero de Alluxio para rastrear el tamaño del conjunto de trabajo y la tasa de aciertos de caché infinita. El caché de sombra puede realizar un seguimiento dinámico del tamaño del conjunto de trabajo en la ventana anterior y se implementa mediante una serie de filtros de floración. La caché de sombra se implementa en Meta (Facebook) Presto y se aprovecha para comprender el cuello de botella del sistema y ayudar con las decisiones de diseño de enrutamiento.

Motivación y Antecedentes

En Meta (Facebook), Presto es un motor de consultas distribuido en tiempo real que utiliza lenguaje SQL como interfaz para realizar consultas rápidas e interactivas en petabytes de datos. Admite ANSI SQL estándar, incluidas consultas, agregaciones, JOIN y funciones de ventana.

Alluxio es la plataforma de orquestación de datos como una tecnología crítica que admite Presto y otras aplicaciones y casos de uso de análisis de datos. Alluxio crea una capa de datos virtuales que federa datos de cualquier sistema de archivos o almacén de objetos, proporciona un espacio de nombres unificado en todos los sistemas de almacenamiento y entrega los datos a las aplicaciones utilizando interfaces estándar de la industria con acceso rápido a los datos.

Para mejorar el rendimiento de Presto, es esencial comprender el impacto del tamaño de la memoria caché y la tasa de aciertos de la memoria caché. Presto necesita conocer cierta información de almacenamiento en caché de Alluxio para determinar si expandir el tamaño de la memoria caché puede ayudar a mejorar la tasa de aciertos y el rendimiento de la memoria caché cuando el almacenamiento de la memoria caché es limitado. Esta información también es útil para optimizar los algoritmos de almacenamiento en caché. También queremos optimizar el algoritmo de enrutamiento para un mejor equilibrio y eficiencia. Como resultado, la forma de rastrear y administrar mejor los datos de caché de Alluxio es clave para las decisiones de optimización de presto.

Dos preguntas clave deben abordarse desde el lado de Presto:

1. ¿Cómo dimensionar el caché para cada arrendatario?

2. ¿Cuál es la mejora potencial de la proporción de aciertos de caché?

Proponemos "Shadow Cache", un componente ligero de Alluxio para rastrear el tamaño del conjunto de trabajo y la tasa de aciertos de caché.

Para responder a la primera pregunta, Shadow Cache le dirá al administrador cuántos bytes no duplicados ha recibido el caché en las últimas 24 horas para estimar la futura demanda de caché. Para la segunda pregunta, Shadow Cache le dirá al administrador cuántas solicitudes llegaron a la memoria caché si la memoria caché puede mantener todas las solicitudes durante las últimas 24 horas, es decir, las que no fueron respondidas son las que nunca aparecieron, por lo que la tasa máxima de aciertos de el caché se puede calcular.

Este componente ligero de Alluxio, Shadow Cache, puede proporcionar información sobre el conjunto de trabajo de la memoria caché y cómo se vería la tasa de aciertos de la memoria caché si hubiera un espacio infinito en la memoria caché. Para monitorear el estado de caché del clúster, definimos las siguientes métricas clave.

• C1: uso de caché real en un momento determinado
• C2: conjunto de trabajo de caché de sombra en una ventana de tiempo (1 día / 1 semana)
• H1: Tasa de aciertos de caché real
• H2: Tasa de aciertos de Shadow Cache

El reto

Si bien hemos intentado proporcionar las métricas anteriores para el caché de Alluxio, hemos encontrado varios desafíos.

Baja sobrecarga de CPU y memoria

Shadow Cache es un componente liviano que realiza un seguimiento del tamaño de los conjuntos de trabajo almacenados en caché. Es difícil hacer un seguimiento de un conjunto de trabajo "infinito" con memoria limitada. Shadow Cache también debe tener una sobrecarga de CPU baja, ya que almacena en caché los datos al procesar cada consulta. De lo contrario, las solicitudes de los usuarios se bloquearán durante mucho tiempo.

Precisión

Shadow Cache también debe garantizar la precisión. En Presto, Shadow Cache mide el estado de caché de un clúster y, si la tasa de aciertos de caché límite estimada es demasiado baja, Presto puede determinar erróneamente que este trabajo no admite caché. Por el contrario, si la tasa de aciertos de caché límite estimada es demasiado alta, Presto puede creer que expandir la caché del clúster en este punto mejorará significativamente el rendimiento general.

Actualización dinámica

Presto y otras aplicaciones de datos modernas se utilizan principalmente para descubrir tendencias actuales o futuras. Por lo tanto, Shadow Cache también debería descartar elementos obsoletos en tiempo real. De lo contrario, es probable que interfiera con el ruido en la decisión. Las ventanas deslizantes son uno de los métodos más comunes para almacenar los elementos más nuevos, pero crear la estructura de datos para el modelo de ventana deslizante no es fácil. Cuando la ventana se desliza, debemos eliminar los elementos que se acaban de mover en tiempo real. Es importante encontrar el elemento que debe eliminarse lo más rápido posible y eliminarlo.

La solución

A la luz de los dos requisitos de alta precisión y baja sobrecarga, inmediatamente pensamos en el filtro Bloom, que ha ganado popularidad en varias bases de datos distribuidas. Shadow Cache estima el tamaño del conjunto de trabajo y la tasa de aciertos límite en función del filtro Bloom. Así es como los filtros Bloom resuelven los tres desafíos.

Filtros Bloom: la solución a los problemas de sobrecarga y precisión

El filtro Bloom es una prueba de membresía de estructura de datos probabilística eficiente en el espacio. Un filtro Bloom es una matriz inicializada con todos ceros en bits, y cada objeto se representa con solo varios bits, lo que ahorra espacio de manera significativa y proporciona consultas con una eficiencia excelente. Los filtros Bloom pueden determinar si un elemento existe o no. El elemento no debe existir si el filtro Bloom devuelve que no existe. Tenga en cuenta que los falsos positivos son posibles, pero los falsos negativos no.

El filtro Bloom tiene k funciones hash. Para agregar un elemento, aplique cada función hash y establezca el bit en 1. Para consultar un elemento, aplique cada función hash y AND los bits. Cuando todos los bits en las posiciones k son 1, se considera que el elemento existe. De lo contrario, el artículo no se considera que existe.

Bloom Filter Chain: la solución a la actualización dinámica

Los filtros Bloom pueden proporcionar una sobrecarga baja y una alta precisión, entonces, ¿podemos aplicarlos directamente a Shadow Cache?

El primer problema que encontramos es que los filtros Bloom no admiten la eliminación. Esto se debe a que solo nos importa el tamaño del conjunto de trabajo de la aplicación del usuario a lo largo del tiempo, y se requiere Shadow Cache para hacer esto. Shadow Cache hace esto al vincular varios filtros para crear una cadena de filtros Bloom.

Así es como se puede usar la cadena de filtros Bloom para actualizar el tamaño de carga del conjunto de trabajo en tiempo real.

Consulta: como se muestra arriba, Shadow Cache es una cadena compuesta por múltiples filtros Bloom. Al rastrear el tamaño del conjunto de trabajo de un usuario en las últimas 24 horas, podemos dividir las 24 horas en cuatro períodos. Un filtro Bloom rastrea cada período en Shadow Cache, y cada filtro Bloom rastrea un período. Shadow Cache usa todos los filtros Bloom existentes o crea un nuevo filtro Bloom para la consulta, como se muestra en la siguiente figura.

Actualización en vivo: para mantener los datos en tiempo real, necesitamos Shadow Cache para descartar los datos que se han vuelto obsoletos cuando la ventana de tiempo se está deslizando. Los valores del filtro Bloom deben actualizarse continuamente con el tiempo t, y los elementos del filtro Bloom que ya están fuera de la ventana de tiempo deben eliminarse. Dado que estamos combinando varios filtros Bloom, es fácil determinar dónde se encuentran los elementos obsoletos al final del filtro Bloom, como se muestra en la siguiente figura. Cada vez que comienza un nuevo período, eliminamos el filtro más antiguo de la cadena y agregamos un nuevo filtro completamente vacío para registrar los datos más recientes.

Tamaño del conjunto de trabajo : dado que los filtros de floración asignan un elemento a varios bits, juzgar el tamaño del conjunto de trabajo basándose únicamente en la cantidad de bits a 1 introduciría un error inaceptable, ya que un bit puede representar varios elementos y un elemento puede estar disperso entre varios bits. Por lo tanto, empleamos la fórmula derivada de Swamidass & Baldi (2007) . Aprovechamos la aproximación con la siguiente ecuación para medir el tamaño del conjunto de trabajo.

Donde n* es una estimación de la cantidad de elementos en el filtro, m es la longitud (tamaño) del filtro, k es la cantidad de funciones hash y X es la cantidad de bits establecidos en uno.

Proporción de aciertos de tamaño infinito: después de proporcionar la métrica de tamaño del conjunto de trabajo, Shadow Cache también debe proporcionar la proporción de aciertos de tamaño infinito. Podemos usar filtros Bloom como un caché con espacio infinito porque pueden rastrear grandes cantidades de datos con poco uso de memoria. La cantidad de solicitudes de usuario que llegan a un filtro Bloom es igual a la cantidad de visitas en una memoria caché infinita, indicada como una visita. El número total de "solicitudes de usuario" se indica como queryNum. QueryNum es el número total de "solicitudes de usuario", por lo que la tasa de aciertos es igual a hit/queryNum.

Uso de Shadow Cache para determinar el estado de caché de clúster de Presto

Después de completar la cadena de filtros Bloom, podemos aprender rápidamente las métricas definidas anteriormente H1, H2, C1, C2. En el siguiente paso, Presto puede determinar el estado de caché del clúster comparando la relación de tamaño entre ellos, como se muestra en la siguiente figura.

Cuando H2 es bajo, indica que la tasa de aciertos de caché de la aplicación en este clúster no se puede alcanzar incluso con espacio de caché ilimitado. Esto implica que esta aplicación no es compatible con caché. Cuando H2 es alto y H1 es bajo y C2 > C1, indica que el espacio de caché del clúster está infraasignado y la tasa de aciertos se puede mejorar aún más si se expande la capacidad de caché. Cuando H2 es alto y H1 es alto y C2 < C1, la memoria caché del clúster se sobreasigna y los recursos se desperdician. Un clúster está en buen estado si H2 > H1 y C2 > C1 y C2 > C1, lo que significa que no es necesario escalar la memoria caché.

Implementación

La implementación de Shadow Cache de los filtros Bloom se basa en Guava BloomFilter lib y admite configuraciones de filtro específicas basadas en el presupuesto de sobrecarga de memoria definido por el usuario y la ventana de shadow cache. Actualmente, Shadow Cache admite el tamaño del conjunto de trabajo en términos de #páginas y #byte, que representan cuántas páginas y cuántos bytes específicos contiene el conjunto de trabajo, respectivamente. Para el cálculo de la tasa de aciertos, Shadow Cache admite una tasa de aciertos de bytes de tamaño infinito y una tasa de aciertos de objetos.

A continuación se muestran las configuraciones.

#La ventana pasada para definir el conjunto de trabajo

alluxio.user.client.cache.shadow.window=**24h**

#La sobrecarga de memoria total para los filtros de floración utilizados para el seguimiento

alluxio.user.client.cache.shadow.memory.overhead=**125MB**

#La cantidad de filtros de floración utilizados para el seguimiento. Cada uno rastrea un segmento de la ventana

alluxio.user.client.cache.shadow.bloomfilter.num=**4**

Resultados de la prueba

Probamos Shadow Cache y descubrimos que con solo 125 MB de espacio, Shadow Cache puede rastrear 27 TB de conjuntos de trabajo con una tasa de error de solo el 3 %. Además, la tasa de error se puede reducir aún más mediante el uso de HyperLogLog, pero la estimación de la proporción de aciertos de tamaño infinito no se admitirá si se utiliza HyperLogLog.

Optimización de enrutamiento Presto

Para mejorar el rendimiento, Presto necesita una forma de ajustar el clúster a tiempo si aprende el estado específico del clúster de Shadow Cache. Nuestro próximo paso es describir el algoritmo de enrutamiento actual de Presto y luego brindar varias opciones para la optimización del enrutamiento después de presentar Shadow Cache.

Enrutamiento rápido

Presto almacena diferentes tablas en diferentes clústeres y comparte la caché entre clústeres por nombre de tabla. Por lo tanto, una consulta que acceda a la misma tabla siempre irá al mismo clúster de destino para maximizar su caché. La memoria caché del clúster se llenaría con varias tablas dispares si no se hiciera esto. A continuación se muestra un diagrama del algoritmo de enrutamiento.

Como se muestra en la figura anterior, la tabla 1 a la tabla 4 tienen nombres de tabla diferentes y, por lo tanto, se asignan a diferentes clústeres. Al solicitar datos de la tabla 1, el algoritmo de enrutamiento enviará la solicitud al clúster 1, y al solicitar datos de la tabla 3, el algoritmo de enrutamiento enviará la solicitud al clúster 3.

Opciones de optimización de enrutamiento

El tiempo de respuesta de una solicitud de clúster es una forma sencilla de determinar si un clúster está funcionando. Cuando el clúster responde lentamente o tarda demasiado en responder, asumimos que el clúster tiene un problema. Con Shadow Cache, como se mencionó anteriormente, combinado con H1, H2, C1, C2, podemos determinar rápidamente si un clúster está experimentando una degradación del rendimiento debido al estrés de la memoria caché.

Presto propone las siguientes tres opciones de optimización de enrutamiento para un clúster de bajo rendimiento. Por supuesto, cada opción tiene su contrapartida.

• Opción 1: cuando el clúster principal esté ocupado, tenga un clúster secundario designado con el caché activado para esas consultas. Sin embargo, este enfoque requiere el almacenamiento de caché de tablas adicionales en cada clúster.
• Opción 2: ambos clústeres se tratan como el clúster principal para atender solicitudes y el equilibrio de carga se realiza en ambos clústeres. Sin embargo, esta opción multiplicará el uso del espacio en disco de caché.
• Opción 3: cree el mapa de tablas a clústeres y haga que la utilización de la CPU sea más uniforme. Sin embargo, podría hacer que la distribución del almacenamiento de caché no sea uniforme y requiera espacio de caché adicional.

Resumen

El desafío de rastrear y estimar el tamaño del conjunto de trabajo en el caché es significativo, por lo que desarrollamos un componente liviano Shadow Cache de Alluxio usando filtros Bloom. Debido a que solo estamos interesados en el estado más reciente del conjunto de trabajo, es necesario usar un modelo de ventana de tiempo para eliminar los elementos obsoletos. Shadow Cache divide la ventana de tiempo en cuatro segmentos para este propósito. Cada segmento se rastrea con un filtro Bloom diferente. Se crea un nuevo filtro Bloom para rastrear los datos más recientes, reemplazando al más antiguo en cada eliminación. Finalmente, cuando se necesita proporcionar el tamaño del conjunto de trabajo, usamos la fórmula propuesta por Swamidass & Baldi (2007) para la estimación base.

En general, Shadow Cache le brinda a Presto cuatro métricas convenientes: H1, H2, C1, C2, donde H1 y C1 representan la tasa de aciertos y el uso reales de la memoria caché, respectivamente, mientras que H2 y C2 representan la tasa de aciertos límite de la memoria caché y el tamaño de el conjunto de trabajo del usuario durante un período de tiempo. Presto puede determinar rápidamente la relación entre la capacidad de caché y el rendimiento de la aplicación y optimizar el algoritmo de enrutamiento para un mejor equilibrio y eficiencia en función de las cuatro métricas anteriores.

Enlaces

• Código fusionado
• La versión china de este artículo.

Sobre los autores

Ke Wang es ingeniero de software en Meta (Facebook), y se enfoca en consultas de baja latencia en el equipo de Presto.

Zhenyu Song es un Ph.D. candidato en el departamento de Ciencias de la Computación de la Universidad de Princeton, investigando el aprendizaje automático para mejorar la eficiencia del almacenamiento en caché en las CDN.