Hortonworks Ted Yu: Tiny LFU, a highly efficient cache admission policy

[Original article from 51CTO.com] On November 25, 2016, the WOT2016 Big Data Technology Summit hosted by 51CTO.com was held at the JW Marriott Hotel Beijing Yuecai. More than 50 senior technical experts in the field of big data from well-known companies such as Alibaba, Tencent, Baidu, JD.com, Xiaomi, etc. gathered at the conference site. They will have face-to-face exchanges and share experiences with more than a thousand front-line IT technicians in two days.

At the main venue of the WOT2016 Big Data Technology Summit, Ted Yu, a senior technical member of Hortonworks and a core contributor to HBase, gave a speech titled "Tiny LFU, a highly efficient cache admission policy". The following is a transcript of his speech:

[[177099]]

The distribution of data will also change over time. For example, if a user leaves, the data will not be very popular next week. So we need to consider the following two issues: when the cache is full, it must be removed. Many cache management solutions basically ignore admission. Compare the efficient policy with the new data to see which one is more suitable. If the new data has a greater contribution, put it back into the cache.

If it is accessed more frequently recently, we want to put it in the cache. Can we achieve a similar effect by increasing the size of the cache? The horizontal axis is the number of entries, which is how many entries the cache can hold. The larger the cache, the higher the percentage of entries that can be found in the cache. We found that when the cache reached 3,700 entries, its hit rate was equivalent to the two purple and blue ones at the bottom. So it can be seen that the size of the cache is not the determining factor of the cache.

What we are discussing today is mainly based on the access frequency. The lines above, TLFU and WLFU, for an entry, we hope that its source data occupies as little space as possible. Let's take a look at the simpler Window LFU. Let's take a look at this sliding window, which is based on the access frequency of the active window. There is a purple box, representing an entry. If it is more frequent than this WindowLFU, it will be placed in the cache.

Can we remove this sliding window? The expected value of the sliding window is 10. The fourth one is the yellow one, which is the extra one. If the window is not greater than 10, keep putting this entry in the cache. At this time, different entries come in. Well, the window of real-time entries is full. If we look for its window, we divide the Coueters for each entry by 3 divided by 2, which becomes 1, which will lose some precision.

The first is to remove the sliding window, and the second is that these statistical values ​​are not expressed in exact values, but in approximate values. The results presented below show that the effect is still very good. In the entry, this Counter can also be shared. You will know what this sharing means in the next column. In this way, the space consumed by the source data is very small, but the price is the loss of some precision. Simply put, this precision is divided by 2 and divided by 2 every time, but the maximum loss is 1.

To put it simply, how to determine if there is a value, convert it into a numerical value, and then see if it is in a set. One option is hashing, and after hashing, a value will be obtained. So in order to reduce collisions, the table is enlarged, which may be the opposite of reducing the space occupied by the source data that we are discussing now.

So Bloom fiters are more abstract. Let's take a look at this example. Suppose our data has 11 bits, and then there is K, that is, H to K, and the calculation is performed in the range from 0 to 1. When calculating Bloom fiters, it is necessary to connect to Y and K and calculate them all. The function of this Bloom fiter is still relatively limited, so we need to introduce a Counting Bloom, so that each bit is not only 0 and 1, but can be higher. When doing an increment, these bits are faceted accordingly, which is an increment operation. The second operation is to do a decrement, such as the 7th and 5th bits, and do an increment accordingly. The third is to make a corresponding estimate, because each position can have one bit. This one is 4, because 4 is the smallest.

One of the main techniques is Counting Bloom. When incrementing, we do not increment the first and fifth bits by 1, because 3 is the smallest, so we increment it by 1. However, we cannot decrement at this time, because there is only one bit and we don't know who to increment. The second improvement is to make the Counter smaller. Assuming a W is given, we roughly need to use LogW. With so many bits of information to represent it, can we do better? If an entry has to stay in the Counter, a W/C appears for the entire Counter. So for each Counter, 13 bits are enough, not 14 bits.

This counter can be made even smaller. Let's go back to the basic assumption that the distribution is very uneven. When watching videos on Youku or Tudou, some videos are not watched by many people, such as very few times, zero times or once, while some videos are very popular. Therefore, for those videos that only appear once, we need to set a SBF, which is the same as Counting Bloom. We first set a Counting Bloom of one bit. For these less popular data, we hope to limit its increment here.

If each position corresponds to 1 when doing increments, what will happen in the second-level SBF? So this is a two-level structure. Let's look at an example, which is deduced based on empirical values. Suppose there are one thousand entries, nine thousand Window LFUs, and an access frequency of 0.9 for alpha. In fact, 7239 items appear in the first item, and only 416 items can enter the second-level SBF. So from an overall average consideration, each entry only needs 1.22 bits, which only requires a very small space to represent the source data. Of course, in fact, each entry needs to be arranged with a Counter, so the source data should be a little more.

I just talked about four points, the main one is to remove the sliding window and use Counting Bloom as an approximation.

This graph has just appeared, let me say a few more words. WLFU does not need to be approximated. You can see that the purple line and the large blue line have the same accuracy, the first one is when alpha is equal to 0.9, and the second one is when alpha is equal to 0.7. This is from Wikipedia, because its sparsity may be different, but the meaning is the same. So I will quickly go through it.

IBM's work, this T1 is the recently accessed data, and the green area T2 is the area where the entries that are accessed more frequently are located more than twice. So the size of T1+T2 is fixed, but there is a pointer sliding between T2 and T1, which is to dynamically adjust between RU and RFU.

The rule is this: first, if you can't find it in T1 or T2, then go to B1, and change to a small ghost, and look for it in B1 or B2. If you find it in B1, you have to tilt the RLU part, so move it to the right, and if you find it in B2, then move it to the left.

Another competing one is called Low inter-reference Recency Set, which has a threshold. The second one is For frequent items, which are recently accessed. Below you will see a series of curves. The red one with a triangle is the top one, which is the ideal value. You can see that it is close to 60%, and the horizontal axis is still large in terms of items. The line opposite the red line is Lifs, and you can see that the two are comparable. The top one is the best solution, and the second one below is the Window Cache hit rate, which are all different data levels.

The green triangle in this chart is ARC, which is worse than the Window LFU rate. I want to talk about this chart. The red grid is sampling. Sampling is what I linked here with the other side. The window width of the first chart is 17,000 items, and the second is 9,000 items. The error in the green chart is basically not visible. The green is the decision error. The decision error is because 1.5 has become 1 as mentioned earlier, so there is a decision error. This error is relatively stable, and it is represented by the green space. The blue slash represents the approximate error, which is actually an approximation. This approximation itself has an error. It is not very visible in this chart, but when each item is 1.25 bits, there will be an approximate error. So you can see that the blue part appears at 1.25. If more data than 1.25 is used to represent it, there will be no such data.

So I want to tell you that when each entry uses 1.25 bytes, the effect is very ideal if the second sampling error, decision error and approximation error are taken into consideration. OK, let's see how it is related to HBase. LruBlockCache has 4766387 visits and a hit rate of 85.67%.

[51CTO original article, please indicate the original author and source as 51CTO.com when reprinting on partner sites]