NoSQL資料庫的調查與決策指引

NoSQL Databases: a Survey and Decision Guidance

  • 來源: https://medium.baqend.com/nosql-databases-a-survey-and-decision-guidance-ea7823a822d#.yy30ffv1e
  • 本文已獲作者Felix Gessert同意翻譯. (The translation of this article is authorized by the author Felix Gessert)
  • 我只處理文字部份, 圖片部份會連結到原網頁。

NoSQL Databases: 調查與決策指引

與University of Hamburg的同事們,就是 Felix GessertWolfram WingerathSteffen Friedrich 與 Norbert Ritter ,在 SummerSOC’16一起提供了一份涵蓋了NoSQL的概述。我們盡力去傳達我們在建構Baqend時所學到的NoSQL知識。

懶人包

這個年頭,資料的產生量與使用量都是史無前例的。而這導致了新的大量資料管理方法,來處理快速增加的資料量與負荷,”NoSQL”資料庫這個新的名詞被提出來代表這個方法。然而,現存系統的異質性與多樣性阻礙了我們挑選適合的資料儲存機制。所以,我們發表這篇文件來由上而下地觀察這個領域,基於NoSQL資料庫之間的功能性技術與演算法,我們做了比較性的分類,而不是去對比各別資料庫的實作。NoSQL Toolbox讓我們可以透過一個簡單的決策樹,來協助實作人員或研究人員以應用需求來過濾可行的系統。

1. 導論

經過幾十年的發展,傳統的relational database management systems (RDBMSs) 對於儲存與查詢結構化資料,提供了強健的一致性與交易保證,在可信賴性、可靠性與支援上,都達到了一個極高的水準。然而近幾年來,在某些領域的可用資料多到不能用傳統的儲存方案來處理。簡單舉兩個例子,社群網站上使用者產生的資料,或是大型感測器網路所產生的資訊,這種狀況即是大家說的Big Data。可以處理Big Data的新一代資料儲存機制被稱為NoSQL databases,藉由犠牲一些查詢能力與一致性保證,他們提供了比傳統資料庫更強大的水平擴展與高可用性。因為任何服務的擴展性與容錯性都與底層資料儲存機制相關,所以這樣的犠牲對於以服務為導向的計算或服務模型都是關鍵的。

NoSQL資料庫有好幾十種,加上他們的實作變得很快,功能也一直進化,要去了解他們哪裡優秀或是哪裡失敗,甚至是哪裡不一樣,都是很困難的。在這篇文章裡面,我們將範圍鎖定在NoSQL的概念、典型的需求、滿足需求所用的技術與他們必要的妥協,而不是各系統的規格。我們會專注在key-value、document與wide-column型式上,因為這些NoSQL種類在擴展性資料管理上,已經包含了大部份的相關技術與設計決策。

在第2節,我們會透過key-value、document與wide-column儲存資料模型,或是透過safety-liveness在設計上的妥協(像是CAP與PACELC)這些常見的高階方法來分類NoSQL。然後在第3節,我們會深入調查一下查用的技術,並討論需求與技術面如何關聯到我們的模型。第4節我們會應用我們的模型於那些傑出的資料庫系統,來做更廣泛的概述。在第5節,我們會有一個基於應用程式需求,用來縮減合適NoSQL系統選項的簡單抽象決策模型。

2. 高階系統分類

為了要從各個NoSQL系統的實作抽象化,我們可以使用高階的分類標準來將類似的資料儲存方法分為不同群組。在這一節,我們會講兩種最傑出的方法:資料模型與CAP理論類別。

2.1 資料模型的差異

最常用來判斷NoSQL資料庫差異的就是他們如何儲存、存取資料。在這篇文章裡面,我們會討論到的系統可以被分類為key-value、document或是wide-column的其中一種。

2.1.1 Key-Value Stores,鍵值儲存。Key-value 儲存形式會包含key-value pairs並擁有唯一key值。由於這種簡單的結構,它們只支援讀(get)與寫(put)兩種操作。因為對資料庫來說,儲存的值是可見的,單純的key-value儲存形式不支援CRUD(Create, Read, Update, Delete)以外的操作,因此通常被識為schemaless,意思是對於儲存資料的結構,會以應用程式的邏輯(schema-on-read)去編碼,而不是明確的透過資料定義語言去定義(schema-on-write)。

Figure 1: Key-value儲存提供了任意值的高效率儲存與擷取。

簡單,就是這種資料模型最明顯的優勢。這種簡單的抽象方法讓資料的分割與查詢都變得容易許多,也讓資料庫系統容易達到低延遲與高流量。然而,如果應用程式要求更複雜些的操作,像是區間查詢,這種資料模型就不怎麼夠力。Figure 1顯示了使用者帳戶資訊與設定值可能的儲存方式。既然比查表法(lookup)更複雜的查詢都不支援,需要分析資料的時候,像是要找出cookies有沒有被支援(cookies: false這個資料),效率就不怎麼好了。

3.1.2 文件儲存,document store。 所謂的文件儲存其實也是一種key-value儲存,只是值的部份是半結構化的格式,像是JSON之類的。這種改變,相較與key-value儲存來說,在存取資料時帶來了很大的彈性。不只是可以透過ID去存取整份文件,更可以僅擷取文件的某個部份(例如客戶的年齡),還可以做聚合查詢、以例查詢甚至是全文檢索。

Figure 2: 儲存個體的內部節構對文件儲存而言是已知的,所以可以支援查詢動作。

3.1.3 寬欄儲存 Wide-column stores。寬欄儲存(或寬列儲存),這個名字是來自於解釋底層資料模型的圖:一個有很多稀疏欄位的關聯表。技術上來說,Wide-column stores比較接近分散式多層排序映射(distributed multi-level sorted map),第一層的keys用來表明包含一堆key-value pairs的rows,這裡的keys稱為row keys。第二層的keys則稱為column keys。這種儲存綱要讓任意多欄的表格變得可行,因為每個column key都會有個對應的值存在。也因此,null值可以在儲存時不消秏任何多餘空間。所有的欄位都被分割到column families去,並將經常一起存取的欄位一起配置到磁碟去。在磁碟上,Wide-column stores並不會把每個row的資料配置在一起,相對的,是將同一個column family且同一個row的值配置在一起。因此,一個實體,也就是一個row,並不能像文件儲存一般透過單一查表就找出來,而是要從所有column families之中的欄位去找。然而,這種儲存方式通常可以對資料進行高度壓縮,使得擷取個體的部份時,變得很有效率。資料是以key的字典順序去儲存的,所以在適當的key設計之下,共同存取的資料可以是物理相連,速度會比較快。所有的rows都分散到不同tablet servers的連續區域(tablets)時,rows的掃瞄動作只會作用到少數伺服器,因此非常有效率。

Figure 3: 寬欄儲存的資料

Figure 3是Bigtable的圖例,Bigtable是Wide-column stores的領航者,特別發展來儲存大量網頁用的。網頁table裡面的每個row都對應到一個網頁。row key是反轉順序的URL,column key則是column family名稱與column qualifier組成,並由冒號隔開。這裡有兩個column families,分別是”contents”與”anchor”。contents只有一個column,包含真正的網頁內容,而anchor則是包含連結到每個網頁的超連結,每個連結存到個自欄位去。在table中的每一格(也就是可以透過row與column key存取的值)都可以由時間戳記或是版本號碼來知道更新狀況。要特別說明的是,大部份的資訊其實是在key而不只在值。

2.2 一致性與可用性的抉擇: CAP 與 PACELC

除了資料如何儲存、資料怎麼存取之外,另一個資料庫決定性的性質就是他們提供了什麼程度的資料一致性。有些資料庫在設計之初就決定了要保證強一致性與序列性(ACID),有些則是偏好高可用性(BASE)。在這兩端所形成的光譜上,每個分散式資料庫與許多不同的NoSQL系統都繼承了這種抉擇。接下來,我們依資料庫系統在光譜上的位置來分類並解釋CAP與PACELC兩個理論。

CAP. 就像知名的 FLP Theorem一般,由Eric Brewer在PODC 2000提出來並由Gilbert與Lynch後來證明CAP 理論,在分散式計算領域是真正有影響力的impossibility results之一,因為它對分散式系統可以完成的事情設立了一個超級upper bound。它主要是說明,在容易發生網路斷掉的非同步系統中,循序一致的讀寫然後回應到每個要求是不可能的。換句話說,在某個時間點,下面三個屬性最多只有兩個可以保證:

  • 一致性 (Consistency,C): 讀與寫的動作都能單元性的執行而且嚴格保證資料一致性(linearizable)。換句話說,每個客戶端在每個時間點看到的資料都一樣。
  • 可用性(Availability,A): 在系統裡面的每個沒有掛掉的節點,都能接受客戶端要求的讀寫要求,並且可以回應期待的訊息,而非錯誤訊息。
  • 分區容忍度(Partition-tolerance,P): 在節點或是部分系統失敗時,若有訊息遺失狀況,系統仍要能支援一致性的保證與可用性。

 (Mick註一、建議可參考這兩篇來了解CAP理論:

  1. NoSQL 之 CAP 定理 與 挑選
  2. Wiki CAP定理

)

Brewer認為在一般操作時,系統可以同時滿足可用性與一致性,但是在系統發生分割的情況下,就不可能了。如果系統不管分割而持續運作,就表示會有某些失敗的節點跟其它節點失聯,因此必須要決定是要繼續處理客戶端的要求以滿足可用性(AP兩個屬性,也就是eventual consistent systems),或是拒絕客戶的要求,以保持一致性的保證,也就是CP。對一個選擇會違反一致性的原因是它會導致讀取到過時的資料,或是導致寫入衝突;而第二種選擇則是明顯犠牲了可用性。也有一些系統會滿足CA,但是在網路發生分割的情況下會全部掛掉,例如單點系統。對任何至少跟causal consistency一樣強,且包含了任何對容許過時資料的界限(Δ-atomicity)的一致性來說,CAP理論都已經被證明適用。與交易隔離的正確性評估一樣的序列性並不是強一致性的要求,然而,跟一致性相似的是,在網路發生分割的情況下,序列化也可以是做不到的事。

對NoSQL分類AP、CP或CA約略的反映了它們個體的能力,也因此在高階比較時,這是廣泛被接受的做法。然而,必須強調的是,CAP理論並沒有敘述任何關於一般操作的事情,它僅告訴我們,一個系統在面對網路被分割時,是偏向可用性還是一致性。相對於FLP理論,CAP理論假設了一個允許丟棄、重新排序、無限延遲任意訊息的失敗模型。在較弱的可信賴通訊頻道(訊息永遠會到達但是可能是非同步或是有重排過)前提下,CAP系統其實很可能是基於 Attiya, Bar-Noy, Dolev algorithm,一直到大部份的節點都上線。所以,在許多NoSQL系統上,用來協調的一致化要嘛是原生的(例如 Megastore)或是透過像Chubby的協調服務。比起強一致性來說, Zookeeper要滿足高可用性是更困難的,參見 FLP Theorem

PACELC. 在Daniel Abadi的文章中,敘述了CAP理論不足的地方。他指出,CAP理論沒有處理到一般操作的延遲與一致性的取捨,即使在發生失敗的情境中,分散式系統的設計比可用性-一致性的取捨要來得更重要。Daniel設計了PACELC來統一這些取捨,因此可以更準確的描述分散式系統的設計。從PACELC,我們學到什麼?「in case of a Partition, there is an Availability-Consistency trade-off; Else, i.e. in normal operation, there is a Latency-Consistency trade-off」,在面對分割時,會有可用性與一致性的取捨,在一般操作上,則是延遲與一致性的取捨。

PACELC的分類方法基本上提供了分割情境(A/C)與一般操作(L/C)的選擇,所以會比CAP理論要來得更細一些。然而,許多系統並不能明確被分到PACELC的一個類別,而PACELC的四個類別,稱為PC/EL,也很難被指派給一個系統。

3. 技術

每個明顯取得成功的資料庫都是為了特定類別的應用程式設計的,或是為了滿足特定的系統性質而設計的。為什麼會有那麼多不同的資料庫系統的原因,是因為沒有一個系統可以同時滿足那麼多種需求。傳統的SQL資料庫,像是PostgreSQL,被建立來提供許多功能:非常有彈性的資料模型、複雜的查詢能力像是join、全域整合性限制與交易保證。在設計光譜的另一端,有像Dynamo這樣的key-value儲存,可以處理大量資料與要求,提供很高的讀寫流量,同時滿足低延遲,但是除了簡單的查表外,幾乎沒有什麼其它功能。

在這一節,我們強調分散式資料庫的設計,重點放在sharding、replication、storage management與query processing。我們調查了資料管理系統對於不同的功能或是特性所使用的技術,並加以討論。為了表示哪些技術對達到哪些特性是可行的,我們做了NoSQL Toolbox,如Figure 4,其中每個技術都連接到某個功能或是特性。

Figure 4: NoSQL Toolbox: 包含許多NoSQL資料庫針對需求的功能與非功能性的特性所支援的技術

3.1 Sharding,切片

像是Oracle RAC或IBM DB2 pureScale等分散式資料庫都依靠shared-disk架構,也就是所有的資料庫節點都會存取同一個中央資料儲存體(例如用NAS或SAN)。因此,這些系統在任何時間都能提供一致性的資料,但是也難以擴增。相對的,在這篇文章中所講的NoSQL資料庫都是基於shared-nothing架構,也就是每個系統都包含了一堆伺服器,這些伺服器各自的記憶體、磁碟,並且以網路相連。所以呢,流量與資料量的高擴充性是透過不同節點(稱為shards)的資料sharding(或稱分割)來達成。有三個基本的分散式技術:range-sharding、hash-sharding與entity-group sharding。range-sharding是讓資料可以用排序與連續值區間來分割資料,增進掃瞄的效率。然而,range-sharding需要一個master來協調作業,為了確保靈活度,系統需要去自動偵測解析熱點並進一步將過載的節點做切割。 BigTable、HBase、Hypertable之類的Wide-column stores,或是MongoDB、RethinkDB、Espresso 與 DocumentDB 之類的文件儲存,都支援range-sharding。

另一種切割的方法是hash-sharding,每個資料都依它主鍵的雜湊值來指派到一個shard server。若是使用的雜湊函式能產生均勻分佈的結果,這種切割方法可以讓資料均勻分部到不同shards中,而且不需要協調作業的master角色。而這個機制的明顯缺點就是,這樣會變成只能做查表,沒辦法做掃瞄。Hash-sharding主要是用在key-value儲存,但也可以用在某些Wide-column stores,像是Cassandra 或 Azure Tables。對一筆記錄來說,對應的shard server可以用像是 serverid = hash(id)%servers 這樣的方法來取得。但是這種計算方法,在有新的伺服器加入或移除的時候,會導致全部資料都要重算一遍,也因此無法用在一些有彈性的系統,像是Dynamo、Riak或Cassandra,因為它們允許視需求新增資源,也允許在不需求資源時做移除。為了增加機動性,那些有彈性的系統通常會用 consistent hashing,資料不會直接被指派到伺服器去,而是指派到一個邏輯區塊,這個區塊再分散到全部的shade伺服器去。當系統拓樸改變時,只有一部份的資料需要重新指派。舉例來看,一個系統要縮減大小時,可以卸載特定伺服器A上面的全部邏輯區塊,把區塊搬到其它伺服器,然後把這個伺服器A給關機。想要了解consistent hashing在NoSQL上的細節,可參見 Dynamo 文獻。

Entity-group sharding 是為了達到co-located資料在單一區塊交易的資料分割方法。分割被稱為entity-groups,可以是明確由應用程式宣告的(例如在 G-Store 與 MegaStore 之中),或是由交易的存取樣式衍生出來(例如Relational Cloud 與 Cloud SQL Server)。如果一個交易在多於一個group上面進行存取,資料的所有權可以在entity-group之間做轉移,又或者,交易管理員可以退而使用昂貴的多節點交易協定。

3.2 複本,Replication

就CAP來看,傳統RDBMS通常都是單伺服器模式的CA系統:機器掛掉就全系統一起死。也因此系統操作者會用昂貴但可靠的高級硬體來保全資料完整性與系統可用性。相對的,NoSQL系統,像是Dynamo、BigTable或Cassandra,一開始設計的目標資料與要求的數量,就不是單一機器所能負荷的,所以他們通常是跑在數千台機器所組成的cluster上,而且這些機器通常會比較低階,比較便宜。既然失敗無法避免而且在巨型分散式系統上還會常常失敗,系統必須每天對抗這種狀況。2009年,Google的Jeff Dean敘述了Google裡面一個典型的新型叢集系統在第一年面對數千硬碟故障、1000個機器故障、20個機櫃故障、數個網路因預期與非預期狀況斷線的故事。近期也有許多大型雲端中心發生網路故障斷線的報告。複本可以讓系統在這些錯誤中維持可用性與持續性。然而,在叢集的不同機器(複本伺服器)上儲存相同的資料,會導致機器間的同步問題,而且也需要在一致性與延遲與可用性之間做取捨。

Gray 等人 基於資料更新的傳遞時間(何時)與資料更新被接受的位置(何地),對不同的複本策略提出了一個兩層式分類法。在第一層(何時),有兩個選項:Eager(同步)複本策略會在回傳給客戶commit之前,同步的將改變傳遞到所有的複本去。而Lazy(非同步)則是只有在收到與傳送複本時才做更新。Eager的最大優點是資料在複本之間的一致性,但是會有較高的寫入延遲,因為要等每一個複本都寫入結束,而這也會影響到可用性。Lazy的速度會比較快,因為它允許複本長得不一樣,結果是舊資料可能仍然在裡面。在第二層(何地),也有兩個選擇:master-slave(主拷貝)是只能被一個master複本接受寫入,update anywhere(多master)則是每一個複本都能接受寫入。在master-slave協定中,同步控制跟沒有複本的分散式系統比起來,沒有比較複雜,但是一旦master掛掉,全部的複本都不能用了。多master協定需要比較複雜的機制來避免與偵測並調停多個改變所引發的衝突。常使用的技術包括了versioning、vector clocks、gossiping and read repair (如 Dynamo 所用的)與convergent or commutative datatypes (例如Riak)。

基本上,這兩層式分類的四種排列組合都是可行的。分散式的關聯式系統通常採用eager master-slave來保持強一致性。Google的Megastore用了Eager update anywhere則是遭受同步所產生的大量額外通訊負擔,而且會引發分散死結,而且偵測死結是很耗成本的。NoSQL資料庫通常會用lazy複本策略,搭配master-slave (CP型的,像是HBase與MongoDB)或是update anywhere (AP型的,像是Dynamo與Cassandra)。許多NoSQL系統讓客戶去決定要延遲還是一致性,在每次要求時,客戶端決定要等任意複本回應來滿足最小延遲,或是等大部份的複本回應(或是由master回應)來確保某個程度的一致性並避免過期的資料。

有個複本的東西並沒有被這個兩層式分類法提到,就是複本之間的距離。兩個複本離很近,當然會有低延遲的優點,但是放很近也可能對可用性造成影響,例如,兩個複本放同一個機櫃,機櫃故障時,兩個複本都沒用了。比起暫時不可用來看,複本放很近相當於冒天災時資料全部不見的風險。Orestes使用了一個縮減延遲的替代方案,用web caching架構與快取一致性協定的技術將資料快取到離應用程式近一點的地方。

Geo-replication可以保護系統避免資料全部不見,也可以降低客戶分散式存取的延遲。Eager geo-replication,就像MegastoreSpannerMDCC 與 Mencius所實作的,達到了強一致性但是代價是高寫入延遲(通常是100ms到600ms)。Dynamo、PNUTSWalterCOPS、Cassandra 與 BigTable用的lazy geo-replication則是可能會遺失最近的改變,但系統效能佳,網路斷掉也有一定的可用性。 Charron-Bost et al. (Chapter 12)Öszu and Valduriez (Chapter 13) 提出了關於資料庫複本的易懂討論。

3.3 儲存管理

為了達到最佳效能,資料庫系統需要為他們所使用的儲存媒體做最佳化。儲存媒體主要是RAM、SSD與HDD。跟RDBMS在企業裡的設定不同,分散式NoSQL資料庫避免了特定的shared-disk架構而是用一般的伺服器(用一般的儲存媒體)來走shared-nothing叢集。儲存裝置通常會用儲存金字塔來看(如 Figure 5 或 Hellerstein 等人的文章)。其它還有透通快取(例如L1到L3的CPU快取與磁碟緩衝區),只有設計良好的資料庫演算法善用資料區域性時可以好好利用到。RAM、SSD與HDD的成本與效能差異很大,加上不同的儲存媒體使用策略,是NoSQL資料庫為什麼差異那麼大的理由之一。儲存管理具有空間維度(資料存哪裡)與時間維度(什麼時候存)。Update-in-place與append-only-IO是組織資料時,兩個互補的空間維度技術。In-memory指示了以RAM做為儲存地點,而logging則是分離主記憶體與永久儲存體的時間維度技術,提供了資料最終儲存地點的控制。

Figure 5: 儲存金字塔與它們在NoSQL系統中的角色

Stonebraker等人在他們的論文 “the end of an architectural era”中,發現到典型的RDBMS只有6.8%的執行時間是用在”有用的工作”,其它的則是:

  • 緩衝管理 (34.6%),像是做快取以減少慢速磁碟的存取
  • 門鎖(latching) (14.2%),在多執行緒環境中用來在race conditions情況下保護shared資料結構
  • 隔離鎖(locking) (16.3%),保證交易時的邏輯隔離
  • logging (1.9%),在失敗時確保持續性
  • hand-coded optimizations (16.2%)

這個發現引發了使用RAM來當主儲存體(in-memory databases)的大量效能優化技術。缺點則是儲存的成本變高,而且持續性變差-電源瞬斷就可以把資料庫搞掛。這些問題有兩種方向可以解決:複製n個in-memory server節點的狀態,來避免n-1個節點失敗(例如 HStore與VoltDB的作法),或是在持續性儲存媒體上做logging(例如Redis或SAP Hana的作法)。透過logging,隨機寫入的存取模式可以被轉換成一個將收到的操作與它們的屬性(例如redo的資訊)組合在一起的序列。對大部份的NoSQL來說,logging的commit rule是確認的,每個確認成功的寫入操作都會被log,而且這個log會被存入永久儲存裝置中。為了避免對每個操作做logging所引發的HDD旋轉延遲,log的記錄動作可以用批次的,這樣雖然會稍微拉高單獨寫入的延遲,但是卻會大幅增進流量。

SSD與其它基於NAND快閃記憶體的儲存裝置,跟HDD有本質上的差異:(1)非對稱的讀寫速度,(2)非in-place覆寫,也就是整個區塊在被該區塊的任意page覆寫之前,必須被抹除,(3)有限的程式/抹除次數 (Min et al., 2012)。因此,資料庫系統的儲存管理不可以將SSD與HDD看成是稍慢的、可永存的RAM,SSD的隨機寫入速度跟循序寫入速度比起來,慢了一個量級呢。另一方面,隨機讀取可說是沒有任何效能上的問題。某些資料庫系統(例如 Oracle Exadata 與 Aerospike)明確的針對SSD的效能特性來設計。對HDD來說,隨機讀寫跟循序讀寫比起來都是10到100倍的慢。因此logging比較適合用在SSD與HDD因為兩者都可在循序寫入達成高流量。

對in-memory資料庫來說,update-in-place存取會是比較理想的,它可以簡化實作,而且隨機RAM寫入在本質上會跟循序寫入一樣快,差在一些pipelining與CPU快取而已。然而,RDBMS與許多NoSQL系統(例如MongoDB)也對永久儲存使用update-in-place。要減輕永久儲存體在隨機存取的緩慢的影響,主記憶體通常用來當成快取,與logging互補來保證持續性。在RDBMS中,要透過複雜的緩衝池來達成,這緩衝池不只是使用cache-replace演算法來處理一般SQL-based存取,也確保ACID語義。NoSQL資料庫的緩衝池比較簡單,因為查詢也比較簡單,而且不用管ACID交易。緩衝池的替代方案是把快取透過虛擬記憶體留給作業系統(例如MongoDB的MMAP儲存引擎的做法)。這樣做會簡化資料庫的架構,但是對於哪些資料或pages放在記憶體,或是他們何時被移除,就比較沒辦法控制。而且,使用OS緩衝來執行read-ahead(預測讀取)與write-behind(緩衝寫入),會沒那麼智慧,因為那些處理的邏輯是基於檔案系統而不是資料庫查詢。

Append-only儲存(也被稱為log-structuring)是將寫入循序化來達成流量最大化。雖然log-structured檔案系統具有悠久的研究歷史,append-only I/O卻是近期才因為BigTable使用Log-Structured-Merge (LSM)才流行的。LSM 樹包含了一個in-memory快取、一個永存log與一些不可變且間歇性寫入儲存的檔案。LSM樹與它的變種,像是Sorted Array Merge Trees (SAMT)與Cache-Oblivious Look-ahead Arrays (COLA),都被應用在許多NoSQL資料庫裡面(Cassandra、CouchDB、LevelDB、Bitcask、RethinkDB、WiredTiger、RocksDB、InfluxDB、TokuDB)。透過永遠寫入一個log來設計一個可以達到最大寫入效能的資料庫系統是簡單的,困難的地方是在提供快速的隨機與循序讀取。這需要一個合適的索引結構,這結構要嘛是永遠在寫入時做更新(copy-on-write資料結構,COW,例如CouchDB的COW B-trees)或是不變動的資料結構(如BigTable-style系統)。所有log-structured儲存方法都有一個問題,就是對於更新或刪除資料後的空間回收機制成本很高。

在虛擬環境中,像是IaaS雲端環境,許多剛才討論的儲存特質都是隱藏起來的。

Table 1: 以NoSQL Toolbox針對MongoDB、Redis、HBase、Riak、Cassandra與MySQL進行功能性與非功能性的需求與技術比較

3.4 查詢處理

NoSQL資料庫的查詢能力主要是依據它的分散式模型、一致性保證與資料模型。每個NoSQL系統都支援Primary key lookup,也就是以唯一ID來擷取資料,因為這方法與區域或是雜湊分割都相容。Filter queries會從一個表格中傳回符合指定性質的資料項目。在最簡單的型式中,他們可以執行過濾全表格掃瞄。對雜湊分割的資料庫來說,這陰含了scatter-gather樣式,每個分割都要執行同樣的掃瞄,最後把結果合併起來。對區域分割型的系統來說,可以使用任何區域屬性條件去選擇分割。

可以使用第二階索引來解決掃瞄時間複雜度是O(n)的低效率。第二階索引可以是每個分割自己管理的local第二階索引,也可以是對全部分割做索引的global第二階索引。global第二階索引必須分散到各個分割,維護一致的第二階索引會迫使緩慢且可能無法使用的commit協議。所以在實作上,大部份系統僅對索引提供最終一致性(例如Megastore、Google AppEngine Datastore、DynamoDB),或是乾脆不支援 (例如 HBase與 Azure Tables)。在對local第二階索引執行全域查詢時,若是查詢條件與分割規則有交集,查詢的目標只能鎖定在分割的一個子集合。否則,查詢結果就必須透過scatter-gather來得到。舉個例子來看,一個使用者表格,年齡欄位使用了區域分割,則它可以處理一個分割裡的年齡相等性查詢,同時,查詢名字時必須在每個分割上面做計算。全文搜尋是global第二階索引的一個特例,選定的欄位或整個資料項目會被塞進資料庫內部的inverted index(MongoDB的作法),或是塞到外部的搜尋平台,像是ElasticSearch或是Solr(Riak Search、DataStax Cassandra的作法)。

Query planning是為了最小化執行成本而對查詢做最佳化。對於聚合與合併查詢,做查詢規畫是必要的,因為這種查詢很慢而且很難在應用程式實作。目前的NoSQL對於關聯式查詢處理的豐富文獻通常都沒在管,理由有兩個。第一,key-value與Wide-column stores是以CRUD為中心,以主鍵做掃瞄操作,所以沒什麼東西可以最佳化。第二,分散式查詢處理的大部份工作都專注在OLAP (online analytical processing),跟延遲比起來,比較重視流量,同時,單一節點的查詢最佳化不容易在分割且有複本的資料庫裡實作。然而,如何一般化可行的查詢最佳化技術,也變成一個開放的研究挑戰,尤其是在文件型資料庫。(目前只有RethinkDB可以執行一般的 Θ-joins,MongoDB的聚合框架支援left-outer equi-join,CouchDB允許對pre-declared map-reduce views做join)。

In-database analytics 可以以原生方式執行(例如MongoDB、Riak與CouchDB)也可以透過外部分析平台像是Hadoop、Spark與Flink(例如Cassandra與HBase)。NoSQL所普遍使用的原生批次分析是 MapReduce。(MapReduce的替代方案是一般化的資料處理管線(data processing pipelines),也就是資料庫基於更富宣告性的查詢語言去對資料的流向與計算的地域性去做最佳化,例如MongoDB的aggregation框架)。因為I/O、通訊的額外成本與有限的執行計畫最佳化,這些批次或是微批次導向(micro-batch-oriented)方法都需要很高的回應時間。Materialized views 是一種低查詢回應時間的替代方案。他們在設計時期就先宣告,在後續操作時若有改變就進行更新(例如CouchDB與Cassandra)。然而,跟global第二階索引的問題一樣,在分散式環境下,view的一致性通常會在偏向快速、寫入的高可用性時降低。只有少數資料庫系統有實作內建支援無限制資料串流,near-real-time analytics通常會以 Lambda ArchitectureKappa Architecture來實作:Lambda Architecture用串流串理(像是Storm,可參考 Summingbird)補足了批次處理框架(像是Hadoop MapReduce),而Kappa Architecture則是特別依靠串流處理而放棄了批次處理。

4. System Case Studies

在這一節,我們對傑出的key-value、document與wide-column儲存提供性質的比較。我們所呈現的結果是大幅濃縮的,細節留給各個系統的文件去說明。NoSQL Toolbox(參見Figure 4)用來以三個維度抽象分類資料庫系統:功能需求、非功能需求、使用的技術。這種分類方法可以將資料庫做良好的分類,並可以用來凸顯它們的對比。Table 1顯示了MongoDB、Redis、HBase、Riak、Cassandra與MySQL在使用預設值時的直接比較結果。放在文末的Table 2則是比較多說明的系統性質比較。

用來驗證這些系統性質的方法,包含了公開文件的in-depth分析與其它系統文獻。另外,有些性質是必須要去研究原始碼才能評估,有些是以個人名義與開發者得到,有些則是報告的meta-analysis與某些人實作的benchmark。

可以參考我們寫的ICDE 2016 Tutorial投影片,裡面會提到很多不同NoSQL系統的細節。

比較結果闡明了SQL跟NoSQL在設計上如何去滿足不同的需求:RDBMS在功能面提供的程式是NoSQL無法企及的,但NoSQL在非功能方面,例如擴充性、可用性、低延遲與高流量,則是有相當優異的表現。然而,NoSQL之中還是有很大的差異。例如Riak與Cassandra,可以設定來滿足很多非功能需求,但只能做到最終一致性,而且除了資料分析之外,許多功能都不支援,不過Cassandra倒還另外支援條件式更新。另一方面,MongoDB與HBase提供了強一致性與更多精明的功能,像是掃瞄查詢,MongoDB還特別有filter查詢,但是他們在網路斷線時並不維護讀寫可用性,而且讀取的延遲偏高。Redis,在這個比較中除了MySQL之外的唯一非分割系統,表現了獨特的取捨,使用in-memory資料結構與非同步主從複本機制來達到超高流量與低延遲。

Figure 6: 從需求對應到NoSQL資料庫系統的決策樹

5. 結論

選擇一個資料庫系統往往等同於從一堆特性中選擇出你想要的。為了簡化這種選擇的複雜,我們呈現了二元決策樹在Figure 6,將取捨決策對應到範例應用程式與可能合適的資料庫系統。樹葉節點的應用程式包含了從最左邊的簡單快取到最右邊的大數據分析。當然這個視角並不完備,但是它約略地指出了特定資料管理問題的解決方案。

這決策樹最開始的分支是應用程式的存取樣式:依賴快速查表(左半邊)或是需要複雜的查詢能力(右半邊)。快速查表型的應用程式可以進一步用資料量來區分:如果單一機器的記憶體大到可以包含全部資料,一個單節點系統,例如Redis或Memcache可能是最好的選擇,看你是要功能(Redis)或是簡單性(Memcache)。如果資料量會大過RAM的大小,甚至是沒有極限的,可以水平擴展的多節點系統會比較合適。最重要的決策是要選擇可用性(AP)還是一致性(CP),一如CAP理論所述。Cassandra與Riak可以做到Always-on,而HBase、MongoDB與DynamoDB則是有強一致性。

決策樹的右半部包含了需要複雜查詢的應用程式。所以,我們首先一樣以要處理的資料量來做分隔,依據的是單節點系統(HDD大小)夠不夠用,或是需要分散式(無限大小)。對於大資料量常用的OLTP,傳統的RDBMS或圖資料庫像是Neo4J都很好用,因為他們提供了ACID。然而,如果可用性才是重點,MongoDB、CouchDB或DocumentDB這類的分散式系統會比較適合。

如果資料量超過單一機器的極限,從右邊的系統做選擇就要靠常用的查詢樣式:當複雜的查詢必須要為了延遲而進行最佳化,例如社群網路的應用,MongoDB是很有吸引力的,因為它利用了expressive ad-hoc查詢。HBase與Cassandra在同樣情境中也很有用,但是在與Hadoop合併對流量最佳化的大數據分析會更好。

總結來說,我們相信我們基於重點需求提出的由上而下模型,對於過濾大量NoSQL資料庫來說,是個有效的決策支援。NoSQL Toolbox進一步的提供了從功能性與非功能性到常見實作技術的對應,可對持續演化的NoSQL系統提供了分類。

Table 2: MongoDB、HBase、Cassandra、Riak與Redis資料庫在性質的比較

Don’t want to miss our next post on NoSQL topics? Get it conveniently delivered to your inbox by joining our newsletter.

Leave a Reply

你的電子郵件位址並不會被公開。 必要欄位標記為 *