AC-Cache: A Memory-Efficient Caching System for Small Objects via Exploiting Access Correlations

Abstract

In-memory key-value (KV) caching bridges the performance gap between high-performance networks and disk devices. However, 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, an access-correlation-aware in-memory caching system for small objects. AC-Cache comprises three design primitives: (i) we formulate the distribution of KV objects as an integer linear programming problem to balance data accesses and memory consumption; (ii) we capture the access 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 with billions of objects 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%.