简介

这篇文章在Linux2.6.35上检测了MOSBENCH应用是否scale，也就是在单核和在48个核上面的性能是否线性增长。
在找到不scale的原因以后，进一步分析是因为application的问题，linux kernel的问题还是底层硬件的问题。之后要么修改application的结构，要么修改application使用kernel service的方式，要么修改kernel，总能改进scalability。

本文的贡献：

1. 提出了sloppy counters方法用于解决shared counter不scale的问题。该方法只需要修改shared counter不scale的部分，而不需要对所有引用该counter的地方进行修改。
2. 一个内核scalability测试集：MOSBENCH。
3. 各种改进scalability的小技巧。
4. 结论：并不需要修改传统内核设计方式来达到scale的目标。

MOSBENCH

說明：全部測試項目使用駐內存tmpfs文件系統來避免磁盤讀寫瓶頸。

• 郵件服務器
  Exim使用一個master進程來監聽SMTP請求，對每個新連接，fork一個新進程處理。這個新進程負責接收郵件，將郵件隊列到一個繞軸目錄中（目錄中每個文件是一個郵件），接下來分發郵件到用戶郵件文件，刪除繞軸目錄中的郵件，在log中記錄等等。每個進程需要fork兩次來發送一封郵件，單核運行花費69%的時間在內核中，包括進程創建和小文件創建以及刪除。
• Memcached
  單個Memcached服務器在多核中運行時，會瓶頸在保護key-value哈希表的內部鎖上，爲了避免這一點我們運行多個Memcached服務器，每個都有自己的端口，客戶端確定地分佈式訪問這些服務端。單核時80%時間在內核中，主要包括網絡棧的使用。
• Apache
  配置爲每個核運行一個進程，每個進程用一個線程池，線程池中一個線程負責接受連接，其他線程負責處理連接。單核運行時Apache花費60%的時間在Kernel上，對文件系統，網絡棧壓迫較大，因爲其對每個請求都要打開並且統計一個文件。
• 數據庫 PostgreSQL
  和其他項目不同，PostgreSQL中有大量的數據結構共享和同步操作。將數據庫表保存爲文件，並且被所有postgreSQL進程共享訪問。每個連接開一個進程，利用內核鎖機制同步和負載均衡這些進程，並且通過共享網絡接口的TCP socket和客戶端通訊。對於一個只讀測試，PostgreSQL在單核上1.5%的時間在內核中，48核82%的時間在內核中。
• 並行編譯
  我們使用編譯linux內核的方式來評測gmake。gmake創建了比CPU核心數更多的進程並且大量讀寫文件，單核時7.6%的時間在內核裏，但是整體耗時瓶頸在它所運行的編譯器上。
• 文件索引
  Psearchy是用來索引和查詢網頁的工具。pedsort在每個核上運行一個索引器進程，進程間共享輸入文件。每個核跑兩個階段，第一階段是從工作隊列中拉出輸入文件，讀文件並且把每個單詞的位置輸入進每個核一個的哈希表中，當哈希表大到一定程度以後對其按照字母排序，寫到磁盤上一個臨時索引文件中然後繼續讀文件。這個階段既是CPU密集的也是文件系統密集的。採用排序的方式先處理大文件，到工作隊列爲空時，每個核合併它生成的所有臨時索引文件，把單詞位置列表合併起來，生成一個保存了每個單詞位置的索引文件以及一系列的BDB文件保存了每個單詞和它在文件中的偏移量。這一階段主要是文件系統密集的。單核在內核中時間是1.9%，48核則是23%，這是scalability問題導致的。
• MapReduce
  臨時表存放在內存中，對內核的內存分配和page fault處理有壓力，單核3%的內核運行時間，48核則爲16%。

內核優化

下面的表格總結了每個scalability瓶頸。

1. 並行accept （Apache）
   不同的accept系統調用共用一個socket，導致競爭。
   解決方案：每個核使用備用隊列（backlog queue）存儲監聽socket。
2. dentry 引用計數（Apache， Exim）
   文件名解析過程在目錄項（directory entry）的引用計數變量上存在競爭。
   解決方案：使用sloppy counter保存目錄項對象的引用計數。
3. 掛載點vfsmount引用計數 （Apache， Exim）
   遍歷文件名路徑的時候，在掛載點的引用計數變量上存在競爭。
   解決方案： 使用sloppy pointers保存掛載點的引用計數變量。
4. 請求目錄項的自旋鎖。
   遍歷文件名路徑的時候，在每個目錄項的自旋鎖上存在競爭。
   解決方案：在dlookup中使用無鎖算法。
5. 掛載點列表自旋鎖競爭
   解決方案：爲每個CPU核心分配掛載點列表的緩存
6. 分配DMA緩衝區時在內存節點0上的自旋鎖上存在競爭
   解決方案：在本地內存節點上分配DMA緩衝區
7. net_device和device上的只讀域存在僞共享
   解決方案：在cache line上設置只讀域標記。
8. 保護inode列表的全局鎖在不同CPU核心間存在競爭
   解決方案：避免不必要的鎖請求
9. lseek中保護每個inode的互斥量上存在競爭
   解決方案：使用原子讀操作避免請求互斥量
10. 母頁的軟缺頁錯誤導致對每個進程的互斥量存在競爭
    解決方案：將per-process的互斥量修改爲per-super-page。（增加鎖粒度）
11. 清空母頁時同時清空了CPU Cache
    解決方案：使用非cache指令來清空母頁（super-page）。

當需要串行執行的操作越多，增加CPU核心所能提供的性能提升也就越少。根據Amdahl定律當25%的指令是串行執行的時候，再多的CPU核心也不能提供4倍以上的增速。這裏我們列出一系列的需要串行執行的操作：

1. 不同的任務請求同一共享數據結構上的鎖。核越多，等待該鎖的時間也就越長。
2. 不同的任務寫同一個共享內存地址，因此核越多，緩存花越長的時間在獨佔模式（exclusive-mode）等待。使用無鎖數據結構也不能解決這個問題。
3. 不同的任務搶佔有限的硬件緩存。即使這些任務不共享內存也同樣存在這個問題。
4. 不同的任務搶競爭其他硬件資源，例如核心間DRAM帶寬，這導致額外的核花時間在等待上面而不是計算。
5. 可能有的核特別忙而有的核特別閒，調度不合理

很多可擴展性的問題表現爲因爲一個核心要使用另外一個核寫的數據導致緩存未中（cache miss）的現象。這是兩個核競爭鎖和競爭無鎖可變數據時常見的現象。具體細節取決於緩存一致性協議。例如每個核有一個數據緩存，當一個核寫其他核緩存好的數據時，一致性協議要求該核在找到其他所有核的緩存並且無效化它們以後才能寫入。另一種場景是當一個核準備讀其他核剛剛寫完的數據時，一致性協議要求只有當找到了寫好改變以後數據的那塊緩存，並且告訴那塊緩存數據已經被拷貝之後才能讀入。這些操作的耗時和RAM讀取類似（幾百個週期），因此核間共享數據會導致不成比例的性能問題。

修改共享數據時應用緩存一致性協議會導致兩種可擴展性問題。第一，緩存一致性協議會串行化對同意緩存行的修改，阻礙並行化加速。其二，極端情況下該協議會耗盡核間帶寬，進一步使得性能無法隨着CPU核心數目增加而提高。因此我們需要通過讓可寫數據只分佈在一個核上的方式來提高性能和可擴展性。

另外情況是總吞吐率隨着核心數目增加而降低，因爲每個等待的核心都在拖慢工作核心的進度。舉例來說不可擴展的自旋鎖導致了正比於正在等待的核心數量大小的核間通訊佔用帶寬，這些核間通訊拖慢了持有鎖的核心。例如，如果請求鎖的核心當前正持有鎖，那麼需要消耗十幾個週期。如果請求鎖的核心當前並不持有鎖，在無競爭的情況下需要消耗幾百個週期，而競爭情況下要消耗的比這多很多。

性能往往是可擴展性的敵人。使用低效的算法有時反而能增強可擴展性，因爲可以讓每個核心計算自己的部分並且不共享可寫數據。相應地提高算法複雜性往往意味着使用更多的共享數據因此可擴展性也更差。這在我們的評測中印證了很多次。

一些可擴展性瓶頸很難解決，因爲共享數據結構的語義就是要求串行執行。然而我們常常可以修改實現使得核心之間不需要彼此等待。例如現有的Linux內核會把一系列的線程劃分爲每個核自己獨有的調度隊列，通常情況下每個核僅僅讀寫核對自己的隊列加鎖。有很多類似的改進能夠避免鎖競爭和對內部數據的競爭。使用無鎖數據結構，或者細粒度加鎖等常見方式也可以改進可擴展性。

多核數據包處理

Linux網絡棧使用隊列來連接處理網絡包的不同階段。收到一個包以後會經過多個隊列處理之後才會進入per-socket 隊列，應用才通過read或者accept系統調用從這個per-socket隊列中讀取數據。理想狀態下每個數據包，隊列以及連接應該在同一個核上進行，這樣這能避免核間的緩存miss或者隊列鎖的開銷。
有兩種方法來實現這點，第一是硬件的多重隊列，第二種是軟件包路由算法。在多重隊列的情況下，Linux可以爲每個核分配一個硬件隊列，對發出的包就簡單地放在這個隊列裏面。進入的包則由硬件根據路由算法（可以根據源IP核端口號）來幫助把包放到某一特定隊列上，因此也能放到特定的CPU核上。IXGBE驅動可以做到更多：它可以每20個TCP包採樣一次，然後根據該TCP連接對應的CPU核心是哪個來更新硬件的網絡包路由表，根據這個路由表來將TCP包分發到相應的核心。這種設計對長連接很有效，但是對短連接效果不好，因爲短連接TCP連接變動情況很大，根據採樣結果進行路由的效果不好。

Apache的情況是所有的CPU核心都通過同一個socket來接受連接（不同的進程共享同一個socket並同時在這個socket上面進行accept系統調用）。我們修改了accept的實現使得網絡包被分發到本地的核心上，因此如果接受連接和處理連接是在同一個核上進行，那麼所有關於該連接的動作都只在一個核上面進行，這麼做也能幫助減輕對同一socket上面單一連接隊列上鎖的競爭。
爲了實現這個修改，我們配置IXGBE驅動，使用網絡報文頭部的哈希值來把來自同一個連接的網絡包分發到處理該連接的核心上，然後放進per-core的存儲隊列裏面，accept調用從這個隊列裏面拿請求，如果accept發現隊列爲空，那麼它會試圖去另外一個核的隊列裏面拿一個請求以實現負載均衡。如果在處理連接的過程中線程被遷移到另外一個核心上，那麼也許組合一下這種方法以及之前的採樣方法是最好的選擇。

Sloppy pointers

Linux使用共享指針來進行引用計數。如果多個核心都想更新這個引用計數那麼就會引起競爭。即使使用無鎖原子加法和減法操作也沒有用，因爲底層硬件一致性依然會串行化這一系列操作。MOSBENCH在目錄項，掛載項，路由表項這三個對象的引用計數上存在瓶頸，此外在TCP和UDP的內存使用統計計數量上也存在競爭。
我們的解決方案是使用Sloppy pointers，每個核心維護自己一個局部計數器，同時有一個共享的全局計數器。當增加1個引用的時候，會首先試圖從局部計數器中減少1，如果局部計數器是0，那麼會讓全局計數器加1。中心思想是全局計數器的值=（所有引用的數目+所有局部計數器的大小）。這樣很多時候只需要訪問局部計數器就能修改引用計數（因爲同一個核上面修改引用計數不需要訪問共享的全局計數器）。另外的好處就是全局計數器得到保留因此不需要修改已有代碼。

sloppy pointer的好處是不需要修改原來使用共享指針部分的代碼。但是由於在刪除資源時sloppy pointer需要協調處理本地指針和全局指針的關係，因此會有大量開銷。另外它的空間開銷與CPU核心的數目成正比。

無鎖比較

我們注意到MOSBENCH應用有時會瓶頸在對目錄項緩存的名稱查找上。目錄項緩存（directory entry cache）是將目錄和文件名映射到dentry上的一個哈希表，dentry中包含了對應文件的inode。在找到了候選的dentry之後，會有一個per-dentry的自旋鎖鎖住該dentry防止其他核心並行訪問，在常見前綴/usr等目錄上可能會存在競爭。
我們使用了類似Linux的無鎖頁緩存的機制來實現對dentry的無鎖並行訪問，需要一個共享的generation counter。當修改一個dentry時，首先獲得dentry的自旋鎖，然後將counter置0，然後修改dentry，修改後將counter加1。
做比較時，如果counter值爲0那麼等待鎖，否則記錄下counter的值然後拷貝dentry到本地變量，如果拷貝之後發現counter值變了，那麼還是等待鎖。拷貝之後做比較，如果引用計數是0那麼還是回滾到鎖機制。無鎖協議增強了可擴展性，它允許不同核心不需要串行化就可以同時對同一個目錄項進行查找操作，減少了鎖競爭。

核私有的數據結構

我們遇到了三種內核數據結構限制了可擴展性：1.

減少僞共享

一些MOSBENCH應用導致了內核中發生僞共享。一些例子是內核會把頻繁寫入的數據和頻繁讀取的數據放在同一cacheline中，導致不同的核爲僞共享的cacheline發生競爭。Exim的可擴展性就受限於物理頁的引用數和flag標記，這些變量被放在了一個page變量的同一個cacheline上。memcached，Apache以及PostgreSQL在net_device以及device變量上存在類似的問題。我們的解決方案是將修改較頻繁的共享數據放到不同的cacheline中。

避免不必要的加鎖

核數目比較小時，Linux中的鎖競爭不限制MOSBENCH的可擴展性。16個核以上之後memcached, Apache等應用的可擴展性瓶頸在獲得文件系統和虛擬內存管理代碼中的自旋鎖和互斥鎖。很多情況下我們可以檢測不需要鎖的情況，例如我們把一個保護所有母頁映射的互斥鎖更換爲每個母頁一個的粒度更細的互斥鎖。

評測

討論與結論

雖然我們解決了很多瓶頸，但是不同的應用程序和更多的核心可能會暴露更多的問題。之前我們就遇到了在24個核心下不是問題，但是48核心下就成爲瓶頸的情況。例如，如果父進程和子進程不在同一個核心上，那麼進程創建的開銷可能會增大很多。我們推測隨着核心增加而修改內核需要對應用和Linux內核進行最低程度的修改，而在應用程序級別改進可擴展性，或者考慮應用程序並不是瓶頸在CPU週期，而是在DRAM帶寬等情況可能更有挑戰性。
總體來說Linux上可以應用很多已有的增強可擴展性的技術，不過Linux固有的大量內存共享策略在處理器的緩存一致性協議不夠高效的情況下仍然是一個問題。