BTT - 塊轉換表

1. 簡介

基於持久記憶體的儲存能夠以位元組（或更準確地說，快取行）粒度執行 IO。 但是，我們經常希望將此類儲存公開為傳統塊裝置。 持久記憶體的塊驅動程式將完全做到這一點。 但是，它們不提供任何原子性保證。 傳統的 SSD 通常在硬體中提供針對扇區撕裂的保護，使用電容器中儲存的能量來完成正在進行的塊寫入，或者可能在韌體中。 我們沒有持久記憶體的這種奢侈 - 如果寫入正在進行中，並且我們遇到電源故障，則該塊將包含新舊資料的混合。 應用程式可能沒有準備好處理這種情況。

塊轉換表 (BTT) 為持久記憶體裝置提供原子扇區更新語義，以便依賴於扇區寫入不被撕裂的應用程式可以繼續這樣做。 BTT 將自身表現為堆疊的塊裝置，併為元資料保留部分底層儲存。 其核心是一個間接表，用於重新對映捲上的所有塊。 它可以被認為是一個極其簡單的檔案系統，僅提供原子扇區更新。

2. 靜態佈局

可以佈置 BTT 的底層儲存在任何方面都不受限制。 但是，BTT 將可用空間分成最大 512 GiB 的塊，稱為“Arenas”。

每個 arena 對其元資料採用相同的佈局，並且 arena 中的所有引用都是內部的（除了指向下一個 arena 的一個欄位）。 以下描述了“磁碟上”元資料佈局

  Backing Store     +------->  Arena
+---------------+   |   +------------------+
|               |   |   | Arena info block |
|    Arena 0    +---+   |       4K         |
|     512G      |       +------------------+
|               |       |                  |
+---------------+       |                  |
|               |       |                  |
|    Arena 1    |       |   Data Blocks    |
|     512G      |       |                  |
|               |       |                  |
+---------------+       |                  |
|       .       |       |                  |
|       .       |       |                  |
|       .       |       |                  |
|               |       |                  |
|               |       |                  |
+---------------+       +------------------+
                        |                  |
                        |     BTT Map      |
                        |                  |
                        |                  |
                        +------------------+
                        |                  |
                        |     BTT Flog     |
                        |                  |
                        +------------------+
                        | Info block copy  |
                        |       4K         |
                        +------------------+

3. 操作理論

a. BTT 對映

對映是一個簡單的查詢/間接表，將 LBA 對映到內部塊。 每個對映條目為 32 位。 兩個最高有效位是特殊標誌，其餘位形成內部塊號。

位

描述

31 - 30

錯誤和零標誌 - 以下列方式使用

== ==  ====================================================
31 30  Description
== ==  ====================================================
0  0   Initial state. Reads return zeroes; Premap = Postmap
0  1   Zero state: Reads return zeroes
1  0   Error state: Reads fail; Writes clear 'E' bit
1  1   Normal Block – has valid postmap
== ==  ====================================================

29 - 0

對映到內部“postmap”塊

隨後將使用的一些術語

外部 LBA

LBA 向上層公開。

ABA

Arena 塊地址 - arena 中的塊偏移量/編號

Premap ABA

arena 中的塊偏移量，這是透過範圍檢查外部 LBA 決定的

Postmap ABA

從對映間接定址後在“資料塊”區域中獲得的塊號

nfree

在任何給定時間維護的空閒塊數。 這是可以對 arena 進行的併發寫入次數。

例如，在新增 BTT 之後，我們浮現一個 1024G 的磁碟。 我們得到對 768G 處外部 LBA 的讀取。 這屬於第二個 arena，並且在這個 arena 貢獻的 512G 塊中，這個塊位於 256G。 因此，premap ABA 是 256G。 我們現在參考對映，並找出塊 'X' (256G) 的對映指向塊 'Y'，例如 '64'。 因此，postmap ABA 是 64。

b. BTT Flog

BTT 透過使每次寫入都成為“分配寫入”來提供扇區原子性，即每次寫入都轉到“空閒”塊。 空閒塊的執行列表以 BTT flog 的形式維護。 ‘Flog’ 是 “free list” 和 “log” 這兩個詞的組合。 flog 包含 ‘nfree’ 個條目，一個條目包含

lba

正在寫入的 premap ABA

old_map

舊的 postmap ABA - 在 'this' 寫入完成後，這將是一個空閒塊。

new_map

新的 postmap ABA。 對映將更新以反映此 lba->postmap_aba 對映，但我們在此處記錄它，以防我們需要恢復。

seq

序列號，用於標記此 flog 條目的 2 個部分中的哪一個有效/最新。 它在正常操作下在 01->10->11->01 (二進位制) 之間迴圈，00 表示未初始化狀態。

lba’

備用 lba 條目

old_map’

備用舊的 postmap 條目

new_map’

備用新的 postmap 條目

seq’

備用序列號。

上述每個欄位都是 32 位，使一個條目成為 32 位元組。 條目也被填充到 64 位元組以避免快取行共享或別名。 Flog 更新的完成方式是，對於正在寫入的任何條目，它： a. 根據序列號覆蓋條目中的“舊”部分 b. 寫入“新”部分，使得序列號最後寫入。

c. 通道的概念

雖然 'nfree' 描述了一個 arena 可以併發處理的併發 IO 的數量，但 'nlanes' 是整個 BTT 裝置可以處理的 IO 的數量

nlanes = min(nfree, num_cpus)

在任何 IO 開始時都會獲得一個通道號，並且在 IO 的持續時間內用於索引所有磁碟上和記憶體中的資料結構。 如果 CPU 的數量多於可用通道的最大數量，那麼通道會受到自旋鎖的保護。

d. 記憶體資料結構：讀取跟蹤表 (RTT)

考慮這樣一種情況：我們有兩個執行緒，一個進行讀取，另一個進行寫入。 我們可以遇到這樣一種情況：寫入器執行緒獲取一個空閒塊來執行新的 IO，但（慢速）讀取器執行緒仍在從中讀取。 換句話說，讀取器查閱了一個對映條目，並開始讀取相應的塊。 寫入器開始寫入相同的外部 LBA，並完成了寫入，更新了該外部 LBA 的對映以指向其新的 postmap ABA。 此時，讀取器（仍然）正在讀取的內部 postmap 塊已插入到空閒塊列表中。 如果另一個寫入進入相同的 LBA，它可以獲取此空閒塊，並開始寫入它，導致讀取器讀取不正確的資料。 為了防止這種情況，我們引入了 RTT。

RTT 是一個簡單的、每個 arena 的表，具有 ‘nfree’ 個條目。 每個讀取器都將其正在讀取的 postmap ABA 插入到 rtt[lane_number] 中，並在讀取完成後清除它。 每個寫入器執行緒在獲取空閒塊後，都會檢查 RTT 中是否存在它。 如果 postmap 空閒塊位於 RTT 中，它將等待直到讀取器清除 RTT 條目，然後才開始寫入它。

e. 記憶體資料結構：對映鎖

考慮這樣一種情況：兩個寫入器執行緒正在寫入相同的 LBA。 在以下步驟序列中可能存在競爭

free[lane] = map[premap_aba]
map[premap_aba] = postmap_aba

兩個執行緒都可以使用相同的舊的、釋放的 postmap_aba 更新它們各自的 free[lane]。 這透過丟失一個空閒條目並同時為兩個通道複製另一個空閒條目使佈局不一致。

為了解決這個問題，我們可以有一個（每個 arena 的）單個對映鎖，必須在執行上述序列之前獲取它，但我們認為這可能太有爭議了。 相反，我們使用一個 (nfree) map_locks 的陣列，該陣列由 (premap_aba modulo nfree) 索引。

f. 從 Flog 重建

在啟動時，我們分析 BTT flog 以建立我們的空閒塊列表。 我們遍歷所有條目，並且對於每個通道，在兩個可能的“部分”的集合中，我們始終只檢視最新的一個（基於序列號）。 重建規則/步驟很簡單

  • 讀取 map[log_entry.lba]。

  • 如果 log_entry.new 與對映條目匹配，則 log_entry.old 是空閒的。

  • 如果 log_entry.new 與對映條目不匹配，則 log_entry.new 是空閒的。 （這種情況只能由電源故障/不安全關機引起）

g. 總結 - 讀取和寫入流程

讀取

  1. 將外部 LBA 轉換為 arena 編號 + pre-map ABA

  2. 獲取通道（並獲取 lane_lock）

  3. 讀取對映以獲取此 pre-map ABA 的條目

  4. 將 post-map ABA 輸入到 RTT[lane] 中

  5. 如果在對映中設定了 TRIM 標誌，則返回零並結束 IO（轉到步驟 8）

  6. 如果在對映中設定了 ERROR 標誌，則以 EIO 結束 IO（轉到步驟 8）

  7. 從此塊讀取資料

  8. 從 RTT[lane] 中刪除 post-map ABA 條目

  9. 釋放通道（和 lane_lock）

寫入

  1. 將外部 LBA 轉換為 Arena 編號 + pre-map ABA

  2. 獲取通道（並獲取 lane_lock）

  3. 使用通道索引到記憶體中的空閒列表並獲得一個新塊、下一個 flog 索引、下一個序列號

  4. 掃描 RTT 以檢查是否存在空閒塊，如果存在，則旋轉/等待。

  5. 將資料寫入此空閒塊

  6. 讀取對映以獲取此 pre-map ABA 的現有 post-map ABA 條目

  7. 寫入 flog 條目：[premap_aba / old postmap_aba / new postmap_aba / seq_num]

  8. 將新的 post-map ABA 寫入對映。

  9. 將舊的 post-map 條目寫入空閒列表

  10. 計算下一個序列號並寫入空閒列表條目

  11. 釋放通道（和 lane_lock）

4. 錯誤處理

如果任何元資料因錯誤或介質錯誤而無法恢復地損壞，則 arena 將處於錯誤狀態。 以下條件指示錯誤

  • Info 塊校驗和不匹配（並且從副本恢復也失敗）

  • 所有內部可用塊都不能被對映塊和空閒塊（來自 BTT flog）的總和唯一且完全地定址。

  • 從 flog 重建空閒列表會顯示缺少/重複/不可能的條目

  • 對映條目超出範圍

如果遇到任何這些錯誤情況，則使用 info 塊中的標誌將 arena 置於只讀狀態。

5. 用法

BTT 可以在 libnvdimm 子系統（pmem 或 blk 模式）公開的任何磁碟（名稱空間）上設定。 設定此類名稱空間的最簡單方法是使用 ‘ndctl’ 實用程式 [1]

例如，用於設定扇區大小為 4k 的 btt 的 ndctl 命令列是

ndctl create-namespace -f -e namespace0.0 -m sector -l 4k

有關更多選項，請參閱 ndctl create-namespace --help。

[1]: https://github.com/pmem/ndctl