簡(jiǎn)介
這篇文章在Linux2.6.35上檢測(cè)了MOSBENCH應(yīng)用是否scale，也就是在單核和在48個(gè)核上面的性能是否線性增長(zhǎng)堡赔。
在找到不scale的原因以后，進(jìn)一步分析是因?yàn)閍pplication的問題设联，linux kernel的問題還是底層硬件的問題善已。之后要么修改application的結(jié)構(gòu)，要么修改application使用kernel service的方式离例，要么修改kernel换团，總能改進(jìn)scalability。
本文的貢獻(xiàn)：
- 提出了sloppy counters方法用于解決shared counter不scale的問題宫蛆。該方法只需要修改shared counter不scale的部分艘包，而不需要對(duì)所有引用該counter的地方進(jìn)行修改。
- 一個(gè)內(nèi)核scalability測(cè)試集：MOSBENCH洒扎。
- 各種改進(jìn)scalability的小技巧辑甜。
- 結(jié)論：并不需要修改傳統(tǒng)內(nèi)核設(shè)計(jì)方式來達(dá)到scale的目標(biāo)。
MOSBENCH
說明：全部測(cè)試項(xiàng)目使用駐內(nèi)存tmpfs文件系統(tǒng)來避免磁盤讀寫瓶頸袍冷。
- 郵件服務(wù)器
Exim使用一個(gè)master進(jìn)程來監(jiān)聽SMTP請(qǐng)求磷醋，對(duì)每個(gè)新連接，fork一個(gè)新進(jìn)程處理胡诗。這個(gè)新進(jìn)程負(fù)責(zé)接收郵件邓线，將郵件隊(duì)列到一個(gè)繞軸目錄中（目錄中每個(gè)文件是一個(gè)郵件），接下來分發(fā)郵件到用戶郵件文件煌恢，刪除繞軸目錄中的郵件骇陈，在log中記錄等等。每個(gè)進(jìn)程需要fork兩次來發(fā)送一封郵件瑰抵，單核運(yùn)行花費(fèi)69%的時(shí)間在內(nèi)核中你雌，包括進(jìn)程創(chuàng)建和小文件創(chuàng)建以及刪除。 - Memcached
單個(gè)Memcached服務(wù)器在多核中運(yùn)行時(shí)二汛，會(huì)瓶頸在保護(hù)key-value哈希表的內(nèi)部鎖上婿崭，爲(wèi)了避免這一點(diǎn)我們運(yùn)行多個(gè)Memcached服務(wù)器，每個(gè)都有自己的端口肴颊，客戶端確定地分佈式訪問這些服務(wù)端氓栈。單核時(shí)80%時(shí)間在內(nèi)核中，主要包括網(wǎng)絡(luò)棧的使用婿着。 - Apache
配置爲(wèi)每個(gè)核運(yùn)行一個(gè)進(jìn)程授瘦，每個(gè)進(jìn)程用一個(gè)線程池醋界，線程池中一個(gè)線程負(fù)責(zé)接受連接，其他線程負(fù)責(zé)處理連接提完。單核運(yùn)行時(shí)Apache花費(fèi)60%的時(shí)間在Kernel上形纺，對(duì)文件系統(tǒng)，網(wǎng)絡(luò)棧壓迫較大氯葬，因爲(wèi)其對(duì)每個(gè)請(qǐng)求都要打開並且統(tǒng)計(jì)一個(gè)文件挡篓。 - 數(shù)據(jù)庫 PostgreSQL
和其他項(xiàng)目不同，PostgreSQL中有大量的數(shù)據(jù)結(jié)構(gòu)共享和同步操作帚称。將數(shù)據(jù)庫表保存爲(wèi)文件官研，並且被所有postgreSQL進(jìn)程共享訪問。每個(gè)連接開一個(gè)進(jìn)程闯睹，利用內(nèi)核鎖機(jī)制同步和負(fù)載均衡這些進(jìn)程戏羽，並且通過共享網(wǎng)絡(luò)接口的TCP socket和客戶端通訊。對(duì)於一個(gè)只讀測(cè)試楼吃，PostgreSQL在單核上1.5%的時(shí)間在內(nèi)核中始花，48核82%的時(shí)間在內(nèi)核中。 - 並行編譯
我們使用編譯linux內(nèi)核的方式來評(píng)測(cè)gmake孩锡。gmake創(chuàng)建了比CPU核心數(shù)更多的進(jìn)程並且大量讀寫文件酷宵，單核時(shí)7.6%的時(shí)間在內(nèi)核裏，但是整體耗時(shí)瓶頸在它所運(yùn)行的編譯器上躬窜。 - 文件索引
Psearchy是用來索引和查詢網(wǎng)頁的工具浇垦。pedsort在每個(gè)核上運(yùn)行一個(gè)索引器進(jìn)程，進(jìn)程間共享輸入文件荣挨。每個(gè)核跑兩個(gè)階段男韧，第一階段是從工作隊(duì)列中拉出輸入文件，讀文件並且把每個(gè)單詞的位置輸入進(jìn)每個(gè)核一個(gè)的哈希表中默垄，當(dāng)哈希表大到一定程度以後對(duì)其按照字母排序此虑，寫到磁盤上一個(gè)臨時(shí)索引文件中然後繼續(xù)讀文件。這個(gè)階段既是CPU密集的也是文件系統(tǒng)密集的口锭。採用排序的方式先處理大文件朦前，到工作隊(duì)列爲(wèi)空時(shí)，每個(gè)核合併它生成的所有臨時(shí)索引文件鹃操，把單詞位置列表合併起來况既，生成一個(gè)保存了每個(gè)單詞位置的索引文件以及一系列的BDB文件保存了每個(gè)單詞和它在文件中的偏移量。這一階段主要是文件系統(tǒng)密集的组民。單核在內(nèi)核中時(shí)間是1.9%，48核則是23%悲靴，這是scalability問題導(dǎo)致的臭胜。 - MapReduce
臨時(shí)表存放在內(nèi)存中莫其，對(duì)內(nèi)核的內(nèi)存分配和page fault處理有壓力，單核3%的內(nèi)核運(yùn)行時(shí)間耸三，48核則爲(wèi)16%乱陡。
內(nèi)核優(yōu)化
下面的表格總結(jié)了每個(gè)scalability瓶頸。
- 並行accept （Apache）
不同的accept系統(tǒng)調(diào)用共用一個(gè)socket仪壮，導(dǎo)致競(jìng)爭(zhēng)憨颠。
解決方案：每個(gè)核使用備用隊(duì)列（backlog queue）存儲(chǔ)監(jiān)聽socket。 -
dentry引用計(jì)數(shù)（Apache积锅， Exim）
文件名解析過程在目錄項(xiàng)（directory entry）的引用計(jì)數(shù)變量上存在競(jìng)爭(zhēng)爽彤。
解決方案：使用sloppy counter保存目錄項(xiàng)對(duì)象的引用計(jì)數(shù)。 - 掛載點(diǎn)
vfsmount引用計(jì)數(shù) （Apache缚陷， Exim）
遍歷文件名路徑的時(shí)候适篙，在掛載點(diǎn)的引用計(jì)數(shù)變量上存在競(jìng)爭(zhēng)。
解決方案： 使用sloppy pointers保存掛載點(diǎn)的引用計(jì)數(shù)變量箫爷。 - 請(qǐng)求目錄項(xiàng)的自旋鎖嚷节。
遍歷文件名路徑的時(shí)候，在每個(gè)目錄項(xiàng)的自旋鎖上存在競(jìng)爭(zhēng)虎锚。
解決方案：在dlookup中使用無鎖算法硫痰。 - 掛載點(diǎn)列表自旋鎖競(jìng)爭(zhēng)
解決方案：爲(wèi)每個(gè)CPU核心分配掛載點(diǎn)列表的緩存 - 分配DMA緩衝區(qū)時(shí)在內(nèi)存節(jié)點(diǎn)0上的自旋鎖上存在競(jìng)爭(zhēng)
解決方案：在本地內(nèi)存節(jié)點(diǎn)上分配DMA緩衝區(qū) -
net_device和device上的只讀域存在僞共享
解決方案：在cache line上設(shè)置只讀域標(biāo)記。 - 保護(hù)
inode列表的全局鎖在不同CPU核心間存在競(jìng)爭(zhēng)
解決方案：避免不必要的鎖請(qǐng)求 - lseek中保護(hù)每個(gè)inode的互斥量上存在競(jìng)爭(zhēng)
解決方案：使用原子讀操作避免請(qǐng)求互斥量 - 母頁的軟缺頁錯(cuò)誤導(dǎo)致對(duì)每個(gè)進(jìn)程的互斥量存在競(jìng)爭(zhēng)
解決方案：將per-process的互斥量修改爲(wèi)per-super-page窜护。（增加鎖粒度） - 清空母頁時(shí)同時(shí)清空了CPU Cache
解決方案：使用非cache指令來清空母頁（super-page）效斑。
當(dāng)需要串行執(zhí)行的操作越多，增加CPU核心所能提供的性能提升也就越少柄慰。根據(jù)Amdahl定律當(dāng)25%的指令是串行執(zhí)行的時(shí)候鳍悠，再多的CPU核心也不能提供4倍以上的增速。這裏我們列出一系列的需要串行執(zhí)行的操作：
- 不同的任務(wù)請(qǐng)求同一共享數(shù)據(jù)結(jié)構(gòu)上的鎖坐搔。核越多藏研，等待該鎖的時(shí)間也就越長(zhǎng)。
- 不同的任務(wù)寫同一個(gè)共享內(nèi)存地址概行，因此核越多蠢挡，緩存花越長(zhǎng)的時(shí)間在獨(dú)佔(zhàn)模式（exclusive-mode）等待。使用無鎖數(shù)據(jù)結(jié)構(gòu)也不能解決這個(gè)問題凳忙。
- 不同的任務(wù)搶佔(zhàn)有限的硬件緩存业踏。即使這些任務(wù)不共享內(nèi)存也同樣存在這個(gè)問題。
- 不同的任務(wù)搶競(jìng)爭(zhēng)其他硬件資源涧卵，例如核心間DRAM帶寬勤家，這導(dǎo)致額外的核花時(shí)間在等待上面而不是計(jì)算。
- 可能有的核特別忙而有的核特別閒柳恐，調(diào)度不合理
很多可擴(kuò)展性的問題表現(xiàn)爲(wèi)因爲(wèi)一個(gè)核心要使用另外一個(gè)核寫的數(shù)據(jù)導(dǎo)致緩存未中（cache miss）的現(xiàn)象伐脖。這是兩個(gè)核競(jìng)爭(zhēng)鎖和競(jìng)爭(zhēng)無鎖可變數(shù)據(jù)時(shí)常見的現(xiàn)象热幔。具體細(xì)節(jié)取決於緩存一致性協(xié)議。例如每個(gè)核有一個(gè)數(shù)據(jù)緩存讼庇，當(dāng)一個(gè)核寫其他核緩存好的數(shù)據(jù)時(shí)绎巨，一致性協(xié)議要求該核在找到其他所有核的緩存並且無效化它們以後才能寫入。另一種場(chǎng)景是當(dāng)一個(gè)核準(zhǔn)備讀其他核剛剛寫完的數(shù)據(jù)時(shí)蠕啄，一致性協(xié)議要求只有當(dāng)找到了寫好改變以後數(shù)據(jù)的那塊緩存场勤，並且告訴那塊緩存數(shù)據(jù)已經(jīng)被拷貝之後才能讀入。這些操作的耗時(shí)和RAM讀取類似（幾百個(gè)週期）歼跟，因此核間共享數(shù)據(jù)會(huì)導(dǎo)致不成比例的性能問題和媳。
修改共享數(shù)據(jù)時(shí)應(yīng)用緩存一致性協(xié)議會(huì)導(dǎo)致兩種可擴(kuò)展性問題。第一嘹承，緩存一致性協(xié)議會(huì)串行化對(duì)同意緩存行的修改窗价，阻礙並行化加速。其二叹卷，極端情況下該協(xié)議會(huì)耗盡核間帶寬撼港，進(jìn)一步使得性能無法隨著CPU核心數(shù)目增加而提高。因此我們需要通過讓可寫數(shù)據(jù)只分佈在一個(gè)核上的方式來提高性能和可擴(kuò)展性骤竹。
另外情況是總吞吐率隨著核心數(shù)目增加而降低帝牡，因爲(wèi)每個(gè)等待的核心都在拖慢工作核心的進(jìn)度。舉例來說不可擴(kuò)展的自旋鎖導(dǎo)致了正比於正在等待的核心數(shù)量大小的核間通訊佔(zhàn)用帶寬蒙揣，這些核間通訊拖慢了持有鎖的核心靶溜。例如，如果請(qǐng)求鎖的核心當(dāng)前正持有鎖懒震，那麼需要消耗十幾個(gè)週期罩息。如果請(qǐng)求鎖的核心當(dāng)前並不持有鎖，在無競(jìng)爭(zhēng)的情況下需要消耗幾百個(gè)週期个扰，而競(jìng)爭(zhēng)情況下要消耗的比這多很多瓷炮。
性能往往是可擴(kuò)展性的敵人。使用低效的算法有時(shí)反而能增強(qiáng)可擴(kuò)展性递宅，因爲(wèi)可以讓每個(gè)核心計(jì)算自己的部分並且不共享可寫數(shù)據(jù)娘香。相應(yīng)地提高算法複雜性往往意味著使用更多的共享數(shù)據(jù)因此可擴(kuò)展性也更差。這在我們的評(píng)測(cè)中印證了很多次办龄。
一些可擴(kuò)展性瓶頸很難解決烘绽，因爲(wèi)共享數(shù)據(jù)結(jié)構(gòu)的語義就是要求串行執(zhí)行。然而我們常忱睿可以修改實(shí)現(xiàn)使得核心之間不需要彼此等待安接。例如現(xiàn)有的Linux內(nèi)核會(huì)把一系列的線程劃分爲(wèi)每個(gè)核自己獨(dú)有的調(diào)度隊(duì)列，通常情況下每個(gè)核僅僅讀寫核對(duì)自己的隊(duì)列加鎖英融。有很多類似的改進(jìn)能夠避免鎖競(jìng)爭(zhēng)和對(duì)內(nèi)部數(shù)據(jù)的競(jìng)爭(zhēng)赫段。使用無鎖數(shù)據(jù)結(jié)構(gòu)呀打，或者細(xì)粒度加鎖等常見方式也可以改進(jìn)可擴(kuò)展性。
多核數(shù)據(jù)包處理
Linux網(wǎng)絡(luò)棧使用隊(duì)列來連接處理網(wǎng)絡(luò)包的不同階段糯笙。收到一個(gè)包以後會(huì)經(jīng)過多個(gè)隊(duì)列處理之後才會(huì)進(jìn)入per-socket 隊(duì)列，應(yīng)用才通過read或者accept系統(tǒng)調(diào)用從這個(gè)per-socket隊(duì)列中讀取數(shù)據(jù)撩银。理想狀態(tài)下每個(gè)數(shù)據(jù)包给涕，隊(duì)列以及連接應(yīng)該在同一個(gè)核上進(jìn)行，這樣這能避免核間的緩存miss或者隊(duì)列鎖的開銷额获。
有兩種方法來實(shí)現(xiàn)這點(diǎn)够庙，第一是硬件的多重隊(duì)列，第二種是軟件包路由算法抄邀。在多重隊(duì)列的情況下耘眨，Linux可以爲(wèi)每個(gè)核分配一個(gè)硬件隊(duì)列，對(duì)發(fā)出的包就簡(jiǎn)單地放在這個(gè)隊(duì)列裏面境肾。進(jìn)入的包則由硬件根據(jù)路由算法（可以根據(jù)源IP核端口號(hào)）來幫助把包放到某一特定隊(duì)列上剔难，因此也能放到特定的CPU核上。IXGBE驅(qū)動(dòng)可以做到更多：它可以每20個(gè)TCP包採樣一次奥喻，然後根據(jù)該TCP連接對(duì)應(yīng)的CPU核心是哪個(gè)來更新硬件的網(wǎng)絡(luò)包路由表偶宫，根據(jù)這個(gè)路由表來將TCP包分發(fā)到相應(yīng)的核心。這種設(shè)計(jì)對(duì)長(zhǎng)連接很有效环鲤，但是對(duì)短連接效果不好纯趋，因爲(wèi)短連接TCP連接變動(dòng)情況很大，根據(jù)採樣結(jié)果進(jìn)行路由的效果不好冷离。
Apache的情況是所有的CPU核心都通過同一個(gè)socket來接受連接（不同的進(jìn)程共享同一個(gè)socket並同時(shí)在這個(gè)socket上面進(jìn)行accept系統(tǒng)調(diào)用）吵冒。我們修改了accept的實(shí)現(xiàn)使得網(wǎng)絡(luò)包被分發(fā)到本地的核心上，因此如果接受連接和處理連接是在同一個(gè)核上進(jìn)行西剥，那麼所有關(guān)於該連接的動(dòng)作都只在一個(gè)核上面進(jìn)行痹栖，這麼做也能幫助減輕對(duì)同一socket上面單一連接隊(duì)列上鎖的競(jìng)爭(zhēng)。
爲(wèi)了實(shí)現(xiàn)這個(gè)修改蔫耽，我們配置IXGBE驅(qū)動(dòng)结耀，使用網(wǎng)絡(luò)報(bào)文頭部的哈希值來把來自同一個(gè)連接的網(wǎng)絡(luò)包分發(fā)到處理該連接的核心上，然後放進(jìn)per-core的存儲(chǔ)隊(duì)列裏面匙铡，accept調(diào)用從這個(gè)隊(duì)列裏面拿請(qǐng)求图甜，如果accept發(fā)現(xiàn)隊(duì)列爲(wèi)空，那麼它會(huì)試圖去另外一個(gè)核的隊(duì)列裏面拿一個(gè)請(qǐng)求以實(shí)現(xiàn)負(fù)載均衡鳖眼。如果在處理連接的過程中線程被遷移到另外一個(gè)核心上黑毅，那麼也許組合一下這種方法以及之前的採樣方法是最好的選擇。
Sloppy pointers
Linux使用共享指針來進(jìn)行引用計(jì)數(shù)钦讳。如果多個(gè)核心都想更新這個(gè)引用計(jì)數(shù)那麼就會(huì)引起競(jìng)爭(zhēng)矿瘦。即使使用無鎖原子加法和減法操作也沒有用枕面，因爲(wèi)底層硬件一致性依然會(huì)串行化這一系列操作。MOSBENCH在目錄項(xiàng)缚去，掛載項(xiàng)潮秘，路由表項(xiàng)這三個(gè)對(duì)象的引用計(jì)數(shù)上存在瓶頸，此外在TCP和UDP的內(nèi)存使用統(tǒng)計(jì)計(jì)數(shù)量上也存在競(jìng)爭(zhēng)易结。
我們的解決方案是使用Sloppy pointers枕荞，每個(gè)核心維護(hù)自己一個(gè)局部計(jì)數(shù)器，同時(shí)有一個(gè)共享的全局計(jì)數(shù)器搞动。當(dāng)增加1個(gè)引用的時(shí)候躏精，會(huì)首先試圖從局部計(jì)數(shù)器中減少1，如果局部計(jì)數(shù)器是0鹦肿，那麼會(huì)讓全局計(jì)數(shù)器加1矗烛。中心思想是全局計(jì)數(shù)器的值=（所有引用的數(shù)目+所有局部計(jì)數(shù)器的大小）箩溃。這樣很多時(shí)候只需要訪問局部計(jì)數(shù)器就能修改引用計(jì)數(shù)（因爲(wèi)同一個(gè)核上面修改引用計(jì)數(shù)不需要訪問共享的全局計(jì)數(shù)器）瞭吃。另外的好處就是全局計(jì)數(shù)器得到保留因此不需要修改已有代碼。
sloppy pointer的好處是不需要修改原來使用共享指針部分的代碼碾篡。但是由於在刪除資源時(shí)sloppy pointer需要協(xié)調(diào)處理本地指針和全局指針的關(guān)係虱而，因此會(huì)有大量開銷。另外它的空間開銷與CPU核心的數(shù)目成正比开泽。
無鎖比較
我們注意到MOSBENCH應(yīng)用有時(shí)會(huì)瓶頸在對(duì)目錄項(xiàng)緩存的名稱查找上牡拇。目錄項(xiàng)緩存（directory entry cache）是將目錄和文件名映射到dentry上的一個(gè)哈希表，dentry中包含了對(duì)應(yīng)文件的inode穆律。在找到了候選的dentry之後惠呼，會(huì)有一個(gè)per-dentry的自旋鎖鎖住該dentry防止其他核心並行訪問，在常見前綴/usr等目錄上可能會(huì)存在競(jìng)爭(zhēng)峦耘。
我們使用了類似Linux的無鎖頁緩存的機(jī)制來實(shí)現(xiàn)對(duì)dentry的無鎖並行訪問剔蹋，需要一個(gè)共享的generation counter。當(dāng)修改一個(gè)dentry時(shí)辅髓，首先獲得dentry的自旋鎖泣崩，然後將counter置0，然後修改dentry洛口，修改後將counter加1矫付。
做比較時(shí)，如果counter值爲(wèi)0那麼等待鎖第焰，否則記錄下counter的值然後拷貝dentry到本地變量买优，如果拷貝之後發(fā)現(xiàn)counter值變了，那麼還是等待鎖∩庇拷貝之後做比較烘跺，如果引用計(jì)數(shù)是0那麼還是回滾到鎖機(jī)制。無鎖協(xié)議增強(qiáng)了可擴(kuò)展性脂崔，它允許不同核心不需要串行化就可以同時(shí)對(duì)同一個(gè)目錄項(xiàng)進(jìn)行查找操作滤淳，減少了鎖競(jìng)爭(zhēng)。
核私有的數(shù)據(jù)結(jié)構(gòu)
我們遇到了三種內(nèi)核數(shù)據(jù)結(jié)構(gòu)限制了可擴(kuò)展性：1.
減少僞共享
一些MOSBENCH應(yīng)用導(dǎo)致了內(nèi)核中發(fā)生僞共享砌左。一些例子是內(nèi)核會(huì)把頻繁寫入的數(shù)據(jù)和頻繁讀取的數(shù)據(jù)放在同一cacheline中娇钱，導(dǎo)致不同的核爲(wèi)僞共享的cacheline發(fā)生競(jìng)爭(zhēng)。Exim的可擴(kuò)展性就受限於物理頁的引用數(shù)和flag標(biāo)記绊困，這些變量被放在了一個(gè)page變量的同一個(gè)cacheline上。memcached适刀，Apache以及PostgreSQL在net_device以及device變量上存在類似的問題秤朗。我們的解決方案是將修改較頻繁的共享數(shù)據(jù)放到不同的cacheline中。
避免不必要的加鎖
核數(shù)目比較小時(shí)笔喉，Linux中的鎖競(jìng)爭(zhēng)不限制MOSBENCH的可擴(kuò)展性取视。16個(gè)核以上之後memcached, Apache等應(yīng)用的可擴(kuò)展性瓶頸在獲得文件系統(tǒng)和虛擬內(nèi)存管理代碼中的自旋鎖和互斥鎖。很多情況下我們可以檢測(cè)不需要鎖的情況常挚，例如我們把一個(gè)保護(hù)所有母頁映射的互斥鎖更換爲(wèi)每個(gè)母頁一個(gè)的粒度更細(xì)的互斥鎖作谭。
評(píng)測(cè)
討論與結(jié)論
雖然我們解決了很多瓶頸，但是不同的應(yīng)用程序和更多的核心可能會(huì)暴露更多的問題奄毡。之前我們就遇到了在24個(gè)核心下不是問題折欠，但是48核心下就成爲(wèi)瓶頸的情況。例如吼过，如果父進(jìn)程和子進(jìn)程不在同一個(gè)核心上锐秦，那麼進(jìn)程創(chuàng)建的開銷可能會(huì)增大很多。我們推測(cè)隨著核心增加而修改內(nèi)核需要對(duì)應(yīng)用和Linux內(nèi)核進(jìn)行最低程度的修改盗忱，而在應(yīng)用程序級(jí)別改進(jìn)可擴(kuò)展性酱床，或者考慮應(yīng)用程序並不是瓶頸在CPU週期，而是在DRAM帶寬等情況可能更有挑戰(zhàn)性趟佃。
總體來說Linux上可以應(yīng)用很多已有的增強(qiáng)可擴(kuò)展性的技術(shù)扇谣，不過Linux固有的大量?jī)?nèi)存共享策略在處理器的緩存一致性協(xié)議不夠高效的情況下仍然是一個(gè)問題。
