线性一致性理解Linearizability
文章目錄
- 1. 線性一致性來源
- 2. 線性一致性解析
- 1. 單線程執行的正確性
- 2. 并發的運行歷史分析
- 3. 應用程序的線性化判斷
- 1. 程序線性化的理論要求
- 2. linearization point 檢查
- 3. 簡單總結
- 1. 程序中對共享對象的操作的可線性化
- 2. 應用程序的線性一致性
- 3. 分布式系統的可線性化(線性一致性)
終于理解了線性一致性，很開心
1. 線性一致性來源
??線性一致性是Maurice P. Herlihy 與 Jeannette M. Wing共同提出的關于并行對象行為正確性的一個條件模型,在《多處理器并發編程的藝術》這本書中提及。原文用的是Linearizability, 目前看翻譯有的叫線性一致性,有的叫可線性化性。 這個模型的解釋其實還是挺復雜的，下面d大部分的理解來源于stackoverflow的這篇解答
2. 線性一致性解析
??當我們在解釋并發處理是否正確的時候，我們常常是使用偏序(partial order)來拓展到全局有序(total order),查看并發操作的歷史序列是否是正確的要比直接觀察過程來判斷并發操作是否是正確的要容易的多。這里的操可以是一個方法調用,后面我們也是拿方法調用作為一個操作來進行舉例闡述。
1. 單線程執行的正確性
??首先，我們先把并發操作放在一邊，先考慮單個線程的處理程序。我們假設有一個歷史的處理序列H_S(history sequence), 這個歷史的處理序列由一系列的events構成,event可能是Invoke也可能是Response,這個時候這個操作序列是這樣的：每個Invoke后面都緊跟著他對應的Response.這里的緊跟著就是在Invoke_i 和 Response_i 之間不會有其他的invoke或者response.也就是對方法的調用是串行的。
H_S有可能是這樣的
因為沒有并發，這里我們很容易就可以判斷出來H_S是一個正確的操作序列，這里所謂的正確就是這個序列產生的結果是和我們編寫程序時候預期的結果是一樣的。這樣的描述可能有點抽象，我們可以舉個例子，把操作對應的方法定義如下
//int i = 0; i is a global shared variable. int inc_counter() {while(true){int old_i=i;int j = old_id++;if(cas(&i,old_i,j)==0){ //沒有操作成功，就循環操作，操作成功了就返回continue;}else{return j;}} }對應的cas操作是一個原子操作
int cas(long *addr, long old, long new) {/* Executes atomically. */if(*addr != old)return 0;*addr = new;return 1; }則對inc_counter()的調用，使用單線程的話，判斷程序是否是正確的，就是如果我們不停的調用inc_counter(),對應的Ri(res)中的結果res(i)的值肯定是遞增的,滿足了是遞增的，那么就是和我們編寫程序想要達到的目標是一致的。
2. 并發的運行歷史分析
??實際情況下，程序的運行大多是多線程的，有可能我們的應用程序中會有A B兩個線程在運行這個方法，當我們運行項目的時候我們也可以得到一個并發的運行歷史，稱之為H_C (History_Concurrent),像在H_S中一樣,我們也使用Ii~Ri來表示方法的調用。因為兩個線程是并發的，所以A B產生的調用處理在時間上可能是相互重疊的，所以從時間維度上我們可能會得到下面的一個操作歷史
thread A: IA1----------RA1 IA2-----------RA2 thread B: | IB1---|---RB1 IB2----|----RB2 || | | | | | | || | | | | | | | real-time order: IA1 IB1 RA1 RB1 IB2 IA2 RB2 RA2------------------------------------------------------>time對應的是這樣的
H_C : IA1 IB1 RA1 RB1 IB2 IA2 RB2 RA2這個時候我們應該如何判斷序列H_C是正確的呢，我們可以根據下面的規則將H_C 進行重排序得到H_RO(History_Reorder)
如果一個方法調用m1 發生在另一個m2調用之前，則m1在重新排序的序列中必須在m2之前。
在這種規則下，我們說H_C等效于H_RO（history_reorder）。
這意味著如果Ri在H_C中的Ij前面，則必須確保Ri在重新排序的序列中仍在Ij的前面，i和j沒有它們的順序，我們也可以使用a，b，c …。
H_RO有兩個屬性
在不考慮上面的兩條屬性的情況下，我們可以將H_C重排序為以下幾種類型(下面用H_S來代表H_RO)
H_S1: IA1 RA1 IB1 RB1 IB2 RB2 IA2 RA2 H_S2: IB1 RB1 IA1 RA1 IB2 RB2 IA2 RA2 H_S3: IB1 RB1 IA1 RA1 IA2 RA2 IB2 RB2 H_S4: IA1 RA1 IB1 RB1 IA2 RA2 IB2 RB2但是我們不能排出下面的順序
H_S5: IA1 RA1 IA2 RA2 IB1 RB1 IB2 RB2因為在H_C中,IB1~RB1是在IA2~RA2之前發生的
??那么即使有了這些序列，我們如何確定我們的H_C是正確（correct）的呢?(當下我們只討論這個序列是correct，而不是討論程序的correctness),這里所謂的正確和剛才單線程情況下討論的正確性是一致的。就是這個序列產生的結果是否和我們編寫程序時候預期的結果是一樣的
??答案很簡單，只要對應的H_S有一個是和我們預期的結果是一樣的（正確性的條件），那么就可以認為H_C是可線性化的，把H_S稱為H_C的線性化,同時認為H_C是一個正確的執行,也是我們期望程序表現出來的正常的結果。如果做過并發編程，可能你就會遇到過看起來正常的程序，執行的結果卻和你認為的結果相去甚遠。
還拿上面的程序舉例，假設變量i的初始值為0，則程序運行可能有這樣的一個序列,這里我們加上了response的結果
thread A: IA1----------RA1(1) IA2------------RA2(3) thread B: | IB1---|------RB1(2) IB2----|----RB2(4) || | | | | | | || | | | | | | | real-time order: IA1 IB1 RA1(1) RB1(2) IB2 IA2 RB2(4) RA2(3)---------------------------------------------------------->time對應的H_C為
H_C : IA1 IB1 RA1(1) RB1(2) IB2 IA2 RB2(4) RA2(3)對應的reorder之后的H_S有
H_S1: IA1 RA1(1) IB1 RB1(2) IB2 RB2(4) IA2 RA2(3) H_S2: IB1 RB1(2) IA1 RA1(1) IB2 RB2(4) IA2 RA2(3) H_S3: IB1 RB1(2) IA1 RA1(1) IA2 RA2(3) IB2 RB2(4) H_S4: IA1 RA1(1) IB1 RB1(2) IA2 RA2(3) IB2 RB2(4)然后使用上面提到的H_RO的兩個屬性，上面的H_S序列中只有H_S4是符合預期的一個執行序列，那么也就是說H_C是可線性化的，把H_S4稱為H_C的線性化,同時認為H_C是一個正確的執行。
3. 應用程序的線性化判斷
1. 程序線性化的理論要求
??目前為止，我們終于搞明白了,對于一個并發的項目，什么是可線性化的運行歷史（linearizable history ）,那么我們又該如何評價一個程序是否是可線性化的呢,書中暗表：
The basic idea behind linearizability is that every concurrent history is equivalent, in the following sense, to some sequential history. [The Art of Multiprocessor Programming 3.6.1 : Linearizability] (“following sense” is the reorder rule I have talked about above)
線性化背后的基本思想是，在遵循reorder的規則下，每個并發歷史都等效于某些順序歷史。
也就是說對應一個應用程序來說，如果他執行的每一個H_C都能通過reorder rule轉化為一個正確的H_S,那么就說這個應用程序是可線性化的。
2. linearization point 檢查
??但是，將所有并發歷史H_C重新排序為順序歷史H_S以判斷程序是否可線性化的方法僅在理論上可行。在實踐中，我們面臨著由幾十個線程對同一個方法的大量調用。我們不能對它們的所有歷史進行重新排序。我們甚至無法列出一個復雜程序的所有并發歷史(H_C),所以作者又提出來另一個叫linearization point的概念：
The usual way to show that a concurrent object implementation is linearizable is to identify for each method a linearization point where the method takes effect.
[The Art of Multiprocessor Programming 3.5.1 : Linearization Points]
表明并發對象的操作是可線性化的通常方法是為每個方法確定一個當前方法生效的線性化點。
??們將圍繞“并發對象”來討論上面相關的問題（如果每個線程操作的都是非并發的對象那么程序肯定是正確的）。并發對象的實現一般是有一些方法來訪問并發對象的數據。而且多線程共享一個并發對象。因此，當他們通過調用對象的方法并發訪問對象時，并發對象的實現者必須確保并發方法調用的正確性。
??最重要的是要理解 方法的linearization point,同樣的，where the method takes effect這句描述也確實比較難以理解，下面舉一些例子來進行解釋。
假如我們有下面的方法
//int i = 0; i is a global shared variable. int inc_counter() {int j = i++;return j; }很容易發現這個方法存在并發問題，比如我們將i++翻譯成匯編語言可以得到
#Pseudo-asm-code Load register, address of i Add register, 1 Store register, address of i因此，兩個同時執行i++的線程有可能產生下面的并發歷史H_C
thread A: IA1----------RA1(1) IA2------------RA2(3) thread B: | IB1---|------RB1(1) IB2----|----RB2(2) || | | | | | | || | | | | | | | real-time order: IA1 IB1 RA1(1) RB1(1) IB2 IA2 RB2(2) RA2(3)---------------------------------------------------------->time對于這樣的并發歷史，無論你怎樣reorder，都不能得到一個正確的sequential history (H_S)。
我們需要使用下面的方式重寫相關的代碼
//int i = 0; i is a global shared variable. int inc_counter(){//do some unrelated work, for example, play a popular song.lock(&lock);i++;int j = i;unlock(&lock);//do some unrelated work, for example, fetch a web page and print it to the screen.return j; }??這樣的話，應該能夠理解inc_counter()方法的linearization point了吧，就是整個lock和unlock中間的爭議區域critial section,因為在多線程調用inc_counter()的時候，只有爭議區域保持原子性的執行才能保證方法的正確性。改良后的inc_counter()方法的response是全局變量i的遞增值，有可能是像下面的序列
thread A: IA1----------RA1(2) IA2-----------RA2(4) thread B: | IB1---|-------RB1(1) IB2--|----RB2(3) || | | | | | | || | | | | | | | real-time order: IA1 IB1 RA1(2) RB1(1) IB2 IA2 RB2(3) RA2(4)明顯的，上面的序列可以轉換為下面的合法sequential history (H_S)
IB1 RB1(1) IA1 RA1(2) IB2 RB2(3) IA2 RA2(4) //a legal sequential history我們對IB1~RB1和 IA1~RA1進行了重排序，因為他們在真實的處理時間上面有重疊，所以可以使用任意一個在前的排序方式。同時依據有效的H_S我們可以判斷在H_C當中是IB1~RB1先于 IA1~RA1進入爭議區域critial section。
上面的例子比較簡單，我們再來看一個例子
//top is the tio void push(T val) {while (1) {Node * new_element = allocte(val);Node * next = top->next;new_element->next = next;if ( CAS(&top->next, next, new_element)) { //Linearization point1//CAS success!//ok, we can do some other work, such as go shopping.return;}//CAS fail! retry!} }T pop() {while (1) {Node * next = top->next;Node * nextnext = next->next;if ( CAS(&top->next, next, nextnext)) { //Linearization point2//CAS succeed!//ok, let me take a rest.return next->value;}//CAS fail! retry!} }這是一個充滿bug的lock-free stack的算法實現，請忽略算法的細節。我只是想要展示一下push()和pop()的linearization point，在代碼的注釋中已經標注了相應的linearization point。想象一下假如有許多線程重復調用push（）和pop（），它們將在CAS步驟中進行排序。其他步驟似乎無關緊要，因為無論它們同時執行什么，它們對stack的最終影響（精確地說是top變量）都取決于CAS步驟（線性化點）的順序。如果我們可以確保線性化點真正起作用，則并發堆棧是正確的。即使H_C非常的長，但是我們可以確認必須存在與H_C等效的合法序列。
因此，如果要實現并發對象，那么如何判斷程序的正確性呢？您應該確定每個方法的線性化點，并仔細考慮（甚至證明）它們將始終保持并發對象的不變性。然后，所有方法調用的順序H_C可以擴展到至少一個合法的總順序（事件的順序歷史記錄H_S），該順序滿足并發對象的順序規范。
3. 簡單總結
??這里簡單的再來總結一下線性化的含義，之前看過一些書和一些相關文章，可能每個作者都試圖用自己的方式來闡述什么是可線性化，所以很多時候只是注意到了可線性化的其中一方面的特點，這次通過這個很好的回答的學習也算是真正了解了可線性化的含義。我們可以嘗試從幾個層面去闡述線性化,線性一致性最開始是用在多處理器編程當中，一般是一個進程多個線程這個時候存儲是共享的，為了實現程序的線性一致性，主要需要保證的是程序在爭議區執行的原子性來保證線性一致性。后面逐漸發展出來分布式系統，這個時候強調分布式系統的一致性，不僅要關注系統對執行的原子化保證，還要了解分布式系統對多副本的處理方式，這個時候多個并發使用的存儲并不一定是同一個存儲空間。
還有一點是非常重要的，無論在哪個層級定義線性化，線性化的含義總是：
線性化描述的是程序在外部調用的情況下系統總體對外響應的正確性。這個系統可以是一個java并發對象，可以是一個應用處理軟件(單機的掃雷游戲)，也可以是一個通過網絡訪問的數據存儲應用（Redis）,或者是一個分布式的存儲系統（Zookeeper）等。線性化只是對系統提出了這些要求，但是系統具體怎么實現的他是不關注的。
而且，并非系統都是線性化的，因為線性化對系統要求比較嚴格，會影響系統的吞吐量已經系統的復雜度，所以很多系統可能都工作在非線性話的狀態，比如MYSQL常用的事務的隔離級別中的臟讀，讀提交，可重復讀等都不是線性一致性的。
1. 程序中對共享對象的操作的可線性化
??簡單的概括來說,如果一個對象是線性化的，可以理解為他的所有方法都是原子的(atomic),就像是java的synchronized方法一樣，而且操作的方法必須立即執行，不能使用lazy模式。這里隱含的一個條件是這個對象肯定是多個線程共享操作的。
2. 應用程序的線性一致性
??同樣的，如果把線性化擴展到一個應用程序的話，那么該應用程序的線性化可以描述為，應用程序對于輸入的處理都是原子性的。程序的輸出的正確性并不受并發的輸入的影響。這里默認的一個隱含條件也是程序是多線程或者多進程的對輸入進行處理，但是數據是共享的(內存或者磁盤上)。
3. 分布式系統的可線性化(線性一致性)
如果把線性化擴招到一個分布式系統的話,那么可以這樣描述這個系統
所以在分布式系統中設計一個可線性化的系統更加困難，因為不僅要考慮到操作的原子性保證，還有多個副本（在數據可能不一致的情況下）如何保證向外提供的的數據也滿足線性一致性。
主要參考
https://stackoverflow.com/questions/9762101/what-is-linearizability
總結
以上是生活随笔為你收集整理的线性一致性理解Linearizability的全部內容，希望文章能夠幫你解決所遇到的問題。
