Cutting Latency Tail: Analyzing and Validating Replication without Canceling Academic Article

journal

  • IEEE Transactions on Parallel and Distributed Systems

abstract

  • La variabilidad del tiempo de respuesta en las aplicaciones de software puede degradar gravemente la calidad de la experiencia del usuario. Para reducir esta variabilidad, la replicación de solicitudes surge como una solución efectiva al generar múltiples copias de cada solicitud y utilizar el resultado de la primera que se complete. La mayoría de los estudios anteriores se han centrado principalmente en la latencia media de los sistemas que implementan la cancelación de réplicas, es decir, todas las réplicas de una solicitud se cancelan una vez que termina la primera. En cambio, desarrollamos modelos para obtener la distribución del tiempo de respuesta para sistemas en los que la cancelación de réplicas puede ser demasiado costosa o inviable de implementar, como en los sistemas "rápidos", como los servicios web, o en los sistemas heredados. Además, introducimos un nuevo modelo de servicio para considerar explícitamente la correlación en los tiempos de procesamiento de las réplicas de las solicitudes, y diseñamos un algoritmo eficiente para parametrizar el modelo a partir de datos reales. Las evaluaciones exhaustivas de un benchmark de MATLAB y una aplicación web de tres niveles (MediaWiki) muestran una precisión notable, por ejemplo, un error medio del 7 (4 por ciento) en el tiempo de respuesta del percentil 99 para el benchmark (respectivamente, MediaWiki), cuyas peticiones se ejecutan en el orden de los segundos (respectivamente, milisegundos). De este modo, se obtiene información sobre los niveles óptimos de replicación a partir de este análisis cuantitativo preciso, bajo una amplia variedad de escenarios de sistema.
  • Response time variability in software applications can severely degrade the quality of the user experience. To reduce this variability, request replication emerges as an effective solution by spawning multiple copies of each request and using the result of the first one to complete. Most previous studies have mainly focused on the mean latency for systems implementing replica cancellation, i.e., all replicas of a request are canceled once the first one finishes. Instead, we develop models to obtain the response-time distribution for systems where replica cancellation may be too expensive or infeasible to implement, as in 'fast' systems, such as web services, or in legacy systems. Furthermore, we introduce a novel service model to explicitly consider correlation in the processing times of the request replicas, and design an efficient algorithm to parameterize the model from real data. Extensive evaluations on a MATLAB benchmark and a three-tier web application (MediaWiki) show remarkable accuracy, e.g., 7 (4 percent) average error on the 99th percentile response time for the benchmark (respectively, MediaWiki), the requests of which execute in the order of seconds (respectively, milliseconds). Insights into optimal replication levels are thereby gained from this precise quantitative analysis, under a wide variety of system scenarios.

publication date

  • 2017/11/1

edition

  • 28

keywords

  • Application programs
  • Chemical analysis
  • Legacy systems
  • MATLAB
  • Processing
  • Response time (computer systems)
  • Web services

International Standard Serial Number (ISSN)

  • 1045-9219

number of pages

  • 14

start page

  • 3128

end page

  • 3141