  Modern latency-critical online services such as search engines often process
requests by consulting large input data spanning massive parallel components.
Hence the tail latency of these components determines the service latency. To
trade off result accuracy for tail latency reduction, existing techniques use
the components responding before a specified deadline to produce approximate
results. However, they may skip a large proportion of components when load gets
heavier, thus incurring large accuracy losses. This paper presents
AccuracyTrader that produces approximate results with small accuracy losses
while maintaining low tail latency. AccuracyTrader aggregates information of
input data on each component to create a small synopsis, thus enabling all
components producing initial results quickly using their synopses.
AccuracyTrader also uses synopses to identify the parts of input data most
related to arbitrary requests' result accuracy, thus first using these parts to
improve the produced results in order to minimize accuracy losses. We evaluated
AccuracyTrader using workloads in real services. The results show: (i)
AccuracyTrader reduces tail latency by over 40 times with accuracy losses of
less than 7% compared to existing exact processing techniques; (ii) when using
the same latency, AccuracyTrader reduces accuracy losses by over 13 times
comparing to existing approximate processing techniques.
