sqlite原子提交原理

英文地址
文章參考

1. 簡介
   支持事務的資料庫系統如sqlite的一個重要特性是原子提交(atomic commit)。也就是在一個事務中進行的對資料庫的寫操作要麼全部執行，要麼全部不執行。看起來像是對資料庫不同部分的寫操作時瞬時發生的。
   實際上，對磁碟內容的改變需要一段時間，寫操作不可能是瞬時發生的。為此，sqlite內部有一套邏輯保證保證事務操作的原子性，即使系統crash或掉電也不會破壞原子性。
   這篇文章介紹了確保原子操作的技巧和策略，只適用於rollback mode。如果資料庫在WAL mode下運行，策略和這篇文章不同。
2. 對硬體的假設
   1. 硬碟寫入的最小單位是扇區(sector)。
      不能修改小於一個扇區的數據。如果需要的話，應該讀出整個扇區，然後修改一部分，再把整個扇區寫入。
      扇區的大小在3.3.14以前，在代碼中寫死是512位元組。隨著硬體的發展，扇區的大小發展到4k位元組了。因此在3.3.15以後開始的版本中，提供了一個函數和文件系統打交道，用來獲取扇區的大小。然而由於unix和Windows系統中不會返迴文件扇區的大小，因此這個函數仍然返回512位元組。不過這個函數可以在嵌入式系統中起作用。
      
   2. 對扇區的寫操作不是原子的，卻是線性的。
      這裡線性的意思是開始寫操作時，會從扇區的一端開始，一比特一比特地寫，直到扇區的另一端。寫操作的方向可以是從扇區起始到結束，也可以從扇區的結束到起始。如果在寫操作的過程中，系統掉電了，那麼這個扇區會一部分已經改變，一部分仍然沒改變。
      SQLite假設的關鍵是如果扇區的一部分發生了改變，那麼在扇區的起始或結束一定會發生變化。
      在3.5.0以後的版本中，新增了一個VFS（虛擬文件系統）的介面。VFS是SQLite和文件系統交互的唯一介面。SQLite為Unix和Windows提供了預設的VFS實現，並且可以讓用戶在運行時實現一個自定義的VFS實現。
      VFS介面中，有一個函數叫做xDeviceCharacteristics。這個函數和文件系統交互，並提供文件系統的一些特性，比如扇區寫操作是否是原子的。如果這個扇區寫操作時原子的，那麼SQLite會利用這些特性。然而Unix和Windows預設的xDeviceCharacteristics函數不會提供這些信息。
   3. 操作系統會對文件寫操作進行緩衝。
      因此在寫操作的請求返回時，數據還沒有真實寫入資料庫文件中。此外，還假設操作系統會對寫操作進行reorder。
      因此，SQLite會在關鍵點調用flush或fsync操作。SQLite假設這個操作在數據被寫入文件之前不會返回。
      然而，有一些Windows版本和Unix版本的fluse或fsync操作不是這樣子的。這樣子，在commit的過程中發生掉電，會導致資料庫文件損壞。
   4. 文件size的變化發生在內容變化之前。
      也就是說文件的大小先發生改變，這樣子文件會包含一些垃圾數據，然後會將數據寫入文件。
      寫入文件大小之後，寫入數據之前會發生掉電。SQLite做了一些其他的工作來保證這種情況下不會引起資料庫文件損壞。
      如果VFS的xDeviceCharacteristics方法確定在改變文件大小之前，數據已經被寫入到文件中，那麼SQLite會利用這個特性。然而預設的實現沒有確認這個特性。
   5. 文件的刪除是原子的
      文件在刪除的過程中掉電，那麼重啟之後，文件要麼完全沒有刪除，或者完全刪除。
      如果重啟之後，文件只有部分使被刪除的，那麼會損壞資料庫。
   6. Powersafe Overwrite 當程式寫數據到文件中時，在所寫範圍之外的數據不會被改變，即使發生了crash或掉電。
      假設不成立的情況：如果寫操作只發生了扇區的前幾個位元組。由於寫操作的最小單位是扇區。寫完前幾個位元組以後就掉電，重啟時，對這個扇區內的數據進行校驗，發現不對，就會用全0或者全1進行覆蓋。這樣子就修改了寫操作範圍以外的數據。
      現代的磁碟可以檢測到掉電，然後會利用剩餘的電量將這個扇區的數據寫完。

3. 單個文件commit過程

   1. 初始狀態
      中間部分是系統的磁碟緩衝區。
      

   2. 獲取讀鎖
      在寫操作之前需要獲取讀鎖，獲取資料庫的基本數據，這樣子才能解析SQL語句。
      註意共用鎖只針對系統的磁碟緩存，而不是磁碟文件。文件鎖其實就是系統內核的一些flag。在系統crash或掉電之後，鎖會失效。通常創建鎖的進程退出也會導致鎖失效。
      

   3. 從資料庫中讀數據
      先讀到系統磁碟緩存，再讀到用戶空間。如果命中了緩存，那麼會直接從磁碟緩存中讀到用戶空間。
      
      註意不是把整個資料庫讀入記憶體。
      

   4. 獲取reserved lock
      在對資料庫進行改變之前，要先獲取reserved lock。允許其他擁有共用讀鎖的進程操作，但是一個資料庫文件只能有要給reserved lock。保證了只有同時最多一個進程可以進行資料庫寫操作。
      

   5. 創建回滾日誌文件
      日誌文件就是要改變的資料庫文件中原有的page。
      此外還包括一個頭部，記錄了原有資料庫文件的大小。page的number被寫入到了每一個資料庫的page中。
      註意此時並沒有寫文件到磁碟中。
      

   6. 在用戶空間改變資料庫的page
      每一個資料庫鏈接都有自己的資料庫文件拷貝。所以，此時其他資料庫連接仍然可以正常進行讀操作。
      

   7. 把日誌文件刷入磁碟中
      在大多數系統中，需要進行兩次flush或fsync操作。第一次將文件數據刷入文件中，第二次用來更改header中的記錄日誌文件的page數目，並把header刷入文件。
      

   8. 獲取exclusive鎖
      獲取exclusive鎖分兩步。首先獲取一個pending鎖，保證不會有新的寫操作和讀操作。然後等待其他的讀進程結束，釋放讀鎖，最後獲取exclusive鎖。
      

   9. 將用戶空間中的數據寫入資料庫文件
      此時可以確定沒有其他資料庫連接在從資料庫中讀文件。這一步通常只會寫入到磁碟緩存中，不會寫到資料庫文件。
      

   10. 將更改寫入磁碟文件中
       調用fsync或flush操作。這一部和寫日誌文件到磁碟中占用了一個transaction中最多的時間。
       

   11. 刪除日誌文件

       SQLite gives the appearance of having made no changes to the database file or having made the complete set of changes to the database file depending on whether or not the rollback journal file exists.

       刪除日誌文件不是原子的，但是從用戶看來，這個操作是原子的。詢問操作系統這個文件是否存在，回答是yes或no。
       在一些系統中，刪除文件時一個耗時的操作。SQLite可以配置為將文件的大小改為0或用0來覆蓋日誌文件的頭部。在這兩種情況下，日誌文件都不可能進行恢復，因此SQLite認為commit已經完成。
       

   12. 釋放鎖
       在這張圖裡，用戶空間的資料庫內容已經被清空。在最新版本中，做了優化。在資料庫第一個page中，維護了一個計數器，每一次寫操作，都會對這個計數器加一。如果計數器不變，這個資料庫連接就可以重覆利用用戶空間中的資料庫內容。
       

4. 回滾
   由於一個commit操作需要時間。在這個過程中，如果發生了crash或掉電，就需要進行回滾以保證資料庫事務的完成是『瞬時』的。利用資料庫日誌文件回滾到這個資料庫事務發生之前。

   1. 初始情況 假設在第10步時，發生了斷電。在重啟之後，資料庫文件其實只寫入了1個半page，但是我們有完整的journal文件。 
   2. hot rollback journal 當一個新的資料庫連接建立時，會嘗試獲取共用read鎖，也會註意到有一個回滾用的日誌文件。接下來這個資料庫連接就會檢驗這個資料庫文件是不是"hot journal"。當一個事務在commit時發生掉電或者crash，就會產生"hot journal"。 判斷標準如下：
      • 存在回滾日誌文件
      • 回滾日誌文件不是空文件
      • 在資料庫文件中不存在reserved lock（掉電以後會丟失）
      • 日誌文件的頭部格式沒有被破壞
      • 日誌文件中不包含主日誌文件的名字（用戶多個文件提交） 或包含主日誌文件，主日誌文件存在 有了日誌文件，我們就可以來恢複數據庫。
   3. 獲取exclusive鎖 用來防止其他進程同時用這個日誌文件回滾資料庫。
   4. 回滾沒有完成的變更 把日誌文件從磁碟文件中讀入記憶體，然後寫入資料庫。 日誌文件頭部存儲了原來資料庫的大小信息。如果原有的操作使得資料庫文件變大，這個信息用來截斷資料庫。 這一步之後，資料庫的大小、內容都和這個事務發生之前是一致的。 
   5. 刪除hot journal 也可能大小被改為0，也可能文件的header用0覆蓋。總之，不在是hot journal了。 
   6. 繼續進行其他操作
      此時資料庫文件已經恢復正常，可以正常使用了。

5. 多文件提交

6. commit過程的重要細節

   1. 總是記錄整個扇區
      如果page的大小是1k，扇區的大小是4k。為了更改某一個page的數據，必須把整個扇區的數據計入日誌文件；寫數據到資料庫文件時，也必須將整個扇區寫入。
   2. 處理寫日誌文件時的垃圾數據
      在向資料庫日誌文件追加數據是，SQLite假設資料庫日誌文件的size會先變大，然後才會寫入數據。如果在這兩步之間發生了掉電，那麼日誌文件中會留有垃圾數據。如果利用這個日誌文件進行恢復，就覆蓋原有資料庫中的正確內容。
      SQLite使用兩種策略來應對這種情況。
      1. 在日誌文件的頭部加入日誌中page的數目
         把日誌文件的page數據寫入頭部，初始值是0。因此利用不完整的日誌文件進行回滾時，會發現頭部是0，也就不會進行任何操作。
         在commit之前，日誌文件的內容會被刷入磁碟中，並保證沒有垃圾數據。此時，才會將日誌文件中page的數目再次刷入磁碟。日誌文件頭和文件中的page不在同一個扇區，因此即使掉電，也不會破壞日誌文件中的page。
         上面說的情況僅僅發生在"synchronous pragma"是FULL。如果是normal，那麼page的數目和page的內容會同步刷入磁碟文件。即使在代碼中先刷入page的內容，再刷入page的數目，由於系統會改變操作順序，也有可能會導致page的數目正確寫入了磁碟，page的內容卻沒有被正確寫入磁碟。
      2. 每一個page使用校驗和
         SQLite在每一個page都準備了一個32bit的校驗和。如果有一個page的校驗和不滿足，那麼整個回滾過程就不進行。
         如果synchronous pragma是FULL，理論上就不需要校驗和。然而檢驗和是沒有副作用的，因此無論synchronous pragma是什麼，在日誌文件中都有校驗和的存在。
   3. 提交前緩存溢出
      如果提交前，修改的內容已經超過了用戶空間的緩存，那麼必須先把已經完成的操作寫入資料庫文件中，再進行其他操作。
      緩存溢出會將reserved鎖提升為exclusive鎖，因此降低了併發性。還有引起額外的flush或fsync操作，這些操作是十分耗時的。要儘量避免緩存溢出。

7. 優化
   性能分析表示SQLite將大多數時間花費在了磁碟IO。因此如果可以減少磁碟IO的話，就可以提升SQLite的性能。下麵介紹一些SQLite採用的在保證事務原子性的前提下提升性能的一些方法。

   1. 在事務之間緩存
      舊版本的SQLite中，在事務結束以後，會把SQLite的內容從用戶空間中移除。原因是因為其他操作會改變資料庫的內容。下次讀取相同的內容時，仍然需要從磁碟緩存或磁碟中讀數據到用戶空間。
      在新版本(3.3.14)之後，用戶控制項內的資料庫緩存會保留。同時在資料庫的header(24到27位元組)中維護計數器，每次改變加一。下次這個進程讀取資料庫時，只需要判斷是否計數器有變化，如果沒有變化，那麼使用緩存即可。
   2. 獨享訪問模式
      3.3.14版本之後新增，即資料庫只能被一個進程訪問（適合iOS）。在這個模式下，有以下優點。
      1. 在事務結束之後不必改變資料庫header中的計數器。為日誌文件和資料庫主文件減少一個文件寫入。
      2. 在事務開始和結束時不必檢測header中的計數器，也不必清空緩存。
      3. 事務結束後，可以覆蓋日誌文件header的方法而不是刪除日誌文件。減少了一些文件操作，比如更改資料庫文件的目錄項、釋放日誌文件對應的磁碟扇區等。
   3. 不將空閑頁記錄到日誌文件中（3.5.0以後新增）
      當從資料庫中刪除信息時，會將原本記錄被刪除內容的page計入空白列表(freelist)中。當後續有新增操作時，會從空白列表中取數據，而不是擴展資料庫文件。
      一些空閑頁中包含重要信息，比如其他空閑頁的位置。但是大部分空閑頁不包含有用信息，被稱為葉子（leaf）空閑頁（我理解是空閑頁用樹來存儲，空閑頁即葉子節點）。
      葉子空閑頁是不重要的，因此SQLite避免將空閑頁寫入日誌文件中，可以大大減少IO數目
   4. 單頁更新和原子扇區寫
      現代磁碟一般都可以保證對單個扇區的寫是原子的。當掉電時，磁碟可以利用電容中的電量或磁碟轉動的角動量完成當前扇區的寫操作。
      假如扇區的寫是原子的，資料庫page的大小和扇區的大小是一致的，並且資料庫的寫操作只涉及一個page，那麼資料庫會跳過所有的日誌及刷新操作，直接將更改的內容寫入資料庫文件。
      資料庫首頁的變更計數器會被單獨修改，因為不會對資料庫有任何影響，即使在計數器更新之前發生了掉電。
   5. 安全追加(Safe Append)的文件系統（3.5.0以後新增）
      SQLite假設當追加數據到文件時，文件的大小先改變，然後內容才改變。這樣子掉電以後會導致日誌文件中包含垃圾數據。
      如果文件系統支持文件的size更新以前，文件的content一定已經更新，那麼在掉電或者系統crash以後，日誌文件也不會有垃圾數據。
      為了支持這種文件系統，SQLite在日誌文件的頭部用來存儲page數目的地方存儲-1。SQLite使用文件的size來計算文件中page的數目。
      當commit時，我們節省了一次flush或fsync操作。此外，當緩存溢出時，不必將新的page數目寫入資料庫日誌文件
   6. 持久的日誌文件
      即在資料庫事務結束時不刪除日誌文件，這樣子可以節省一次文件刪除和一次文件創建的工作。
      啟用方法PRAGMA journal_mode=PERSIST;
      這樣子會導致一直有資料庫日誌文件存在。 還可以把mode設為TRUNCATE，PRAGMA journal_mode=TRUNCATE;
      PERSIST是把日誌文件的頭部置為0，以後的對資料庫文件的操作是覆蓋。TRUNCATE是把日誌文件的size置為0，不需要調用fsync操作，以後對資料庫文件的操作是append。 在具有同步文件系統的嵌入式系統中，append操作比overrite慢一些，因此TRUNCATE會導致比PERSIST較慢的行為。

8. 測試提交行為原子性

9. 導致資料庫損壞的可能性

   1. 不正確的鎖實現
      在網路操作系統中，實現鎖機制是很困難的。因此，儘量不要在網路操作系統中使用SQLite。
      當使用不同的鎖機制來獲取同一個文件，而這兩種鎖機制又不是互斥時，也會發生錯誤。
   2. 不完整的磁碟刷新
      Unix上的fsync()系統調用或Windows上的FlushFileBuffers()調用工作不正常。
   3. 部分文件被刪除
      SQLite假設文件的刪除是原子的。如果SQLite刪除的文件在掉電重啟以後部分恢復，就會發生故障。
   4. 被寫入垃圾數據
      其他程式可以向SQLite文件中寫入垃圾數據。
      操作系統的bug。
   5. 刪除或重命名hot journal

10. 總結及未來的路