Go 內(nèi)存頁管理 與 radix tree
??? Go語言最初采用了TCmalloc算法作為其內(nèi)存分配的指導(dǎo)思想,TCmalloc算法的核心想法之一是將內(nèi)存分成若干大小級別的class塊。這種算法由于需要將對象的內(nèi)存映射到最接近的class，因此會有內(nèi)存浪費的問題。但是分成的若干級別可以free-lock 進(jìn)行訪問，這在多線程的程序中，性能會大大提升。?
????世面上Go語言的文章在介紹內(nèi)存分配時，比較強調(diào)在mallocgc函數(shù)中，如何根據(jù)對象大小放入到不同的span class中。存儲在不同P中的不同級別的span塊，以及span中對象的cache，能夠幫助非常快的分配對象。它能夠說明有了span之后快速分配的問題，但是不能解決span是如何來的問題。span怎么來就涉及到Go語言對于內(nèi)存頁(page 8KB)的管理。
????在Go1.12的時候,Go語言采用了Treap 進(jìn)行內(nèi)存的管理，Treap 是一種引入了隨機數(shù)的二叉樹搜索樹，其實現(xiàn)簡單，并且引入的隨機數(shù)以及必要時的旋轉(zhuǎn)保證了比較好的平衡特性。
??? Michael Knyszek 提出這種方式具有擴展性的問題，確實，由于這棵樹是mheap管理，當(dāng)操作此二叉樹的時候都需要維持一個lock。這在密集的對象分配以及nprocs過多的時候，會導(dǎo)致更長的等待時間。雖然這種情況不是特別的嚴(yán)重，但是這種擴展性問題不能接受。
??? Michael Knyszek 提出用bitmap來管理內(nèi)存頁,并在每個P中維護(hù)了一份page cache。這就是現(xiàn)在Go語言實現(xiàn)的方式。具體的實現(xiàn)細(xì)節(jié)要復(fù)雜很多，但是Knyszek 用優(yōu)雅的代碼展現(xiàn)了一位頂尖工程師的恐怖實力。
????作者將這樣內(nèi)存管理的結(jié)構(gòu)叫做基數(shù)樹（radix tree）， 他和一般的基數(shù)樹有點不太一樣，這個名字很大一部分是由于父節(jié)點包含了子節(jié)點的若干信息。
????最底層的葉子節(jié)點包含了一個chunk的信息（512 * 8 K）, 每一個父節(jié)點都包含了8個子節(jié)點的內(nèi)存信息。這些內(nèi)存信息存儲在叫做summary的結(jié)構(gòu)中，這個結(jié)構(gòu)非常特殊，summary包含了在這個區(qū)域中空閑內(nèi)存頁的信息，包括了在開頭有多少連續(xù)內(nèi)存頁，最大有多少連續(xù)內(nèi)存頁，在末尾有多少連續(xù)內(nèi)存頁。??
????在查找的時候，這些信息非常有用，他可以快速的確定子節(jié)點是否有足夠的內(nèi)存。由于這棵樹的結(jié)構(gòu)特性，當(dāng)分配的對象很大時，它能夠很快的知道當(dāng)前的大對象是否可以分配。如果超過了當(dāng)前樹的最大連續(xù)內(nèi)存，就會向操作系統(tǒng)申請內(nèi)存。
????一棵樹管理的內(nèi)存為16G，這樣一棵radix tree樹有多少個呢？答案是初始化的時候大約有16384個（64位linux）。而且一個summary就uint64大小，很小的。
現(xiàn)在now，就可以將npages放進(jìn)P的cache中，對密集小對象分配實現(xiàn)free-lock。現(xiàn)在的結(jié)構(gòu)對于內(nèi)存頁的管理真是很細(xì)微了，而且它提供了很強的擴展性，更神奇的是，這些節(jié)點隱含了內(nèi)存地址的信息，radix tree 任意一個節(jié)點都可以找到在它對應(yīng)的在內(nèi)存中的地址，舒服了。
推薦閱讀