preface

Hello, everyone, I’m Asong. Recently wanted to write a localcache headphones, work so long, also seen many colleagues to achieve the local cache, all strengths and they usually also in thinking about how to achieve a high performance local cache, then I will be based on their understanding of a version to cache, welcome leaders put forward valuable opinion, I will constantly improving according to the opinion.

This article focuses on what to think about when designing a local cache, but keep an eye on this series for future implementation articles.

Why local cache

With the popularity of Internet, more and more users, and traffic, which requires our application support more concurrency value, such as a treasure to the front page of a flow, a large number of users to enter the home page at the same time, to our application server and database server computing is huge, itself takes up the database connection, database access to network overhead, In the face of such high concurrency, the database will be the bottleneck, then consider to add the cache, the cache is divided into distributed cache and local cache, most of the scenes we use distributed cache can meet the requirements, a distributed cache access speed is very fast, but the data need across the network transmission, in the face of the home page under the high concurrency magnitude, the performance requirements are very high, In this case, local cache can be used to improve performance. Local cache does not need to be transmitted across networks. Applications and cache reside in the same process.

To sum up, we tend to use the local cache after the system architecture is like this:

Although local cache brings performance optimization, it also has some disadvantages. The cache and application coupling, multiple applications cannot directly share the cache, each application or cluster node need to maintain their own separate cache, it is a waste of memory, we programmers use cache. According to the data types and business scenarios, we should accurately determine what type of cache to use and how to use this cache to achieve the optimal purpose with the lowest cost and the fastest efficiency.

Consider: How to implement a high-performance local cache

The data structure

The first step is to consider how data should be stored; Data search efficiency to high, first of all, we thought of the hash table, hash table search efficiency is high, time complexity is O(1), can meet our needs; Because different business scenarios use different data types, for general purpose, we can use generics in Java, Go language does not have generics, we can use interface type instead. Leaving parsing data in the hands of programmers to make their own assertions increases extensibility, but also some risk.

Conclusion:

  • Data structure: Hash table;
  • key:stringType;
  • value:interfaceType;

Concurrent security

The application of local cache will definitely face the scenario of concurrent read and write, which is to consider the problem of concurrent security. Because we choose hash structure, Go language mainly provides two kinds of hashing, one is a non-thread-safe map, the other is a thread-safe sync.map. For convenience, we can directly choose sync.map, or we can consider using map+sync.RWMutex combination to ensure thread safety. Sync. map performs better than the map+sync.RWMutex combination when more reads than writes are performed. In the local cache, the read operation is much higher than the write operation, but the local cache not only supports the use of locks for data storage, but also for expiration operations, so the map+ sync.rwmutex method is more flexible, so we choose this method to ensure concurrency security.

High-performance concurrent access

Locking can ensure data read and write security, but it will increase lock competition. Local cache is designed to improve performance, not make it a performance bottleneck, so we need to optimize lock competition. In the local cache application scenario, buckets can be processed by key to reduce lock contention.

Our keys are all strings, so we can use the DJB2 hash algorithm to break the keys into buckets, and then lock each bucket, that is, lock refinement to reduce competition.

Upper limit of the object

Because the local cache is stored in memory, memory is limited, we can not store infinite, so we can specify the number of cache objects, based on our specific application scenario to estimate the upper limit, the default value of cache is 1024.

Elimination strategy

Because we will set the number of cache objects, when the upper limit is triggered, we can use the elimination strategy to eliminate them. Common cache elimination algorithms are as follows:

LFU

LFU (Least Frequently Used) is an algorithm that weeds out data based on the historical access frequency of the data. The core idea of this algorithm is that the data that has been Used less Frequently in the recent times is most likely to be Used no longer, and the data that has been Used Least Frequently is replaced out.

Existing problems:

Some data in a short period of time by high-frequency access, after a long period of time no longer be accessed, because before the visit frequency has increased dramatically, so the will not be eliminated in a short time later, occupies a position in front of the queue, will lead to more frequent use of block is more easy to remove, just enter the new data cache may soon be deleted.

LRU

LRU (further Recently User), namely the Least Recently used algorithm to eliminate according to access data in the history of the data, this algorithm is the core thought that Recently used data is very big probability will once again use, has not been used for a period of time data, large probability won’t use again, the longest time not accessed data exchange

Existing problems:

If a client accesses a large amount of historical data, the data in the cache may be replaced by historical data, reducing the cache hit ratio.

FIFO

FIFO (First in First out) is the First in First out algorithm, the core idea of this algorithm is recently accessed, the possibility of future access is relatively large, the First data into the cache is the First to be eliminated.

Existing problems:

This algorithm uses an absolutely fair way to replace data, and it is easy to have the problem of missing pages.

Two Queues

Two Queues are the combination of FIFO + LRU. Its core idea is to cache data in FIFO Queues when it is accessed for the first time and move it from FIFO Queues to LRU Queues when it is accessed for the second time. These Two Queues eliminate data in their own ways.

Existing problems:

This algorithm is the same as LRU-2, but has poor adaptability. The data in LRU requires a large number of accesses before the historical records are cleared.

ARU

Adaptive Replacement Cache (ARU) is a combination of LFU and LRU algorithm. Its core idea is to increase the size of the corresponding LRU or LFU linked list according to the access of eliminated data. ARU mainly contains four linked lists. LRU and LRU Ghost, LFU and LFU Ghost, Ghost linked list is the corresponding eliminated data record linked list, do not record data, only record ID and other information.

When the data is accessed, it is added to the LRU queue. If the data is accessed again, it is also placed in the LFU linked list. If the data is discarded in the LRU queue, the data goes to the LRU Ghost queue, and if the data is accessed later, the SIZE of the LRU queue is increased while the size of the LFU queue is reduced.

Existing problems:

Because there are four queues to maintain, it takes up more memory.

choose

Each algorithm has its own characteristics, combined with our local cache use scenario, it is a good choice to choose ARU algorithm to do cache cache elimination strategy, can dynamically adjust the size of LRU and LFU to adapt to the current best cache hit.

Overdue cleared

In addition to using a cache flush policy to clean up data, you can also add an expiration time as a double guarantee to prevent infrequently accessed data from occupying memory. There are two ways to do this:

  • If the data expires, delete it directly
  • Data is not deleted when it expires and is updated asynchronously

Advantages and disadvantages of each two practices in asynchronous update data need to choose specific business scenarios, in order to cater to most of the business, we use the data is out of date directly delete this method more friendly, here we adopt the way of lazy loading, when get the data to determine whether a data expiration, setting up a regular tasks at the same time, every time delete outdated data.

The cache monitor

A lot of people for the cache monitor is ignored, after the basic writing is not an error he has to take effect by default, this will not be able to perceive whether the cache works, so the cache monitor of various indicators, is more important, through the different index data, we can optimize the cache parameters, so that to optimize the cache. For enterprise applications, we can use Prometheus for monitoring and reporting, and we can write a simple widget to print the number of caches and the hit ratio of caches.

The GC tuning

For applications that use a lot of local caching, GC issues must be common because of the cache obsolescence involved. If there are more GCS and longer STW times, service availability will definitely be affected. This is usually done on a case-by-case basis, and always check GC monitoring once the local cache is online.

The cache to penetrate

When using cache, you need to consider the problem of cache penetration, but this is not generally implemented in the local cache, basically left to the user to implement, when the cache can not find the element, it sets the cache key lock; Other threads will then wait for the element to be populated, rather than hit the database (encapsulated externally with SingleFlight).

Refer to the article

  • zhuanlan.zhihu.com/p/352910565
  • Cloud.tencent.com/developer/a…
  • Tech.meituan.com/2017/03/17/…
  • www.cnblogs.com/vancasola/p…

conclusion

Really want to design a high performance local cache is not easy, because I am also unskilled, the design idea of this article is personal practice ideas, welcome your valuable suggestions, we make a real high performance local cache.

In the next article I will share a local cache of my own writing, please look forward to it!!

Welcome to the public account: Golang Dream Factory