takeaway

The size of a sort field also affects sorting performance. I was left with one question:

SELECT * FROM user WHERE user_name LIKE "%am%" AND age > = 18 AND age < = 24 AND sex = 0 ORDER BY age, user_name LIMIT 0.50
Copy the code

Mysql > select * from ‘age’; mysql > select * from ‘username’;

You may have found that this SQL in fact just want to get them before 50 sorted users, however, the execution of 1000 records in a table is indeed, if I only 50 record sorting, ensure this article 50 record is sorted before 50, from the point of sorting algorithm, is at the expense of the smaller? So, how do we sort only 50 records, and at the same time, those 50 records are the first 50 records to be sorted?

As those of you who have studied sorting algorithms might have guessed, heap sort! Yes, MySQL5.6 introduced a new sorting algorithm called priority queue sorting, which uses heap sorting to ensure that only a finite number of n records are sorted, and that the result of sorting is the first n records.

Heap sorting, computer related students should be more familiar with, here, I will not elaborate on.

PTMalloc

Here, I mainly combine with “What is the best time to divide tables when the data size of a single table reaches?” By default, MySQL uses the PTmalloc allocator to allocate memory to a process.

The data structure

So let’s first look at the data structure ptmalloc uses to manage memory blocks:

Distribution area

Ptmalloc uses one primary allocation and multiple dynamic allocation to manage memory. Primary and non-primary allocation are managed using a circular linked list. For example, the Main Arena in the figure above represents a Main allocation area, and the Dynamic Arena represents three Dynamic allocation areas, which are connected at the end to form a ring shape. Ptmalloc dynamically increases the number of non-primary extents based on the amount of contention the system has for the allocated area, and once the number of allocated extents increases, it does not decrease.

In “What is the best time to separate tables when the data size of a single table reaches?” Part of the memory allocation, I talked about memory allocator no can allocate memory in ourselves, it will apply to the Linux system memory, can apply for heap memory, also can apply for to the memory of file mapping area, so, for ptmalloc, the main distribution area can apply for to heap memory, and file mapping dynamically allocate memory area can only apply for file mapping area.

When a thread needs to malloc () allocates memory space, the line first to check the thread already exists in private variables a distribution area, if there is, to try to lock the distribution area, if the lock is successful, the use of the assigned area allocated memory, if it fails, the thread search circular linked list to try to get a no lock distribution area. If all allocations are already locked, malloc() creates a new allocation, adds it to the global allocation loop and locks it, and then uses the allocation for memory operations. In a free operation, the thread also attempts to acquire the lock on the allocated area of the memory block to be freed. If the allocated area is being used by another thread, the thread must wait until the mutex of the allocated area is released by another thread.

chunk

Ptmalloc will uniformly manage the free memory blocks in the allocation area. When the user makes the next allocation request, PTMALloc will first try to select a free memory block for the user, so as to avoid frequent system calls and reduce the overhead of memory allocation. The memory blocks in question are the blocks in the picture above connected vertically by two-way arrows, called chunks, which are connected to each other in a two-way linked list. The heads of each linked list comprise an array of bins, which are the horizontal squares of the diagram. Bins are grouped into four types:

  1. Small bins: As shown in the figure above, the first 64 bins in the array numbered from 2 are called Small bins, and the chunks in the same small bin have the same size. The chunk size difference between two adjacent Small bin nodes is 8bytes. Small bins of chunks are arranged in order of most recent use, with the last released chunk being linked to the head of the linked list and chunks being applied from the bottom, so that each chunk has an equal chance of being selected by PTmalloc.
  2. Bins large: As shown above, the bins after small bins are called large bins. Each bin in large bins contains chunks in a given range, arranged in order of size. Chunks of the same size are also listed in order of most recent use.

When the chunk is released and linked to the bin, ptMALloc sets the flag P to 0 indicating whether the chunk is in use (note that the flag is actually in the next chunk), At the same time, PTMALloc will also check whether the chunks before and after it are also free. If so, PTmalloc will first merge them into a large chunk and then put the merged chunk into unstored bin. Note that not all chunks are immediately released into the bin. This leads us to the third type of bin: unsorted bin.

  1. Unsorted Bins: Unsorted bins uses the first of the bins array as shown in the header above.

As mentioned above, when the allocator merges several adjacent small chunks, it may immediately have another request for a small chunk of memory, so the allocator needs to split another chunk from the large free memory. Isn’t this inefficient?

Ptmalloc therefore introduced fast bins in the allocation process to solve this problem. Thus, number 4 bins:

  1. Fast bins: When chunks not larger than max_FAST (default: 64B) are released, they are first placed in fast bins, which do not change their usage flag P. Bins are then allocated to users with chunks less than or equal to max_FAST, and ptMALloc will first look for the corresponding free chunks in fast before looking for the free chunks in the bins. In this way, user processes that request small memory allocations can be fetched directly from Fast bins, instead of having to split large chunks.

Sort_buffer uses the PTMALloc memory allocator to apply for memory from the Linux kernel. Since PTMALloc locks the allocation area when allocating memory, the contention for lock under high concurrency is more intense, PTMALloc has to create more allocation area for the process. Since the allocation area does not release memory for a long time, As a result, the number of chunks in ptmalloc cache grows faster, resulting in memory explosion and even overflow. For database MySQL the mass data storage is not acceptable, because if the high concurrency scenarios, MySQL continuously create more and more assigned district to cache more data, then, certainly will soon run out of memory resources, memory is exhausted, had to be more data to disk, at this point, the efficiency of data query will significantly decline. So, what is the solution to this problem?

Remember my article “What is the best time to split tables?” The TCMALloc memory allocator is mentioned in this section, as you might have guessed, yes! Replace ptMALloc with TCMALloc. Let’s start with the data structure used by TCMALloc and explain how it can solve the problem of lock contention.

TCMalloc

The data structure

Here is the data structure used by TCMALloc:

Tcmalloc mainly consists of the following parts:

The size of the class: TCMalloc divides 85 classes into Size classes for small objects up to 256KB, which is called Size Class. Each Size Class corresponds to a Size, such as 8 bytes, 16 bytes, 32 bytes. When an application requests memory, TCMalloc will first round up the requested memory size to the size of the size class. For example, 8 bytes will be allocated for the memory between 1 and 8 bytes, 16 bytes will be allocated for the memory between 9 and 16 bytes, and so on. See the size class section in the figure above. By rounding, we find that if the requested memory is smaller than the size class, internal fragmentation will be generated after rounding. For example, IF I want to apply for 4 bytes of memory, I am allocated 8 bytes. If all subsequent requests exceed 4 bytes, the remaining 4 bytes are fragmented. TCMalloc keeps internal debris within 12.5% here.

ThreadCache: TCMalloc stores a separate Cache for each Thread, called ThreadCache. Each ThreadCache has a separate FreeList for each size class, which caches n free objects that are not yet used by the application.

As shown in the figure above, there are n threads with one Cache for each Thread. Thread Cache0 ~ Thread Cache N. Size class0 ~ size class n

Since ThreadCache is one per thread, memory can be fetched or reclaimed from a ThreadCache without locking, which is fast. In this way, the problem of increasing contention for allocation lock caused by ptmalloc multithreading is solved.

CentralCache: A cache common to all threads. CentralCache also has a separate linked list for each size class to cache free objects, called CentralFreeList, as shown in the CentralCache section above, which is used by threadcaches for each thread to retrieve free objects. In other words, CentralCache provides memory resources for ThreadCache.

PageHeap: TCMalloc abstraction of dynamically allocated memory. When there are not enough free objects in CentralCache, CentralCache requests a block of memory from PageHeap (either from the PageHeap cache or from the system) and breaks it up into a series of free objects. Add to CentralFreeList of the corresponding size class. Its internal memory blocks are retrieved in span units. See the PageHeap section in the figure above.

There are two different caching strategies within PageHeap based on the size of the memory block (SPAN). Spans of up to 128 pages are cached in a linked list for each size. Spans of more than 128 pages are stored in an ordered set (STD ::set). As shown above, squares in a linked list and squares in a set represent a span. Assuming that a page is 4 bytes, then the sum of the sizes of all spans in the linked list of page 1 in the figure above is 4 bytes. Similarly, the total span size of 2 pages is 8 bytes, 3 pages is 12 bytes, and so on.

This is all about memory allocation. What about memory reclamation?

When a user process calls free() or delete a small object, it inserts it into a FreeList corresponding to its size class in ThreadCache. No lock is required, so it is very fast.

Only when certain conditions are met are free objects in ThreadCache put back into CentralCache for other threads to retrieve. Similarly, when certain conditions are met, free objects in CentralCache are returned to PageHeap, and PageHeap is returned to the system.

Now let’s look at the tcMALloc process of allocating and freeing memory.

Memory allocation

Tcmalloc divides memory allocation into three categories:

Small object allocation

Tcmalloc calls the allocation of objects greater than 0 and less than or equal to 256K small object allocation. The specific process is as follows:

  • The memory size to be allocated is mapped to the corresponding size class.

  • Check the size class’s FreeList in ThreadCache.

  • If the FreeList is not empty, the first free object of the FreeList is removed and returned, the allocation ends.

  • If FreeList is empty:

  • Get a bunch of free objects from CentralFreeList corresponding to the size class in CentralCache.

    • If CentralFreeList is also empty then:
    • Request a SPAN from PageHeap.
    • Split it into free objects of the corresponding size of size class and put them into CentralFreeList.

  • Place the heap into a FreeList corresponding to the size class in ThreadCache (except for the first object).

  • Returns the first object retrieved from CentralCache, and the allocation is complete.

Middle object allocation

Tcmalloc calls the allocation of objects greater than 256K and less than or equal to 1M central object allocation. The specific process is as follows:

  • Round up the memory size required by the application to an integer number of pages, say k pages
  • Start with the k page span list and go to the 128 page span list to find the first non-empty list in sequence.
  • Take a span from the non-empty list and split the span into two spans:
  • A SPAN of K pages is returned as an allocation result.
  • Another span of n-K pages is inserted back into the span list of n-K pages.
  • If no non-empty list can be found, the assignment is treated as a large object assignment
Large object allocation

Tcmalloc calls the allocation of objects larger than 1M large object allocation. The specific process is as follows:

  • Round up the memory size required by the application to an integer number of pages, say k pages
  • Search the Set in PageHeap to find the smallest span with at least K pages
  • Split this span into two spans:
  • A SPAN of k pages is returned as the result.
  • The other span size is n-K pages, if n-k > 128, it is inserted into the set of the large span, otherwise, it is inserted into the corresponding small span linked list.
  • If no suitable span is found, new memory is applied to the system using SBRK or MMAP to generate a new SPAN, and the allocation algorithm for medium or large objects is re-executed.

Now I take MySQL sort field sort_buffer as an example, combined with the above TCMALloc memory allocation policy, explain the memory allocation process in detail.

MySQL > select * from ‘sort_buffer_size’; select * from ‘sort_buffer_size’; select * from ‘sort_buffer_size’;

  1. MySQL > select memory size from 128 MB to 32 pages (128/4=32 pages)
  2. Since 32 is less than 128, we allocate the middle object:
    • Start with a 32-page span list and work your way up to a 128-page span list to find the first non-empty list.
    • Assuming that this non-empty list corresponds to 64 pages, take a span from the non-empty list of 64 pages and split the span into two spans
    • A SPAN of K pages is returned as an allocation result.
    • Insert another span with a size of 64-32 = 32 pages into the 32-page span list.

By using TMALloc to explain the MySQL sort field memory application process and TMALloc memory management data structure, TMALloc through one thread one cache way, in the small object allocation, avoid multi-thread concurrent cache lock caused by performance degradation, but, For medium objects and large object allocation, there is still the problem of locking. After all, tcMALloc addresses the performance problem of small object allocation.

Now let’s see how to install tcmalloc into MySQL so that MySQL can use the memory allocator.

Install the LibunWind library for 64-bit operating systems

yum -y install gcc make gcc-c++ libunwind
Copy the code

Then download and install Google-PerfTools

# Download the source packageWget HTTP: / / https://github.com/gperftools/gperftools/releases/download/gperftools-2.5/gperftools-2.5.tar.gzUnzip the source packageThe tar xf gperftools - 2.5. Tar. Gz# start compiling and installing
./confighre
make
make install
Do a search to find the relevant C library files installed
find / -name libtcmalloc.so
/usr/local/ lib/libtcmalloc. So/opt/gperftools - 2.5 / libs/libtcmalloc. SoCreate a lib library soft link so you don't need to use LDConfig
ln -sf /usr/local/lib/libtcmalloc.so /usr/lib/
ln -sf /usr/local/lib/libtcmalloc.so /usr/lib64/
# complete
ll /usr/lib/libtcmalloc.so
lrwxrwxrwx. 1 root root 29 Jan 23 12:05 /usr/lib/libtcmalloc.so -> /usr/local/lib/libtcmalloc.so
Copy the code
Open the mysql configuration file and add the following two lines
vim /usr/local/mysql/my.cnf
    .
    .
    .
[mysqld_safe]
malloc-lib=tcmalloc
    .
    .
    .
# restart mysql
/etc/init.d/mysql restart
Copy the code

Enter the following command to verify:

Lsof -n | grep tcmalloc mysqld 3665 mysql mem REG/usr / 253, 0 1050408 100663894local/lib/libtcmalloc_minimal.so.4.3.0
mysqld     3665  3666   mysql  mem       REG              253,0    1050408  100663894 /usr/local/lib/libtcmalloc_minimal.so.4.3.0
mysqld     3665  3669   mysql  mem       REG              253,0    1050408  100663894 /usr/local/ lib/libtcmalloc_minimal. So. 4.3.0Copy the code

Tcmalloc has been successfully installed in MySQL.

conclusion

If the value of a sorted field does not exceed sort_buffer_size and the SQL contains limit, MySQL will use a priority queue to sort the fields. This avoids sorting invalid records and improves sorting efficiency.

At the same time, I can use TCMALloc memory allocator to make MySQL avoid lock competition when allocating small object memory, so as to make full use of memory resources, let more data stored in memory, improve the efficiency of query.