In addition to Weibo, there is also WeChat
Please pay attention
WeChat public account
Shulou
2025-01-21 Update From: SLTechnology News&Howtos shulou NAV: SLTechnology News&Howtos > Development >
Share
Shulou(Shulou.com)06/02 Report--
In this issue, the editor will bring you the principle analysis of how to carry out the memcache kernel. The article is rich in content and analyzes and narrates it from a professional point of view. I hope you can get something after reading this article.
Memcache is the most frequently used KV cache in the hierarchical architecture of the Internet. During the interview, the questions related to memcache are almost necessary. What level can you answer to the interview questions about memcache?
The first kind of question: do you know?
This kind of question is relatively easy to answer to see if it has been used or whether it is known.
Some of the basic features of memcache can be answered by all the partners who have used it:
The core function of mc is KV memory management, value storage * * is 1m, it does not support complex data structures (hash, list, collection, ordered collection, etc.)
Mc does not support persistence
Mc supports key expiration
Memory fragmentation is rare when mc is running continuously, and the speed does not slow down with the running time of the service.
Mc uses the non-blocking IO multiplexing network model and the listening thread / worker thread multithreading model.
In the face of this kind of closed question, you must answer it firmly and without hesitation.
The second kind of question: why (why), what (what)
This kind of question, examines regarding a tool, only stays in the use level, or has the principle thinking.
(1) Why doesn't memcache support complex data structures? Why not support persistence?
Business determines the technical solution, the birth of mc, with the design goal of "managing KV memory as a service rather than a library". It subverts the KV memory management component library, complex data structures and persistence are not its original intention.
Of course, the word "subversion" is not necessarily inappropriate. Libraries and services have their own usage scenarios, but in a distributed environment, services are used more widely. Design goal, birth background is very important, which to some extent determines the implementation plan, such as the emergence of redis, in order to have a better use, more multi-functional cache service.
Voiceover: I like to ask this question very much. when most candidates face this question with no standard answer, their status may be a circle.
(2) what technology does memcache use to achieve key expiration?
Lazy elimination (lazy expiration).
(3) Why can memcache guarantee running performance with few memory fragments?
Allocate memory in advance.
(4) Why does memcache use the non-blocking IO multiplexing network model and the listening thread / worker thread multithreading model? what are the advantages and disadvantages?
The goal is to improve throughput.
Multi-threading can make full use of multi-core, but it will bring some lock conflicts.
In the face of such semi-open questions, some of them do not have standard answers, so we must answer our own thoughts and opinions.
The third type of question: what to do (how) | the text has just begun.
How thoroughly the candidates understand, how well they master, and how much they get to the bottom of the technology.
Voiceover: the so-called "curiosity" is really important, and it is very difficult for technical people who only want "a job" to have such curiosity.
(1) what does memcache implement memory management to reduce memory fragmentation, and how does it allocate memory?
Before we begin, let's explain a few very important concepts:
Chunk: it is the smallest unit that allocates memory to the user.
Item: the data that users want to store, including key and value, is eventually stored in chunk.
Slab: it manages several chunk of a fixed chunk size, while memory management of mc consists of several slab.
Voiceover: in order to avoid complexity, the concept of page is not introduced in this article.
As shown above, a series of slab manages 128B, 256B, 512B, respectively. The chunk memory unit of the
Zoom in on the slab0 managing 128B in the figure above:
Some of the core data structures found in slab are:
Chunk_size: this slab manages 128B chunk
Free_chunk_list: used to quickly find free chunk
Chunk []: actual chunk space that has been pre-allocated for storing user item data
Voiceover: actually, there is lru_list.
(2) if the user wants to store a 100B item, how to find the corresponding available chunk?
The corresponding chunk is quickly found through free_chunk_list from the chunk [] of the slab that is closest to the size of item. As shown in the figure above, the chunk closest to the size of item is 128B.
(3) Why is there no memory fragmentation?
Get a 128B chunk to store a 100B item, and the remaining 28B will not be used by other item, that is, actually wasting storage space to reduce memory fragmentation and ensure access speed.
Voiceover: in theory, memory fragmentation is almost non-existent.
(4) memcache quickly allocates memory and stores users' item through slab,chunk,free_chunk_list, so how does it quickly achieve key lookup?
There is no special algorithm:
Quick lookup through hash table
Resolve conflicts through linked lists
Realize the fast search of key in the most simple way.
(5) with the increasing number of item and hash conflicts, how to ensure the query efficiency of hash table?
When the total number of item reaches 1.5 times the length of the hash table, the hash table will dynamically expand and rehash will redistribute the data to ensure that the search efficiency will not decrease continuously.
(6) after expanding the hash table, the location of the same key in the new and old hash table will change, how to ensure the consistency of the data, and how to ensure the availability of the service during the migration process (surely you can't add a big lock, migrate the completed data, and then re-serve it)?
Hash table extension, data migration is a time-consuming operation, there will be a special thread to implement, in order to avoid large locks, using the "segmented migration" strategy.
When the number of item reaches the threshold, the migration thread migrates in segments, locks some buckets in the hash table, migrates data, and unlocks them:
First, it is guaranteed that there will be no prolonged blocking, which will affect the availability of the service.
Second, make sure that item will not be inconsistent between the new hash and the old hash.
(7) A new problem arises: the item that already exists in the old hash table can be migrated in the above way, so in the process of item migration, if there is a new item insert, should the old hash table or the new hash table be inserted?
What memcache does is to determine whether the bucket that item should insert in the old hash table has been migrated to the new table:
If migrated, item inserts directly into the new hash table
If it has not been migrated, insert the old hash table directly and wait for the migration thread to migrate to the new hash table in the future
(8) Why would you do that? can't you just insert the new hash table?
Memcache does not give an official explanation, and the landlord speculates that this method can ensure that the data in a bucket will only be in a hash table (either a new table or an old table), and will not appear in any scenario. The old table and the new table will be queried twice to improve the query speed.
(9) how does memcache achieve the expiration of key and how does lazy expiration play?
The two most common ways to achieve timeout and expiration are:
Start a timeout thread to scan all item. If a timeout is found, the timeout callback will be performed.
Each item sets a timeout signal notification, which triggers timeout callback processing.
Both methods require additional resource consumption.
The query business of mc is very simple, and only returns cache hit and cache miss results. In this scenario, it is very suitable to use lazy elimination.
The core of lazy elimination is:
Item will not be actively eliminated, that is, there is no timeout thread, and there is no signal notification to actively check
Every time item queries (get), check the timestamp. If it has expired, it will be passively eliminated and cache miss will be returned.
For example, if set has a key, the validity period is 100s:
On the 50s, a user get the key, determines that it has not expired, and returns the corresponding value.
On the 200s, another user inquires (get) the key, determines that it has expired, releases the chunk where the item is located, and returns cache miss
The implementation of this approach is very inexpensive and consumes very low resources:
In item, add an expiration attribute
In get, add a time judgment
Memory is always limited, and when the number of chunk is limited, the number of item that can be stored is limited. What if chunk is used up?
Still the above example, if the 128B chunk is used up and the user set a 100B item, do you want to squeeze out the existing item? Yes.
The lesson here is:
Even if the validity period of item is set to "*", it may be eliminated.
If you want to do full data caching, you must carefully evaluate that the memory size of cache must be greater than the total size of full data, otherwise it is easy to mine the pit.
(10) which item is squeezed out? How do you squeeze?
The LRU phase-out mechanism is involved here.
If the operating system manages memory, the most common elimination algorithms are FIFO and LRU:
FIFO (first in first out): * item,*** eliminated by set
LRU (least recently used): recently the least used (get/set) item,*** has been eliminated
To crowd out item using the LRU algorithm, you need to add two attributes:
Recent item access count
Recent item access time
And add a LRU linked list, it can be quickly implemented.
Voiceover: so, manage every slab of chunk, in addition to free_chunk_list, there is also lru_list.
The above is the editor for you to share how to analyze the principle of the memcache kernel, if you happen to have similar doubts, you might as well refer to the above analysis to understand. If you want to know more about it, you are welcome to follow the industry information channel.
Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.
Views: 228
*The comments in the above article only represent the author's personal views and do not represent the views and positions of this website. If you have more insights, please feel free to contribute and share.
Continue with the installation of the previous hadoop.First, install zookooper1. Decompress zookoope
"Every 5-10 years, there's a rare product, a really special, very unusual product that's the most un
© 2024 shulou.com SLNews company. All rights reserved.