1. Use an array to store data Mark each data item with an access timestamp. Each time a new data item is inserted, first increment the timestamp of the data item existing in the array, set the timestamp of the new data item to 0 and insert it into the array. . Each time a data item in the array is accessed, the timestamp of the accessed data item is set to 0. When the array space is full, the data item with the largest timestamp is eliminated.

2. Use a linked list to implement Every time new data is inserted, the new data is inserted into the head of the linked list; every time the cache hits (that is, the data is accessed), the data is moved to the head of the linked list; then when the linked list is full, the data at the end of the linked list is moved. throw away.

3. Use linked lists and hashmaps. Maintain linked list and map at the same time, map is used for index search When a new data item needs to be inserted, if the new data item exists in the linked list (generally called a hit), the node is moved to the head of the linked list. If it does not exist, a new node is created and placed at the head of the linked list. If the cache is full, just delete the last node of the linked list. When accessing data, if the data item exists in the linked list, move the node to the head of the linked list, otherwise -1 is returned. In this way, the node at the end of the linked list is the most recently accessed data item.

LinkedHashMap

When hot data exists, LRU is very efficient, but occasional and periodic batch operations will cause the LRU hit rate to drop sharply and cache pollution to be serious.

The main purpose of LRU-K is to solve the "cache pollution" problem of the LRU algorithm. Its core idea is to extend the judgment criterion of "recently used once" to "recently used K times".

accomplish

2Q changes the access history queue in the LRU-2 algorithm (note that this is not used to cache data) to a FIFO cache queue, that is: the 2Q algorithm has two cache queues, one is a FIFO queue and the other is an LRU queue.

When the data is accessed for the first time, the 2Q algorithm caches the data in the FIFO queue. When the data is accessed for the second time, the data is moved from the FIFO queue to the LRU queue. The two queues each eliminate the data according to their own methods.

Avoids cache damage caused by batch queries

The MQ algorithm divides data into multiple queues based on access frequency. Different queues have different access priorities. The core idea is to cache data with more access times first. The detailed algorithm structure diagram is as follows, Q0, Q1...Qk represent different priority queues, Q-history represents the queue that eliminates data from the cache, but records the index and reference number of the data.

The newly inserted data is put into Q0, and each queue is managed according to LRU. When the number of accesses to the data reaches a certain number and the priority needs to be increased, the data is deleted from the current queue and added to the head of the higher-level queue; in order To prevent high-priority data from ever being eliminated, when the data is not accessed within the specified time, the priority needs to be lowered, the data is deleted from the current queue, and added to the head of the lower-level queue; when the data needs to be eliminated, Starting from the lowest level queue, the queue is eliminated according to LRU. When each queue eliminates data, the data is deleted from the cache and the data index is added to the Q-history header. If the data is revisited in Q-history, its priority is recalculated and moved to the head of the target queue. Q-history eliminates the index of data according to LRU.

The data stream length N is very large and unknown, so it cannot be stored in memory at once.

The time complexity is O(N).

m numbers are randomly selected, and the probability of each number being selected is m/N.

If the amount of received data is less than m, it is put into the reservoir in sequence.

When the i-th data is received, i >= m, a random number d is taken in the range [0, i]. If d falls in the range [0, m-1], the received i-th data is used. The data replaces the dth data in the reservoir.

Repeat step 2.

The probability that the i-th received data can finally stay in the reservoir = the probability that the i-th data has entered the reservoir * the probability that the i-th data will not be replaced thereafter (i-th to N-th data processing will not be replaced).

Idea: Prove respectively that when i <=m, the probability of entering the reservoir and the probability of not being replaced by the following value When i>m, the probability of entering the reservoir and the probability of not being replaced later Important proof is below

When i<=m, the program starts to perform the replacement operation when receiving the m 1th data. The m 1st processing will replace the data in the pool is m/(m 1), and the probability of replacing the ith data is 1/m, then the probability of replacing the i-th data in the m-th processing is (m/(m 1))*(1/m)=1/(m 1), and the probability of not being replaced is 1- 1/(m 1)=m/(m 1). In turn, the probability that the m-th processing does not replace the i-th data is (m 1)/(m 2)... The probability that the N-th processing does not replace the i-th data is (N-1)/N. Therefore, the probability that the i-th data will not be replaced later =m/(m 1)*(m 1)/(m 2)*...*(N-1)/N=m/N.

Idea: 1. Split N into k machines, which can be divided according to hash. 2. A single machine obtains m values ​​from each reservoir. 3. Randomly pick a value from [1, N]. If it is on N1 (on the first machine, it can be calculated directly based on the hash if you use hash), then randomly 1/ m takes a value

Assume that there are K machines, and the large data set is divided into K data streams. Each machine uses a stand-alone version of the reservoir to sample and process a data stream, sample m data, and finally record the amount of processed data as N1, N2, .. ., Nk, ..., NK (assuming m<Nk). N1 N2...NK=N.

Take a random number d from [1, N]. If d<N1, select a data in the first machine's reservoir with medium probability without replacement (1/m); if N1<=d<(N1 N2 ), then select a piece of data from the reservoir of the second machine with medium probability without replacement; by analogy, repeat m times, and finally select m pieces of data from the N large data set.

Derivation

Set the total funnel capacity as the maximum concurrency level of the service

Set the consumption rate of the funnel, which is fixed

The funnel is empty by default, and requests enter the bucket.

The funnel algorithm is actually pessimistic, because it strictly limits the throughput of the system. From a certain perspective, its effect is very similar to concurrency limiting. The funnel algorithm can also be used in most scenarios, but because it has strict and fixed limits on service throughput

Guarantee the highest number of concurrency of the service, but the performance is not good when the instantaneous traffic increases.

The token bucket algorithm can limit the average transmission rate of data while also allowing a certain degree of burst transmission.

When the token bucket can be empty, the request will be discarded. At the same time, tokens are stored in the bucket at a rate of 1/r

load balancing

Handle sharding, no distributed lock architecture

Use Hash Ring

Route the request to the ring, and drift the request to the previous node clockwise when drifting

Use virtual nodes.

Including hash ring add, remove and hash node positioning

Use two Maps

murmur