最近参与了一个不错的开源项目，是一个基于 BitCask 模型实现的 KV 存储引擎。项目地址：CouloyDB。大家觉得不错的话可以来一个小小的 star。
因为功能上想向 Redis 看齐，所以打算实现过期自动删除的功能。我采取了小顶堆来实现过期删除，并且在 Get 的时候，也会进行惰性删除。
时间堆的实现
堆中的每个元素都是一个 Job：
type Job struct {
Key string
Expiration time.Time
}其中记录了每个Key和它的过期时间Expiration。
堆的实现定义如下：
type h struct {
heap []*Job
index map[string]int
}index存储的是Key对应的Job在数组中的切片，用以快速获取Job而无需遍历切片。
在 Go 中可以通过实现heap.go中的接口来实现堆：
type Interface interface {
sort.Interface
Push(x any) // add x as element Len()
Pop() any // remove and return element Len() - 1.
}具体实现可以查看CouloyDB/public/ds/timeHeap.go at master · Kirov7/CouloyDB · GitHub，这里就不给出详细代码了，重点注意实现的时候需要在接口方法里同样对 index 进行更新。
实现了堆的接口之后，h结构体就可以使用堆的一些方法来操作了。额外对 h 封装了一层：
type TimeHeap struct {
heap h
}TimeHeap实现了如下方法：
- Push.
- Pop.
- Get.
- Remove.
- Peek.
- IsEmpty.
具体实现同样可以查看CouloyDB/public/ds/timeHeap.go at master · Kirov7/CouloyDB · GitHub。
利用时间堆实现 TTL 机制
具体实现可以查看CouloyDB/ttl.go at master · Kirov7/CouloyDB · GitHub，这里就重点说一下exec方法：
func (ttl *ttl) exec() {
now := time.Now()
duration := MaxDuration
ttl.mu.Lock()
job := ttl.timeHeap.Peek()
ttl.mu.Unlock()
if job != nil {
if job.Expiration.After(now) {
duration = job.Expiration.Sub(now)
} else {
duration = 0
}
}
if duration > 0 {
timer := time.NewTimer(duration)
defer timer.Stop()
select {
case start方法的执行流程如下：
- 从堆顶取出一个 Job；
- 判断这个 Key 是否已经过期了，并计算剩余的存活时间；
- 如果这个 Key 没有过期，那么启动一个 Timer 来等待这个 Key 过期，Timer 触发之后，会将这个 Job 从堆中 Pop 出来；如果已经过期了那么直接 Pop 出来。
- 开启一个协程来异步删除 Key。
这个流程中有一个很值得注意的地方是：
select {
case 一旦有堆中元素被插入或删除都需要直接返回，跳到下一次exec的调用。这是因为有可能新插入的元素会在当前堆顶元素之前过期，应该要先删除。或是当前堆顶元素已经被删除了，再次 Pop 的话就会出现错误了。
调用接口
在Get方法中，如果 Key 存在就要去时间堆中检查一下是否过期了，如果过期了就直接返回错误。
if db.ttl.isExpired(string(key)) {
// if the key is expired, just return and don't delete the key now
return nil, public.ErrKeyNotFound
}然后我将原先的Put方法又重新封装了一下：
func (db *DB) PutWithExpiration(key, value []byte, duration time.Duration) error {
return db.put(key, value, duration)
}
func (db *DB) Put(key, value []byte) error {
return db.put(key, value, 0)
}在put方法中可以根据duration是不是 0 来进行相应的操作。
如果duration不为 0，那么就计算出过期时间，并向时间堆中添加/更新一个Job，但duration如果为 0，有可能是要将之间设置了过期时间的 Key 给取消过期时间，所以要进行一次删除。
var expiration int64
if duration != 0 {
expiration = time.Now().Add(duration).UnixNano()
db.ttl.add(ds.NewJob(string(key), time.Unix(0, expiration)))
} else {
// If it is a key without an expiration time set
// you may need to remove the previously set expiration time
db.ttl.del(string(key))
}接着在Del方法中，只需要简单的从时间堆删除对应的Job即可。
db.ttl.del(string(key))测试
测试了正常的过期删除、数据库重启之后的过期删除（重构时间堆）、取消过期时间、对同一个 Key 再次 Put 来取消过期时间均无问题。具体实现可以查看CouloyDB/ttl_test.go at master · Kirov7/CouloyDB · GitHub。
参与项目
目前项目还处于刚起步的状态，有很多功能还没有实现也有性能优化方面的事情要做，想要参与项目的朋友可以直接提 issue 或 pr，有什么问题也可以直接联系我，掘金私信或联系邮箱 bigboss2063@outlook.com。
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
相关推荐: 2023年09月 C/C++（六级）真题解析#中国电子学会#全国青少年软件编程等级考试
C/C++编程（1~8级）全部真题・点这里 Python编程（1~6级）全部真题・点这里 第1题：生日相同 在一个有180人的大班级中，存在两个人生日相同的概率非常大，现给出每个学生的名字，出生月日。试找出所有生日相同的学生。 时间限制：1000 内存限制：6…
