The Fastest KV Engine | Innovative Engine Developed by the Tair Team

1) Overview

2) Background

Peak Traffic at 00:00

Hot Spots

Hot Spot Optimization

  • Client Cache: Hot spot data is marked in advance for client-side caching. As shown in the preceding figure, the processing results of access requests are returned at the business layer to reduce the load on the KVS system.
  • Hot Spot Hash: Hot spot data is backed up on multiple KVS nodes to distribute the hot spot access traffic. The access traffic processing capability increases manifold, with lower resource consumption and system overhead.
  • Read-Copy-Update (RCU) Lock-free Engine: RCU enables lock-free access to the in-memory KVS engine. For more information, see Papers [1] and [2] in the “References” section. This significantly increases the KVS engine performance and its hot spot access traffic processing capability.
  • HotRing: As an innovative in-memory KVS engine designed with hot spot awareness based on index structures and developed from the RCU lock-free engine, HotRing dynamically identifies hot spots and adjusts index structures in real-time in lock-free mode. This significantly improves engine performance in power-law distribution scenarios.

3) HotRing

Existing Technologies

Design Challenges

  • Why use an ordered ring?
  • How to dynamically identify hot spots and adjust the head pointer?
  • How to ensure lock-free concurrent access?
  • How to implement a lock-free rehash based on dynamic changes in the amount of hot spot data?
  • Random Movement Policy: For every R accesses, the head pointer points to the item at the Rth access. The head pointer does not move if it already points to this item. This policy accelerates response and requires no extra metadata overhead or sampling.
  • Sampling Analysis Policy: For every R accesses, sampling is started on the corresponding collision ring to calculate the item access frequency. Sampling is not started if the head pointer already points to the item at the Rth access.
  • How the sampling analysis policy selects the optimal position of the head pointer
  • Sampling optimization based on RCU updates
  • Cold start prevention through hot spot inheritance
  • Initialization: HotRing creates a background rehash thread. This thread creates a new hash table with twice the space size and indexes the hash table by reusing the highest bit of the tag. Therefore, the new hash table has two head pointers that correspond to the single head pointer of the old hash table. HotRing divides data based on the tag range. If the maximum tag value is T and the tag range is [0, T), then the two new head pointers correspond to tags in the ranges [0, T/2) and [T/2, T). The rehash thread creates a rehash node that contains two sub-item nodes with empty data. Each of the sub-item nodes corresponds to a new head pointer. HotRing identifies the sub-item nodes of the rehash node based on the rehash flags of the sub-items.
  • Split: The rehash thread splits the ring by inserting the two sub-item nodes of the rehash node into the ring. As shown in the Figure “Split”, Item B and Item E are the range boundaries, so the sub-item nodes are inserted before Item B and Item E, respectively. After the two sub-item nodes are inserted, the new hash table is activated and all access requests are routed to the new hash table. In this way, the collision ring is logically divided into two. At most, half of the collision ring is scanned during the data search process.
  • Deletion: The old hash table is recycled, and the rehash node is deleted and recycled. An RCU transition period exists between the split phase and the deletion phase. The transition period ensures that results are returned to all access requests that pass through the old hash table. If the old hash table is directly recycled, concurrent operations may encounter an error.

4) Summary

References

Original Source:

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Alibaba Cloud

Alibaba Cloud

Follow me to keep abreast with the latest technology news, industry insights, and developer trends. Alibaba Cloud website:https://www.alibabacloud.com