三四月，又是一年跳槽離職漲工資的高峰期，校園春季招聘、社會招聘的你，是否準備好了呢？
且不說面試會可能會遇到這個問題，我們很多服務器程序在長週期或者大量訪問的情況後會變得反應遲鈍，排查原因發現佔用內存會隨著請求數量的增多不規律而且不正常地增長，和內存洩漏一樣。如果使用valgrind這樣的內存洩露工具排查卻發現並無內存洩露，其根本原因是內存碎片造成的。這也是我們在開發高性能服務器需要解決的一個問題，那如何解決這個問題呢？請聽我慢慢道來。
一、 內存分配與內存碎片
經典的進程內存佈局如圖1所示。
圖1 內存佈局圖
圖1中底端是內存地址為0的地方，頂端是內存線性地址最大的地方（如32位下線性地址最大值是0xFFFFFFFF），而佔據頂端的就是內核空間，這裡是操作系統內核預留的空間區域。第二部分是棧空間，也就是堆棧所在的內存空間，眾所周知，棧是自高地址處向低地址處增長的，這在圖中也有所反映。最後一部分是堆空間，在這個簡化的理論模型上所有的剩餘空間都預留給了堆，堆是從低地址向高地址增長的。
當然這只是一個簡化模型，實際上在堆的下方，還會為靜態內存空間預留內存，而堆與棧的中間可能還有供mmap（內存映射）使用的區域。此外，由於棧的空間有限，而且只用來管理所謂的“自動變量”，因此我們在實際程序中需要大量使用到堆。堆空間不僅可用內存多，而且可以動態分配，也就是說按需獲取，按需使用，不需要時釋放即可。C中的malloc/free與C++中的new/delete就是用來管理內存的。但是較
少有人去深入瞭解malloc/free或者new/delete到底為我們做了什麼。
首先，內存管理函數並不會直接去向操作系統索要內存，因為系統調用的開銷比較大，這樣做是非常不值的。此外，直接使用過系統調用的人都知道，在Linux下分配堆內存需要使用brk系統調用，而這個系統調用只是簡單地改變堆頂指針而已，也就是將堆擴大或者縮小。所以如果我們遇到這種情況，是沒有辦法直接將內存歸還給操作系統的，如圖2所示。
圖2 內存圖
這種情況下，假設我們先分配了memory2，再分配memory1。現在memory2內存不需要了，我們想還給內存，但是遇到問題了——如果我們改變brk指針，那麼memory1也會被還給系統，這樣是不可行的。
我們有兩種解決方案：一是將memory2內存中的數據複製到memory1中，但是這樣一來，所有的內存地址都會發生變化，是不可行的；二是將memory2的內存緩存下來，下一次用戶申請內存時我們不需要直接使用系統調用，而是直接從緩存的內存中劃出一塊交給用戶。等到用戶完全不使用memory1和memory2了再將這兩塊內存釋放。所以在C/C++真正的內存管理中，都會有這麼一個內存管理器，它負責向操作系統申請內存，並將內存緩存下來，並通過某種算法從緩存的內存中劃出一塊交給用戶，這樣一可以提高程序的運行效率，二可以提高內存的使用效率，一舉兩得。這個內存管理器就像一個“批發商”，一次性向操作系統索要可觀的內存數量，並直接將自己“批發”來的內存銷售給調用內存管理函數的用戶。
但是，如果我們這個“批發商”對商品管理不當，還是會出很大問題的，如圖3所示。
圖3 原始內存圖
其中，每個字符串我們都分配了一定數量的空間，如字符串“a”需要2字節（C中字符串需要一個額外的0字符用於標識字符串結束）。現在我們發現“a”、“c”、“e”這3個字符串再也不需要了，所以我們將其釋放，現在內存如圖4所示。
圖4 釋放字符串之後的內存圖
這樣這3塊內存又可以重複利用了。但是這些內存太小了，為了保證之後可以更好地利用，我們需要將其合併起來（合併成一塊內存），這樣再次分配內存時，只要用戶需要的內存不超過6字節，只需要從中劃出一塊分給用戶即可。合併之後的內存圖如圖5所示。
圖5 合併之後的內存圖
但這是一種非常理想的情況，而且是一種極端最優情況。讓我們來看另一種極端最壞的情況，假設我們分配內存如圖6所示。
圖6 內存圖
現在看起來是正常的。但是如果我們不需要那幾個2字節的內存空間，內存如圖7所示。
圖7 內存圖
現在那幾個2字節的空間是被還給內存管理器了，但是內存管理器沒辦法對其進行合併，因為這幾個很小的空間是零碎分佈在這片內存中的。一個極端情況是：如果程序再也沒有2字節的動態內存可以分配了，而且這幾個4字節內存是永遠佔用的，那麼這幾個2字節內存又該如何使用呢？
很明顯，這幾塊內存已經再也無法使用了，既不能分配又不能歸還——這就是所謂的內存碎片。小規模的內存分配越多，內存碎片也就會越嚴重。而gcc默認使用的ptmalloc分配器對這種內存碎片的優化不是非常理想，導致了Samuel出現了看似是“內存洩漏”的問題，實際上是內存碎片問題。
此外，我們想象另一個場景，如果每個線程併發分配堆，由於對於每個進程堆是唯一的，因此我們再分配內存時還需要上鎖，如果在一個程序中需要在短時間內頻繁地分配小內存，那麼又會出現因為頻繁上鎖而導致的性能損耗。這是我們無法接受的。
二、tcmalloc
為了解決這些問題，我們可以使用一些更好的內存管理器替代默認的內存管理器，如Google開發的tcmalloc（Google的gperftools的一部分，網址為https://github.com/gperftools/gperftools）和jemalloc等內存管理庫，這些庫使用得非常頻繁，而且不需要改變原有代碼，對於頻繁使用內存的程序，是非常值得使用的，例如，Redis為了獲得最好的性能就使用了tcmalloc和jemalloc。（Redis是一個開源的使用ANSI C語言編寫、支持網絡、可基於內存亦可持久化的日誌型、Key-Value數據庫，並提供多種語言的API，是目前最流行的緩存解決方案之一。）
tcmalloc和jemalloc的原理非常相似，都是在鏈接時期替代標準libc中的malloc和free，因此加載程序後就會替代原有的malloc和free進行工作，因此在不改動代碼的情況下，就可以解決內存碎片的問題。
下面介紹一下tcmalloc。
tcmalloc就是一個內存分配器，管理堆內存，主要影響malloc和free，用於降低頻繁分配、釋放內存造成的性能損耗，並且有效地控制內存碎片。glibc中的內存分配器是ptmalloc2，tcmalloc號稱要比它快。一次malloc和free操作，ptmalloc需要300 ns，而tcmalloc只要50 ns。同時tcmalloc也優化了小對象的存儲，需要更少的空間。tcmalloc特別對多線程做了優化，對於小對象的分配基本上不存在鎖競爭，而大對象使用了細粒度、高效的自旋鎖（Spinlock）。分配給線程的本地緩存在長時間空閒的情況下會被回收，供其他線程使用，這樣提高了在多線程情況下的內存利用率，不會浪費內存，而這一點ptmalloc2是做不到的。tcmalloc區別地對待大、小對象。它為每個線程分配了一個線程局部的cache，線程需要的小對象都是在其cache中分配的，由於是thread local的，所以基本上是無鎖操作（在cache不夠，需要增加內存時，會加鎖）。同時，tcmalloc維護了進程級別的cache，所有的大對象都在這個cache中分配，由於多個線程的大對象的分配都從這個cache進行，所以必須加鎖訪問。在實際
的程序中，小對象分配的頻率要遠遠高於大對象，通過這種方式（小對象無鎖分配，大對象加鎖分配）可以提升整體性能。
線程級別cache和進程級別cache實際上就是一個多級的空閒塊列表（Free List）。一個空閒塊列表以大小為k B倍數的空閒塊進行分配，包含n個鏈表，每個鏈表存放大小為n×k B的空閒塊。在tcmalloc中，小於等於32 KB的對象被稱為小對象，大於32 KB的是大對象。在小對象中，小於等於1024 B的對象以8n B分配，大於1025 B，小於等於32 KB的對象以128n B大小分配，例如，要分配20 B則返回的空閒塊大小是24 B，小於等於B的，這樣在小於等於1024 B的情況下最多浪費7 B，大於1025 B則浪費127 B。而大對象是以頁大小4 KB進行對齊的，最多會浪費4KB-1 B。圖8所示為一個空閒塊列表的示意圖。
圖8 tcmalloc空閒鏈表示意圖
實際上，一個空閒塊列表就是一個數組索引多個鏈表，每個鏈表存放相同大小的塊。可以根據要分配的內存大小size算出合適的塊在free list中的下標，然後找到對應的空閒塊鏈表。
tcmalloc的數據結構組織如圖9所示。
圖9 tcmalloc數據組織
1）線程局部空閒鏈表：線程本地的空閒塊cache，用於分配小對象。
2）堆空閒鏈表：中心free list，全局唯一，用於按頁對齊分配大對象或者將連續的多個頁（被稱作span）分割成多個小對象的空閒塊分配給thread-local free list。
3）頁面數組：用於描述當前tcmalloc持有的內存狀態，完成從page number到span的映射。
小對象的分配過程如下。
1）根據分配的size計算出對應的空閒塊大小，從而確定對應空閒塊鏈表，然後從thread local的free list進行分配。
2）如果空閒塊鏈表非空，直接將頭結點對應的空閒塊返回並從空閒塊鏈表中將其刪除。
3）如果空閒塊鏈表是空的，需要從heap free list獲取一個span。如果heap free list非空，則將span切分成多個相同大小的空閒塊插入空閒塊鏈表中，然後返回頭節點。
4）如果heap free list是空的，則調用sbrk或者mmap進行內存的分配，一系列連續的內存頁作為span，然後切分成多個相同大小的空閒塊插入空閒塊鏈表，然後返回頭結點。大對象的分配簡單得多，直接從heap free list分配4n KB大小的空閒塊即可，如果heap free list不存在該大小的空閒塊，通過系統調用分配連續的內存頁。
tcmalloc還會對thread local cache進行垃圾收集，從而避免內存浪費。或者我們還可以使用一個傳統的解決方案——內存池。
三、內存池
內存池的思想很簡單，既然對於特定用途通用內存管理器已經無法很好地運作了，那麼幹脆就模仿內存管理器，直接在系統分配的一塊大內存上建立我們自己的內存管理機制，並設計一套數據結構與算法來適應我們特殊的內存分配需求即可。
如果是通用內存池，我們可以模仿通用的內存管理器，通過如圖10所示的數據結構來管理內存空間。
圖10 內存分配示意圖
其中，上面一塊是元數據區域，用來記錄我們的內存分配信息，元數據區域中最重要的是一個鏈表，這個鏈表維護了我們所使用的內存數據。分配內存時我們從內存中分出一塊並加入一個表項到鏈表中；釋放內存時，我們將內存從鏈表中移除。
圖10只是一個示意圖，如果只是簡單地這樣管理內存，依然無法解決內存碎片問題，需要對數據結構進行優化，這需要讀者自行閱讀相關資料。
內存池的另一個好處是我們可以為每個線程單獨分配一個內存池，而不需要整個進程共用，這樣在多線程的程序中，還可以避免多個線程之間同時分配內存時頻繁上鎖。除此之外，我們還可以在用戶引用錯誤內存時給出更清晰、更明確的異常信息，並進行Heap Dump，總之就是可以增強我們對內存的控制能力。
此外，如果將內存池技術和句柄技術結合，我們可以更好地解決內存碎片問題，如圖11所示。
圖11 內存池與句柄
我們將鏈表中的每個對象都看成一個句柄，併為這些句柄進行編號。用戶不再使用直接的指針，而是使用我們包裝過的句柄引用對象。這些對象裡包含的是句柄的編號。當我們發現由於小塊內存過多而引發內存碎片時，只需要將數據內存中的內存進行壓縮（也就是將正在使用的內存重新排布到一起，將空閒的內存空間預留出來，可以看成內存的碎片整理），並修改句柄列表中句柄指向的實際地址，這樣就可以一定程度上解決內存碎片問題。雖然這樣會引起程序的暫時停頓，但是在不直接和用戶進行UI交互的服務器程序中，這種小間斷往往是可以接受的，尤其是那些追求高吞吐量同時又要避免內存碎片的程序非常適合使用這種模型。
閱讀更多 一個程序員的奮鬥史 的文章
