分散式系統概念解疑

1 人贊了文章

「分散式」對應的是「集中式」

「微服務架構」對應的是「單體架構」

其實上面兩種分類的架構是有交叉的，同時也是各有利弊，並非「分散式」或者「微服務架構」就一定好，分散式引入了更多地複雜性，微服務引入了更難的監控和運維。

好多技術都可以抽象出來本質的，而且必須抽象出來簡單的模式和概念，否則會導致一團亂麻，陷入細節的泥沼。真正的學習是需要抽絲剝繭，從紛亂中看到本質。有幾個基礎關鍵點去發散和展開，從而鋪開分散式系統的大網。

要使用抽象和建模的思想和方法論，來進行有效的學習。 所有的抽象和系統建模都回有一系列假設，比如假設網路連接不會出現故障， 假設越多的系統越簡單和容易理解，但在現實世界中，這種系統越脆弱。越是健壯的系統模型，假設越少。在了解學習各種模型和演算法時，一定要搞清楚它的假設（這些假設就是它的能力限制和不足）。

在分散式系統中，核心技術就是：partition和replication。數據分散必須partition，系統要達到高可用必須replication（當然partition本身也部分提高了系統可用性，因為部分partition所在主機故障不影響其他partition的訪問）。 然後圍繞著partition會出現各種的問題，由此產生各種對應的方法和理論以及演算法（比如consistent hashing，cross-partion query，auto-sharding等，如何使得分區均勻，同時滿足數量的均勻和訪問壓力的均勻，以及支持動態分區---這也是NOSQL出現的一大原因）；而replication更是分散式的核心，是解決很多分散式問題的方法的源頭（解決單點故障，滿足高可用，讀寫分離提升性能等等），同時也是引起分散式諸多難題的根源（比如一致性問題：consistency，產生了各種一致性理論：強一致性/弱一致性/最終一致性等）。

在集中式和分散式系統中，都會有buffer/cache，用以提高性能。在集中式架構中，CPU cache和disk buffer是為了加速訪問數據，在分散式架構中，同樣也是為了加速訪問，在本地緩存一份數據。 只要有緩存，就會有一致性問題，因為出現了同一個數據出現了兩份。（replication導致一致性問題，也是由於同一個數據出現了兩份拷貝）。而資料庫要求的隔離性，以及多線程訪問同一個變數，這類問題則是由於多個客戶端訪問同一份數據導致的問題。

多麼奇妙啊！終於將他們關聯起來了。

多個客戶端訪問同一個數據時，即並發場景下：

• 有且僅有一份拷貝的情況下，會有隔離型問題。
• 有兩份及以上拷貝的情況下，會有一致性問題。（內部隱含了隔離型問題）

上面的這些問題都是相互牽連，可以統一分析，找出規律。

1. active replication VS passive replication （state machine replication VS primary-backup approach）
2. 主動複製是：client發送request給所有的節點（state machine node），每個節點都是一個狀態機，這些節點對外部表現為一個整體，當所有節點執行這個request，將之應用到狀態機之後，才返回給client一個成功的response。 在現實系統中，client實際上發送request給這些節點中的固定一個節點，由這個固定節點只是將request保存到其log中，並不執行該request，而是再廣播該request給其餘節點；這個節點就是leader節點，由leader節點負責和client交互（包括response to client）。Raft演算法就是這樣，它的leader節點就是做這個工作的，作為一個client request/reponse的路由和中轉； Raft就是典型的一個replicated state machine 演算法， 也就是主動複製：active replication。 paxos也是一種主動複製演算法，並且支持client和所有節點交互，它不存在leader節點，所有節點都可以和client交互（接收client request和返回 response）

1. 被動複製是：在所有節點中必須存在一個primary節點，由它和client交互，client發送request給primary節點，primary在收到request之後就直接執行並將結果應用到其狀態機中，然後將state change（而不是client request本身）廣播給其餘節點。當primary收到廣播的返回結果之後，再返回response給client。

In active replication each client request is processed by all the servers. Active Replication was first introduced by Leslie Lamport under the name state machine replication. This requires that the process hosted by the servers is deterministic. Deterministic means that, given the same initial state and a request sequence, all processes will produce the same response sequence and end up in the same final state. In order to make all the servers receive the same sequence of operations, an atomic broadcast protocol must be used. An atomic broadcast protocol guarantees that either all the servers receive a message or none, plus that they all receive messages in the same order. The big disadvantage for active replication is that in practice most of the real world servers are non‐deterministic. Still active replication is the preferable choice when dealing with real time systems that require quick response even under the presence of faults or with systems that must handle byzantine faults.

In passive replication there is only one server (called primary) that processes client requests. After processing a request, the primary server updates the state on the other (backup) servers and sends back the response to the client. If the primary server fails, one of the backup servers takes its place. Passive replication may be used even for non‐deterministic processes. The disadvantage of passive replication compared to active is that in case of failure the response is delayed.

1. 上面兩種複製也可以繼續分為sync replication和async replication。

1. 分散式一致性

consensus problem是分散式系統的核心問題，翻譯過來就是一致性問題，但是這個翻譯容易和consistency混淆，因為consistency也是翻譯成一致性；而實際上consensus是多個分散式進程對某一個事物（value或者leader election等）達成共識，而consistency則是多個副本的數據保持一致；兩者意思完全不一樣，consensus problem更具有普遍性和基礎性，consensus problem的解決方法同樣也可以解決consistency的問題（paxos本身是解決最基礎的consensus problem的，就是多個進程隊某個值達成共識；而通過組合paxos形成的multi-paxos則可以解決replicated state machine的consistency問題）。

其實在英英詞典中的翻譯：consensus的意思是「A consensus is general agreement among a group of people」，就是「共識」的意思，根本就不應該翻譯成「一致性」。 而consistent的意思是：「always behaving in the same way or having the same attitudes, standards etc」，就是「〔行為、態度、標準等〕一貫的，一致的」的意思。consensus problem包含了：transaction commit / leader election / atomic broadcast / Mutual exclusion / state machine replication等等問題。 可見，consensus problem是如此的重要，之所以如此重要是由於在網路和進程不穩定的分散式系統中，多個進程達成一個共識是極難的（指不需要第三方協調者，單純依靠這些進程本身去達成共識。由第三方協調的話，比如由meta master負責多個副本數據的一致性，由masterr負責多個副本達成一致，那麼要多個副本達成一致就比較容易了，但是這個master本身要極其可靠才行，因此master本身是要依靠consensus演算法來維持的；通常master是由consensus演算法實現的集群實現的，這又回到了consensus的複雜性上面了。總結一句話就是：複雜性從「維持多副本一致」轉到「master維持」上了）。

1. 2PC和Paxos的關係

原來 paxos就是2PC的改善升級版。本質上Paxos也是一個兩階段協議（propose和accept兩個階段），而2PC的兩階段提交，有很大的缺點：協調者故障問題/參與者故障問題/網路分區等問題，在multi-Paxos中，協調者本身就是從眾多參與者中通過leader election選舉出來的，可以解決協調者故障問題；同時multi-Paxos是一種多數派協議（major quorum），可以容忍F個參與者節點故障（參與者共有2F+1個的情況下），這樣也就解決了參與者故障問題，同時也解決了部分網路分區的問題。疑問：為什麼Leslie Lamport 會說paxos是3階段協議呢？「Instead, I discovered the Paxos algorithm, described in this paper. At the heart of the algorithm is a three-phase consensus protocol.」,看起來應該是在prepare/promise和accepte/accepted這兩個階段之外，由一個decide階段，由proposer發送decided消息給所有的參與者，通知他們value最終確定的值。

1. 多數派（major quorum）的思考

幾乎所有知名的consensus演算法，包括paxos，raft，zab，viewstamped replication的內核都是使用多數派的思路，這是由於多數派是解決strong consistency最有效的方法，因為演算法本身要能夠最大限度的容忍更多的節點故障，同時要保證整個系統的strong consistency和availablity，就只能容忍最多f個節點（系統共有2f+1個節點），必須保留major quorum的正常運行才能維持系統的一致性。這個f是系統能夠容忍節點故障的上限。我們假設不採用多數派思路，而是保留f個節點正常運行，容忍f+1個故障，那麼就無法保證一致性，這種假定的系統，會在出現網路分區時，兩個分區A和B都認為自己是正常的，都繼續對外提供服務（包括寫服務和更新服務），同時A和B不能通信，最終導致系統出現混亂和不一致。多數派思想就是避免出現這種現象的解決方案。

1. 中心化和去中心化的複製

在基於多數派的consensus演算法的使用場景中，有兩種截然不同的架構方案。以paxos演算法為例，存在如下兩種架構：

• 有leader的。所有client寫操作都只和leader交互，client發給任意節點的請求都forward到leader，再由leader通過primary-copy方式（ZAB演算法使用的passive replication）或者state machine replication方式（RAFT演算法使用的active replication，leader作為中轉站的主動複製）請client request（RAFT使用的）或者state update（ZAB使用的）發送到其它節點進行複製。 這個就是中心化的複製方案。針對讀操作，可以只和leader交互（如果不允許讀不一致的數據），或者可以從任意節點讀取數據（如果允許讀不一致的數據）。這句總結是錯的，如果要保證強一致性的話，讀操作也必須通過對應的一致性演算法來操作才行，如果要提高單純讀操作（read-only）的性能，同時又要保持強一致性，就要使用一些特殊方法。
• 無leader的，client的寫操作發送給多個節點（major quorum），多數派節點對本次寫操作達成共識之後，返回成功的應答給client，而讀操作也是和多節點交互，通過多數派的返回f個副本，比對時間戳（使用類似向量時鐘技術），client能夠找到最新的那個數據副本。這就是去中心化的複製方案。實際的使用方案中，client讀寫請求並不是直接群發給所有節點，而是發給其中的任意一個節點，再由該節點廣播到其餘節點。

1. Dynamo 和 BigTable中partition設計的思考

Dynamo是一個分散式鍵值系統，partition採用的是鍵值hash，不需要meta server來保存分片的位置，直接依靠consistent hashing進行計算獲得位置。而Bigtable則是將分片信息保存在meta server（在HBase架構中，是保存在HRegion中的hbase:meta表，而不是HMaster中），因此不需要consistent hashing方法。

1. 故障檢測、租約和心跳

其實最難搞定的是：如何有效進行故障檢測，通過心跳檢測是最普遍的方案，但是，這有不小的弊端，心跳超時不能夠區分出如下場景：「網路分區或擁塞」/「節點故障」/「節點負載過大」。尤其是對強一致性的系統，一定要能夠判斷出是節點問題還是網路問題，master需要確保該節點不能再提供服務，否則將出現多台伺服器同時服務同一份數據而導致數據不一致的情況。

1. 故障恢復
2. 容災
3. membership change --- 組成員變更

這也是一個難點，和重要部分

1. 偏序，全序，因果序，FIFO序
2. 一致性模型

一致性模型是一個約定，是分散式系統和客戶端程序做的一個約定，約定客戶端如果遵從某些規則可以達到某種一致性，越嚴格的一致性越是容易被程序員理解，也越容易保證程序目標的正確性。

包含多路處理器架構中內存訪問順序，以及分散式系統的操作順序，是否也去深入學習多路處理器和多線程。

以順序一致性（sequential consistency）為核心去學習，順序一致性有兩點要求：

1. 單個進程中，按照program order的順序執行全局來看，

2. 各個進程來看，各個進程的操作order可以交叉，但是交叉結果必須是一致的，從各個進程的角度看是一致的。

其實順序一致性和多線程模型的執行類似，無分支循環的多線程中每個線程也都是交叉執行CPU的，每個線程都是按照線程程序自己的順序執行的。

線性一致性（Linearizability，又叫strong consistency）是更嚴格的一致性，是在順序一致性基礎上加上時間的考慮，在順序一致性中，進程A中的操作m和進程B中的操作n沒有必然的時間順序（順序一致性的結果可以是m在n前，也可以是n在m前）；然而，在線性一致性模型的處理結果中，m和n的順序必須按照其操作的執行時間進行排序。具體是增加了如下的約束：如果操作m開始時間晚於n結束時間，則在Sequential Consistency定序時，要求n在m前。

其實還有一個關於線性一致性的定義：那就是任何操作的執行是「瞬時完成」，這個「瞬時」不是說調用之後間完成操作然後返回，而是說在操作調用和返回之間的某個點瞬時完成操作。這是最嚴格的一致性。 根據Raft演算法的描述，要保證一致性，除了演算法本身的邏輯之外，還要client interactive即客戶端交互的配合，比如在Raft中，演算法本身會保證寫操作通過leader節點在多數派機器上面達到線性一致性，但是讀操作如果是從任意一個節點直接讀取，那麼就導致不一致了，不能保證線性一致性；因此讀操作必須也從leader節點走一遍Raft演算法才能保證一致性。

因果一致性是在順序一致性基礎上減弱要求，即：有因果關係的保證順序一致性，而無因果關係的可以不用維持全局順序，可以並發和亂序。

嚴格一致性（strict consistency）是指任何操作瞬時完成，就像單個副本的分散式存儲。這個是最嚴格的一致性，現實世界不可能達到。但是可以作為數序模型來指導現實世界的分散式存儲的設計。其實不考慮性能，是可以通過如下方法實現的：「讓整個系統只在單個節點的單個線程運行。或者，在系統粒度上，讀寫操作被讀寫鎖保護起來（另一種形式的單點運行）。」

分析一致性模型時，最好最容易理解的方式是從客戶端進程的角度去分析，然後再結合分散式存儲的內部實現。尤其是利用2-4個客戶端進程的寫操作和讀操作序列做例子去分析，如圖一所示，每個client進程對分散式存儲系統的讀寫操作請求，任意請求的返回時間和實際work的時間可以是不對應的，比如當client P1發送一個Write(x=1)的寫請求Request1，Client P2發送一個Write(x=2)的寫請Request2，兩者可以並發在存儲系統中執行，當存儲系統返回Reponse1給P1的時候，write(x=1)並不一定已經work起作用了，有可能存儲只是暫時將Request1存到操作日誌，或者只是在leader節點起作用，其它節點的副本還沒其作用，而存儲系統可以自己來組織並發請求的執行順序。下面三篇文章是分析一致性很好的文章。

https://36kr.com/p/5037166.html

http://danielw.cn/history-of-distributed-systems-2

http://danielw.cn/network-failure-models

圖 一 . 一致性分析模型

圖二 多處理器模

下面是網上對於順序一致性和線性一致性最好最簡明的解讀：

Linearizability和Sequential Consistency你可以把它們想像成一個燒烤架, 上面有很多烤串, 你不可以把肉和洋蔥在一個烤叉上互換位置(單個進程需要符合program order), 但是你可以撥動所有烤叉上的肉和洋蔥, 讓他們從左往右排列出來一個先後順序. 不管是Linearizability還是Sequential Consistency, 那麼下面A和C誰在前面都可以, 因為A和C是並行的, 但是C和B在Linearizabiltiy中必須C在前B在後, 而Sequential Consistency中B和C的順序可以互換.

因果一致性：比順序一致性更松的一致性，為了提升性能，放鬆順序一致性的全序要求，只關注有因果關係的操作，有因果關係的操作順序必須對所有進程看到是一致的，而不同進程可以看到不同的並發操作的順序。

因果一致性 causal consistency

當一個讀操作後面跟著一個寫操作時，這兩個事件就具有潛在的因果關係，同樣，讀操作也與為讀操作提供數據的寫操作因果相關。沒有因果關係的操作被稱為並發的。

所有進程必須以相同的順序看到具有潛在因果關係的寫操作，不同機器上的進程可以以不同的順序被看到並發的寫操作。

實現因果一致性要求跟蹤哪些進程看到了哪些寫操作。這就意味著必須構建和維護一張記錄哪些操作依賴於哪些操作的依賴關係圖。一種實現方法是向量時間戳。

因果關係，就是Lamport在Lamport在分散式時鐘事件序論文中描述的happen-before關係及其傳遞閉包，即如下三種因果：

• 同一個進程內的事件A早於B (program order)
• A完成後發消息通知觸發B
• 已知A<B，B<C，根據傳遞性質推到出來的A<C

Causal Consistency要求，如果兩個事件有因果關係，則要求這兩個事件的先後順序滿足因果序，並且所有進程看到的這兩個事件的順序都是滿足這個因果序的。

Causal Consistency相比Sequential Consistency來說，僅要求有因果關係的事件順序對所有進程看到的一致，沒有因果關係的事件順序對於所有進程可以不一致。

FIFO一致性：FIFO Consistency要求同一個進程的program order下的幾個操作被其他所有進程看到的順序是相同的。但是不同進程的幾個操作被其他所有進程看到的順序可能是不同的（即使有因果關係）。 簡單的說，FIFO一致性是放鬆了順序一致性，和順序一致性一樣要求保持program order，但不同點在於：順序一致性要求所有進程看到一致的全局操作順序，而FIFO一致性可以讓不同進程看到不同的全局操作順序，只需要保證一點：同一個進程的program order的順序必須維持住就行。

最終一致性：是一種妥協，為提高性能做的妥協，副本會有短時間的不一致，但是最終，所有副本會保持一致。更正式的說法是：在沒有新的更新操作情況下，最終，所有的請求都會返回最後更新的副本數據。

順序一致性、線性一致性和因果一致性是按照Data-centric Consistency Models分析劃分的。

而最終一致性是按照Client-centric Consistency Models分析劃分的。更有趣的是：因果一致性保證如下四個一致性要求，這四個要求是分散式存儲系統的最低保證了，否則存儲系統對程序員來說沒有使用價值，因為保證太少，程序員難以使用：

• Read Your Writes : this means that preceding write operations are indicated and reflected by the following read operations.
• Monotonic Reads: this implies that an up-to-date increasing set of write operations is guaranteed to be indicated by later read operations.
• Writes Follow Reads: this provides an assurance that write operations follow and come after reads by which they are influenced.
• Monotonic Writes: this guarantees that write operations must go after other writes that reasonably should precede them.

而這四個一致性要求，分別是：讀寫一致性、單調讀一致性、寫跟隨讀一致性和單調寫一致性，這四個一致性是按照Client-centric Consistency Models劃分的，而因果一致性是按照Data-centric Consistency Models劃分的。

最終一致性的幾種具體實現：

1、讀不舊於寫一致性（Read-your-writes consistency）：使用者讀到的數據，總是不舊於自身上一個寫入的數據。

2、會話一致性（Session consistency）：比讀不舊於寫一致性更弱化。使用者在一個會話中才保證讀寫一致性，啟動新會話後則無需保證。

3、單讀一致性（Monotonic read consistency）：讀到的數據總是不舊於上一次讀到的數據。

4、單寫一致性（Monotonic write consistency）：寫入的數據完成後才能開始下一次的寫入。

5、寫不舊於讀一致性（Writes-follow-reads consistency）：寫入的副本不舊於上一次讀到的數據，即不會寫入更舊的數據。

Werner Vogels認為：在很多互聯網應用中，單讀一致性＋讀不舊於寫一致性可以提供足夠的一致性了。

弱一致性：系統中的某個數據被更新後，後續對該數據的讀取操作可能得到更新後的值，也可能是更改前的值。

1. ACID中的隔離性
2. 故障模型

從強到弱，分為四種：

• 拜占庭故障，最複雜和難以解決的故障，一般不在考慮範圍
• Fail-Recovery 故障，市面上多數分散式系統容忍的故障，比如kafka（In distributed systems terminology we only attempt to handle a "fail/recover" model of failures where nodes suddenly cease working and then later recover (perhaps without knowing that they have died). Kafka does not handle so-called "Byzantine" failures in which nodes produce arbitrary or malicious responses (perhaps due to bugs or foul play).）
• omission 故障
• Fail-stop 故障

1. 系統模型

分散式系統的系統模型有兩類：同步系統和非同步系統，這個概念並非類似同步阻塞IO和非同步非阻塞IO的概念，而是指同步系統模型中：網路傳輸時間有上限；所有節點的時鐘漂移有上限；所有節點的計算速度一樣。 而非同步系統模型中，網路傳輸時間無上限，節點的時鐘漂移無上限，節點的計算速度不可預料。其實從asynchronous的英文解釋中< (digital communication) pertaining to a transmission technique that does not require a common clock between the communicating devices; timing signals are derived from special characters in the data stream itself> 和 < asynchronous computer processes happen at different times or rates >發現就是這個意思。

1. 線性化（linearizability） VS 串列化（serializability）

• 線性化是分散式系統一致性模型中的一種一致性的保證，多個client對分散式存儲系統中單個對象進行讀寫操作的一種保證，又稱為強一致性。是CAP理論中的C，針對單個對象操作。是一種local property，是關於單個對象訪問的property
• 串列化是操作系統事務中的一種概念，是隔離性的保證，是ACID中的I，針對事務。支持事務的資料庫系統必須有效地對操作進行同步以保證事務之間的隔離性。最簡單的方法就是串列執行事務～可以按任意次序一次一次地執行事務。遺憾的是，這種解決方案對有多個交互用戶共享其資源的伺服器而言是不可接受的。 任何支持事務的伺服器的目標就是最大限度的實現並發，因此如果事務的並發執行與串列執行具有相同效果，即他們是串列等級（serially equivalent）的或可串列化（serializable）的，那麼可允許事務並發執行。 串列化是一種global property，是關於多個對象訪問的property。

根據上面的理解，線性化和串列化能夠很好的區分開來。再深入一點，如果把對分散式單個對象的地個讀/寫操作看作是一個事務的話，可以把線性化理解為更嚴格的串列化。

1. 多客戶端、應答時間（latency）、並發、緩存

其實所有的系統，不管是多處理器架構、分散式系統、資料庫以及多線程架構，甚至包括文件系統，都有共性問題，這些共性問題其實解決思路是共通的，如下：

1. 並發：

要同時支持成千上萬的客戶端（對多線程和多處理器架構而言，客戶端就是線程本身），這些client的訪問和操作不能混淆和混亂，因此最簡單的解決方案就是將這些訪問操作串列化，然後系統每次只處理一個訪問操作。但是這個方案導致系統沒有並發能力，客戶端請求操作長時間排隊等待，是不可接受的。因此出現了各種技術和方案來解決這個問題，以使系統能夠實現最大程度的並發。即：並發處理客戶端請求。

要很好地弄清這些問題，就一定要搞明白「一個操作或者事務結束」實際上有兩種不同的含義：一個是a：對client request有一個successful response； 一個是b：系統內部真正徹底完成了client request的操作。通常系統為了提高系統並發性，都是在b未完成之前就做了a（舉個例子：write operation未持久化而是寫到buffer就返回成功，對client來說這個write operation已經結束，但是對存儲系統來說並沒徹底完成；類似的例子還有：write operation到leader，並沒有複製到其它副本，就返回成功），而不是等到b完成才做a。這個思路一定要清晰，它是理解分散式一致性和其它概念的核心基礎。

1. 緩存：

要提升系統的處理性能，就必須使用緩存。數據的持久化是必須的，但是持久化存儲（比如disk）的讀寫速度太慢，因此需要將讀寫數據緩存到內存甚至CPU Cache，這樣才能加快處理速度。Cache和Buffer是如此普遍的應用，在帶來系統性能提升同時也帶來很多問題，諸如一致性問題。

1. 系統分析方法

根據對一致性模型的學習，總結了兩種對一個系統的分析方法：

1. Data-centric

從系統內部對數據的處理來分析

1. Client-centric

從連接到系統的client的角度分析，從對client的讀寫訪問的角度分析

1. 租約(lease)

In computer science, a Lease is a contract that gives its holder specified rights to some resource for a limited period. Because it is time-limited, a lease is an alternative to a lock for resource serialization.

The term lease was applied to this concept in a 1989 paper by Cary G. Gray and David R. Cheriton,[1] but similar concepts (expiring tokens[2] and breakable locks with timeouts[3]) had been used in prior systems. 根據維基上的描述，租約實際上是一個lock，用來鎖定某些資源，不過這個lock是breakable的，有時效期的，時效過了，自動解鎖。

到底租約是什麼？

在很多時候，租約的定義似乎很模糊，有的時候租約類似心跳，有的時候又類似於鎖。到底租約的本質是什麼呢？

回到租約最原始的定義：租約就是在一定期限內給予持有者特定權力的 協議。我覺得這裡的期限就是租約的根本特性，正是這一特性使得租約可以容忍機器失效和網路分割。在期限之內，租約其實就是伺服器和客戶端之間的協議，而這 個協議的內容可以五花八門。如果協議內容是伺服器確認客戶端還存活，那麼這個租約的功能就相當於心跳；如果協議內容是伺服器保證內容不會被修改，那麼這個 租約就相當於讀鎖；如果協議內容是伺服器保證內容只能被這個客戶端修改，那麼這個租約就相當於寫鎖。租約這種靈活性和容錯性，使其成為了維護分散式系統一致性的有效工具。

租約機制由於是一種timeout的lock，依賴於分散式節點時鐘的一致性，節點之間只可容忍較小的時鐘漂移，需要能夠做到時鐘同步才行。

1. 讀與寫的權衡

讀和寫操作時互為影響的兩個操作，系統在設計時，依據讀寫操作的比例，來合理進行架構設計，來滿足最終需求。

• 對於讀比寫更頻繁的系統，比如chubby，chubby提供小文件存儲和分散式鎖服務，讀比寫頻繁得多，因此為了提升讀的性能，就要犧牲掉部分寫的性能，具體是：使用租約機制，客戶端獲得租約，並緩存數據，在讀的時候直接從緩存中取，不需要和master聯繫，加快性能；而在寫的時候，伺服器在寫之前首先向所有可能緩存該數據的客戶端發送「緩存過期」的信息，等到Master在接收到所有相關的客戶端針對該過期信號的應答後（應答包括兩類，一種是客戶端明確要求更新緩存，另一類則是客戶端允許緩存租期過期），再繼續之前的寫操作。 這就是犧牲寫性能來換取讀性能。
• 對於寫比更頻繁的系統，尤其是對於大數據的寫，比如HBase，則採用LSM樹的方案，直接在內存中寫，寫到memcache，後續刷到磁碟；而對於讀，則需要進行memcache、blockcache和HFile的綜合，才能讀取到最新的數據。這就是典型的犧牲讀性能來換取寫性能。

1. 極其重要概念的澄清

多線程中的Critical section(臨界區)，其實和資料庫中的Transaction(事務)非常類似，是一個概念，都是屬於並發問題，基本100%的相通，可以一起綜合分析。

1. 臨界區中包含共享資源的訪問，多個線程同時訪問這些資源； 事務中包含表的訪問，多個客戶端同時訪問這些表。

2. 臨界區的執行必須是原子性的和隔離性的；而事物的執行也必須是原子性和隔離性的。

3. 臨界區的隔離性要達到可串列化serializability，事務的隔離性也要求達到可串列化serializability。 他們都使用了鎖來實現。

4. 事務要求一致性和持久化，這兩點，臨界區並不涉及。

而和多線程相關的多處理器架構中，緩存一致性(cache conheren)和分散式系統的一致性，概念上很類似，都是同一個數據多個副本達到一致性的問題。java和C++中的Volatile修飾符，就是用來解決多處理器中數據的不一致性，具體就是：告訴編譯器，這個變數不要進行優化，讀寫都要在內存中做，不要從Cache中取也不要在Cache中緩存，這種技術就是內存屏障。

分散式系統中沒有隔離性的概念，這是由於分散式系統中，每個client的操作都是單步操作：read 或者 write，單步操作一步完成，不需要隔離。（實際是需要隔離的，不過在真實可用的分散式系統中做到了每一步操作的可串列化，就是順序一致性，sequential consistency，做到每一步操作互不打擾，互不干擾實際上就是串列化。可串列化是最低的要求，因為它不保證先後順序，而順序一致性就是一種串列化，不過在分散式系統中又加上一個限制：同時要求多個副本上看到一致的操作順序。 可串列化 加上 時間先後的限制，就變成 線性化了 Linearizability。 雖然這樣理解是可以的，但是最好還是將 「可串列化」概念用在資料庫事務中，把它和ACID中的隔離性關聯起來，否則容易迷糊。 下面的<Linearizability versus Serializability>）。 而在多線程臨界區和資料庫事物中，一個執行並不是一步完成的，而是包含多步操作的，這些操作是作為整體，不能被分割的，但是實際上在執行中間會被干擾（單處理器的多線程中，CPU調度會打斷執行；多處理器的多線程中，CPU會並發執行多線程中的每個線程；資料庫中，資料庫執行引擎會並發執行多個客戶端的操作。），因此為了防止被干擾，就要使用類似鎖的機制保持共享資源的獨佔性。

Linearizability versus Serializability

24 Sep 2014

Linearizability and serializability are both important properties about interleavings of operations in databases and distributed systems, and it』s easy to get them confused. This post gives a short, simple, and hopefully practical overview of the differences between the two.

Linearizability: single-operation, single-object, real-time order

Linearizability is a guarantee about single operations on single objects. It provides a real-time (i.e., wall-clock) guarantee on the behavior of a set of single operations (often reads and writes) on a single object (e.g., distributed register or data item).

In plain English, under linearizability, writes should appear to be instantaneous. Imprecisely, once a write completes, all later reads (where 「later」 is defined by wall-clock start time) should return the value of that write or the value of a later write. Once a read returns a particular value, all later reads should return that value or the value of a later write.

Linearizability for read and write operations is synonymous with the term 「atomic consistency」 and is the 「C,」 or 「consistency,」 in Gilbert and Lynch』s proof of the CAP Theorem. We say linearizability is composable (or 「local」) because, if operations on each object in a system are linearizable, then all operations in the system are linearizable.

Serializability: multi-operation, multi-object, arbitrary total order

Serializability is a guarantee about transactions, or groups of one or more operations over one or more objects. It guarantees that the execution of a set of transactions (usually containing read and write operations) over multiple items is equivalent to some serial execution (total ordering) of the transactions.

Serializability is the traditional 「I,」 or isolation, in ACID. If users』 transactions each preserve application correctness (「C,」 or consistency, in ACID), a serializable execution also preserves correctness. Therefore, serializability is a mechanism for guaranteeing database correctness.1

Unlike linearizability, serializability does not—by itself—impose any real-time constraints on the ordering of transactions. Serializability is also not composable. Serializability does not imply any kind of deterministic order—it simply requires that some equivalent serial execution exists.

Strict Serializability: Why don』t we have both?

Combining serializability and linearizability yields strict serializability: transaction behavior is equivalent to some serial execution, and the serial order corresponds to real time. For example, say I begin and commit transaction T1, which writes to item x, and you later begin and commit transaction T2, which reads from x. A database providing strict serializability for these transactions will place T1 before T2 in the serial ordering, and T2 will read T1』s write. A database providing serializability (but not strict serializability) could order T2 before T1.2

As Herlihy and Wing note, 「linearizability can be viewed as a special case of strict serializability where transactions are restricted to consist of a single operation applied to a single object.」

Coordination costs and real-world deployments

Neither linearizability nor serializability is achievable without coordination. That is we can』t provide either guarantee with availability (i.e., CAP 「AP」) under an asynchronous network.3

In practice, your database is unlikely to provide serializability, and your multi-core processor is unlikely to provide linearizability—at least by default. As the above theory hints, achieving these properties requires a lot of expensive coordination. So, instead, real systems often use cheaper-to-implement and often harder-to-understand models. This trade-off between efficiency and programmability represents a fascinating and challenging design space.

未完待續！