SkewTide: Bridging Efficiency and Tail Latency in Key-Value Stores via Kernel Re-Architecture

Key-value stores are the key building block of online services such as e-commerce. However, highly skewed workloads (i.e., skewed access frequency and request size) may cause severe load imbalance and head-of-line blocking, resulting in significant performance penalty (e.g., low throughput and high latency). Existing works mitigate skewed workloads, but often struggle to balance CPU efficiency with low tail latency or require specialized hardware. In this paper, we present SkewTide, an in-kernel architecture that breaks this trade-off through workload-aware request pre-processing and bypassing unnecessary network stack operations. Moreover, SkewTide carefully orchestrates size-aware parsing, sharding, caching, and queueing in the kernel. Both designs enable efficient CPU multiplexing and preserve low tail latency without specialized hardware. We implement SkewTide as an out-of-the-box framework using eBPF, making it readily deployable in existing key-value store infrastructure. Evaluation with YCSB traces shows that SkewTide achieves up to 8.1× higher throughput, 37% lower 99th-percentile latency, and 32% lower CPU usage compared to existing systems.