天天看點

leveldb源碼分析之log檔案結構理論基礎

log檔案在LevelDb中的主要作用是系統故障恢複時,能夠保證不會丢失資料。因為在将記錄寫入記憶體的Memtable之前,會先寫入Log檔案,這樣即使系統發生故障,Memtable中的資料沒有來得及Dump到磁盤的SSTable檔案,LevelDB也可以根據log檔案恢複記憶體的Memtable資料結構内容,不會造成系統丢失資料.

leveldb源碼分析之log檔案結構理論基礎

LevelDb對于一個log檔案,會把它切割成以32K為機關的實體Block,每次讀取的機關以一個Block作為基本讀取機關,下圖展示的log檔案由3個Block構成,是以從實體布局來講,一個log檔案就是由連續的32K大小Block構成的

leveldb源碼分析之log檔案結構理論基礎

在應用的視野裡是看不到這些Block的,應用看到的是一系列的Key:Value對,在LevelDb内部,會将一個Key:Value對看做一條記錄的資料,另外在這個資料前增加一個記錄頭,用來記載一些管理資訊,以友善内部處理,圖3.2顯示了一個記錄在LevelDb内部是如何表示的。 記錄頭包含三個字段,ChechSum是對“類型”和“資料”字段的校驗碼,為了避免處理不完整或者是被破壞的資料,當LevelDb讀取記錄資料時候會對資料進行校驗,如果發現和存儲的CheckSum相同,說明資料完整無破壞,可以繼續後續流程。“記錄長度”記載了資料的大小,“資料”則是上面講的Key:Value數值對,“類型”字段則指出了每條記錄的邏輯結構和log檔案實體分塊結構之間的關系,具體而言,主要有以下四種類型:FULL/FIRST/MIDDLE/LAST

CheckSum,即CRC驗證碼,占4個位元組
記錄長度,即資料部分的長度,2個位元組
類型,這條記錄的類型,後續講解,1個位元組
資料,就是這條記錄的資料。
           

如果記錄類型是FULL,代表了目前記錄内容完整地存儲在一個實體Block裡,沒有被不同的實體Block切割開;如果記錄被相鄰的實體Block切割開,則類型會是其他三種類型中的一種。

結合上面的分析,整個log結構如下:

leveldb源碼分析之log檔案結構理論基礎

LevelDB 的 log 檔案内容被組織成多個 32 KB 的定長塊(block)。每個 block 由 1~多個 record 組成(末尾可能會 padding)。一個 record 由一個固定 7 位元組的 header(checksum: uint32 + length: uint16 + type: uint8) 和實際資料(data: uint8[length])組成。

如果 block 的末尾不足 7 位元組(小于 header 的大小),則全部填 0x00,讀取的時候會被忽略。

如果 block 的末尾剛好 7 位元組,則填充一個 length 為 0 的 record。

下面,我們将上層寫入的資料稱之為 user record,以區分 block 中的 record。由于 block 是定長的,而 user record 是變長的,一個 user record 有可能被截斷成多個 record,儲存到一段連續的 block 中。是以,在 header 中有一個 type 字段用來表示 record 的類型:

下面以一個例子來解釋上面的過程。

初始化整個 log 為空,假設我們有 3 個 user records:

  • A 大小為 1000 位元組
  • B 大小為 97270 位元組
  • C 大小為 8000 位元組

    A 小于 32KB,會被儲存到第一個 block,長度為 1000,類型為 kFullType,占用空間為 7 + 1000 = 1007。

B 比較大,會被切分成 3 個分片,儲存到不同的 block:

第一個分片儲存到第一個 block,長度為 31754 位元組,類型為 kFirstType。因為儲存 A 之後,這個 block 剩餘的空間為 32768 - 7 - 1000 = 31761 位元組。除去 header,可以儲存 B 的前 31761 - 7 = 31754 位元組。此時 B 還有 97270 - 31754 = 65516 位元組需要儲存。

65516 位元組超過了一個 block 的大小,是以第二個分片需要完整占用第二個 block,長度為 32768 - 7 = 32761 位元組,類型為 kMiddleType。此時 B 還有 65516 - 32761 = 32755 位元組需要儲存。

B 的第三個分片儲存到第三個 block ,長度為 32755,類型為 kLastType。第三個 block 剩餘的空間為 32768 - 7 - 32755 = 6 位元組。由于 6 位元組小于一個 header 的大小(7 位元組),會被進行 padding(填 0)。

C 會被儲存到第四個 block,長度為 8000 位元組,類型為 kFullType,占用空間 7 + 8000 = 8007。

綜上,A、B、C 在 log 檔案中的結構如下。

leveldb源碼分析之log檔案結構理論基礎

LevelDB 為什麼采用這種定長塊的方式儲存日志呢?一個明顯的好處就是,當日志檔案發生資料損壞的時候,這種定長塊的模式可以很簡單地跳過有問題的塊,而不會導緻局部的錯誤影響到整個檔案。