前言

前段時間有幸跟 NOVA 的作者 Jian Xu 博士深入交流了一番灸促，受益頗多，決定趁熱打鐵，好好研究一下 NOVA，一方面可以知道在 Linux 下面如何開發(fā)一個文件系統(tǒng)凑懂，而另一方面，則是想了解下當前硬件的發(fā)展水平瞳别，以及為了更好的發(fā)回硬件性能征候，我們需要做什么，算是對未來做一些技術(shù)調(diào)研和儲備工作祟敛。

NOVA 是一個支持混合 Volatile/Non-volatile main memories 的文件系統(tǒng)，volatile main memory 其實 我們很容易理解兆解，就是我們通常說的 DRAM馆铁。而 Non-volatile main memory （NVM） 則可以認為是跟 DRAM 有一樣的性能（可能還是稍微比 DRAM 慢一點），但能進行數(shù)據(jù)持久化的技術(shù)锅睛，譬如我司現(xiàn)在就有十塊基于 NVM 技術(shù)的 3D XPoint 盤埠巨，如果有同學對這塊感興趣历谍，想嘗試下為最近硬件設(shè)計程序，歡迎聯(lián)系我辣垒。

NVM 預計很快就會跟 DRAM 一樣望侈，出現(xiàn)在處理器內(nèi)存總線上面，所以融合 DRAM 和 NVMM 的特性勋桶，設(shè)計出一套更好的存儲系統(tǒng)脱衙，我認為是有必要的。現(xiàn)階段例驹，傳統(tǒng)的文件系統(tǒng)捐韩，譬如 XFS，ext4 并不能和好的工作于這種混存架構(gòu)上面鹃锈，所以徐博士他們就設(shè)計了一個 Non-Volatile memory Accelerated (NOVA) 的文件系統(tǒng)荤胁。

這里，再說一點小插曲屎债，我開始以為 NVMM 和 NVMe 是一樣的東西仅政，于是問了徐博士這個問題，結(jié)果他告訴我兩個是不一樣的盆驹，真的是差之毫厘謬以千里圆丹，看來我在硬件上面的知識積累不足，后面需要多跟徐博士他們這些牛人請教召娜。

NVMM

在開始討論 NOVA 之前运褪，我們可以先說說 NVMM，NVMM 這種新的硬件體系給文件系統(tǒng)的設(shè)計帶來了新的挑戰(zhàn)玖瘸，主要有幾個方面：

• 性能：NVMM 的性能非常的好秸讹，延遲非常的低。NVMM 甚至提供了 Direct Access (DAX) 或者其他方式來直接操作數(shù)據(jù)雅倒，不需要將數(shù)據(jù)拷貝到 DRAM 上面璃诀。之前的存儲系統(tǒng)，會認為延遲的主要開銷在于硬件蔑匣，但現(xiàn)在劣欢，很可能主要開銷會出現(xiàn)在軟件層面上面。
• 寫入重排：現(xiàn)代的處理器和它們的緩存可能會為了性能將存儲指令重新排列裁良。而對于 DRAM 來說凿将，CPU 是能夠保證一致性的，但對于 NVMM 卻沒有這樣的保證价脾。雖然我們可以強制 flush 緩存以及是所有內(nèi)存屏障來保證寫入順序牧抵，但 clflush 會極大的降低性能，而 mfence 并不能保證寫回到 NVMM 的順序。幸運的是犀变，Intel 已經(jīng)開發(fā)了新的指令集 clfushopt妹孙， clwb，PCOMMIT获枝，而 NOVA 就是基于這些新的指令集的蠢正。（跟徐博士聊天順帶問了下 AMD 是否也有了類似的指令集，他回答『不確定省店，不過應(yīng)該是有了』）嚣崭。
• 原子性：POSIX 類型的文件系統(tǒng)在很多操作上面都需要保證原子性，譬如 rename 這些萨西，但這些操作很多會涉及到多個數(shù)據(jù)的修改有鹿，譬如 append file 這種的既要更改文件數(shù)據(jù)，也需要更改文件元信息谎脯，而 NVMM 只能提供 64 bits 的原子性保證葱跋，這對于原子性的設(shè)計是一個很大的挑戰(zhàn)。

通常文件系統(tǒng)實現(xiàn)原子性有幾種方式：

• Journaling：這個應(yīng)該算是最常見的做法了源梭，不光是傳統(tǒng)的文件系統(tǒng)還有很多數(shù)據(jù)庫娱俺，很多都采用的是這種做法。任何更新操作先寫到 log废麻，然后在寫到實際的位置荠卷，當然這種寫兩份的策略并不高效，所以也有很多的優(yōu)化方法烛愧，譬如只在 journaling 上面更新 metadata油宜。
• Shadow paging：還有一些文件系統(tǒng)使用的是 Copy-On-Write 機制，對于更新操作不是直接寫到之前的 page 上面怜姿，而是先寫到另一個 page 上面慎冤，在將這個新的 page 加入到文件系統(tǒng)的 tree 里面，這里就需要涉及到對 tree 上面的 node 的更新沧卢，而有時候蚁堤，我們需要將新 page 到 root 的所有 node 都更新一遍，這個開銷還是挺大的但狭。
• Log-structuring：雖然結(jié)構(gòu)化日志很早就有披诗，但我第一次被震撼到還是遇到了 LevelDB 的時候，它通過這種方式將隨機寫變成了文件的順序追加立磁。對于文件系統(tǒng)來說呈队，其實也是一樣的原理，但這些文件系統(tǒng)為了保證順序追加唱歧，可能需要連續(xù)的可用存儲空間掂咒，同時也需要定期的去清理過期的數(shù)據(jù)，釋放空間迈喉，這些都可能造成開銷绍刮。

設(shè)計

現(xiàn)階段，基于 NVMM 的文件系統(tǒng)已經(jīng)有不少了挨摸，譬如 Ext4-DAX（感覺原生的 Ext4 應(yīng)該是不適用與 NVMM 的）孩革，它采用的是 Journaling 的方式，但只保證 metadata 的更新原子性得运，并沒有保證數(shù)據(jù)的膝蜈。

而 NOVA 是一個使用 log-structuring 的文件系統(tǒng)，但為了更好的利用 NVMM熔掺，NOVA 并沒有直接使用傳統(tǒng)的 log-structuring 的方式饱搏，而且做了改進。徐博士他們在做 NOVA 的時候置逻，發(fā)現(xiàn)幾個現(xiàn)象：

1. 支持原子更新的 log 很容易實現(xiàn)推沸，但要高效的查出相關(guān)的操作其實并不容易。而要在 NVMM 里面實現(xiàn)一個支持高效搜索的數(shù)據(jù)結(jié)構(gòu)券坞，也是比較困難的鬓催。
2. 傳統(tǒng)的 log-structuring 文件系統(tǒng)連續(xù)的存儲空間，但這個對于 NVMM 來說沒有這個必要恨锚，因為它的隨機訪問速度太快了宇驾。
3. 傳統(tǒng)的 log-structuring 會采用單一 log 的方式，雖然會影響并發(fā)性能猴伶，但考慮到 disk 仍然是性能主要瓶頸课舍，其實也無所謂。但在 NVMM 上面他挎，快速筝尾，高并發(fā)的隨機存取操作是完全沒問題了，所以我們可以使用多個 log雇盖。

觀察到以上現(xiàn)象之后忿等，NOVA 就做了如下設(shè)計：

1. 將 Log 保存在 NVMM 里面，而索引則保存在 DRAM崔挖。索引使用的是 radix tree 來實現(xiàn)的贸街，這個我問過徐博士，為啥選擇這個數(shù)據(jù)結(jié)果狸相，給我的答復是 kernel 里面就沒幾個數(shù)據(jù)結(jié)構(gòu)薛匪，他們又不想自己寫，就拿了一個現(xiàn)成可用的脓鹃。
2. 每一個 inode 有一個 log逸尖。這個就是充分利用 NVMM 的隨機存取高效的特性了，而且每個 inode 一個 log，不會存在并發(fā)的問題娇跟。
3. 使用 logging 和輕量級的 journaling 來進行復雜的原子更新岩齿。譬如一個文件從一個目錄 move 到另一個目錄，這設(shè)計到多個 inode 的修改苞俘，NOVA 會首先將操作記錄到 inode 的 log 上面盹沈，然后在 journal 上面記錄對應(yīng)的 log tail 的改動，最后在將 log tail 更新吃谣。NOVA 的 journaling 只會記錄 log tail乞封，并且任何 POSIX 的文件操作涉及到的 inode 不會超過 4 個，所以 journaling 是非常輕量的岗憋。這里肃晚，我同時問了徐博士，這已經(jīng)涉及到了幾個 inode仔戈，如何保證并發(fā)关串，他回答道 Linux VFS 其實已經(jīng)保證了，所以他們不需要做杂穷。
4. 使用鏈表的方式實現(xiàn)了 log悍缠，NOVA 使用的是 4 KB 的 page，并且在每個 page 的最后面會有一個指向下個 page 的指針耐量。這種方式不需要分配大量的連續(xù)存儲空間飞蚓，同時對于 log 的清理也比較友好，回收過期的 page 只需要一些指針的操作廊蜒。
5. 不記錄 file data趴拧。Inode 里面只記錄了 file metadata，沒有記錄 file data山叮。NOVA 使用了 COW 的機制更新 file data著榴，然后在將 metadata 追加到 log 上面。

架構(gòu)

DraggedImage.png

上圖是 NOVA 的整體架構(gòu)屁倔，NOVA 將 NVMM 分成了四塊脑又，superblock 和 recovery inode，inode tables锐借， journals问麸，最后就是 log / data pages。Superblock 包含了全局的文件系統(tǒng)信息钞翔，而 recovery inode 則存放了用于下一次啟動加速 NOVA remount 的恢復信息严卖，inode tables 則包含 inodes，而 journals 則是為目錄操作提供了原子支持布轿，剩下的就是實際的 log 和 data 的 pages哮笆。

NOVA 為每個 CPU 設(shè)置了自己的 inode table来颤，journal，page list稠肘，這樣就能避免不同的 CPU 之間的 lock 問題福铅。這個優(yōu)化其實在 RocksDB 的 statistics 上面也有體現(xiàn)，它也使用了 per-CPU 模型启具，每個 CPU 負責自己的統(tǒng)計信息本讥。

Inode Table

NOVA 首先會 為每一個 inode table 初始化一個 2 MB 的 inodes array，每一個 inode 都是 128 byte 字節(jié)鲁冯，所以給定一個 inode number，NOVA 會很容易就定位到對應(yīng)的 inode色查。

對于新增的 inode薯演，NOVA 會使用 round-robin 算法，依次添加到各個 inode table 上面秧了，保證整個 inodes 的均勻分布跨扮。如果一個 inode table 滿了，NOVA 會再分配一個 2 MB 的 sub-table验毡，并用鏈表串聯(lián)起來衡创。為了減少 inode table 的大小，每個 inode 上面有一個 bit 來表示是否 invalid晶通，NOVA 就能重用這些 inode 給新的文件或者目錄了璃氢。

一個 inode 包含指向 log 的 head 和 tail 指針，log 是一個由 4 KB page 串聯(lián)的鏈表狮辽，tail 一直指向的是最后一個提交的 log entry一也，當系統(tǒng)第一次訪問 NOVA 的時候，NOVA 會通過遍歷 head 到 tail 的所有 log 去重建 DRAM 里面的數(shù)據(jù)結(jié)構(gòu)喉脖。

Journal

NOVA 的 journal 是一個 4 KB 的環(huán)形 buffer椰苟，使用一對 <enqueue, dequeue> 指針來操作這個 buffer。Journal 主要是為了保證操作多個 inode 的原子性树叽，首先 NOVA 會將更新追加到 inode 的各自 log 上面舆蝴，然后開啟一個事務(wù)，將涉及到的 log tail 寫入當前 CPU 的 journal enqueue题诵，并且更新 enqueue 指針洁仗，當 各個 inode 完成了自己的更新，NOVA 就更新 dequeue 指針到 enqueue仇轻，完成事務(wù)的提交京痢。

空間管理

NOVA 將 NVMM 給每個 CPU 分了一個 pool，然后將空閑的 page list 保存在了 DRAM 里面篷店。如果當前 CPU pool 里面沒有可用的 page祭椰，就從最大的 pool 里面拿臭家。NOVA 使用 red-black tree 按照 address 來存放空閑的 pages，正常關(guān)機下面方淤，NOVA 會將分配好的 page 狀態(tài)保存到 recovery inode 的 log 里面钉赁，但如果是非正常關(guān)機，則會遍歷所有 inode 的 log 并重建携茂。

最開始你踩，一個 inode 的 log 只有一個 page，當需要更多 page 的時候讳苦，NOVA 直接使用 x 2 的方式带膜，但如果 log 的長度超過了一定閾值，就每次只新分配固定數(shù)量的 pages 了鸳谜。

實現(xiàn)

前面簡單的介紹了一些 NOVA 的架構(gòu)以及基本的數(shù)據(jù)結(jié)構(gòu)膝藕，下面介紹下一些常用功能的大概實現(xiàn)。

目錄操作

NOVA 的目錄包括兩塊咐扭，一個是保存到 NVMM 里面的 inode log芭挽，另一個則是放到 DRAM 里面的 radix tree。目錄的 log 包括 directory entires （也就是通常的 dentry） 和 inode update entires蝗肪。Dentry 包括目錄名袜爪，子目錄，子文件薛闪，inode 個數(shù)辛馆，還有 timestamp 這些信息。對于改目錄下面的文件操作逛绵，譬如 create怀各，delete焦蘑，rename 這些戒祠，NOVA 都會在 log 里面追加一個 dentry。 對于 delete 操作來說因痛，NOVA 會將 dentry 的 inode number 設(shè)置為 0胰苏，用以跟 create 區(qū)分硕蛹。

為了加快 dentry 的查詢速度，NOVA 在 DRAM 里面維護了一個 radix tree硕并，key 就是 dentry 的名字法焰，而 tree 的子節(jié)點則指向 log 中對應(yīng)的 dentry。

DraggedImage-1.png

上面是一個 create 的例子倔毙，我們要創(chuàng)建一個 zoo 的目錄埃仪，會有如下幾個操作：

1. 在 inode table 里面為 zoo 選擇并初始化一個未使用的 inode
2. 將 zoo 的 dentry 添加到目錄的 log 里面
3. 使用當前 CPU journal 更新 dir 目錄的 log tail 和給新的 inode 設(shè)置一個 valid 位。
4. 將 zoo 添加到 radix tee 上面陕赃。

文件操作

NOVA 的文件 log 包含兩種卵蛉，一個是 inode update entries颁股，另一個 write entries，write entry 里面會描述 write operation 以及指向?qū)嶋H的 data page傻丝。如果一次寫入太大甘有，NOVA 會使用多個 write entries，并將它們?nèi)孔芳拥?log 后面葡缰，然后最后更新 log tail亏掀。

DraggedImage-2.png

上面是一個文件寫入例子，上面的 <0, 1> 這種的表示 <filepageoff, num pages>泛释，也就是 page 的 offset 和有多少個 page滤愕。譬如 <0, 1> 就表示這個 page 的 offset 是 0， 有一個 page胁澳，也就是 4 KB该互。當我們要進行一次 <2, 2> 寫入（也就是在 offset 為 2 的地方重新寫入 2 pages），流程如下：

1. 使用 COW 技術(shù)將數(shù)據(jù)寫入到 data page 上面
2. 將 <2, 2> 追加到 inode log 上面
3. 原子更新 log tail韭畸，提交這次寫入
4. 更新 DRAM 里面的 radix tree，這樣 offset 2 就指向了新的 page
5. 將之前舊的兩個 page 放到 free list 里面

上面需要注意蔓搞，雖然我們更新 log tail 是原子的胰丁，但并沒有保證原子更新 log tail 和 radix tree，這里跟徐博士討論的時候他說到喂分，使用了一個 read-write lock锦庸，其實他覺得并不高效，后面考慮優(yōu)化蒲祈。

Atomic mmap

我們可以使用 DAX-mmap 技術(shù)將 NVMM 的數(shù)據(jù)直接映射到用戶空間甘萧，采用這種方式，我們能直接繞過文件系統(tǒng)的 page cache梆掸，雖然能降低開銷扬卷，但對于程序員來說還是有很大的挑戰(zhàn)，上面說了酸钦，NVMM 只有 64 位的原子操作支持怪得，而且一些 fence 和 flush 指令還需要依賴處理器，所以先基于這些初級的機制構(gòu)造健壯的 non-volatile 的數(shù)據(jù)結(jié)構(gòu)卑硫，其實是非常困難的徒恋。

為了解決這個問題，NOVA 使用了一種 atomic-mmap 的機制欢伏，它其實是使用了一個 replica pages入挣，然后將實際修改的數(shù)據(jù)放到了 replica pages 上面，當用戶調(diào)用了 msync 操作硝拧，NOVA 就會將相關(guān)的修改當做一次 write 操作處理径筏，它會使用 movntq 指令將 replica pages 的數(shù)據(jù)拷貝到 data pages葛假，然后在原子性的提交。

雖然采用這種方式能保證數(shù)據(jù)強一致匠璧，但并沒有 DAX-mmap 高效桐款。而對于通常 DRAM 的 mmap，NOVA 現(xiàn)在并不支持夷恍，未來可能有計劃魔眨。

GC

NOVA 將文件的 metadata 和實際 data 不同存放，這樣對于 GC 來說其實是很高效的酿雪。對于 data 來說遏暴，只要 write 操作產(chǎn)生了 stale data pages（就譬如我們前面說的那個例子），NOVA 就直接對 data pages 進行回收指黎。

但回收 inode logs 就比較復雜了朋凉。我們需要確認一個 log entry 是 dead 的，首先這個 entry 不能是 log 的最后一個 entry醋安，并且需要滿足以下任意一個條件杂彭，就可以認為是 dead 了：

1. 對于 file write entry ，沒有指向任何 valid 的 data page
2. 對于包含更新 inode metadata 的 entry吓揪，后面有一個新的更新同樣 metadata 的 entry
3. 對于一個包含 dentry update 的 entry亲怠，已經(jīng)被標記為 invalid

NOVA 使用兩種 GC 方式，F(xiàn)ast GC 和 Thorough GC柠辞。

DraggedImage-3.png

當 NOVA 發(fā)現(xiàn)一個 log page 里面所有的 entries 都是 dead团秽，那么就可以直接回收這個 page，這個僅僅需要更新 page 的指針就可以了叭首。譬如上面流程 a 就是 Fast GC 的例子习勤，2 這個 page 只有 dead entries 了，我們只需要將 page 1 的 next pointer 指針指向 page 3 就可以了焙格。

如果一個 log page 里面 live entries 的數(shù)量小于一半了图毕，NOVA 就會開始進行 Thorough GC，就是將 live entries 拷貝到另一個新的 log 上面间螟，指向新的 log吴旋，并且回收舊的 log。上面的流程 b 就是 Through GC 的例子厢破，NOVA 將 page 1 和 3 的 entries 拷貝到 page 5 上面荣瑟，然后鏈接 page 5 和 page 4，并且回收 page 1 和 3摩泪。這里 NOVA 并沒有處理 page 4 的 live entries笆焰，這樣就用原子更新 log head，從而避免同時更新 log head 和 tail见坑，這個沒法保證原子性嚷掠。

Recovery

當系統(tǒng)關(guān)閉并重新啟動之后捏检，NOVA 就會重現(xiàn)去 mount，它使用了一種延遲重建的機制不皆，也就是只有第一次訪問的時候才會去重建 radix tree 這些贯城。對于正常關(guān)機來說，因為 NOVA 會將所有的 page 分配狀態(tài)都保存到 recovery inode log 里面霹娄，所以 remount 的時候只需要從 recovery inode log 恢復就可以了能犯。

但對于異常關(guān)機（譬如掉電）來說，NOVA 就必須重建 page 分配狀態(tài)犬耻，NOVA 就需要遍歷所有的 inode logs 了踩晶。但這個速度也是很快的，因為首先能每個 CPU 并發(fā)去恢復枕磁，另外渡蜻，因為 log 里面不包含 data，所以 log 比較短计济，恢復速度自然就很快茸苇。在恢復的時候，NOVA 需要處理：

1. 檢查 journal沦寂，并且回滾所有沒有提交的事務(wù)
2. 每個 CPU 開啟一個 recovery 線程去并發(fā)的訪問 inode tables税弃，為每個 valid 的 inode 掃描 log。對于目錄 inode 來說凑队，NOVA 只需要遍歷它覆蓋的 pages，并不需要讀取 log 的內(nèi)容幔翰。而對于文件 inode漩氨，NOVA 則需要讀取 write entries 并遍歷所有的 data pages。

小結(jié)

NOVA 的源碼在 GitHub 遗增，大家如果感興趣叫惊，可以去學習一下，畢竟對于如何在新硬件體系上面做一個文件系統(tǒng)這種事情做修，還是非郴粽酷的。這篇文章也算是我對 NOVA 的一些探究饰及，里面如果有不對的地方蔗坯，如果徐博士看到了，麻煩指正出來燎含。

對于新硬件體系的研究宾濒，以及如何基于這些硬件體系更好的設(shè)計數(shù)據(jù)庫的存儲引擎，是我們未來重點會跟進的一個方向屏箍，歡迎各位對這方面感興趣的同學加入我們 PingCAP绘梦，你可以直接給我發(fā)郵件 tl@pingcap.com橘忱。畢竟從頭開始打造一個未來的存儲引擎，我覺得是一件非常有意思卸奉，有挑戰(zhàn)的事情钝诚。