歡迎回來!如果您錯過了第1部分, 您可以在這里查看。

由微軟亞洲研究院提出的 pacifica 算法是一種用于日志復制系統的分布式一致性算法。界定該公約的論文于2008年發表 (太平洋文件)。es 已正式聲明, 其復制模型基于該算法。

彈性搜索數據復制模型是基于原始備份模型的, 在微軟研究的太平洋論文中得到了很好的描述。該模型基于復制組中的單個副本, 該副本充當主分片。其他副本稱為副本分片。主索引作為所有索引操作的主要入口點。它負責驗證它們, 并確保它們是正確的。一旦索引操作被主操作接受, 主操作還負責將該操作復制到其他副本。

互聯網上提供該算法細節的文章很少, 因此, 本文簡要介紹了基于太平洋紙業的算法。該算法具有以下功能:

  1. 具有較強的一致性。
  2. 將單個主節點中的數據與多個輔助節點同步。
  3. 使用其他一致性組件進行配置維護。
  4. 即使有少數副本節點可用, 也支持寫入。

術語表

首先, 讓我們看一下此算法使用的一些術語:

  1. 副本組: 一個數據集, 其中的每個數據塊都是另一個數據的副本, 每個副本都是一個副本節點。”副本組中只有一個副本” 是 “主節點”; “其余為輔助節點。
  2. 配置: 副本組的配置描述了哪些副本包含在副本組中, 哪些副本是主要副本。
  3. 配置版本: 配置的版本號。每當發生配置更改時, 版本號都會增加1。
  4. 配置管理器: 這將管理全局配置組件, 從而確保配置數據的一致性。配置更改請求由 “副本” 節點啟動, 然后與版本一起發送到配置管理器。配置管理器驗證版本是否正確。否則, 更改請求將被拒絕。
  5. 查詢和更新: 有兩種類型的副本組操作: 查詢和更新。查詢不會更改數據, 而 “更新” 則會更改數據。
  6. 序列號 (sn): 這表示每個更新操作執行的順序。它為每個更新操作增加 1, 并且它是一個連續的數字。
  7. 準備列表: 這是更新操作的準備順序。
  8. 提交列表: 這是更新操作的提交序列。提交序列中的操作肯定會生效 (除非所有副本都崩潰)。在同一副本節點上, “已提交列表” 必須排在 “準備列表” 之前

2;顏色: rgb(34, 38, 53);保證金上衣: 20px;邊際底部: 5px;字體大小:25 px;清楚的: 兩者;字體樣式: 正常;字體-變種連字: 正常;字體變量帽: 正常;字母間距: 正常;孤兒: 2;文本對齊: 開始;文本縮進: 0px;文本轉換: 無;空白: 正常;寡婦: 2;字間距: 0px;-webkit-text-寬度: 0px;背景顏色: rgb(255, 255, 255);文本裝飾風格: 初始;文本裝飾顏色: 初始; “> 主要不變

利用 PacificA 算法, 需要一種誤差檢測機制來滿足以下不變。

當 “副本” 節點在任何時候都將自己視為 “主節點” 時, 配置管理器中維護的配置也將其視為當前的 “主” 節點。在任何時候, 只有一個副本節點認為自己是此副本組中的主節點。

主不變可以確保, 當一個節點本身視為主節點時, 它必須是當前的主節點。如果無法滿足主變量, 則可能會將查詢請求發送到舊主版, 這將導致讀取舊數據。

如何確保滿足主不變?根據本文的研究, 采用租賃機制可以實現這一點, 租賃機制是分布式系統中常用的方法。具體來說, 主節點定期獲得租約, 一旦成功獲得租約, 它就認為自己是設定時間段內唯一的主節點。如果期限到期后, 它未獲得新的租約, 則它將失去主狀態。只要每臺計算機中的 cpu 沒有明顯的時鐘偏差, 租賃機制的有效性就可以得到保證。

如本文所述, 租約機制使主節點向所有輔助節點發送檢測信號以獲取租約, 而不是讓所有節點從集中組件獲取租約。使用此分散模型可確保沒有集中式組件, 如果失敗, 將導致所有節點丟失其租約。

查詢

查詢過程相對簡單。查詢只能發送到主節點, 并且 “主節點” 返回基于最新提交的數據的相應值。由于此算法要求滿足主不變條件, 因此查詢始終讀取最新提交的數據。

更新

更新過程如下所示:

  1. 主節點將序列號 (sn) 分配給更新請求。
  2. 主節點將此更新請求添加到其自己的準備列表中。同時, 它將準備請求發送到所有輔助節點, 要求它們將此更新請求添加到其準備的列表中。
  3. 當所有副本節點完成準備時, 即當所有副本節點的準備列表包含更新請求時, 主節點開始提交請求, 將更新請求添加到已提交列表并應用更新
  • 結果將返回到客戶端, 并且更新操作成功。
  • 當 “主節點” 將下一個請求發送到 “輔助” 節點時, “主要” 的當前 “提交點” 將附加到該請求, 并且 “輔助” 節點將增加其提交點。

    我們可以從更新過程中推導出以下不變:

    承諾的不變

    我們將 “已提交的輔助節點列表” 標記為 “已提交的” 列表 “、” 已編制的列表 “(” 已編制 “列表) 和” 提交的一級節點列表 “(” 提交的 “一級委員會列表”)。名單必須在原始委員會列表之前, 而優先委員會列表必須在第二屆預案列表之前。

    重新配置: 二次故障、主故障、新添加的節點

    1. 二次故障

    當輔助節點失敗時, 主節點將重新配置請求發送到配置管理器, 從副本組中刪除失敗的節點。刪除 “副本” 節點后, 它將不再屬于 “副本組”, 并且不再向其發送請求。

    假定網絡故障發生在 “主節點” 和 “輔助” 節點之間。在這種情況下, 兩者仍然可以連接到配置管理器。此時, 主節點檢測到沒有來自 “輔助” 節點的響應, 同樣, “輔助” 節點也檢測到沒有來自 “主節點” 的響應。兩者都嘗試發送重新配置請求, 以便將另一個請求從副本組中刪除。此處應用的策略是 “第一次贏” 原則: 配置管理器收到的第一個請求生效, 并且發件人仍保留在副本組中;因為另一個節點不再屬于副本組, 所以它不能再更新配置。由于 “主節點” 請求 “輔助” 節點的租約, 因此 “輔助” 節點在租約有效時不會執行重新配置, 并且 “主” 節點的探測間隔必須小于租約探測間隔。在此情況下, 似乎傾向于主節點執行重新配置以刪除輔助節點。

    2. 主故障

    當 “主節點” 失敗時, “輔助” 節點將停止接收來自 “主節點” 的檢測信號。如果租約已過期, 輔助節點將發送重新配置請求, 以刪除主節點, 這也遵循 “贏首” 原則: 發送成功請求的輔助節點將成為新的主節點。

    輔助節點成為主節點后, 必須先經歷一個名為 “對帳” 的階段, 然后才能提供服務。由于上面提到的 “提交不變”, 前一個主節點的 “提交列表” 必須在新主節點的 “準備列表” 之前。這意味著, 當我們將新主節點的 “準備好的列表” 內容與當前副本組中的其他節點對齊 (這相當于在所有節點上重新提交此節點的未提交記錄) 時, 必須包括所有以前的 “提交” 記錄。這將導致下一個不變:

    • 重新配置不變:當新的主節點在 t 時間完成對帳時, t 時間之前的任何節點的 “提交列表” (包括原始主節點) 都優先于新主節點的當前 “提交列表”

    3. 新添加的節點

    新添加的節點必須首先成為輔助候選節點, 然后主節點開始向其發送 “準備請求”。同時, 此節點嘗試趕上以前未同步的記錄。一旦它趕上記錄, 它就會發送一個請求作為輔助節點, 之后主節點會向配置管理器發送配置更改請求, 以便將該節點添加到副本組。

    還有另一種情況: 一個節點位于副本組中, 并且由于臨時故障而被刪除, 現在需要重新添加到副本組。此時, 此節點上的 “提交列表” 中的數據必須已提交, 而 “已準備列表” 中的數據可能尚未提交。因此, 應刪除未提交的數據, 并從提交點的 “主起點” 開始請求數據。

    太平洋算法綜述

    PacificA 是一種具有很強一致性的算法, 既滿足讀又寫要求。它將數據一致性與配置一致性分開, 并使用其他一致性組件 (配置管理器) 來維護配置一致性。這樣, 當數據副本不到一半時, 仍然可以編寫新的數據, 并確保強有力的一致性。

    es 設計是指太平洋 a 算法。它通過 master 維護 index meta, 這類似于配置管理器的配置維護, 如本文所述。在索引 meta 中, InSyncAllocationIds 表示當前可用的碎片, 這類似于紙張中的副本組維護。接下來, 我們將在 es 中引入序列號和檢查點。這兩個類類似于太平洋 a 算法中的序列號和提交點。然后, 我們比較了 es 實現與太平洋的異同。

    序列號、檢查點和故障發現

    文中介紹了 es 所采用的一致性算法模型–太平洋 a。請務必注意, 每個太平洋更新操作都有相應的序列號, 指示執行順序。在以前版本的 es 中, 某些功能是有限的, 因為每個寫入操作都缺少序列號或類似的機制。2015年, es 官員開始計劃為每個寫入操作添加序列號, 并假定會有許多應用程序方案。

    更多詳情可在以下兩個鏈接中找到:

    • 添加序列號以編寫操作 #10708

    • 接下來, 我們簡要介紹了序列和檢查點的定義, 并討論了它們的應用場景。

      術語和序列號

      為每個寫入操作分配兩個值: 術語和序列號。每當主更改時, 術語都會增加 1, 這類似于太平洋 a 論文中的配置版本。每個操作后序列號增加 1, 這類似于太平洋紙中的序列號。

      因為讀取請求總是發送到主節點, 所以它分配術語和序列號。將同步請求發送到 “副本” 節點時, 將附加這兩個值。

      本地檢查點和全局檢查點

      本地檢查點指示此分片中的所有值小于此值的請求都已處理。

      全局檢查點指示所有副本節點上處理的值小于此值的所有請求都已處理。全局檢查點由主節點維護。每個副本節點將其本地檢查點報告到主節點, 然后主節點將根據該信息增加全局檢查點。

      global俄點是一個全局安全點, 指示 “副本” 節點已正確處理之前的所有請求, 并可用于在從節點故障中恢復后重新填充數據。全局檢查點也可用于 tranlog gc, 因為不再需要保存以前的操作記錄。但是, es 中的 tranlog gc 策略是基于大小或時間應用的, 而全局檢查點似乎沒有使用。

      快速故障恢復

      當副本節點出現故障時, es 會將其刪除。當故障超過特定時間段時, es 會將新的副本節點分配給新的節點。此時, 需要完全數據同步。但是, 如果以前失敗的副本節點返回, 只需在故障恢復后重新填充數據, 并在趕上記錄后將該節點重新添加, 就會導致快速恢復故障第一個條件可以通過保存 tranlog 特定的時間來滿足;第二個條件可以滿足使用檢查點, 最終實現快速故障恢復。這是使用序列號和檢查點的第一個重要應用程序方案。

      彈性搜索與太平洋 a 的比較

      相似 之 處

      1. 元一致性和數據一致性是單獨處理的: 在 PacificA 中, 配置一致性是通過配置管理器來維護的;在 es 中, 元一致性是通過 master 保持的。
      2. 同步維護副本集合: 在太平洋, 將維護副本組; 在太平洋, “復制” 組保持 “在 es 中, 保持同步分配器。
      3. 序列號: 在 pacica 和 es 中, 寫入操作都使用序列號來記錄操作順序。

      差異

      主要區別在于 es 符合太平洋 a;但其實現仍未滿足算法的所有要求, 意味著嚴格的強一致性不能保證。要點如下:

      1. 元一致性: 我們在上一節中分析了 es 中的元一致性問題, 我們可以看到 es 不能保證元一致性, 因此它肯定不能嚴格保證數據一致性。
      2. 準備階段: PacificA 具有準備階段, 可確保在所有節點上成功準備數據并確保未丟失提交的數據之前不會提交數據。在 es 中, 數據是直接寫入的, 因為它缺少此階段。
      3. 讀取一致性: 在 es 中, 可以讀取所有不同步副本節點, 從而提高數據可讀性;但是, 也可以讀取舊數據。另一方面, 即使只可以讀取主節點, es 也需要類似租約的機制, 這樣舊主節點也不會被讀取。考慮到 es 是一個近乎實時的系統, 對讀取一致性的要求可能不是很嚴格。

      引用
      1. 索引 api彈性搜索參考6。2
      2. 閱讀和編寫文檔彈性搜索參考6。2
      3. 基于日志的分布式存儲系統中的復制
      4. 添加序列號以編寫操作 #10708
      5. 序列 id: 即將進入您附近的彈性搜索群集
    Comments are closed.