記錄一次伺服器宕機分析過程（2）-深入Lua GC

繼續接著上一篇文章記錄一次伺服器宕機分析過程（1）-排查問題分析宕機問題

Lua GC演算法

Lua GC實現的是一個三色增量標記回收演算法（Tri-Color Incremental Mark & Sweep）。它是基於二色標記回收演算法（Two-Color Mark & Sweep）的改進。

狀態變化圖

首先，我們先了解一下二色標記回收演算法。在演算法中，所有新建對象都會被初始化為白色。一次回收的過程大概是：

1. 從root對象組（所有最上層定義的對象）開始遍歷，所有可達對象都被標記為黑色。
2. 等遍歷完成後，剩餘的白色對象即為可回收對象，我們回收這些白色對象。
3. 重置黑色對象為白色對象，等待下次回收過程。

一個示例如下圖所示：

二色回收過程

這個演算法有個缺點，就是執行過程必須是完整的。如果一次處理的數據量過大，會佔用比較大的時間片，有一定的性能問題。

Tri-Color Incremental Mark & Sweep

狀態變化圖

為了能夠分步執行回收演算法，Lua在5.1版本開始使用三色增量標記回收演算法。同樣，所有新建對象都會被初始化為白色。一次回收的過程大概是：

1. （1）從root對象組（所有最上層定義的對象）開始遍歷，所有可達對象都push入棧並被標記為灰色。
   （2）從棧中pop出一個對象，標記為黑色，遍歷這個對象的可達對象，如果是白色，標記為灰色push入棧；（重複執行這個過程執行到棧為空為止）。
2. 等遍歷完成後，剩餘的白色對象即為可回收對象，我們回收這些白色對象。
3. 重置黑色對象為白色對象，等待下次回收過程。

過程 1 耗費整個回收演算法最多的時間，是可分步執行的，步驟的中間會新建白色對象，為了將它們納入標記過程，有兩種方式：

（1）直接置灰push入棧 (barrier fwd)。

（2）指向這個白色對象的黑色對象被重新置灰push入棧 (barrier back)。

ps：根據具體對象類型選擇barrier的方式。

一個示例如下圖所示：

三色回收過程

Lua 源碼分析

我們來看下Lua的源碼（http://github.com/LuaDist/lua/tree/lua-5.3/src）來理解一些具體的GC執行流程。先看下觸發GC的代碼，在lua執行的過程中，會經常通過luaC_checkGC宏命令，根據GCdebt的值（受設置的pause影響）確定是否需要GC：

#define luaC_condGC(L,pre,pos) { if (G(L)->GCdebt > 0) { pre; luaC_step(L); pos;}; condchangemem(L,pre,pos); }/* more often than not, pre/pos are empty */#define luaC_checkGC(L) luaC_condGC(L,,)

如果需要GC，則執行luaC_step：

/*** performs a basic GC step when collector is running*/void luaC_step (lua_State *L) { global_State *g = G(L); l_mem debt = getdebt(g); /* GC deficit (be paid now) */ if (!g->gcrunning) { /* not running? */ luaE_setdebt(g, -GCSTEPSIZE * 10); /* avoid being called too often */ return; } do { /* repeat until pause or enough "credit" (negative debt) */ lu_mem work = singlestep(L); /* perform one single step */ debt -= work; } while (debt > -GCSTEPSIZE && g->gcstate != GCSpause); if (g->gcstate == GCSpause) setpause(g); /* pause until next cycle */ else { debt = (debt / g->gcstepmul) * STEPMULADJ; /* convert work units to Kb */ luaE_setdebt(g, debt); runafewfinalizers(L); }}

luaC_step會根據debt的值（受設置的stepmul的影響）執行多步singlestep：

static lu_mem singlestep (lua_State *L) { global_State *g = G(L); switch (g->gcstate) { case GCSpause: { g->GCmemtrav = g->strt.size * sizeof(GCObject*); restartcollection(g); g->gcstate = GCSpropagate; return g->GCmemtrav; } case GCSpropagate: { g->GCmemtrav = 0; lua_assert(g->gray); propagatemark(g); if (g->gray == NULL) /* no more gray objects? */ g->gcstate = GCSatomic; /* finish propagate phase */ return g->GCmemtrav; /* memory traversed in this step */ } case GCSatomic: { lu_mem work; int sw; propagateall(g); /* make sure gray list is empty */ work = atomic(L); /* work is what was traversed by atomic */ sw = entersweep(L); g->GCestimate = gettotalbytes(g); /* first estimate */; return work + sw * GCSWEEPCOST; } case GCSswpallgc: { /* sweep "regular" objects */ return sweepstep(L, g, GCSswpfinobj, &g->finobj); } case GCSswpfinobj: { /* sweep objects with finalizers */ return sweepstep(L, g, GCSswptobefnz, &g->tobefnz); } case GCSswptobefnz: { /* sweep objects to be finalized */ return sweepstep(L, g, GCSswpend, NULL); } case GCSswpend: { /* finish sweeps */ makewhite(g, g->mainthread); /* sweep main thread */ checkSizes(L, g); g->gcstate = GCScallfin; return 0; } case GCScallfin: { /* call remaining finalizers */ if (g->tobefnz && g->gckind != KGC_EMERGENCY) { int n = runafewfinalizers(L); return (n * GCFINALIZECOST); } else { /* emergency mode or no more finalizers */ g->gcstate = GCSpause; /* finish collection */ return 0; } } default: lua_assert(0); return 0; }}

singlestep根據當前的GC state判定這步執行什麼代碼。GC有以下幾種state：

1. GCSpause： GC cycle的初始化過程；一步完成。
2. GCSpropagate： 遍歷對象，直到棧空 ；多步完成。
3. GCSatomic： 處理收尾工作；一步完成。
4. GCSswpallgc： 清理 allgc 鏈表；多步完成。
5. GCSswpfinobj： 清理 finobj 鏈表；一步完成。
6. GCSswptobefnz： 清理 tobefnz 鏈表；一步完成。
7. GCSswpend： sweep main thread ；一步完成。
8. GCScallfin： 執行一些 finalizer (__gc) 完成循環；一步完成。

其中GCSpropagate是最耗時的遍歷對象的過程，根據log顯示大部分的singlestep都在做GCSpropagate。

結合演算法和源碼分析宕機問題

按照三色標記回收演算法的增量計算方式，如果在GCSpropagate階段，不斷的新增大量的新對象，會不斷增加GCSpropagate的工作量。如果每個step執行的singlestep不夠多的話，可能導致GC cycle長時間處在GCSpropagate狀態。

根據這個猜想，我在singlestep函數內列印了狀態信息，果然發現GC一直處在GCSpropagate狀態，而內存一直在漲。在之前的實驗中，我們通過調節stepmul在一定程度上解決了內存上漲問題，是因為這樣可以增加每個step可執行的singlestep數量，讓GC可以更快跳出GCSpropagate狀態，完成GC cycle。

Tips：

1. 對於大量產生臨時內存的程序要關注lua的GC工作情況，如有需要可以適當調節setpause、setstepmul參數。
2. 可以加入GC保護機制，超過多少內存強制GC。
3. 可以加入內存報警機制。

演算法參考：http://wiki.luajit.org/New-Garbage-Collector