一、背景：传统缓存在多线程并发下的困境

使用者痛点：在高并发服务中，缓存往往成为性能瓶颈。业务侧频繁的读写请求导致锁竞争激烈。CPU 缓存命中率低，甚至出现热点数据被频繁淘汰的现象。

LRU 缓存的并发瓶颈

LRU是最经典的缓存淘汰策略，其主要思想是「最近最少使用的数据最先被淘汰」。典型实现使用哈希表 + 双向链表哈希表提供 O 查找，双向链表维护访问顺序。

只是这种结构在多线程环境下存在天然的并发瓶颈：

• 每次读操作都需要写链表即使是Lookup也必须将命中节点移动到链表头部。这代表着读操作是一个写操作，必须加锁保护。
• 锁竞争严重。分片也无法根治由于链表是全局共享的，所有线程的读写操作都竞争同一把 mutex；按理说，即使采用分片，每个分片内部仍然需要 mutex。当热点数据集中在少数分片时锁竞争依然是主要瓶颈。
• 缓存行颠簸链表节点在内存中分散分布，频繁的指针追踪导致 CPU 缓存命中率低下。
• 扫描抗性差大批量顺序扫描会快速冲刷链表，使热点数据被误删。

传统 LRU 的问题

问题	表现
读操作需要写	每次 Lookup 都要移动链表节点 锁粒度为每分片一把 mutex。热点分片竞争严重 内存布局散乱导致 CPU 缓存不友好 扫描抗性差——扫描流量直接冲刷链表

Clock 算法：为并发而生的淘汰策略

User Pain Point：L​RU 的全局锁与指针跳转让程序在高 QPS 场景下出现“卡顿”，而 Clock 通过环形数组天然避免这些问题。

The Clock algorithm originated from OS page replacement and is an efficient approximation of LRU. Its core advantages are:

• No linked list: Uses a fixed‑size circular array + a clock hand,enabling contiguous memory layout.
• Read operations are wait‑free: A single atomic fetch_add marks a hit;怎么说呢，no node movement or CAS loops.
• SLOT‑level write locking: Insert/evict lock granularity is per slot rar than per shard,allowing true parallel writes.
• Pipelined eviction: The clock hand advances via atomic fetch_add,each thread gets its own scan window,eliminating contention.
• Burst‑scan resistance: The “second chance” mechanism protects hot entries from being evicted by massive sequential scans.

The above traits make Clock an ideal foundation for a high‑performance lock‑free cache.

RocksDB HyperClockCache 与本项目的关系

S​wiftClockCache directly draws inspiration from RocksDB HyperClockCache。providing a simplified and independent implementation that only depends on C++ standard library and xxHash.

The original HyperClockCache is tightly coupled with RocksDB internals,making it difficult to extract as a standalone component. SwiftClockCache extracts core algorithmic ideas—open addressing hash table + per‑slot atomics + Clock eviction—and re‑implements m as a generic C++ library.

二、项目概览

S​wiftClockCache 是基于 Clock 淘汰算法的高性能、线程安全内存缓存库。它采用开放寻址哈希表 + 分片+ 原子操作a architecture that reduces contention to smallest possible granularity,achieving safe and efficient insert/lookup/delete/eviction under heavy concurrency.

主要特性

• Theoretically wait‑free reads: Lookup only performs an atomic increment of reference counter.
• SLOT‑level parallel writes: Multiple threads can insert/evict different slots without blocking each or.
• T​TL support: Each entry may carry an independent expiration timestamp.
• S​harding: Distributes load across N shards。furr lowering contention.
•  Lookup returns a Handle that automatically manages reference counting—no manual shared_ptr wrapping needed.

三、整体架构

The library is organized in three layers: top‑level API → Shard → FixedClockTable . Below is an ASCII diagram rendered in HTML for clarity.

┌─────────────────────────────────────────────────────────────────┐
│ SwiftClockCache │
│ │
│ ┌──────────────────┐ ┌──────────────────┐ ┌──────────────────┐ │
│ │ ClockCacheShard │ │ ClockCacheShard │ │ ClockCacheShard │ │
│ │ Shard │ │ Shard │ │ Shard N-…按理说，│ │
│ └────────┬─────────┘ └────────┬─────────┘ └────────┬─────────┘ │
│ │ │ │ │
│ ┌────────▼─────────┐ ┌────────▼─────────┐ ┌────────▼─────────┐ │
│ │ FixedClockTable │ │ FixedClockTable │ │ FixedClockTable │ │
│ └──────────────────┘ └──────────────────┘ └──────────────────┘ │
│ …，…|
│ Lookup 返回 → Handle → 自动 Release |
└─────────────────────────────────────────────────────────────────────┘

层级	文件	职责
Toplevel API swift_clock_cache.h	- 对外 API - 分片路由 & 哈希计算 - Handle RAII 封装
P​​er‑shard engine clock_cache_shard.h	- 单分片容量管理 - 驱逐触发主要引擎
Main engine fixed_clock_table.h	- 开放寻址哈希表 - Clock 淘汰 - 无锁并发控制
I​​nfrastructure base.h	- 时间函数 & 工具宏 - 错误码定义

四、主要数据结构详解

SlotMeta —— 位原子状态字

The concurrency control hinges on SlotMeta,which packs all slot state into a single 64‑bit word so that every state transition can be performed with one atomic operation.

// bit layout
| Visible | Shareable | Occupied | ReleaseCounter | AcquireCounter |
| 1b | 1b | 1b | ... | ... |

标志位	含义
OccupiedBit / td> td> Slot 已被占用 / td> / tr>
ShareableBit / td> td> 数据已建立完成。可被并发读取 / td> / tr>
VisibleBit / td> td> 数据对查找可见 / td> / tr>

The state machine transitions are illustrated below :

Empty
↓ fetch_or
UnderConstruction
↓ Store
Visible
↓ FetchClearVisible
Invisible
↓ CAS -> UnderConstruction -> Free

• Empty : Slot free .
• UnderConstruction : Writer holds slot,ors cannot read.
• Visible : Normal usable state.
• Invisible : Marked deleted,will be reclaimed when refcount drops to zero.

引用计数 & 倒计时融合

The reference count uses two counters – AcquireCounter and ReleaseCounter – each occupying its own bit field within same atomic word. The effective refcount is computed as:

/ pre>
Refcount = AcquireCounter - ReleaseCounter

This design solves classic ABA problem because increments and decrements affect disjoint bit ranges and can be done via independent #fetch_add acquire/release#` operations. Moreover,when a slot becomes unreferenced ,absolute value of AcquireCounter serves as “life timer” for Clock eviction algorithm – each lookup increments it,while eviction decrements both counters synchronously until y reach zero before reclaiming slot.

Slot结构

struct Slot {
AtomicSlotMeta meta;// 64-bit atomic state
std:的观点是，atomic* displacements;
// 探测方法计数
再看std:，atomic* expire_at;// TTL 时间戳
HashedKey hashed_key;// 128-bit 哈希值
unsigned char key_storage;unsigned char value_storage;}，

K&V 使用 placement new 在预分配字节数组上原地构造，从而避免额外堆分配。

Displacement计数器

• 插入时 : 每经过一个非目标槽位就 ++displacements。
• 删除时 : 回滚方法时 --displacements。
• 查找时 : 若遇空槽且 displacements ==0。 则说明没有元素经过此处，可提前终止搜索。 按理说，

This technique replaces tombstones with a cheap numeric guard that dramatically reduces scan length after deletions.

五、主要操作流程

哈希与分片路由

S​wiftClockCache uses xxHash XXH3_128bits with a random seed to produce a 128‑bit hash :

• / li> 用作哈希表基地址。
• / li> 用作探测步长。/ li>
• / li>。/ li>

Insert 流程   🡒 简化版关键步骤如下：

// Caller -> Shard -> FixedClockTable
if EvictIfNeeded;slot = FindSlot;if return false;// TryInsert:
if ) { // 成功占位
placement_new;placement_new;slot.meta.store;}
else if {
// 回滚 displacement 增长，并返回 nullptr；}

1. 原子占位 ： fetch_or。若之前为空则成功，
2. 构造数据 ： 在占位成功后安全写入 Key/Value/HashedKey/ExpireAt。
3. 发布 ： Store 同时把引用计数初始化为零，使其他线程可见。/li>
4. 重复检测 ： 若探测到已有相同 Key 的 Visible Slot，则回滚 displacement 并返回失败。/li>

Lookup 流程   🡒 关键步骤：

>addacquire 增加 AcquireCounter。/li > 如果匹配且未过期，则返回 Handle 并保持已递增的引用计数；否则执行 Unref 将计数回退；当遇到 displacement==0 的空槽位时提前终止搜索，以提高查找效率。/li>

---