你知道如何建立數(shù)據(jù)庫嗎?動態(tài)編程,貪婪算法和啟發(fā)式?大數(shù)據(jù)中數(shù)據(jù)庫又是如何工作的?如果你對大數(shù)據(jù)專業(yè)有濃厚的興趣,那么你可以接著看看以下內容。
優(yōu)化器的真正工作是在有限的時間內找到一個好的解決方案。大多數(shù)情況下,優(yōu)化器找不到最佳解決方案,而是找到“好的”解決方案。對于小的查詢,可以使用蠻力方法。但是有一種方法可以避免不必要的計算,因此即使是中等查詢也可以使用蠻力方法。這稱為動態(tài)編程。
動態(tài)編程:這兩個詞背后的想法是,許多執(zhí)行計劃非常相似。
它們共享相同的(A JOIN B)子樹。因此,與其在每個計劃中都不計算此子樹的成本,我們可以對其進行一次計算,保存計算的成本,并在再次看到此子樹時重新使用它。為了避免對部分結果進行額外的計算,我們使用了記憶。
使用這種技術,而不是(2 * N)!/(N + 1)!時間復雜度,我們“只”有3 ñ。在我們前面的具有4個聯(lián)接中,這意味著從336的順序傳遞到81。如果你通過8個聯(lián)接(不大)進行較大的查詢,則意味著從57 657 600傳遞到6561。
在你已經(jīng)了解動態(tài)編程或對算法精通的情況下才能更好的運用:
procedure findbestplan(S)
if (bestplan[S].cost infinite)
return bestplan[S]
// else bestplan[S] has not been computed earlier, compute it now
if (S contains only 1 relation)
set bestplan[S].plan and bestplan[S].cost based on the best way
of accessing S /* Using selections on S and indices on S */
else for each non-empty subset S1 of S such that S1 != S
P1= findbestplan(S1)
P2= findbestplan(S - S1)
A = best algorithm for joining results of P1 and P2
cost = P1.cost + P2.cost + cost of A
if cost < bestplan[S].cost
bestplan[S].cost = cost
bestplan[S].plan = “execute P1.plan; execute P2.plan;
join results of P1 and P2 using A”
return bestplan[S]
對于更大的查詢,你仍然可以采用動態(tài)編程方法,但是要使用額外的規(guī)則(或啟發(fā)式方法)來消除可能性:
如果僅分析某種類型的計劃(例如,左深樹),則最終得到n * 2 n而不是3 n
如果添加邏輯規(guī)則來避免針對某些模式的計劃(例如“如果表作為給定謂詞的索引,則不要嘗試對表進行合并聯(lián)接,而僅對索引進行嘗試”),它將減少可能性的數(shù)量而不會損害盡可能最好的解決方案。如果我們在流上添加規(guī)則(例如“在所有其他關系操作之前執(zhí)行聯(lián)接操作”),那么它也會減少很多可能性。
對于非常大的查詢或具有非常快的答案(但不是非??斓牟樵?的情況,則使用另一種算法,即貪婪算法。這個想法是遵循規(guī)則(或啟發(fā)式)以增量方式構建查詢計劃。使用此規(guī)則,貪婪算法一次找到一個問題的最佳解決方案。該算法從一個JOIN開始查詢計劃。然后,在每個步驟中,算法都會使用相同的規(guī)則將新的JOIN添加到查詢計劃中。
假設我們有一個查詢,其中包含5個表(A,B,C,D和E)上的4個聯(lián)接。為了簡化問題,我們僅將嵌套聯(lián)接作為可能的聯(lián)接。讓我們使用“使用成本最低的聯(lián)接”規(guī)則。任意從5個表之一開始(讓我們選擇A),用A來計算每次連接的成本(A是內部或外部關系)。會發(fā)現(xiàn)A JOIN B成本最低,然后使用A JOIN B(A JOIN B是內部或外部關系)的結果來計算每個連接的成本,(A JOIN B)JOIN C提供了最佳成本,然后使用(A JOIN B)JOIN C的結果來計算每個聯(lián)接的成本,最后我們找到了計劃((((A JOIN B)JOIN C)JOIN D)JOIN E)。
由于我們從A任意開始,因此我們可以對B,C,D,E都應用相同的算法。然后以最低的成本保留計劃。對于完整的動態(tài)編程版本,該算法的成本為O(N * log(N))對O(3 N)。如果你有20個聯(lián)接的大型查詢,則意味著26 vs 3 486 784 401。
該算法的問題在于,如果我們保持此聯(lián)接并添加新聯(lián)接,則假定在2個表之間找到最佳聯(lián)接將為我們帶來最佳成本。但:即使A JOIN B給出了A,B和C之間的最佳成本,(A JOIN C)JOIN B可能比(A JOIN B)JOIN C更好的結果。為了改善結果,你可以使用不同的規(guī)則運行多種貪婪算法,并保持最佳計劃。
資料管理員
在此步驟中,查詢管理器正在執(zhí)行查詢,并且需要表和索引中的數(shù)據(jù)。它要求數(shù)據(jù)管理器獲取數(shù)據(jù),但是有兩個問題:
關系數(shù)據(jù)庫使用事務模型。因此,你無法隨時獲取任何數(shù)據(jù),因為其他人可能會同時使用/修改數(shù)據(jù)。
數(shù)據(jù)檢索是數(shù)據(jù)庫中最慢的操作,因此數(shù)據(jù)管理器必須足夠聰明才能獲取并將數(shù)據(jù)保留在內存緩沖區(qū)中。
在這一部分中,我們將看到關系數(shù)據(jù)庫如何處理這兩個問題。我不會談論數(shù)據(jù)管理器獲取數(shù)據(jù)的方式,因為它不是最重要的(本文足夠長!)。
緩存管理器
正如我已經(jīng)說過的,數(shù)據(jù)庫的主要瓶頸是磁盤I / O。為了提高性能,現(xiàn)代數(shù)據(jù)庫使用高速緩存管理器。
查詢執(zhí)行程序不是直接從文件系統(tǒng)獲取數(shù)據(jù),而是向高速緩存管理器請求數(shù)據(jù)。高速緩存管理器具有一個稱為緩沖池的內存中高速緩存。從內存中獲取數(shù)據(jù)極大地加快了數(shù)據(jù)庫的速度。很難給出一個數(shù)量級,因為它取決于你需要執(zhí)行的操作:
順序訪問(例如:全面掃描)與隨機訪問(例如:按行ID進行訪問);讀與寫;數(shù)據(jù)庫使用的磁盤類型:7.2k / 10k / 15k rpm硬盤,固態(tài)硬盤,RAID 1/5 /…內存比磁盤快100到10萬倍會導致另一個問題。高速緩存管理器需要在查詢執(zhí)行程序使用它們之前獲取內存中的數(shù)據(jù)。否則查詢管理器必須等待慢速磁盤中的數(shù)據(jù)。此問題稱為預取。查詢執(zhí)行器知道它需要的數(shù)據(jù),因為它知道查詢的全部流程,并且知道具有統(tǒng)計信息的磁盤上的數(shù)據(jù)。
當查詢執(zhí)行程序正在處理其第一堆數(shù)據(jù)時,它要求緩存管理器預加載第二組數(shù)據(jù),當它開始處理第二組數(shù)據(jù)時,它要求CM預加載第三束,并通知CM可以從緩存中清除第一束。CM將所有這些數(shù)據(jù)存儲在其緩沖池中。為了知道是否仍然需要數(shù)據(jù),緩存管理器添加了有關緩存數(shù)據(jù)的額外信息(稱為閂鎖)。
有時查詢執(zhí)行器不知道需要什么數(shù)據(jù),而某些數(shù)據(jù)庫不提供此功能。取而代之的是,他們使用推測性預取或順序預取。為了監(jiān)視預取的工作狀況,現(xiàn)代數(shù)據(jù)庫提供了一個稱為“緩沖區(qū)/緩存命中率”的指標。命中率顯示在不要求磁盤訪問的情況下在緩沖區(qū)高速緩存中找到請求數(shù)據(jù)的頻率。
但是,緩沖區(qū)是有限的內存量。因此,它需要刪除一些數(shù)據(jù)才能加載新數(shù)據(jù)。加載和清除緩存在磁盤和網(wǎng)絡I / O方面要付出一定的代價。如果你有一個經(jīng)常執(zhí)行的查詢,則始終加載然后清除此查詢使用的數(shù)據(jù)并不是很有效。為了解決此問題,現(xiàn)代數(shù)據(jù)庫使用緩沖區(qū)替換策略。
緩沖區(qū)替換策略
大多數(shù)現(xiàn)代數(shù)據(jù)庫(至少是SQL Server,MySQL,Oracle和DB2)都使用LRU算法。
LRU
LRU代表大號東- [R ecently ü sed的。該算法的思想是將最近使用過的數(shù)據(jù)保存在緩存中,因此更有可能再次使用。
這是一個視覺示例:
在這個簡單的示例中,緩沖區(qū)可以存儲3個元素:
1:緩存管理器使用數(shù)據(jù)1并將數(shù)據(jù)放入空緩沖區(qū)
2:CM使用數(shù)據(jù)4并將數(shù)據(jù)放入半裝入的緩沖區(qū)
3:CM使用數(shù)據(jù)3并將數(shù)據(jù)放入半載緩沖區(qū)
4:CM使用數(shù)據(jù)9。緩沖區(qū)已滿,因此數(shù)據(jù)1被刪除, 因為它是最近使用的數(shù)據(jù)。數(shù)據(jù)9被添加到緩沖區(qū)中
5:CM使用數(shù)據(jù)4。數(shù)據(jù)4已在緩沖區(qū)中,因此它再次成為最近使用的第一個數(shù)據(jù)。
6:CM使用數(shù)據(jù)1。緩沖區(qū)已滿,因此數(shù)據(jù)9被刪除, 因為它是最近使用的數(shù)據(jù)。數(shù)據(jù)1被添加到緩沖區(qū)
…
該算法效果很好,但存在一些局限性。如果在一張大桌子上進行全面掃描怎么辦?換句話說,當表/索引的大小大于緩沖區(qū)的大小時會發(fā)生什么?使用此算法將刪除高速緩存中的所有先前值,而完全掃描中的數(shù)據(jù)可能僅使用一次。
權重是使用數(shù)據(jù)的次數(shù),如果將一堆新數(shù)據(jù)加載到緩存中,則不會刪除舊的但經(jīng)常使用的數(shù)據(jù)(因為它們的權重更高)。但是,如果不再使用舊數(shù)據(jù),該算法便無法將其保留在緩存中。因此,如果不使用數(shù)據(jù),權重會隨著時間的推移而降低。
權重的計算成本很高,這就是為什么SQL Server僅使用K = 2的原因。該值在可接受的開銷下表現(xiàn)良好。要更深入地了解LRU-K,可以閱讀原始研究論文(1993年):用于數(shù)據(jù)庫磁盤緩沖的LRU-K頁面替換算法。
當然,還有其他算法可以管理緩存,例如
2Q(類似于LRU-K的算法)
時鐘(類似于LRU-K的算法)
MRU(最近使用,使用與LRU相同的邏輯,但使用另一條規(guī)則)
LRFU(最近和經(jīng)常使用的最少)
一些數(shù)據(jù)庫允許使用默認算法以外的其他算法。寫緩沖區(qū):在數(shù)據(jù)庫中,你還擁有寫緩沖區(qū),用于存儲數(shù)據(jù)并將數(shù)據(jù)按束刷新到磁盤上,而不是一一寫入數(shù)據(jù)并產生許多單個磁盤訪問權限。
緩沖區(qū)存儲的是頁面(數(shù)據(jù)的最小單位)而不是行(這是查看數(shù)據(jù)的邏輯/人為方式)。如果頁面已被修改且未寫入磁盤,則緩沖池中的頁面是臟的。有多種算法可以決定在磁盤上寫入臟頁的最佳時間,但是它與事務的概念高度相關。
ACID事務是確保以下四件事的工作單元:
原子性:即使持續(xù)10小時,交易還是“全有還是全無”。如果事務崩潰,則狀態(tài)返回到事務之前(事務回滾)。
隔離度:如果2個事務A和B同時運行,則無論A在事務B之前/之后還是期間完成,事務A和B的結果都必須相同。
持久性:提交事務(即成功結束)后,無論發(fā)生什么情況(崩潰或錯誤),數(shù)據(jù)都會保留在數(shù)據(jù)庫中。
一致性:僅將有效數(shù)據(jù)(就關系約束和功能約束而言)寫入數(shù)據(jù)庫。一致性與原子性和隔離性有關。
在同一事務中,你可以運行多個SQL查詢來讀取,創(chuàng)建,更新和刪除數(shù)據(jù)。當兩個事務使用相同的數(shù)據(jù)時,混亂就開始了。經(jīng)典示例是從帳戶A到帳戶B的資金轉帳。假設你有2筆交易:
交易1從帳戶A收取100 $,并將其轉入帳戶B;交易2從帳戶A收取50 $,并將其轉入帳戶B。
如果我們回到ACID屬性:
原子性確保無論在T1期間發(fā)生什么情況(服務器崩潰,網(wǎng)絡故障...),你都不會遇到從A撤回100 $而沒有給B的情況(這種情況是不一致的) 。
I solation確保如果T1和T2同時發(fā)生,最終A將被收取150 $,B被給予150 $,而不是,例如,A會被收取150 $,而B僅被給予$ 50,因為T2已部分刪除了操作T1的狀態(tài)(這種情況也是不一致的狀態(tài))。
持久性可確保如果T1提交后數(shù)據(jù)庫崩潰,T1將不會消失。
一致性確保不會在系統(tǒng)中創(chuàng)建或銷毀任何資金。
大多數(shù)數(shù)據(jù)庫都添加了自己的自定義隔離級別(例如PostgreSQL,Oracle和SQL Server使用的快照隔離)。而且,大多數(shù)數(shù)據(jù)庫并沒有實現(xiàn)SQL規(guī)范的所有級別(尤其是讀取未提交的級別)。
用戶/開發(fā)人員可以在連接開始時覆蓋默認的隔離級別(這是添加的非常簡單的代碼行)。
并發(fā)控制
確保隔離,一致性和原子性的真正問題是對同一數(shù)據(jù)的寫操作(添加,更新和刪除):
如果所有事務都僅讀取數(shù)據(jù),則它們可以在不修改另一事務行為的情況下同時工作。
如果(至少)一個事務正在修改其他事務讀取的數(shù)據(jù),則數(shù)據(jù)庫需要找到一種對其他事務隱藏此修改的方法。此外,還需要確保不會被其他未看到修改后的數(shù)據(jù)的事務擦除此修改。
此問題稱為并發(fā)控制。
解決此問題的最簡單方法是一個接一個地(即順序地)運行每個事務。但這根本不是可擴展的,并且只有一個內核在多處理器/內核服務器上工作,效率不是很高……
解決此問題的理想方法是每次創(chuàng)建或取消交易時:監(jiān)視所有交易的所有操作;檢查兩個(或多個)交易的部分是否存在沖突,因為它們正在讀取/修改相同的數(shù)據(jù);對沖突事務中的操作進行重新排序以減小沖突部分的大小;以一定順序執(zhí)行沖突部分(非沖突事務仍在并發(fā)運行)。
鎖管理器:為了解決此問題,大多數(shù)數(shù)據(jù)庫都使用鎖和/或數(shù)據(jù)版本控制。
悲觀鎖定
鎖定背后的想法是:如果交易需要數(shù)據(jù),它鎖定數(shù)據(jù)如果另一筆交易也需要此數(shù)據(jù),它必須等到第一個事務釋放數(shù)據(jù)。這稱為排他鎖。但是,對于僅需要讀取數(shù)據(jù)的事務使用排他鎖非常昂貴,因為它會強制其他只希望讀取相同數(shù)據(jù)的事務等待。這就是為什么還有另一種類型的鎖,即共享鎖。
使用共享鎖:如果交易只需要讀取數(shù)據(jù)A,它“共享鎖定”數(shù)據(jù)并讀取數(shù)據(jù),如果第二筆交易也只需要讀取數(shù)據(jù)A;它“共享鎖定”數(shù)據(jù)并讀取數(shù)據(jù),如果第三筆交易需要修改數(shù)據(jù)A,它“獨占鎖定”數(shù)據(jù),但它必須等到其他2個事務釋放它們的共享鎖后才能將獨占鎖定應用于數(shù)據(jù)A。盡管如此,如果將數(shù)據(jù)作為排他鎖,則僅需要讀取數(shù)據(jù)的事務將不得不等待排他鎖的結尾才能在數(shù)據(jù)上放置共享鎖。
鎖管理器是提供和釋放鎖的過程。在內部,它將鎖存儲在哈希表中(其中的鍵是要鎖定的數(shù)據(jù)),并知道每個數(shù)據(jù):哪些事務鎖定了數(shù)據(jù),哪些事務正在等待數(shù)據(jù)。
但是使用鎖可能會導致2個事務永遠等待數(shù)據(jù)的情況:
在此圖中:
事務A擁有對data1的排他鎖,正在等待獲取data2;事務B在data2上具有排他鎖,并且正在等待獲取data1,這稱為死鎖。
在死鎖期間,鎖管理器選擇要取消(回滾)的事務以刪除死鎖。這個決定并不容易:是否最好殺死修改了最少數(shù)據(jù)量的事務(因此將產生最便宜的回滾)?最好是因為另一筆交易的用戶等待了更長的時間而取消了最老的交易?是否最好取消將花費較少時間完成的交易(并避免可能的饑餓)?如果發(fā)生回滾,此回滾將影響多少交易?但是在做出選擇之前,它需要檢查是否存在死鎖。
哈希表可以看作是一個圖形(就像前面的圖中一樣)。如果圖中存在周期,則存在死鎖。由于檢查周期非常昂貴(因為帶有所有鎖的圖相當大),因此通常使用一種更簡單的方法:使用timeout。如果在此超時時間內未給出鎖定,則事務將進入死鎖狀態(tài)。
鎖管理器還可以在提供鎖之前檢查該鎖是否會產生死鎖。但是,完美地做到這一點在計算上又很昂貴。因此,這些預檢查通常是一組基本規(guī)則。
兩相鎖定
確保純隔離的最簡單方法是在事務開始時獲取鎖,然后在事務結束時釋放鎖。這意味著事務必須在開始之前等待所有鎖,并且在事務結束時釋放由事務持有的鎖。它可以工作,但 會浪費大量時間來等待所有鎖。
更快的方法是兩階段鎖定協(xié)議(DB2和SQL Server使用),該協(xié)議將事務分為兩個階段:
事務可以獲取鎖,但不能釋放任何鎖的增長階段。
在收縮階段,事務可以釋放鎖(針對已經(jīng)處理并且不會再次處理的數(shù)據(jù)),但是無法獲得新的鎖。
這兩個簡單規(guī)則的思想是:
釋放不再使用的鎖,以減少等待這些鎖的其他事務的等待時間,以防止在交易開始后交易會修改數(shù)據(jù)并因此與交易獲取的第一個數(shù)據(jù)不一致的情況。該協(xié)議運行良好,除非修改(取消)了修改數(shù)據(jù)并釋放關聯(lián)鎖的事務。你可能最終遇到另一個事務讀取修改后的值而該值將被回滾的情況。為避免此問題,必須在事務結束時釋放所有排他鎖。
當然,實際的數(shù)據(jù)庫使用的是更復雜的系統(tǒng),其中涉及更多類型的鎖(例如意圖鎖)和更多的粒度(行,頁面,分區(qū),表,表空間上的鎖),但是這種想法仍然存在相同的。
版本控制的思想是:每個交易都可以同時修改相同的數(shù)據(jù);每筆交易都有其自己的數(shù)據(jù)副本(或版本)。
如果2個事務修改了相同的數(shù)據(jù),則僅接受一個修改,而另一個則被拒絕,并且關聯(lián)的事務將回滾(并可能重新運行)。由于以下原因,它提高了性能:讀者交易不會阻止作家交易,作家交易不會阻止讀者交易“胖而慢”的鎖管理器沒有任何開銷。
一切都比鎖好,除非兩個事務寫入相同的數(shù)據(jù)。此外,你可能很快就會面臨巨大的磁盤空間開銷。
數(shù)據(jù)版本控制和鎖定是兩個不同的愿景:樂觀鎖定與悲觀鎖定。他們都有優(yōu)點和缺點;這實際上取決于用例(更多的讀取還是更多的寫入)。
某些數(shù)據(jù)庫,例如DB2(直到DB2 9.7)和SQL Server(快照隔離除外)僅使用鎖。其他類似PostgreSQL,MySQL和Oracle的混合方法涉及鎖和數(shù)據(jù)版本控制。
版本控制會對索引產生有趣的影響:有時,唯一索引包含重復項,索引所包含的條目可能比表中具有行的條目多,等等。
如果閱讀有關隔離級別不同的部分,則增加隔離級別時會增加鎖的數(shù)量,因此事務等待其鎖所浪費的時間。這就是為什么大多數(shù)數(shù)據(jù)庫默認情況下不使用最高隔離級別(可序列化)的原因。
為了提高性能,數(shù)據(jù)庫將數(shù)據(jù)存儲在內存緩沖區(qū)中。但是,如果在提交事務時服務器崩潰,則崩潰期間你仍然會丟失仍在內存中的數(shù)據(jù),這將破壞事務的持久性。你可以將所有內容寫在磁盤上,但是如果服務器崩潰,最終將一半的數(shù)據(jù)寫在磁盤上,這將破壞事務的原子性。
事務編寫的任何修改必須撤消或完成。要解決此問題,有兩種方法:
卷影副本/頁面:每個事務都會創(chuàng)建自己的數(shù)據(jù)庫副本(或只是數(shù)據(jù)庫的一部分)并在此副本上工作。萬一出錯,副本將被刪除。如果成功,數(shù)據(jù)庫將使用文件系統(tǒng)技巧立即從副本切換數(shù)據(jù),然后刪除“舊”數(shù)據(jù)。
事務日志:事務日志是一個存儲空間。在每次將磁盤寫入磁盤之前,數(shù)據(jù)庫都會在事務日志上寫入信息,以便在事務崩潰/取消的情況下,數(shù)據(jù)庫知道如何刪除(或完成)未完成的事務。
當在涉及許多事務的大型數(shù)據(jù)庫上使用時,卷影副本/頁面會產生巨大的磁盤開銷。這就是為什么現(xiàn)代數(shù)據(jù)庫使用事務日志的原因。事務日志必須存儲在穩(wěn)定的存儲器中。我不會更深入地介紹存儲技術,但是必須(至少)使用RAID磁盤來防止磁盤故障。
大多數(shù)數(shù)據(jù)庫(至少是Oracle,SQL Server,DB2,PostgreSQL,MySQL和 SQLite)都使用預寫日志記錄協(xié)議(WAL)處理事務日志。WAL協(xié)議是3條規(guī)則的集合:
1)對數(shù)據(jù)庫的每次修改都會產生一個日志記錄,并且在將數(shù)據(jù)寫入磁盤之前,必須將日志記錄寫入事務日志中。
2)日志記錄必須按順序寫入;在必須在日志記錄B之前但在B之前寫入的日志記錄A
3)提交事務后,必須在事務成功結束之前將提交順序寫在事務日志上。
這項工作由日志管理器完成。在完成所有工作之后,你應該知道與數(shù)據(jù)庫相關的所有內容都受到“數(shù)據(jù)庫效應”的詛咒。更嚴重的是,問題是找到一種在保持良好性能的同時寫入日志的方法。如果事務日志上的寫入太慢,它們將減慢所有操作。
數(shù)據(jù)庫必須回滾事務有多種原因:因為用戶取消了,由于服務器或網(wǎng)絡故障,因為事務破壞了數(shù)據(jù)庫的完整性(例如,你對列具有UNIQUE約束,并且事務添加了重復項)。
事務期間的每個操作(添加/刪除/修改)都會生成一個日志。該日志記錄由以下內容組成:
LSN:一個獨特的大號OG小號層序Ñ棕土。該LSN按時間順序給出*。這意味著,如果操作A在操作B之前發(fā)生,則日志A的LSN將低于日志B的LSN。
TransID:產生該操作的事務的ID。
PageID:修改后的數(shù)據(jù)在磁盤上的位置。磁盤上的最小數(shù)據(jù)量是一個頁面,因此數(shù)據(jù)的位置就是包含該數(shù)據(jù)的頁面的位置。
PrevLSN:指向同一事務產生的先前日志記錄的鏈接。
撤消操作:消除操作影響的一種方法
例如,如果操作是更新,則UNDO將存儲更新之前的更新元素的值/狀態(tài)(物理UNDO),或者存儲反向操作以返回到先前狀態(tài)(邏輯UNDO)**。
REDO:重播操作的一種方式
同樣,有兩種方法可以做到這一點。你可以在操作之后存儲元素的值/狀態(tài),或者在操作本身中存儲元素以重播它。
此外,磁盤上的每個頁面(用于存儲數(shù)據(jù),而不是日志)具有修改數(shù)據(jù)的最后操作的日志記錄(LSN)的ID。
每個日志都有一個唯一的LSN。鏈接的日志屬于同一事務。日志按時間順序鏈接(鏈接列表的最后一個日志是最后一個操作的日志)。為避免日志寫入成為主要瓶頸,使用了日志緩沖區(qū)。
當查詢執(zhí)行者要求修改時:
1)緩存管理器將修改存儲在其緩沖區(qū)中。
2)日志管理器將關聯(lián)的日志存儲在其緩沖區(qū)中。
3)在這一步,查詢執(zhí)行者認為操作已完成(因此可以要求其他修改)
4)然后(稍后),日志管理器將日志寫入事務日志中。何時寫入日志的決定是由算法完成的。
5)然后(稍后),緩存管理器將修改內容寫入磁盤。何時將數(shù)據(jù)寫入磁盤的決定是由算法決定的。
提交事務后,這意味著對于事務中的每個操作,都將完成步驟1、2、3、4、5。寫入事務日志的速度很快,因為它只是“在事務日志中的某處添加日志”,而將數(shù)據(jù)寫入磁盤則更為復雜,因為它是“以快速讀取數(shù)據(jù)的方式寫入數(shù)據(jù)”。
竊取和強制政策
出于性能原因,可能在提交后執(zhí)行步驟5,因為如果發(fā)生崩潰,仍然可以使用REDO日志恢復事務。這就是所謂的NO-FORCE政策。
數(shù)據(jù)庫可以選擇一個FORCE策略(即,必須在提交之前執(zhí)行步驟5),以降低恢復過程中的工作量。
另一個問題是選擇是將數(shù)據(jù)逐步寫入磁盤(STEAL策略),還是選擇緩沖區(qū)管理器是否需要等到提交順序一次寫入所有內容(NO-STEAL)。在STEAL和NO-STEAL之間進行選擇取決于你想要的:使用UNDO日志進行長時間恢復的快速寫入還是快速恢復?
STEAL / NO-FORCE 需要UNDO和REDO:最高的性能,但提供更復雜的日志和恢復過程(如ARIES)。這是大多數(shù)數(shù)據(jù)庫所做的選擇。
STEAL / FORCE僅需要撤消;無需竊取/無需強制只需要重做;無竊取/強制不需任何東西:最差的性能和大量的夯是必需的。
ARIES通過以下三步從崩潰中恢復:
1)分析階段:恢復過程讀取完整的事務日志*,以重新創(chuàng)建崩潰期間發(fā)生的事情的時間表。它確定要回滾的事務(所有沒有提交訂單的事務都將回滾)以及崩潰時需要將哪些數(shù)據(jù)寫入磁盤。
2)重做過程:此過程從分析期間確定的日志記錄開始,并使用REDO將數(shù)據(jù)庫更新為崩潰前的狀態(tài)。
在重做階段,將按時間順序(使用LSN)處理REDO日志。
對于每個日志,恢復過程都會讀取磁盤上包含要修改的數(shù)據(jù)的頁面的LSN。
如果LSN(page_on_disk)> = LSN(log_record),則意味著數(shù)據(jù)已在崩潰之前被寫入磁盤(但是該值已被日志之后和崩潰之前發(fā)生的操作所覆蓋),因此什么也不做。
如果LSN(page_on_disk)
即使對于將要回滾的事務,重做也已完成,因為它簡化了恢復過程(但我敢肯定,現(xiàn)代數(shù)據(jù)庫不會這樣做)。
3)撤消密碼:此密碼會回退崩潰時所有未完成的事務?;貪L從每個事務的最后一個日志開始,并以反時間順序(使用日志記錄的PrevLSN)處理UNDO日志。
在恢復期間,必須警告事務日志有關恢復過程所執(zhí)行的操作,以便磁盤上寫入的數(shù)據(jù)與事務日志中寫入的數(shù)據(jù)同步。一種解決方案是刪除正在撤消的事務的日志記錄,但這非常困難。而是,ARIES將補償日志寫入事務日志中,該日志將邏輯上刪除要刪除的事務的日志記錄。
當“手動”取消交易或由鎖定管理器取消交易(以停止死鎖)或僅由于網(wǎng)絡故障而取消交易時,則不需要分析通過。實際上,有關REDO和UNDO內容的信息可在2個內存表中找到:
一個事務表(存儲所有當前事務的狀態(tài))
一個臟頁表(需在磁盤上寫入數(shù)據(jù)需要存儲)。
這些表由緩存管理器和事務管理器針對每個新事務事件進行更新。由于它們在內存中,因此在數(shù)據(jù)庫崩潰時會被銷毀。
分析階段的工作是在崩潰后使用事務日志中的信息重新創(chuàng)建兩個表。*為了加快分析過程,ARIES提供了checkpoint的概念。想法是不時在磁盤上寫入事務表,臟頁表的內容以及該寫入時的最后LSN的內容,以便在分析過程中僅分析此LSN之后的日志。
當你不得不在錯誤的NoSQL數(shù)據(jù)庫和堅如磐石的關系數(shù)據(jù)庫之間進行選擇時,請三思而后行。有些NoSQL數(shù)據(jù)庫很棒。但是他們還很年輕,正在回答涉及一些應用程序的特定問題。
經(jīng)過以上了解,大家應該明白大數(shù)據(jù)中數(shù)據(jù)庫是如何工作的了,想要學習更深層次的大數(shù)據(jù)專業(yè)知識,可以到AAA教育官網(wǎng)了解一下,大數(shù)據(jù)分析專業(yè),互聯(lián)網(wǎng)熱門行業(yè),技術含量高,無論是找工作還是自我提升都是不錯的選擇。
填寫下面表單即可預約申請免費試聽!怕錢不夠?可先就業(yè)掙錢后再付學費! 怕學不會?助教全程陪讀,隨時解惑!擔心就業(yè)?一地學習,可推薦就業(yè)!
?2007-2022/ m.5wd995.cn 北京漫動者數(shù)字科技有限公司 備案號: 京ICP備12034770號 監(jiān)督電話:010-53672995 郵箱:bjaaa@aaaedu.cc