動機

筆記

intro

提醒大家，在你設計一個系統時或者面對一個你需要解決的問題時，如果你可以在一台計算機上解決，而不需要分佈式系統，那你就應該用一台計算機解決問題

有很多的工作都可以在一台計算機上完成，並且通常比分佈式系統簡單很多。所以，在選擇使用分佈式系統解決問題前，你應該要充分嘗試別的思路，因為分佈式系統會讓問題解決變得複雜

分佈式系統的問題（挑戰）在於

  • 並發
  • 局部錯誤
    • 一部分組件在工作、另一部分組件停止運行
    • 這些計算機都在正常運行，但是網絡中斷了或者不穩定
  • 實際上一千台機器到底有多少性能是一個棘手的問題

基礎架構

  • 存儲
  • 通信（網絡）
  • 計算

我們希望通過這種抽象的接口，將分佈式特性隱藏在整個系統內 我們的確也需要構建這樣一種基礎架構，它能夠盡可能多的對應用開發人員屏蔽和掩蓋錯誤

  • 性能 => 可擴展性(Scalability)
  • 容錯 => 可用性(Availability)
    • 大型分佈式系統中有一個大問題，那就是一些很罕見的問題會被放大
      • 1000台計算機的集群中，總是有故障
        • 主機
        • 網路
    • recoverability
      • 如果出現了問題，服務會停止工作，不再響應請求，之後有人來修復，並且在修復之後系統仍然可以正常運行，就像沒有出現過問題一樣
      • 為了實現這些特性，有很多工具
        • 非易失存儲（non-volatile storage，類似於硬盤）
          • checkpoint, log
        • 複製（replication）
          • 關鍵問題在於，這兩個副本總是會意外的偏離同步的狀態，而不再互為副本
  • 一致性（Consistency）
    • 一致性就是用來定義操作行為的概念 (多個副本)
      • 強一致（Strong Consistency）
        • 強一致可以確保get獲取的是最新的數據，但是實現這一點的代價非常高
        • 分佈式系統的各個組件需要做大量的通信，才能實現強一致性
      • 弱一致

分佈式存儲系統的難點 (loop)

  1. 巨大的性能加成 > 分片
  2. 分片（Sharding），但你將會看見常態的故障 > 容錯（fault tolerance）
  3. 複製（replication） > 不一致（inconsistency）
  4. 強一致 > 低性能

mapreduce

這裡確實需要將每一份數據都通過網絡從創建它的Map節點傳輸到需要它的Reduce節點 這裡實際上可能會有大量的網絡通信

gfs

設計與目標

  • big,fast
  • global
  • sharding
  • automatic recovering

前提

  • single data centor
  • internal use
  • big sequential access
    • 沒有random access

Master節點用來管理文件和Chunk的信息 Chunk服務器用來存儲實際的數據

Master節點知道每一個文件對應的所有的Chunk的ID，這些Chunk每個是64MB大小，它們共同構成了一個文件

master node

  • filename
    • 很多chunk id
  • chunk id
    • chunk server的列表
    • version
    • 是不是primary chunk
      • write只能在primary上跑
    • 租約時間

Master會在磁盤上存儲log，每次有數據變更時，Master會在磁盤的log中追加一條記錄，並生成CheckPoint（類似於備份點）

read

  • filename + offset -> chunk id + chunk server list
  • 選一個chunk server -> chunk id + offset
  • 從一般的fs拿檔案

write(只有append)

當有多個客戶端同時寫同一個文件時，一個客戶端並不能知道文件究竟有多長 沒有一個客戶端會知道文件究竟有多長，因此也就不知道該往什麼樣的偏移量，或者說向哪個Chunk去追加數據。 客戶端可以向Master節點查詢哪個Chunk服務器保存了文件的最後一個Chunk。

對於某個特定的Chunk來說，在某一個時間點，Master不一定指定了Chunk的主副本。所以，寫文件的時候，需要考慮Chunk的主副本不存在的情況

如果發現Chunk的主副本不存在，Master會找出所有存有Chunk最新副本的Chunk服務器

當客戶端想要對文件進行追加，但是又不知道文件尾的Chunk對應的Primary在哪時，Master會等所有存儲了最新Chunk版本的服務器集合完成，然後挑選一個作為Primary，其他的作為Secondary

Master會增加版本號，並將版本號寫入磁盤，這樣就算故障了也不會丟失這個數據

Master節點會向Primary和Secondary副本對應的服務器發送消息並告訴它們，誰是Primary，誰是Secondary，Chunk的新版本是什麼

  1. client寫資料到各個chunk
    • 客戶端會將要追加的數據發送給Primary和Secondary服務器，這些服務器會將數據寫入到一個臨時位置。
    • 最開始，這些數據不會追加到文件中
  2. 當所有的服務器都返回確認消息說，已經有了要追加的數據，客戶端會向Primary服務器發送一條消息，將這個數據追加到這個文件中
  3. Primary服務器或許會從大量客戶端收到大量的並發請求，Primary服務器會以某種順序，一次只執行一個請求
  4. Primary會通知所有的Secondary服務器也將客戶端要追加的數據寫入在它們自己存儲的Chunk末尾

如果客戶端從Primary得到寫入失敗，那麼客戶端應該重新發起整個追加過程

GFS這樣設計的理由是足夠的簡單，但是同時也給應用程序暴露了一些奇怪的數據 這里希望為應用程序提供一個相對簡單的寫入接口，但應用程序需要容忍讀取數據的亂序

將GFS升級成強一致系統，我可以為你列舉一些你需要考慮的事情

  • 讓Primary來探測重複的請求
  • 對於Secondary來說，如果Primay要求Secondary執行一個操作，Secondary必須要執行而不是只返回一個錯誤給Primary
    • 於一個嚴格一致的系統來說，是不允許Secondary忽略Primary的請求而沒有任何補償措施的
  • 當Primary要求Secondary追加數據時，直到Primary確信所有的Secondary都能執行數據追加之前，Secondary必須小心不要將數據暴露給讀請求
    • 第一個階段，Primary向Secondary發請求，要求其執行某個操作，並等待Secondary回复說能否完成該操作，這時Secondary並不實際執行操作。
    • 在第二個階段，如果所有Secondary都回复說可以執行該操作，這時Primary才會說，好的，所有Secondary執行剛剛你們回复可以執行的那個操作
    • 兩階段提交（Two-phase commit）
  • 新的Primary上任時，需要顯式的與Secondary進行同步
    • 當Primary崩潰時，可能有一組操作由Primary發送給Secondary
  • 要么對於Secondary需要一個租約系統，就像Primary一樣，這樣就知道Secondary在哪些時間可以合法的響應客戶端

就是raft!!

vmware ft

複製不能處理軟件中的bug和硬件設計中的缺陷

如果我們有兩個副本，一個Primay和一個Backup節點，我們總是假設兩個副本中的錯誤是相互獨立的。但是如果它們之間的錯誤是有關聯的，那麼複製對我們就沒有幫助

這種複制的方案是否值得？因為它使用了我們實際需要的2-3倍的計算機資源

State Transfer Primary將自己完整狀態，比如說內存中的內容，拷貝並發送給Backup

Replicated State Machine 它只會從Primary將這些外部事件，例如外部的輸入，發送給Backup。 通常來說，如果有兩台計算機，如果它們從相同的狀態開始，並且它們以相同的順序，在相同的時間，看到了相同的輸入，那麼它們會一直互為副本，並且一直保持一致。

狀態轉移傳輸的是可能是內存，而復制狀態機會將來自客戶端的操作或者其他外部事件，從Primary傳輸到Backup。

在多核上工作。這個新系統從我看來使用了狀態轉移，而不是複制狀態機。因為面對多核和並行計算，狀態轉移更加健壯。如果你使用了一台機器，並且將其內存發送過來了，那麼那個內存鏡像就是機器的狀態，並且不受並行計算的影響，但是複制狀態機確實會受並行計算的影響。但是另一方面，我認為這種新的多核方案代價會更高一些。

會復制機器的完整狀態，這包括了所有的內存，所有的寄存器

應用程序級別的複制系統。這樣做的後果是，複製這個行為，必須構建在應用程序內部。如果你收到了一系列應用程序級別的操作，你確實需要應用程序參與到復制中來

VMware FT的獨特之處在於，它從機器級別實現複製，因此它不關心你在機器上運行什麼樣的軟件，它就是複制底層的寄存器和內存

它的缺點是，它沒有那麼的高效，優點是，你可以將任何現有的軟件，甚至你不需要有這些軟件的源代碼，你也不需要理解這些軟件是如何運行的

  • primary負責收client的request
  • VMM(hyperviser)遇到request會copy一份到secondary(log channel)
    • 不確定性
      • 中斷發生的時間有一樣嗎?
      • 有狀態的指令 (random, timeoftoday)
      • 多核
    • 對此需要特別的request格式
      • 日誌條目的類型
      • 數據: 一般資料或是已經跑完不確定性指令的資料
      • 事件發生時的指令序號
  • 在primary跑request之前會確認backup有收到log!! (ack)
    • 沒收到就不會把response丟回去
      • 就算primary已經做好了
      • 幾乎每一個複制系統都有這個問題，在某個時間點，Primary必須要停下來等待Backup，這對於性能是實打實的限制
        • 所以如果條件允許，人們會更喜歡使用在更高層級做複製的系統（詳見4.2 最後兩段）
        • 也就是應用程式層級的複製
  • VMM會讓來自primary的response通過，backup的會drop
    • 重複output
      • 如果
        • primary在傳完response掛掉
        • backup還沒處理新的log
      • 這樣backup會消耗log來成為primary，之後丟response
      • 但因為現在backup是primary，所以response會被丟回去!!
        • 不過因為都是用TCP連線，所以TCP會drop重複的packet
          • tcp的狀態與原本的primary一樣
    • 對於任何有主從切換的複制系統，基本上不可能將系統設計成不產生重複輸出
      • 為了避免重複輸出，有一個選項是在兩邊都不生成輸出，但這是一個非常糟糕的做法（因為對於客戶端來說就是一次失敗的請求）
      • 當出現主從切換時，切換的兩邊都有可能生成重複的輸出，這意味著，某種程度上來說，所有復制系統的客戶端需要一種重複檢測機制
  • primary與backup之間有heart beat確認health
    • 還有Test-and-Set確認對方真的掛了 (想像雙方剛好log channel的連線被block)
      • Test-and-Set服務不運行在Primary和Backup的物理服務器上，VMware FT需要通過網絡支持Test-and-Set服務
        • 這有點像一個鎖。為了能夠上線，它們或許會同時發送一個Test-and-Set請求，給Test-and-Set服務。
          • 當第一個請求送達時，Test-and-Set服務會說，這個標誌位之前是0，現在是1
      • 在6.824這門課程中，有個核心的規則就是，你無法判斷另一個計算機是否真的掛了，你所知道的就是，你無法從那台計算機收到網絡報文，你無法判斷是因為那台計算機掛了，還是因為網絡出問題了導致的

raft

整個系統有兩個時間

  • server自己
    • 也就是做了什麼
  • 動作的source
    • 現在該聽誰的
      • 單一source可以處理brain-split

raft是共識algorithm，所以要處理consistency

  • 單一source => brain-split
    • 也有可能沒有leader，但這個時候system也不能做什麼事
  • majarity votes => fault-toroelent
  • commit, and then apply

重要的state (時間)

  • 所有server的現在時間
    • currentTerm
  • server自身的時間
    • votedFor
    • log[]
      • 後面處理log compaction會看到，log還要多一個狀態snapshot

執行期狀態 (做到哪)

  • server自己
    • commitIndex: log收到哪
    • lastApplied: log做到哪
  • leader狀態
    • nextIndex[]: 要從哪個log開始塞給ith follower
    • matchIndex[]: ith follower做到哪了

接下去就是下面其中一個事件發生

  1. 選leader
    • RequestVote RPC
      • 前提
        • 收到的term要大於等於自己 (所有server的現在時間夠新)
      • 之後就
        • 改votedFor

  1. 處理client request
    • AppendEntries RPC
      • 前提
        • 收到的term要大於等於自己 (所有server的現在時間夠新)
        • prevLogIndex 有東西 & prevLogTerm 對得起來 (server自身的時間是對得起來的)
          • 對不起來?
            1. prevLogIndex沒東西
              • return false (leader與自己的狀態對不起來)
            2. prevLogTerm不對
              • 把prevLogIndex後面的東西刪掉
      • 之後就
        • 把entries接上去
        • 更新commitIndex

接著就是看state怎麼改變的

  1. 什麼時候apply log

    • commitIndex > lastApplied
      • 同時跟新lastApplied

  2. 什麼時候換currentTerm

    • 收到大於自己term的rpc時
      • 同時換votedFor
    • 成為candidate (來自timeout)

  3. leader怎麼知道

    • 大家commit到哪 (leader怎麼跟新commitIndex)
      • N > commitIndex, a majority of matchIndex[i] ≥ N, and log[N].term == currentTerm
    • 我的prevLogIndex是錯的
      • AppendEntries回傳false, 之後leader的prevLogIndex自己退一格，retry AppendEntries
        • leader退無可退怎麼辦?
          • 這個時候就是snapshot了
        • 退一格不會太慢 (7.3 快速恢复（Fast Backup）)
          • follower的reply加上，衝突位置(prevLogIndex)的
            • XTerm: prevLogIndex的位置的term
            • XIndex: XTerm的第一個event的log 位置
            • XLen: 有多少空白的log
          • 之後有3個case
            • XTerm是空的
              • 從XLen開始蓋
            • 沒看過XTerm的term
              • 從XIndex開始蓋
            • 看過XTerm的term，所以是index對不上
              • 從XIndex-1開始蓋
    • 什麼時候要response給client
      • 收到AppendEntries的過半reply

有一個細節在 6.8 选举定时器（Election Timer） 提到 就是timeout可能有livelock，所以可以像ethernet的CSMA/CD，但是retry的間隔至少要大於heartbeat的間隔

Linearizability

一個系統的執行歷史是一系列的客戶端請求，或許這是來自多個客戶端的多個請求。如果執行歷史整體可以按照一個順序排列，且排列順序與客戶端請求的實際時間相符合，那麼它是線性一致的

對於線性一致的順序順序，有兩個限制條件：

  1. 如果一個操作在另一個操作開始前就結束了，那麼這個操作必須在執行歷史中出現在另一個操作前面。
    • 時間序 (可能會出現concurrent)
    • 可以當成從第一個write response最後開始跑的bfs tree
  2. 執行歷史中，讀操作，必須在相應的key的寫操作之後。
    • 把tree壓成line

這裡要看一個例子 這個read是3符合Linearizability?

在第一個write後發read，但是中間經歷重傳，也許read是在write 4之後完成的

但是這裡的第一個read是在第一個write之後，所以就算丟3也ok

客戶端永遠也不能在一個線性一致的系統中看到舊的數據（也就是X=1），因為一個線性一致的系統不允許讀出舊的數據 對於讀請求不允許返回舊的數據，只能返回最新的數據。或者說，對於讀請求，線性一致系統只能返回最近一次完成的寫請求寫入的值。

zookeeper

first-in-first-out order

如果系統不提供線性一致性，那麼系統是否還可用？客戶端發送了一個讀請求，但是並沒有得到當前的正確數據，也就是最新的數據，那我們為什麼要相信這個系統是可用的？

如果read/write都是透過leader做，這樣沒有scalbility

  • Zookeeper並不要求返回最新的寫入數據。 Zookeeper的方式是，放棄線性一致性，提升read的效率
  • 直接讓follower處理read

但是zookeeper保證會照client的指令order(first-in-first-out)去跑

  • how?
    • 在指令上打index，讓index對到log的index(response中附上log index(zxid))，之後就是確保在log的index大於等於前面坐指令時的log index大的狀態下跑指令

讀寫請求是線性一致的，這讓前面的第一個問題有了解法，同步操作（sync）

同步操作（sync）就是

  1. 先發一個write (透過raft完成)
  2. 之後read要求一定要在前面的write發生之後 (透過first-in-first-out完成)

ready file(transcation, seqlock)

  1. 先刪raedy file
  2. 做write
  3. 創ready file

之後client就能認ready file去讀，但這樣有問題有可能在刪之前ready還在，但中間其他的write啟動了

所以會多一個watch確認ready file有沒有被動，有被通知就要retry Zookeeper可以保證如果某個人刪除了Ready file，相應的通知，會在任何後續的讀請求之前，發送到客戶端。 客戶端會先收到有關Ready file刪除的通知，之後才收到其他在Log中位於刪除Ready file之後的讀請求的響應

API

Zookeeper的API某種程度上來說像是一個文件系統 Zookeeper被設計成要被許多可能完全不相關的服務共享使用。所以我們需要一個命名系統來區分不同服務的信息

Zookeeper中包含了3種類型的znode

  1. Regular znodes
    • 這種znode一旦創建，就永久存在，除非你刪除了它。
  2. Ephemeral znodes
    • 如果Zookeeper認為創建它的客戶端掛了，它會刪除這種類型的znodes
      • 客戶端需要時不時的發送心跳給Zookeeper，這樣Zookeeper才不會刪除客戶端對應的ephemeral znodes。
  3. Sequential znodes
    • Zookeeper實際上創建的文件名是你指定的文件名再加上一個數字。
    • 當有多個客戶端同時創建Sequential文件時，Zookeeper會確保這裡的數字不重合，同時也會確保這裡的數字總是遞增的。

每一個znode都有一個表示當前版本號的version，當znode有更新時，version也會隨之增加

  • CREATE(PATH，DATA，FLAG)
  • DELETE(PATH，VERSION)
  • EXIST(PATH，WATCH)
  • GETDATA(PATH，WATCH)
  • SETDATA(PATH，DATA，VERSION)
  • LIST(PATH)

acc

V是版本號

WHILE TRUE:
    X, V = GETDATA("F")
    IF SETDATA("f", X + 1, V):
        BREAK

Non-Scalable Lock

WHILE TRUE:
    IF CREATE("f", data, ephemeral=TRUE): RETURN
    IF EXIST("f", watch=TRUE):
        WAIT

最終鎖會以刪除文件的形式釋放，所以我們這里通過EXIST函數加上watch=TRUE，來監測文件的刪除

羊群效應（Herd Effect） 對於計數器的例子來說，就是當有1000個客戶端同時需要增加計數器時，我們的複雜度是$O(n^2)$，這是處理完1000個客戶端的請求所需要的總時間。

$loop * watch通知 = O(n^2)$

Scalable Lock

CREATE("f", data, sequential=TRUE, ephemeral=TRUE)
WHILE TRUE:
    LIST("f*")
    IF NO LOWER #FILE: RETURN
    IF EXIST(NEXT LOWER #FILE, watch=TRUE):
        WAIT

Chain Replication with Apportioned Queries

Chain Replication

所有機器串成linked list，從頭開始處理write，直到碰到最後一個機器才response read就是從tail的狀態直接拉

可以注意到這個系統是線性一致的!! 同時可以讓read的性能可以scale!!

Fail Recover

  • head, tail fail?
    • 找前一個或是後一個替代
  • mid fail?
    • 把mid移除，把前一個的write轉給下一個

Chain Replication 與 Raft

  • 從性能上看，對於Raft，如果我們有一個Leader和一些Follower。
    • Leader需要直接將數據發送給所有的Follower。
      • 所以，當客戶端發送了一個寫請求給Leader，Leader需要自己將這個請求發送給所有的Follower。
    • 然而在Chain Replication中，HEAD只需要將寫請求發送到一個其他節點。
  • 數據在網絡中發送的代價較高，所以Raft Leader的負擔會比Chain Replication中HEAD的負擔更高。
  • 當客戶端請求變多時，Raft Leader會到達一個瓶頸，而不能在單位時間內處理更多的請求。
    • 而同等條件以下，Chain Replication的HEAD可以在單位時間處理更多的請求，瓶頸會來的更晚一些。
  • 另一個與Raft相比的有趣的差別是，Raft中讀請求同樣也需要在Raft Leader中處理，所以Raft Leader可以看到所有的請求。
    • 而在Chain Replication中，每一個節點都可以看到寫請求，但是只有TAIL可以看到讀請求。
    • 所以負載在一定程度上，在HEAD和TAIL之間分擔了，而不是集中在單個Leader節點。
  • 前面分析的故障恢復，Chain Replication也比Raft更加簡單。這也是使用Chain Replication的一個主要動力。

Chain Replication並不能抵禦網絡分區，也不能抵禦腦裂。 總是會有一個外部的權威（External Authority）來決定誰是活的，誰掛了，並確保所有參與者都認可由哪些節點組成一條鏈

Configuration Manager的工作就是監測節點存活性，一旦Configuration Manager認為一個節點掛了，它會生成並送出一個新的配置，在這個新的配置中，描述了鏈的新的定義，包含了鏈中所有的節點，HEAD和TAIL

你是如何使得一個服務是容錯的，不否認自己，同時當有網絡分區時不會出現腦裂呢？ Configuration Manager通常會基於Raft或者Paxos

Aurora

RDS的歷史

EC2對於無狀態的Web服務器來說是完美的

如果突然新增了大量客戶，你可以立刻向Amazon租用更多的EC2實例，並在上面啟動Web服務。這樣你就可以很簡單的對你的Web服務進行擴容

當Web服務所在的服務器宕機了，是完全沒有問題的，因為Web服務本身沒有狀態，你只需要在一個新的EC2實例上啟動一個新的Web服務就行

對於數據庫來說，EC2就不像對於Web服務那樣完美了 如果服務器宕機了，那麼它本地硬盤也會無法訪問

從EC2實例來看，EBS就是一個硬盤，你可以像一個普通的硬盤一樣去格式化它，就像一個類似於ext3格式的文件系統或者任何其他你喜歡的Linux文件系統

在實現上，EBS底層是一對互為副本的存儲服務器 兩個EBS服務器會使用Chain Replication（9.5）進行複制

現在你運行了一個數據庫，相應的EC2實例將一個EBS volume掛載成自己的硬盤。當數據庫執行寫磁盤操作時，數據會通過網絡送到EBS服務器。

EBS的缺點

  • 如果你在EBS上運行一個數據庫，那麼最終會有大量的數據通過網絡來傳遞
    • 網絡負載更加重要
    • 不太關心CPU和存儲空間的消耗
  • EBS的容錯性不是很好
    • 出於性能的考慮，Amazon總是將EBS volume的兩個副本存放在同一個數據中心

RDS

  • 將數據庫在多個AZ之間做複製
    • 這樣就算整個數據中心掛了，你還是可以從另一個AZ重新獲得數據而不丟失任何寫操作
  • 對於RDS來說，有且僅有一個EC2實例作為數據庫
    • 這個數據庫將它的data page和WAL Log存儲在EBS，而不是對應服務器的本地硬盤
  • 當數據庫執行了寫Log或者寫page操作時，這些寫請求實際上通過網絡發送到了EBS服務器
  • 每一次數據庫軟件執行一個寫操作，Amazon會自動的，將寫操作拷貝發送到另一個數據中心的AZ中
  • 每一次寫操作，數據除了發送給AZ1的兩個EBS副本之外，還需要通過網絡發送到位於AZ2的副數據庫
    • 副數據庫接下來會將數據再發送給AZ2的兩個獨立的EBS副本

這種Mirrored MySQL比Aurora慢得多的原因是，它通過網絡傳輸了大量的數據

Aurora

  1. 在替代EBS的位置，有6個數據的副本，位於3個AZ，每個AZ有2個副本
    • 這里通過網絡傳遞的數據只有Log條目
      • 存儲系統不再是通用（General-Purpose）存儲，這是一個可以理解MySQL Log條目的存儲系統
  2. Aurora並不需要6個副本都確認了寫入才能繼續執行操作 (Quorum)
    • 只要Quorum形成了，也就是任意4個副本確認寫入了，數據庫就可以繼續執行操作
      • 可以處理斷線、太慢的node
    • Quorum
      • 假設有N個副本。為了能夠執行寫請求，必須要確保寫操作被W個副本確認，W小於N
      • Quorum系統要求，任意你要發送寫請求的W個服務器，必須與任意接收讀請求的R個服務器有重疊
        • 這樣任意W個服務器至少與任意R個服務器有一個重合 ($W+R>=N$)
      • 客戶端讀請求可能會得到R個不同的結果，哪一個是正確的呢？
        • 投票?
          • 可能只有一個是對的
            • 只能確保Read Quorum必須至少與Write Quorum有一個服務器是重合的
        • 版本號（Version）
          • 每一次執行寫請求，你需要將新的數值與一個增加的版本號綁定
          • 從Read Quorum得到了一些回复，客戶端可以直接使用其中的最高版本號的數值
      • Quorum系統可以調整讀寫的性能。通過調整Read Quorum和Write Quorum，可以使得系統更好的支持讀請求或者寫請求
    • Aurora’s Quorum
      • 不會直接覆蓋資料，append log
        • Quorum系統通常讀寫的數據都是相同的
      • 數據庫服務器寫入的是Log條目，但是讀取的是page
        • 數據庫服務器會記錄每一個存儲服務器
          • 接收了多少Log
          • 收到的最高連續的Log條目號
        • 當一個數據庫服務器需要執行讀操作，它只會挑選擁有最新Log的存儲服務器，然後只向那個服務器發送讀取page的請求
      • 請求發送到存儲服務器，會要求存儲服務器返回當前最新的page數據。在這個時候，存儲服務器才會將Log條目中的新數據更新到page，並將page寫入到自己的磁盤中，之後再將更新了的page返回給數據庫服務器
      • 數據庫服務器有時也會使用Quorum Read!!
        • 如果DB壞了，監控系統可以檢測到Aurora數據庫服務器崩潰
        • 之後就會要求store server把還沒完成的transation丟了
        • 去找遺失的transaction id，對此跑Quorum Read
        • 讓連到的store server保留遺失的transaction id之前的log

sharding

目前為止，我們已經知道Aurora將自己的數據分佈在6個副本上，每一個副本都是一個計算機，上面掛了1-2塊磁盤。

但是如果只是這樣的話，我們不能擁有一個數據大小大於單個機器磁盤空間的數據庫

因為雖然我們有6台機器，但是並沒有為我們提供6倍的存儲空間

Amazon的做法是將數據庫的數據，分割存儲到多組存儲服務器上，每一組都是6個副本，分割出來的每一份數據是10GB

如果一個數據庫需要20GB的數據，那麼這個數據庫會使用2個PG（Protection Group），其中一半的10GB數據在一個PG中，另一半的10GB數據存儲在另一個PG中

recover

一個store server會有其他PG的其中一塊，如果store server掛了，怎麼復原? 對於每一個數據塊，我們會從Protection Group中挑選一個副本，作為數據拷貝的源。 之後，就可以並行的通過網絡將100個數據塊從100個源拷貝到100個目的

single write

對於Aurora來說，通常會有非常大量的只讀數據庫查詢

對於寫請求，可以只發送給一個數據庫，因為對於後端的存儲服務器來說，只能支持一個寫入者 Log需要按照數字編號，如果只在一個數據庫處理寫請求，非常容易對Log進行編號

當客戶端向只讀數據庫發送讀請求，只讀數據庫需要弄清楚它需要哪些data page來處理這個讀請求，之後直接從存儲服務器讀取這些data page，並不需要主數據庫的介入

只讀數據庫也需要更新自身的緩存，所以，Aurora的主數據庫也會將它的Log的拷貝發送給每一個只讀數據庫

cache & Transaction

我們不想要這個只讀數據庫看到未commit的事務。所以，在主數據庫發給只讀數據庫的Log流中，主數據庫需要指出，哪些事務commit了

數據庫背後的B-Tree結構非常複雜，可能會定期觸發rebalance(需要有原子性)

數據庫服務器可以通知存儲服務器說，這部分複雜的Log序列只能以原子性向只讀數據庫展示，也就是要就全展示，不然就不展示 (微事務（Mini-Transaction）)

教訓

數據庫和存儲系統基本是一起開發出來的，數據庫和存儲系統以一種有趣的方式集成在了一起 通常我們設計系統時，需要有好的隔離解耦來區分上層服務和底層的基礎架構 但是在Aurora面臨的問題中，性能問題是非常嚴重的，它不得不通過模糊服務和底層基礎架構的邊界來獲得35倍的性能提升

雲基礎架構中什麼更重要的隱含信息

  • 需要擔心整個AZ會出現故障
  • 需要擔心短暫的慢副本，這是經常會出現的問題
  • 網絡是主要的瓶頸，畢竟Aurora通過網絡發送的是極短的數據，但是相應的，存儲服務器需要做更多的工作
    • 明顯，從Amazon看來，網絡容量相比CPU要重要的多

Frangipani

緩存一致性是指，如果我緩存了一些數據，之後你修改了實際數據但是並沒有考慮我緩存中的數據，必須有一些額外的工作的存在，這樣我的緩存才能與實際數據保持一致

大部分的討論都會假設Petal就是一個被所有Frangipani使用的，基於網絡的共享磁盤。你可以通過一個塊號或者磁盤上的一個地址來讀寫數據，就像一個普通的硬盤一樣

在每個工作站或者說每個Frangipani服務器上要持有緩存之外，我們還需要支持Write-Back緩存。 這意味著，如果我想要修改某個數據，比如說我修改了一個文件，只要沒有其他的工作站需要看到我的改動，Frangipani通過Write-Back緩存方式管理這些數據

在這樣的架構下，一個非常重要的後果是，文件系統的邏輯需要存在於每個工作站上，所有的複雜的邏輯都在工作站中的Frangipani模塊中

所有的這些修改最初只會在本地緩存中存在，因此類似於創建文件的操作可以非常快的完成，因為只需要修改本地的內存中對於磁盤的緩存。而這些修改要過一會才會寫回到Petal (複雜度的開始)

Frangipani的挑戰（Challenges）

  1. 緩存
    • 文件系統必須要做一些事情來確保客戶端可以讀到最新的寫入文件 (強一致或者線性一致)
      • 但是在一個緩存的環境中，現在說的一致性的問題不是指存儲服務器的一致性，而是
        • 指工作站上的一些修改需要被其他工作站看到 (Cache Coherence)
    • 由於Write-Back緩存，可能會在本地的緩存中堆積了大量的修改
      • 如果我的工作站崩潰了，但是這時這些修改只有部分同步到了Petal，還有部分仍然只存在於本地
        • 我的工作站在執行操作的過程中的崩潰，最好不要損壞其他人同樣會使用的文件系統 (crash recovery)
  2. 去中心化的架構帶來的大量的邏輯存在於客戶端之中進而引起的問題
    • 因為所有的文件和目錄都是共享的，非常容易會有兩個工作站在同一個時間修改同一個目錄 (Atomicity)
      • 我們希望類似於創建文件，刪除文件這樣的操作表現的就像即時生效的一樣，同時不會與相同時間其他工作站的操作相互干擾

緩存一致性

Frangipani的緩存一致性核心是由鎖保證的，我們之後在原子性和故障恢復中將會再次看到鎖。

Lock server

  • server 本身
    • file到owner的map
      • 我們假設鎖是排他鎖（Exclusive Lock），儘管實際上Frangipani中的鎖更加複雜可以支持兩種模式：要么允許一個寫入者持有鎖，要么允許多個讀取者持有鎖
  • workstation
    • file, lock state, file content的table
      • BUSY: 正在跑syscall
      • IDLE: syscall跑完了
        • 只要係統調用結束了，工作站會在內部釋放鎖
        • 但是從鎖服務器的角度來看，工作站仍然持有鎖 (延遲將鎖還給鎖服務器)
          • 像是folder，就算read好，也許還會在目錄底下再做一些事

Frangipani應用了很多的規則，這些規則使得Frangipani以一種提供緩存一致性的方式來使用鎖

  • 工作站不允許持有緩存的數據，除非同時也持有了與數據相關的鎖
  • 先向Petal存儲系統寫數據，之後再釋放鎖
    • 如果你在釋放鎖之前，修改了鎖保護的數據，那你必須將修改了的數據寫回到Petal，只有在Petal確認收到了數據，你才可以釋放鎖
    • 最後再從工作站的lock表單中刪除關文件的鎖的記錄和緩存的數據

緩存一致性的訊息

  • Request: 拿鎖
  • Grant: lock server通知拿到鎖了
    • 如果從鎖服務器的lock表單中發現鎖已經被其他人持有了，那鎖服務器不能立即交出鎖。
    • 但是一旦鎖被釋放了，鎖服務器會回復一個Grant消息給工作站
      • 這裡的Request和Grant是異步的
  • Revoke: 要求歸還鎖
    • 如果別人要用，同時workstation的lock state是idle，就會開始跑release lock
  • Release: 還鎖
    • 在還之前會先把log與髒的資料寫回去

優化

  1. idle做延遲還鎖
  2. Frangipani有共享的讀鎖（Shared Read Lock）和排他的寫鎖（Exclusive Write Lock）

原子性（Atomicity）

要么發現文件不存在，要么文件完全存在，但是我們絕不希望它看到中間狀態

Frangipani在內部實現了一個數據庫風格的事務系統，並且是以鎖為核心。並且，這是一個分佈式事務系統

  1. 首先我的工作站需要獲取所有我需要讀寫數據的鎖，在完成操作之前，我的工作站不會釋放任何一個鎖
  2. 為了遵循一致性規則（11.3），將所有修改了的數據寫回到Petal之後，我的工作站才會釋放所有的鎖
  3. 之後完成所有的步驟，比如完成所有數據的更新，並將更新寫入到Petal，最後釋放鎖

Frangipani使用鎖實現了兩個幾乎相反的目標。 對於緩存一致性，這裡使用鎖來確保寫操作可以被看見。 但是對於原子性來說，鎖確保了人們在操作完成之前看不到任何寫操作

Frangipani與其他的系統一樣，需要通過預寫式日誌（Write-Ahead Log，WAL，見10.2）實現故障可恢復的事務（Crash Recoverable Transaction）

當一個工作站需要完成涉及到多個數據的複雜操作時，在工作站向Petal寫入任何數據之前，工作站會在Petal中自己的Log列表中追加一個Log條目，這個Log條目會描述整個的需要完成的操作

只有當這個描述了完整操作的Log條目安全的存在於Petal之後，工作站才會開始向Petal發送數據

  1. Frangipani對於每個工作站都保存了一份獨立的Log (一般都是share一個log)
  2. 工作站的Log存儲在Petal，而不是本地磁盤中
    • 每個工作站的獨立的Log，存放在公共的共享存儲中
      • log裡面有 (Log只包含了對於元數據的修改)
        • Log序列號 (找最新的log)
        • 數組中的每一個元素會有一個Petal中的塊號（Block Number），一個版本號和寫入的數據
          • 類似的數組元素會有多個，這樣就可以用來描述涉及到修改多份文件系統數據的操作。
      • 向Petal寫入數據的時候，如果我們在中途故障退出了，我們需要確認其他組件有足夠的信息能完成我們未完成修改 (log)
      • 如果出事可以讓其他workstation利用原本的log redo!!

Distributed Transaction

  • 並發控制（Concurrency Control）
    • 並發控制就是可序列化的別名
    • Pessimistic (mutex)
      • 兩階段鎖（Two-Phase Locking）
        1. 在使用任何數據之前，在執行任何數據的讀寫之前，先獲取鎖
        2. 事務必須持有任何已經獲得的鎖，直到事務提交或者Abort，你不允許在事務的中間過程釋放鎖
    • Optimistic (rwlock)
  • 原子提交（Atomic Commit）
    • 從部分故障中恢復的能力
    • 兩階段提交（Two-Phase Commit）
      • 除了原本的DB，還有一台Transaction Coordinator
        1. 因為是transaction，各自的DB會拿有關的所有鎖
        2. 開始跑指令
        3. 發preare問參與事務的DB好了沒
          • TC發prepare/commit之前掛了
            • 基於log，重發 (可能需要標這是重複的)
          • TC發prepare/commit之後掛了
            • log還原自己的狀態
          • DB收到preare前掛了
            • DB重開，發現沒有log，回abort
          • DB收到prepare在回了yes之後掛掉
            • transaction的動作、相關狀態，再回prepare之前都要在log
            • DB重開，有log與prepare，之後TC發prepare就能回yes
        4. 都好了就發commit
          • DB收到commit之後掛了
            • 回yes之前掛了
              • redo, 回yes
            • 回完yes之後掛了
              • 這個時候所有有關的log都被清了(也許)與該改的都寫到HDD了
              • 有可能DB是找不到commit相關訊息的
              • 不論怎樣，DB都會直接回yes

如果遇到網路斷線?

  • TC可以retry，如果太久就abort
  • DB是根據prepare的回答
    • no
      • 自己abort，之後TC的prepare就發no
    • yes
      • 就是等TC的指令，剩下都不能動!!
        • 只要回prepare yes就是等 (BLOCK)
        • A或者B不能決定Commit還是不Commit事務，A和B之間不會交互來達成一致並完成事務的Commit，相反的只有事務協調者可以做決定

數據庫通常對於正確性有一個概念稱為ACID

可序列化是指，並行的執行一些事物得到的結果，與按照某種串行的順序來執行這些事務，可以得到相同的結果

使用Raft可以通過將數據複製到多個參與者得到高可用。 Raft的意義在於，即使部分參與的服務器故障了或者不可達，系統仍然能工作。 Raft能做到這一點是因為所有的服務器都在做相同的事情，所以我們不需要所有的服務器都參與，我們只需要過半服務器參與

兩階段提交，參與者完全沒有在做相同的事情，每個參與者都在做事務中的不同部分，比如A可能在對X加1，B可能在對Y減1。 所以在兩階段提交中，所有的參與者都在做不同的事情。 所有的參與者都必須完成自己那部分工作，這樣事務才能結束，所以這裡需要等待所有的參與者。

Raft完全就是可用性，而兩階段提交完全不是高可用的，系統中的任何一個部分出錯了，系統都有可能等待直到這個部分修復

同時具備Raft的高可用性，但同時又有兩階段提交的能力將事務分包給不同的參與者。 這裡的結構實際上是，通過Raft或者Paxos或者其他協議，來複製兩階段提交協議裡的每一個組成部分。

spanner

需求 & 前提

  • 大部分的workload都是read-only transactions
    • read要快
      • spanner區分read/write & read/only transaction
  • 更好的synchronous replication
  • flexible sharding
  • 分散式transaction (橫跨多個shard)
    • 2pc真的慢，要別的方法
  • External consistency
    • linearizability + serializability

為了可用性，所以把distributed tranasaction的每個元件包成one Paxos group

read/write transactions

  • two-phase commit (2pc) with Paxos-replicated participants
    • 基本上與2pc步驟一樣但是所有溝通都是由各個shard的leader做
      • 在shard的leader中有lock table
  • 2pc所以很慢
  • parallelism
    • many clients, many shards

read/only transactions

  • 兩個重點
    • 沒有2pc
    • 只從local replica讀
  • 正確性
    • Serializable
    • Externally consistent
      • 為什麼不直接讀最新commit的值?
        • T1: Wx Wy C
        • T2: Wx Wy C
        • T3: Rx Ry
  • Snapshot Isolation (SI)
    • 用wall-time做timestamp(TS)
      • 怎麼synchronize wall-time?
        • TrueTime
          • TTinterval = [ earliest, latest ]
          • 在這個區間一定有對的時間
    • 只拉同一個TS的資料(最少不能超過read的TS)
      • 怎麼確保replica夠新?
        • replica “safe time”
          • read上給時間，直到replica上看到write的時間夠後面才serve
    • 每個transaction都有time-stamp
      • r/w: commit time.
      • r/o: start time.
      • Synchronized timestamps確保external consistency (commit wait)
    • SI確保serializable r/o transactions
  • 怎麼確保r/w在r/o之前完成 (Commit wait)
    • 定義transacation的TS
      • xaction TS = TT.now().latest
      • for r/o, at start time
      • for r/w, when commit begins
    • 在r/w跑commit之前，Commit wait
      • Before commit, delay until TS < TS.now().earliest

FaRM, Optimistic Concurrency Control

FaRM & Spanner差在

  • 都用2pc
  • Spanner
    • geographic replication
    • r/o transaction & TrueTime
    • bottleneck: speed of light and network delays
  • FaRM
    • 都在同一個data center
    • RDMA(remote dma)限制只能用Optimistic Concurrency Control (OCC)
      • Optimistic Concurrency Control
        • steps
          • read不用lock
          • write直到commit才會真的寫入
          • commit檢查有沒有衝突
        • 不用server參與!!
          • one-sided RDMA
            • sender給mem addr, read整個cache line
    • bottleneck: CPU time on servers
    • 都用ram存資料
      • non-volatile RAM
        • 每個rack都有電池在出事之前可以把ram寫到hdd

架構

API(simplified)

  • FaRM transaction API (simplified):
    • txCreate()
    • o = txRead(oid) – RDMA
      • oid?
        • <region #, address>
        • region # indexes a mapping to [ primary, backup1, ... ]
        • target RDMA NIC uses address directly to read or write RAM
    • o.f += 1
    • txWrite(oid, o) – purely local
    • ok = txCommit() – Figure 4

流程

  1. 跑指令
  2. LOCK
    • 檢查lock state, version
    • 往primary上打log，之後等return yes
    • VALIDATE
      • one-sided RDMA read to re-fetch object’s version and lock flag
        • fail early
        • T1: Rx Ly Vx Cy
        • T2: Ry Lx Vy Cx
          • LOCKs will both succeed
          • VALIDATEs will both fail
    • COMMIT BACKUP
      • 在commit之前至少backup要有法定人數台機器有新的值
        • a committed write might be revealed as soon the first COMMIT-PRIMARY is sent
      • LOCK 通知 primaries 有新值
      • COMMIT-BACKUP 通知 backups 有新值
        • 不一定馬上處理，會放在log中
      • 直到LOCKs與COMMIT-BACKUPS都完成，TC才發COMMIT-PRIMARY
        • 2pc中COMMIT之後就是
          • 狀態都ok了
          • 不能回頭了
  3. COMMIT PRIMARY
    • 就是最後的commit
      • 往primary上打log
    • primary清狀態, version++, 把值寫進去
  • fault tolerance?
    • 假設總是有一個backup在

spark

skip

Scaling Memcache at Facebook

網站的成長旅程

  1. 一台host = web server + DB + app
    • app吃爆cpu
  2. 多台web server + app, 一台DB
    • DB只有一台
  3. 多台web server + app, 多台DB
    • 做shard，如果沒有特別熱門的key就沒事
      • cross-shard transactions & queries基本不能做了
    • read變慢!!
  4. 多台web server + app, 多台DB for write, cache for read
    • cache怎麼與db sync
    • 沒有成功cache hit，DB的load直接起飛
      • warm-up
      • cache miss
    • 接下去就是DB write，但這很難解

教訓

  • partition 或 replicate

    • partition: divide keys over mc servers
      • good: ram花得少 (kv不用重複copy)
      • bad: web server要一次問很多台
        • huge “fan-out” => parallel fetch, in-cast congestion
      • 適用: key沒有很熱門 (不用每個data center都放)
    • replicate: divide clients over mc servers
      • good: 比較少tcp連線
      • bad: 比較少key能被cache
      • 適用: key很熱門

  • region (data center)

    • lower RTT to users
    • quick local reads, from local mc and DB
      • writes 很慢，一定要到primary
    • 多 mc clusters 在 每個 region
      • “regional pool” shared by all clusters => unpopular objects (no need for many copies)

  • warmup is painful

    • get miss => 打DB => 去set cache
      • 只給第一個req設定cache的權限(lease)
      • 其他就先等
        • mc tells others “try get() again in a few milliseconds”

  • 容錯?

    • pool of idle mc servers, clients only use after mc server fails

  • 網路

    • get
      • UDP
    • set
      • TCP
    • 把req累積成一個packet
      • mcrouter batches many requests into each packet

consistency

  1. not more than a few seconds stale
  2. read-your-own-writes (due to delete())
    • cache怎麼與DB sync (delete)
      1. DB去做
      2. writing client去做

delete會有racing

Race 1

真正的race, 用樂觀鎖、rwlock解

k not in cache
C1 get(k), misses
C1 v1 = read k from DB
    C2 writes k = v2 in DB
    C2 delete(k)
C1 set(k, v1)

get時會給一個lease，如果有delete就會把lease取消掉，之後看有沒有lease決定要不要吃這個set

Race 2

與race3很像，都是因為write傳播太慢，導致source資料不對，這裡因為是cold所以只能從hot copy，所以wait hot試試看有沒有可能ok

在warm-up時，get從warm cluster拉資料
k starts with value v1
C1 updates k to v2 in DB
C1 delete(k) -- in cold cluster
C2 get(k), miss -- in cold cluster
C2 v1 = get(k) from warm cluster, hits
C2 set(k, v1) into cold cluster

cold cluster會在2秒中忽略set，去等warm收到DB資料

Race 3

source是local db，但是我們知道才剛update，所以標上要從remote拉

k starts with value v1
C1 is in a secondary region
C1 updates k=v2 in primary DB
C1 delete(k) -- local region
C1 get(k), miss
C1 read local DB  -- sees v1, not v2!
later, v2 arrives from primary DB

C1做delete時把key標上"remote mark" 讓後面的人去DB拉資料

Causal Consistency, COPS

we’ve seen two solutions for geo-replication Spanner writes involve Paxos and perhaps two-phase commit Paxos quorum for write must wait for some remote sites no one site can write on its own but has read transactions, consistent, fairly fast Facebook / Memcache writes must go to the primary site’s MySQL again, non-primary sites cannot write on their own but reads are blindingly fast (1,000,000 per second per memcache server)

情境

  • 3 data centers
  • data centers有各自的shard

ver1: eventually consistent

  • reads and writes just local shard

    • 會自己把write推到其他data center

  • eventually consistent

    • client看到update的順序不確定
    • write要等夠久才看的到
    • 例子
      • quorum, with overlap (Dynamo/Cassandra)
      • local write + asynchronously push

  • 每個put加個timestamp(version)?

    • COPS用Lamport clocks設定timestamp
      • Tmax = highest v# seen (from self and others)
      • T = max(Tmax + 1, wall-clock time)
    • concurrent write時，要選哪一個write?
      • last-writer-wins?
        • increment a counter時會起飛
      • 需要其他方式做merge
        • real transactions
        • mini-transactions (atomic)
        • 特定的合併方式 (set union)
        • action transform
        • mvcc
      • resolution of conflicting writes is a problem for eventual/causal consistency
        • no single “serialization point” to implement atomic operations or transactions

ver2: barrier

  • 留個sync指令
    • 直到確認每個datacenter都有夠新的key才return
  • 需要等 (慢)
    • 但其他work其實寫都要等
      • spanner等majority of replica
      • fb’s cache等primary datacenter
  • 不需要transaction不失為一個不錯的方案

ver3: log

  • 每個datacenter都有一個log server
    • write對應到一個log
  • datacenter把log送到其他datacenter
    • datacenter照log順序跑
  • log server會是bottleneck

COPS: client’s context

  • client的context會記錄下指令的順序
    • 這就是dependency
get(X)->v2
    context: Xv2
get(Y)->v4
    context: Xv2, Yv4
put(Z, -)->v3
    client sends Xv2, Yv4 to shard server along with new Z
    context: Xv2, Yv4, Zv3
    (COPS optimizes this to just Zv3)

shard怎麼處理?

  • local shard
    • 收到put(Z, -, Yv4)
      • 設定時間: v# = 3 for Z
      • write: Z, -, v3
      • 傳送到其他datacenter(不等reply)
  • remote shard
    • 收到Z/-/v3/Yv4
      • 會等到Yv4到了才設定Z/-/v3

causal consistency

  • dependency來自?

    • client的一連串puts and gets
    • 當read來自其他client資料的時候

  • 這dependency是transitive

  • 可能拿到比想像中更新的資料

    • 不能用在transaction或是snapshot

  • get_trans(k1,k2,…)

    • client檢查dep對不對，不對就重拿不對的
    • 只有read的mini-transaction
    • scenerio: ACL
      • get(ACL), then get(list)?
        • what if someone deletes you from ACL, then adds a photo?
      • get(list), then get(ACL)?
        • what if someone deletes photo, then adds you to ACL?
for ACL / list example:
  C1: get_trans(ACL, list)
  C1: get(ACL) -> v1, no deps
      C2: put(ACL, v2)
      C2: put(list, v2, deps=ACL/v2)
  C1: get(list) -> v2, deps: ACL/v2
  (C1 checks dependencies against value versions)
  C1: get(ACL) -> v2
  (now C1 has a causally consistent pair of get() results)

Secure Untrusted Data Repository (SUNDR)

integrity

Naive design: sign file contents.

  • 只能保證檔案內容與作者是誰
  • 但server可以
    • 亂送其他版本的檔案
    • 假裝檔案不在

Fork consistency

  • 每個fork看到都一樣
  • 容易找出攻擊
  • 難以假造log

SUNDR: log of operations.

  • log: fetch or modify, user, sig.
    • 簽名要包含所有log
  • steps
    • 下載log
    • check log
    • 做事(Construct FS state)
    • 加上log與簽名
    • 上傳log
  • 包含所有log?!
    • 超慢
      • 簽名慢
      • check慢
    • 優化
      1. 只看最後一個簽名 (前面的一定被確認過了)
      2. 只要簽自己改過的地方就好 (一堆inode => i-table)

Idea: signed version vectors. Version vector: user -> how many operations that user performed. Version structure: signed i-handle together with version vector.

Consistency

Consistency就是發生效果的亂序程度 越弱越難預期

有兩個排序單位

  • operation
  • transaction

eventual Consistency 總有一天會拿到最新的結果 沒有時間序、執行序

Causal Consistency 某部分效果發生是有序的(有因果關係) 這也是通常concurrent programming使用的Consistency

Sequential Consistency 效果發生照執行序來，所以如果concurrent可能有超過一種排列組合

因為一般concurrent programming沒有transaction的概念，所以從這開始就有人叫strong Consistency

Linearizability 照執行序來、時間序 (看前面的定義) 但是transaction的執行順序不確定(也許r/w有序，但ro穿插其間)

Strict Serializability 照執行序來、執行序、transaction的執行順序確定

一般提到distributed system的consistemcy最多提到上面5種，因為通常討論transaction都是DB範圍

比較完整的圖在這 可以到來源看定義

這邊備註一下PRAM，就是FIFO Consistency(zookeeper)

Ref

Consistency Consistency Models

bitcoin

在byzantine中共識

  • 像SUNDR
    • 簽過的log與fork
  • 不像SUNDR
    • 分散式的選用fork

組成

  • ledger record

    • pub(user1)
      • 新owner的public key
    • hash(prev)
      • 前一個transaction的hash
    • sig(user2)
      • 前owner的簽名
    • (其他: amount (fractional), multiple in/out, …)

  • transaction 例子

    • Y 擁有一枚硬幣，之前由 X 給它：
      • T6：pub(X)，…
      • T7：pub(Y)、hash(T6)、sig(X)
    • Y 從 Z 買了一個漢堡包並用這枚硬幣付款
    • Z 將公鑰發送給 Y
    • Y 創建一個新交易並對其進行簽名
      • T8：pub(Z)、hash(T7)、sig(Y)
    • Y 向 Z 發送交易記錄
    • Z 驗證：
      • T8 的 sig(Y) 對應 T7 的 pub(Y)
    • Z給Y漢堡包

  • block chain

    • 一個coin可以花兩次嗎?
      • 可以，創兩個transaction
        • coin其實源自於transaction，有transaction才有coin
      • 別阿
    • 需要一個共同依據
      • fork consistency
        • 有所有交易紀錄
        • 大家看到的都一樣的
        • 做了就不能反悔
      • 參與者可能會做壞事
        • 挑最長的chain
    • block有
      • hash(prevblock)
      • set of transactions
      • current time (wall clock timestamp)
      • “nonce” (類似隨機資料)
    • 誰可以產生block
      • miner (proof-of-work, nonce要有N個0，所以要try)
    • 怎麼交易
      • 假設現在block在B7
      • payer先flood我要交易到peer
      • miner把交易記錄起來，等B8(目前mine的block)好
        • 每10分鐘一個block產生
      • 把交易記錄放到B9
      • payee看到交易記錄就可以接受交易
    • 能產生分支嗎?
      • 能
        • 在同一時間找到同樣的nonce
        • network問題
      • 怎麼處理
        • miner挑最長的append
          • 這能hack吧 (yes)
            • 但要能做出更長的chain

壞處

  • 超慢
  • flood限制效能與攻擊點
  • 只要有人有過半的算力就能控制整個chain
  • user要保護好private key

DAPP

DAPP怎麼工作的

  • 從remote server拉資料
  • DAPP處理寫回去

好處

  • 換app很方便，因為資料不會被綁在app上
    • todo的項目可以在todo list, microsoft todo上通用
  • app有通用的資料格式

壞處

  • 分散式很複雜
  • 資料加密與server安全

Ref

6.824的部分中文翻譯 MIT6.824_2021_note 分布式系统概念简介及其问题的描述 Design Principles