2018/06/05 淩晨，雨夜！
遲到的雨，還是來了！
人們幾乎已經逼近了單CPU的處理時延極限，于是人們希望通過多CPU的方式來提高處理帶寬，進而得到更多的處理容量，理論上講，這無可厚非，但現實中，這太難了。
幾乎所有上世紀70年代以來的作業系統都不是為多核CPU并行程式設計而設計的，是以當它們遇到多核CPU的各種問題時，無一不是東填西補，最終情況依然不容樂觀。這裡說一個典型的，就是Linux核心協定棧的可伸縮性(scalable)問題，本文主要描述TCP建立連接配接方面的一個可伸縮性優化措施。
傳統上講，Linux核心協定棧針對同一個Listener的TCP建立連接配接處理主要擁有兩個瓶頸點：
- 單一的accept隊列
- 單一的hash表(其實是兩張，listener hash，establish hash)
TCP的建立連接配接會頻繁操作上述兩個資料結構，在多核CPU情況(後面簡稱SMP)下，為了保證資料的一緻性，lock是繞不開的。不管多少個并行處理的CPU，在TCP建立連接配接時，必然要在操作上述兩個資料結構時被串行化！這是悲哀的。
我們知道，随着CPU核數的增多，每秒能接納的連接配接請求數也會随着增多，但由于上述兩個串行化點的存在，這意味着lock沖突也會相應的增多！串行化的lock沖突意味着什麼？請考慮地鐵站入口，人們從多個大門湧入，最終卻隻有一個安檢點，過了這個安檢點又呈現了多個閘機…
最終，随着CPU核數的增多，性能并沒有能線性地增長，最終的CPU核數/性能曲線便呈現了一種上凸的趨勢。這一切都是因為鎖。
我們來看一下如何進一步拆解上面兩個問題。本文主要描述如何把鎖進行更加細粒度的拆解，下一篇文章聊聊cache相關的内容。
單一accept隊列問題的解鎖
非常幸運，這個問題已經被google的reuseport機制解決了。詳情請自行搜尋reuseport相關的資料。
值得一提的是，新浪的fastsocket在google的reuseport機制基礎上做了一個比較優雅的封裝，使得應用程式不用修改就能享受到reuseport的收益，同時進一步地提高了TCP連接配接的可伸縮性問題。它的項目位址是：https://github.com/fastos/fastsocket
我是在2015年中接觸到這個項目的，當時感覺這種實作非常棒。
單一establish hash表問題的解鎖
根據我上周的壓測，CPS資料擷取過程中，短連結會頻繁操作establish hash表，頻繁調用inet_hash，inet_unhash兩個函數(listener hash并不必在意，因為listener socket比較穩定，不會頻繁生成和銷毀)，其中的熱點在兩個spinlock：
bool inet_ehash_insert(struct sock *sk, struct sock *osk)
{
struct inet_hashinfo *hashinfo = sk->sk_prot->h.hashinfo;
struct hlist_nulls_head *list;
struct inet_ehash_bucket *head;
spinlock_t *lock;
bool ret = true;
WARN_ON_ONCE(!sk_unhashed(sk));
sk->sk_hash = sk_ehashfn(sk);
head = inet_ehash_bucket(hashinfo, sk->sk_hash);
list = &head->chain;
// 以hash bucket來lock！！
lock = inet_ehash_lockp(hashinfo, sk->sk_hash);
spin_lock(lock); // 串行化lock
if (osk) {
WARN_ON_ONCE(sk->sk_hash != osk->sk_hash);
ret = sk_nulls_del_node_init_rcu(osk);
}
if (ret)
__sk_nulls_add_node_rcu(sk, list);
spin_unlock(lock);
return ret;
}
可以看到，在目前的Linux TCP實作中，每一個hash bucket擁有一個spinlock，其實粒度已經夠細了，參見我下面的文章：
Linux socket hash查找的持續優化曆程：https://blog.csdn.net/dog250/article/details/80490859
在以往的年代，這裡的性能更加糟糕！上述代碼是4.14核心，幾乎就是最新的版本了，我們看一下它的示意圖：
上圖的窘局其實是可以破解的，隻需要把per slot的spinlock再做細分即可，改為per slot per CPU的spinlock，其實就是把每一個slot的連結清單攤開成per cpu的即可。這裡決定一個socket應該給哪個CPU先使用一個最簡單的政策，即調用inet_hash的時候哪個CPU在處理，就給哪個CPU。
為此，我們需要修改下面的資料結構：
struct inet_ehash_bucket {
struct hlist_nulls_head chain;
};
這個資料結構便是上圖中slot，我們需要将其改成：
struct inet_ehash_bucket {
// struct hlist_nulls_head chain[NR_CPUS]
struct hlist_nulls_head *chain;
};
我們稍微修改一下insert函數：
bool inet_ehash_insert(struct sock *sk, struct sock *osk)
{
struct inet_hashinfo *hashinfo = sk->sk_prot->h.hashinfo;
struct hlist_nulls_head *list;
struct inet_ehash_bucket *head;
spinlock_t *lock;
bool ret = true;
// 取目前CPU！
int cpu = smp_processor_id();
WARN_ON_ONCE(!sk_unhashed(sk));
sk->sk_hash = sk_ehashfn(sk);
sk->sk_hashcpu = cpu;
head = inet_ehash_bucket(hashinfo, sk->sk_hash);
// 取出對應CPU的list
head = &head[cpu];
list = &head->chain;
lock = inet_ehash_lockp(hashinfo, sk->sk_hash);
// 取出對應CPU的lock
lock = &lock[cpu];
spin_lock(lock);
if (osk) {
WARN_ON_ONCE(sk->sk_hash != osk->sk_hash);
ret = sk_nulls_del_node_init_rcu(osk);
}
if (ret)
__sk_nulls_add_node_rcu(sk, list);
spin_unlock(lock);
return ret;
}
是不是簡單快捷呢？對應的lookup也要修改，在lookup的過程中，不再recheck slot的一緻性，而要recheck CPU的一緻性：
struct sock *__inet_lookup_established(struct net *net,
struct inet_hashinfo *hashinfo,
const __be32 saddr, const __be16 sport,
const __be32 daddr, const u16 hnum,
const int dif, const int sdif)
{
INET_ADDR_COOKIE(acookie, saddr, daddr);
const __portpair ports = INET_COMBINED_PORTS(sport, hnum);
struct sock *sk;
const struct hlist_nulls_node *node;
unsigned int hash = inet_ehashfn(net, daddr, hnum, saddr, sport);
unsigned int slot = hash & hashinfo->ehash_mask;
struct inet_ehash_bucket *head = &hashinfo->ehash[slot];
int cpu = smp_processor_id(), self; // 從目前CPU開始！如果底層有做CPU綁定的話，這樣做就對了。
self = cpu;
begin:
head = &head[cpu];
if (hlist_nulls_empty(&head->chain)) {
goto recheck2;
}
sk_nulls_for_each_rcu(sk, node, &head->chain) {
... // 邏輯不變，省略
}
if (get_nulls_value(node) != cpu) {
cpu = ;
goto begin;
} else if (get_nulls_value(node) == cpu) {
recheck2:
cpu ++;
if (cpu >= nr_cpu_ids)
cpu = ;
if (cpu == self)
goto out;
goto begin;
}
out:
sk = NULL;
found:
return sk;
}
同時，ehash的每一個slot在初始化的時候，都要初始化成per CPU的(當然，我這裡還沒有用per CPU的API)，并且把hlist的null尾用CPU id來初始化！
現在讓我們看看采用per slot per CPU的新方案後，局面在觀感上變成了什麼樣子：
我們知道，spinlock是不可睡眠的，除了被硬中斷打破，所有的CPU在調用inet_hash的時候，幾乎都是可以無競争不自旋立即完成的。但是你可能注意到了，我在上文中沒有提到inet_unhash的調用，我們知道，unhash的時候也是要持有spinlock的，如何來保證unhash的調用者和當初hash的調用者是同一個CPU呢？
答案顯然是不能保證，是以正如nf_conntrack裡unconfirm list和dying list的per cpu處理那般，在調用unhash的時候，cpu變量必須從socket裡面取出來：
void inet_unhash(struct sock *sk)
{
struct inet_hashinfo *hashinfo = sk->sk_prot->h.hashinfo;
spinlock_t *lock;
bool listener = false;
int done;
if (sk_unhashed(sk))
return;
if (sk->sk_state == TCP_LISTEN) {
lock = &hashinfo->listening_hash[inet_sk_listen_hashfn(sk)].lock;
listener = true;
} else {
// 取出hash時的cpu，確定從哪裡insert就從哪裡remove時而一緻性。
int cpu = sk->sk_hashcpu;
if (cpu != smp_processor_id()) {
DEBUG("Shit!:%d", misstat++);
}
lock = inet_ehash_lockp(hashinfo, sk->sk_hash);
lock = &lock[cpu];
}
spin_lock_bh(lock);
...
}
現在問題來了。由于Linux排程器的排程政策影響，很有可能調用unhash時的CPU已經不是當初調用hash時的那個CPU了，最終在别的CPU上處理的unhash過程還是可能和其它一個調用hash過程的CPU競争同一把鎖。然而這是沒有辦法的，排程器不屬于協定棧的範疇，我們能做的，僅僅是避免這種情況的發生，比如通過外部的機制或者工具，對程序和CPU進行強綁定或者弱綁定，盡最大的努力避免程序在CPU之間乒乓！
預告
下一篇準備寫一下單純的Linux核心版本的spinlock存在什麼問題已經如何去優化它，隻要本周大雨持續，我便有更多的時間在雨夜寫作，敬請期待！
我的懶惰愚笨之回顧
做出本文描述的這個優化是我周日一天完成的，後來簡單壓測，發現spinlock熱點真的消失了，TCP CPS在我的虛拟實驗環境下8核心CPU提高了30%多！很可觀的資料了！這還是盲寫第一版的簡單測試，沒有任何進一步調優。當然了，簡單配置一下RPS和CPU綁定還是需要的，我說的是代碼就這樣子了，沒有任何進一步的優化。是以總體上講，我是快樂的！更讓我快樂的是，深圳在接下來的一周，持續局部大到暴雨，我并不曉得局部到底在哪裡，有時間的話，我會去追。
我不但不擅長大段大段地寫代碼，也不擅長搬運東西，切菜洗碗也慢，造成這一切的根源就在于我很懶惰，并且也并不聰明，是以在解決任何問題的時候，我都企圖尋求最簡單的方案，因為我并不聰明，是以如果我找不到，我會去請教聰明的人，希望他們告訴我，迷信點說，我一直都需要點石成金之術，和所有人一樣。
和很多人不同的是，他們很聰明卻也不去思考，而我雖然愚笨，卻一直在努力。
就好比做飯，菜單超過8步驟，我就放棄，因為太麻煩，用料超過10種，放棄，因為太麻煩，但我依然思考我如何能用最簡單的步驟最少的食材做出美味；就好比旅遊，我一個人的話，最多一個背包，或者什麼都不帶，跟别人一起，箱子背包超過3個我就會煩，因為我不擅長搬運，然而我還是會去想如何才能避免搬運大件物品，是以我很擅長打包！
不管怎麼說，懶惰和愚笨已經深入到我生活，工作，學習，娛樂的方方面面，我相信很多人跟我一樣，因為我相信正态分布和幂律，你永遠不要說自己很另類，大部分的所謂自我都處在總人口的長尾。我了解這個事實并且正視它，但很多人不了解且試圖規避它，我可以給他們以幫助并且實際上也真的幫助了。這也許就是我雖然不善交際，但也在很多圈子中的原因吧…