I. Introduction
On-Line Data Intensive (OLDI) applications such as web search, advertising, and online retail form a major fraction of data center applications [105]. Meeting soft real-time deadlines in the form of Service Level Objectives (SLOs) determines end-user experience [19], [47], [57], [90] and is of paramount importance. Whereas OLDI applications once had largely monolithic software architectures [51], modern OLDI applications comprise numerous, distributed microservices [69], [87], [108], [117] such as HTTP connection termination, key-value serving [73], query rewriting [49], click tracking, access-control management, protocol routing [22], etc. Several companies such as Amazon [3], Netflix [26], Gilt [12], LinkedIn [20], and SoundCloud [38] have adopted microservice architectures to improve OLDI development and scalability [126]. These microservices are composed via standardized Remote Procedure Call (RPC) interfaces, such as Google’s Stubby and gRPC [15] or Facebook/Apache’s Thrift [42].