NoSQL數據庫原理-第二章-NoSQL數據庫的基本原理課件

1、NoSQL數據庫原理第2章 NoSQL數據庫的基本原理2.1.1 關系模型（1）實體（Entity）：是指現(xiàn)實世界中的具體或抽象的事物。例如：一個學生、一個教師、一門課程等。（2）屬性（Attribute）：對實體的特性進行描述，例如學生的學號、班級、姓名等。屬性一般要求具有原子性，即不可再分割。屬性具有值域和數據類型兩種特性。（3）實體標識符：能夠唯一標識一個實體的屬性稱為實體標識符，例如學生的學號，即數據庫實現(xiàn)中的鍵（key）的概念。（4）聯(lián)系（Relation）：實體之間的關系，以及實體內部屬性之間的關系。第2章 NoSQL數據庫的基本原理2.1 關系型數據庫的重要機制回顧2.1.1 關

2、系模型關系模型中的常見特征關系模型中具有明確的表結構列具有原子性，不可再分割列的值域和類型時固定的如果某字段出現(xiàn)空值，一般會保留存儲空間(NULL)，以便今后插入數值NoSQL可能打破這些特征NoSQL中可能沒有明確的結構列可能是復合型的列中的內容和類型可能是隨意的、無定義的不會為空值流出存儲空間，可能很難直接插入數值第2章 NoSQL數據庫的基本原理2.1 關系型數據庫的重要機制回顧2.1.2 關系型數據庫的完整性約束關系模型中的完整性約束域完整性：是指對列的值域、類型等進行約束。實體完整性：實體集中的每個實體都具有唯一性標識，或者說數據表中的每個元組是可區(qū)分的。這意味著數據表中存在不能為空

3、的主屬性（即主鍵）。參照完整性：表明表1中的一列A依賴于表2中被參照列的情況。用戶定義的完整性：用戶根據業(yè)務邏輯定義的完整性約束。NoSQL中的完整性約束域完整性一般較弱，或不支持可能存在主鍵相同的行，或內容相同但時間戳不同的行等情況，一般不會出現(xiàn)空的主屬性一般不提供參照完整性，或者外鍵，因此一般也不支持跨表的關聯(lián)查詢（Join）用戶定義完整性靠應用程序支持第2章 NoSQL數據庫的基本原理2.1 關系型數據庫的重要機制回顧2.1.3 關系型數據庫的事務機制事務是關系型數據庫最重要的機制之一關系型數據庫會對并發(fā)操作進行控制，防止用戶在存取數據時破壞數據的完整性，造成數據錯誤。事務機制可以保障用

4、戶定義的一組操作序列作為一個不可分割的整體提交執(zhí)行，這一組操作要么都執(zhí)行，要么都不執(zhí)行，當事務執(zhí)行成功，我們認為事務被整體“提交”，則所有數據改變均被持久化保存，而當事務在執(zhí)行中發(fā)生錯誤時，事務會進行“回滾”，返回到事務尚未開始執(zhí)行的狀態(tài)。ACID：原子性（Atomicity）、一致性（Consistency）、隔離性（Isolation）、持久性（Durability）。ACID是典型的強一致性要求ACID是大多數NoSQL拋棄的機制，因為無法在分布式環(huán)境中保證效率第2章 NoSQL數據庫的基本原理2.1 關系型數據庫的重要機制回顧2.1.3 關系型數據庫的事務機制并發(fā)控制和封鎖機制并發(fā)調度

5、指將多個事務串行化，并發(fā)控制則強調解決共享資源并發(fā)存取過程中產生的各類問題丟失更新、幻讀、臟讀封鎖是數據庫中所采用的常見并發(fā)控制。封鎖是一種軟件機制，使得當某個事務訪問某數據對象時，其他事務不能對該數據進行特定的訪問。共享鎖、排它鎖死鎖和預防死鎖順序加鎖、超時法、等待圖法分布式環(huán)境下實現(xiàn)事務和鎖，可能出現(xiàn)什么問題？第2章 NoSQL數據庫的基本原理2.1 關系型數據庫的重要機制回顧2.1.4 關系型數據庫的分布式部署關系型數據庫一般部署在單機上，并通過垂直擴展（scale up）方式提升性能一些關系型數據庫也可以實現(xiàn)水平擴展，一般需要通過外部軟件、或用戶編程等方式實現(xiàn)。（1）將不同的表存儲在不

6、同節(jié)點。如果某個表體積過大、或頻繁被訪問，則其他節(jié)點無法提供幫助。（2）水平分割數據，將表中不同的行存儲在不同節(jié)點上。在RDBMS中需要保持數據的完整性，插入數據時需要檢查所有節(jié)點上的數據。索引、鎖等機制的維護也較為繁瑣。（3）垂直分割數據，將表中不同的列存儲在不同節(jié)點上。在大數據場景下，表中的行數可能仍然過多，熱點數據可能無法做到負載均衡。也可能遇到和水平分割數據類似的問題。分布式環(huán)境下，數據存儲存儲在不同節(jié)點，此時必須通過網絡傳遞相關消息，如果出現(xiàn)網絡故障或部分節(jié)點失效，則有可能導致整個系統(tǒng)變得低效或死鎖，因此在分布式環(huán)境下實現(xiàn)高效率的事務機制、以及強一致性等特性較為困難。關系型數據庫目前

7、也存在多種橫向擴展方案橫向擴展可以提供負載均衡能力，例如：將數據進行垂直節(jié)分或水平切分。橫向擴展可以提供一定的容錯能力，例如：采用讀寫分離機制。靈活運用上述方案，可以在很多應用場景中解決問題，但是當數據量持續(xù)增大時，則可能無法應對。運用上述方案時，用戶可能仍需要進行較多的第2章 NoSQL數據庫的基本原理2.1 關系型數據庫的重要機制回顧2.1.4 關系型數據庫的分布式部署主從集群（讀寫分離）無法解決寫數據的瓶頸，但保持了對單機事務的支持讀數據時，可以實現(xiàn)一定的負載均衡，提高并發(fā)性能，并且可以提供一定的容錯機制一般來說從服務之間是不共享數據的，每臺從服務器都保存全集數據，一般不會進行數據分割主

8、從服務器之間可能存在數據不一致的隱患第2章 NoSQL數據庫的基本原理2.1 關系型數據庫的重要機制回顧利用分發(fā)服務器實現(xiàn)主從數據同步例如：Microsoft SQL Server提供了“Database Mirroring”、“l(fā)og shipping”、發(fā)布訂閱、“always on”等多種讀寫分離策略第2章 NoSQL數據庫的基本原理2.1 關系型數據庫的重要機制回顧分布式中間件實現(xiàn)關系型數據庫的分布式2.1.4 關系型數據庫的分布式部署分布式中間件例如：MySQL Fabric、MySQL Cluster、阿里的Cobar(疑似已停止更新)一般可以實現(xiàn)數據水平拆分、容錯、數據路由等功能

9、，中間件實現(xiàn)難度較大，中間件實際上承擔了NoSQL數據庫的大部分功能，關系型數據庫只用來實現(xiàn)數據分片的存儲，用戶配置、使用均較為復雜系統(tǒng)功能受到一定限制（和單機部署的RDBMS相比）2.1.4 關系型數據庫的分布式部署MySQL Fabric方案MySQL官方方案支持水平分片（Shard x）支持主從數據庫（Primary/Secondary）第2章 NoSQL數據庫的基本原理2.1 關系型數據庫的重要機制回顧MySQL Fabric的架構圖2.1.4 關系型數據庫的分布式部署MySQL Cluster方案數據保存在“NDB Cluster”，并盡量將數據寫入內存表結構保存在“MySQL Se

10、rver”應用程序通過“MySQL Server”訪問數據表管理客戶端通過管理工具(ndb_mgmd)管理“NDB存儲服務器”。管理配置較為復雜，功能受到一定限制第2章 NoSQL數據庫的基本原理2.1 關系型數據庫的重要機制回顧MySQL ClusterNoSQL中的數據：結構復雜、數據量大NoSQL一般采用分布式部署，為保證效率、可靠性等，一方面弱化RDBMS中的部分特性，另一方面哈需要接入分布式部署中遇到的各種難題：數據均勻、分布式存儲，統(tǒng)一使用、管理數據系統(tǒng)可伸縮（橫向增加節(jié)點或替換故障節(jié)點）存儲和查詢任務的容錯性錄入、查詢數據時的高性能提高系統(tǒng)的易用性第2章 NoSQL數據庫的基本原

11、理2.2 分布式數據管理的特點假設某個NoSQL數據庫將數據均勻存儲在n個節(jié)點上，此時可能出現(xiàn)各種難題或故障：如何查看整個集群還有多少存儲空間？如何在整個集群不停止工作下，快速、方便的增加節(jié)點？或者如何盡量減少增加、刪除節(jié)點所需的時間和工作量？某個節(jié)點出現(xiàn)硬盤故障，如何保證數據不缺失？執(zhí)行查詢任務時，某個節(jié)點沒有回應，如何保證查詢結果沒有缺失？2.2.1 數據分片目的使數據均勻分布到多個節(jié)點上，執(zhí)行查詢或處理任務時，各個節(jié)點只查詢自身數據，實現(xiàn)并行處理跨表聯(lián)合查詢性能？由于需要在多個節(jié)點之間計算笛卡兒積，因此性能很差，大部分NoSQL并不支持。當運行分布式查詢或處理任務時，可以每次處理一個分片

12、，將一個分片一次性讀入內存例如HBASE（借助于HDFS），將數據分片為64MB-256MB大小。架構主從架構：主節(jié)點負責存儲元數據，和客戶端訪問接口，從節(jié)點負責存儲數據分片，如：HBase對等結構：無主節(jié)點，各個節(jié)點都可以接受客戶端訪問請求，如果自身沒有存儲相關分片，則去該節(jié)點回去向其他節(jié)點查詢數據，如：Cassandra第2章 NoSQL數據庫的基本原理2.2 分布式數據管理的特點2.2.1 數據分片重要機制如果原始數據是一個大型文件（比如TXT換格式的100GB的網站日志文件），則需要將數據切分大數據工具存儲日志類數據時，可以根據自然的行進行切分數據導入NoSQL之后，可以根據記錄的行進

13、行切分當節(jié)點數量變化時，分片的存儲位置等應該可以調整（到其他節(jié)點）節(jié)點對自身存儲的分片負責，循環(huán)檢查數據分片是否健康，節(jié)點一般不關心其他節(jié)點上分片存儲切分過程、分片的調整過程等應當是自動的，用戶不需要手動處理分片用戶訪問一個接口，即可訪問所有數據，用戶不需要知道數據屬于哪個分片，存儲在哪個節(jié)點上。問題：如果部分節(jié)點出現(xiàn)故障，數據或查詢任務是否會出現(xiàn)缺失？如何解決？當數據庫為單機部署時，不存在系統(tǒng)部分故障的問題，系統(tǒng)要么100%正常，要么100%失效，此時可以通過主備服務器等方式提高系統(tǒng)的可靠性第2章 NoSQL數據庫的基本原理2.2 分布式數據管理的特點2.2.2 數據多副本背景：在大規(guī)模分布

14、式系統(tǒng)中，要將部分節(jié)點失效視為“常態(tài)”，而非異常。此時必須考慮集群系統(tǒng)在局部故障的情況下，也能夠正常運行。故障可能是臨時的，也可能時永久的，例如：節(jié)點死機、節(jié)點硬盤故障、網絡雍塞、交換機故障等解決：將數據存儲為多個副本，不同的副本存儲在不同節(jié)點上，通常是以數據分片為單位實現(xiàn)多副本。相對于原始文件或整個表格，分片的體積較小，容易被檢測、拷貝理論上n個副本都可以被讀取，但n個副本是否可以被更新，則要視系統(tǒng)實現(xiàn)和用戶策略而定例如：HDFS中，基于“機架感知”的三副本機制。進一步的問題：假設分片被復制了n份，存儲在不同節(jié)點上，當一個副本被更新時，其他副本如何同步？如果在更新同步時出現(xiàn)臨時或永久故障，如

15、何解決？用戶是否需要了解，或如何了解副本的同步情況？第2章 NoSQL數據庫的基本原理2.2 分布式數據管理的特點2.2.2 數據多副本進一步的問題：假設分片被復制了n份，存儲在不同節(jié)點上，當一個副本被更新時，其他副本如何同步？如果在更新同步時出現(xiàn)臨時或永久故障，如何解決？用戶是否需要了解，或如何了解副本的同步情況？如果n個副本只有一個能被更新，則該機制就是“讀寫分離”，此時，如果“讀”副本出現(xiàn)臨時故障，則在故障恢復后可以再向主節(jié)點查詢并同步數據。如果“讀”副本出現(xiàn)永久故障，則系統(tǒng)一般會在其他節(jié)點上建立新的副本。如果“寫”副本出現(xiàn)故障，則系統(tǒng)無法繼續(xù)更新數據，此時需要通過“選舉”等機制，建立一

16、個新的“寫”副本。如果n個副本都可以被更新，則可能多個副本之間可能存在數據版本”分叉“（沖突），此時需要額外機制檢測到分叉，并消除。（參見第六章的Dynamo機制）用戶是否需要了解副本同步情況，不同的NoSQL系統(tǒng)有不同的策略。第2章 NoSQL數據庫的基本原理2.2 分布式數據管理的特點2.2.3 一次寫入多次讀?。╓ORM）背景：典型的大數據場景，如：搜索引擎抓取網頁并抽取正文、鏈接，并不需要修改抓取的原始網頁。網站或物聯(lián)網應用抓取到日志或監(jiān)控數據，一般只會進行查詢、統(tǒng)計、挖掘，也不需要修改原始數據。從系統(tǒng)層面，如果數據不需要修改（update、insert或delete），數據的存儲、分

17、片和多副本機制可以大為簡化。此外可以實現(xiàn)將分片內數據排序等機制，以加快掃描速度。應用一次寫入多次讀取機制，意味著在系統(tǒng)底層只支持新建和追加（append）。此時系統(tǒng)具有更好的順序存儲特性，對于機械硬盤，順序讀寫比隨機讀寫的開銷更小，硬件損耗更小，出現(xiàn)碎片的可能性較?。ㄐ枰浜掀渌麢C制，詳情可以參考第五章描述的HBASE寫入機制）。如何在一個只支持append的存儲系統(tǒng)上實現(xiàn)數據更新、插入和刪除？可以采用時間戳機制。從WORM設計，也可以看出NoSQL應用場景和RDBMS存在差異，相互不可替代。第2章 NoSQL數據庫的基本原理2.2 分布式數據管理的特點2.2.4 分布式系統(tǒng)的可伸縮性背景：分

18、布式系統(tǒng)中可能存在節(jié)點故障、以及持續(xù)采集數據導致系統(tǒng)容量或處理能力出現(xiàn)瓶頸。目標：分布式系統(tǒng)需要提供一種易于操作的增加、移去或替換節(jié)點的方法節(jié)點變動時，數據分片和副本可以自動平衡，空白的新節(jié)點會被存入適當的分片副本，移走的節(jié)點所負責的數據會被指派給別的節(jié)點個別節(jié)點變動和數據平衡時，對系統(tǒng)服務的影響較小，即節(jié)點變化可以動態(tài)進行，數據平衡在后臺進行（例如：限制數據平衡時使用的帶寬，以防止對系統(tǒng)正常服務產生過大影響等）節(jié)點變化后，用戶可以方便的查看當前節(jié)點的列表和運行情況第2章 NoSQL數據庫的基本原理2.2 分布式數據管理的特點小結：在分布式數據管理中，需要保持集群的高性能、高可靠性和易用性進行

19、分布式數據管理的主要目的是通過橫向擴展提升數據存儲、管理、查詢和處理性能負載均衡：數據分片，并均勻分布在各個節(jié)點上；計算本地化，節(jié)點只查詢自身的數據集群可伸縮：集群規(guī)模可以隨著數據增長進行橫向擴展將底層存儲設置為“一次寫入多次讀取”，簡化大數據場景下的軟件設計難度由于分布式環(huán)境中存在部分節(jié)點不可達的可能，因此需要保證部分節(jié)點出現(xiàn)故障時，系統(tǒng)的其他部分仍可以正常工作；此外故障最終可以被發(fā)現(xiàn)和消除容錯性：數據多副本，副本存儲在不同節(jié)點上，多副本之間具有同步更新、沖突檢測等機制集群可伸縮：可以移除故障節(jié)點，替換新節(jié)點，并實現(xiàn)數據的再平衡不能要求用戶精通分布式系統(tǒng)原理，或者事先了解集群中的大量細節(jié)信息

20、才能使用，系統(tǒng)必須易用自動管理副本：自動分片、自動檢測副本狀態(tài)、節(jié)點的變化，并平衡數據統(tǒng)一訪問接口：用戶通過統(tǒng)一接口即可訪問數據，不必預先知道各個節(jié)點的信息或集群拓撲等。第2章 NoSQL數據庫的基本原理2.2 分布式數據管理的特點目標分布式系統(tǒng)中（特別是NoSQL數據庫），數據多副本產生的一致性問題進一步的目標：各個節(jié)點之間對某一主題達成共識（例如：配置信息更新）概念上的差別（CAP和BASE的概念將在隨后解釋）ACID中的一致性：強調（一個或多個）事務前后，數據的狀態(tài)（約束、完整性等）都是有效的。CAP中的一致性：強調多個副本是狀態(tài)一致、同步更新的BASE中的一致性：和ACID中的一致性相

21、近，但強調弱一致性第2章 NoSQL數據庫的基本原理2.3 分布式系統(tǒng)的一致性問題2.3.1 CAP理論CAP是指分布式系統(tǒng)中的Consistency（一致性）、Availability（可用性）、Partition tolerance（分區(qū)容錯性）。CAP理論是指在分布式系統(tǒng)中，CAP三個特性不可兼得，只能同時滿足兩個。和RDBMS中的ACID相比較的原因是，理論上分布式系統(tǒng)中多副本的更新應該是一個“事務”，要么都成功，要么都失敗，并且性能很好，但實際上存在難題。一些分布式系統(tǒng)可以實現(xiàn)分布式事務（當前大多數NoSQL系統(tǒng)不支持，或不能良好支持），即可以提供跨節(jié)點的ACID。CAP則是強調集群

22、環(huán)境下，數據多副本帶來的問題，此時二者討論的主題不同。第2章 NoSQL數據庫的基本原理2.3 分布式系統(tǒng)的一致性問題CAP理論可參考：Brewers Conjecture and the Feasibility of Consistent，Available，Partition-Tolerant Web Services2.3.1 CAP理論Consistency（一致性），是指分布式系統(tǒng)中所有節(jié)點都能對某個數據達成共識，例如：多個副本內容是否相同，當出現(xiàn)不一致時，以哪個副本為準。Availability（可用性），這里可以理解為分布式系統(tǒng)的響應速度，或響應能力。Partition tole

23、rance（分區(qū)容錯性），指在部分節(jié)點故障、以及出現(xiàn)消息丟包的情況下，集群系統(tǒng)（的剩余部分）仍然可以提供服務，完成數據訪問，這一般需要通過合理的數據多副本機制實現(xiàn)。CAP不能兼顧，但并非絕對對立。在實際NoSQL系統(tǒng)中， 一般通過設計上的取舍和使用過程中的配置，在A和C之間進行權衡對于大多數分布式系統(tǒng)，P是必須的在系統(tǒng)設計層面，或系統(tǒng)的模塊設計層面，以及在不同的業(yè)務場景下，都可能采用不同取舍策略或配置策略第2章 NoSQL數據庫的基本原理2.3 分布式系統(tǒng)的一致性問題2.3.1 CAP理論假設系統(tǒng)中，數據只有一個副本。則一致性（C）可以得到絕對的保障，由于在讀寫時不需要通過網絡查詢其他副本的情

24、況，因此讀寫性能較高（A），但如果存儲數據的節(jié)點故障則無法容錯，即該設計兼顧CA。假設系統(tǒng)中，數據存在n個副本，但采用“讀寫分離”機制，只有一個副本可以接受寫請求。此時：對于寫操作，一致性和可用性較好，因為只要寫完一個副本，操作即為成功，但此時該寫入節(jié)點無法實現(xiàn)分區(qū)可用性，即兼顧CA。對于讀操作，假設數據存在多個“只讀”副本，客戶端每次只讀取其中一個，則該設計實現(xiàn)了讀操作的分區(qū)可用性（多副本），可用性較好，但客戶端無法判斷該副本是否為最新的（考慮網絡通信的不確定性），即只兼顧了PA。對于讀操作，假設客戶端需要同時讀取多個副本，并對比這些副本，以檢查是否存在版本差異或版本沖突。則此時兼顧了PC，

25、由于需要讀取多個副本，因此客戶端響應時間變長，可用性（A）變弱。第2章 NoSQL數據庫的基本原理2.3 分布式系統(tǒng)的一致性問題2.3.1 CAP理論思考：假設在分布式系統(tǒng)中，數據存儲為3個副本，每個副本都可以接受讀寫請求。如果強調讀操作的PA，應采用何種策略？如果強調讀操作的PC，應采用何種策略？如果強調寫操作的PA，應采用何種策略？如果強調寫操作的PC，應采用何種策略？如何在保證P的情況下，希望能夠兼顧AC，可以采用何種妥協(xié)策略？在“一次寫入多次讀取”機制下，是否可以討論寫操作的CAP？數據分片可能支持Append數據分片可能被整體刪除數據分片可能在批量更新沒有完成時出現(xiàn)網絡故障針對一條記

26、錄，可以通過時間戳+append等機制實現(xiàn)數據改寫，從而在多副本之間產生版本差異第2章 NoSQL數據庫的基本原理2.3 分布式系統(tǒng)的一致性問題2.3.2 BASE和最終一致性BASE: An Acid AlternativeBASE是一個和ACID相對比的概念，強調弱一致性ACID指事務的強一致性。在分布式環(huán)境下，涉及到網絡通信的不可靠性，性能較差，且技術實現(xiàn)復雜。ACID認為事務執(zhí)行時不應存在中間狀態(tài)，只有“成功”、“回滾”等最終狀態(tài)。BASE強調，在互聯(lián)網等場景中，用戶響應（即可用性）很重要，必須首先滿足。最終一致性（ Eventual Consistency ），即事務存在中間狀態(tài)，但

27、經歷一段時間之后，最終會一致。最終一致性（在一些應用場景下）也可以看作NoSQL允許多個副本可以存在暫時的不同步（即異步更新），結合CAP理論，這種設計強調PA，可以提高響應速度。第2章 NoSQL數據庫的基本原理2.3 分布式系統(tǒng)的一致性問題2.3.2 BASE和最終一致性BASE所強調的軟狀態(tài)、弱一致性等，在一些互聯(lián)網業(yè)務中，并不會帶來大的問題。例如：一位歐洲用戶在社交軟件上短時間內更新了多次頭像，但他在亞洲的好友即便正在刷新，可能也只能在一段時間后才看到更新的情況，并且只看到了最終的頭像，中間的更新結果在服務器同步信息的過程中被覆蓋了。弱一致性場景中， 經常會使用“異步消息機制”在網絡節(jié)

28、點之間的進行通信。異步消息意味著消息的發(fā)送和接受之間存在時間差。消息的發(fā)送者在消息發(fā)出后立刻退出發(fā)送流程，不會阻塞等待接受者的反饋，因此不會受到網絡延遲等影響，因此系統(tǒng)的響應時間較少。這也可以看作是一種軟狀態(tài)機制。NoSQL中也會使用異步消息機制進行事件通知等，但最終用戶一般不需要關心其具體過程。第2章 NoSQL數據庫的基本原理2.3 分布式系統(tǒng)的一致性問題2.3.2 BASE和最終一致性BASE所強調的軟狀態(tài)、弱一致性等，在一些互聯(lián)網業(yè)務中，并不會帶來大的問題。例如：一位歐洲用戶在社交軟件上短時間內更新了多次頭像，但他在亞洲的好友即便正在刷新，可能也只能在一段時間后才看到更新的情況，并且只

29、看到了最終的頭像，中間的更新結果在服務器同步信息的過程中被覆蓋了。弱一致性場景中， 經常會使用“異步消息機制”在網絡節(jié)點之間的進行通信。異步消息意味著消息的發(fā)送和接受之間存在時間差。消息的發(fā)送者在消息發(fā)出后立刻退出發(fā)送流程，不會阻塞等待接受者的反饋，因此不會受到網絡延遲等影響，因此系統(tǒng)的響應時間較少。這也可以看作是一種軟狀態(tài)機制。NoSQL中也會使用異步消息機制進行事件通知等，但最終用戶一般不需要關心其具體過程。第2章 NoSQL數據庫的基本原理2.3 分布式系統(tǒng)的一致性問題假設在讀寫分離場景下，有一個寫節(jié)點（稱為主節(jié)點），和若干個讀節(jié)點（稱為從節(jié)點）。當主節(jié)點出現(xiàn)故障時，集群如何實現(xiàn)自動的故

30、障恢復？可以在從節(jié)點中“選舉”出一個新的主節(jié)點?？梢杂蓮墓?jié)點（或若干外部節(jié)點）進行自動選舉。此時需要一個算法（或網絡協(xié)議），來協(xié)調選舉者的行為。假設在一個集群環(huán)境中，所有節(jié)點都需要更新一個配置項，如何自動發(fā)現(xiàn)該配置項的更新？需要所有節(jié)點對“xx配置項更新為xx”，（發(fā)現(xiàn)并）達成共識第2章 NoSQL數據庫的基本原理2.3.4.Paxos算法簡介Paxos是一種基于異步消息的一致性算法（共識算法），主要解決了如下問題：如何發(fā)起投票，特別是當多個節(jié)點希望發(fā)起投票時，如何決定投票主題？具有投票權的節(jié)點如何投票？出現(xiàn)網絡故障、延遲或部分節(jié)點失效時，投票過程和結果是否還有效？如何讓“吃瓜群眾”（lear

31、ner）獲知投票結果Paxos“被認為是同類算法中最有效的”，具有多種改進算法（例如：Fast Paxos等）?，F(xiàn)有的分布式一致性軟件，如：Zookeeper、chubby軟件，以及諸如MongoDB等NoSQL數據庫中的主節(jié)點選舉模塊，大多使用或借鑒了Paxos（至少是相似的）。第2章 NoSQL數據庫的基本原理2.3.4.Paxos算法簡介基本角色若干proposer （提議者）：proposer負責提出投票提議（proposal），以及給出建議的決議（或稱為值，value）。若干（一般三個以上的奇數個）acceptor（投票者）：acceptor收到提議后進行投票，以少數服從多數的原則決

32、定是否接受提議，以及是否批準該值?？赡苓€存在下列角色client客戶端：提議的產生者，client將提議提交給任意proposer，由其提交投票。learner （學習者，有時稱observer）：learner只能觀察投票結果，并更新自己的認識（值）。leader：在改進后的Paxos機制中負責。在實際系統(tǒng)中，通常只有客戶端和服務器的概念。客戶端一般扮演client、proposer和learner的角色，而服務端扮演accepter、coordinator和leader的角色。此外，一個節(jié)點也可能承擔多個角色。第2章 NoSQL數據庫的基本原理2.3.4.Paxos算法簡介第一階段為發(fā)起提

33、議階段反饋的acceptor為半數以上原則，少部分節(jié)點失效時，投票仍可以進行接受提議的編號為最新原則，確保當前只為一個提議投票，確保當前提議是最新的。反饋決議為歷史決議或空值原則第二階段為決議的批準階段proposer決定決議（值）反饋的acceptor為半數以上原則學習者或客戶端只能學習到投票通過的決議（或值）進一步需要解決如何防止提升編號搶占提議權？引入leader機制，在第一階段由leader決定提議。如何加快投票過程。（fast Paxos協(xié)議）授予leader在第二階段發(fā)生沖突時的決策權。第2章 NoSQL數據庫的基本原理2.3.4.Paxos算法簡介投票流程：第2章 NoSQL數據

34、庫的基本原理2.3.4.Paxos算法簡介相當于實現(xiàn)了分布式環(huán)境下的ACID，必須全部節(jié)點都成功提交更新，整個事務才算成功存在協(xié)調者（左）和參與者（右）兩個角色在不同階段，不同的角色或通信出現(xiàn)故障，所產生的影響是不同的大部分NoSQL數據庫軟件并不直接支持分布式事務提交。因為其阻塞過程對系統(tǒng)的整體性能影響較大第2章 NoSQL數據庫的基本原理補充：分布式事務、二階段提交和三階段提交兩階段提交過程三階段提交過程兩階段提交的簡要過程如下：1協(xié)調者和參與者準備就緒，參與者等待消息。2第一階段開始:協(xié)調者進入PREPARE狀態(tài)，發(fā)送PREPARE消息，協(xié)調者等待消息3參與者收到消息，能夠繼續(xù)執(zhí)行，則進

35、入READY狀態(tài)并發(fā)送READY指令，否則發(fā)送ABORT。消息發(fā)送后，將日志寫入磁盤，參與者進入阻塞狀態(tài)等待后續(xù)消息。4第二階段開始:協(xié)調者收到所有消息，從PREPARE變更為COMMIT或ABORT狀態(tài)，相應的發(fā)送global_commit或者global_abort指令給所有的參與者。5參與者收到global_commit或者global_abort消息，執(zhí)行本地事務操作或回滾，同時解除阻塞狀態(tài)。兩階段提交可以在大多數情況保障分布式事務的原子性，即事務的相關操作要么都成功，要么都失敗。分析如下：1兩階段提交中所有的消息等待過程，都可以設置超時。在步驟3、4接收消息時，如果出現(xiàn)超時，則參與者

36、或協(xié)調者可以認為對方故障，因而事務失敗，并執(zhí)行相應指令。2在步驟5處，如果參與者一直沒有收到global_commit或者global_abort消息，則無法直接判斷是否應該中止事務，因為有可能commit消息已經發(fā)出，但由于網絡問題沒有收到，此時有可能其他節(jié)點已經進行了commit，也有可能時協(xié)調者故障。同理，如果在執(zhí)行步驟4之后，參與者出現(xiàn)故障，當故障恢復之后，參與者無法判斷事務處在何種狀態(tài)。3如果認為參與者之間可以相互通信，則參與者一直沒有收到global_commit或者global_abort消息時，可以向其他參與者發(fā)出詢問。如果參與者在此過程中出現(xiàn)故障，也可以在故障恢復后，通過向協(xié)

37、調者或其他參與者詢問的方式恢復事務應有的狀態(tài)。如果協(xié)調者在步驟4出現(xiàn)故障，則可能所有參與者都沒有收到步驟5處的global_commit或者global_abort消息。此時會造成參與者一直阻塞，直到協(xié)調者恢復（例如通過日志恢復）或有部分參與者收到global_commit或者global_abort消息等。如果有部分參與者還沒有進行投票時就出現(xiàn)協(xié)調者故障，則在參與者相互協(xié)商之后，可中止事務。上述機制稱為協(xié)同中止機制。兩階段提交的主要問題在于，當第二階段出現(xiàn)協(xié)調者故障時，參與者阻塞時間較長，可能需要協(xié)調者完全恢復，參與者才知道要做什么，并解除阻塞。在阻塞期間，參與者無法參與其他事務，也無法執(zhí)行

38、其他可能破壞事務原子性的操作。針對這個問題，有人提出了三階段提交方案。三階段提交的前提是節(jié)點可能發(fā)生故障，但通信鏈路不會發(fā)生故障。三階段提交的主要流程為：1第一階段：協(xié)調者發(fā)出投票消息，參與者判斷自身是否可以提交任務，并反饋給協(xié)調者。2第二階段：如果所有參與者都可以提交，協(xié)調者發(fā)出PreCommit消息，參與者收到消息后將事務寫入日志，并反饋給些調整。3第三階段：協(xié)調者根據情況發(fā)出global_commit消息，參與者收到消息后進行真正的提交。二階段提交時，如果在第二階段出現(xiàn)協(xié)調者故障，則參與者必須阻塞等待到超時，在執(zhí)行協(xié)同中止機制，甚至有幾率引發(fā)更長的阻塞。但在三階段提交時，如果參與者沒有收

39、到第二階段的PreCommit消息，或協(xié)調者沒能收到全部的PreCommit回復，都可以判定提交失敗，而不需要協(xié)同中止。如果在收到PreCommit之后，參與者沒有收到global_commit，也可以之際提交任務，因為收到PreCommit即表示所有參與者都承諾可以提交任務，此時不存在不確定性，不需要阻塞等待。三階段提交以更大的網絡開銷，降低了參與者處在不確定狀態(tài)的時間，使得發(fā)生故障時的阻塞時間更短。但是在故障率較低的場景下，為降低網絡開銷，二階段提交應用的更加廣泛。NoSQL并沒有一個統(tǒng)一的存儲模式，底層存儲引擎的實現(xiàn)差異很大，具體策略和配置方式也因軟件而異。常見的存儲模式有：鍵值模式、列

40、存儲模式、文檔存儲模式和圖存儲模式等。常見的NoSQL軟件可能會結合使用多種存儲模式，例如鍵值對和列存儲。這些存儲模式在底層大多是一次寫入多次讀取的。除了圖存儲模式之外，大多對分布式環(huán)境支持較好。這些存儲模型之上，一般只支持簡單的查詢，對關聯(lián)查詢等支持較差。這些存儲模型對索引（例如：二級索引）的支持較差。第2章 NoSQL數據庫的基本原理2.4 NoSQL的常見存儲模式NoSQL并沒有一個統(tǒng)一的存儲模式，底層存儲引擎的實現(xiàn)差異很大，具體策略和配置方式也因軟件而異。常見的存儲模式有：鍵值模式、列存儲模式、文檔存儲模式和圖存儲模式等。常見的NoSQL軟件可能會結合使用多種存儲模式，例如鍵值對和列存

41、儲。這些存儲模式在底層大多是一次寫入多次讀取的。除了圖存儲模式之外，大多對分布式環(huán)境支持較好。這些存儲模型之上，一般只支持簡單的查詢，對關聯(lián)查詢等支持較差。這些存儲模型對索引（例如：二級索引）的支持較差。第2章 NoSQL數據庫的基本原理2.4 NoSQL的常見存儲模式NoSQL并沒有一個統(tǒng)一的存儲模式，底層存儲引擎的實現(xiàn)差異很大，具體策略和配置方式也因軟件而異。常見的存儲模式有：鍵值模式、列存儲模式、文檔存儲模式和圖存儲模式等。常見的NoSQL軟件可能會結合使用多種存儲模式，例如鍵值對和列存儲。這些存儲模式在底層大多是一次寫入多次讀取的。除了圖存儲模式之外，大多對分布式環(huán)境支持較好。這些存儲

42、模型之上，一般只支持簡單的查詢，對關聯(lián)查詢等支持較差。這些存儲模型對索引（例如：二級索引）的支持較差。第2章 NoSQL數據庫的基本原理2.4 NoSQL的常見存儲模式2.4.1 鍵值對存儲模式所謂鍵值對，即（物理上）每行數據的結構為：，或者等形式。Key相當于主鍵如果有多個Key相同的鍵值對，則被看作在邏輯上是一行數據，或者被認為是該value的更新歷史（以時間戳決定版本新舊）Value一般較為自由，不限定數據類型、值域等，很難對Value建立索引。沒有列或列名的概念，列名可能顯式的現(xiàn)在value中，例如：，即key為 編號001，value包含了列名（姓名）和取值（張三）。在實際系統(tǒng)中，一

43、般會根據key進行數據分片內的局部排序，以加快檢索效率Redis、HBase、Cassandra等使用該存儲模式第2章 NoSQL數據庫的基本原理2.4 NoSQL的常見存儲模式2.4.2 文檔式存儲模式可以看作鍵值對模式的升級，底層存儲的每行數據中仍然存在key（或者ID）和value。但Value是采用JSON等格式描述的復雜數據類型每條數據的文檔格式可以不同文檔格式中支持嵌套等復雜形式比較有名的文檔式數據庫，如MongoBD和CouchDB等第2章 NoSQL數據庫的基本原理2.4 NoSQL的常見存儲模式這是MongoDB中的一行數據，描述一條通信錄數據。數據包含_id、usernam

44、e、contact和access列， contact和access列是復合列，不滿足關系型數據庫中的列的原子性JSON是一種輕量級的數據交換語言。JSON最被熟知的應用之一，是作為JavaScript語言中的對象和數組，這從它的英文名也可以看出。JSON也被用來在RESTFUL風格的Web接口中進行數據交換。JSON對數據的組織方法和XML類似，獨立于語言，具有自我描述性，但是比XML更簡潔，對結構的要求也沒有那么嚴謹，如下面的例子：“mail”: “from”:“Alice”,”to”:“Bob”, “head”:“This is an email”, “body”:“ Hello! Thi

45、s is an email.”, “attachment”:“ Hello! This is an attachment.” “comment”:“This is a comment”JSON中的元素可以看作是一種鍵值對的描述方式，以“：”為間隔，前面是鍵后面是值，鍵需要用雙引號包括。JSON支持一些數據簡單的數據類型，如：整數或浮點數：“year”:2018 字符串：“year”:“2018” 對象：“year”:“2018”，“month”:“Jan”，“dayofmonth”:“1” 邏輯值：“IsHoliday”: true空值：“IsHoliday”: null數組：“week”:“

46、Mon”, “Tue”, “Wed”, “Thu”, “Fri”, “Sat”, “Sun”一般認為，描述相同的數據結構，JSON比XML更加簡潔，JSON的存儲和處理效率更高。JSON支持一些簡單的數據類型，因此在描述數據時更加方便。JSON沒有保留字，不要求嚴格的樹形結構。用javascript、Python等常見高級語言，可以非常方便地解析JSON數據。2.4.3 列存儲模式可以看作是一種縱向切分數據的方式，不同列會放到不同的位置（節(jié)點）存儲，實際軟件一般也會按照行鍵（key）再進行橫向切片和分布式存儲。對于稀疏表（空值較多），其存儲效率較高底層一般也是一次寫入多次讀取的在切片內一般會按

47、行鍵進行排序，以加快分布式檢索速度。比較有名的列存儲數據庫，如谷歌的Big Table和Dremal，以及HBase等。第2章 NoSQL數據庫的基本原理2.4 NoSQL的常見存儲模式面向行和面向列存儲的對比Dremel列存儲架構簡介（1）Dremel是谷歌研發(fā)的交互式數據分析系統(tǒng)，谷歌在2006年撰寫、并2010年公開的論文Dremel: Interactive Analysis of Web Scale Datasets介紹了這個系統(tǒng)。Apache Drill和Cloudera Impala則是基于Dremel模型實現(xiàn)的開源分布式數據倉庫軟件的典型代表。Dremel采用了列存儲機制，此外

48、Dremel中的每條記錄也可以看作文檔型記錄，下面對其存儲架構做一個介紹：假設有兩個文檔類型的記錄，r1和r2，如圖所示：Dremel列存儲架構簡介（2）r1和r2表示的是兩個網頁的部分信息數據。其結構參見右上角的“Documents”格式（schema），這個格式采用個谷歌的proto buffer格式構建。這兩個記錄顯然不滿足列的原子性原則。結構中出現(xiàn)了嵌套的字段，例如“Name”，格式定義中的“group”表明其可以嵌套。結構中具有可以重復的字段如“Language”，在格式定義時，“Language”前面的“repeat”關鍵字說明該情況，注意其重復次數是不固定的，最少可以是零次。結構

49、中的“DocId”字段必須存在（“required”），其他的字段都是可選的，在格式定義中的“option”說明該情況?！癋orward”和“backward”字段的數值是其他記錄的“DocId”。此外，r1和r2的信息內容差別很大，如果以面向行的方式存儲，則r2可能存在大量空值。且支持“repeat”的字段，可能需要采用多個表實現(xiàn)。Dremel列存儲架構簡介（3）假設存在很大數量的記錄，為了支持快速的檢索，Dremel設計了一種列存儲方式，如圖所示：可以看出Dremel中設計了了六個容器（六個表或六個文件）來存儲不同的非集合字段，對Name和Language等集合型字段則沒有專門的容器。表名

50、記錄了字段名以及所屬的集合，例如：Name.url表明url在name這個集合（或稱為路徑）下。表中的“Value”記錄具體的字段數值，r表示重復級別，d表示字定義深度。例如：DocId表記錄了r1和r2的docid。其重復級別和定義深度都是0。Dremel列存儲架構簡介（4）重復級別表示了當前value在哪個級別出現(xiàn)了重復。觀察r1中name重復了三次，而name. language以及其中的code字段在第一個name中重復兩次，在第三個name中出現(xiàn)1次。在name.language.code表中，這三個code字段的重復級別為0、2、1：0表示en-us這個值在第一個name，以及na

51、me中的第一個language路徑下，此時美這個字段是第一次出現(xiàn)，沒有重復。2表示en這個值在第一個name下，但在第二個language中，這是這個字段在r1中的重復出現(xiàn)。由于name是第一級可重復的集合（定義了repeat關鍵字），language是第二級可重復的集合，數值2表明該值實在第二級上出現(xiàn)了重復。1表示en-gb這個值在第二個name下的第一個language下面，和之前數值相比，是在第一級上出現(xiàn)了重復，所以表示為數值1。同理，考察link.forward這個表，20、40、80這三個記錄的r值分別為0、1、1，即表示20是在r1記錄中第一處出現(xiàn)的forward值，此時沒有發(fā)生任

52、何重復。后面的1、1則表示在forward級別上出現(xiàn)重復，注意此時link不計入重復級別的計算，因為link的定義中沒有“repeat”關鍵字。Dremel列存儲架構簡介（5）注意name.language.code表中記錄了一個空值，這表示在r1的第三個name中并沒有l(wèi)anguage和code，由于是記錄第三個name下的情況，在name這個級別上有重復，即對于這個空值，r=1。第二個空值則表示在r2記錄中，第一個name不存在language和code字段，此時還未發(fā)生重復，所以r=0。定義深度表示當前值的路徑中，有多少個可選字段是存在的，所謂可選字段包括option和repeat兩種定

53、義方式，反例則是required關鍵字。 仍然考察name.language.code這個表，name和language都是可選的，而code是必須的，所以所有的非空數值，其定義深度d都是2，換句話說，對于所有同類型的非空字段，其定義深度都是一樣的。但對于表中的空值來說，第一個NULL表明在r1記錄中，第三個name下沒有l(wèi)anguage.code這個值，甚至連language也沒有，因此在這個null值所在的路徑上，只有一個可選字段有定義，即name。第二個NULL值表明在r2記錄中也是只有name存在，后續(xù)的language.code都不存在。可見定義深度大多數情況只對空值有用，它說明了該

54、空值所屬的路徑到哪個級別就不存在來了。Dremel列存儲架構簡介（6）在上述數據結構中，如果進行寫入，則只能進行順序的增加，很難進行對已有記錄的修改和插入，特別是為記錄增加新字段。因為在列存儲結構中，不會為空值或可重復的字段預留足夠的空間。在讀取時，這種結構非常適合進行全表掃描，特別是指定字段的全表掃描。例如：想查看某個指定ID記錄所支持的語言，只需要記錄這個ID在DocID表中的位置n（第n個記錄），然后再language表的r字段找到第n個0就行了，因為重復級別為0則表示這是再當前記錄中第一次出現(xiàn)該字段，而0的數量則暗示了這是第幾條記錄。同樣的，這種結構非常適合進行記錄的計數（Count）

55、和聚合（Group by）等操作。如果對上述數據結構進行拆分，并進行分布式處理，則全表掃描的速度還會以數倍的速度加快，這也體現(xiàn)了Dremel是為大數據業(yè)務服務的理念。Dremel的表結構看上去不適合進行快速的交互式隨機查詢，但是考慮到Dremel的主要用途是進行網頁分析、日志分析等典型大數據業(yè)務，實時隨機查詢并不是很常見的行為，并且數據一旦寫入一般不會被更改（即一次寫入多次讀?。?，因此缺陷并不會其在常用領域發(fā)揮作用。此外，理論上說還可以通過為特定的表加索引等方式加快隨機查找速度，但谷歌發(fā)表的論文中并沒有涉及這方面內容。谷歌為Dremel設計了相應的數據壓縮、編碼、查詢等機制，支持以簡單SQL語

56、句的方式查詢數據。并通過測試證明這種機制在查詢效率、擴展性、容錯性等方面表現(xiàn)較好。進一步的，可以看出列存儲、乃至NoSQL只是服務于特殊場景下的數據庫工具，在這些特定領域之外，NoSQL會顯得功能過于簡單，性能也無從談起，也無法替代關系型數據庫。2.4.4 圖存儲模式將數據存儲為點和邊的關系點通過邊相連接，具有名稱、類型和屬性、相連接的邊等關聯(lián)信息邊一般是單向的，具有名稱、類型、起止節(jié)點和屬性等信息右圖中有14條數據（記錄）：類型為顧客的點（3條數據）類型為商品的點（3條數據）類型為瀏覽的邊（2條數據）類型為購買的邊（4條數據）類型為配件的邊（2條數據）常見的圖存儲數據庫，如：Neo4J等。第

57、2章 NoSQL數據庫的基本原理2.4 NoSQL的常見存儲模式一個簡單的圖示例2.5.1 分布式數據處理NoSQL一般不提供復雜的數據處理功能大數據的處理可能是分布式的、多輪次的、耗時很長的，需要解決一系列問題在集群中分配出合理資源，例如：在數個節(jié)點分配出適合的內存大小、CPU能力等任務調度，一方面解決多任務排隊等問題，另一方面解決在一個任務中，如何將任務分解，分派給各個節(jié)點（或任務容器等），如何將處理邏輯交給各個節(jié)點（實現(xiàn)所謂計算本地化）如果處理任務需要多個輪次（步驟），如何解決中間數據分發(fā)、匯總等問題。如何監(jiān)控任務的進行過程，如何發(fā)現(xiàn)子任務的故障并提供容錯性。如何實現(xiàn)整個系統(tǒng)的易用性常見

58、的大數據處理軟件，如：Hadoop和Spark等NoSQL數據庫可以作為數據源配合工作。第2章 NoSQL數據庫的基本原理2.5 NoSQL系統(tǒng)的其他相關技術2.5.2 時間同步服務在分布式應用中，經常需要確保所有節(jié)點的時間是一致的。否則各個節(jié)點可能無法根據時間戳等機制進行通知、同步或一致性保障等。實際軟件系統(tǒng)中，如果節(jié)點時間差異較大，可能整個集群會無法啟動。NoSQL等大數據應用可能部署在局域網環(huán)境中，此時可以不和真實時間進行同步，但各個節(jié)點之間的時間應一致。NTP（Network Time Protocol，網絡時鐘協(xié)議）是一種常見的分布式時間同步機制。NTP協(xié)議已經發(fā)展到版本4，其精度可

59、以達到毫秒級，并且已經成為國際標準（IETF RFC 5905）Windows系統(tǒng)和大多數Linux系統(tǒng)均支持NTP協(xié)議既可以作為客戶端，也可以作為NTP服務端。可以實現(xiàn)基于互聯(lián)網的時間同步，也可以在局域網內實現(xiàn)局部時間同步。第2章 NoSQL數據庫的基本原理2.5 NoSQL系統(tǒng)的其他相關技術2.5.3 布隆過濾器歷史悠久，并非專門為分布式應用設計。目的是檢查某個元素是否存在于集合（例如數據塊）中。優(yōu)點是空間占用低、檢索速度快，缺點則是存儲在一定的誤報率：當布隆過濾認為某元素存在于集合時，該元素可能并不存在，但如果布隆過濾認為該元素不存在于集合，則肯定不存在。假設在一個節(jié)點上有多個數據文件。

60、當進行數據檢索時，節(jié)點可能需要依次掃描所有文件。受限于硬件條件，掃描速度可能成為性能瓶頸。即便存在誤報率，但布隆過濾器還是可以快速排除一些數據文件，從而大大提高單節(jié)點上的掃描速度。第2章 NoSQL數據庫的基本原理2.5 NoSQL系統(tǒng)的其他相關技術2.5.3 布隆過濾器隆過濾器利用一個定長的二級制向量和哈希函數構成。通過哈希函數將數據塊中存在的元素映射為二進制相量中的一個二進制位。二進制向量的長度一般是定值，但具體值可以根據用戶需求調整。元素與二進制位的映射關系是多對一的。如果某個二進制位有對應的值，則該點為1，否則為0。第2章 NoSQL數據庫的基本原理2.5 NoSQL系統(tǒng)的其他相關技術