Principle and implementation of handwriting cache framework redis expire from scratch

preface

We are From zero handwriting cache framework (1) to achieve a fixed size cache Our cache has been preliminarily implemented in.

In this section, let's learn how to implement the expire function similar to that in redis.

Expiration is a very useful feature. For example, I want to put my login information into redis and expire after 30 minutes; Or the accumulated information of a single day is put in redis and automatically cleared in the early morning of each day.

code implementation

Interface

Let's first define the interface.

There are mainly two: one is how long it expires and the other is when it expires.

public interface ICache<K, V> extends Map<K, V> {

    /**
     * Set expiration time
     * (1)If the key does not exist, do nothing.
     * (2)The method of specifying the expiration time of a new key is not provided temporarily, which will destroy the original method.
     *
     * What will you do:
     * Similar to redis
     * (1)Inert deletion.
     * When executing the following method, delete it if it expires.
     * {@link ICache#get(Object)} obtain
     * {@link ICache#values()} Get all values
     * {@link ICache#entrySet()} Get all details
     *
     * [Data inconsistency]
     * Calling other methods may not get the expected result of the user, because the expire information may not be updated in time.
     * such as
     * {@link ICache#isEmpty()} Is it empty
     * {@link ICache#size()} Current size
     * At the same time, it will lead to the problem of using size() as the expiration condition.
     *
     * Solution: consider adding refresh and other methods, and do not consider consistency for the time being.
     * For practical use, we are more concerned about K/V information.
     *
     * (2)Scheduled deletion
     * Start a scheduled task. Each time, randomly select a key of the specified size to judge whether it is expired.
     * Similar to redis, in order to simplify, you can consider setting the timeout time. The frequency is inversely proportional to the timeout time.
     *
     * Other expansionary considerations:
     * In the later stage, atomic operations are considered to ensure transaction. Don't think about it for the time being.
     * TTL is used as the benchmark for comparison by default. We don't want to support the elimination strategy of LastAccessTime for the time being. Will increase complexity.
     * If the lastAccessTime is added to expire, this method can not be modified.
     *
     * @param key         key
     * @param timeInMills Expires in milliseconds
     * @return this
     * @since 0.0.3
     */
    ICache<K, V> expire(final K key, final long timeInMills);

    /**
     * Expires at the specified time
     * @param key key
     * @param timeInMills time stamp
     * @return this
     * @since 0.0.3
     */
    ICache<K, V> expireAt(final K key, final long timeInMills);

}

code implementation

In order to facilitate processing, we calculate how long it will expire. Turn the two questions into the same question, the question of when to expire.

The core code mainly depends on the cacheExpire interface.

@Override
public ICache<K, V> expire(K key, long timeInMills) {
    long expireTime = System.currentTimeMillis() + timeInMills;
    return this.expireAt(key, expireTime);
}

@Override
public ICache<K, V> expireAt(K key, long timeInMills) {
    this.cacheExpire.expire(key, timeInMills);
    return this;
}

Cache expiration

Here, in order to facilitate the later expansion, the expired processing is defined as an interface, which is convenient for the later flexible replacement.

Interface

Among them, expire (final K key, final long expirat); Is where we call in our method.

Referrsexpire is an inert deletion. It should be considered only when refreshing is required. We will explain it later.

public interface ICacheExpire<K,V> {

    /**
     * Specify expiration information
     * @param key key
     * @param expireAt When does it expire
     * @since 0.0.3
     */
    void expire(final K key, final long expireAt);

    /**
     * Delete the keys to be processed in the lazy
     * @param keyList keys
     * @since 0.0.3
     */
    void refreshExpire(final Collection<K> keyList);

}

Principle of expire implementation

In fact, the actual idea of expiration is also relatively simple: we can start a scheduled task, such as one rotation training every second to clear the expired information.

Storage of expired information

/**
 * Expired map
 *
 * Space for time
 * @since 0.0.3
 */
private final Map<K, Long> expireMap = new HashMap<>();

@Override
public void expire(K key, long expireAt) {
    expireMap.put(key, expireAt);
}

We define a map, where key is the corresponding information to expire, and value stores the expiration time.

Polling cleanup

We fixed a cleaning time of 100ms, with a maximum of 100 at a time.

/**
 * Quantity limit of single emptying
 * @since 0.0.3
 */
private static final int LIMIT = 100;

/**
 * Cache implementation
 * @since 0.0.3
 */
private final ICache<K,V> cache;
/**
 * Thread execution class
 * @since 0.0.3
 */
private static final ScheduledExecutorService EXECUTOR_SERVICE = Executors.newSingleThreadScheduledExecutor();
public CacheExpire(ICache<K, V> cache) {
    this.cache = cache;
    this.init();
}
/**
 * Initialize task
 * @since 0.0.3
 */
private void init() {
    EXECUTOR_SERVICE.scheduleAtFixedRate(new ExpireThread(), 100, 100, TimeUnit.MILLISECONDS);
}

A single thread is defined here to perform the emptying task.

Empty task

This is very simple. Traverse the expired data and judge the corresponding time. If it has expired, execute the emptying operation.

In order to avoid a single execution time is too long, only 100 items can be processed at most.

/**
 * Perform tasks regularly
 * @since 0.0.3
 */
private class ExpireThread implements Runnable {
    @Override
    public void run() {
        //1. Judge whether it is empty
        if(MapUtil.isEmpty(expireMap)) {
            return;
        }
        //2. Get the key for processing
        int count = 0;
        for(Map.Entry<K, Long> entry : expireMap.entrySet()) {
            if(count >= LIMIT) {
                return;
            }
            expireKey(entry);
            count++;
        }
    }
}

/**
 * Perform expiration operation
 * @param entry detailed
 * @since 0.0.3
 */
private void expireKey(Map.Entry<K, Long> entry) {
    final K key = entry.getKey();
    final Long expireAt = entry.getValue();
    // Logical processing of deletion
    long currentTime = System.currentTimeMillis();
    if(currentTime >= expireAt) {
        expireMap.remove(key);
        // Then remove the cache, which can be compensated by lazy deletion
        cache.remove(key);
    }
}

Optimization idea of emptying

If there are few expired application scenarios, the significance of frequent rotation training is not practical.

For example, 99% of our tasks are to empty data in the early morning. No matter how we poll during the day, it is a pure waste of resources.

Is there any way to quickly judge whether there are expired elements to be processed?

The answer is yes, that is the sorted MAP.

Let's change our thinking, let the expired time be the key, and put the information that needs to expire at the same time in a list as value.

Then sort the expiration time. When polling, you can quickly judge whether there is expired information.

public class CacheExpireSort<K,V> implements ICacheExpire<K,V> {

    /**
     * Quantity limit of single emptying
     * @since 0.0.3
     */
    private static final int LIMIT = 100;

    /**
     * Sort cache storage
     *
     * Use cache processing sorted by time.
     * @since 0.0.3
     */
    private final Map<Long, List<K>> sortMap = new TreeMap<>(new Comparator<Long>() {
        @Override
        public int compare(Long o1, Long o2) {
            return (int) (o1-o2);
        }
    });

    /**
     * Expired map
     *
     * Space for time
     * @since 0.0.3
     */
    private final Map<K, Long> expireMap = new HashMap<>();

    /**
     * Cache implementation
     * @since 0.0.3
     */
    private final ICache<K,V> cache;

    /**
     * Thread execution class
     * @since 0.0.3
     */
    private static final ScheduledExecutorService EXECUTOR_SERVICE = Executors.newSingleThreadScheduledExecutor();

    public CacheExpireSort(ICache<K, V> cache) {
        this.cache = cache;
        this.init();
    }

    /**
     * Initialize task
     * @since 0.0.3
     */
    private void init() {
        EXECUTOR_SERVICE.scheduleAtFixedRate(new ExpireThread(), 1, 1, TimeUnit.SECONDS);
    }

    /**
     * Perform tasks regularly
     * @since 0.0.3
     */
    private class ExpireThread implements Runnable {
        @Override
        public void run() {
            //1. Judge whether it is empty
            if(MapUtil.isEmpty(sortMap)) {
                return;
            }

            //2. Get the key for processing
            int count = 0;
            for(Map.Entry<Long, List<K>> entry : sortMap.entrySet()) {
                final Long expireAt = entry.getKey();
                List<K> expireKeys = entry.getValue();

                // Judge whether the queue is empty
                if(CollectionUtil.isEmpty(expireKeys)) {
                    sortMap.remove(expireAt);
                    continue;
                }
                if(count >= LIMIT) {
                    return;
                }

                // Logical processing of deletion
                long currentTime = System.currentTimeMillis();
                if(currentTime >= expireAt) {
                    Iterator<K> iterator = expireKeys.iterator();
                    while (iterator.hasNext()) {
                        K key = iterator.next();
                        // Remove itself first
                        iterator.remove();
                        expireMap.remove(key);

                        // Then remove the cache, which can be compensated by lazy deletion
                        cache.remove(key);

                        count++;
                    }
                } else {
                    // Skip directly without expired information
                    return;
                }
            }
        }
    }

    @Override
    public void expire(K key, long expireAt) {
        List<K> keys = sortMap.get(expireAt);
        if(keys == null) {
            keys = new ArrayList<>();
        }
        keys.add(key);

        // Set corresponding information
        sortMap.put(expireAt, keys);
        expireMap.put(key, expireAt);
    }
}

It seems feasible, which can reduce the pressure of polling.

In fact, space is used to exchange time. I think it can be improved later. The performance of this method should be good.

However, I did not adopt this scheme, mainly considering the problem of inert deletion, which will be more troublesome. I will continue to improve this scheme in the future.

Inert deletion

Causes of occurrence

Similar to redis, when we use the scheme of scheduled deletion, there is a problem: the data may not be cleaned up in time.

When we query, we may get dirty data.

So some people think that when we care about some data, we can make the corresponding deletion judgment operation on the data, so the pressure will be much less.

It's a compromise.

Methods that need to be deleted

Generally, it refers to various query methods, such as when we obtain the value corresponding to the key

@Override
@SuppressWarnings("unchecked")
public V get(Object key) {
    //1. Refresh all expired information
    K genericKey = (K) key;
    this.cacheExpire.refreshExpire(Collections.singletonList(genericKey));
    return map.get(key);
}

We refresh the data before obtaining it.

Implementation of refresh

The implementation principle is also very simple, that is, a cycle, and then delete it.

A small optimization is added here: select a small number of as the outer loop.

The time complexity of the loop set is O (n), map The time complexity of get() is O(1);

@Override
public void refreshExpire(Collection<K> keyList) {
    if(CollectionUtil.isEmpty(keyList)) {
        return;
    }
    // Judge the size, and use the small one as the external circulation. Generally, the expired keys are relatively small.
    if(keyList.size() <= expireMap.size()) {
        for(K key : keyList) {
            expireKey(key);
        }
    } else {
        for(Map.Entry<K, Long> entry : expireMap.entrySet()) {
            this.expireKey(entry);
        }
    }
}

test

After the above code is written, we can verify it.

ICache<String, String> cache = CacheBs.<String,String>newInstance()
        .size(3)
        .build();
cache.put("1", "1");
cache.put("2", "2");

cache.expire("1", 10);
Assert.assertEquals(2, cache.size());

TimeUnit.MILLISECONDS.sleep(50);
Assert.assertEquals(1, cache.size());

System.out.println(cache.keySet());

The results also meet our expectations.

Summary

Here, an expire function similar to redis is basically implemented.

Of course, there are many optimization places.

For example, for the convenience of adding various listeners in the future, I adjusted all the places that need to be refreshed to use bytecode + annotation instead of adding refresh methods to each required method.

In the next section, we will learn how to implement various listeners.

If it's helpful to you, you're welcome to like comments and collect attention~

Your encouragement is my greatest motivation~

Original address

Cache Travel-09 - implementation principle of redis expire expiration of handwriting cache from zero

Posted by simenss on Sat, 14 May 2022 14:51:02 +0300