RocksDB 詳解
簡(jiǎn)介
RocksDB是一個(gè)高性能、可擴展、嵌入式、持久化、可靠、易用和可定制的鍵值存儲庫。它采用LSM樹(shù)數據結構，支持高吞吐量的寫(xiě)入和快速的范圍查詢(xún)，可被嵌入到應用程序中，實(shí)現持久化存儲，支持水平擴展，可以在多臺服務(wù)器上部署，實(shí)現集群化存儲，具有高度的可靠性和穩定性，易于使用并可以根據需求進(jìn)行定制和優(yōu)化。RocksDB主要使用到了下面知識：
LSM樹(shù)
LSM樹(shù)全稱(chēng)Log-Structured Merge Tree，是一種數據結構，常用于鍵值存儲系統中。LSM樹(shù)的優(yōu)點(diǎn)是可以支持高吞吐量的寫(xiě)入，具有良好的性能和可擴展性，并且可以在磁盤(pán)上存儲大量的數據。但是，由于需要定期進(jìn)行合并操作，因此對查詢(xún)性能和磁盤(pán)空間的使用可能會(huì )造成一定的影響。為了解決這個(gè)問(wèn)題，LSM樹(shù)還有許多優(yōu)化，如Bloom Filter、Compaction等，可以進(jìn)一步提高查詢(xún)性能和減少磁盤(pán)空間的使用。
LSM的組成
LSM樹(shù)中的層級可以分為內存和磁盤(pán)兩個(gè)部分，具體分層如下：
- 內存層：內存層也被稱(chēng)為MemTable，是指存儲在內存中的數據結構，用于緩存最新寫(xiě)入的數據。當數據寫(xiě)入時(shí)，先將其存儲到MemTable中，然后再將MemTable中的數據刷寫(xiě)到磁盤(pán)中，生成一個(gè)新的磁盤(pán)文件。由于內存讀寫(xiě)速度非?？?，因此使用MemTable可以實(shí)現高吞吐量的寫(xiě)入操作。
- 磁盤(pán)層：磁盤(pán)層是指存儲在磁盤(pán)中的數據文件，可以分為多個(gè)層級。一般來(lái)說(shuō)，LSM樹(shù)中的磁盤(pán)層可以分為以下幾個(gè)層級：
- Level-0: 是最底層的磁盤(pán)層，存儲的是從內存層寫(xiě)到磁盤(pán)中的文件。Level-0的文件一般比較小，按照寫(xiě)入順序排序。由于要保證寫(xiě)入速度很快，因此Level-0中的文件數量較多。
- Level-1: 是Level-0的上一層，存儲的是由多個(gè)Level-0的文件合并而來(lái)，Level-1中的文件一般比較大，按照鍵值排序。由于Level-0中的文件較多，因此Level-1中的文件也是比較多。
- Level-2以上：Level-2以上的磁盤(pán)層數都是由更底層級別的文件合并而來(lái)的文件，文件大小逐漸增大，排序方式也逐漸趨向于按照鍵值排序。由于每個(gè)層級的文件大小和排序方式不同，因此可以根據查詢(xún)的需求，會(huì )選擇更適合的層級進(jìn)行查詢(xún)，從而提高查詢(xún)效率。
LSM樹(shù)的內存層和磁盤(pán)層之間存在多層級的分層結構，可以通過(guò)不同文件大小和排序方式，滿(mǎn)足不同的查詢(xún)需求。通過(guò)分層的方式，LSM樹(shù)能夠高效的進(jìn)行寫(xiě)入操作，并且能夠快速定位到所需要的數據。
Memtable
Memtable是存儲在內存中的數據結構，用于緩存最新寫(xiě)入的數據。當數據寫(xiě)入時(shí)，先將其存儲到Memtable中，然后再將Memtable中的數據刷新到磁盤(pán)當中，生成一個(gè)新的磁盤(pán)文件。
Memtable一般采用的數據結構有有序數組、有序鏈表、hash表、跳表、B樹(shù)，由于存儲在內存中，因此讀寫(xiě)速度非?？?，支持快速高吞吐量的寫(xiě)入操作。
當數據達到一定量時(shí)，需要將數據刷新到磁盤(pán)當中，生成一個(gè)新的磁盤(pán)文件，Flush操作會(huì )將Memtable的所有數據按照鍵的大小排序，并寫(xiě)入到磁盤(pán)當中。
為了減少Flush操作帶來(lái)的影響，通常會(huì )設置多個(gè)Memtable，當一個(gè)Memtable中的數量達到一定大小時(shí)，就將其刷寫(xiě)到磁盤(pán)中，并將其替換成一個(gè)新的MemTable。這個(gè)過(guò)程被稱(chēng)為“Compaction”。Compaction操作會(huì )將多個(gè)磁盤(pán)文件合并成一個(gè)新的磁盤(pán)文件，從而減少磁盤(pán)文件的數量，提高讀取性能。在Compaction操作中，也會(huì )同時(shí)將多個(gè)MemTable合并到一起，生成一個(gè)新的MemTable，從而減少Flush操作的頻率，提高寫(xiě)入性能。
Immutable MemTable
Immutable MemTable是指已經(jīng)被刷寫(xiě)到磁盤(pán)中的、不可修改的MemTable。當一個(gè)MemTable達到一定的大小后，會(huì )被Flush到磁盤(pán)中，生成一個(gè)新的SSTable文件。同時(shí)將該MemTable標記為Immutable MemTable。
在LSM樹(shù)的Compaction過(guò)程中，多個(gè)Immutable MemTable會(huì )被合并成一個(gè)新的SSTable文件。Compaction操作也會(huì )將多個(gè)SSTable文件合并成一個(gè)新的SSTable文件，并將其中的重復數據進(jìn)行去重。因為Immutable MemTable是只讀的，所以它們在Compaction過(guò)程中是不會(huì )被修改的，這樣就可以避免數據沖突和一致性問(wèn)題。
SSTable(Sorted String Table)
SSTable是LSM樹(shù)中的一種數據存儲結構，用于存儲已經(jīng)被flush到磁盤(pán)的Immutable MemTable數據。它的特點(diǎn)是數據按照key有序存儲，并且支持快速的范圍查詢(xún)和迭代訪(fǎng)問(wèn)。
SSTable是由多個(gè)數據塊（Data Block）和一個(gè)索引塊（Index Block）組成。數據塊中存儲著(zhù)按照key有序排列的數據，索引塊中存儲著(zhù)數據塊的位置和對應的key。
SSTable中的數據塊采用了一些壓縮算法，例如LZ4、Snappy等，可以有效地壓縮數據，減少磁盤(pán)存儲空間。同時(shí)，SSTable還支持Bloom Filter等數據結構，可以提高查詢(xún)的效率。
SSTable是LSM樹(shù)中非常重要的一種數據存儲結構，通過(guò)有序的存儲方式和快速的索引訪(fǎng)問(wèn)方式，提高了查詢(xún)性能和存儲空間的利用率。
Compaction
在LSM樹(shù)中，數據的更新是通過(guò)追加日志形式完成的。這種追加方式使得LSM樹(shù)可以順序寫(xiě)，避免了頻繁的隨機寫(xiě)，從而提高了寫(xiě)性能。
在LSM樹(shù)中，數據被存儲在不同的層次中，每個(gè)層次對應一組SSTable文件。當MemTable中的數據達到一定的大小時(shí)，會(huì )被刷寫(xiě)（flush）到磁盤(pán)上，生成一個(gè)新的SSTable文件。這種以追加式的更新方式會(huì )導致數據冗余的問(wèn)題。需要定期進(jìn)行SSTable的合并（Compaction）操作，將不同的SSTable文件中相同Key的數據進(jìn)行合并，并將舊版本的數據刪除，從而減少冗余數據的存儲空間。
數據在LSM樹(shù)中存儲的方式，讀取時(shí)需要從最新的SSTable文件開(kāi)始倒著(zhù)查詢(xún)，直到找到需要的數據。這種倒著(zhù)查詢(xún)的方式會(huì )降低讀取性能，尤其是在存在大量SSTable文件的情況下。為了提高讀取性能，LSM樹(shù)通常會(huì )采用一些技術(shù)，例如索引和布隆過(guò)濾器來(lái)優(yōu)化查詢(xún)速度，減少不必要的磁盤(pán)訪(fǎng)問(wèn)。
壓縮
LSM樹(shù)壓縮策略需要圍繞三個(gè)問(wèn)題進(jìn)行考量：
- 讀放大：在讀取數據時(shí)，需要讀取的數據量大于實(shí)際的數據量。在LSM樹(shù)中，需要先在MemTable中查看是否存在該key，如果不存在，則需要繼續在SSTable中查找，直到找到為止。如果數據被分散在多個(gè)SSTable中，則需要遍歷所有的SSTable，這就導致了讀放大。如果數據分布比較均勻，則讀放大不會(huì )很?chē)乐?，但如果數據分布不均，則可能需要遍歷大量的SSTable才能找到目標數據。
- 寫(xiě)放大：在寫(xiě)入數據時(shí)，實(shí)際寫(xiě)入的數據量大于真正的數據量。在LSM樹(shù)中寫(xiě)入數據時(shí)可能會(huì )觸發(fā)Compact操作，這會(huì )導致一些SSTable中的冗余數據被清理回收，但同時(shí)也會(huì )產(chǎn)生新的SSTable，因此實(shí)際寫(xiě)入的數據量可能遠大于該key的數據量。
- 空間放大：數據實(shí)際占用的磁盤(pán)空間比數據的真正大小更多。在LSM樹(shù)中，由于數據的更新是以日志形式進(jìn)行的，因此同一個(gè)key可能在多個(gè)SSTable中都存在，而只有最新的那條記錄是有效的，之前的記錄都可以被清理回收。這就導致了空間的浪費，也就是空間放大。
size-tiered 策略
Size-tiered策略是一種常用的Compaction策略。它可以有效地減少SSTable的數量和大小，降低查詢(xún)時(shí)的磁盤(pán)讀取次數和延遲，提高LSM樹(shù)的查詢(xún)性能和空間利用率。
- 統計每個(gè)層級中的SSTable數量和總大小。當某個(gè)層級中的SSTable數量達到預設的閾值N后，就會(huì )觸發(fā)Compaction操作。
- 將該層級中的所有SSTable按照大小分成若干組。每組的大小大致相等。
- 對于每組SSTable，選擇一個(gè)合適的合并策略。常用的合并策略包括兩兩合并（Two-Level Merge）、級聯(lián)合并（Cascade Merge）和追加合并（Append Merge）等。
- 執行合并操作，將同一組中的SSTable合并為一個(gè)更大的SSTable，并將合并后的結果寫(xiě)入到下一層級的隊尾。這樣可以保持每個(gè)層級中的SSTable大小相近，從而減少后續Compaction操作的成本。
- 更新索引和元數據信息，記錄新生成的SSTable的位置、大小和版本號等信息，以便后續的查詢(xún)和Compaction操作。
- 刪除原有的SSTable文件，釋放磁盤(pán)空間。如果需要保留一定數量的歷史版本，則可以將舊的SSTable文件移動(dòng)到歷史版本目錄中，以便后續的查詢(xún)和回滾操作。
leveled 策略
Leveled策略是一種基于有序SSTable的高效Compaction策略。它可以有效地減小空間放大和讀放大問(wèn)題，提高LSM樹(shù)的查詢(xún)性能和空間利用率。
當一個(gè) SSTable 中的數據量達到一定大小時(shí)，它就會(huì )被合并到上一層，這個(gè)過(guò)程被稱(chēng)為 L0 合并（Level 0 Merge）。在 L0 合并時(shí)，相鄰的 SSTable 會(huì )被合并成一個(gè)更大的 SSTable，這樣可以減少 SSTable 的數量，降低查詢(xún)時(shí)需要掃描的 SSTable 的數量，從而提高查詢(xún)效率。
在 L0 合并完成之后，新生成的 SSTable 會(huì )被插入到第 1 層，如果第 1 層的 SSTable 數量超過(guò)了限制，那么就會(huì )進(jìn)行 L1 合并，將相鄰的 SSTable 合并成一個(gè)更大的 SSTable，同樣的過(guò)程會(huì )在第 2 層、第 3 層等等一直進(jìn)行下去，直到最高層。
當進(jìn)行查詢(xún)時(shí)，LSM 樹(shù)會(huì )從最底層開(kāi)始查找，如果在當前層的 SSTable 中找不到需要的數據，就會(huì )往上一層查找，直到找到需要的數據或者到達最高層。由于每一層的 SSTable 都是有序的，因此可以使用二分查找等算法來(lái)加速查詢(xún)。
評論
