How HotRing Boosts In-Memory KV Store Performance by 2.58×

01 Overview

Alibaba Cloud's intelligent database Tair team, responsible for a self‑developed distributed key‑value store used across Alibaba’s core businesses, recently had a paper titled HotRing: A Hotspot‑Aware In‑Memory Key‑Value Store accepted at FAST'20 (USENIX FAST, CCF A‑class, 16% acceptance).

HotRing is an innovative pure‑memory KV engine whose throughput can reach 600 M ops/s, delivering a 2.58× performance improvement over the fastest existing KV systems, primarily by dramatically increasing hotspot handling capacity.

02 Background

Zero‑Hour Peak

During the 2019 Tmall Double‑11 event, the order peak at midnight reached 544 k orders per second, translating to roughly 1 B accesses per second when considering business logic amplification and pure traffic spikes. Tair’s peak access was 992 M accesses per second, acting as a distributed cache for hot data such as products, inventory, and risk‑control information.

Hotspot Problem

Business‑level hotspots follow a heavy‑tailed (Zipfian) distribution with a θ parameter around 1.22, meaning a small fraction of keys receive the majority of accesses. This leads to severe load skew, risking node overload and system crashes.

Hotspot Optimizations

Client‑side cache: pre‑mark hotspots and cache them on the client to reduce KV load.

Hotspot hashing: replicate hotspot data across multiple KV nodes to spread the load.

RCU lock‑free engine: use Read‑Copy‑Update to achieve lock‑free memory KV access.

HotRing: a hotspot‑aware memory KV engine built on top of the RCU lock‑free engine, dynamically identifying hotspots and adjusting the index structure without locks.

The accumulated technology has been released as Alibaba Cloud Redis Enterprise.

03 HotRing

Existing Techniques

Traditional in‑memory KV engines use chained hashing: a key is hashed to a bucket, then traversed through a collision chain. Accessing items at the tail of a long chain incurs many memory hops.

Because insertion order determines a key’s position in the chain, hot items are uniformly distributed, offering no advantage for hotspot access.

Design Challenges

Moving all hotspots to the head of the chain is difficult because hotspot popularity changes dynamically and the engine must remain lock‑free with sub‑100 ns latency.

HotRing Overall Design

HotRing transforms the chained hash into an ordered ring hash. The collision chain is closed into a ring, and the head pointer can move lock‑free to point to the hottest item, allowing faster hotspot access.

Design 1 – Ordered Ring

To avoid infinite traversal, HotRing orders items by a composite (tag, key) where the tag is part of the hash value. This ordering lets the engine detect a read‑miss when the target key falls between two consecutive items, terminating the scan after roughly half the ring on average.

Design 2 – Dynamic Hotspot Identification

HotRing employs two strategies, each triggered every R accesses (R≈5):

Random move: the head pointer jumps to the R‑th accessed item.

Sampling analysis: a lightweight sampling records total accesses and per‑item counters, allowing the engine to compute the optimal head position.

Sampling uses the unused high bits of 64‑bit pointers to store counters without extra memory overhead.

Design 3 – Lock‑Free Concurrency

Based on the RCU lock‑free linked‑list technique, HotRing ensures that concurrent insertions, updates, and head‑pointer moves compete on the same memory word (e.g., an Occupied flag), guaranteeing correctness without locks.

Design 4 – Lock‑Free Rehash for Varying Hotspot Volume

HotRing replaces the traditional load‑factor trigger with an access overhead metric (average memory hops per access). When the overhead exceeds 2, a background rehash thread creates a new hash table with doubled space, splits the ring based on tag ranges, and performs a lock‑free transition after an RCU grace period.

04 Conclusion

In‑memory KV stores are widely used as high‑performance caches in cloud storage services, but they suffer from severe hotspot skew that can cause node failures. HotRing introduces a hotspot‑aware index that dynamically moves hot items to the head of an ordered ring, employs lock‑free concurrency, and uses access‑overhead‑driven rehashing. Compared with traditional KV engines, HotRing achieves up to 600 M ops/s throughput—a 2.58× improvement—without additional metadata overhead.

References

John D. Valois. Lock‑free linked lists using compare‑and‑swap. PODC 1995.

Timothy L. Harris. A Pragmatic Implementation of Non‑blocking Linked‑lists. DISC 2001.

Berk Atikoglu. Workload Analysis of a Large‑Scale Key‑Value Store. SIGMETRICS 2012.