This article describes the cache processing operation implemented by Nodejs based on LRU algorithm. Share it for your reference, as follows:
LRU is the abbreviation of Least Recently Used, which means that the page substitution algorithm is used at least recently. It is a virtual page storage management service and makes decisions based on the usage of the page after it is transferred into memory. Since it is impossible to predict the future usage of each page, you can only use the "recent past" as the approximation of the "recent future", so the LRU algorithm eliminates the most recently unused pages.
A special stack can be used to save the page numbers of each page currently in use. When a new process accesses a page, the page number is pushed to the top of the stack, and the other page numbers are moved to the bottom of the stack. If the memory is insufficient, the page number at the bottom of the stack will be removed. In this way, the top of the stack is always the number of the latest page being visited, while the bottom of the stack is the page number of the page that has not been visited recently.
If the following sequence is entered: 4,7,0,7,1,0,1,2,1,2,6
The result is:
4
4 7
4 7 0
4 0 7
4 0 7 1
4 7 1 0
4 7 0 1
4 7 0 1 2
4 7 0 2 1
4 7 0 1 2
7 0 1 2 6
An LRU cache suitable for, capacity is the cache capacity, and when it is 0, it constructs a general cache.
function CacheLRU(capacity) {
/* Use an LRU cache written by Buffer. Capacity is the cache capacity. When it is 0, it does not limit the capacity.
myCache = new CacheLRU(capacity); //Construct cache
(key); //Read the cached value named key
(key, value); //Write a cached value named key
(key); //Delete the cached value named key
(); //Clear the cache
(); //Return myCache cache information
LRU principle: build a hash linked list for all cached data keys. When a certain data is used for get or put operations, the key is mentioned to the front end of the linked list (latest). When put data exceeds capacity, delete the cached data at the end of the linked list (oldest)
The hash link list operation can directly locate the key without experiencing the entire hash object, so it reads and writes very quickly. The cache capacity no longer affects read and write speed.
*/
= capacity || Number.MAX_VALUE;
= {};
= {};
= {
length: 0,
head: null,
end: null
}
if (capacity <= 0) = Number.MAX_VALUE;
};
= function(key) {
key = '_' + key;
var lruEntry = [key];
if (!lruEntry) return;
refresh(, lruEntry);
return ([key].toString());
};
= function(key, value) {
key = '_' + key;
var lruEntry = [key];
if (value === undefined) return this;
if (!lruEntry) {
[key] = {key: key};
+= 1;
lruEntry = [key];
}
refresh(, lruEntry);
[key] = new Buffer((value));
if ( > ) ((1));
return this;
};
= function(key) {
key = '_' + key;
var lruEntry = [key];
if (!lruEntry) return this;
if (lruEntry === ) = ;
if (lruEntry === ) = ;
link(, );
delete [key];
delete [key];
-= 1;
return this;
};
= function() {
= {};
= {};
= {
length: 0,
head: null,
end: null
}
return this;
};
= function() {
var size = 0,
data = ;
while (data){
size += [].length;
data = ;
}
return {
capacity: ,
length: ,
size: size
};
};
// Update the linked list and mention the key of the get or put method operation to the linked list head, which means the latestfunction refresh(linkedList, entry) {
if (entry != ) {
if (!) {
= entry;
} else if ( == entry) {
= ;
}
link(, );
link(entry, );
= entry;
= null;
}
}
// Create a link to two linked list objects to form a chainfunction link(nextEntry, prevEntry) {
if (nextEntry != prevEntry) {
if (nextEntry) = prevEntry;
if (prevEntry) = nextEntry;
}
}
= CacheLRU;
// test:
/*var user = new CacheLRU(5);
('user1', {name:'admin', age: 30});
('user2', {name:'user', age: 31});
('user3', {name:'guest', age: 32});
('user4', {name:'guest', age: 34});
('user5', {name:'guest', age: 35});
(('user1'));
(('user2'));
(('user3'));
('user6', {name:'guest', age: 36});
(());*/
The LRU algorithm can also be used in some practical applications. If you want to build a browser or an application similar to a Taobao client, you must use this principle. Everyone knows that when the browser browses the web, it will temporarily save the downloaded images in a folder on the machine. The next time you access it, it will be read directly from the temporary folder on the machine. However, the temporary folders for saving pictures have certain capacity limits. If you browse too many web pages, some of the images you least use most will be deleted, and only some of the pictures you have used most recently. At this time, the LRU algorithm can be used. At this time, the special stack in the above algorithm is not the sequence number of the page, but the sequence number or size of each picture; so the elements of the above stack are represented by the Object class, so that the stack can save the object.
I hope this article will be helpful to everyone's nodejs programming.