📄
文｜黃章衡（SOFAJRaft 項目組）
福州大學 19 級計算機系
研究方向｜分布式中間件、分布式資料庫
Github 首頁｜
https://github.com/hzh0425校對｜馮家純（SOFAJRaft 開源社群負責人）
本文 9402 字 閱讀 18 分鐘
▼
PART. 1 項目介紹
1.1 SOFAJRaft 介紹
SOFAJRaft 是一個基于 RAFT 一緻性算法的生産級高性能 Java 實作，支援 MULTI-RAFT-GROUP，适用于高負載低延遲的場景。使用 SOFAJRaft 你可以專注于自己的業務領域，由 SOFAJRaft 負責處理所有與 RAFT 相關的技術難題，并且 SOFAJRaft 非常易于使用，你可以通過幾個示例在很短的時間内掌握它。
Github 位址：
https://github.com/sofastack/sofa-jraft
1.2 任務要求
目标：目前 LogStorage 的實作，采用 index 與 data 分離的設計，我們将 key 和 value 的 offset 作為索引寫入 rocksdb，同時日志條目（data）寫入 Segment Log。因為使用 SOFAJRaft 的使用者經常也使用了不同版本的 rocksdb，這就要求使用者不得不更換自己的 rocksdb 版本來适應 SOFAJRaft， 是以我們希望做一個改進：移除對 rocksdb 的依賴，建構出一個純 Java 實作的索引子產品。
PART. 2 前置知識
Log Structured File Systems
如果學習過類似 Kafka 等消息隊列的同學，對日志型系統應該并不陌生。
如圖所示，我們可以在單機磁盤上存儲一些日志型檔案，這些檔案中一般包含了舊檔案和新檔案的集合。差別在于 Active Data File 一般是映射到記憶體中的并且正在寫入的新檔案(基于 mmap 記憶體映射技術)，而 Older Data File 是已經寫完了，并且都 Flush 到磁盤上的舊檔案，當一塊 Active File 寫完之後，就會将其關閉，并打開一個新的 Active File 繼續寫。
并且每一次的寫入，每個 Log Entry 都會被 Append 到 Active File 的尾部，而 Active File 往往會用 mmap 記憶體映射技術，将檔案映射到 os Page Cache 裡，是以每一次的寫入都是記憶體順序寫，性能非常高。
終上所述，一塊 File 無非就是一些 Log Entry 的集合，如圖所示:
同時，僅僅将日志寫入到 File 中還不夠，因為當需要搜尋日志的時候，我們不可能順序周遊每一塊檔案去搜尋，這樣性能就太差了。是以我們還需要建構這些檔案的 “目錄”，也即索引檔案。這裡的索引本質上也是一些檔案的集合，其存儲的索引項一般是固定大小的，并提供了 LogEntry 的元資訊，如:
- File_Id : 其對應的 LogEntry 存儲在哪一塊 File 中
- Value_sz : LogEntry 的資料大小
(注: LogEntry 是被序列化後, 以二進制的方式存儲的)
- Value_pos: 存儲在對應 File 中的哪個位置開始
- 其他的可能還有 crc，時間戳等......
那麼依據索引檔案的特性，就能夠非常友善的查找 IndexEntry。
- 日志項 IndexEntry 是固定大小的
- IndexEntry 存儲了 LogEntry 的元資訊
- IndexEntry 具有單調遞增的特性
舉例，如果要查找 LogIndex = 4 的日志:
- 第一步，根據 LogIndex = 4，可以知道索引存儲的位置：IndexPos = IndexEntrySize * 4
- 第二步，根據 IndexPos，去索引檔案中，取出對應的索引項 IndexEntry
- 第三步，根據 IndexEntry 中的元資訊，如 File_Id、Pos 等，到對應的 Data File 中搜尋
- 第四步，找到對應的 LogEntry
記憶體映射技術 mmap
上文一直提到了一個技術：将檔案映射到記憶體中，在記憶體中寫 Active 檔案，這也是日志型系統的一個關鍵技術，在 Unix/Linux 系統下讀寫檔案，一般有兩種方式。
傳統檔案 IO 模型
一種标準的 IO 流程, 是 Open 一個檔案，然後使用 Read 系統調用讀取檔案的一部分或全部。這個 Read 過程是這樣的：核心将檔案中的資料從磁盤區域讀取到核心頁高速緩沖區，再從核心的高速緩沖區讀取到使用者程序的位址空間。這裡就涉及到了資料的兩次拷貝：磁盤->核心，核心->使用者态。
而且當存在多個程序同時讀取同一個檔案時，每一個程序中的位址空間都會儲存一份副本，這樣肯定不是最優方式的，造成了實體記憶體的浪費，看下圖：
記憶體映射技術
第二種方式就是使用記憶體映射的方式
具體操作方式是：Open 一個檔案，然後調用 mmap 系統調用，将檔案内容的全部或一部分直接映射到程序的位址空間(直接将使用者程序私有位址空間中的一塊區域與檔案對象建立映射關系)，映射完成後，程序可以像通路普通記憶體一樣做其他的操作，比如 memcpy 等等。mmap 并不會預先配置設定實體位址空間，它隻是占有程序的虛拟位址空間。
當第一個程序通路核心中的緩沖區時，因為并沒有實際拷貝資料，這時 MMU 在位址映射表中是無法找到與位址空間相對應的實體位址的，也就是 MMU 失敗，就會觸發缺頁中斷。核心将檔案的這一頁資料讀入到核心高速緩沖區中，并更新程序的頁表，使頁表指向核心緩沖中 Page Cache 的這一頁。之後有其他的程序再次通路這一頁的時候，該頁已經在記憶體中了，核心隻需要将程序的頁表登記并且指向核心的頁高速緩沖區即可，如下圖所示：
對于容量較大的檔案來說（檔案大小一般需要限制在 1.5~2G 以下），采用 mmap 的方式其讀/寫的效率和性能都非常高。
當然，需要如果采用了 mmap 記憶體映射，此時調用 Write 并不是寫入磁盤，而是寫入 Page Cache 裡。是以，如果想讓寫入的資料儲存到硬碟上，我們還需要考慮在什麼時間點 Flush 最合适 (後文會講述)。
PART. 3 架構設計
3.1 SOFAJRaft 原有日志系統架構
下圖是 SOFAJRaft 原有日志系統整體上的設計：
其中 LogManager 提供了和日志相關的接口，如:
/*** Append log entry vector and wait until it's stable (NOT COMMITTED!)** @param entries log entries* @param done callback*/void appendEntries(final Listentries, StableClosure done);/*** Get the log entry at index.** @param index the index of log entry* @return the log entry with {@code index}*/LogEntry getEntry(final long index);/*** Get the log term at index.** @param index the index of log entry* @return the term of log entry*/long getTerm(final long index); 實際上，當上層的 Node 調用這些方法時，LogManager 并不會直接處理，而是通過 OfferEvent( done, EventType ) 将事件釋出到高性能的并發隊列 Disruptor 中等待排程執行。
是以，可以把 LogManager 看做是一個 “門面”，提供了通路日志的接口，并通過 Disruptor 進行并發排程。
「注」: SOFAJRaft 中還有很多地方都基于 Disruptor 進行解耦，異步回調，并行排程， 如 SnapshotExecutor、NodeImpl 等，感興趣的小夥伴可以去社群一探究竟，對于學習 Java 并發程式設計有很大的益處 !
關于 Disruptor 并發隊列的介紹，可以看這裡:
https://tech.meituan.com/2016/11/18/disruptor.html最後，實際存儲日志的地方就是 LogManager 的調用對象，LogStorage。
而 LogStorage 也是一個接口:
/*** Append entries to log.*/boolean appendEntry(final LogEntry entry);/*** Append entries to log, return append success number.*/int appendEntries(final Listentries);/*** Delete logs from storage's head, [first_log_index, first_index_kept) will* be discarded.*/boolean truncatePrefix(final long firstIndexKept);/*** Delete uncommitted logs from storage's tail, (last_index_kept, last_log_index]* will be discarded.*/boolean truncateSuffix(final long lastIndexKept); 在原有體系中，其預設的實作類是 RocksDBLogStorage，并且采用了索引和日志分離存儲的設計，索引存儲在 RocksDB 中，而日志存儲在 SegmentFile 中。
如圖所示，RocksDBSegmentLogStorage 繼承了 RocksDBLogStorageRocksDBSegmentLogStorage 負責日志的存儲 RocksDBLogStorage 負責索引的存儲。
3.2 項目任務分析
通過上文對原有日志系統的描述，結合該項目的需求，可以知道本次任務我需要做的就是基于 Java 實作一個新的 LogStorage，并且能夠不依賴 RocksDB。實際上日志和索引存儲在實作的過程中會有很大的相似之處。例如，檔案記憶體映射 mmap、檔案預配置設定、異步刷盤等。是以我的任務不僅僅是做一個新的索引子產品，還需要做到以下:
- 一套能夠被複用的檔案系統, 使得日志和索引都能夠直接複用該檔案系統，實作各自的存儲
- 相容 SOFAJRaft 的存儲體系，實作一個新的 LogStorage，能夠被 LogManager 所調用
- 一套高性能的存儲系統，需要對原有的存儲系統在性能上有較大的提升
- 一套代碼可讀性強的存儲系統，代碼需要符合 SOFAJRaft 的規範
......
在本次任務中，我和導師在存儲架構的設計上進行了多次的讨論與修改，最終設計出了一套完整的方案，能夠完美的契合以上的所有要求。
3.3 改進版的日志系統
架構設計
下圖為改進版本的日志系統，其中 DefaultLogStorage 為上文所述 LogStorage 的實作類。三大 DB 為邏輯上的存儲對象, 實際的資料存儲在由 FileManager 所管理的 AbstractFiles 中，此外 ServiceManager 中的 Service 起到輔助的效果，例如 FlushService 可以提供刷盤的作用。
為什麼需要三大 DB 來存儲資料呢? ConfDB 是幹什麼用的?
以下這幅圖可以很好的解釋三大 DB 的作用:
因為在 SOFAJraft 原有的存儲體系中，為了提高讀取 Configuration 類型的日志的性能，會将 Configuration 類型的日志和普通日志分離存儲。是以，這裡我們需要一個 ConfDB 來存儲 Configuration 類型的日志。
3.4 代碼子產品說明
代碼主要分為四大子產品:
- db 子產品 (db 檔案夾下)
- File 子產品 (File 檔案夾下)
- service 子產品 (service 檔案夾下)
- 工廠子產品 (factory 檔案夾下)
- DefaultLogStorage 就是上文所述的新的 LogStorage 實作類
3.5 性能測試
測試背景
- 作業系統：Window
- 寫入資料總大小：8G
- 記憶體：24G
- CPU：4 核 8 線程
- 測試代碼：
#DefaultLogStorageBenchmark 資料展示
Log Number 代表總共寫入了 524288 條日志
Log Size 代表每條日志的大小為 16384
Total size 代表總共寫入了 8589934592 (8G) 大小的資料
寫入耗時 (45s)
讀取耗時 (5s)
Test write: Log number :524288 Log Size :16384 Cost time(s) :45 Total size :8589934592 Test read: Log number :524288 Log Size :16384 Cost time(s) :5 Total size :8589934592Test done! PART. 4 系統亮點
### 4.1 日志系統檔案管理
在 2.1 節中，我介紹了一個日志系統的基本概念，回顧一下:
而本項目日志檔案是如何管理的呢? 如圖所示，每一個 DB 的所有日志檔案(IndexDB 對應 IndexFile, SegmentDB 對應 SegmentFile) 都由 File Manager 統一管理。
以 IndexDB 所使用的的 IndexFile 為例，假設每個 IndexFile 大小為 126，其中 fileHeader = 26 bytes，檔案能夠存儲十個索引項，每個索引項大小 10 bytes。
而 FileHeader 存儲了一塊檔案的基本元資訊:
// 第一個存儲元素的索引 : 對應圖中的 StartIndexdprivate volatile long FirstLogIndex = BLANK_OFFSET_INDEX;// 該檔案的偏移量，對應圖中的 BaseOffsetprivate long FileFromOffset = -1; 是以，FileManager 就能根據這兩個基本的元資訊，對所有的 File 進行統一的管理，這麼做有以下的好處:
- 統一的管理所有檔案
- 友善根據 LogIndex 查找具體的日志在哪個檔案中, 因為所有檔案都是根據 FirstLogIndex 排列的，很顯然在這裡可以基于二分算法查找:
int lo = 0, hi = this.files.size() - 1;while (lo <= hi) { final int mid = (lo + hi) >>> 1; final AbstractFile file = this.files.get(mid); if (file.getLastLogIndex() < logIndex) { lo = mid + 1; } else if (file.getFirstLogIndex() > logIndex) { hi = mid - 1; } else { return this.files.get(mid); }} - 友善 Flush 刷盤(4.2 節中會提到)
4.2 Group Commit - 組送出
在章節 2.2 中我們聊到，因為記憶體映射技術 mmap 的存在，Write 之後不能直接傳回，還需要 Flush 才能保證資料被儲存到了磁盤上，但同時也不能直接寫回磁盤，因為磁盤 IO 的速度極慢，每寫一條日志就 Flush 一次的話性能會很差。
是以，為了防止磁盤 '拖後腿'，本項目引入了 Group commit 機制，Group commit 的思想是延遲 Flush，先盡可能多的寫入一批的日志到 Page Cache 中，然後統一調用 Flush 減少刷盤的次數，如圖所示:
- LogManager 通過調用 appendEntries() 批量寫入日志
- DefaultLogStorage 通過調用 DB 的接口寫入日志
- DefaultLogStorage 注冊一個 FlushRequest 到對應 DB 的 FlushService 中，并阻塞等待，FlushRequest 包含了期望刷盤的位置 ExpectedFlushPosition。
private boolean waitForFlush(final AbstractDB logDB, final long exceptedLogPosition, final long exceptedIndexPosition) { try { final FlushRequest logRequest = FlushRequest.buildRequest(exceptedLogPosition); final FlushRequest indexRequest = FlushRequest.buildRequest(exceptedIndexPosition); // 注冊 FlushRequest logDB.registerFlushRequest(logRequest); this.indexDB.registerFlushRequest(indexRequest); // 阻塞等待喚醒 final int timeout = this.storeOptions.getWaitingFlushTimeout(); CompletableFuture.allOf(logRequest.getFuture(), indexRequest.getFuture()).get(timeout, TimeUnit.MILLISECONDS); } catch (final Exception e) { LOG.error(.....); return false; }} - FlushService 刷到 expectedFlushPosition 後，通過 doWakeupConsumer() 喚醒阻塞等待的 DefaultLogStorage
while (!isStopped()) { // 阻塞等待刷盤請求 while ((size = this.requestQueue.blockingDrainTo(this.tempQueue, QUEUE_SIZE, WAITING_TIME, TimeUnit.MILLISECONDS)) == 0) { if (isStopped()) { break; } } if (size > 0) { ....... // 執行刷盤 doFlush(maxPosition); // 喚醒 DefaultLogStorage doWakeupConsumer(); ..... }} 那麼 FlushService 到底是如何配合 FileManager 進行刷盤的呢? 或者應該問 FlushService 是如何找到對應的檔案進行刷盤?
實際上在 FileManager 維護了一個變量 FlushedPosition，就代表了目前刷盤的位置。從 4.1 節中我們了解到 FileManager 中每一塊 File 的 FileHeader 都記載了目前 File 的 BaseOffset。是以，我們隻需要根據 FlushedPosition，查找其目前在哪一塊 File 的區間裡，便可找到對應的檔案，例如：
目前 FlushPosition = 130，便可以知道目前刷到了第二塊檔案。
4.3 檔案預配置設定
當日志系統寫滿一個檔案，想要打開一個新檔案時，往往是一個比較耗時的過程。所謂檔案預配置設定，就是事先通過 mmap 映射一些空檔案存在容器中，當下一次想要 Append 一條 Log 并且前一個檔案用完了，我們就可以直接到這個容器裡面取一個空檔案，在這個項目中直接使用即可。有一個背景的線程 AllocateFileService 在這個 Allocator 中，我采用的是典型的生産者消費者模式，即用了 ReentrantLock + Condition 實作了檔案預配置設定。
// Pre-allocated filesprivate final ArrayDequeblankFiles = new ArrayDeque<>();private final Lock allocateLock private final Condition fullCond private final Condition emptyCond 其中 fullCond 用于代表目前的容器是否滿了，emptyCond 代表目前容器是否為空。
private void doAllocateAbstractFileInLock() throws InterruptedException { this.allocateLock.lock(); try { // 如果容器滿了, 則阻塞等待, 直到被喚醒 while (this.blankAbstractFiles.size() >= this.storeOptions.getPreAllocateFileCount()) { this.fullCond.await(); } // 配置設定檔案 doAllocateAbstractFile0(); // 容器不為空, 喚醒阻塞的消費者 this.emptyCond.signal(); } finally { this.allocateLock.unlock(); }}public AbstractFile takeEmptyFile() throws Exception { this.allocateLock.lock(); try { // 如果容器為空, 目前消費者阻塞等待 while (this.blankAbstractFiles.isEmpty()) { this.emptyCond.await(); } final AllocatedResult result = this.blankAbstractFiles.pollFirst(); // 喚醒生産者 this.fullCond.signal(); return result.abstractFile; } finally { this.allocateLock.unlock(); }} 4.4 檔案預熱
在 2.2 節中介紹 mmap 時，我們知道 mmap 系統調用後作業系統并不會直接配置設定實體記憶體空間，隻有在第一次通路某個 page 的時候，發出缺頁中斷 OS 才會配置設定。可以想象如果一個檔案大小為 1G，一個 page 4KB，那麼得缺頁中斷大概 100 萬次才能映射完一個檔案，是以這裡也需要進行優化。
當 AllocateFileService 預配置設定一個檔案的時候，會同時調用兩個系統：
- Madvise()：簡單來說建議作業系統預讀該檔案，作業系統可能會采納該意見
- Mlock()：将程序使用的部分或者全部的位址空間鎖定在實體記憶體中，防止被作業系統回收
對于 SOFAJRaft 這種場景來說，追求的是消息讀寫低延遲，那麼肯定希望盡可能地多使用實體記憶體，提高資料讀寫通路的操作效率。
- 收獲 -
在這個過程中我慢慢學習到了一個項目的正常流程:
- 首先，仔細打磨立項方案，深入考慮方案是否可行。
- 其次，項目過程中多和導師溝通，盡快發現問題。本次項目也遇到過一些我無法解決的問題，家純老師非常耐心的幫我找出問題所在，萬分感謝!
- 最後，應該注重代碼的每一個細節，包括命名、注釋。
正如家純老師在結項點評中提到的，"What really makes xxx stand out is attention to low-level details "。
在今後的項目開發中，我會更加注意代碼的細節，以追求代碼優美并兼顧性能為目标。
後續，我計劃為 SOFAJRaft 項目作出更多的貢獻，期望于早日晉升成為社群 Committer。也将會借助 SOFAStack 社群的優秀項目，不斷深入探索雲原生!
- 鳴謝 -
首先很幸運能參與本次開源之夏的活動，感謝馮家純導師對我的耐心指導和幫助 !
感謝開源軟體供應鍊點亮計劃和 SOFAStack 社群給予我的這次機會 !
*本周推薦閱讀*
SOFAJRaft 在同程旅遊中的實踐 下一個 Kubernetes 前沿：多叢集管理 基于 RAFT 的生産級高性能 Java 實作 - SOFAJRaft 系列内容合輯 終于！SOFATracer 完成了它的鍊路可視化之旅