NoSQL數(shù)據(jù)庫原理-第二章-NoSQL數(shù)據(jù)庫的基本原理課件

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

44、e、contact和access列， contact和access列是復(fù)合列，不滿足關(guān)系型數(shù)據(jù)庫中的列的原子性JSON是一種輕量級的數(shù)據(jù)交換語言。JSON最被熟知的應(yīng)用之一，是作為JavaScript語言中的對象和數(shù)組，這從它的英文名也可以看出。JSON也被用來在RESTFUL風(fēng)格的Web接口中進(jìn)行數(shù)據(jù)交換。JSON對數(shù)據(jù)的組織方法和XML類似，獨(dú)立于語言，具有自我描述性，但是比XML更簡潔，對結(jié)構(gòu)的要求也沒有那么嚴(yán)謹(jǐn)，如下面的例子：“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支持一些數(shù)據(jù)簡單的數(shù)據(jù)類型，如：整數(shù)或浮點(diǎn)數(shù)：“year”:2018 字符串：“year”:“2018” 對象：“year”:“2018”，“month”:“Jan”，“dayofmonth”:“1” 邏輯值：“IsHoliday”: true空值：“IsHoliday”: null數(shù)組：“week”:“

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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