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

Cloud Native

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

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

Cloud Native

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

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

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

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

IndexItem

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

Cloud Native

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

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

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

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

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

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

格式轉(zhuǎn)換前

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

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

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

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

Cloud Native

單個(gè)索引文件生命周期

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

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

多個(gè)索引文件存儲(chǔ)模型

Cloud Native

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

1. 寫入線程

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

2. 索引查詢線程

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

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

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

3. 后臺(tái)定時(shí)任務(wù)線程

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

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

Cloud Native

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

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

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

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

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

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

Cloud Native

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

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

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

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

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

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

Cloud Native

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

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

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

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

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

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

Cloud Native

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

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

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

審核編輯：湯梓紅