內(nèi)存數(shù)據(jù)庫究竟是如何發(fā)揮內(nèi)存優(yōu)勢的？

文章目錄

前言

一、指針式復(fù)用

1、指針

2、RDD

3、返回指針

二、外鍵預(yù)關(guān)聯(lián)

1、外鍵關(guān)聯(lián)

2、指針引用

3、預(yù)關(guān)聯(lián)

三、序號定位

1、序號

2、索引

3、序號定位

四、集群維表

1、集群

2、JOIN

3、分布式數(shù)據(jù)庫

4、外鍵關(guān)聯(lián)

五、回顧與總結(jié)

七、SPL

前言

與以磁盤存儲(chǔ)為主的普通數(shù)據(jù)庫相比，內(nèi)存數(shù)據(jù)庫的數(shù)據(jù)訪問速度可以高出幾個(gè)數(shù)量級，能大幅提高運(yùn)算性能，更適合高并發(fā)、低延時(shí)的業(yè)務(wù)場景。

不過，當(dāng)前大部分內(nèi)存數(shù)據(jù)庫仍然采用 SQL 模型，而 SQL 缺乏一些必要的數(shù)據(jù)類型和運(yùn)算，不能充分利用內(nèi)存的特征實(shí)現(xiàn)某些高性能算法。僅僅是把外存的數(shù)據(jù)和運(yùn)算簡單地搬進(jìn)內(nèi)存，固然也能獲得比外存好得多的性能，但還沒有充分利用內(nèi)存特征，也就不能獲得極致的性能。

下面我們來看看，有哪些適合內(nèi)存特征的算法和存儲(chǔ)機(jī)制，可以進(jìn)一步提升內(nèi)存數(shù)據(jù)庫計(jì)算速度。

一、指針式復(fù)用

1、指針

我們知道，內(nèi)存可以通過地址（指針）來訪問。但 SQL 沒有用內(nèi)存指針表示的數(shù)據(jù)對象，在返回結(jié)果集時(shí)，通常要把數(shù)據(jù)復(fù)制一份，形成一個(gè)新的數(shù)據(jù)表。這樣不僅多消耗 CPU 時(shí)間（用于復(fù)制數(shù)據(jù)）而且還會(huì)占用更多昂貴的內(nèi)存空間（用于存儲(chǔ)復(fù)制的數(shù)據(jù)），降低內(nèi)存使用率。

2、RDD

除了 SQL 型的內(nèi)存數(shù)據(jù)庫外，Spark 中的 RDD 也有這個(gè)問題，而且情況更嚴(yán)重。為了保持 RDD 的 immutable 特性，Spark 在每個(gè)計(jì)算步驟后都會(huì)復(fù)制出新的 RDD，造成內(nèi)存和 CPU 的大量浪費(fèi)。所以，即使耗用了巨大資源，Spark 也仍然做不到高性能。相比之下，SQL 型的內(nèi)存數(shù)據(jù)庫通常還會(huì)優(yōu)化，在 SQL 語句中的計(jì)算會(huì)盡量使用內(nèi)存地址，通常要比 Spark 的性能更好。

但是，受到理論限制，實(shí)現(xiàn) SQL 的邏輯時(shí)，返回的結(jié)果集就必須復(fù)制了。如果涉及多步驟的過程運(yùn)算，要多次在上一步的結(jié)果集（臨時(shí)表）基礎(chǔ)上進(jìn)一步計(jì)算，SQL 的劣勢就會(huì)很明顯了。

3、返回指針

事實(shí)上，如果沒有改變數(shù)據(jù)結(jié)構(gòu)，我們可以直接用原數(shù)據(jù)的地址形成結(jié)果集，不需要復(fù)制數(shù)據(jù)本身，僅僅多保存一個(gè)地址（指針），同時(shí)減少 CPU 和內(nèi)存的消耗。

SPL 擴(kuò)展了 SQL 的數(shù)據(jù)類型，支持這種指針式復(fù)用機(jī)制。比如，對訂單表按照訂單日期（odate）范圍過濾后，分別求出訂單金額（amount1）大于 1000 和運(yùn)貨費(fèi)（amount2）大于 1000 的訂單，再計(jì)算出兩者的交集、并集和差集，最后將差集按照客戶號（cid）排序。SPL 代碼大致是這樣：

以上代碼中有好幾個(gè)步驟，有的中間結(jié)果也被用了多次，但由于使用的都是訂單表記錄的指針，所以內(nèi)存占用增加的很少，也避免了記錄復(fù)制的耗時(shí)。

二、外鍵預(yù)關(guān)聯(lián)

1、外鍵關(guān)聯(lián)

外鍵關(guān)聯(lián)是指用一個(gè)表（事實(shí)表）的非主鍵字段，去關(guān)聯(lián)另一個(gè)表（維表）的主鍵。比如訂單表中的客戶號和產(chǎn)品號分別關(guān)聯(lián)客戶表、產(chǎn)品表的主鍵。現(xiàn)實(shí)運(yùn)算中這種關(guān)聯(lián)可能多達(dá)七八個(gè)甚至十幾個(gè)表，還可能出現(xiàn)多層的關(guān)聯(lián)。SQL 數(shù)據(jù)庫通常使用 HASH JOIN 算法來做內(nèi)存連接，需要計(jì)算和比對 HASH 值，過程中還會(huì)占用內(nèi)存來存儲(chǔ)中間結(jié)果，關(guān)聯(lián)表很多時(shí)計(jì)算性能就會(huì)急劇下降。

2、指針引用

其實(shí)，我們也可以利用內(nèi)存指針引用機(jī)制事先做好關(guān)聯(lián)。在系統(tǒng)初始化階段，把事實(shí)表中的關(guān)聯(lián)字段值轉(zhuǎn)換為對應(yīng)維表記錄的指針。因?yàn)榫S表的關(guān)聯(lián)字段是主鍵，所以關(guān)聯(lián)記錄唯一，將外鍵值轉(zhuǎn)換成記錄指針不會(huì)引起錯(cuò)誤。在后續(xù)計(jì)算中，需要引用維表字段時(shí)，可以用指針直接引用，無需計(jì)算和比對 HASH 值，也不需要再存儲(chǔ)中間結(jié)果，從而獲得更優(yōu)的性能。SQL 沒有記錄指針這種數(shù)據(jù)類型，也就無法實(shí)現(xiàn)預(yù)關(guān)聯(lián)了。

3、預(yù)關(guān)聯(lián)

SPL 則從原理上支持并實(shí)現(xiàn)了這種預(yù)關(guān)聯(lián)機(jī)制。例如，完成訂單表和客戶表、產(chǎn)品表預(yù)關(guān)聯(lián)的代碼大致是這樣：

A1、A2 加載客戶表和產(chǎn)品表。

A3：加載訂單表，將其中的客戶號 cid、產(chǎn)品號 pid 轉(zhuǎn)換為對應(yīng)維表記錄的指針。

A4：將完成預(yù)關(guān)聯(lián)的訂單表存入全局變量，供后續(xù)計(jì)算使用。

系統(tǒng)運(yùn)行時(shí)，按照產(chǎn)品供應(yīng)商過濾訂單，再按客戶所在城市分組匯總的代碼大致是下面這樣：

訂單表中的 pid 已經(jīng)轉(zhuǎn)換為產(chǎn)品表記錄的指針，所以可以直接用“.”操作符引用產(chǎn)品表記錄。 不僅書寫更簡單，而且運(yùn)算性能也快得多。

只是兩、三個(gè)表關(guān)聯(lián)時(shí)，預(yù)關(guān)聯(lián)和 HASH JOIN 的差別還不是非常明顯。這是因?yàn)殛P(guān)聯(lián)并不是最終目的，之后還會(huì)有其它很多運(yùn)算，關(guān)聯(lián)本身運(yùn)算消耗時(shí)間的占比相對不大。但如果關(guān)聯(lián)情況比較復(fù)雜，涉及的表很多，以及有多層的時(shí)候（比如訂單關(guān)聯(lián)產(chǎn)品，產(chǎn)品關(guān)聯(lián)供應(yīng)商，供應(yīng)商關(guān)聯(lián)城市，城市關(guān)聯(lián)國家等等），預(yù)關(guān)聯(lián)的性能優(yōu)勢會(huì)更明顯。

三、序號定位

1、序號

與外存相比，內(nèi)存的另一個(gè)重要特征是支持高速的隨機(jī)訪問，可以快速從內(nèi)存表中按指定序號（也就是位置）取出數(shù)據(jù)。在做查找計(jì)算時(shí)，如果被查找的值正好是目標(biāo)值在內(nèi)存表中的序號，或者很容易通過被查找值計(jì)算出目標(biāo)值的序號，我們就可以用序號直接取目標(biāo)記錄。這種方法不需要進(jìn)行任何比對就能直接取出查找結(jié)果，性能不僅遠(yuǎn)遠(yuǎn)好于遍歷查找，也好于使用索引的查找算法。

2、索引

但是，SQL 以無序集合為基礎(chǔ)，不能按序號取成員，只能用序號去查找。如果沒有索引就只能遍歷查找，會(huì)非常慢。即使有索引也要計(jì)算 HASH 值或用二分法查找，速度也比不上直接定位。而且，建立索引也會(huì)占用昂貴的內(nèi)存。如果數(shù)據(jù)表中沒有序號還要先排序再硬造個(gè)序號時(shí)，性能就會(huì)更差。

3、序號定位

SPL 以有序集合為基礎(chǔ)，提供序號定位功能。比如訂單表中的訂單號是從 1 開始的自然數(shù)。在查找訂單號 i 時(shí)，直接取訂單表中的第 i 條記錄就行了。再比如數(shù)據(jù)表 T 從 2000 年到 2022 年每天存儲(chǔ)一條數(shù)據(jù)，現(xiàn)在需要查詢指定日期的記錄。日期雖然不是目標(biāo)值的序號，但是我們可以先算出指定日期距離起始日期的天數(shù)。這就是目標(biāo)值的序號，然后再用序號取 T 表記錄就可以了。對表 T 用序號定位查找 2022 年 4 月 20 日記錄的代碼，大致是下面這樣：

A

1 ? ?=date(2022,12,31)-date(1999,12,31)

2 ? ?=T_orginal.align@b(to(A1),dt-date(1999,12,31))

3 ? ?=env(T,A5)

4 ? ?=T(date(2021,4,20)-date(1999,12,31))

A1：計(jì)算出 2000 年到 2022 年總天數(shù)是 8401 天。

A2：用原始的 T 表記錄計(jì)算出距離起始日期的天數(shù)，再和 to(A1)這個(gè)自然數(shù)集合 [1,2,3,…,8401] 對齊，空缺的日期會(huì)用 null 補(bǔ)齊。align 的 @b 選項(xiàng)表示對齊時(shí)將使用二分法來查找位置，這樣完成對齊動(dòng)作也會(huì)更快一點(diǎn)。

A3：計(jì)算好的結(jié)果，放到全局變量 T 中。

A4：要查找 2021 年 4 月 20 日記錄，求出這個(gè)日期和起始日期距離 7781 天，直接取出 T 表中第 7781 條記錄就可以了。

A1 到 A3 是對齊計(jì)算，用于處理空缺的日期，可以放在系統(tǒng)初始化階段。在查找計(jì)算時(shí)，用 A4 中的序號定位代碼就能得到查找結(jié)果，實(shí)際查找的日期可以作為參數(shù)傳入。

四、集群維表

1、集群

當(dāng)數(shù)據(jù)量太大，超出單機(jī)內(nèi)存時(shí)，就要使用集群來加載這些數(shù)據(jù)。許多內(nèi)存數(shù)據(jù)庫也支持分布式計(jì)算，通常是將數(shù)據(jù)分成多段，分別加載到集群不同分機(jī)的內(nèi)存中。

2、JOIN

JOIN 是分布式計(jì)算的一個(gè)麻煩任務(wù)，會(huì)涉及多個(gè)分機(jī)之間的數(shù)據(jù)傳輸。嚴(yán)重的時(shí)候，傳輸造成的延遲會(huì)抵消集群分?jǐn)傆?jì)算量得到的好處，會(huì)出現(xiàn)集群變大反而性能并不能提升的現(xiàn)象。

3、分布式數(shù)據(jù)庫

SQL 體系下的分布式數(shù)據(jù)庫，通常是將單機(jī) HASH JOIN 方法擴(kuò)展到集群上。每個(gè)分機(jī)根據(jù) HASH 值將本機(jī)數(shù)據(jù)分發(fā)到其他分機(jī)，確保相關(guān)聯(lián)的數(shù)據(jù)在同一分機(jī)上。然后再在各個(gè)分機(jī)上做單機(jī)連接。但是，HASH 方法在運(yùn)氣不好的時(shí)候，可能會(huì)造成數(shù)據(jù)分配的嚴(yán)重不均衡，需要借助外存來緩存這些分發(fā)到的數(shù)據(jù)，否則可能因?yàn)閮?nèi)存溢出而導(dǎo)致系統(tǒng)崩潰。但是，內(nèi)存數(shù)據(jù)庫的主要特征就是將數(shù)據(jù)加載到內(nèi)存中計(jì)算，出現(xiàn)外存緩存會(huì)嚴(yán)重拖慢計(jì)算性能。

4、外鍵關(guān)聯(lián)

實(shí)際上，外鍵關(guān)聯(lián)的事實(shí)表和維表有很大區(qū)別。事實(shí)表一般都比較大，要用各個(gè)分機(jī)內(nèi)存分段加載才能裝的下。正好事實(shí)表也比較適合分段，每個(gè)分段的數(shù)據(jù)都相互獨(dú)立，分機(jī)之間不需要相互訪問。而維表記錄則會(huì)被隨機(jī)訪問，事實(shí)表的任何一個(gè)分段都可能關(guān)聯(lián)全部維表記錄。我們可以利用事實(shí)表和維表的區(qū)別，對集群的外鍵關(guān)聯(lián)提速。

如果維表比較小，則將維表全量數(shù)據(jù)復(fù)制到所有分機(jī)內(nèi)存中。這樣，每個(gè)分機(jī)中的事實(shí)表分段和全量維表就可以繼續(xù)完成預(yù)關(guān)聯(lián)，完全避免了關(guān)聯(lián)過程中的網(wǎng)絡(luò)傳輸。

如果維表也很大，單機(jī)內(nèi)存放不下，只能在各分機(jī)內(nèi)存中分段加載。這時(shí)，沒有一個(gè)分機(jī)上有全量的維表，外鍵關(guān)聯(lián)計(jì)算就無法避免網(wǎng)絡(luò)傳輸了。不過傳輸內(nèi)容并不算很大，只涉及事實(shí)表的外鍵和維表關(guān)聯(lián)記錄的字段，事實(shí)表其它字段不需要傳輸，計(jì)算可以直接完成，過程中也不會(huì)產(chǎn)生緩存數(shù)據(jù)。

SPL 從原理上區(qū)分維表和事實(shí)表，針對維表較小和維表較大兩種情況，分別提供了維表復(fù)制機(jī)制和分段維表機(jī)制，實(shí)現(xiàn)了上述算法，能顯著提高集群情況下外鍵關(guān)聯(lián)的計(jì)算性能。

五、回顧與總結(jié)

內(nèi)存數(shù)據(jù)庫的計(jì)算體系，必須充分利用內(nèi)存的特征才能獲得極致性能。從數(shù)據(jù)計(jì)算的角度來看，內(nèi)存主要優(yōu)點(diǎn)有：支持指針引用、支持高速隨機(jī)訪問、并發(fā)讀取能力強(qiáng)。內(nèi)存的缺點(diǎn)是：成本高昂、擴(kuò)容有上限。

而 SQL 計(jì)算體系中缺乏一些必要的數(shù)據(jù)類型和運(yùn)算，比如：缺少記錄指針類型，不支持有序運(yùn)算，JOIN 定義過于籠統(tǒng)，不區(qū)分 JOIN 類型等，從原理上就不能充分利用內(nèi)存的上述特征實(shí)現(xiàn)某些高速算法。基于 SQL 的內(nèi)存數(shù)據(jù)庫，通常只是簡單的照搬外存數(shù)據(jù)結(jié)構(gòu)和運(yùn)算，會(huì)出現(xiàn)各種問題。比如：記錄式復(fù)制過多消耗 CPU 和內(nèi)存；查找和 JOIN 性能沒有達(dá)到極致。再比如集群方面：內(nèi)存利用率過低；大量網(wǎng)絡(luò)傳輸導(dǎo)致分機(jī)數(shù)量增加但性能反而下降；多機(jī) JOIN 出現(xiàn)外存緩存等等。

開源數(shù)據(jù)計(jì)算引擎 SPL 擴(kuò)展了數(shù)據(jù)類型和運(yùn)算定義，可以充分利用內(nèi)存的特征，從而實(shí)現(xiàn)多種高性能算法，讓性能達(dá)到極致。其中，指針式復(fù)用利用內(nèi)存特有的指針引用機(jī)制，節(jié)省了內(nèi)存空間，而且速度更快。預(yù)關(guān)聯(lián)同樣利用指針引用機(jī)制，在初始化階段完成很耗時(shí)的外鍵關(guān)聯(lián)，后續(xù)計(jì)算中直接使用關(guān)聯(lián)好的結(jié)果，計(jì)算速度顯著提高。序號定位利用有序性，充分發(fā)揮內(nèi)存高速隨機(jī)訪問的優(yōu)勢，不用做任何計(jì)算和比對，直接用序號讀取記錄，性能好于 HASH 索引等查找算法。集群維表有效避免或減少了網(wǎng)絡(luò)傳輸、避免了外存緩存，備胎式容錯(cuò)在保證高可用性的前提下，有效提高了集群內(nèi)存利用率。

SQL 數(shù)據(jù)庫

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。