一種基于預寫日志的SQLite快速數據恢復方法*

夏文菁，徐 明，吳 鋌，鄭 寧

（杭州電子科技大學，浙江 杭州 310018）

0 引 言

SQLite是一款輕量級的單文件關系型數據庫，其使用時無需啟動獨立的進程用于提供數據庫服務，而是通過解析處理數據庫文件直接進行數據的CRUD操作。基于此特性，SQLite被廣泛應用于手機系統及日志服務器等讀寫頻率較高的場景。在設計初期，SQLite被用于處理小數據量存儲的需求，但隨著技術發展與版本迭代，其已經能夠存儲龐大的數據。在數據管理系統、日志系統等常見的軟件系統中，系統日志、操作記錄以及訂單信息等數據往往會保存在SQLite數據庫中。隨著軟件的運行，數據庫的數據量會逐漸增加，最終會達到100GB至1TB。在傳統數據庫恢復方法中，由于未考慮大數據量的情況，恢復時會消耗大量的內存空間和時間。

預寫日志作為一種用于替換回滾日志機制的新方案，在SQLite3.7版本被引入[1]。與回滾日志相比，其具有更快的檢索速度和更新速度，并且對多線程操作有著良好的支持。在此方法中，對數據庫的操作不會直接修改數據庫文件，而是預先記錄到日志文件，當事務進入檢查點時，日志文件中記錄的操作會被同步到數據庫文件。基于預寫日志的恢復方法主要對日志文件進行分析，由于日志文件在使用結束后會被刪除，因此對日志數據進行數據恢復時，需要先從文件系統中恢復被刪除的預寫日志文件，并對其進行處理與拼接。由于文件鏡像本身空間較大，檢索被刪除的預寫日志文件會消耗大量時間。

綜上所述，在SQLite數據庫的恢復過程中，存在某些耗時很大的操作，這些操作會影響數據庫的恢復效率[2]。因此，對傳統數據庫恢復技術進行改進更新以提升恢復效率，這具有重要的理論意義和實際價值。

1 SQLite數據快速恢復原理

1.1 MapReduce概述

常用的大規模并行計算技術使用谷歌提出的MapReduce架構，該架構可以充分利用多臺計算機的性能來提升運行速度。MapReduce由Map（映射）與Reduce（歸納）兩個過程組成，其中，Map過程主要用來過濾、排序、分段處理等操作，而Reduce過程則主要用于數據的聚合操作[3-7]。在MapReduce架構中，通常會通過對分布式的服務器進行自動編組，并行運行各種任務，并且會管理分布式服務器各個部分之間的通信以及數據的傳輸，在這個過程中還會提供部分的冗余和容錯機制，最終保證結果的可靠性。

MapReduce模型的使用過程中，根據其特性，將數據分析的過程轉換為拆分、應用、組合這三個操作。雖然MapReduce模型的實際使用中和最開始的形式則有比較大的不同，但是它的靈感最早來源于函數式編程中的Map和Reduce函數，在單線程的實現中，使用MapReduce進行操作不會比傳統的實現更快，它在多處理器硬件上的多線程實現中應用才能獲得盡可能大的執行速度增益。在進行分布式操作時，最重要的過程是優化通信效率，這個對算法的良好運行至關重要。

1.2 MapReduce的并行編程模型

由前文可知，MapReduce編程模型是Google最先提出的[8]，并定義了兩個抽象的編程接口：Map和Reduce。

式（1）處理的是k2、v2這樣的一組數據，這個數據在Map方法中會作為鍵值對傳入，在了Map方法計算完成后，會得到另一種形式的鍵值對，這個鍵值對的結果類似[(k2;v2)]。

在式（2）中，傳入的參數由Map方法生成，參數為一組鍵值對，其形式為k2;[v2]。其中，v2是一個集合，對于Reduce操作來說，相同的鍵可能會產生多個不同的值，因此在Reduce操作的過程中，會將所有相同鍵的數據整合到同一個集合中來進行統一的規劃。在這里，Map方法得到的中間結果會進行類似整合的處理操作，最終的實際結果也會是一對鍵值對，其形式類似[(k3;v3)]。

經過上面對MapReduce的基本介紹后，Map Reduce操作可以對現有的邏輯結構進行劃分，得到了圖1中的并行計算模型。圖1中表達了MapReduce模型的基本處理過程，該過程主要分成4步：

（1）對數據本身進行分片，并在Map操作中對每一片的數據分別并行進行處理，得到中間結果；

（2）Reduce操作會接收Map操作中給出的執行結果，并按照一定的邏輯進行數據處理；

（3）只有當所有的Map操作都完成任務，Reduce操作才實際處理Map產生的數據；

（4）在Reduce完成操作后，需要對其結果繼續進行整合得到最終結果。

1.3 Hadoop系統構架

Hadoop是一款比較流行的MapReduce編程框架，其由Java語言完成，而且是一款開源的項目。其主要采用了谷歌公司提出的MapReduce方法[9-10]。Hadoop系統的基本構成如圖2所示[11]。Hadoop系統的本質操作是基于分布式的存儲和多個服務器的并行計算。Hadoop中主要包含兩種節點，分別是NameNode和DataNode。其中NameNode的主要作用是保存分布式存儲中整個文件存儲系統的元數據，而DataNode則主要作為存儲大數據的基本節點。Hadoop主要部署在Linux操作系統中，很多實現都依賴了Linux的一些功能，比如，在并行計算的主體架構中，Hadoop就使用了JobTracker，這是一個管理節點和計算時間的工具，Hadoop主要用這個工具來計算框架執行時間和不同任務的規劃管理。

圖1 MapReduce并行編程模型

圖2 Hadoop系統的基本組成架構

在Hadoop的本地化計算中，DataNode和Task Tracker兩個操作都會合并到同一個節點中，換句話說，每個節點都會同時完成DataNode與TaskTracker兩個部分的操作，所以每個TaskTracker都可以計算當前DataNode中的數據。

NameNode和JobTracker分別作為數據存儲節點和作業執行節點也可以配置到相同的節點中。而在大規模的集群中，由于主節點的負載可能會非常龐大，從而導致互相之間出現性能沖突，此時可以為兩個節點各自配置相關的參數到不同的節點中。

2 預寫日志結構分析

2.1 預寫日志基本說明

在新版本的SQLite中，所有數據庫的操作預先記錄到日志文件中，當事務進入檢查點時，日志文件中記錄的操作會一次性同步到數據庫文件。由此可見，在預寫日志中包含了所有數據庫相關的操作信息。

在大多數情況下，預寫日志文件會在完成數據寫入操作后被刪除。因此，在數據庫恢復過程中，需要對硬盤鏡像文件進行預處理，從中恢復已經被刪除的預寫日志文件。在常見的硬盤鏡像類型中，手機的硬盤鏡像大小一般為16GB到128GB。而服務器的硬盤鏡像則至少為50GB，甚至上TB級別。這些鏡像文件進行文件恢復需要消耗大量時間，對恢復速度有很大的影響。因此，本文引入了MapReduce技術，使用MapReduce進行被刪除預寫日志文件的恢復操作。

2.2 預寫日志格式解析

預寫日志是一種二進制的存儲結構，其主要包含了日志邏輯結構、日志頭結構和Frame塊結構。

一個日志文件由零到多個Frame塊組成，前32個字節為日志頭部。日志頭部中主要記載了日志的版本、B樹頁的節點個數、校驗碼等信息，其主要描述如表1所示。日志頭部還包含兩組隨機數值，其主要用于判斷多個Frame是否屬于同一條記錄。圖3是在二進制文件查看工具中得到的一個日志文件頭部的基本構造。

表1 日志文件頭部說明

圖3 預寫日志頭結構

Frame塊主要由頭部和具體包含數據的B樹結構組成，其中，頭部為固定的24個字節，具體的字段說明見表2所示。其主要包含數據部分的邏輯頁號和提交事務后數據庫的理論大小。圖4是在二進制文件查看工具中得到的一個Frame塊頭部的基本構造。

表2 Frame塊頭描述信息

圖4 Frame 頭結構

Frame塊數據部分的大小通常為1 024個字節或者4 096個字節，這個大小主要和SQLite的默認配置有關，在我們采用EXT4文件格式中，一般會采用4 096個字節，也就是4KB的大小來限制Frame部分的體積。由于在數據庫操作的過程中，數據往往會大于4 096字節，Frame數據文件會有多個，保存在文件系統不連續的數據空間上。因此，在恢復數據之前，還需要對這些Frame塊進行拼接，然后才能進行基于預寫日志的數據恢復。

3 基于預寫日志的恢復算法

3.1 預寫日志的文件提取方法

Android設備中默認會開啟預寫日志文件的功能，在預寫日志中可能包含了被刪除的SQLite數據信息，因此，基于SQLite預寫日志的數據庫恢復方法可以通過在系統鏡像文件中搜索日志的Frame塊并拼接，從中提取出被刪除的數據來實現。數據恢復的總體架構如圖5所示。在基于預寫日志的SQLite數據恢復過程中，主要可以分成兩個步驟：第一步，從硬盤鏡像中恢復被刪除的預寫日志文件；第二步，從預寫日志中恢復數據庫信息。

本文恢復方法步驟說明如下：

（1）將手機連上電腦，或者直接在服務器上使用dd命令獲取到鏡像文件，作為恢復的基礎數據文件；

（2）利用MapReduce方法掃描鏡像文件，從中恢復出日志文件的數據，并利用這些數據拼接出有效的Frame塊；

（3）利用MapReduce提取數據頁中的記錄，執行恢復操作后，將數據寫入到用于恢復的數據庫中；

（4）處理恢復數據庫，并刪除其中重復出現的數據。

（5）綜上，該方法可以概述為，從鏡像文件中提取出預寫日志文件并將預寫日志中保存的數據提取出來后，還原到原來的數據庫中。

圖5 方法總體框架

3.2 基于日志文件的的SQLite數據庫快速恢復算法

在本文基于預寫日志的SQLite數據庫恢復過程中，Map操作主要用于對硬盤鏡像文件的塊結構進行分析，從中獲取必要的信息，包括塊類型、子塊的偏移值，以及塊中的文件信息等等。其中，對于頭部塊，需要從中獲取到其他所有塊的偏移值信息，對于數據塊部分，則需要從中提取所有被刪除以及未被刪除的文件信息，如文件名、文件數據等等。塊數據的Map操作具體的偽代碼如算法1所示。

算法1 對塊數據的Map操作：

Input：硬盤文件塊偏移值

Output：恢復出來的預寫日志文件

1.page ← 根據塊偏移值獲取頁

2.blockType ← 從block中獲取塊的類型

3.if blockType == headerType then

4.offsets ←獲取所有子塊的偏移值

5.return offsets # 返回偏移值，對這些偏移值繼續進行Map操作

6.else

7.fileData = []

8.while haveDeletedFile # 遍歷當前塊中所有被刪除的文件節點

9.if checkFile # 檢查文件的后綴以及文件中的魔法數

10.從dataPage中獲取數據信息

11.fileData(data)

12.end if

13.end while

算法1主要用于獲取每個數據塊的內容，在第一次執行的時候，傳入的鏡像偏移值為0，用來提取B-tree結構中根節點的基本信息，完成了提取后會繼續調用Map任務，將下面子塊的偏移值作為參數來繼續進行處理。當獲取到了數據塊后，對塊中的文件名進行分析，提取后綴為wal的文件，并對數據進行初步分析，提取出頭部信息來判斷是否為預寫日志文件。如果確定為需要的預寫日志文件，則將該預寫日志文件發送給Reduce任務進行后續處理。

在Reduce操作中，主要進行的工作是對Map生成的預寫日志數據進行處理，并進行整合操作。在這里主要的任務是根據預寫日志的魔法數和時間戳信息，對預寫日志進行重組，并對其提取，然后得到需要的信息。Reduce的偽代碼如算法2所示。

算法2 預寫日志文件恢復的Reduce操作：

Define：恢復出來的數據recoveryData

存在預寫日志中的魔法數，用來標志對應的數據庫magicNumber1和magicNumber2

Input：恢復出來的預寫日志文件數據data

Output：恢復出來的數據庫

1.recoveryDatas = []

2.magicNumber1，magicNumber2 ← 從文件數據data中獲取魔法數

3.if checkMagicNumber(magicNumber1，magicNumber2)： # 檢查魔法數是否為當前數據庫的

4.recoveryData = recoveryByWSL(data) // 將相關的數據信息提取出來

5.recoveryDatas.add(recoveryData) # 將恢復結果添加到恢復數據集合中

6.end if

7.對recoveryData的數據去重

8.return recoveryData

算法2的操作中，核心部分是重組操作，并進行深度檢查，拋棄不符合要求的預寫日志文件。該方法中會先從文件中提取出魔法數，然后與當前數據庫的魔法數進行比較，確定無誤后，提取出文件中的歷史操作記錄，經過去重操作后，記錄到數據庫內。

4 實驗及結果分析

4.1 實驗準備

本文通過在物理機上搭建Hadoop集群實現，有4臺獨立的服務器用于實驗的進行，其中1臺用于運行單機的數據庫恢復程序，另外3臺則用于搭建集群服務，來運行本章基于集群的數據庫恢復程序。這4臺的服務器配置相同，均采用了4核2.6 GHz i7-6700 CPU，內存為8G，各擁有50GB的SSD硬盤空間。均安裝了Ubuntu 16.04的操作系統，并更新到了最新版。3臺集群服務器安裝了Hadoop3.0.1。分別部署了3套測試環境，它們分別為：

（1）Android手機，使用Android8.0系統，硬盤容量為256GB；

（2）Linux服務器，使用Ubuntu16.04操作系統，其硬盤容量為256GB；

（3）Linux服務器，使用Ubuntu16.04操作系統，硬盤容量為512GB。

在這些測試環境中，分別利用了腳本，創建了1GB大小的數據庫文件，并對數據庫文件各自做了隨機50次的插入刪除操作，每次插入刪除操作均會先刪除30%的數據，再增加30%的數據。

4.2 實驗設計

本節實驗的目標是測試提出的基于MapReduce的數據恢復方法的有效性。實驗步驟如下：

（1）獲取256GB A（手機鏡像）、256GB B（服務器鏡像）、512GB三個不同大小的鏡像文件；

（2）使用本章方法對三個不同大小的鏡像文件，進行恢復；

（3）使用傳統預寫日志恢復方法對三個不同大小的鏡像文件，進行恢復；

（4）對恢復結果進行統計和分析。

4.3 實驗結果和分析

通過本文提出的方法進行恢復實驗，實驗的最終結果是從人工數據集（一共1 500萬條記錄）中恢復出了1 360萬條有效數據記錄（重復記錄自動去除）。通過分析鏡像發現，重復記錄是因為修改的數據頁還未同步到數據庫中，幾乎每個數據頁都存在多個歷史版本，表3展示了鏡像中恢復出的部分數據記錄。

表3 人工數據集恢復記錄部分結果

本章使用恢復時間對實驗方法進行評估。對于人工數據集的恢復，方法的準確率是0.907。結果（只展示時長）如圖6所示。

圖6 人工數據集恢復結果對比

由圖6可知，當恢復方法一定時，恢復時間基本和文件系統鏡像的大小成正比關系，而對于相同大小的文件系統鏡像，其操作系統的區別也會影響恢復時間；當文件系統鏡像一定時，本章方法的恢復速度比原來的方法均要快2倍左右，因為此處采用的鏡像文件體積較大，集群服務器之間的操作交互不會對數據恢復帶來更大的影響。

使用對比方法（單服務器）也是以人工數據庫作為恢復樣本，對比方法恢復1 360萬條有效數據記錄，準確率為0.907。與本章方法的恢復效果對比如圖7所示。從圖7可以得到，文件大小在256 GB以上的時候，文件大小本身對SQLite數據的恢復速度影響是恒定的，通過實驗結果分析可知，本文方法相對于傳統恢復方法，速度提升了2倍，進一步證明了本方法的有效性。

圖7 人工數據集恢復速度比值

5 結 語

本文提出了一個利用MapReduce來提升基于預寫日志的SQLite數據恢復速度的方法。在利用SQLite預寫日志恢復數據的過程中，需要從文件系統中檢索出所有被刪除的日志文件，這個操作的耗時非常龐大，并且由于預寫日志的數據量會非常多，在拼接處理的過程中，也需要消耗較多的計算量。在本章中使用了MapReduce技術提升了這些過程的速度。通過研究現有的恢復方法，將恢復過程劃分為檢索鏡像文件提取被刪除的日志信息、利用頭部特征定位符合條件的日志首頁、根據頭部結構的隨機數繼續從鏡像中提取目標數據庫的數據頁并拼接這幾個操作，其中第一步和最后一步的檢索操作可以使用MapReduce來提升運行速度。通過比較使用了MapReduce技術的恢復方法和未使用該技術的恢復方法的運行速度，驗證速度的提升效果。通過人工數據集的實驗，驗證方法的可行性和有效性。但是，在利用本文方法進行數據恢復時，發現Hadoop中網絡延時對計算時間有一定影響，那么針對這種時間影響在后續研究中找出一定的規律性，也會對該類研究問題做出一定的貢獻。