知识卡片

SafeTimer用双重索引实现高效取消

专业/工作 · 511.d

内容

SafeTimer 同时维护两个数据结构:一个按到期时间升序排列的 multimap(schedule),后台线程只需检查队首任务是否到期,不用遍历整个任务集合;另一个是 Context 指针到 schedule 迭代器的反向映射(events),使得取消某个具体定时任务时可以 O(log n) 直接定位、无需线性扫描。这是”用空间换时间、用双重索引换双向高效访问”的典型模式:只按时间排序满足不了随时按任务取消的需求,只按任务索引又不能快速判断谁最先到期,两个索引各司其职。

参考来源

《Ceph源码分析》第2章《Ceph通用模块》