跳到內容

通過寫時復制進行更新

介紹

“寫時復制”是一種在計算中的各種應用中使用的技術。 RDM在幾個領域中都使用了此技術。在深入研究RDM之前,讓我們看一下一般情況。

 

寫時復制背後的主要思想是複制一些內容,然後修改副本,而不是在寫入內存,文件或塊設備時修改原始內容。這就是術語“寫時復制”的來源。某些應用程序是在函數式編程中結合“引用計數”進行寫時復制的。在Unix中,在有一些硬件幫助的情況下,分叉系統調用的實現中使用寫時復制來共享虛擬內存。 Linux中的Btrfs文件系統使用寫時復制功能來進行有效的事務處理和快照隔離。虛擬機管理程序和虛擬機實現也可以使用此技術進行有效的內存管理。

 

在RDM中,我們將這種技術用於嵌套事務。但是,本文重點介紹在RDM 15.0中實現的數據庫文件格式。首先,讓我們看一下RDM的早期版本。


先前版本的RDM

RDMe 12.0和更早版本(“ RDMe”)使用了事務日誌。這意味著數據通常被寫入兩次-首先寫入事務日誌,然後寫入實際的數據庫文件。 RDMe還存儲了固定長度的項目,在某些情況下,其他內容必須單獨存儲在其他位置。這種設計導致浪費的空間,在必須拆分內容時會產生額外的開銷,並且通常不太靈活。由於記錄的長度固定,因此對數據進行任何類型的壓縮也沒有用。

 

為了減輕這些問題,RDM 14.0使用“寫時復制”更新了可變大小的記錄。數據庫文件被拆分為我們所謂的“打包文件”。總是通過“寫時復制”來完成軟件包的更新。但是,RDM 14.0並未進行完整的遞歸“寫入時復制”。取而代之的是,每當內容從數據包中的一個位置移動到另一個位置時,它都依賴於鍵值存儲(ID索引)。

 

這種設計有其自身的問題。 ID索引跟踪未使用的空間。這種跟踪和有效利用未使用空間所需的數據結構非常昂貴。與批量寫入結合使用時,它還防止了空間的重用。 I / O性能也遠非最佳,因為只有一部分頁面被更新時,數據才被寫入頁面。 

 

此設計還需要ID索引的事務日誌,該日誌已集成到RDM 14.1包中。刷新ID索引也相對昂貴,這可能會導致數據庫打開和關閉速度變慢。這些問題使該設計不適用於像 REST API,它依賴於為每個單個請求打開和關閉數據庫。

 

RDM 14.2採用的方法與RDM 14.1略有不同。在以下部分中,我們將主要討論15.0設計,該設計與14.2設計具有許多共同的特徵,以及與14.1設計具有一些共同的特徵。


RDM 15.0

兩項原則

RDM 15.0建立在兩個原則上。

 

我們所依賴的第一個原則是完全遞歸的“寫時復制”。這意味著RDM 15.0中使用的持久性數據結構是一棵樹(或一棵樹,取決於抽象級別),而沒有使用ID索引。使用了兩種樹結構:B樹和R樹。數據庫將為模式中定義的每個鍵都有一棵樹,但是還需要其他樹。其詳細信息超出了本文的範圍。在結束本討論時,我們提到要將所有這些樹綁在一起,還有一個主樹,它引用了其他樹的根節點。

 

我們所依賴的第二個原則始終是附加到最後一個包文件的末尾。

因此,打包文件永遠不會在中間進行更新。這意味著可以避免只在頁面的一小部分進行更新的中間進行昂貴的更新,並且也無需管理可用空間。不再引用的空間只會導致無法訪問。


“自下而上”附加和編寫更改

這兩個原則有很多含義。隨之而來的一個暗示是,所有更新都必須通過將其附加到包的末尾來完成。 RDM通過首先寫入沒有直接或間接引用其他更新項目的新項目和更新項目,然後是引用這些項目的樹節點,其父樹節點,其祖父母樹節點等,直到它們的根節點,來提交事務。主B樹已被編寫。

 

這種設計意味著即使沒有其他更改,也將必須寫入其他節點。對於大型事務,通常不需要考慮此問題,因為大型事務更可能在同一B樹節點上發生多個更新。另一方面,對於僅進行少量更改的小型交易而言,額外的開銷可能是相當大的。對於涉及時間序列或 圓桌.


快照

使用遞歸“寫入時復制” 快照 可以非常有效地實施請求快照時,請求快照的客戶端可以使用主B樹的當前根節點,並且其數據視圖是從該節點可以到達的位置派生的。快照和使用讀取鎖的讀取之間的唯一區別是,請求讀取鎖的客戶端將阻止對請求讀取鎖的表的更新,而快照則不會。無需其他任何昂貴的內部數據結構即可處理快照。請求快照的客戶端可以簡單地處理來自事務文件服務器(TFS)的內容請求,其處理方式與帶鎖的普通讀取完全相同。它獲得一個主要的B樹根節點,並根據其中的引用從TFS請求其他節點。

 

結果,利用寫時復制的打包文件格式非常適合快照。當請求快照時,可以在包中引用舊數據。從打包文件的實現角度來看,我們只需要確保不會刪除快照中可見數據的打包文件。


耐用性

由於數據僅附加到最後一個打包文件的末尾(文件的格式經過精心設計),因此在大多數情況下,只需同步最後一個打包文件,就可以實現持久性。與需要同步多個文件的其他數據庫(包括較早版本的RDM)相比,這具有一些性能優勢。 

 

事實證明,如果不需要持久性,大多數同步可以省略。在這種情況下,系統崩潰可能會導致某些數據丟失。但是,由於我們僅附加到文件,因此,如果找到一個主要的B樹根節點,那麼從該根節點引用的所有數據都應該是有效的。假設文件系統實現在僅向該文件追加時不會丟失文件中間的塊。 RDM必須採取一種預防措施,才能起作用:每當請求新的打包文件時,都必須同步以前的打包文件(在Linux和Unix上,我們也必須同步目錄)。這樣可以確保從一個打包文件到上一個打包文件的任何引用都不會丟失。

 

我們還實現了一種不安全模式,該模式下我們根本不同步打包文件。僅當不擔心丟失數據庫中的數據時才應使用此模式,否則可以確保不同步文件就不會關閉操作系統或使之崩潰。數據庫崩潰是可以的,因為寫入的內容將在文件系統緩存中。請注意,在某些嵌入式系統中可能不是這種情況,其中文件系統是在用戶空間中實現的。

 

為了進行恢復,精心設計了打包文件格式,以便可以向前和向後讀取打包文件。對於每個64KiB,都有特殊的恢復信息,使您可以向前和向後掃描文件,而不必從頭開始讀取整個文件。此屬性對於有效和可靠的恢復很重要。 Recovery不會向包中寫入任何內容,而是找到最後一個主要的B樹根節點並驗證包的末尾。如果發現數據庫處於某種不完整狀態,則將創建一個新的打包文件。這僅意味著崩潰可能會導致打包文件中的內容未被主B樹根節點直接或間接引用。

 

打包文件格式允許並行執行多個更新事務,但是當它們提交時,追加到打包文件將在當前提交的事務之間交替進行。小型事務可能能夠將其所有數據附加到一個塊中,而大型事務將需要輪流寫入其數據。主B樹需要專門編寫,並且每次完成時,其他更新事務或吸塵器(垃圾收集器,我們將在後面介紹)的更改都必須與手頭事務的更改集成在一起。


運行時緩存

具有ID索引的舊設計以及基於固定大小項目的實現都要求,只要我們有另一個客戶端對同一表進行更新,就必須清除運行時緩存中給定表的數據。使用RDM 15.0設計,我們不需要清除任何數據。運行時緩存始終使用包地址查找數據,因此可以保證在緩存時找到正確的數據。這意味著數據可能能夠在運行時緩存中保留更長的時間,從而有可能提高性能。


並行與直接讀寫

具有ID-index的舊設計不允許操作並行運行。利用寫時復制的RDM 15.0設計允許來自不同客戶端的大多數操作並行運行。該文件格式甚至允許大多數文件操作在同一台機器上從不同進程並行執行,而無需直接與TFS進行通信即可直接讀取和寫入打包文件。這種方法產生了更高的性能。


吸塵

儘管RDM 15.0設計具有如上所述的許多優點,但它具有一個主要缺點。由於我們只附加到包的末尾,因此它將無限期地增長。為了解決此問題,我們執行了稱為“真空”的垃圾收集過程。吸塵將在 單獨的文章.


結論

我們已經看到,RDM 15.0的文件格式非常靈活,非常適合快照隔離,並行性,低內存佔用和快速恢復。我們建議您繼續閱讀 快照隔離吸塵。享受! 

 

Sverre Hvammen Johansen和Daigoro Toyama