preface

Set key value px 100; set key value px 100; set key value px 100; But we did not implement Redis expiration policy, this article is mainly to implement Redis expiration policy.

Principle of Redis expiration policy

Let’s take a look at the definition in the official document:

Redis keys are expired in two ways: a passive way, and an active way.

A key is passively expired simply when some client tries to access it, and the key is found to be timed out.

Of course this is not enough as there are expired keys that will never be accessed again. These keys should be expired anyway, so periodically Redis tests a few keys at random among keys with an expire set. All the keys that are already expired are deleted from the keyspace.

Specifically this is what Redis does 10 times per second:

  1. Test 20 random keys from the set of keys with an associated expire.
  2. Delete all the keys found expired.
  3. If more than 25% of keys were expired, start again from step 1.

This is a trivial probabilistic algorithm, basically the assumption is that our sample is representative of the whole key space, and we continue to expire until the percentage of keys that are likely to be expired is under 25%

This means that at any given moment the maximum amount of keys already expired that are using memory is at max equal to max amount of write operations per second divided by 4.

To recap: Redis keys can be invalidated in two ways: passive and active. Passive invalidation is a key that is accessed to see if it is expired, and if it is, it is processed. The active approach is a background timed task (also in the main thread, triggered by timer events in the event model) that periodically cleans up expired keys (10 times per second). The main logic is as follows:

  1. Find 20 random keys with expiration dates
  2. Delete expired keys
  3. If more than 25% of the keys are out of date, the loop starts again with step1.

This is simply a probabilistic algorithm, which means that the maximum number of expired keys in Redis at any given moment is only 1/4 of the number of writes per second.

Redis’ key expiration policy looks simple, so let’s start implementing it

Redis expiration policy implementation

Take the initiative to expire

Active expiration is the expiration of a key when it is accessed. This is easy to implement:

  1. Check if a key is in the expired dictionary. If not, return the key
  2. In the expired dictionary, whether it is expired, no expiration, returns directly
  3. If the key has expired, delete it

Add key expiration check before we find key:

db.go

func (r *redisDb) lookupKey(key *robj) *robj {
	// Check whether the key has expired. If so, delete it
	r.expireIfNeeded(key)

	return r.doLookupKey(key)
}

func (r *redisDb) expireIfNeeded(key *robj) int {
	when := r.getExpire(key)

	if when < 0 {
		return 0
	}
	now := mstime()

	if now <= when {
		return 0
	}

	return r.dbDelete(key)
}
Copy the code

Passive overdue

Passive expiration Redis is triggered by timer events in its AE event model, and the GNET we use has a Tick event that does exactly the same thing (Golang is implemented using coroutines, but it doesn’t prevent us from understanding how Redis is implemented).

Let’s focus on the frequency of execution: it says that Redis executes expired timed tasks at a rate of 10 times per second. How did this frequency come from? In the redisServer structure, there is a field hz, which is used to control the execution frequency of background tasks. The execution interval of each task is 1000/ Hz ms, and the default value of Hz is 10, that is, 10 times per second, 100ms per time.

redis.c

In addition to the execution frequency, Redis also sets a limit on the processing duration for each DB when the expired key is processed. If the processing duration exceeds the maximum, Redis exits. This prevents the execution of normal commands from being affected due to the long execution time of expired tasks.

redis.c

The ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC value is 25, which indicates that the maximum time of each execution is 25% of the CPU time. For example, if the time of a scheduled task is 100ms, the maximum time of each DB execution is 25ms

It can be seen here that in fact, server. Hz and Timelimit are inversely proportional. If the Hz setting is larger, timelimit will be smaller, that is, the higher the execution frequency, and the shorter the running time will be.

Our specific implementation is as follows: first register the timing event, and set the time interval

redis.go

// Initialize the server
func initServer(a){...// Initialize the event handler
	server.events.react = dataHandler
	server.events.accept = acceptHandler
        // Register timer events
	server.events.tick = func(a)(delay time.Duration, action gnet.Action) {
		return serverCron(), action
	}
        ...
}

func serverCron(a) time.Duration {
	databasesCron()
	return time.Millisecond * time.Duration(1000 / server.hz)
}



Copy the code

Specific key expiration logic:

redis.go

func activeExpireCycle(a){
	// Now we have only one DB, so we don't need to loop through DB
	// for DB in server. DBS {}

	// Record the start time
	start := ustime()

	// Maximum execution time per DB
	timelimit := int64(1000000 * activeExpireCycleSlowTimeperc / server.hz / 100)

	if timelimit <= 0 {
		timelimit = 1
	}
	db := server.db
	for {
		nums := 0
		expired := 0
		now := mstime()
		// The size of the expired dictionary
		nums = db.expires.used()
		if nums == 0 {
			break
		}
                
                //TODO If the size of an expired dictionary is less than 1% of its capacity, it is not processed.
                
		// A maximum of 20
		if nums > activeExpireCycleLookupsPerLoop {
			nums = activeExpireCycleLookupsPerLoop
		}

		for; nums >0; nums = nums - 1 {
			
			// Get a random key
			de := db.expires.getRandomKey()
			if de == nil {
				break
			}
			
			// Expire the key
			if activeExpireCycleTryExpire(db, de, now) {
				expired++
			}
		}
		log.Printf("expired %v keys", expired)

		// Execution duration
		elapsed := ustime() - start

		if elapsed > timelimit {
			log.Printf("expired cost too long. elapsed: %v, timelimit: %v", elapsed, timelimit)
			break
		}
		if expired < activeExpireCycleLookupsPerLoop / 4 {
			log.Printf("expired count %v less than %v. ending loop", expired, activeExpireCycleLookupsPerLoop / 4)
			break}}}Copy the code

The logic is simple:

  1. Loop through all DB (ours only implements one DB, so we don’t need this layer of loop)
  2. I’m going to pick it randomly from DB each timeMin (20, expired dictionary capacity)And delete the expired key
  3. As long as the execution time does not exceed the maximum execution time and more than 25% of the sampled data is expired (Min (20, expired dictionary capacity)/4), then keep doing the loop, otherwise exit the DB loop

At this point our Redis expired implementation is complete, in fact, the logic is quite simple.

Implementation of related commands

With the expiration policy implemented, we can implement the relevant commands

EXPIRE command implementation

The expire command is as simple as adding the corresponding key and expiration time to the expire dictionary:

redis.go

func expireGenericCommand(client *redisClient, basetime int64, unit int) {
	key := client.argv[1]
	param := client.argv[2]
	w, _ := strconv.Atoi(string(param.ptr.(sds)))
	when := int64(w)
	if unit == unitSeconds {
		when *= 1000
	}
	when += basetime

	if client.db.lookupKey(key) == nil {
		addReply(client, shared.czero)
	}

	client.db.setExpire(key, when)
	addReply(client, shared.cone)
}
Copy the code

TTL command implementation

TTL = TTL; TTL = TTL;

  1. If the key is not present in the dictionary, return -2
  2. See if this key is in the expired dictionary, and return -1 if it doesn’t mean it won’t expire
  3. Return value in the expired dictionary

redis.go

func ttlGenericCommand(client *redisClient, outputMs bool) {

	var ttl int64 = - 1

	if client.db.lookupKey(client.argv[1= =])nil {
		addReplyLongLong(client, 2 -)
		return
	}

	expire := client.db.getExpire(client.argv[1])

	ifexpire ! =- 1 {
		ttl = expire - mstime()
		if ttl < 0 {
			ttl = 0}}if ttl == - 1 {
		addReplyLongLong(client, - 1)}else {
		if! outputMs { ttl = (ttl +500) / 1000
		}
		addReplyLongLong(client, ttl)
	}
}
Copy the code

conclusion

The Redis key expiration logic has been basically implemented. Finally, we summarize:

  • Redis’s expiration policy is active expiration + passive expiration
  • Passive expiration is queryingkeyIf it expires, delete it
  • Active expiration is through the background scheduled task of Redis (also executed in the main thread), which is generally executed every 100ms by default, traverses all DB, and randomly selects 20 expiration dictionaries each time for expiration detection, and deletes them if they are expired.

Redis uses these two expiration strategies to achieve a balance between memory utilization and performance. How does Redis choose which keys to eliminate when its memory usage reaches its upper limit? Next, we are ready to implement Redis’ cache elimination strategy.

Full code: github.com/cadeeper/my…