Arachne: Core-Aware Thread Management

osdi參考連結：https://www.usenix.org/conference/osdi18/presentation/qin

1、 簡介

Arachne是斯坦福大學開發的一個使用者態執行緒排程方案(協程)，適用的場景是短生命週期的應用，如memcached和RAMCloud這類，他們的server執行緒生命週期通常只有幾us。使用傳統linux執行緒會帶來較大的開銷和延時。
Arachne的核心思想是讓應用程式根據負載確定自己需要的core數量，程式知道哪些核是分配給自己的，同時控制適量的執行緒在這些core上執行；而core arbiter用來給應用程式分配這些core。
Arachne執行緒庫經過最佳化，可最大限度的減少cache-misses，同時它可以在220ns內啟動新的使用者執行緒。
由於Arachne是在使用者態實現的，完全不需要修改核心。

2、 使用者態執行緒庫的場景

Arachne被設計用於那些需要處理大量短生命週期請求的服務，同時還要保證較低的延時，比如memcached。
Memchached處理一個請求的時間大概是10us，正常情況下，核心執行緒的開銷太大，無法為所有的請求建立單獨的執行緒；所以memcached使用了執行緒池來處理這個問題，在程式啟動時，建立一批執行緒池，當需要處理新的請求時，由一個分發執行緒將請求分派到某個工作執行緒來處理。
但執行緒池的執行緒數量固定的，在執行時，當可用core比執行緒數少時，將造成多個執行緒共用同一個core，這會導致未被排程的執行緒增加很大的延時，最好的情況是，一個工作執行緒需要單獨使用一個core。
此外，在低負載期間，每個工作執行緒都可能處於idle狀態，這將導致部分core進入節能樣式，而從節能樣式被喚醒的開銷又非常大，這也會增加延時。Arachne嘗試在低負載期間在較少的core上高密集的的執行，這也能獲取更好的表現。
預設情況下，Arachne使用忙轉的排程策略，這將使core的佔用率達到100%。

3、 架構

傳統應用在應對低延遲和高吞吐量時，很難權衡。大部分時候，應用程式無法告訴os他們需要多少core，也不知道哪些core是分配給自己使用的。因此應用程式無法調整其內部並形象以匹配可用的core，這可能導致部分core的利用率不足或者負載過高，而需要透過負載均衡來維持的話，將帶來很多額外的開銷，且延遲無法保證。
Arachne作為一個執行緒管理器，透過讓應用程式看到它們正在使用的cores來解決這些問題，core arbiter給程式分配專用core，且分配的core可以保持給該應用使用較長的週期(幾十ms)。應用程式知道自己分配到了哪些core，從而可以在這些cores上合理的分佈它的工作執行緒。
Arachne的特點如下：

• Arachne可以預估應用程式所需的core數量。
• Arachne允許每個應用程式定義一個核心策略，該策略在執行時確定應用程式需要多少核心以及如何將執行緒置於可用核心上。
• 它使用未就緒佇列的排程佇列，該佇列為執行緒建立，排程和同步提供了低延遲和可擴充套件的機制。
• 完全在使用者態實現，不需要修改核心；core arbiter使用cpuset實現。Os在執行Arachne程式的同時，也可以執行非arachne的執行緒。

圖1 Arachne架構

Arachne的架構如圖1所示，包括三個元件：

• core arbiter包含一個獨立的使用者態行程用於管理cores並且將cores分配給不通的應用程式；同時每個應用程式連結一個arbiter lib用以和core arbiter做通訊。
• Arachne runtime用於建立一些核心執行緒並且用來管理和執行app的工作執行緒(個人理解這裡的kernel thread是普通的linux執行緒，類似vcpu的概念，透過vcpu管理真正的業務執行緒)，並且這裡實現了執行緒的建立/刪除、鎖、條件變數，並且這些實現都是在使用者態，比傳統核心實現要快得多。
• Arachne runtime還包含一個core的策略器，這個策略器透過arachne runtime收集應用程式的效能指標(負載等)，根據指標決定分配多個cores，同時決定哪些執行緒在哪些cores上執行。
• 使用者可以實現自己的執行緒庫，用以代替archane runtime和core policy。
• 工作執行緒的排程採用非搶佔樣式，如果應用需要長時間執行，需要偶爾呼叫yeild()防止同一個core上其他的執行緒被餓死。

Arachne內部管理兩種cores，一種是託管核，一種是非託管核。其中託管核用來建立arachne執行緒且託管核是由core arbiter來分配的，只有arachne的執行緒才會在託管核上執行；而應用自己建立的，如呼叫std::thread建立的執行緒，將全部步署在非託管核上執行。
在core arbier啟動時，會將所有的物理cores分配到非託管核，並且將所有執行緒放入該非託管核群，這些執行緒建立的新執行緒也在非託管核。後期為了將core分配給Arachne程式，core arbiter會將core從非託管核群刪除，納入到託管核群，並分配給請求者，當應用程式不再需要這些託管核時，core arbiter可以將他們再次收回，並歸還到非託管核群。這種架構可以讓一個程式中同時存在arachne執行緒核普通linux執行緒，當然，託管核群的優先順序比非託管核群要高，也就是說有申請core的請求過來，會優先將非託管群的core分配出去，但是非託管群最少也會保留一個core。

4、 降低cache-miss

在傳統排程上，一個core上有一個或者多個runnable queue，當正在執行的執行緒睡眠或者退出時，排程器需要從runnable queue獲取一個新的執行緒來執行，而從runnable queue新增或刪除一個執行緒，需要修改的變數很多，如果queue是多核共享的，即使queue是lockless的，這也會引起大量的cache-miss。所以我們希望執行緒被喚醒時，必須將它新增到它原本所在的core上，但喚醒操作可能是由其它core上的執行緒來呼叫的，這將引起競爭。同時，執行緒的排程狀態也會有讀寫競爭，通常會使用鎖來保護它，但鎖也會導致額外的cache-miss。
為了消除這些cache-miss，arachne不使用runnable queue，而是對當前core相關的所有執行緒進行掃描，直到找到一個可以執行的執行緒為止。
這種設計是基於以下兩個前提：

• 在給定時間內，一個core只為幾個工作執行緒提供使用。
• 遍歷執行緒最大的開銷，還是在執行緒state值的cache-miss，這個state通常由不同的core來操作以喚醒執行緒。變數的cache被其他核寫入並掃清直到本核能讀取到新值，大概需要經歷100或更多的cycles，而排程器可以利用這個時間週期，繼續遍歷大量的執行緒。

Arachne對執行緒state變數做了無鎖處理，在執行緒管理結構體中，用一個64位的wakeupTime來標示，當wakeupTime比當前cpu的cycles小，排程器認為該執行緒是可執行的，當排程器切換到該執行緒之前，排程器會將它的wakeupTime置為max。當執行緒進入阻塞時，不需要修改wakeupTime，因為max大於當前cpu cycles計數，任務不會被再次執行。要喚醒執行緒，只需將wakeupTime被設定為0，排程器在下一次排程時，會發現該執行緒成為一個可執行的狀態，因為沒有競爭條件，所以該state不需要使用鎖來保護。

5、 效果

5.1、Memcached:

註：Memcached-A表示使用Arachne版本的mamcached

5.2、RAMCloud:

從效能對比來看，在memcached和ramcloud這種特殊場景下，arachne帶來的效能提升，包括延時和吞吐率都有比較明顯的提升。