CN106469121B - Method and device for allocating memory - Google Patents

Abstract

The invention discloses a memory allocation method and device. By acquiring the information of each slab class; calculating the influence factor of each slab class according to the preset minimum influence factor selection algorithm and the information; and assigning the slab with the smallest influence factor The class is selected as the source slab class, and the slab with the largest number of swapped out within a period of time is set as the destination slab; the memory of a slab in the source slab class is cleared and redistributed to the destination slab, and the minimum impact factor selection algorithm is proposed , comprehensively consider the characteristics of stored data in the case of compression, reasonably select the appropriate source slab class and destination slab for recycling and reallocation; adjust the memory allocation mechanism of Memcached, and effectively divide the area according to the slab storage status empty, full, etc., when When memory is needed, it starts recycling from the free slab at the end.

Description

Method and device for allocating memory

technical field

Embodiments of the present invention relate to the technical field of memory allocation, and in particular, to a memory allocation method and device.

Background technique

Memcached allocates memory to the corresponding slab class according to the size of the requested object. Once all the available memory in Memcached is allocated, the problem arises when the memory is redistributed due to changes in the distribution of requests, which is referred to as the Calcification problem (Calcification). Changing external requests are dynamically adjusted. If the size distribution of the objects that Memcached needs to store does not change over time, then the calcification problem will not affect the performance of Memcached, because the basic swapping strategy implemented in Memcached can well guarantee the storage of hot objects. However, if the size distribution of storage objects changes at any time, the calcification problem has a greater impact on the hit rate of Memcached.

The direct way to solve the Memcached calcification problem is to allow Memcached to reclaim and reallocate the allocated memory to the required slab classes. Data compression exacerbates Memcached's calcification problem. When Memcached starts the data compression function, not only the space left in the compressed slab class cannot be returned to Memcached, but also it will cause greater pressure on the compressed slab class. In Memcached with the data compression function added, although data compression brings different performance improvement effects to Memcached, it also exacerbates the calcification problem of Memcached.

Contents of the invention

The purpose of the embodiments of the present invention is to provide a method and device for memory allocation, aiming at solving the problem of calcification in Memcached with added data compression function.

To achieve this purpose, the embodiments of the present invention adopt the following technical solutions:

In a first aspect, a method for memory allocation, the method comprising:

Obtain the information of each slab class, the information including the number of used objects, the number of requests, the total number of objects and the number of swapped out;

Calculate the impact factor of each slab class according to the preset minimum impact factor selection algorithm and the information;

Select the slab class with the smallest impact factor as the source slab class, and set the slab with the largest number of swaps out within a period of time as the destination slab;

A slab memory in the source slab class is emptied and recovered and then redistributed to the target slab.

Preferably, the calculation of the impact factor of each slab class according to the preset minimum impact factor selection algorithm and the information includes:

Wherein, the used_chunks represents the number of used objects in the specific slab class, the request represents the number of requests in the specific slab class within a period of time, and the total_chunks represents the total number of objects in the specific slab class.

Preferably, the redistribution to the destination slab after emptying and reclaiming a slab memory in the source slab class includes:

Obtain the slab with the largest amount of free space in the source slab class;

Empty the slab memory with the largest amount of free space in the source slab class, reclaim the emptied memory and redistribute it to the destination slab.

Preferably, the method also includes:

The used space and unused space in Memcached are treated differently, the used area is concentrated on the front end of the slab, and the unused area is concentrated on the back end of the slab.

Preferably, the method also includes:

The front end of each slab in each slab class is provided with three pointers for specifying the scope of the slab, and the three pointers include the pointer slab_start for identifying the first storage object in the slab, and the pointer slab_start for identifying the first storage object in the slab. The pointer slab_end of the last storage object and the pointer cur_free used to identify the currently available storage object in the slab.

In a second aspect, a memory allocation device is characterized in that the device includes:

An acquisition module, configured to acquire the information of each slab class, said information including the number of objects used, the number of requests, the total number of objects and the number of swapped out;

A selection module, configured to calculate the impact factor of each slab class according to a preset minimum impact factor selection algorithm and the information;

The selection module is used to select the slab class with the smallest impact factor as the source slab class, and set the slab with the largest number of swaps out within a period of time as the destination slab;

An allocating module, configured to clear and recover a slab memory in the source slab class and redistribute it to the target slab.

Preferably, the selection module includes:

Wherein, the used_chunks represents the number of used objects in the specific slab class, the request represents the number of requests in the specific slab class within a period of time, and the total_chunks represents the total number of objects in the specific slab class.

Preferably, the allocation module is used for:

Obtain the slab with the largest amount of free space in the source slab class;

Empty the slab memory with the largest amount of free space in the source slab class, reclaim the emptied memory and redistribute it to the destination slab.

Preferably, the device also includes:

The adjustment module is used to treat the used space and the unused space in Memcached differently, concentrate the used area on the front end of the slab, and concentrate the unused area on the back end of the slab.

Preferably, the device also includes:

The module is set, and the front end of each slab in each slab class is provided with three pointers for specifying the scope of the slab, and the three pointers include the pointer slab_start for identifying the first storage object in the slab, for A pointer slab_end for identifying the last storage object in the slab, and a pointer cur_free for identifying the currently available storage object in the slab.

Embodiments of the present invention provide a method and device for memory allocation. The method obtains information of each slab class, the information including the number of used objects, the number of requests, the total number of objects, and the number of swapped out; according to the preset minimum The impact factor selection algorithm and the information calculate the impact factor of each slab class; the slab class with the smallest impact factor is selected as the source slab class, and the slab with the largest number of swapped out in the period of time is set as the destination slab; the described A slab memory in the source slab class is emptied and redistributed to the target slab after being emptied and reclaimed. A minimum impact factor selection algorithm is proposed, and the characteristics of the stored data under compression are considered comprehensively, and the appropriate source slab class and target slab are reasonably selected for recycling and Reallocate; adjust the memory allocation mechanism of Memcached, effectively divide the area according to the slab storage status empty, full, etc., and start recycling from the idle slab at the end when memory is needed.

Description of drawings

FIG. 1 is a schematic flowchart of a memory allocation method provided by an embodiment of the present invention;

FIG. 2 is another schematic flowchart of a memory allocation method provided by an embodiment of the present invention;

Fig. 3 is a schematic diagram of a space allocation method provided by an embodiment of the present invention;

Fig. 4 is a schematic diagram of another space allocation method provided by an embodiment of the present invention;

FIG. 5 is a schematic diagram of a memory allocation pointer structure provided by an embodiment of the present invention;

FIG. 6 is a schematic diagram of a comparison of calcification before and after memory allocation provided by an embodiment of the present invention;

FIG. 7 is a schematic diagram of functional modules of a device for memory allocation provided by an embodiment of the present invention.

Detailed ways

The embodiments of the present invention will be further described in detail below in conjunction with the drawings and embodiments. It should be understood that the specific embodiments described here are only used to explain the embodiments of the present invention, rather than to limit the embodiments of the present invention. In addition, it should be noted that, for the convenience of description, the drawings only show some but not all structures related to the embodiments of the present invention.

Referring to FIG. 1 , FIG. 1 is a schematic flowchart of a memory allocation method provided by an embodiment of the present invention.

In Fig. 1, the method of memory allocation includes:

Step 101, obtaining the information of each slab class, said information including the number of objects used, the number of requests, the total number of objects and the number of swapped out;

Specifically, due to the addition of a data compression function in Memcached, data characteristics of objects stored in Memcached have changed. From the perspective of compression quantity, request quantity and total number of objects, a minimum impact factor selection algorithm is proposed. Impact factor (IF) is an index obtained by combining the impact of the number of compressions, the number of requests, and the total number of objects on the slab recovery process.

Step 102, calculating the impact factor of each slab class according to the preset minimum impact factor selection algorithm and the information;

Preferably, the calculation of the impact factor of each slab class according to the preset minimum impact factor selection algorithm and the information includes:

Wherein, the used_chunks represents the number of used objects in the specific slab class, the request represents the number of requests in the specific slab class within a period of time, and the total_chunks represents the total number of objects in the specific slab class.

Specifically, the smaller the impact factor, the more suitable the slab is to provide memory as the source slab class.

Step 103, selecting the slab class with the smallest impact factor as the source slab class, and setting the slab with the largest number of swaps out within a period of time as the destination slab;

Specifically, the number of used objects, the number of requests, the total number of objects, and the number of swapped out objects of each slab class are collected. Calculate the impact factor for each slab class, and select a slab class with the smallest impact factor as the source slab class. Select the slab class with the largest number (frequently) swapped out from the slab classes as the destination slab.

Step 104, emptying and reclaiming a slab memory in the source slab class and reallocating it to the destination slab.

Preferably, the redistribution to the destination slab after emptying and reclaiming a slab memory in the source slab class includes:

Obtain the slab with the largest amount of free space in the source slab class;

Empty the slab memory with the largest amount of free space in the source slab class, reclaim the emptied memory and redistribute it to the destination slab.

Wherein, the memory space is a memory with a fixed size of 1M.

Specifically, refer to FIG. 2 , which is another schematic flowchart of a method for memory allocation provided by an embodiment of the present invention.

Step 201, if it is judged that the slab needs to be recovered and redistributed, then select the source slab class;

Step 202, select the target slab;

Step 203, judging whether to perform slab recovery and reallocation;

Step 204, if it is judged that the slab does not need to be reclaimed and redistributed, then it is judged whether the selected slab class is valid;

Step 205, if the selected slab class is valid, perform slab recovery and reallocation.

Preferably, the method also includes:

The used space and unused space in Memcached are treated differently, the used area is concentrated on the front end of the slab, and the unused area is concentrated on the back end of the slab.

Specifically, the space already used by Memcached in Figure 3 is treated differently from the free space, that is, the occupied area is concentrated at the front end of the slab and the free area is concentrated at the back end of the slab. When a calcification problem occurs, memory recovery and reallocation are given priority to the backend area.

Figure 4 is a schematic diagram of the modified Memcached slab allocator, which not only concentrates the occupied area on the front end, but also makes the pointers between the slabs more regular, which is conducive to the disconnection of the linked list when reclaiming memory. When Memcached reclaims memory, it will clear the objects stored in the selected slab and re-segment them into small blocks of other sizes. The operation of clearing objects will affect the hit rate of Memcached to a certain extent. Using the slab allocator structure shown in Figure 4 can reduce this effect.

Preferably, the method also includes:

The front end of each slab in each slab class is provided with three pointers for specifying the scope of the slab, and the three pointers include the pointer slab_start for identifying the first storage object in the slab, and the pointer slab_start for identifying the first storage object in the slab. The pointer slab_end of the last storage object and the pointer cur_free used to identify the currently available storage object in the slab.

Specifically, refer to FIG. 5 , which is a schematic diagram of a memory allocation pointer structure provided by an embodiment of the present invention. Figure 5 shows the specific modification method. In addition to adding three pointers as shown in the figure in the slab structure, it is also necessary to add corresponding processing codes in the memory allocation function.

Referring to FIG. 6 , FIG. 6 is a schematic diagram of a comparison of calcification before and after memory allocation provided by an embodiment of the present invention. The gray dotted line in Figure 6 is the experimental effect, from which it can be seen that the hit rate improvement under the calcification problem has been significantly improved from the transition from request type A to request type B. This scheme effectively improves Memcached's compression by calcification The problem that caused the hit rate to drop. The gray curve is the hit rate curve of Memcached affected by calcification under compression.

The embodiment of the present invention provides a method for memory allocation, the method obtains the information of each slab class, the information includes the number of used objects, the number of requests, the total number of objects and the number of swapped out; according to the preset minimum impact factor Selection algorithm and the influence factor of each slab class are calculated by the information; the slab class with the smallest influence factor is selected as the source slab class, and the slab with the largest number of swapped out in the period of time is set as the destination slab; the source slab A slab memory in a class is emptied and re-allocated to the target slab, and a minimum impact factor selection algorithm is proposed, comprehensively considering the characteristics of the stored data under compression, and reasonably selecting the appropriate source slab class and target slab for recycling and re-allocation ;Adjust the memory allocation mechanism of Memcached, effectively divide the area according to the slab storage status empty, full, etc., and start recycling from the idle slab at the end when memory is needed.

Referring to FIG. 7 , FIG. 7 is a schematic diagram of functional modules of a device for memory allocation provided by an embodiment of the present invention.

In Figure 7, the memory allocation means include:

Obtaining module 701, is used for obtaining the information of each slab class, and described information comprises used object quantity, request quantity, object total number and exchanged out quantity;

Selection module 702, for calculating the impact factor of each slab class according to the preset minimum impact factor selection algorithm and the information;

Preferably, the selection module 702 includes:

Wherein, the used_chunks represents the number of used objects in the specific slab class, the request represents the number of requests in the specific slab class within a period of time, and the total_chunks represents the total number of objects in the specific slab class.

The selection module 703 is used to select the slab class with the smallest impact factor as the source slab class, and set the slab with the largest number of swaps in a period of time as the destination slab;

The allocating module 704 is configured to clear and reclaim a slab memory in the source slab class and then reallocate it to the target slab.

Preferably, the allocation module 704 is configured to:

Obtain the slab with the largest amount of free space in the source slab class;

Empty the slab memory with the largest amount of free space in the source slab class, reclaim the emptied memory and redistribute it to the destination slab.

Preferably, the device also includes:

The adjustment module is used to treat the used space and the unused space in Memcached differently, concentrate the used area on the front end of the slab, and concentrate the unused area on the back end of the slab.

Preferably, the device also includes:

Setting module is used to set three pointers for specifying the scope of the slab at the front end of each slab in each slab class, and the three pointers include pointers slab_start, the first storage object used to identify the slab The pointer slab_end used to identify the last storage object in the slab, and the pointer cur_free used to identify the currently available storage object in the slab.

The embodiment of the present invention provides a device for memory allocation, by obtaining the information of each slab class, the information includes the number of used objects, the number of requests, the total number of objects and the number of swapped out; according to the preset minimum impact factor selection algorithm and The information calculates the impact factor of each slab class; the slab class with the smallest impact factor is selected as the source slab class, and the slab with the largest number of swapped out in the period of time is set as the destination slab; the source slab class in the A slab memory is emptied and redistributed to the target slab after being reclaimed, and a minimum impact factor selection algorithm is proposed to comprehensively consider the characteristics of the stored data under compression, and reasonably select the appropriate source slab class and destination slab for recycling and redistribution; adjust Memcached The memory allocation mechanism effectively divides the area according to the slab storage status empty, full, etc. When the memory is needed, it starts to recycle from the idle slab at the end.

The above describes the technical principles of the embodiments of the present invention in conjunction with specific embodiments. These descriptions are only for explaining the principles of the embodiments of the present invention, and cannot be construed as limiting the protection scope of the embodiments of the present invention in any way. Based on the explanations herein, those skilled in the art can think of other specific implementation manners of the embodiments of the present invention without creative work, and these manners will fall within the protection scope of the embodiments of the present invention.

Claims (8)

1. A method of memory allocation, the method comprising:

acquiring information of each slab class in Memcached with a data compression function, wherein the information comprises the number of used objects, the number of requests, the total number of the objects and the number of swapped-out objects;

Calculating the influence factor of each slab class according to a preset minimum influence factor selection algorithm and the used object number, the request number and the total number of the objects in the information; the number of used objects is associated with a number of compressions; the minimum impact factor selection algorithm is represented as follows:

Wherein the used _ chunks represents the number of used objects, the request represents the number of requests, and the total _ chunks represents the total number of objects;

Selecting the slab class with the smallest influence factor as a source slab class, and setting the slab with the largest quantity exchanged within a period of time as a target slab;

And clearing and recycling one slab memory in the source slab class and then redistributing the cleared slab memory to the target slab.

2. The method of claim 1, wherein said deallocating said one of said source slab class to said destination slab after flushing and reclaiming said one of said slab class comprises:

Obtaining the slab with the largest amount of free space in the source slab class;

and emptying the slab memory with the largest quantity of free space in the source slab class, and recycling and redistributing the emptied memory to the target slab.

3. the method according to any one of claims 1 to 2, further comprising:

and (3) the used space and the unused space in Memcached are treated differently, the used area is concentrated at the front end of the slab, and the unused area is concentrated at the rear end of the slab.

4. The method according to any one of claims 1 to 2, further comprising:

and setting three pointers for specifying the range of each slab in each slab class, wherein the three pointers comprise a pointer slab _ start for identifying a first storage object in the slab, a pointer slab _ end for identifying a last storage object in the slab, and a pointer cur _ free for identifying a currently available storage object in the slab.

5. An apparatus for memory allocation, the apparatus comprising:

the device comprises an acquisition module, a processing module and a processing module, wherein the acquisition module is used for acquiring information of each slab class in Memcached with a data compression function, and the information comprises the number of used objects, the number of requests, the total number of objects and the number of swapped-out objects;

The selection module is used for calculating the influence factor of each slab class according to a preset minimum influence factor selection algorithm and the used object number, the request number and the total number of the objects in the information; the number of used objects is associated with a number of compressions; the minimum impact factor selection algorithm is represented as follows:

Wherein the used _ chunks represents the number of used objects, the request represents the number of requests, and the total _ chunks represents the total number of objects;

The selecting module is used for selecting the slab class with the smallest influence factor as a source slab class and setting the slab with the largest quantity exchanged within a period of time as a target slab class;

and the allocation module is used for emptying and recycling one slab memory in the source slab class and then reallocating the slab memory to the target slab.

6. the apparatus of claim 5, wherein the assignment module is configured to:

obtaining the slab with the largest amount of free space in the source slab class;

and emptying the slab memory with the largest quantity of free space in the source slab class, and recovering and redistributing the emptied memory to the target slab.

7. The apparatus of any one of claims 5 to 6, further comprising:

And the adjusting module is used for distinguishing and treating used space and unused space in Memcached, concentrating the used area at the front end of the slab, and concentrating the unused area at the rear end of the slab.

8. the apparatus of any one of claims 5 to 6, further comprising:

And the setting module is used for setting three pointers for specifying the range of each slab in each slab class, wherein the three pointers comprise a pointer slab _ start used for identifying a first storage object in the slab, a pointer slab _ end used for identifying a last storage object in the slab, and a pointer cur _ free used for identifying a currently available storage object in the slab.