Which achieves lower latency with redundant requests, replication or coding?

Abstract

A large-scale distributed storage system is the foundation for big data operations and applications, and replication and coding are the main methods to combat failures. Access latency is a key performance metric in such systems due to its great impact on user experience. Sending redundant requests is a popular and effective approach to reduce latency. It is therefore significant to present a fair latency comparison between replication and coding with the redundant scheduling. We analyze the latency of replication in the general case in which each request desires more than one data block. In the low arrival rate scenario, we give the exact latency analysis of replication, which is a novel generalization of the order statistic analysis of coding, and prove that coding achieves lower latency in this case. In the high arrival rate scenario, we point out the shortcomings of the latency comparison based on some popular latency bounds with redundant scheduling. In addition, this work is an earlier attempt to demonstrate the early cancellation advantage of replication and shows that, with redundant requests, coding can better reduce latency only in the low system load case while replication can achieve lower latency when the system load becomes high. We validate our analysis through extensive simulations using real latency traces from Amazon S3.