expiremap

Overview ¶

Package expiremap provides a thread-safe map with expiring keys. You must pay attention for these facts:

1. Current implementation may hold up to 1 billion keys
2. After creating a new map (calling New()), goroutine is created for deletion expired keys. It exists until Close() method is called
4. There are active and passive expirations. Active expiration is done during Get(), and SetTTL() calls. Passive expiration happens in background and is done by goroutine
4. Passive expiration occurs every 100ms. It is done in two steps - first step is inspired by algorithm used in Redis and second step is sequential expiration
5. It is guaranteed by sequential expiration, that no expired key will live more than map.Size() / 200 seconds

First step's (or random expire) algorithm is following:

1. Check the size of the map. If it is less than 100, just iterate over all keys and stop algorithm
2. Check 20 random keys. Remove all expired keys. If there were at least 5 deletions, do the step 2 again (step 2 is done maximum 10 times)

Second step's (or rotate expire) algorithm is following:

1. Load to X a key on which we stopped on the previous call. If on previous call we hit the bottom of the map, load top key of the map
2. Start from the key X and from that key expire 20 consecutive keys or stop if we hit a bottom of the map

It means that at maximum 2200 expires per second may occur (not counting active expiration). If you have a lot of insertions with unique keys, but you rarely call methods Get and SetTTL on these keys, your map will grow faster than expiration rate and you may hit 1 billion keys limit.

package main

import (
	"fmt"
	"time"

	expiremap "github.com/nursik/go-expire-map"
)

func main() {
	expireMap := expiremap.New()
	// You must call Close(), when you do not need the map anymore
	defer expireMap.Close()

	// GMT Wednesday, 1 January 2025, 0:00:00
	far := time.Unix(1735689600, 0)

	ttl := time.Until(far)

	// Insert
	expireMap.Set(1, 1, ttl)

	// Get value
	v, ok := expireMap.Get(1)
	fmt.Println(v, ok)
	// Output 1 true

	// Get TTL
	v = expireMap.GetTTL(1)
	// The output is equal to ~ ttl
	fmt.Println(v)

	// Update TTL
	v, ok = expireMap.SetTTL(1, time.Second)
	fmt.Println(v, ok)
	// Output 1 true

	time.Sleep(time.Second + time.Millisecond)

	// Because key is already expired, it returns nil, false
	v, ok = expireMap.SetTTL(1, ttl)
	fmt.Println(v, ok)
	// Output nil false

	// Because key is already expired, it returns nil, false
	v, ok = expireMap.Get(1)
	fmt.Println(v, ok)
	// Output nil false
}

Output: