CN106874119A - Merging method and device based on the scanning of homogeneity internal memory - Google Patents

Abstract

The present invention relates to the technical field of memory optimization of a virtualized cluster system, in particular to a homogeneous memory scanning-based merging method and device. Aiming at the memory optimization needs of a virtualized cluster system, a virtualization technology is used to seamlessly aggregate homogeneous The invention provides a method and device for quality memory resources, and uniformly manages free memory resources in the system, providing a basis for searching for homogeneous memory globally. Including: storing the memory page in the dynamic memory pool; finding whether the memory page in the dynamic memory pool has a homogeneous memory page in the stable tree, if so, adding the memory page in the dynamic memory pool to the stable tree; if not, Then proceed to the next step; find out whether the memory pages in the dynamic memory pool have homogeneous memory pages in the unstable tree, if so, add the memory pages in the dynamic memory pool to the stable tree; The memory pages in are added to the unstable tree.

Description

Merging method and device based on homogeneous memory scanning

technical field

The invention relates to the technical field of memory optimization of a virtualized cluster system, in particular to a method and device for merging based on homogeneous memory scanning.

Background technique

The memory on each virtual machine will be completely mapped to the physical memory. Since multiple virtual machines on a server run the same operating system, there are a large number of identical memory pages in the physical memory, which is called homogeneous memory here. . In the design of modern operating systems, shared memory has become a commonly used technology. It is through this feature that we can share these homogeneous memories with multiple virtual machines. By scanning the pages in the memory, we can find the difference between different virtual machines and then merge the same memory pages. When a virtual machine needs to modify a memory page, re-apply for a memory page, copy the original page data to this memory page, and give this memory page to the memory page that needs to be changed. Page virtual machine, so as to reduce the overall memory demand, and improve resource optimization in a single server through resource reuse. We call this method "throttling".

Although the homogeneous memory sharing technology greatly saves the memory usage, in order to make full use of the resources of the server, the administrator usually puts different types of server applications, such as computing-intensive, communication-intensive, and intensive, etc., on the same server. In order to improve the utilization rate of a single server, due to the reduction of the number of homogeneous virtual machines on a single server, it will affect the use effect. At the same time, the data in the virtual machine can be divided into frequent reads and frequent writes. Therefore, some memory pages and memory data are shared indiscriminately, which leads to the frequent separation of frequently written memory pages. The overhead caused by paging is far greater than the performance improvement brought by practical homogeneous memory reuse.

Contents of the invention

In view of this, the present invention provides a method and device for merging based on homogeneous memory scanning. Aiming at the memory optimization needs of a virtualized cluster system, a method and device for seamlessly aggregating homogeneous memory resources using virtualization technology are constructed. Unified management of free memory resources in the system provides a basis for searching for homogeneous memory globally.

In order to achieve the above object, the present invention is achieved through the following technical solutions:

The present invention provides a method for merging based on homogeneous memory scanning, including: storing memory pages into a dynamic memory pool; finding whether the memory pages in the dynamic memory pool have homogeneous memory pages in the stable tree, and if so, storing the memory pages in the dynamic memory pool Add the memory pages in the pool to the stable tree; if not, go to the next step; find out whether the memory pages in the dynamic memory pool have homogeneous memory pages in the unstable tree, and if so, add the memory pages in the dynamic memory pool Add to the stable tree; if not, add the memory page in the dynamic memory pool to the unstable tree.

Further, before storing the memory page into the dynamic memory pool, it also includes: creating the dynamic memory pool.

Further, storing the memory pages into the dynamic memory pool includes: adding deduplication marks to the memory pages where read and write operations occur; and storing the memory pages with deduplication marks added into the dynamic memory pool.

Further, storing the memory page with the deduplication mark added into the dynamic memory pool includes: storing the memory page with the deduplication mark into the limited ring stack, and placing the latest stored memory page at the top of the limited ring stack.

Further, adding the memory pages in the dynamic memory pool to the unstable tree includes: calculating a hash value of the memory pages in the dynamic memory pool; adding the memory pages in the dynamic memory pool to the unstable tree.

Further, after adding the memory pages in the dynamic memory pool to the unstable tree, the method further includes: marking the memory pages added to the unstable tree as read-only.

The present invention also provides a merging device based on homogeneous memory scanning, including: a memory page storage module, used to store the memory page into the dynamic memory pool; a first search module, used to check whether the memory page in the dynamic memory pool is There are homogeneous memory pages in the stable tree; the second search module is used to find whether the memory pages in the dynamic memory pool have homogeneous memory pages in the unstable tree; the first adding module is used to use the memory pages in the dynamic memory pool The memory page is added to the stable tree; the second adding module is used to add the memory page in the dynamic memory pool to the non-stable tree.

Further, it also includes: a dynamic memory pool creating module, configured to create a dynamic memory pool.

Further, it also includes: a de-duplication identification adding module, configured to add de-duplication identifications to the memory pages where read and write operations occur.

Further, it also includes: a hash calculation module, configured to calculate the hash value of the memory page in the dynamic memory pool;

Further, it also includes: a memory page attribute change module, which is used to mark the memory pages added to the unstable tree as read-only.

The invention provides a method for merging based on homogeneous memory scanning, which has the following beneficial effects: scan memory pages out of sequence according to the reading and writing sequence to find homogeneous memory pages, and merge them into a stable tree, The object of the read operation of the virtual file system and the target of the write operation of the virtual file system are used as the main memory page of the scan, and all memory read and write prompts are captured in the dynamic memory pool, and then homogeneous memory pages are globally searched in the dynamic memory pool , can greatly increase the sharing degree of a single page, thus saving more memory pages.

The beneficial effect of the merging device based on homogeneous memory scanning is similar to that of the merging method based on homogeneous memory scanning, and will not be repeated here.

Description of drawings

FIG. 1 is a schematic flowchart of a homogeneous memory scan-based merging method provided by an embodiment of the present invention;

FIG. 2 is another implementation manner of a schematic flowchart of a homogeneous memory scanning-based merging method provided by an embodiment of the present invention;

FIG. 3 is a schematic structural diagram of a merging device based on homogeneous memory scanning provided by an embodiment of the present invention.

detailed description

In order to make the purpose, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly and completely described below in conjunction with the drawings in the embodiments of the present invention. Obviously, the described embodiments It is a part of embodiments of the present invention, but not all embodiments. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.

Exemplary embodiments of the present invention are described below in conjunction with specific circumstances:

Please refer to FIG. 1. FIG. 1 is a schematic flow diagram of a merging method based on homogeneous memory scanning provided by an embodiment of the present invention; the present invention provides a merging method based on homogeneous memory scanning, including:

Step S101, storing memory pages into a dynamic memory pool;

Step S102, check whether the memory pages in the dynamic memory pool have homogeneous memory pages in the stable tree, if so, proceed to step S103;

Step S103, adding memory pages in the dynamic memory pool to the stable tree; if not, proceed to step S104;

Step S104, check whether the memory pages in the dynamic memory pool have homogeneous memory pages in the unstable tree, if so, proceed to step S103; if not, proceed to step S105;

Step S105, adding memory pages in the dynamic memory pool to the unstable tree.

Please refer to FIG. 2. FIG. 2 is another implementation manner of a schematic flowchart of a homogeneous memory scanning-based merging method provided by an embodiment of the present invention; this embodiment provides a homogeneous memory scanning-based merging method, including:

Step S201, creating a dynamic memory pool;

Step S202, adding a deduplication flag for the memory page where the read/write operation occurs;

Step S203, storing the memory page with the deduplication flag added into the dynamic memory pool;

In this embodiment, the memory page with the deduplication mark added is stored in the limited ring stack, and the latest stored memory page is placed on the uppermost layer of the limited ring stack.

Step S204, check whether the memory pages in the dynamic memory pool have homogeneous memory pages in the stable tree, if so, proceed to step S205;

Step S205, adding memory pages in the dynamic memory pool to the stable tree; if not, proceed to step S206;

Step S206, find out whether the memory pages in the dynamic memory pool have homogeneous memory pages in the unstable tree, if so, proceed to step S205; if not, proceed to step S207;

Step S207, calculating the hash value of the memory page in the dynamic memory pool;

Step S208, adding memory pages in the dynamic memory pool to the unstable tree;

Step S209, marking the memory pages added to the unstable tree as read-only;

It is worth noting that the original KSM processing flow can be explained from the following KSM principle: KSM is KernelSamePage Merging, also known as a kernel module, KSM as a daemon process in the kernel regularly performs page scanning to identify duplicate pages And merge the copy, freeing these pages for other use. The process of performing the above operations is transparent to the user. For example, duplicate pages are merged (and then marked read-only), but if one of the users of this page changes the page for some reason, that user will receive their own duplicate.

KSM uses a different approach than that used in memory de-affinity. In traditional deweighting, objects are hashed, and the hash value is then used for an initial similarity check. When the hash values agree, the next step is to do an actual object comparison to formally determine whether the objects agree. KSM took this approach in its first implementation, but later developed a more intuitive approach to simplify it. It should be pointed out that KSM relies on the upper-layer application interface to provide the scanned memory area. Although KSM can scan all memory pages in the system, due to the relatively large memory capacity, it takes a lot of time and consumes a lot of computing resources to completely scan the memory area. . Therefore, Linux provides a registration function for the application program, allowing the application program to register the memory space that it wants to merge with the operating system through this interface. This interface function is:

#include <sys/mman.h>

int madvise(void * start, size_t length, int advise)

In the current KSM, pages are managed through two "red-black" trees, one of which is temporary. The first tree is called the unstable tree and is used to store new pages that are not yet understood to be stable. In other words, pages that are merge candidates are stored in this unstable tree. Pages in an unstable tree are not write-protected. The second tree, called the stable tree, stores pages that have been found to be stable and merged by KSM. To determine whether a page is stable, KSM uses a simple 32-bit checksum. When a page is scanned, its checksum is calculated and stored with the page. On a subsequent scan, if the newly calculated checksum is not equal to the previously calculated checksum, the page is changing and therefore is not a good candidate for a merge. Since the data structure of these two trees is a red-black tree, the time complexity of inserting and deleting into this tree is O(logn).

When KSM processes a single page, the first step is to check whether the page can be found in the stable tree. A memcmp (memory compare) operation will be performed on this page and the page of the associated node. If memcmp returns 0, the pages are the same and a match was found. Conversely, if it returns -1, it means that the candidate page is smaller than the page of the current node. If it returns 1, it means that the candidate page is larger than the page of the current node. Although comparing 4K pages may seem like a pretty heavyweight comparison, in most cases memcmp will end early once differences are found.

The method described in this embodiment is based on the extension of the native KSM homogeneous memory merge processing flow, and the specific operation method combined with the native KSM processing flow can be explained from the following three aspects:

In the method described in this embodiment, the memory pages added with deduplication hints are inserted into the unstable tree. After that, every time there is a read and write operation on the memory page, the operation target page will be searched in the unstable tree. At the same time, in order to prevent the pages in the unstable tree from being modified, all the pages in it must be marked as read-only mode. When writing is required, the page is removed from the unstable tree, and then reinserted into the unstable tree.

1. Acquisition of the de-duplication logo: According to the introduction to KSM, the scanning range is specified by the system call madvise. In order to realize our function, this system call must be extended. Since most of the shared memory pages come from the virtual disk image, it is also necessary to modify the read commands (read, readv) and write (write, writev) commands of the virtual file system, so that these functions can be added to these pages by the way when they are called. On the corresponding read-write mark, this mark is used as a reminder for deduplication. However, the memory pages for adding read-write marks here must be defined in the system call madvise.

2. Storage of deduplication marks: Since I/O in computers is often provocative, deduplication marks based on I/O are also provocative. When the I/O speed is greater than the scanning rate of KSM, the system may not be able to save a large number of deduplication marks. According to the processing of such ordered information in most systems, an infinite buffer queue is often used to save, but this method is not practical in this system, because we cannot predict the number of I/O, and at the same time, due to the recording of these pages The identification has a certain timeliness. With our processing, the identification at the end of the queue may be aging (when a memory page is not processed in time after being identified, and the memory page is read or written at this time, this It should be said that the identification is aging) and has no practical significance. At this time, it is not only a waste of time to process these identifications, but it may also delay the processing time of subsequent identifications after this identification, further increasing the possibility of these identifications becoming invalid. The direct consequence of doing this is that it may make it impossible to find any candidate merge pages in the end.

Since in the system, it is not necessary to find all shareable homogeneous memory pages in one scan, we propose a new identity storage method: limited ring stack. This approach requires very little overhead and is basically maintenance-free.

In the finite circular stack, the system always fetches these identifiers from top when processing them, which means that each time it processes the latest deduplication identifier memory page, according to our above analysis, the latest is pushed into the stack The memory pages are often the most likely to be shared, and for those memory pages identified at the bottom of the stack, the timeliness may not have any meaning, so when these pages are processed, it means that there are no newly identified memory pages in the system , Even if these useless flags are processed at this time, it will not bring additional pressure to the system. If there are too many marked memory pages, only those useless marks at the bottom of the stack will be deleted. According to our previous analysis, the system does not need to find all the shared memory pages in the process of processing again, and these marks may no longer be meaningful , in this way we can achieve our goal effectively and simply. Since this is just a normal finite ring stack, no additional maintenance is required.

3. Processing of deduplication identification: It needs to be specially pointed out here that although we have proposed a deduplication mechanism based on I/0 identification, it does not mean that we do not need the original deduplication mechanism. The deduplication mechanism based on the I/0 access identifier is mainly for those memory pages that have a relatively short sharing time and have I/0 behaviors, and for those memory pages that basically have no I/0 behaviors, this method cannot find other memory pages. share opportunities. According to the mechanism of adding deduplication identifiers to memory pages, the system needs to expand the original KSM processing method, and the new processing flow is similar to the original KSM processing flow.

Mix this mechanism with the original KSM. When there is data in the limited ring stack, use the KSM deduplication method based on the I/O deduplication flag first, otherwise consider the native KSM method. At the same time, the hybrid mechanism also periodically scans the memory space registered by madvise.

In this method, we first check whether the marked memory page is already included in the stable tree, and if so, change the physical address in the page table in the memory pool to the page address in the stable tree, and then release the original memory page; If it is not in the stable tree, first calculate the size of the memory page, and check it in the unstable tree, if it exists in the unstable tree, merge the two pages, and insert one of them into the stable tree, if in the unstable tree If it is not found in the unstable tree, the memory page is inserted into the unstable tree.

Degeneration of unstable tree: In the native KSM implementation, those memory pages that are frequently written are excluded from the unstable tree. The advantage of this is to avoid repeated searches for these pages, because the hash value calculated each time is different, and the same They are also not merged, and only those pages whose hashes remain the same between scans are inserted into the unstable tree. However, in our implementation, when a memory page has a deduplication flag, the page is inserted into the unstable tree.

Those memory pages associated with virtual DMA read and write operations are usually considered part of the cache in the guest operating system. For the application program running in the Guest os, if the internal buffer of the virtual machine is filled, the unstable tree in the Host os is bound to degenerate. This is because in this case, even if the cache is not cleared by the Host os, the Guest os will delete the entire buffers originating from the virtual disk image to rebuild a new buffer space. At this time, all marked memory pages in the unstable tree will be modified, and the unstable tree will become unreachable to the outside world. In addition, when an internal node of an unstable tree changes, all sibling nodes at the same level are also unreachable. This is also the only thing the Host os can know after the Guest os writes these modified pages to the virtual disk. KSM's Unstable Tree autohealer repair speed is reduced due to the increased number of memory pages per full scan. If the frequency of scanning remains constant, then a page can be multi-marked due to previous releases. Therefore, in order to cope with the degradation of unstable trees, an effective solution is to mark pages inserted into unstable trees as read-only. In this case, when a memory page on the unstable tree is written, the memory page will be deleted from the unstable tree due to a write error.

The present invention also provides a merging device based on homogeneous memory scanning, including:

The memory page is stored in the module, which is used to store the memory page into the dynamic memory pool;

The first search module is used to find whether the memory pages in the dynamic memory pool have homogeneous memory pages in the stable tree;

The second search module is used to find whether the memory pages in the dynamic memory pool have homogeneous memory pages in the unstable tree;

The first adding module is used to add memory pages in the dynamic memory pool to the stable tree;

The second adding module is used to add memory pages in the dynamic memory pool to the unstable tree.

Please refer to FIG. 3. FIG. 3 is a schematic structural diagram of a merging device based on homogeneous memory scanning provided by an embodiment of the present invention; in this embodiment, a merging device based on homogeneous memory scanning includes:

The memory page is stored in the module 301, which is used to store the memory page into the dynamic memory pool;

The first search module 302 is used to find whether the memory pages in the dynamic memory pool have homogeneous memory pages in the stable tree;

The second search module 303 is used to find whether the memory pages in the dynamic memory pool have homogeneous memory pages in the unstable tree;

A first adding module 304, configured to add memory pages in the dynamic memory pool to the stable tree;

The second adding module 305 is used to add memory pages in the dynamic memory pool to the unstable tree;

A dynamic memory pool creation module 306, configured to create a dynamic memory pool.

The de-duplication identification adding module 307 is configured to add de-duplication identifications to memory pages where read and write operations occur.

Hash calculation module 308, for calculating the hash value of the memory page in the dynamic memory pool;

A memory page attribute changing module 309, configured to mark the memory pages added to the unstable tree as read-only.

Finally, it should also be noted that in this text, relational terms such as first and second etc. are only used to distinguish one entity or operation from another, and do not necessarily require or imply that these entities or operations, any such actual relationship or order exists. Furthermore, the term "comprises", "comprises" or any other variation thereof is intended to cover a non-exclusive inclusion such that a process, method, article, or apparatus comprising a set of elements includes not only those elements, but also includes elements not expressly listed. other elements of or also include elements inherent in such a process, method, article, or device. Without further limitations, an element defined by the phrase "comprising a ..." does not exclude the presence of additional identical elements in the process, method, article or apparatus comprising said element.

The above is a detailed introduction to a high-density server hard disk backplane provided by the present invention. In this paper, specific examples are used to illustrate the principle and implementation of the present invention. The description of the above embodiments is only used to help understand the method of the present invention. and its core idea; at the same time, for those of ordinary skill in the art, according to the idea of the present invention, there will be changes in the specific implementation and scope of application. limits.

Claims (10)

1. A method for merging based on homogeneous memory scanning, characterized in that, comprising: Depositing the memory page in the dynamic memory pool; Finding whether the memory page in the dynamic memory pool has a homogeneous memory page in the stable tree, if so, then Add the memory pages in the dynamic memory pool to the stable tree; if not, proceed to the next step; find out whether the memory pages in the dynamic memory pool have homogeneous memory pages in the unstable tree, and if so, add them to the dynamic memory pool The memory pages in the dynamic memory pool are added to the stable tree; if not, the memory pages in the dynamic memory pool are added to the unstable tree. 2. The merging method based on homogeneous memory scanning according to claim 1, further comprising: creating a dynamic memory pool before storing the memory pages into the dynamic memory pool. 3. the merging method based on homogeneous memory scan according to claim 1, is characterized in that, memory page is stored in dynamic memory pool, comprises: For the memory page that read and write operation takes place, add deduplication mark; The relabeled memory pages are stored in the dynamic memory pool. 4. the merging method based on homogeneous memory scanning according to claim 3, is characterized in that, depositing the memory page that has added deduplication mark into dynamic memory pool, comprises: Depositing the memory page that has added deduplication mark into Finite circular stack, the uppermost layer of the limited circular stack places the latest stored memory page. 5. the merging method based on homogeneous memory scanning according to claim 1, is characterized in that, the memory page in the dynamic memory pool is added in the unstable tree, comprising: calculating the hash of the memory page in the dynamic memory pool Value; Add memory pages from the dynamic memory pool to the non-stable tree. 6. the merging method based on homogeneous memory scan according to claim 1, is characterized in that, after the memory page in the dynamic memory pool is added in the unstable tree, also comprises: Adding the memory page in the unstable tree The page is marked as read-only. 7. A merging device based on homogeneous memory scanning, characterized in that it comprises: a memory page storage module, which is used to store memory pages into a dynamic memory pool; a first search module, which is used to search for memory in the dynamic memory pool Whether the page has a homogeneous memory page in the stable tree; the second search module is used to find whether the memory page in the dynamic memory pool has a homogeneous memory page in the unstable tree; the first adding module is used to add the dynamic memory pool The memory pages in the memory pool are added to the stable tree; the second adding module is used to add the memory pages in the dynamic memory pool to the unstable tree. 8. The homogeneous memory scanning-based merging device according to claim 7, further comprising: a dynamic memory pool creation module, configured to create a dynamic memory pool. 9. The merging device based on homogeneous memory scanning according to claim 7, further comprising: a deduplication mark adding module, configured to add a deduplication mark to a memory page where a read/write operation occurs. 10. The merging device based on homogeneous memory scanning according to claim 7, further comprising: a hash calculation module, configured to calculate the hash value of the memory page in the dynamic memory pool; preferably, also comprising : A memory page attribute change module that marks memory pages added to the unstable tree as read-only.