消息系統(tǒng)中隨機(jī)索引的特點(diǎn)

Cloud Native

RocketMQ 廣泛使用于各類業(yè)務(wù)場景中，在實(shí)際生產(chǎn)場景中，用戶通常會選擇消息 ID 或者特定的業(yè)務(wù) Key（例如學(xué)號，訂單號）來查詢和定位特定的一批消息，進(jìn)而定位分布式系統(tǒng)中的復(fù)雜問題。傳統(tǒng)方案下，消息索引的存儲是基于數(shù)據(jù)庫系統(tǒng)或者基于本地文件系統(tǒng)實(shí)現(xiàn)的，受限于磁盤容量，很難滿足海量數(shù)據(jù)的寫入訴求。 在云原生場景下，對象存儲能夠?yàn)橛脩籼峁椥院桶戳扛顿M(fèi)的能力，有效降低存儲成本，但對隨機(jī)讀寫的支持不夠友好。RocketMQ 的隊(duì)列模型中寫入的數(shù)據(jù)是按時間近似有序的，對于隨機(jī)索引熱數(shù)據(jù)實(shí)現(xiàn)了 non-stop write 的特性，同時支持冷熱分離，使用異步歸整的方式冷數(shù)據(jù)轉(zhuǎn)移到更廉價(jià)存儲系統(tǒng)中。

磁盤中 RocketMQ 構(gòu)建的索引結(jié)構(gòu)

Cloud Native

索引是一種以空間換時間的支持快速存儲和查找的高效數(shù)據(jù)結(jié)構(gòu)。我們來看看 RocketMQ 的索引文件的結(jié)構(gòu)設(shè)計(jì)。RocketMQ 的索引文件文件結(jié)構(gòu)采用三段式結(jié)構(gòu)基于頭插法的 HashTable 設(shè)計(jì)的。該索引文件存儲結(jié)構(gòu)具有查詢速度快、占用空間小、易于維護(hù)等特點(diǎn)，但是隨著數(shù)據(jù)量的增加，本地索引文件數(shù)量也會不斷增加。

分別為：索引頭部（IndexHeader），索引槽（Slots），索引條目（IndexItems）。

索引文件結(jié)構(gòu)

Hash 沖突的索引通過單向鏈表進(jìn)行連接，索引條目采取文件末尾追加寫入的方式提升寫入性能： 1. 索引頭部（IndexHeader）包含了該索引文件的元數(shù)據(jù)信息，其中包括了 MagicCode 用來判斷文件的起始位置。開始時間戳（startTimeStamp）和結(jié)束時間戳（endTimeStamp）表示了索引存儲的時間區(qū)間范圍。然后還包括了該文件已經(jīng)使用的索引槽數(shù)量（hashSlotCount）和已經(jīng)存儲的索引數(shù)量（indexCount）。 2. 索引槽（Slots）為固定數(shù)量，其中存儲了產(chǎn)生哈希沖突的索引索引的頭節(jié)點(diǎn)所在的位置，通過哈希映射得到哈希值，然后哈希值對索引槽（Slots）數(shù)量進(jìn)行取余得到索引具體的槽的位置，可以看作鏈表的頭節(jié)點(diǎn)。 3. 索引條目（IndexItems）存儲了每個索引具體存儲的數(shù)據(jù)，消息隊(duì)列發(fā)送的消息最后都存儲在一個特定topic的一個隊(duì)列的一個叫做 CommitLog 的文件中，因此每個索引條目都包含了 topicId，QueueId，Offset，Size 等信息來定位到實(shí)際消息在 CommitLog 中的存儲位置。

IndexItem

索引文件數(shù)據(jù)格式轉(zhuǎn)換 Compact

Cloud Native

在 RocketMQ 中，由于索引模塊是一個寫多讀極少零更新的結(jié)構(gòu)，因此為了降低系統(tǒng)整體的平均操作代價(jià)，單次讀有一些讀放大的開銷是可以接受的。假設(shè)消息索引寫入時間開銷需要 t1，平均每條消息索引在經(jīng)過 t2 之后被查詢，格式轉(zhuǎn)換時間開銷為 t_compact，通常 t_compact 遠(yuǎn)遠(yuǎn)小于 t2，因此 t_compact 可以在 t2 時間內(nèi)異步完成，格式轉(zhuǎn)換前消息索引查詢時間為 t_before，格式轉(zhuǎn)換后的消息索引平均查詢時間開銷為 t_after，格式轉(zhuǎn)換后消息索引平均查詢時間開銷小于格式轉(zhuǎn)換后查詢時間開銷 t_before < t_after，那么不進(jìn)行格式轉(zhuǎn)換數(shù)據(jù)存儲查詢時間開銷大于進(jìn)行了格式轉(zhuǎn)換后存儲查詢時間開銷 。

t1 + t2 + t_before > t1 + t2 + t_after。

時間軸 RocketMQ 索引文件使用基于頭插法實(shí)現(xiàn)的開鏈的 HashTable，在索引寫入時可以順序?qū)懭?。然而，在進(jìn)行指定 key 查詢時，由于使用的是單向鏈表，對 key 進(jìn)行 hash 到指定 slot 并獲取到鏈表頭節(jié)點(diǎn)，然后根據(jù)鏈表頭節(jié)點(diǎn)遍歷單向鏈表屬于隨機(jī) IO 查詢，對象存儲類似于機(jī)械硬盤的特性，讀取 20 Bytes 和讀取數(shù) KB 時間幾乎相同，多次隨機(jī) IO 會造成較大的時間開銷，因此在較多 Hash 沖突時可能存在嚴(yán)重的數(shù)據(jù)讀放大問題。 為了減少對象存儲文件的隨機(jī)查詢訪問次數(shù)，多級存儲異步對索引文件數(shù)據(jù)格式轉(zhuǎn)換，格式轉(zhuǎn)換后的索引文件可以一次性取回大塊數(shù)據(jù)，可以極大的減少對對象存儲文件的 IO 訪問次數(shù)。 具體地，隨機(jī)索引異步重排機(jī)制包括以下步驟：

1. 將本地索引文件按照映射后的 slot 槽為單位進(jìn)行分組，每組包含一定數(shù)量的索引項(xiàng)。

2. 對相同的組按照順序?qū)懭胄碌乃饕募?，同一個槽對應(yīng)的組的索引項(xiàng)在物理地址空間上是連續(xù)的數(shù)組。

3. 在需要查詢時，根據(jù)要查詢的 key 的 hash 值，映射到指定的槽，然后槽的位置存儲了數(shù)組的首地址，通過遍歷數(shù)組，確定需要查詢索引。 通過這種方式，可以大大減少在對象存儲中進(jìn)行的隨機(jī)查詢操作，從而提高查詢效率，降低時間開銷。同時，由于本地索引文件需要進(jìn)行格式轉(zhuǎn)換和分組，因此也需要一定的計(jì)算和存儲資源。

格式轉(zhuǎn)換前

格式轉(zhuǎn)換后 重排后的索引文件，將物理地址不連續(xù)的鏈表重新排列成了物理地址連續(xù)的數(shù)組，每個 SlotItem 的 8 個字節(jié)，前 4 個字節(jié)用來記錄數(shù)組的首地址，后 4 個字節(jié)用于記錄數(shù)組的長度。這樣的格式轉(zhuǎn)換有以下幾個好處。

這樣后續(xù)對索引的讀取從鏈表的隨機(jī) IO 變成了數(shù)組順序 IO。降低了隨機(jī) IO 帶來的時間開銷。

可以利用空間局部性，增加內(nèi)存 pageCache 的緩存命中率。

單個索引文件的狀態(tài)變化

Cloud Native

單個索引文件生命周期

單個索引文件的容量是有限的。當(dāng)有許多索引進(jìn)行寫入時，一個索引文件達(dá)到了能夠存儲的最大索引數(shù)量后，需要新建一個索引文件，繼續(xù)寫入。因此一個文件從創(chuàng)建到銷毀都會經(jīng)歷新建文件，Compact 文件，上傳成為對象存儲文件，過期銷毀等階段。

當(dāng)一個“正在寫入文件”狀態(tài)的索引文件完全寫滿后，需要將其標(biāo)記為“Compact文件”狀態(tài)。Compact 文件狀態(tài)意味著該文件已經(jīng)不再需要被寫入并且已經(jīng) Compact 完成，但是仍然需要被保留以便后續(xù)上傳到對象存儲。此時，可以通過將該文件上傳到對象存儲系統(tǒng)進(jìn)行存儲，并將其標(biāo)記為“對象存儲文件”狀態(tài)。因此也對應(yīng)了文件的三種狀態(tài)，unsealed, compacted, upload。

多個索引文件存儲模型

Cloud Native

為了實(shí)現(xiàn) Non-Stop Write 的特性，提高索引的寫入性能，設(shè)計(jì)劃分了三種不同的線程進(jìn)行相互協(xié)作。他們分別為寫入線程，索引查詢線程和后臺定時任務(wù)線程。他們各自負(fù)責(zé)不同的任務(wù)，并且通過讀寫鎖來保證并發(fā)條件下正確性。消息隊(duì)列是一個按時間近似有序的存儲系統(tǒng)，不同的索引文件存儲了不同時間段的索引，因此可以按照時間的近似有序性來管理多個文件。采用跳表數(shù)據(jù)結(jié)構(gòu)進(jìn)行管理，可以很方便的支持快速的定位查找和區(qū)間查詢。

1. 寫入線程

是非阻塞的，它的職責(zé)是將索引寫入到隊(duì)列尾部的處于正在寫入狀態(tài)的文件。當(dāng)一個文件寫滿后，該線程會自動在隊(duì)列尾部新建一個文件，并切換到下一個文件進(jìn)行寫入。為了提高寫入效率，該線程在將索引寫入文件時還負(fù)責(zé)將索引緩存在內(nèi)存中，當(dāng)緩存達(dá)到一定數(shù)量后再將其批量寫入到文件中，以減少磁盤 IO 次數(shù)。

2. 索引查詢線程

可以查詢處于不同狀態(tài)的索引文件具體查詢策略如下：

對于處于正在寫入狀態(tài)的文件，查詢線程需要等待寫入線程將索引寫入完成后才能進(jìn)行查詢；對于已經(jīng)寫滿的文件，查詢線程可以直接對其進(jìn)行查詢；對于已經(jīng) Compact 的文件，查詢線程也直接從本地文件進(jìn)行查詢。

對于上傳到對象存儲的文件，可以直接從對象存儲中讀取其數(shù)據(jù)，對 Compact 后格式的索引文件進(jìn)行查詢。

3. 后臺定時任務(wù)線程

主要負(fù)責(zé)對正在處于寫入狀態(tài)的文件并且已經(jīng)寫滿的文件進(jìn)行 Compact 操作。在進(jìn)行 Compact 操作時，該線程需要先獲取對應(yīng)文件的讀寫鎖，以避免其他線程對該文件的并發(fā)訪問。Compact 完成后切換該文件的狀態(tài)為 Compact 完成，然后需要將 Compact 過的文件上傳到對象存儲成為對象存儲文件，上傳完將文件狀態(tài)切換成已上傳狀態(tài)。在上傳過程中，該線程需要釋放對該文件的讀寫鎖。

系統(tǒng)層次設(shè)計(jì)

Cloud Native

為了提高系統(tǒng)的可擴(kuò)展性和方便編寫單元測試，整個索引服務(wù)采用了層次設(shè)計(jì)的思想，自頂向下，分別設(shè)計(jì)了索引服務(wù)層、索引文件解析層和數(shù)據(jù)存儲層。不同的層負(fù)責(zé)處理不同的任務(wù)，層與層之間解耦合，上層只依賴下層提供的服務(wù)。

索引服務(wù)層：該層為 RocketMQ 提供消息索引服務(wù)，它的職責(zé)是負(fù)責(zé)消息索引的存儲和查詢，同時負(fù)責(zé)索引文件的生命周期管理，包括創(chuàng)建索引文件、Compact 文件、上傳文件，銷毀文件等。

索引文件解析層：該層主要針對單個處于不同狀態(tài)的索引文件進(jìn)行格式解析，同時提供單個文件的 KV 查詢和存儲服務(wù)。具體而言，該層負(fù)責(zé)讀取索引文件中的數(shù)據(jù)，并將其解析為可讀格式，以供上層調(diào)用。

數(shù)據(jù)存儲層：該層負(fù)責(zé)二進(jìn)制流數(shù)據(jù)的寫入和讀取，支持不同類型的存儲方式，包括對象存儲、本地磁盤文件、或者數(shù)據(jù)庫文件等。具體而言，該層將數(shù)據(jù)存儲在本地磁盤或?qū)ο蟠鎯χ谢驍?shù)據(jù)庫文件。在讀取數(shù)據(jù)時，該層負(fù)責(zé)從本地磁盤或?qū)ο蟠鎯χ蝎@取數(shù)據(jù)，并將其轉(zhuǎn)換為二進(jìn)制流數(shù)據(jù)返回給調(diào)用方。

通過采用層次設(shè)計(jì)的思想，將整個索引服務(wù)劃分為三個不同的層次，使得系統(tǒng)具有良好的可擴(kuò)展性和可維護(hù)性，方便后續(xù)升級和維護(hù)。同時，各層次之間解耦合，職責(zé)明確，方便進(jìn)行單元測試和維護(hù)。

高可用的系統(tǒng)宕機(jī)恢復(fù)流程設(shè)計(jì)

Cloud Native

由于索引文件有不同的狀態(tài)，通過跳表的數(shù)據(jù)結(jié)構(gòu)進(jìn)行管理和維護(hù)，在系統(tǒng)宕機(jī)狀態(tài)下，需要對處于不同狀態(tài)的索引文件進(jìn)行恢復(fù)。為此，我們采用了分類分文件夾進(jìn)行管理，通過文件夾名稱來對不同狀態(tài)的索引文件進(jìn)行管理和記錄。

在進(jìn)行宕機(jī)恢復(fù)時，我們采用了以下流程設(shè)計(jì)：

1. 在系統(tǒng)重新啟動后，讀取存儲在系統(tǒng)中的文件夾名稱列表，該列表中包含了所有處于不同狀態(tài)的索引文件所對應(yīng)的文件夾名稱。

2. 通過文件夾名稱列表，依次讀取每個文件夾下的索引文件，并將這些索引文件加載到內(nèi)存中，重新構(gòu)建跳表。

3. 根據(jù)文件夾名稱以及其對應(yīng)的索引文件，恢復(fù)當(dāng)前文件所處的狀態(tài)。例如，如果文件夾名稱為 “writing”，則表示該文件夾下的索引文件正處于寫入狀態(tài)，需要根據(jù)寫入狀態(tài)進(jìn)行相應(yīng)的處理。

與其他系統(tǒng)的對比

Cloud Native

Rocksdb 是基于 Google LevelDB 研發(fā)的高性能 kv 持久化存儲引擎。RocksDB 使用 Log-Structured Merge（LSM）trees 作為基本的數(shù)據(jù)存儲結(jié)構(gòu)。當(dāng)數(shù)據(jù)寫入 RocksDB 的時候，首先會寫入到內(nèi)存中的 MemTable 并持久化道磁盤上的 Write-Ahead-Log (WAL) 文件上。

每當(dāng) MemTable 緩存數(shù)據(jù)量達(dá)到預(yù)設(shè)值，MemTable 與 WAL 將會轉(zhuǎn)為不可變狀態(tài)，同時分配新的 MemTable 與 WAL 用于后續(xù)寫入，接著對不可變 MemTable 中相同 key 進(jìn)行 (merge)，LSM tree 有多個層級 (Level)，每個層級由多個 SSTable 組成，最新的 SSTable 都會放置在最底層，下層的 SSTable 通過異步壓縮（Compaction）操作創(chuàng)建。

每層的 SSTable 總大小由配置參數(shù)決定，當(dāng) L 層數(shù)據(jù)大小超出預(yù)設(shè)值，會選擇 L 層的 SSTable 與 L+1 層的SSTable 重疊部分合并，通過重復(fù)這一過程優(yōu)化數(shù)據(jù)的讀性能，但 Compaction 這個動作會帶來較大的讀寫放大。

MySQL InnoDB 是一種事務(wù)型存儲引擎。它提供了高性能、高可靠性和高并發(fā)性的特性，底層采用 B+ 樹進(jìn)行實(shí)現(xiàn)，數(shù)據(jù)文件本身就是索引文件。為了解決宕機(jī)時數(shù)據(jù)丟失的問題，InnoDB 采用了 RedoLog 同步記錄寫行為。因?yàn)?RedoLog 是順序?qū)懭?，因此寫入的效率很高，?shù)據(jù)將會先寫入緩存和 RedoLog 中。 最后數(shù)據(jù)會異步再從 RedoLog 寫入 B+ 樹中。由于 B+ 樹的層次結(jié)構(gòu)導(dǎo)致能夠支持的索引數(shù)量是有上限的，例如單表超過數(shù)億級別的記錄時就會產(chǎn)生顯著的性能下降。同時 B+ 樹葉子結(jié)點(diǎn)的分裂與合并也會帶來較多的讀寫開銷。

RocketMQ 本身是一個寫多讀少零更新并且按時間近似有序的存儲系統(tǒng)。因此 RocketMQ 可以按照時間簡單高效地進(jìn)行冷熱分離存儲。也支持異步的文件格式轉(zhuǎn)換來降低系統(tǒng)整體時間開銷。

還有待改進(jìn)的地方

Cloud Native

當(dāng)前的索引設(shè)計(jì)簡單可靠，但還有一些設(shè)計(jì)上的不足之處。例如：當(dāng)前通常消息隊(duì)列通過 key 查詢消息時，還會有一個 maxCount 參數(shù)，由于對不同的索引文件查詢時并發(fā)的，當(dāng)前系統(tǒng)的實(shí)現(xiàn)存在缺陷，可能需要查詢完所有的索引文件，然后對結(jié)果進(jìn)行匯總，判斷是否達(dá)到 maxCount 參數(shù)指定的索引數(shù)量。

當(dāng)存在較多的索引文件時，這樣可能存在潛在的大量查詢帶來多余的時間開銷。因此一個合理的解決方式是我們需要一個多線程全局的計(jì)數(shù)器，當(dāng)滿足 maxCount 時，可以停止對后續(xù)多余的索引文件進(jìn)行查詢。這里涉及到多線程訪問時可能出現(xiàn)的線程安全問題。

本消息隊(duì)列多級存儲索引模塊提供 kv 數(shù)據(jù)查詢和存儲，可以對索引條目（indexItem）進(jìn)行重新設(shè)計(jì)，可以使本系統(tǒng)遷移到其他系統(tǒng)，為其他系統(tǒng)提供索引服務(wù)。只需要新增一個類將 indexItem 作為父類繼承，重寫相關(guān)函數(shù)，添加自定義字段，就可以實(shí)現(xiàn)對其他系統(tǒng)提供索引服務(wù)。

審核編輯：湯梓紅