1. Introduction

Before you read this article, I hope you read it well: What You Should Know about the evolution of caching and how to design and use caches gracefully? . These two articles mainly from some practical above to introduce how to use the cache. In both articles I recommend Caffeine, a local Cache, to replace your Guava Cache. In this article, I’m going to explain what Caffeine cache does and how it works internally, so you know how and why. Some people may ask: I don’t use Caffeine, this article won’t be useful to me. Don’t worry, your knowledge of Caffeine will definitely help you in other aspects of code design. Of course, before introducing it, I would like to post some comparisons with other caches:

1.1 How to Use

Caffeine is easy to use and has the same API as Guava Cache:

public static void main(String[] args) {
        Cache<String, String> cache = Caffeine.newBuilder()
                .expireAfterWrite(1, TimeUnit.SECONDS)
                .expireAfterAccess(1,TimeUnit.SECONDS)
                .maximumSize(10)
                .build();
        cache.put("hello"."hello");
    }
Copy the code

2. Introduction to Caffeine principle

2.1 W – TinyLFU

The traditional LFU is greatly affected by the time period. So various variations of the LFU have emerged, decaying based on time periods, or frequencies within the most recent time period. Similarly, the LFU uses extra space to record the frequency of each data access, even if the data is not in the cache, so the extra space to maintain is large.

If you create a hashMap of this maintenance space, every data item will be stored in this hashMap, and when the amount of data is very large, the hashMap will be very large.

Going back to LRU, our LRU is not so bad. It can handle bursts of traffic very well because it does not need to accumulate data frequencies.

So W-TinylFU combines some characteristics of LRU and LFU, as well as other algorithms.

2.1.1 Frequency record

The first thing to talk about is frequency recording. What we want to achieve is to use limited space to record the frequency of access over time. In W-Tinylfu we use the Count-min Sketch to record our access frequency, which is also a variant of the Bloom filter. As shown in the figure below:

Here’s a quick comparison to the previous one: If I have a hashMap to record this frequency, if I have 100 data, then the hashMap has to store 100 access frequencies of this data. Even if the capacity of my cache is 1, because of the Lfu rules, I have to record all the access frequency of the 100 data. If I had more data I would have more records.

In The Count-Min Sketch, and I’ll go straight to the caffeine implementation (in FrequencySketch), if your cache size is 100, it will generate a long array whose size is the nearest 100 to the power of 2, which is 128. And this array is going to keep track of our access frequency. In caffeine, the binary bit 1111 with a maximum frequency of 15,15 is defined for a total of 4 bits, while the Long is 64 bits. So each Long can hold 16 algorithms, but Caffeine doesn’t do that. Instead, it uses only four hash algorithms, and each Long is divided into four segments, each of which holds the frequencies of the four algorithms. The advantage of this is that you can reduce Hash collisions even further, so instead of a 128 size Hash, you have a 128 x4 Hash.

The structure of a Long is as follows:

  1. First, determine which segment the hash 50 is in. Hash & 3(the binary value of 3 is 11) must yield A number less than 4, assuming hash & 3=0, which is in segment A.
  2. The hash of 50 is repeated with another hash algorithm to get the position of the long array, that is, the position in the 128 length array. Let’s say we get 1 with S1, 3 with S2, 4 with S3, and 0 with S4.
  3. Since S1 gives 1, we add 1 at S1 in segment A of long[1], 1As1 plus 1, 3As2 plus 1, 4As3 plus 1, 0As4 plus 1.

At this point, one might question whether the maximum frequency of 15 is too small? It doesn’t matter. In this algorithm, for example, if size is equal to 100, if it globally increases size*10, that is 1000 times, it will globally divide by 2 for attenuation, and can continue to increase after attenuation. This algorithm has been proved in w-Tinylfu’s paper that it can better adapt to the access frequency of time period.

2.2 Read/Write Performance

In the Guava Cache, we said that the read and write operations are interlocked with the expiration time, that is, you may also have to do an obsoleted operation during a Put operation, so the read and write performance is affected. As you can see in the figure above, Caffeine does burst the Guava cache on the read and write operations. The main reason is that in Caffeine, these events are handled asynchronously by submitting them to a queue. The data structure of the queue is a RingBuffer. If you don’t know, check out the high-performance unlocked queue Disruptor in this post. It will then be queued by using the default ForkJoinPool.commonPool() or by configuring the pool itself, and will then be eliminated or expired.

Of course, there are different queues for reads and writes. In Caffeine, there are more cache reads than writes, so all threads share a Ringbuffer for writes.

For reads to be more frequent than writes, further reducing contention, there is a RingBuffer for each thread:

2.3 Data elimination strategy

In Caffeine, all data is in ConcurrentHashMap, which is different from the Guava cache, which implements a structure similar to ConcurrentHashMap. There are three LRU queues referenced by records in Caffeine:

  • Eden queue: Caffeine is limited to %1 of the cache capacity, and if size=100, the effective size of this queue is equal to 1. This queue records new data to prevent burst traffic from being eliminated due to lack of previous access frequency. For example, when a new play goes online, there is actually no access frequency at the beginning, so as to prevent it from being eliminated by other caches after going online, and join this region. The Eden area, the most comfortable and comfortable area, is hard to eliminate from other data.

  • “Probationary queue” means your data is relatively cold and you’re on the verge of being phased out. The effective size is size minus Eden minus protected.

  • Protected queue: With this queue, you can rest assured that you’re not on Probation for a while, but don’t worry, if the queue runs out of data or is full of Protected data, you will be. Of course, to get into this queue, you have to visit Probation once, and then it’s promoted to Protected. The effective size is (size minus Eden) X 80%. If size =100, it would be 79.

The relationship of the three queues is as follows:

  1. All new data will go to Eden.
  2. Eden is full, suspended on Probation.
  3. If one of the data is accessed in Probation, it is made Protected.
  4. If Protected is full, it will be downgraded to “Probation”.

When data cull takes place, it will be culled from Probation. The head of the queue will be called the victim, the head of the queue must be the first to enter, according to the ALGORITHM of THE LRU queue then he should be eliminated, but here he can only be called the victim, this queue is the probation queue, which means he is about to be executed. So here we take the end of the line and we call the candidate, or the attacker. This is where the victims will be pitted against the attackers and we will be eliminated.

  • If the attacker is greater than the victim, the victim is eliminated.
  • If the attacker is <=5, then the attacker is eliminated. This logic is explained in his notes:

    He believes that setting a warm-up threshold will lead to a higher overall hit rate.

  • In other cases, random selection.

3.Caffeine analysis

There are a lot of features in Caffeine, so let’s take a look at how these apis work.

3.1 Let a hundred Flowers bloom -Cache factory

There is a LocalCacheFactory class in Caffeine that creates a specific Cache based on your configuration.

3.2 Transient – Expiration Policy

In Caffeine, there are two types of caches, bounded and unbounded. Unbounded caches do not need to expire and have no bounds. Three expiration apis are provided in bounded caches:

  • ExpireAfterWrite: indicates how long after the writing has expired.
  • ExpireAfterAccess: represents how long after the last access has expired.
  • ExpireAfter: In expireAfter you need to implement the Expiry interface yourself, which supports create, Update, and how long after access expires. Note that this API is mutually exclusive with the previous two apis. The difference between this and the previous two apis is that you need to tell the cache framework that it should expire at a specific time, by overwriting create, Update, and Access.

In Caffeine, there is a “schedulehandlers” method that is used to schedule our expired tasks and is called after we read and write:

The first thing he does is lock it, and if the lock fails, someone is already scheduling it. It uses either the default ForkJoinPool or a custom thread pool, and the drainBuffersTask is actually A PerformCleanupTask in Caffeine.

As you can see, there are quite a few methods, and we’ll discuss the others later, but here we’ll focus on expireEntries(), which is the method used to expire:

  • First get the current time.
  • ExpireAfterAccess expireAfterAccess expireAfterAccess

  • The third step is expireAfterWrite:

  • Step 4: expireVariableEntries expire:

The time wheel in Caffeine is shown above. When we insert the data, we calculate the expiration time according to our rewrite method. For example, it should expire at 1536046571142. The expiration time of the last processing was 1536046571100. So put the position of 1.07s directly, and some position in the second layer (which needs to be calculated by some algorithm), and use the tail interpolation method to insert into the list.

When processing the expiration time, the difference between the last processing time and the current processing time is calculated, and all the time rounds within this time range need to be processed. If a Node is not actually expired, it needs to be reincarnated into the time round.

3.3. Out with new — Update your policies

Caffeine provides a refreshAfterWrite() method to allow us to update our strategy after writing:

In the above code, we need to set up a cache loader to do the refresh. In this case, we do it synchronously, and we can do it asynchronously with the buildAsync method. In real business, mapper in our code can be passed in here to refresh the data source.

Note that the refresh does not occur when the data is due, but only after the data is accessed again. For example, if we have data for key:’ coffee ‘and value:’ latte ‘, we set it to refresh for 1 second. After we add data, we wait for 1 minute. The next time we access the data, it should refresh and get the new value. However, if you continue to visit, you will find that he has already refreshed.

Let’s see what auto-refresh does. Automatic refresh only exists after the read operation, which is our afterRead() method. There is a method called refreshIfNeeded that will refresh you depending on whether you are synchronous or asynchronous.

3.4 Solid and False – Soft and weak references

There are four reference types in Java: StrongReference, SoftReference, WeakReference, and PhantomReference.

  • Strong references: Declaring an object directly in our code is a strong reference.
  • Soft references: If an object has only soft references, the garbage collector will not reclaim it if there is enough memory. If the memory space runs out, the memory of these objects is reclaimed. As long as the garbage collector does not reclaim it, the object can be used by the program. Soft references can be used in conjunction with a ReferenceQueue (ReferenceQueue). If the object referenced by the soft reference is collected by the garbage collector, the Java virtual machine will add the soft reference to the ReferenceQueue associated with it.
  • Weak references: When the garbage collector thread scans the area of memory it manages, once it finds an object with only weak references, it will reclaim its memory, regardless of whether the current memory space is sufficient. Weak references can be used in conjunction with a ReferenceQueue (ReferenceQueue). If the object referenced by the weak reference is garbage collected, the Java virtual machine will add the weak reference to the ReferenceQueue associated with the weak reference.
  • Virtual references: If an object holds only virtual references, then it is as likely to be collected by the garbage collector at any time as if there were no references at all. Virtual references must be used in conjunction with the ReferenceQueue. When the garbage collector is ready to reclaim an object, if it finds that it has a virtual reference, it will add the virtual reference to the reference queue associated with it before reclaiming the object’s memory.

3.4.1 Weak reference Elimination policy

The elimination policy for weak references is supported in Caffeine, with two apis: weakKeys() and weakValues(), which set whether key or value is a weak reference. When put, the key and value are wrapped in virtual references and bound to the reference queue:

In the maintenance method we introduced earlier, there are two methods:

Handlers keyReferences (); DrainValueReferences ();Copy the code

The specific processing code is:

Because our key has been reclaimed, and then it goes to the reference queue, and it pops up through the reference queue until it’s empty. We can get the Node based on the application in the queue and expel it.

Note: Many students think that the internal cache is stored in the form of key-value, in fact, it is stored in the form of keyreference-node (Node contains Value).

3.4.2 Soft reference Elimination Policy

In Caffeine, a soft reference elimination policy is also supported. The API is softValues(). Soft references only support Value but not Key. We can see in the recycle policy of Value:

3.5 Know yourself know your enemy – Monitoring

There are a few door-monitoring policies available in Caffeine, which are enabled via the recordStats()Api. By default, Caffeine comes with it, or you can implement it yourself. In the StatsCounter interface, we define the methods that need to be dotted.

  • RecordHits: Records are hit
  • RecordMisses: Record cache misses
  • RecordLoadSuccess: Indicates that the CacheLoader has been successfully loaded.
  • RecordLoadFailure: Record loading failure
  • RecordEviction: Records obsolete data

Through the above monitoring, we can monitor the current state of the cache in real time to evaluate the health of the cache and the hit ratio of the cache, so as to facilitate the subsequent adjustment of parameters.

3.6 Finish what you start – eliminate monitoring

There are a lot of times when you need to know why the cache in Caffeine has been eliminated so that you can optimize it. At this point we need a listener, which looks like this:

Cache<String, String> cache = Caffeine.newBuilder()
                .removalListener(((key, value, cause) -> {
                    System.out.println(cause);
                }))
                .build();
Copy the code

There are a number of reasons why people fail in Caffeine:

  • EXPLICIT: The cause is user-generated and is removed by calling the remove method.
  • REPLACED: When you update, you actually delete the old value.
  • COLLECTED: For our garbage collector, that is, our reduced soft references above, weak references.
  • “EXPIRED” : EXPIRED.
  • SIZE: SIZE elimination, when the maximum will be eliminated.

When we do the weeding, we do the callback, and we can print out the log to monitor the data weeding in real time.

4. The last

This article introduces all of Caffeine’s functional principles, including LFU,LRU, time wheel, four Java references, and more. If Caffeine isn’t your cup of tea, you’ll learn a lot from this introduction. Finally, the series about caching has basically come to an end. If you want to know more, you can follow my official account, add me as a friend or join the technical communication wechat group to discuss.

Finally, this article is included in JGrowing, a comprehensive, excellent, community-built Java learning route, if you want to participate in the maintenance of open source projects, you can build together, github :github.com/javagrowing… A little star, please.

If you think this article is good for you, you can follow my technical official account. Recently, the author has collected a lot of latest learning materials, videos and interview materials, you can get them after you follow them. Your attention and forwarding are the biggest support for me, O(∩_∩)O