In-memory key-value (KV) caching bridges the performance gap between high-performance networks and disk devices. Prior in-memory KV caching systems either consider large objects or introduce additional memory overhead. In this paper, we conduct a systematic analysis over 56 production traces, and make three observations: (i) small objects dominate the traces and data accesses are highly skewed; (ii) the hotness of objects keeps stable across days; and (iii) the multi-get operation that retrieves multiple objects from the same node incurs much shorter tail latency than purely using the single-get operation.

These observations motivate the design of AC-Cache, a correlation-aware distribution scheme of KV objects for in-memory caching systems. AC-Cache comprises three design primitives: (i) we formulate the distribution of KV objects as an integer linear programming problem, seeking to balance both data accesses and memory overhead; (ii) we capture the object correlation in a memory-efficient means and generate fine-grained correlation groups; and (iii) we formulate the distribution of the correlation groups as a maximum flow problem to balance data accesses, and leverage a heuristic algorithm to dispatch other KV objects to balance memory consumption. Extensive experiments on Alibaba Cloud show that AC-Cache can reduce the tail latency by 5.1–80.2% and increase the access throughput by 42.8–534.8%.