preface

In the previous article, I introduced common cache frameworks and learned that Caffeine currently has the best performance in memory caching

This article will explain the internal implementation of Caffeine in detail at the source level, including the following

Elimination strategy tinyLFU
Internal interface relationship of Caffeine
Atomicity of the load put Invalidate operation
Cache expiration policy resolution

Cache elimination algorithm

The function of cache elimination algorithm is to identify which data will be reused in a short time within limited resources, so as to improve the hit ratio of cache

LRU (Least Recently Used)

This algorithm assumes that recently accessed data has a higher chance of being accessed in the future and is usually implemented using linked lists

If data is added or accessed, the data is moved to the head of the linked list. If the head of the linked list is hot, the tail of the linked list is cold. When the data is full, the tail of the data is eliminated

Its implementation is relatively simple, but it also brings some problems. If there is data traversal, LRU hit ratio will drop sharply and cache pollution is serious

The LRU algorithm is not without merit, and it performs well under burst traffic

LFU (Least FrequentlyUsed)

The algorithm weeds out data based on its historical access frequency. The core idea is that if data has been accessed multiple times in the past, it will be accessed more often in the future

According to LFU, if you want to implement this algorithm, you need to maintain an additional set of logic to count the number of times each element is accessed, which will cause a waste of memory resources

FIFO (First In First Out)

First in, first out (FIFO) thinking, judging how long data has been stored, the farthest data from the present is first eliminated. It’s relatively simple to implement

TinyLFU

Caffeine adopts an algorithm combining the advantages of LRU and LFU: W-TinylFU features: high hit ratio and low memory consumption

Before understanding w-TinylFu algorithm, first understand TinyLFU algorithm

TinyLFU aims to solve the problem of large space storage of traditional LFU algorithm, which is also based on LFU algorithm

It can replace the data statistics part of THE LFU in the scenario of heavy traffic. The principle is similar to BloomFilter.

Now that we’re talking about bloom filters, here’s how it works

A BloomFilter is a token that uses a large array of bits to store all keys, each of which is mapped to the corresponding bits of the array through multiple hashes

If the key exists, the corresponding bit is set to 1, so that a large amount of data can be filtered through a small amount of storage space

The Bloom filter can’t tell exactly if a key exists, but if it doesn’t, it must not exist

For those of you who are familiar with the hashmap principle, it is possible to hash two different keys into the same hash slot

In the cache application, it is used to solve the problem of cache penetration

TinyLFU regards multiple bits as a whole and calculates the usage frequency of a key

The key is used to map different bits through different hash computations for many times, and the minimum value of the mapping is taken as a usage frequency of the key when reading

In Caffeine, a 4bit CountMinSketch is maintained to record the frequency of key usage

4-bit means that the maximum number of times a key is used is 15. For the logic, refer to the FrequencySketch class in the source code

The FrequencySketch class description above is clear

The maximum frequency is limited to 15(4 bits) and the periodic aging process halves the popularity of all elements

TinyLFU may not build enough frequency data in time to ensure its presence in the cache when dealing with burst traffic, which leads to the decrease of cache hit ratio. In order to solve this problem, W-TinylFU algorithm is produced

W-TinyLFU

W-tinylfu, which is also the cache strategy adopted by Caffeine, consists of window cache and main cache

The primary cache uses SLRU and TinyLFU reclamation strategies and occupies 99% of the total cache

The window cache uses the LRU algorithm without any reclamation policy and occupies 1% of the total cache. The window cache is used to deal with the problem of burst traffic

Caffeine dynamically adjusts window and main space sizes based on workload characteristics

Window cache

The window cache contains two internal parts, large Windows and small Windows

High frequency Windows are more popular for new data, and low frequency Windows are more popular for new data cache

The main cache

The main cache contains two parts,Probation and Protected

Probation is used for relatively cold data and takes up 20 percent of the main cache

Protected is used for hot data and takes up 80% of the main cache

Data can be transferred between these two parts of space

The process of cache flushing:

The newly added data is first put into the window cache, and if the window cache is full, the data is eliminated from the window cache (candidate)

Move to primary cache Probation zone, and flush data from Probation zone if Probation is also full (victim)

Candidates and victims then decide whether to stay or not based on the frequency of visits recorded by TinyFLU

Check the admit method of BoundedLocalCache class in Caffeine framework, as shown in the figure

Step logic

1. First get the victimFreq= candidateFreq= candidateFreq

2. If the candidate is judged to be greater than the victim, the victim will be eliminated; otherwise, proceed

3. If the frequency of a candidate’s visit is less than or equal to 5, the candidate is eliminated. Otherwise go down

4. If none of them are true, they will be randomly eliminated

Internal interface relationship of Caffeine

Caffeine’s UML class diagram

When viewing the source code, you can first find the framework’s dependency packages and then view the UML class diagram through IDEA. In this way, you can clearly see the relationship between interfaces and classes

There are two packages and two classes in Caffeine source code. The specific implementation logic is under the cache package

Choose the 1:1 method to see more clearly

Ignore the solid blue line with all uppercase class names, which are dynamically generated. It focuses on the implementation of Cache, LocalCache and AsyncLoadingCache

Caffeine is build the source code

When Caffeine is built, it is built using the build method. What loading method is used is also differentiated by the build method

So it’s worth looking at how the build method is implemented

First, open the Caffeine class to view the Build method

From the Caffeine class, we can see that the build is an overloaded method, with both passable and non-passable implementations

Let’s take a look at the contents of the no-argument build method, which comes with a ternary operator and returns the instantiated implementation class

Let’s take a look at Caffeine’s core class diagram to get an idea of the interface relationships inside Caffeine

As you can see, first there is a class called Cache, and then we go through the UML class diagram we just opened to find the Cache and press F4 to enter the Cache class

Cache

A Cache is an interface that provides some method definitions

LoadingCache

Then we move on to the LoadingCache interface

LoadingCache inherits the Cache interface and extends three methods: GET, getAll, and refresh

The Cache interface is more like a map for storing K values

LoadingCache defines the loading and updating mechanism, which operates on specific items in the cache ader passed in by the build method

LocalManualCache

LocalManualCache also inherits the Cache interface

LocalManualCache interface there are two main implementation class UnboundedLocalManualCache and BoundedLocalManualCache

UnboundedLocalManualCache

If in the case of without any recovery strategy UnboundedLocalManualCache will be used, the implementation is also minimal provides the function of the cache

As you can see from the constructor, it initializes a ConcurrentHashMap of capacity 16. It also provides basic state counters, removes listeners, and writers

Since it doesn’t have any active recycle strategy, it essentially operates on ConcurrentHashMap

BoundedLocalManualCache

Caffeine is a cache implementation with a collection policy. Caffeine also has a specific implementation class, implemented by LocalCacheFactory

You can see there’s only one newBoundedLocalCache method in there

This method concatenates a string for each case of our configuration, resulting in the full name of the corresponding implementation class and then loading it through the class loader

The reflexing approach is also due to Caffeine’s optimization for every situation, which is why idea generates UML class diagrams with all caps

It will eventually return a BoundedLocalCache, which is one of the implementation classes that we will eventually use

Caffeine Cache Classification

The three dimensions, from synchronous to asynchronous, manual to autoload, and bounded to unbounded, can be roughly divided into eight cache types

The atomicity of Caffeine’s operation

Caffeine’s load,put, and invalidate operations are all atomic, meaning that they are mutually exclusive

Load and PUT cannot be executed at the same time. Load and invalidate cannot be executed at the same time

This approach is different from Guava, which is non-blocking

If you call load first and then invalidate, the invalidate will be executed very quickly, and the result will not be as expected before the load is loaded

Concepts can be abstract, but here are some examples to illustrate

Guava sample

@SneakyThrows
public static void main(String[] args) {
    LoadingCache<String, String> cache = CacheBuilder.newBuilder()
        .maximumSize(5)
        .expireAfterWrite(10, TimeUnit.MINUTES)
        .build(new CacheLoader<String, String>() {
            @SneakyThrows
            @Override
            public String load(String id) {
                // Sleep for one second while loading
                Thread.sleep(1000);
                returnid + System.currentTimeMillis(); }});// Asynchronous thread loading
    new Thread(() -> {
        try {
            System.out.println("Get");
            cache.get("key");
        } catch (ExecutionException e) {
            e.printStackTrace();
        }
    }).start();

    // Asynchronous thread removal
    new Thread(() -> {
        // Sleep, let this thread execute after
        try {
            Thread.sleep(200);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("Executive invalidate");
        cache.invalidate("key");
    }).start();

    // According to program logic, we should get an empty map
    Thread.sleep(1200);
    System.out.println(cache.asMap());
}
Copy the code

It can be seen that in multi-threaded cases, even if the invalidate method is called after the get call, the key is still not removed, and the execution result does not meet the expectation

Caffeine is the sample

@SneakyThrows
public static void main(String[] args) {
    LoadingCache<String, String> cache = Caffeine.newBuilder()
        .maximumSize(5)
        .expireAfterWrite(10, TimeUnit.MINUTES)
        .build(key -> {
            // Sleep for one second while loading
            Thread.sleep(1000);
            return key + System.currentTimeMillis();
        });

    // Asynchronous thread loading
    new Thread(() -> {
        System.out.println("Get");
        cache.get("key");
    }).start();

    // Asynchronous thread removal
    new Thread(() -> {
        // Sleep, let this thread execute after
        try {
            Thread.sleep(200);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("Executive invalidate");
        cache.invalidate("key");
    }).start();

    // According to program logic, we should get an empty map
    Thread.sleep(1200);
    System.out.println(cache.asMap());
}
Copy the code

You can see that with Caffeine, even in multithreaded execution, the results are as expected

Caffeine’s atomicity is achieved simply by using a ConcurrentHashMap for storage

Using the ConcurrentHashMap node lock, the invalidate operation corresponds to the remove method

Caffeine cache expiration policy resolution

Caffeine has three expiration strategies. How does Caffeine proactively recycle the cache

Open the BoundedLocalCache class to see afterRead and afterWrite methods

You can see that both the afterRead and afterWrite methods call the ScheduleBuffers method

Look again at the Schedulebuffers method

This method is actually used to expire the task scheduling, we can see that its implementation is locking operation

The drainBuffersTask is called by the drainBuffersTask thread pool. The drainBuffersTask belongs to PerformCleanupTask

We can look again at the run method implemented by PerformCleanupTask

The performCleanUp method is called from the cache

You can see that the performCleanUp method locks and unlocks when calling the maintenance method, and then click in to see the implementation of the maintenance method

There are many methods in this method, all of which are used to do specific recycling

void maintenance(@Nullable Runnable task) {
    lazySetDrainStatus(PROCESSING_TO_IDLE);

    try {
      // The read cache is exhausted
      drainReadBuffer();

      // Write cache is exhausted
      drainWriteBuffer();
      if(task ! =null) {
        task.run();
      }
        
      // Key references are exhausted
      drainKeyReferences();
      // The value reference is exhausted
      drainValueReferences();

      // The expiration date has been reached
      expireEntries();
      // The size limit is reached
      evictEntries();

      climb();
    } finally {
      if ((drainStatus() != PROCESSING_TO_IDLE) || !casDrainStatus(PROCESSING_TO_IDLE, IDLE)) {
        lazySetDrainStatus(REQUIRED);
      }
    }
  }
Copy the code

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Implementation principle of Caffeine (Source code Analysis)

preface

Cache elimination algorithm

LRU (Least Recently Used)

LFU (Least FrequentlyUsed)

FIFO (First In First Out)

TinyLFU

W-TinyLFU

Internal interface relationship of Caffeine

Caffeine’s UML class diagram

Caffeine is build the source code

Cache

LoadingCache

LocalManualCache

UnboundedLocalManualCache

BoundedLocalManualCache

Caffeine Cache Classification

The atomicity of Caffeine’s operation

Caffeine cache expiration policy resolution

Implementation principle of Caffeine (Source code Analysis)

preface

Cache elimination algorithm

LRU (Least Recently Used)

LFU (Least FrequentlyUsed)

FIFO (First In First Out)

TinyLFU

W-TinyLFU

Internal interface relationship of Caffeine

Caffeine’s UML class diagram

Caffeine is build the source code

Cache

LoadingCache

LocalManualCache

UnboundedLocalManualCache

BoundedLocalManualCache

Caffeine Cache Classification

The atomicity of Caffeine’s operation

Caffeine cache expiration policy resolution

Related Posts

Dart-aqueduct Framework Development (4)

Automatically download images | Python theme month using Python(crawler)

Python2.0 is dying. What should you do?