共享變量的并發讀寫

我blog上的老文，已經沉了，在專欄發一下。

在高性能并發伺服器中，對于共享對象的讀寫是最常見的操作之一，比如全局配置類對象的并發讀取和更新，以及更複雜的如copy on write btree、堆棧等的并發讀寫，最基本的操作都可以簡化了解為通過全局共享的指針，并發讀取和更新指針所指向對象的操作。

最簡單的模型如下所示，一個包含了多個字段的結構體：

struct GConf

{

int64_t a;

int64_t b;

int64_t c;

};

可以通過一個全局指針struct gConf *g_conf進行通路。有多個線程會同時讀取或更新這個對象，要求任何時刻讀取到的内容一定是“一緻的”，即讀取到的a/b/c的值一定是相同一次更新的值，而不能出現讀到的a是某一次更新的值，而b或c是另外一次更新的值。

我們假設研發平台為x86_64，指令級的原子操作最多是64位（實際intel提供了128bit的原子操作，但是本文後續的讨論的方法隻用到64bit的原子操作），因為gConf包含三個8位元組整數，無法使用原子操作指令對a/b/c一次性指派，是以必須通過程式算法來保證并發情況下讀取到的内容滿足“一緻性”。

下面開始從易到難讨論5種處理“共享對象并發讀寫”的方法。

1. 讀寫鎖

最簡單樸素的想法是為這個結構配備一個讀寫鎖，讀取操作在讀鎖保護下執行，更新操作在寫鎖保護下執行。這個方法在對象讀取和更新操作都比較簡單，且并發程度不高的情況下是一個不錯的選擇。但是由于讀鎖與寫鎖互相阻塞，在讀取或更新操作比較費時的情況下，會出現更新或讀取線程被阻塞的風險，在高并發的場景下，這種阻塞不可接受。一個執行個體是資料庫系統的全局schema管理器，每次事務都需要讀取schema的内容，而DDL會引起schema更新，它的内容比較複雜，更新操作比較費時，會阻塞住處理事務的線程。

1. 引用計數的問題

為了解決讀寫操作互相阻塞的問題，使用類似Copy on write的方式，每次更新時都構造新的對象，在更新過程中，讀取操作還是讀取舊的對象，更新操作完成後，原子的替換掉指針使其指向新的對象。而被替換掉的對象不能立即釋放，而是要確定這個對象不再被繼續使用的情況下，才能将其釋放掉。是以這裡使用引用計數機制，在讀取前将引用計數加1，讀取完畢後将引用計數減1，當引用計數減到0的時候，表示沒人在使用這個對象，可以将其釋放掉。

引用計數在沒有并發保護情況下面臨的問題是，取得全局指針g_conf和通過這個指針操作對象的引用計數這兩個操作并非原子的。可能存在的情況是，一個線程T1取得g_conf的值儲存到寄存器後，就被切換出去，另外一個線程T2将g_conf替換後，判斷舊的對象引用計數為0，則将其釋放。當T1被切換回來繼續執行時，它在寄存器中儲存的g_conf指向的對象已經被釋放，通路對象引用計數的這一次操作就已經存在非法記憶體通路的風險。

下面兩節讨論兩種解決并發引用計數的方案。

1. 帶鎖的引用計數

解決第2點提出的原子性問題，一個最直接的方式是使用鎖，将讀寫g_conf和修改引用計數兩個操作放在一個獨立全局鎖（g_lock）的臨界區執行，代碼示例如下：

讀取并将引用計數加1：

fetch()

g_lock.rdlock();

g_conf->inc_ref();

ret = g_conf;

g_lock.unlock();

}

将引用計數減1：

revert(ptr)

if( == ptr->dec_ref())

{

free(ptr);           

使用新的對象替換舊對象：

set_new_conf(new_conf)

g_lock.wrlock()

if ( == g_conf->dec_ref())

free(g_conf);           

new_conf->inc_ref();

g_conf = new_conf;

在實際場景中，通常讀取g_conf的操作更多且并發量大，而替換g_conf的操作不會經常發生，是以讀取g_conf時加共享鎖，替換g_conf時加互斥鎖。

使用鎖保護引用計數的方式在高并發的情況下存在一些局限：一方面可能存在讀者或寫者被餓死的情況；另一方面多個寫者無法并發，應用在copy on write btree等資料結構中時，多個寫者互相阻塞的問題會影響到整個資料結構的并發性能。

1. 無鎖的引用計數

是以，一個更進一步的設計是使用無鎖的引用計數，即無論讀取g_conf還是替換g_conf都不在鎖中進行，如下圖所示：

RefNode的結構包含了指向GConf對象的指針data_ptr，以及引用計數ref_cnt，自增序列号seq_id，ref_cnt和seq_id長度都為4位元組且位址連續，可以經由一次8位元組的原子操作進行原子性的修改和讀取。每次構造新的GConf對象的要同時配置設定新的RefNode來儲存GConf對象的位址。

RefNode對象的配置設定和釋放由專用的配置設定器進行配置設定和重用，一旦配置設定就不會釋放回系統。引用計數的加1和減1，操作的是RefNode對象的ref_cnt字段，當引用計數減為0時，将data_ptr指向的對象釋放，并将seq_id加1，然後将RefNode對象釋放給記憶體配置設定器。已釋放回配置設定器的RefNode對象仍然可以被安全的通路到。

替代全局GConf指針，我們增加了一個被稱為GNode結構體的全局對象稱為g_node，它包含了指向RefNode對象的指針稱為node_idx，和這個RefNode中seq_id字段的值node_seq。node_idx和seq_id長度都為4位元組且位址連續，可以經由一次8位元組的原子操作進行原子性的讀取和替換。

讀取和替換操作的代碼示例如下：

将引用計數加1并傳回：

GNode tmp_g_node = atomic_load(g_node);

while (true)

if (tmp_g_node.node_idx->atomic_check_seq_and_inc_ref(tmp_g_node.node_seq))
{
  ret = tmp_g_node.node_idx;
  break;
}
else
{
  tmp_g_node = atomic_load(g_node);
}           

revert(node_idx)

if (node_idx->atomic_dec_ref_and_inc_seq())

free(node_idx->data_ptr);
free_list.free(node_idx);           

RefNode *new_node = free_list.alloc();

new_node->ref_cnt = 1;

new_node->data_ptr = new_conf;

GNode new_g_node;

new_g_node.node_seq = new_node->seq_id;

new_g_node.node_idx = new_node;

GNode old_g_node = atomic_store_and_fetch_old(&g_node, new_g_node);

if (old_g_node.node_idx->atomic_dec_ref_and_inc_seq())

free(old_g_node.node_idx->data_ptr);
free_list.free(old_g_node.node_idx);           

其中幾個原子操作的作用：

1. RefNode::atomic_check_seq_and_inc_ref原子性的判斷如果seq_id等于傳入參數就将ref_cnt加1，并傳回true，否則傳回false。
2. atomic_store_and_fetch_old原子性的将第二個參數指派給第一個參數，并傳回第一個參數的舊值。
3. RefNode::atomic_dec_ref_and_inc_seq原子性的将ref_cnt減1，并判斷ref_cnt如果已減為0，則将seq_id加1并傳回true，否則傳回false。

工程實作上，為了達到node_idx長度隻能有4位元組的要求，RefNode配置設定器設計為定長數組，node_idx為數組下标，使用定長無鎖隊列作為配置設定器來維護空閑的node指針。一般來說一個

買遊戲平台

線程隻會增加一次引用計數，是以對于維護GConf這樣全局隻有一個的對象，定長RefNode數組的長度初始化為與線程個數相等就夠用了。

1. HazardPointer

引用計數基本可以解決共享對象并發讀寫的問題，但它仍然存在一些不足：第一，每次讀取都需要使用原子操作修改全局引用計數，高并發情況下的對同一個變量的原子操作可能成為性能瓶頸；第二，管理RefNode對象的無鎖配置設定器有額外的管理和維護成本，增加的實作複雜度；第三，針對每個共享對象都需要維護N個（N為線程個數）RefNode，如果共享對象數量較多（比如Btree節點），為節省空間，還需要額外的機制來避免大量使用RefNode。

是以再介紹一種被稱為HazardPointer的思路，它由Maged M. Michael在論文“Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects”中提出，基本思路是将可能要被通路到的共享對象指針（成為hazard pointer）先儲存到線程局部，然後再通路，通路完成後從線程局部移除。而要釋放一個共享對象時，則要先周遊查詢所有線程的局部資訊，如果尚有線程局部儲存有這個共享對象的指針，說明這個線程有可能将要通路這個對象，是以不能釋放，隻有所有線程的局部資訊中都沒有儲存這個共享對象的指針情況下，才能将其釋放。

g_hp_array[N]; //儲存每個線程局部資訊的數組，N為線程個數

讀取操作：

while(true)

g_hp_array[thread_id] = ret;

if (g_conf == ref)

break;           

else

g_hp_array[thread_id] = NULL;           

// 讀取邏輯代碼…

g_hp_array[thread_id] = NULL;

retired_ptr = atomic_store_and_fetch_old(&g_conf, new_conf);

found = false;

for (i = ; i < g_hp_array.length(); i++)

if (retired_ptr == g_hp_array[i])
{
  found = true;
  break;
}           

if (!found)

free(retired_ptr);           

HazardPointer的設計解決了引用計數原子操作的性能瓶頸，避免了實作額外RefNode無鎖配置設定器的複雜度。但是同時引入一個新的問題：由于回收記憶體的操作需要周遊查詢全局數組g_hp_array，代價比較大，通常工程上的做法是将待回收的指針暫存線上程局部，等數量超過一個配置門限時，才進行批量回收。使得回收記憶體産生延遲，并且回收操作本身由于需要周遊數組，也會消耗較多的時間。

關于并發場景的問題，由于回收操作便利g_hp_array并不能保證原子的周遊，而HazardPointer的設計要求對象已經被放入g_hp_array後是能夠安全通路的，是以可能存在如下時序：

1. 讀取線程拿到g_conf指針存入局部變量ret
2. 更新線程将g_conf指針替換，掃描g_hp_array沒有找到g_conf，釋放g_conf記憶體
3. 讀取線程将剛剛拿到的ret放入g_hp_array，然後開始使用ret，而此時ret指向的記憶體已經釋放

為了處理這個問題，如上述僞代碼所示，讀取線程需要增加double check邏輯，判斷如果從拿到g_conf到放入g_hp_array之間，可能有回收邏輯周遊過g_hp_array，則要重試。

因為替換g_conf意味着要将舊的g_conf釋放，而釋放意味着要先會周遊g_hp_array，是以讀取線程隻需要在将g_conf放入g_hp_array後，判斷g_conf是否變化，如果變化了，則說明g_conf可能正好在從拿到g_conf到放入g_hp_array之間被釋放了，是以需要重試。

1. HazardVersion

HazardPointer的實作簡單，但是與引用計數法有着相似的不足：需要為每個共享變量維護O(N)個（N為線程個數）槽位，使用者需要仔細分析算法以盡量減少同時存在的hazard pointer 或者引入其他機制封裝多個共享變量稱為一個hazard pointer。這樣就給使用者帶來了比較大的難度，HazardPointer機制也與具體資料結構的實作比較緊的耦合在一起。

是以在HazardPointer基礎上發展出了被稱為HazardVersion技術，它提供類似lock一樣的acquire/release接口，支援無限制個數共享對象的管理。

與HazardPointer的實作不同：首先全局要維護一個int64_t類型的GlobalVersion；要通路共享對象前，先将當時的GlobalVersion儲存到線程局部，稱為hazard version；而每次要釋放共享對象的時候先将目前GlobalVersion儲存在共享對象，然後将GlobalVersion原子的加1，然後周遊所有線程的局部資訊，找到最小的version稱為reclaim version，判斷如果待釋放的對象中儲存的version小于reclaim version則可以釋放。

g_version; //全局GlobalVersion

g_hv_array[N]; //儲存每個線程局部資訊的數組，N為線程個數

g_hv_array[thread_id] = g_version;

ret = g_conf;

g_hv_array[thread_id] = INT64_MAX;

retired_ptr->set_version(atomic_fetch_and_add(&g_version, 1));

reclaim_version = INT64_MAX;

for (i = ; i < g_hv_array.length(); i++)

if (reclaim_version > g_hv_array[i])
{
  reclaim_version = g_hv_array[i];
}           

if (reclaim_version > retired_ptr->get_version())

free(retired_ptr);           

可以看到，讀取操作先儲存了GlobalVersion到線程局部，然後去讀取g_conf指針，雖然可能同時發生的回收操作周遊g_hv_array并不保證原子性，但是即使一個更小的hazard version被放入g_hv_array而錯過了周遊，也不會有風險。

因為回收操作是先更新g_conf指針後周遊g_hv_array，而讀取操作是先更新g_hv_array後讀取g_conf指針，是以最壞情況下讀取操作與回收操作同時發生，且讀取操作放入g_hv_array的hazard version被回收操作周遊時錯過，那麼讀取操作讀到的g_conf一定是被回收操作更新之後的，本次不會被回收，可以安全的通路。

HazardVersion相對HazardPointer，在用法上更加簡單，無需針對具體的資料結構進行分析，局限是需要在被管理的對象中儲存version。其次，與HazardPointer一樣，由于周遊g_hv_array比較費時，是以也需要引入類似的延遲回收機制。需要注意的是，它的缺點也比較明顯，一旦出現一個線程長時間不釋放HazardVersin時，會阻塞住後面更大Version對象的釋放。

1. 總結

本文讨論了“讀寫鎖”、“帶鎖的引用計數”、“無鎖的引用計數”、“HazardPointer”、“HazardVersion” 五種方法來處理共享對象的并發讀寫問題，在實際工程領域，“帶鎖的引用計數”比較常見，在特定場景下優化讀寫鎖可以得到不錯的性能，并且很易于了解和實作；“無鎖的引用計數”實作複雜但并發讀寫性能卓越，在已開源的OceanBase版本中也有實踐；“HazardPointer”實作簡單，但是了解和使用都較複雜；“HazardVersion”是一種基于“HazardPointer”的創新思路，有一定的局限性，憑借簡單易用的接口，可以在很多場景替代“HazardPointer”。