第三章 内存缓存队列实现：环形缓冲区、链表队列、数据淘汰策略

埋点数据的实时写入与异步上报之间，依靠内存缓存队列完成缓冲与削峰。队列的结构直接决定写入吞吐量、内存抖动频率和淘汰时机。本章深入三种核心技术：环形缓冲区（定长无锁结构）、链表队列（动态伸缩）、数据淘汰策略（保证内存上限），并给出完整的实现、调试与优化方案。

3.1 原理与核心差异

数据淘汰策略解决“超过容量后，丢弃哪些埋点”的问题。常用三种：

• FIFO（先进先出）：丢弃最早入队的埋点，实现简单，但可能丢掉关键事件。
• LRU（最近最少使用）：根据访问时间淘汰，需维护访问顺序，适合缓存场景，埋点中应用较少。
• LFU（最不经常使用）：统计入队频次，丢弃低频埋点，适合有重要性等级的事件。

3.2 实现流程与核心代码

3.2.1 环形缓冲区（环形数组 + FIFO）

// ring_buffer.h
typedef struct {
    void **buffer;      // 数据指针数组
    size_t capacity;    // 总槽位数
    size_t write_idx;   // 写位置（原子变量，单生产者可省略）
    size_t read_idx;    // 读位置
    int (*evict_policy)(void *data, size_t age);
} RingBuffer;

// 初始化：分配 capacity 个空指针
RingBuffer* rb_create(size_t cap) {
    RingBuffer *rb = malloc(sizeof(RingBuffer));
    rb->buffer = calloc(cap, sizeof(void*));
    rb->capacity = cap;
    rb->write_idx = 0;
    rb->read_idx = 0;
    rb->evict_policy = fifo_evict; // 默认 FIFO
    return rb;
}

// 入队：若不满则直接写入，否则淘汰最老数据（read_idx位置）
int rb_push(RingBuffer *rb, void *data) {
    size_t next_write = (rb->write_idx + 1) % rb->capacity;
    if (next_write == rb->read_idx) {  // 缓冲区满，触发淘汰
        if (rb->evict_policy(rb->buffer[rb->read_idx], 0)) {
            // 淘汰 read_idx 处数据，读指针推进
            free(rb->buffer[rb->read_idx]);
            rb->read_idx = (rb->read_idx + 1) % rb->capacity;
        } else {
            return -1; // 淘汰被拒绝，入队失败
        }
    }
    rb->buffer[rb->write_idx] = data;
    rb->write_idx = next_write;
    return 0;
}

// 出队：非空时取出 read_idx 处数据
void* rb_pop(RingBuffer *rb) {
    if (rb->write_idx == rb->read_idx) return NULL; // 空
    void *data = rb->buffer[rb->read_idx];
    rb->buffer[rb->read_idx] = NULL;
    rb->read_idx = (rb->read_idx + 1) % rb->capacity;
    return data;
}

3.2.2 链表队列（动态节点 + 阈值淘汰）

// linked_queue.h
typedef struct Node {
    void *data;
    struct Node *next;
} Node;

typedef struct {
    Node *head;
    Node *tail;
    size_t count;
    size_t max_count;   // 上限阈值
    void (*evict_batch)(struct LinkedQueue *q, size_t required);
} LinkedQueue;

LinkedQueue* lq_create(size_t max) {
    LinkedQueue *q = calloc(1, sizeof(LinkedQueue));
    q->max_count = max;
    q->evict_batch = fifo_batch_evict; // 批量淘汰最早 N 个
    return q;
}

int lq_push(LinkedQueue *q, void *data) {
    if (q->count >= q->max_count) {
        q->evict_batch(q, q->count - q->max_count + 1);
    }
    Node *n = malloc(sizeof(Node));
    n->data = data;
    n->next = NULL;
    if (q->tail) q->tail->next = n;
    else q->head = n;
    q->tail = n;
    q->count++;
    return 0;
}

3.3 数据淘汰策略实现

实际工程中可通过回调函数灵活切换策略：

// 回调类型定义
typedef int (*evict_predicate)(void *candidate, void *context);

// 使用示例：FIFO 总是返回 1（允许淘汰最老）
int fifo_evict(void *candidate, void *context) {
    (void)candidate; (void)context;
    return 1;  // 直接淘汰
}

// LRU 场景：检查 candidate 是否比 context 中的 timestamp 更老
int lru_evict(void *candidate, void *context) {
    uint64_t *cand_ts = (uint64_t*)candidate; // 假设数据首字段为时间戳
    uint64_t *ref_ts = (uint64_t*)context;
    return *cand_ts < *ref_ts;
}

3.4 调试与日志观察

// 环形缓冲区调试日志（建议条件编译）
#ifdef QUEUE_DEBUG
printf("[RB] write=%zu read=%zu capacity=%zu\n",
       rb->write_idx, rb->read_idx, rb->capacity);
for (size_t i = 0; i < rb->capacity; i++) {
    printf("  slot[%zu] = %p\n", i, rb->buffer[i]);
}
#endif

// 检查环形缓冲区一致性
int rb_self_check(RingBuffer *rb) {
    size_t used = (rb->write_idx - rb->read_idx + rb->capacity) % rb->capacity;
    if (used > rb->capacity) return -1;
    return 0;
}

3.5 常见错误与避坑

• 环形缓冲区读/写指针溢出：取模时未用 % capacity 或 capacity 不是 2 的幂导致用 & 操作符时出错。
• 链表节点内存泄漏：淘汰时只释放了节点指针，未释放节点内的数据指针（需业务层配合 free）。
• 多线程竞争：环形缓冲区在单生产单消费下安全，但链表队列需要加锁或使用无锁 CAS。推荐使用 __sync_fetch_and_add 或 C11 atomic。
• 淘汰策略误判：FIFO 可能丢弃重要事件，LRU 在埋点中无访问概念实现复杂，推荐按业务级别分层队列。

3.6 性能与稳定性优化

1. 批量写入：将多个埋点合并为一个缓冲区块，减少队列操作次数。
2. 内存对齐：节点和槽位按缓存行（64字节）对齐，避免伪共享。
3. 静默淘汰统计：记录淘汰次数和类型，用于监控和动态调整容量。
4. 预热&降级：初始化时预分配环形缓冲区，应用启动阶段可直接使用；当内存不足时降级为丢弃低优先级事件。
5. 零拷贝出队：出队时直接返回指针而非拷贝数据，减少 memcpy 开销（注意生命周期管理）。

// 内存对齐示例（GCC/clang）
typedef struct alignas(64) AlignedNode {
    void *data;
    struct AlignedNode *next;
} AlignedNode;

// 使用 posix_memalign 分配
AlignedNode *node;
posix_memalign((void**)&node, 64, sizeof(AlignedNode));

3.7 部署配置项

在配置中心下发后，热加载检查配置变更，重建队列需确保现有数据安全迁移（例如先开启双写，再切换）。