导读
大家可以想看看这条SQL语句思考一下：
SELECT*FROMuserWHEREuser_nameLIKE"%am%"ANDage=18ANDage=24ANDsex=0ORDERBYage,user_nameLIMIT0,50复制代码
这条SQL使用了快速排序对age,username排序，有没有更好的办法，提升排序的性能？
你可能已经发现，这条SQL其实只需要取前50个排好序的用户，但是，上面的执行过程确对表中的条记录都进行了排序，如果我只对50记录进行排序，保证这50条记录就是排好序的前50条，从排序算法来看，是不是代价就小很多了呢？那么，我们怎么做到只对50记录进行排序，同时，这50条记录又刚好是排好序的前50条呢？
学过排序算法的同学可能已经猜到了，堆排序！是的，MySQL5.6开始引入了一个新的排序算法，叫做优先级队列排序，该队列使用的就是堆排序，保证只对有限数量n条的记录排序，同时，排序后的结果就是前n条记录。
关于堆排序，计算机相关专业的同学应该比较熟悉，在此，我就不详细讲述了。
PTMalloc
这里，我主要结合《单表数据规模达到多大时进行分表最佳？》这一章中《内存分配》这部分，来详细看一下上面排序过程中，MySQL申请内存的过程：MySQL默认使用ptmalloc内存分配器给进程分配内存。
数据结构
因此，我们先来看一下ptmalloc管理内存块所使用的数据结构：
分配区
ptmalloc使用一个主分配区和多个动态分配区来管理内存，主分配区与非主分配区用环形链表进行管理。如上图中的MainAna表示一个主分配区，DynamicAna表示3个动态分配区，它们之间首尾相连，形成环形状。ptmalloc根据系统对分配区的争用情况动态增加非主分配区的数量，分配区的数量一旦增加，就不会再减少了。
在《单表数据规模达到多大时进行分表最佳？》中《内存分配》部分，我讲过内存分配器在自身没有可分配内存时，会向Linux系统申请内存，可以申请堆内存，也可以申请文件映射区的内存，所以，对ptmalloc来说，主分配区可以申请堆和文件映射的内存，而动态分配区只能申请文件映射区的内存。
当某一线程需要调用malloc()分配内存空间时，该线程先查看线程私有变量中是否已经存在一个分配区，如果存在，尝试对该分配区加锁，如果加锁成功，使用该分配区分配内存，如果失败，该线程搜索循环链表试图获得一个没有加锁的分配区。如果所有的分配区都已经加锁，那么malloc()会开辟一个新的分配区，把该分配区加入到全局分配区循环链表并加锁，然后使用该分配区进行分配内存操作。在释放操作中，线程同样试图获得待释放内存块所在分配区的锁，如果该分配区正在被别的线程使用，则需要等待直到其他线程释放该分配区的互斥锁之后才可以进行释放操作。
chunk
ptmalloc会统一管理分配区空闲的内存块，当用户进行下一次分配请求时，ptmalloc会首先试图在空闲的内存块中挑选一块给用户，这样就避免了频繁的系统调用，降低了内存分配的开销。这里所说的内存块就是上图纵向用双向箭头连接的方块，我们叫它chunk，它们互相连接，组成一个双向链表。每个链表的头部组成了bins数组，即图中水平方块组成的部分。bins被划分为4种类型：
smallbins：如上图，数组中从2开始编号的前64个bin称为smallbins，同一个smallbin中的chunk具有相同的大小。两个相邻的smallbin中的chunk大小相差8bytes。smallbins中的chunk按照最近使用顺序进行排列，最后释放的chunk被链接到链表的头部，而申请chunk是从链表尾部开始，这样，每一个chunk都有相同的机会被ptmalloc选中。largebins：如上图，smallbins后面的bin被称作largebins。largebins中的每一个bin分别包含了一个给定范围内的chunk，其中的chunk按大小序排列。相同大小的chunk同样按照最近使用顺序排列。
当chunk被释放并链接到bin中的时候，ptmalloc会把表示该chunk是否处于使用中的标志P设为0（注意，这个标志实际上处在下一个chunk中），同时ptmalloc还会检查它前后的chunk是否也是空闲的，如果是的话，ptmalloc会首先把它们合并为一个大的chunk，然后将合并后的chunk放到unstodbin中。要注意的是，并不是所有的chunk被释放后就立即被放到bin中。于是，这就引出了第三种类型的bin：unsortedbin。
unsortedbins：unsortedbins使用bins数组的第一个，如上图头部。
上面提到了chunk合并，那么，我来看下这么一个场景：当分配器合并了相邻的几个小的chunk之后，也许马上就会有另一个小块内存的请求，这样分配器又需要从大的空闲内存中切分出一块，这样做是不是很低效？
因此，ptmalloc在分配过程中引入了fastbins来解决这个问题。于是，出现了第4种bins：
fastbins：当不大于max_fast(默认值为64B)的chunk被释放后，首先会被放到fastbins中，fastbins中的chunk并不改变它的使用标志P。这样也就无法将它们合并，当需要给用户分配的chunk小于或等于max_fast时，ptmalloc首先会在fastbins中查找相应的空闲块，然后才会去查找bins中的空闲chunk。这样一来，用户进程申请小内存分配时，就可以直接从fastbins中获取，不用再切分大内存块了。
sort_buffer排序使用了ptmalloc内存分配器向Linux内核申请内存，由于ptmalloc分配内存时会对分配区加锁，高并发下锁争用更激烈，ptmalloc不得不为进程创建更多的分配区，由于分配区长时间不释放内存，导致ptmalloc缓存的chunk数量增长更快，从而出现内存暴增，甚至溢出。对于MySQL这种存储大规模数据的数据库而言是不能接受的，因为如果在高并发场景下，MySQL不断创建越来越多的分配区来缓存更多数据，那么，势必很快用尽内存资源，内存耗尽后，不得不将更多数据写入磁盘，此时，数据查询的效率将出现大幅度的下降。那么，问题来了，有什么办法解决这个问题呢？
还记得我在《单表数据规模达到多大时进行分表最佳？》这一章节中提到过tcmalloc内存分配器，或许你已经猜到了，是的！用tcmalloc替换ptmalloc，下面，我们就从tcmalloc使用的数据结构开始，讲解一下其是如何解决锁竞争的问题的？
TCMalloc
数据结构
下图是tcmalloc使用的数据结构：
tcmalloc主要包含下面几个部分：
sizeclass：对于KB以内的小对象分配，TCMalloc按大小划分了85个类别（官方介绍中说是88个左右，但我个人实际测试是85个，不包括0字节大小），称为SizeClass，每个sizeclass都对应一个大小，比如8字节，16字节，32字节。应用程序申请内存时，TCMalloc会首先将所申请的内存大小向上取整到sizeclass的大小，比如1~8字节之间的内存申请都会分配8字节，9~16字节之间都会分配16字节，以此类推。如上图的sizeclass部分。通过取整，我们发现如果申请内存小于sizeclass，取整后就会产生内部碎片。比如：我要申请4字节内存，取整后，给我分配了8字节，如果此后申请的内存大小都超过4字节，那么，剩下的4字节就成为了碎片。TCMalloc将这里的内部碎片控制在12.5%以内。
ThadCache：对于每个线程，TCMalloc都为其保存了一份单独的缓存，称之为ThadCache。每个ThadCache中对于每个sizeclass都有一个单独的FeList，缓存了n个还未被应用程序使用的空闲对象。
如上图，有n个线程，每个线程有一份ThadCache，ThadCache0~ThadCachen。每个cache中包含n个sizeclass的Felist链表：sizeclass0~sizeclassn。
由于每线程一个ThadCache，因此从ThadCache中取用或回收内存是不需要加锁的，速度很快。这样，就解决了上面ptmalloc多线程并发导致的分配区加锁争用加剧的问题。
CentralCache：一个所有线程公用的缓存。CentralCache中对于每个sizeclass也都有一个单独的链表来缓存空闲对象，称之为CentralFeList，如上图CentralCache部分，它供各线程的ThadCache从中取用空闲对象。也就是说CentralCache为ThadCache提供内存资源。
PageHeap：TCMalloc对可动态分配的内存的抽象。当CentralCache中的空闲对象不够用时，CentralCache会向PageHeap申请一块内存（可能来自PageHeap的缓存，也可能向系统申请新的内存），并将其拆分成一系列空闲对象，添加到对应sizeclass的CentralFeList中。其内部的内存块的取用是以span单位。如上图中的PageHeap部分。
PageHeap内部根据内存块（span）的大小采取了两种不同的缓存策略。个page以内的span，每个大小都用一个链表来缓存，超过个page的span，存储于一个有序set（std::set）。如上图，链表中的方块以及set中的方块表示一个span。假设一个page是4字节，那么，上图中1page中链表中所有span的大小总和就等于4字节。以此类推，2pages的span总大小等于8字节，3pages为12字节等等。
上面说的都是内存分配，内存回收的情况是怎样的？
用户进程调用fe()或delete一个小对象时，将其插入到ThadCache中其sizeclass对应的FeList中，不需要加锁，因此速度是非常快的。
只有当满足一定的条件时，ThadCache中的空闲对象才会重新放回CentralCache中，以供其他线程取用。同样的，当满足一定条件时，CentralCache中的空闲对象也会还给PageHeap，PageHeap再还给系统。
现在我们再来看一下tcmalloc分配和释放内存的过程。
内存分配
tcmalloc将内存分配大小分为3类：
小对象分配
tcmalloc将大于0，小于等于K的对象分配称为小对象分配。具体过程如下：
将要分配的内存大小映射到对应的sizeclass。查看ThadCache中该sizeclass对应的FeList。如果FeList非空，则移除FeList的第一个空闲对象并将其返回，分配结束。如果FeList是空的：从CentralCache中sizeclass对应的CentralFeList获取一堆空闲对象。如果CentralFeList也是空的，则：向PageHeap申请一个span。拆分成sizeclass对应大小的空闲对象，放入CentralFeList中。将这堆对象放置到ThadCache中sizeclass对应的FeList中（第一个对象除外）。返回从CentralCache获取的第一个对象，分配结束。
中对象分配
tcmalloc将大于K，小于等于1M的对象分配称为中对象分配。具体过程如下：
将应用程序所要申请的内存大小向上取整到整数个page，假设是k个page从k个page的span链表开始，到个page的span链表，按顺序找到第一个非空链表。取出这个非空链表中的一个span，将这个span拆分成两个span：一个span大小为k个page，作为分配结果返回。另一个span大小为n-k个page，重新插入到n-k个page的span链表中。如果找不到非空链表，则将这次分配看做是大对象分配
大对象分配
tcmalloc将大于1M的对象分配称为大对象分配。具体过程如下：
将应用程序所要申请的内存大小向上取整到整数个page，假设是k个page搜索PageHeap中的set，找到不小于k个page的最小的span将这个span拆分为两个span：一个span大小为k个page，作为结果返回。另一个span大小为n-k个page，如果n-k，则将其插入到大span的set中，否则，将其插入到对应的小span链表中。如果找不到合适的span，则使用sbrk或mmap向系统申请新的内存以生成新的span，并重新执行中对象或大对象的分配算法。
现在我以MySQL排序字段申请sort_buffer为例，结合上面tcmalloc内存分配策略，详细讲解一下内存分配过程。
假设MySQL现在要为排序字段申请sort_buffer_size=M的内存，由于申请大小超过1M，所以，使用大对象分配策略，为了简化计算，假设一个page大小4M：
将MySQL所要申请的内存大小M向上取整到整数个page为/4=32个page由于32小于，所以，进行中对象分配：从32个page的span链表开始，到个page的span链表，按顺序找到第一个非空链表。假设这个非空链表对应的64page，取出64page非空链表中的一个span，将这个span拆分成两个span一个span大小为k个page，作为分配结果返回。另一个span大小为64-32=32个page，重新插入到这32个page的span链表中。
通过使用tmalloc对MySQL排序字段内存申请过程以及tmalloc内存管理的数据结构的讲解，tmalloc通过一个线程一个cache的方式，在小对象分配时，避免了多线程并发对cache加锁引起的性能下降的问题，但是，对于中对象和大对象分配，还是会有加锁的问题存在。但是，毕竟tcmalloc还是解决了小对象分配的性能问题。
那么，现在，我们来看看如何安装tcmalloc到MySQL中，让MySQL可以使用该内存分配器？
64位操作系统请先安装libunwind库
yum-yinstallgccmakegcc-c++libunwind复制代码
然后下载并安装google-perftools
#下载源码包wget