Implementing Redis‑Style Key Expiration in Go with Lazy Deletion and Time Wheel

EasyRedis source code: https://github.com/gofish2020/easyredis

Expiration Strategies

Lazy deletion : a key is removed only when it is accessed and found to be expired.

Timed deletion : a background task removes the key as soon as its TTL expires.

Lazy Deletion Implementation

Read operations invoke an active expiration check. The retrieval path is engine/database.go. When GetEntity(key) is called, the key is looked up in the in‑memory dictionary and then db.IsExpire(key) determines whether the key has timed out.

func (db *DB) GetEntity(key string) (*payload.DataEntity, bool) {
    val, exist := db.dataDict.Get(key)
    if !exist {
        return nil, false
    }
    // active expiration check
    if db.IsExpire(key) {
        return nil, false
    }
    dataEntity, ok := val.(*payload.DataEntity)
    if !ok {
        return nil, false
    }
    return dataEntity, true
}

The expiration check reads the deadline from ttlDict. If no entry exists, the key has no TTL. If a deadline exists and the current time is past it, the key is removed and the function reports expiration.

func (db *DB) IsExpire(key string) bool {
    val, result := db.ttlDict.Get(key)
    if !result {
        return false
    }
    expireTime, _ := val.(time.Time)
    isExpire := time.Now().After(expireTime)
    if isExpire { // proactive removal
        db.Remove(key)
    }
    return isExpire
}

Timed Deletion with a Time Wheel

A fixed‑interval timer (e.g., checking every 3 seconds) is inefficient for keys that expire at finer granularity. The time‑wheel algorithm simulates a clock face: a circular slot array where each slot holds a linked list of tasks scheduled for that slot. The wheel advances at a constant interval; tasks that require multiple rotations carry a circle counter.

When a task with a 3‑second delay is added, it is placed at pos + 3. A 5‑second task goes to pos + 5. If the wheel’s pointer reaches a slot, all tasks in that slot’s list are executed. Tasks spanning more than one full rotation have a non‑zero circle value indicating how many additional cycles must pass.

The implementation resides in tool/timewheel. The wheel struct contains interval, ticker, current slot position, slot count, a slice of linked‑list slots, a map for quick key lookup, and channels for adding, canceling, and stopping tasks.

type TimeWheel struct {
    interval    time.Duration
    ticker      *time.Ticker
    curSlotPos  int
    slotNum     int
    slots       []*list.List
    m           map[string]*taskPos
    addChannel  chan *task
    cacelChannel chan string
    stopChannel chan struct{}
}

Adding a task computes the target slot and the number of full rotations using posAndCircle. The task is appended to the appropriate slot’s list, and the key‑to‑position map is updated to allow cancellation of duplicate keys.

func (tw *TimeWheel) posAndCircle(d time.Duration) (pos, circle int) {
    delaySecond := int(d.Seconds())
    intervalSecond := int(tw.interval.Seconds())
    pos = (tw.curSlotPos + delaySecond/intervalSecond) % tw.slotNum
    circle = (delaySecond / intervalSecond) / tw.slotNum
    return
}

func (tw *TimeWheel) addTask(t *task) {
    pos, circle := tw.posAndCircle(t.delay)
    t.circle = circle
    ele := tw.slots[pos].PushBack(t)
    if t.key != "" {
        if _, ok := tw.m[t.key]; ok {
            tw.cancelTask(t.key)
        }
        tw.m[t.key] = &taskPos{pos: pos, ele: ele}
    }
}

Handling Re‑Setting of Keys

If a key is set with an expiration (e.g., SET key value EX 3) and later overwritten without a TTL ( SET key value), the expiration entry is removed so the key no longer expires. The logic resides in engine/string.go within the cmdSet handler, where the tail of the function deletes the key from ttlDict when the command lacks an expiration argument.

Combined, EasyRedis demonstrates Redis‑style TTL management by performing lazy checks on reads and using a time‑wheel scheduler for proactive expiration.