分布式系統(tǒng)（事務(wù)處理）-創(chuàng)新互聯(lián)

文章目錄
  • 事務(wù)（Transaction）
  • 分布式事務(wù)
  • 原子提交協(xié)議
    • 單階段提交
    • 兩階段提交
    • 三階段提交
  • 串行等價(jià) / 并發(fā)控制
  • 分布式死鎖
    • 鎖超時(shí)
    • 全局等待圖
    • 邊追逐算法
  • 事務(wù)放棄時(shí)的恢復(fù)
  • 服務(wù)器崩潰后的恢復(fù)
    • 恢復(fù)文件
    • 重組恢復(fù)文件
    • 日志
    • 從Crash 中恢復(fù)
    • 2PC 的恢復(fù)

創(chuàng)新互聯(lián)建站從2013年開(kāi)始，先為洋縣等服務(wù)建站，洋縣等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為洋縣企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問(wèn)題。事務(wù)（Transaction）

特性：ACID

  • 原子性（Atomic）：對(duì)于外部世界，事務(wù)不可分割
  • 一致性（Consistent）：事務(wù)不違反系統(tǒng)不變量（system invariants）
  • 隔離性（Isolated）：并發(fā)事務(wù)之間互不干擾
  • 持久性（Durable）：一旦事務(wù)提交，其影響是永久的

事務(wù)的 API，

T = open Transaction{# 對(duì)象訪問(wèn)
        # 數(shù)據(jù)運(yùn)算
        ...
        abort Transaction
        ...
	}close Transaction

事務(wù)的實(shí)現(xiàn)技術(shù)，

  • 串行等價(jià) / 并發(fā)控制：兩階段鎖、時(shí)間戳排序、樂(lè)觀并發(fā)控制
  • 事務(wù)放棄后的恢復(fù)：嚴(yán)格兩階段鎖

故障模型，

  • 磁盤故障：
    • 寫操作失敗、文件寫錯(cuò)誤、數(shù)據(jù)塊損壞
    • 校驗(yàn)和、原子寫
  • 服務(wù)器故障：
    • 運(yùn)行時(shí)崩潰、重啟時(shí)崩潰
    • 進(jìn)程替換
  • 通信故障：
    • 延遲、丟失、重復(fù)、損壞
    • 校驗(yàn)和、可靠的 RPC 機(jī)制
  • 無(wú)拜占庭故障
分布式事務(wù)

訪問(wèn)由多個(gè)服務(wù)器管理的對(duì)象的事務(wù)被稱為分布式事務(wù)。當(dāng)一個(gè)分布式事務(wù)結(jié)束時(shí)，所有參與該事務(wù)的服務(wù)器必須全部提交，或全部放棄。有一個(gè)服務(wù)器扮演協(xié)調(diào)者，由它來(lái)保證在所有的服務(wù)器（參與者）上獲得同一結(jié)果。協(xié)調(diào)者和參與者之間最常用的協(xié)議是兩階段提交協(xié)議（two-phase commit，2PC）。

有兩種分布式事務(wù)：

  1. 平面事務(wù)（flat transaction）：每個(gè)事務(wù)等一個(gè)請(qǐng)求結(jié)束后才發(fā)起下一個(gè)請(qǐng)求，順序訪問(wèn)各個(gè)服務(wù)器上的對(duì)象。
  2. 嵌套事務(wù)（nested transaction）：每個(gè)事務(wù)包含若干子事務(wù)，同一層次的事物可以并發(fā)執(zhí)行；如果它們?cè)L問(wèn)服務(wù)器上不同的對(duì)象，那么這些事務(wù)可以并行執(zhí)行。

在這里插入圖片描述

協(xié)調(diào)者提供Coordinator接口，有三個(gè)基本操作

  • open Transaction，由客戶調(diào)用，返回事務(wù)標(biāo)識(shí)（TID）
  • close Transaction，由客戶調(diào)用，
  • abort Transaction ，由協(xié)調(diào)者或參與者調(diào)用

Coordinator接口提供一個(gè)額外的方法 join(TID,reference to participant)，該方法在一個(gè)新的參與者參加到事務(wù)中的時(shí)候使用

  • 通知協(xié)調(diào)者，一個(gè)新的參與者已加入到事務(wù) TID 中

  • 協(xié)調(diào)者將新的參與者記錄到參與者列表中

在這里插入圖片描述

當(dāng)客戶啟動(dòng)一個(gè)事務(wù)時(shí)，

  1. 客戶向協(xié)調(diào)者發(fā)送 open Transaction 請(qǐng)求
  2. 協(xié)調(diào)者返回 TID 給客戶
  3. 客戶直接發(fā)送 request 給參與者，并攜帶上 TID
  4. 參與者收到請(qǐng)求，調(diào)用 join 方法通知協(xié)調(diào)者，參與到該事務(wù)中
  5. 每個(gè)參與者記錄所有參與事務(wù)的可恢復(fù)對(duì)象（Recoverable objects）
  6. 事務(wù)結(jié)束后，協(xié)調(diào)者決定提交或者放棄事務(wù)
原子提交協(xié)議

事務(wù)的原子特性要求，分布式事務(wù)結(jié)束時(shí)，它的所有操作要么全部成功，要么全部取消。

  • 在一個(gè)分布式事務(wù)中，存在客戶-協(xié)調(diào)者-參與者三方

  • 協(xié)調(diào)者、參與者之間僅有的通信是 join 請(qǐng)求

  • 客戶請(qǐng)求了多個(gè)服務(wù)器上的操作，客戶請(qǐng)求協(xié)調(diào)者提交事務(wù)，協(xié)調(diào)者啟動(dòng)提交協(xié)議

單階段提交

由協(xié)調(diào)者告訴所有參與者是提交或放棄：

  1. 協(xié)調(diào)者不斷地向所有參與者發(fā)送提交或放棄請(qǐng)求，
  2. 直到所有參與者確認(rèn)已執(zhí)行完相應(yīng)操作。

存在問(wèn)題：不允許任何服務(wù)器單方面放棄自己的事務(wù)，然而實(shí)際上每個(gè)服務(wù)器都可能會(huì)掛掉。

兩階段提交

兩階段提交協(xié)議（2PC：Two-Phrase Commit），它允許任何一個(gè)服務(wù)器自行放棄屬于自己的事務(wù)。

故障模型：

  • 異步通信系統(tǒng)，消息可能丟失、損壞、重復(fù)
  • 服務(wù)器僅可能 crash，沒(méi)有隨機(jī)故障
  • 繞過(guò) FLP 不可能：crash 的進(jìn)程被替換，新進(jìn)程從持久存儲(chǔ)和其他進(jìn)程中獲取故障前的信息

一些操作：

  1. can Commit (trans)?

    協(xié)調(diào)者詢問(wèn)參與者，能否提交事務(wù)。參與者回復(fù) Yes / No

  2. do Commit (trans).

    協(xié)調(diào)者通知參與者，讓其提交事務(wù)。參與者提交事務(wù)

  3. do Abort (trans).

    協(xié)調(diào)者通知參與者，讓其放棄事務(wù)。參與者放棄事務(wù)

  4. have Committed (trans, participant).

    參與者通知協(xié)調(diào)者，自己完成了提交。

  5. get Decision (trans).

    當(dāng)參與者投票 Yes 一段時(shí)間后，未收到 do Commit 或者 do Abort 指令。那么就主動(dòng)詢問(wèn)協(xié)調(diào)者，事務(wù)最終的投票結(jié)果。

在這里插入圖片描述

兩階段提交協(xié)議，

  • 投票階段：
    1. 協(xié)調(diào)者發(fā)送 can Commit 給所有參與者，詢問(wèn)它們是否可以提交（能否完成事務(wù)、是否完成事務(wù)）
    2. 參與者如果投票 Yes，那么進(jìn)入 prepared 狀態(tài)（要在持久存儲(chǔ)中保存好事務(wù)的 update）
    3. 參與者如果投票 No，那么立即放棄事務(wù)，并 rollback 到事務(wù)之前的狀態(tài)（可恢復(fù)對(duì)象）
  • 提交階段：
    1. 協(xié)調(diào)者收集所有的 votes，
      1. 如果全是 Yes，那么決定 commit，通知參與者提交事務(wù)
      2. 如果存在 No，或者出現(xiàn)故障，那么決定 abort，通知參與者放棄事務(wù)
    2. 投了 Yes 的參與者，等待協(xié)調(diào)者的決定（在持久存儲(chǔ)中記錄這個(gè) decision）
      1. 如果是 do Commit，那么提交自己的事務(wù)，并向協(xié)調(diào)者發(fā)送 have Committed 確認(rèn)完成提交
      2. 如果是 do Abort，那么就放棄事務(wù)，并 rollback 到事務(wù)之前的狀態(tài)
      3. 如果等候超時(shí)，那么向協(xié)調(diào)者發(fā)送 get Decision，獲取最終的決定

三種超時(shí)情況：

  1. 投票階段，參與者完成事務(wù)之后，等待 can Commit 超時(shí)：?jiǎn)畏矫鏇Q定 abort 事務(wù)
  2. 提交階段，協(xié)調(diào)者等待 votes 超時(shí)：發(fā)送 do Abort 給參與者
  3. 提交階段，投票 Yes 的參與者處于“不確定”狀態(tài)，如果等待 decision 超時(shí)：不斷發(fā)送 get Decision 給協(xié)調(diào)者
  4. 由于可能出現(xiàn)任意多次的服務(wù)器或者通信故障，因此 2PC 僅保證最終完成，但沒(méi)有時(shí)間限制（期間阻塞參與者，阻塞期間可能出現(xiàn)數(shù)據(jù)不一致）

2PC 需要 N N N 個(gè) can Commit 消息， N N N 個(gè) Yes / No 應(yīng)答， N N N 個(gè) do Commit 消息，一共 3 3 3 輪通信 3 N 3N 3N 個(gè)消息的開(kāi)銷（不包含 N N N 個(gè) have Committed 以及若干 g e t D e c i s i o n get Decision getDecision 消息）

2PC 的優(yōu)化：

  • One RM：只有一個(gè)資源管理器，退化為單階段提交，只需 3 3 3 輪通信（而非 4 4 4 輪）。
  • Read-Only Trans：只讀事務(wù)，無(wú)論最終是提交還是放棄，都只需要釋放對(duì)象的讀鎖。一旦收到 can Commit，就可以釋放鎖，然后就用 prepared-read-only 回應(yīng)協(xié)調(diào)者，告訴協(xié)調(diào)者后續(xù)不必發(fā)送 do Commit 或者 do Abort 決定。
  • Presumed abort：推斷事務(wù)一定會(huì)放棄，可以直接不寫日志
  • Cooperative Termination Protocol：協(xié)調(diào)終止協(xié)議，減少等待。每個(gè)參與者不僅知道協(xié)調(diào)者地址，還知道其他參與者的地址。參與者會(huì)保留 decision 一段時(shí)間。
三階段提交

三階段提交協(xié)議（2PC：Two-Phrase Commit），通過(guò)引入 pre-commit 階段，以及 timeout 策略，來(lái)減少整個(gè)集群的阻塞時(shí)間，提升系統(tǒng)性能。

第一階段：can - commit

  • 協(xié)調(diào)者向各個(gè)參與者發(fā)送 can Commit，詢問(wèn)是否可以執(zhí)行事務(wù)操作，并等待回復(fù)。

  • 各個(gè)參與者依據(jù)自身狀況回復(fù)一個(gè)預(yù)估值（此時(shí)不執(zhí)行事務(wù)，輕量級(jí)），

    1. 如果預(yù)估自己能夠正常執(zhí)行事務(wù)，那么就回應(yīng) Yes 投票，并進(jìn)入 prepared 狀態(tài)
    2. 否則，回應(yīng) No 投票，立即放棄事務(wù)

第二階段：pre - commit

  • 協(xié)調(diào)者根據(jù)第一階段的投票結(jié)果，采取相應(yīng)操作：

    1. 所有的參與者都返回 Yes，發(fā)送 pre Commit 預(yù)備提交事務(wù)
    2. 一個(gè)或多個(gè)參與者返回 No，發(fā)送 do Abort 放棄事務(wù)
    3. 協(xié)調(diào)者等待超時(shí)，發(fā)送 do Abort 放棄事務(wù)

  • 投票 Yes 的參與者根據(jù)收到的指令，采取相應(yīng)操作：

    1. 收到 pre Commit，那么就執(zhí)行事務(wù)，
      1. 如果完成了事務(wù)，發(fā)送 Yes 給協(xié)調(diào)者（但不要提交事務(wù)），并進(jìn)入 pre-committed 狀態(tài)
      2. 如果執(zhí)行事務(wù)失敗，就發(fā)送 No 給協(xié)調(diào)者，放棄事務(wù)
    2. 收到 do Abort，那么放棄事務(wù)，rollback
    3. 如果超時(shí)，那么放棄事務(wù)，rollback

第三階段：do - commit

  • 協(xié)調(diào)者根據(jù)第二階段的參與者執(zhí)行情況，采取相應(yīng)操作：

    1. 所有的參與者都返回 Yes，發(fā)送 do Commit 提交事務(wù)
    2. 一個(gè)或多個(gè)參與者返回 No，發(fā)送 do Abort 放棄事務(wù)
    3. 協(xié)調(diào)者等待超時(shí)，發(fā)送 do Abort 放棄事務(wù)

  • 投票 Yes 的參與者根據(jù)收到的指令，采取相應(yīng)操作：

    1. 收到 do Commit，那么提交事務(wù)
    2. 收到 do Abort，那么放棄事務(wù)，rollback
    3. 如果超時(shí)，那么默認(rèn)提交事務(wù)（消除了無(wú)限期的阻塞，但這可能會(huì)導(dǎo)致數(shù)據(jù)不一致）
串行等價(jià) / 并發(fā)控制

分布式系統(tǒng)的每個(gè)服務(wù)器上，都管理著很多的對(duì)象，它們負(fù)責(zé)保證并發(fā)事務(wù)訪問(wèn)這些對(duì)象時(shí)保持一致性。

  • 每個(gè)服務(wù)器負(fù)責(zé)對(duì)自己的對(duì)象應(yīng)用并發(fā)控制機(jī)制
  • 分布式事務(wù)中所有服務(wù)器共同保證事務(wù)以串性等價(jià)方式執(zhí)行
  • 可能的問(wèn)題：
    • 更新丟失，兩個(gè)事務(wù)同時(shí)讀取了舊值（ a ′ : = a + 1 , a ′ : = a + 2 a':=a+1,a':=a+2 a′:=a+1,a′:=a+2），導(dǎo)致其中一個(gè)事務(wù)的 update 被覆蓋（ a ′ ≠ a + 3 a' \neq a+3 a′=a+3）
    • 不一致檢索，一個(gè)檢索事務(wù)觀察了多個(gè)正在更新的值（ a ′ : = a ? 1 , b ′ : = b + 1 a':=a-1,b':=b+1 a′:=a?1,b′:=b+1），導(dǎo)致檢索結(jié)果與實(shí)際不一致（ a + b ≠ a ′ + b ′ a+b \neq a'+b' a+b=a′+b′）

串行等價(jià)性：

  1. 條件一：某個(gè)事務(wù)對(duì)于一個(gè)對(duì)象所有的訪問(wèn)，相對(duì)于其他事務(wù)的訪問(wèn)，是串行化的（一個(gè)事務(wù)中對(duì)同一對(duì)象的多次訪問(wèn)，都位于一個(gè)連續(xù)的臨界區(qū)內(nèi)）
  2. 條件二：兩個(gè)事務(wù)所有的沖突操作對(duì)（讀寫沖突、寫寫沖突），必須以相同的次序執(zhí)行訪問(wèn)（只要事務(wù) T T T 的對(duì)于一個(gè)對(duì)象的沖突訪問(wèn)在事務(wù) U U U 之前，那么對(duì)于其他對(duì)象的沖突訪問(wèn)都是同樣的因果序）

串行等價(jià)的交錯(cuò)執(zhí)行：并發(fā)事務(wù)交錯(cuò)執(zhí)行各個(gè)操作，它的綜合效果與按某種次序，一次只執(zhí)行一個(gè)事務(wù)的效果一樣（讀操作返回相同的值；事務(wù)結(jié)束時(shí)，所有對(duì)象的實(shí)例變量也具有相同的值）。

  • 可以解決更新丟失的問(wèn)題：

在這里插入圖片描述

  • 可以解決不一致檢索的問(wèn)題：

在這里插入圖片描述

通過(guò)加鎖來(lái)實(shí)現(xiàn)并發(fā)控制，達(dá)到串行等價(jià)性：

  1. 加鎖，串行化對(duì)象的訪問(wèn)（條件一）。事務(wù)把一個(gè)對(duì)象的所有訪問(wèn)，全都包含在同一個(gè)臨界區(qū)內(nèi)（一個(gè)對(duì)象只能加一次鎖）
  2. 兩階段鎖，確保沖突操作對(duì)的執(zhí)行次序相同（條件二）。事務(wù)釋放了任意一個(gè)鎖之后，不允許申請(qǐng)任何新的鎖（鎖增長(zhǎng)階段、鎖收縮階段）
  3. 嚴(yán)格兩階段鎖，防止臟數(shù)據(jù)讀取和過(guò)早寫入問(wèn)題。事務(wù)獲取到的鎖，必須在決定 commit 或者 abort 之后，才可以釋放（減小粒度，降低影響范圍）
分布式死鎖

服務(wù)器上某個(gè)對(duì)象的鎖，由本地鎖管理器持有，

  • 每當(dāng)有事務(wù)請(qǐng)求訪問(wèn)對(duì)象時(shí)，鎖管理器就對(duì)這個(gè)對(duì)象嘗試加鎖。如果加鎖失敗，那么需要等待前一個(gè)事務(wù)解鎖
  • 如果多個(gè)事務(wù)訪問(wèn)各個(gè)對(duì)象的加鎖次序不同（事務(wù) T T T 先訪問(wèn) a a a 后訪問(wèn) b b b，事務(wù) U U U 先訪問(wèn) b b b 后訪問(wèn) a a a），這可能會(huì)導(dǎo)致事務(wù)之間的循環(huán)依賴，導(dǎo)致死鎖
    • 單服務(wù)器死鎖：要么避免死鎖發(fā)生，要么檢測(cè)（鎖超時(shí)、等待圖）并解除死鎖
    • 分布式死鎖：多個(gè)服務(wù)器中的對(duì)象訪問(wèn)相互等待，在局部等待圖中可能無(wú)法發(fā)現(xiàn)環(huán)路，必須構(gòu)造出全局等待圖
鎖超時(shí)

思路：

  1. 每個(gè)鎖都設(shè)定時(shí)間期限。一旦超時(shí)，那么鎖就變成可剝奪的。
  2. 如果沒(méi)有事務(wù)在等待此對(duì)象，那么原本的事務(wù)依舊鎖住這個(gè)對(duì)象
  3. 如果有其他事務(wù)正在等待這個(gè)對(duì)象，那么這個(gè)對(duì)象被解鎖后交給等待事務(wù)，而被剝奪的事務(wù)將被放棄

問(wèn)題：

  • 沒(méi)有死鎖的系統(tǒng)，事務(wù)依舊可能因?yàn)殒i超時(shí)被剝奪，從而被放棄
  • 當(dāng)系統(tǒng)過(guò)載時(shí)，長(zhǎng)時(shí)間運(yùn)行的事務(wù)將被經(jīng)常性放棄
  • 恰當(dāng)?shù)某瑫r(shí)時(shí)間長(zhǎng)度難以確定
全局等待圖

對(duì)于服務(wù)器 X , Y , Z X,Y,Z X,Y,Z 上的對(duì)象 A ; B ; C , D A;B;C,D A;B;C,D，交錯(cuò)執(zhí)行的事務(wù) U , V , W U,V,W U,V,W 有如下等待關(guān)系：

在這里插入圖片描述

對(duì)應(yīng)的全局等待圖為：

在這里插入圖片描述

為了找到全局環(huán)，需要服務(wù)器之間進(jìn)行通信。

  • 集中式的死鎖檢測(cè)：
    1. 一個(gè)服務(wù)器擔(dān)任全局死鎖檢測(cè)器，收集、合并各個(gè)服務(wù)器上的局部等待圖
    2. 其他服務(wù)器不定期地發(fā)送局部等待圖給死鎖檢測(cè)器
    3. 死鎖檢測(cè)器一旦在全局等待圖中發(fā)現(xiàn)死鎖環(huán)，那么就決定放棄某一個(gè)事務(wù)，通知其他服務(wù)器
    4. 問(wèn)題：
      • 可用性差、缺乏容錯(cuò)、無(wú)伸縮性
      • 假死鎖：收集到的局部等待圖是老舊的，全局等待圖中有環(huán)，但是有些事務(wù)已經(jīng)放棄了某些鎖，實(shí)際上不存在死鎖
  • 分布式的死鎖檢測(cè)：可伸縮、可容錯(cuò)
邊追逐算法

不需要構(gòu)造全局等待圖，而是在服務(wù)器之間轉(zhuǎn)發(fā) probe（探詢）消息，

  1. 事務(wù)的協(xié)調(diào)者，記錄這個(gè)事務(wù)是活動(dòng)的還是在等待某個(gè)對(duì)象
  2. 事務(wù)的參與者的本地鎖服務(wù)器，通知協(xié)調(diào)者這個(gè)事務(wù)開(kāi)始或停止等待
  3. 當(dāng)某個(gè)事務(wù)被放棄時(shí)，它的協(xié)調(diào)者通知所有參與者放棄事務(wù)，并釋放相關(guān)的鎖
  4. 發(fā)送規(guī)則：當(dāng)事務(wù)依賴關(guān)系為 T 1 → T 2 T_1 \to T_2 T1?→T2?，并且 T 2 T_2 T2? 一直在等待其他事務(wù)，那么服務(wù)器發(fā)送 probe 消息

在這里插入圖片描述

邊追逐算法，

  • 算法啟動(dòng)：
    1. 當(dāng)服務(wù)器 A A A 發(fā)現(xiàn)事務(wù) T T T 等待事務(wù) U U U，并且被阻塞的 U U U 在等待服務(wù)器 B B B 上的對(duì)象，那么 A A A 發(fā)送一個(gè)形如 ( T → U ) (T \to U) (T→U) 的探詢消息給 B B B，啟動(dòng)一次死鎖檢查
    2. 實(shí)際上，服務(wù)器發(fā)送 probe 給協(xié)調(diào)者，由協(xié)調(diào)者轉(zhuǎn)發(fā) probe 給下一個(gè)服務(wù)器，共需要 2 2 2 個(gè)消息
    3. 如果事務(wù) U U U 和其他事務(wù) V V V 共享鎖，那么將探詢消息轉(zhuǎn)發(fā)給這些鎖的擁有者
  • 死鎖檢測(cè)：
    1. 當(dāng)服務(wù)器 B B B 收到了 ( T → U ) (T \to U) (T→U) 消息，檢查事務(wù) U U U 是否在等待其他事務(wù)
    2. 如果 U → V U \to V U→V，那么它就增加新邊，把形如 ( T → U → V ) (T \to U \to V) (T→U→V) 的探詢消息，繼續(xù)發(fā)送到 V V V 等待的服務(wù)器 C C C 上
    3. 每當(dāng)服務(wù)器在 probe 上增加一條新邊，檢查是否存在環(huán)路（對(duì)于 N N N 個(gè)事務(wù)組成的環(huán)路，需要 2 ( N ? 1 ) 2(N-1) 2(N?1) 個(gè)消息）
  • 死鎖解除：
    1. 當(dāng)檢測(cè)到環(huán)路，其中的某個(gè)事務(wù)將被放棄（可能多個(gè)服務(wù)器同時(shí)發(fā)現(xiàn)同一個(gè)死鎖環(huán)）
    2. 設(shè)定事務(wù)的優(yōu)先級(jí)，將環(huán)路中的最低優(yōu)先級(jí)的事務(wù)放棄（避免同時(shí)放棄多個(gè)事務(wù)）
    3. 向下傳遞：讓 probe 消息只能從高優(yōu)先級(jí)的事務(wù)傳遞到低優(yōu)先級(jí)的事務(wù)上（減少通信量）
事務(wù)放棄時(shí)的恢復(fù)

如果事務(wù)取消，那么服務(wù)器必須保證其他并發(fā)事務(wù)無(wú)法看到被取消事務(wù)的影響

  1. 臟數(shù)據(jù)讀?。╠irty read）：一個(gè)被放棄的事務(wù)對(duì)某個(gè)對(duì)象先執(zhí)行了寫操作，之后另一個(gè)被提交的事務(wù)對(duì)這個(gè)對(duì)象執(zhí)行了讀操作。

在這里插入圖片描述

如圖，事務(wù) U U U 讀取了事務(wù) T T T 未提交的臟數(shù)據(jù)，這個(gè)臟數(shù)據(jù)會(huì)影響 U U U 的執(zhí)行結(jié)果（比如發(fā)送 130 130 130 給客戶），而已經(jīng)提交的事務(wù)不能被取消（Undo）。

  1. 過(guò)早寫入（premature writes）：不同的事務(wù)對(duì)同一個(gè)對(duì)象執(zhí)行寫操作，其中一個(gè)寫操作被放棄。

在這里插入圖片描述

如圖，兩個(gè)事務(wù) U , T U,T U,T 同時(shí)對(duì)于對(duì)象 a a a 執(zhí)行寫操作，當(dāng) U U U 被提交后 T T T 再被放棄，對(duì)象 a a a 將被恢復(fù)為最初的狀態(tài)（前映像，before images），從而 U U U 提交的寫操作丟失。

  • 事務(wù)的串行等價(jià)的交錯(cuò)執(zhí)行
    • 對(duì)于同一對(duì)象的讀寫操作，就如同兩個(gè)事務(wù)串行執(zhí)行執(zhí)行一樣，但不要求提交或放棄
    • 只能保證兩個(gè)事務(wù)都提交時(shí)的隔離特性
  • 事務(wù)的嚴(yán)格執(zhí)行，
    • 對(duì)于一個(gè)對(duì)象的讀寫操作，都必須推遲到對(duì)同一對(duì)象執(zhí)行寫操作的其他事務(wù)提交或者放棄之后
    • 可以真正保證事務(wù)的隔離特性
服務(wù)器崩潰后的恢復(fù) 恢復(fù)文件

恢復(fù)管理器（Recovery Manager, RM）

  1. 對(duì)已提交事務(wù)，將對(duì)象保存在持久存儲(chǔ)中的恢復(fù)文件（日志、陰影版本）上
  2. 重新組織恢復(fù)文件，以提高恢復(fù)的性能
  3. 回收恢復(fù)文件中的存儲(chǔ)空間
  4. 處理介質(zhì)故障，需要在獨(dú)立磁盤上對(duì)恢復(fù)文件做一個(gè)拷貝
  5. 服務(wù)器崩潰后，服務(wù)器上對(duì)象的恢復(fù)
  6. 2PC 的恢復(fù)

恢復(fù)文件的組織結(jié)構(gòu)，

  • 對(duì)象：某個(gè)對(duì)象的數(shù)值
  • 事務(wù)狀態(tài)：
    • 事務(wù)標(biāo)識(shí) TID
    • 事務(wù)狀態(tài)（prepared, committed, aborted）
    • 其他用于 2PC 的狀態(tài)
  • 意圖列表：TID 以及一系列的意圖記錄
    • 對(duì)象標(biāo)識(shí) UID
    • 對(duì)象在恢復(fù)文件中的位置

意圖列表的作用，

  • 對(duì)應(yīng)每個(gè)事務(wù)，都記錄下它們修改的對(duì)象列表（值、引用）
  • 當(dāng)某個(gè)事務(wù)提交時(shí)，Server 根據(jù)意圖列表來(lái)確定受影響的對(duì)象，
    1. 將事務(wù)的臨時(shí)對(duì)象版本，替換為對(duì)象的提交版本
    2. 把對(duì)象的新值，寫入到服務(wù)器的恢復(fù)文件上
  • 當(dāng)某個(gè)事務(wù)放棄時(shí)，Server 刪除對(duì)應(yīng)的所有臨時(shí)對(duì)象版本
  • 在 2PC 中，一旦參與者進(jìn)入 prepared 狀態(tài)，那么它的 RM 必須把意圖列表、對(duì)象的臨時(shí)版本、事務(wù)狀態(tài)都寫入恢復(fù)文件
重組恢復(fù)文件
  1. 做檢查點(diǎn)的過(guò)程，是將下列信息寫到一個(gè)新的恢復(fù)文件
    • 當(dāng)前服務(wù)器上所有已提交的對(duì)象版本
    • 事務(wù)的狀態(tài)記錄和尚未完全提交事務(wù)的意圖列表
    • 還包括與 2PC 有關(guān)的信息
  2. 更換恢復(fù)文件的過(guò)程
    1. 在舊的恢復(fù)文件中增加一個(gè)標(biāo)記
    2. 進(jìn)行上述寫動(dòng)作到一個(gè)新的恢復(fù)文件，然后將那個(gè)標(biāo)記以后的項(xiàng)，拷貝到這個(gè)新的恢復(fù)文件
    3. 用新的恢復(fù)文件替換舊的恢復(fù)文件
  3. 檢查點(diǎn)的目的是，使得恢復(fù)更快和回收文件空間，要時(shí)不時(shí)做一下
日志

日志是恢復(fù)文件的一種具體形式，記錄了服務(wù)器上執(zhí)行的所有操作的歷史

  • 最近檢查點(diǎn)的快照 + 快照之后的事務(wù)操作歷史
  • 操作歷史：對(duì)象值、事務(wù)狀態(tài)、意圖列表
  • 日志中的次序，反映了各個(gè)事務(wù)進(jìn)入 prepared / committed / aborted 狀態(tài)的次序

每當(dāng)事務(wù)準(zhǔn)備好、提交、放棄時(shí)，Server 就調(diào)用自己的 RM，

  1. 當(dāng)某事務(wù) prepare，就讓 RM 把意圖列表中的對(duì)象，都 append 到日志中；同時(shí)，事務(wù)的 prepared 狀態(tài)以及它的意圖列表也被寫入
  2. 當(dāng)某事物 commit 或者 abort，就讓 RM 把對(duì)應(yīng)的 committed / aborted 狀態(tài)寫入日志
  3. 日志的寫操作（append），
    • 假定是原子的：如果 crash，那么只有最后一次的 append 可能是不完整的
    • 把多次寫緩沖起來(lái)，順序?qū)懕P比隨機(jī)寫盤快得多

在這里插入圖片描述

從Crash 中恢復(fù)

當(dāng)服務(wù)器進(jìn)程因崩潰而被替換后，新的進(jìn)程執(zhí)行：

  1. 首先將對(duì)象置為缺省的初始值，然后將控制轉(zhuǎn)給恢復(fù)管理器
  2. RM 的任務(wù)是恢復(fù)所有對(duì)象的值（使這些值反映所有已提交事務(wù)的效果，不包含任何未完成或放棄事務(wù)的效果）
    1. 通過(guò)逆向讀取日志文件來(lái)恢復(fù)對(duì)象值（如果從日志的開(kāi)始進(jìn)行恢復(fù)，通常要做更多的工作）
      • 使用具有 committed 狀態(tài)的事務(wù)來(lái)恢復(fù)對(duì)象的值
      • 這個(gè)過(guò)程一直進(jìn)行到所有的對(duì)象都被恢復(fù)
    2. 為了恢復(fù)已提交事務(wù)的更新，RM 從日志文件的意圖列表中找對(duì)象的值
    3. 恢復(fù)過(guò)程必須是冪等的
2PC 的恢復(fù)

恢復(fù)管理器會(huì)用到兩個(gè)事務(wù)狀態(tài)：“完成” 和 “不確定”

  • 參與者用 “不確定” 狀態(tài)，表示它的投票是 Yes，但尚未收到事務(wù)的提交決議
  • 協(xié)調(diào)者用 “已提交” 狀態(tài)，來(lái)標(biāo)記投票的結(jié)果是 Yes
  • 參與者用 “已提交” 狀態(tài)，表示已通知投票結(jié)果
  • 協(xié)調(diào)者用 “完成” 狀態(tài)，表示兩階段提交協(xié)議已經(jīng)完成

此外，恢復(fù)文件還要增加兩類信息

  1. 協(xié)調(diào)者：事務(wù)標(biāo)識(shí)，參與者列表
  2. 參與組合：事務(wù)標(biāo)識(shí)，協(xié)調(diào)者

在這里插入圖片描述

參與者：

  1. 在投票 Yes 之前，必須進(jìn)入 prepared 狀態(tài)，在恢復(fù)文件中添加 “準(zhǔn)備好” 狀態(tài)
  2. 在投票 Yes 時(shí)，在恢復(fù)文件中添加 “參與者” 記錄，并寫入 “不確定” 狀態(tài)
  3. 在投票 No 時(shí)，在恢復(fù)文件中寫入 “已放棄” 狀態(tài)

協(xié)調(diào)者：

  1. 第一階段準(zhǔn)備提交時(shí)，在恢復(fù)文件中添加 “協(xié)調(diào)者” 記錄
  2. 第二階段做出決定后，在恢復(fù)文件中添加 “已提交” 或者 “已放棄” 狀態(tài)（一次性強(qiáng)制寫入）
  3. 協(xié)調(diào)者收到所有的 ack 消息后，在恢復(fù)文件中寫入 “完成” 狀態(tài)

在恢復(fù)文件中最新的事務(wù)狀態(tài)信息決定了故障時(shí)的事務(wù)狀態(tài)，RM 需要根據(jù) Server 是協(xié)調(diào)者或參與者以及狀態(tài)的不同，進(jìn)行事務(wù)恢復(fù)。如圖所示：

在這里插入圖片描述

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

本文標(biāo)題：分布式系統(tǒng)（事務(wù)處理）-創(chuàng)新互聯(lián)
文章地址：http://bm7419.com/article14/cdidge.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供域名注冊(cè)、微信小程序、虛擬主機(jī)、網(wǎng)站制作、響應(yīng)式網(wǎng)站、網(wǎng)站內(nèi)鏈

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

成都做網(wǎng)站