數據複製 - 高可用及讀操作高併發

MySQL - 主從複製

• 實現讀寫分離

• 寫入主服務器

• 由從服務器中讀取

• 主服務器

• 用戶寫的操作發至主服務器

• 主服務器更新數據庫

• 主服務器將寫操作寫入 Bin Log 日誌中

• 從服務器

• Log 獲取線程取得主服務器中的日誌內容

• Log 獲取線程將日誌內容寫入從服務器的 Relay Log 日誌中

• SQL 執行線程負責將 Relay Log 日誌中寫的操作更新至從服務器數據庫

• 用戶一次寫的命令在主、從服務器中各更新一次，共兩次

• 主、從服務器的數據完全一致

MySQL - 一主多從

• 寫入至主服務器中

• 主服務器的 Bin Log 同步至多個從服務器的 Relay Log 中

• 應用服務器可以選擇任一個從服務器進行讀取

• 因為所有的數據庫均完全一致

• 優點

• 分攤負載

• 讀寫分離

• 專機專用

• 每一台從服務器可以專門服務某一類的應用

• 應用服務器使用一台

• 數據分析服務器使用一台

• 進行複雜的 SQL 操作

• 數據備份服務器使用一台

• 便於冷備

• 可以決定甚麼時候停止數據的複製

• 然後進行備份

• 並將備份遷移至光盤、磁帶中

• 不影響應用服務器的正常操作

• 高可用

• 部分高可用

• 讀操作的高可用

• 寫操作的高可用不能做到

• 主服務器當機無法寫

• 也無法寫入從服務器中然後複製到主服務器中

MySQL - 主主複製

• 實現寫操作的高可用

• 主服務器 A 與主服務器 B 的 Bin Log、Relay Log 會相互同步

• 任何一個主服務器的數據變更，都會同步到另外一台主服務器

• 主主複製也可以搭配主從複製

• 各主服務器有自己的主從服務器集群

• 主主失效恢復

• 當主服務器 A 失效

• 寫操作遷移至主服務器 B

• 讀操作遷移至 主服務器 B 的從服務器集群

• 失效維護過程

• 所有主服務器都正常時

• 選擇一個主服務器集群服務讀寫操作

• 當服務寫操作的主服務器失效時

• 讀寫均遷移至另一個主服務器集群

• 重建失效的主服務器集群

• 重複整個過程

MySQL 複製注意事項

• 主主複製的兩個數據庫不能併發寫入

• 不是技術上有問題

• 很多時候會產生邏輯上問題

• 在 A、B 上同時更新同一條紀錄

• 同步後會產生數據衝突

• 數據會不一致

• 避免數據衝突，所以主主不能同時提供寫操作服務

• 複製僅增加讀並法的處理能力，沒有增加寫併發能力和存儲能力

• 主主增加寫的高可用

• 更新表結構會導致巨大延遲

• 如 ALTER TABLE、CREATE TABLE

• 也是寫操作，所以會同步至 Relay Log 中

• 會進行遠程、同步的表結構更新

• 會導致巨大的延遲

• 其他的同步會被擱置

• 實際處理表結構更新

• 會關閉表結構同步操作

• 運維工程師選擇適當時間，同時修改兩個數據的表結構

• 以人工操作取代自動複製

數據分片 - 寫高併發及存儲能力

• 增加寫入的高併發及存儲能力

• 將數據依據某種條件分片至不同的數據庫服務器

• 寫操作也會分配至不同的數據庫服務器 - 高併發

• 各數據庫存儲不一樣的資料，所以也增加存儲能力

• 方式

• 硬編碼

• 由應用程式代碼中硬編碼，決定該寫入哪一台服務器

• 缺點

• 對應用程序影響比較大

• 加入決定分片的邏輯判斷

• 整個集群管理比較麻煩

• 增加/減少服務器須改代碼

• 映射表外部存儲

• 將映對關係存入外部存儲中

• 使用時查表決定向哪一個服務器請求

• 比硬編碼靈活

• 編程、維護

• 數據分片的挑戰

• 需要大量額外代碼，處理邏輯變得複雜

• 無法執行多分片的聯合查詢

• 無法使用數據庫的事務

• 無法通過日誌實現事務的同時提交和回滾

• 不同服務器有不同的日誌

• 隨著數據增長，如何增加更多的服務器

• 需更改代碼或映射表

• 數據如何遷移至新服務器

分布式數據庫中間件

中間件

• 將數據分片的邏輯單獨取出

• 與應用程序完全隔離

• 中間件偽裝成一個數據庫

• 中間件內部進行數據分片

• 可連接多個數據庫服務器

• 依據設定檔的設定，依據特定欄位進行分片

• 由應用程序角度，中間件是一個普通的數據庫服務器

• 中間件進行分片邏輯的轉換，將請求分發給不同的服務器

中間件 Cobar 架構

• 數據庫返回的結果在 Cobar 內進行聚合後，再返回給應用程序

• Cobar 系統組件模型

• 前端通訊模塊

• 模擬關係數據庫的通訊協議

• SQL解析模塊

• 解析出設定檔中的分片條件及其值

• SQL路由模塊

• 決定提交SQL到哪個服務器

• SQL執行代理模塊

• 真正提交SQL到服務器

• 結果合併模塊

• 將各分片返回的數據集進行合併

• 產生最終的結果集返回給應用程序

如何做集群的伸縮

• 擴容一定會關係到數據的遷移

• 配置路由表時通常會預測未來的數據量，再決定對哪個數取模

• 非現在有 A 台，就對 A 取模

• 會取一個比較大的值

• 然後配置比較多的路由

• 將來擴容僅需改變對映的路由 IP

• 程序

• 建立新的服務器

• 設定主從複製，同步應遷移的數據

• 主為原服務器

• 從為新服務器

• 待數據遷移完成，修改路由配置

• 中間件根據新的配置表進行分片

數據庫的部署方案

• 單一服務與單一數據庫

• 主從複製實現伸縮

• 一主多從

• 讀寫分離

• 兩個 Web 服務集兩個數據庫

• 業務分庫

• 在互聯網演化過程中，必然要經歷的一個階段

• 對應用服務進行拆分

• 各服務擁有自己的數據庫集群

• 綜合部署

• 業務分庫後進行分片

• 根據業務的數據量及寫操作併發量決定分片與否

CAP原理與 NoSQL 數據庫架構

CAP 原理

• 討論分布式系統在 "一致性"(C)，"可用性"(A)，及"分區耐受性"(P)之間的關係

CAP

• 一致性 (Consistency)

• 每次讀取的數據都是最新的數據，或者返回一個錯誤

• Every read receives the most recent write or an error

• 不是過期的數據，數據是跟現實最新的是一致的

• 可用性 (Availability)

• 每次請求都應該得到一個響應，而不是返回一個錯誤或失去響應

• Every request receives a (non-error) response, without the guarantee that it contains the most recent write

• 系統需要一直可以正常使用，不會引起調用異常

• 但是不保證響應的數據是最新的 (不需要一致)

• 分區耐受性 (Partition tolerance)

• 即使因為網路原因，部分服務器節點之間消息丟失或延遲，系統應該是可以操作的

• The system continues to operate despite an arbitrary number of message being dropped (or delayed) by the network between nodes

原理

• 分布式系統在必須要滿足分區耐受性的前提下，一致性和可用性無法同時滿足

• 一致性和可用性必須二選一

• 網路失效一定會發生，所以必須保證分區耐受性

• 選擇一致性

• 系統返回一個錯誤碼或乾脆超時

• 系統不可用

• 選擇可用性

• 系統總是返回一個數據，但不能保證數據是最新的

• 系統不一致

• 須根據業務特性去選擇一致性或可用性

• 如付款業務 - 須保證一致性

• 如商品展示 - 可選擇可用性

解決方案 - 最終一致性

• 在保證可用性的狀態下，降低數據不一致性對用戶的影響

• 容許數據在一段時間內不一致

• 但在網路失效恢復之後，數據同步完成時，數據會回復最終一致性



• 服務器 1、2 網路失效

• 客戶端 A、B可以正常操作

• 客戶端 C 會得到舊數據

• 網路正常後，服務器 1 會將變更同步致服務器 2

• 達成數據最終一致性

達到最終一致性的策略

• 最終一致寫衝突

• 根據數據時間戳，最後寫入覆蓋

• 時間戳新的覆蓋時間戳舊的

• 不考慮最新的時間戳是不是就是對的數據

• 僅保證數據最終是一致的

• 由客戶端解決衝突

• 客戶端 1、2 都保有用戶 123 不同購物車數據

• 其他客戶端會讀取到這兩個不同購物車數據

• 由客戶端程序決定是否要合併數據

• 使用這種方法，通常是屬於客戶端邏輯的數據

• 投票解決衝突 (Cassandra，NoSQL數據庫)

• 對需要寫入的數據，寫入多個節點

• 大多數的節點寫入成功，就認為是成功寫入

• 對需要讀取的數據，讀取多個節點的數據

• 若數據不一致，則投票決定要用哪一組數據

NoSQL

• 原生支持數據存儲的分布式特性

• 伸縮性更好，更便於實現分布式

• 犧牲對關係數據庫一些特性的支持

• 不支持SQL

• 不只是SQL數據庫 (Not Only)

• 關係式數據庫的另一種替代品

Cassandra 分布式架構

• 客戶端可以連接到任一節點

• 寫入資料時，由節點計算要將數據寫到哪幾台其他的節點

• 大多數節點寫入成功，即返回寫成功給客戶端

• 讀取資料時，由節點計算要從哪幾台節點讀取資料

• 若讀取到的資料不一致，由節點依投票結果，將最終數據返回給客戶端

• 在節點中的數據可能不一致，只是返回給客戶端是一致的

HBase 架構

• 底層存儲使用 Hadoop 分布式文件系統 (HDFS)

• 數據的複製及文件系統的高可用由 HDFS 保證

• HBase 解決數據的分布式存儲、路由的選擇及一致性

• 通常存儲 Key - Value 結構數據

角色

• HMaster

• 數據分片

• 路由選擇

• 需有多個HMaster，但僅有一個 HMaster對外服務

• HRegionServer

• 真正的服務器實例

• 讀取、寫入數據

• 伸縮時，僅需要增加 HRegionServer

• 不會發生數據遷移

• 因為 HRegionServer不存儲數據

• 數據由 HDFS 管理

• Zookeeper

• 由多個HMaster中，選擇主 HMaster

• 應用程序

• 由Zookeeper處取得主 HMaster

• 利用數據中的 Key，由主HMaster 得到需存入哪一個 HRegionSever

• 將數據寫入HRegionServer中

• HRegionServer會決定數據寫入哪一個 HRegion中

存儲方式 - Log Structed Merge Tree ( LSM 樹)

• 相對應與關係數據庫的 B+ 樹

• B+ Tree 隨機進行讀寫操作

• 以 Log 結構順序地進行寫入

• 小樹先存於內存中

• 當寫入硬盤時，merge進一棵大樹

數據庫的事務(transaction)處理特性

關係數據庫 (ACID)

• 原子性 (Atomicity)

• 事務要麼全部完成，要麼全部取消

• 事務的多個操作不能部分完成

• 事務崩潰，數據庫狀態要回到事務之前 (事務回滾)

• 隔離性 (Isolation)

• 事務 T1 與 T2 同時運行，最終的結果是相同的

• 不管哪一個先結束

• T1、T2 不互相影響

• 主要靠鎖來達成

• 持久性 (Durability)

• 一但事務提交完成，不管系統崩潰或出錯，數據要保存於數據庫中

• 一致性 (Consistency)

• 只有合法的數據才能寫入數據庫中

• 合法數據 - 依照關係約束和函數約束

NoSQL 數據庫 (BASE)

• 基本可用 (Basically Available)

• 系統出現不可預知故障時，損失一部分可用性

• 基本可用，大部分的功能可用

• 軟狀態 (Soft state，弱狀態)

• 允許數據存在中間狀態

• 中間狀態不影響整體系統可用性

• 數據副本間的同步存在一些延時

• 數據存在某種存儲狀態的不一致

• 最終一致性 (Eventually consistent)

• 所有數據副本在經過一段時間後，最終達成一個一致的狀態

• 不須實時的保證系統的強一致

Zookeeper與分布式一致性架構

分布式一致性問題

• 分布式系統腦裂

• 在分布式系統中，不同的服務器獲得相互衝突的數據或指令，導致整個集群陷入混亂，數據損壞

• 例如多台數據服務器同時運作，但不同用戶對不同服務器提交相衝突的寫的操作，造成整個系統數據不一致

• 所以數據庫中雖然配置兩主數據庫可以同步(主主複製)，解決高可用問題，但同一時間只能有一個主服務器來服務寫的操作

• 相同的情況出現在 NoSQL HBase 的 多個 HMaster 服務器中，多台 HMaster 僅能有一台HMaster服務器對外服務

• 若主節點 A 及 B 均對外服務

• 則當一條相衝突的寫操作分別提交給 A 和 B

• 則會造成整個系統數據不一致

• 此時需決定哪一個當成主服務器，哪一個當成備用主服務器就成為分布系統主要的問題

• 用戶向主服務器 (A) 提交服務請求

• 若主服務器 (A) 失效，則需切換至備用主服務器 (B)

• 此時備用主服務器 (B) 變成 對外服務的主服務器

• 當原主服務器 (A) 修復，則變成備用主服務器

• 但切換時用戶怎麼知道?

• 利用 Zookeeper 服務來提供當前運作的主服務器

• 但Zookeeper 自己本身仍然要維護高可用

• 需多台服務器形成集群

• 那zookerper又如何確保自身的分布式一致性呢?

分布式系統一致性難題

• 分布式系統須為高可用

• 高可用就必須部署多台服務器

• 多台服務器會造成分布式系統腦裂

• 所以必須決定一台當前活動的服務器

• 所以引入另外一台服務器來決定

• 但決定哪一台為當前服務器的服務器本身也必須高可用

• 整個問題又開始循環

• 所以如何在多台服務器中保持數據一致的狀態就成為難題

分布式一致性算法

• 都有一個投票的過程，決定最終一致的資料狀態

• 在整個集群中式統一的

• 如在整個系統中，選出一個當前的主服務器對外服務

• 算法協議必須保證本身的高可用，又能保證系統的狀態是一致性

Paxos 協議

• 角色

• Proposer: 提交投票請求

• Acceptor: 相互投票決定

• Learner: 投票結果的接受者

• 由learner對外提供投票的結果

• 通常任一台服務器都存在這三個角色

• 所以任一台服務器失效，不影響整個服務

• 保證高可用

• 算法過程

• 第一階段: Prepare

• Proposer 向 Acceptors 發出 Prepare 請求

• Acceptors針對收到的 Prepare 返回 Promis 承諾

• 若此時有其他 Proposer 發出 Prepare 請求則會排序等待

• 第二階對: Accept

• Proposer收到多數的 Acceptors 的承諾

• Proposer 發出 Propose請求

• 不會有兩個 Propose 請求進行投票

• 因為在第一階段就會被排入排序等待中

• Acceptors 針對收到的 請求進行 Accept 處理

• 決定是否要接受或駁回

• 第三階段: Learn

• Proposer 收到多數的 Acceptors的 Accept

• 標誌本次 Accept 成功，決議形成

• Proposer 將決議發送給所有的 Learner

• 注意事項

• Proposer 生成全局唯一且遞增的 Proposal ID (可使用時間戳加 Server ID)，向所有 Acceptors 發送 Prepare 請求

• Prepare 請求不需攜帶提案內容

• 攜帶 Proposal ID 即可

• Aceeptor 收到 Prepare 和 Propose 請求後

• 不再接受 Proposal ID 小於等於當前請求的 Prepare 請求

• 不再接受 Proposal ID 小於當前請求的 Propose 請求

• 保證對每一個 Propose 請求都順序處理

• 不會有同時兩個 Propose進行投票

Zab 協議

• 簡化 Paxos 協議

• 依然經由投票來決定狀態的一致性

• 角色

• Leader :

• 接受 Request 請求

• 提出 Propose 投票請求

• 決定一致性狀態

• Follower :

• 轉發 Request 給 Leader

• 對 Propose 投票

• 存儲一致性的狀態

• 算法過程



• 多台 Follower 對外服務

Zookeeper

架構



• 使用 Zab 協議

數據結構



• 以樹狀結構紀錄數據

• leaf file 紀錄數據的值

• 如 stupidname、morestupidity、read-1 等

應用

• 配置管理



• 系統配置需要

• 配置的值一致

• 不能拿不到 - 高可用

• getData(path, watch)

• watch == ture: path內的值有變更時，zookeeper 會主動通知

• 選舉 Master



• 選舉當前主服務器

• 當主服務器失效時，重新選舉主服務器

• create(...) 提交Request

• EPHEMERAL

• create 的 path 是臨時的

• 服務器與 zookeeper 的heart beat 中斷時，此 path 會被刪除

• getData(..., true) 由zookeeper監控 path 存不存在並主動通知

• 集群管理 - 負載均衡與失效轉移



• 新增或刪除解點，monitoring process 會接到通知

• 更新負載均衡列表

• 每一個服務器啟動時，自己去節點下create 一個 ephemeral node

性能



• 橫軸為讀寫比例

• 0 表示: 100 %寫，0% 讀

• 100 表示: 0%寫，100%讀

• 縱軸為每秒處理request的能力

• 讀的性能比寫的性能好

• 讀時有多台服務器 (Follower) 提供資料，故能快速返回

• 寫時需進行投票，執行 Propose、ACK、Commit操作

• 而且不能並行，需有順序性

• 服務器越多

• 讀的性能越好

• 因為提供資料的服務器變多了

• 寫的性能越差

• 更多的服務器要參與投票

搜索引擎的基本架構

互聯網搜索引擎整體架構

互聯網搜索引擎

• 通過一個搜索引擎，快速檢索整個互聯網所有的頁面內容

• 爬蟲

• 收錄萬億級頁面內容

• 存儲在搜索引擎內部

• 搜索

• 在萬億級頁面裡面搜索想要的數據內容

整體架構



• 爬蟲、去重複、存入系統中

• 系統建構一個倒排索引

• 系統對頁面內容進行排序

• 利用 PageRank進行排序

• 對內容計算權重

• 當使用者查詢時

• 對檢索詞進行分析，產生搜索詞列表

• 利用倒排索引及PageRank進行排序後，返回給使用者

爬蟲系統架構



• 網頁下載

• 從種子URL或待下載URL對列中獲取URL

• 透過HTTP請求，獲取頁面內容

• 下載後儲存

• URL 紀錄於已下載URL集合中

• 解析頁面超鏈結

• 下載的網頁進行鏈結解析

• 若不在已下載URL集合中，存入待下載URL對列中

• 由種子URL 開始，可以爬到全網的頁面內容

• 因為互聯網是互聯的

• 所有的頁面總有一個鏈結指向它

• 透過爬蟲禁爬協議，可以避免頁面被爬

• 例如有些需付費才能看的頁面

• 此為大家共同的協議

文檔矩陣與倒排索引

• 索引

• 正排索引

• 文檔內包含哪些單詞

• 文檔對應的單詞有哪些

• 倒排索引

• 那些文檔包含了這個單詞

• 單詞對應的文檔有哪些



• 分析單詞分布在那些文檔

• 儲存

• 只存文檔列表

• 若搜尋 "後端" 和 "技術" 兩個詞，則可以由文檔列表取交集而得

• 如 2、4 檔

• 文檔越多、內容越多、詞越多，倒排索引的性能優勢越明顯

• 帶詞頻列表

• 單詞在文檔出現的次數越多，代表單詞對這個文檔越重要

• 可利用詞頻來輔助排序

• 帶詞頻與位置

• 可處理兩個單詞並須相鄰的這種查詢

Lucene 架構

應用系統的搜索引擎

• 優化數據的訪問

• 優化數據的存儲

架構



• Analysis

• 分詞

• Index

• 倒排索引

• QueryParser

• 利用分詞後的結果產生查詢

• Search

• 搜尋倒排索引

• similarity

• 依據結果進行排序、合併

倒排索引



索引準實時更新

• 新增、刪除文件會影響到排索引內容

• 索引更新若全量創建新索引

• 效率低

• 成本高

• 性能差

• Lucene 引入段的概念

• 將索引文件拆分成子文件

• 子文件即為段

• 段是一個可獨立搜索的數據集

• 每個段都會被搜索

• 最後合併所有段的搜索結果

• 索引更新針對段進行操作

• 索引更新

• 新增

• 新建一個段來存儲新增的數據

• 原來的段不變

• 刪除

• 在索引文件新增一個 .del 文件

• 存儲被刪除的數據ID

• 被刪除的數據可以被查到，但進行文檔鏈表合併時，被過濾掉

• 更新

• 先刪除，後新增

• 為控制索引裡段的數量，需定期進行段合併操作

• 數量太多，影響搜索效率

• 真正移除被刪除的檔

• 合併小的段

Lucene 不支持分布式集群

• 只能用一台服務器構建索引

• 當數據量大時，一台服務器不夠

• 不能高可用

ElasticSearch

• 在分布式系統中構建搜索引擎，主要使用ElasticSearch

• 包裝 Lucene 成一個分布式集群

• 引入索引分片，實現分布式

• 引入索引備份，實現高可用

• API 更簡單、更高級

架構



• 八個分片存儲在四台服務器

• 每個分片均有備份在其他台服務器

ES 分片預分配與集群擴容



• 須預先決定要分片的個數，決定後不能改變

• 與分布式數據中間件一樣，必須預規劃將來會擴容到多少台服務器



• 當僅有 Node1 時 ，所有分片均存於 Node1

• 當需擴容時，選取一個分片遷移至 Node2

• 擴容時必須以分片為單位

• 若有 Node3，無法再拆分片數據遷移至 Node3

實際有些應用上，會用 ElasticSearch 取代 NoSQL

• 把 ElashticSearch 當成存儲使用

• 可自己分片

• 可快速集群伸縮

• 提供更壞素的搜索、查詢服務

• API 接口更加便利