我們知道，KeyValue 資料庫，就是透過搜尋 Key 得到 Value 的資料庫，所以 Key 需要索引，Value 不需要索引，並且，在絕大多數情況下，Key 的長度比 Value 的長度小得多。TerarkDB 有兩個核心概念：CO-Index 和 PA-ZipCO-Index： 即 Compressed Ordered Index，把一個型別為 ByteArray 的 Key，對映到一個整數 ID，這個 ID 用來訪問 PA-Zip 中相應的那條 Value。PA-Zip： Point Accessible Zip，可以看做是一個抽象的 array，核心功能是把 ID 作為抽象陣列的下標，去訪問該抽象陣列的元素，當然，這些元素都是壓縮儲存的。CO-Index 和 PA-Zip 一起，構成一個邏輯上的 mapTerark SST 由 CO-Index 和 PA-Zip 組成，建立 SST 的時候，實際上是建立 CO-Index 和 PA-Zip，既然 Key 很短，Value 很長，為了兼顧效能和記憶體用量：建立 CO-Index 時，我們會把相應的 Key 都放在記憶體中，建立 PA-Zip 時，只把關鍵資料（例如字典）放入記憶體，這算是最簡單的記憶體控制（暫且叫做記憶體控制-1）。建立 Terark SST 需要對輸入掃描兩遍建立 PA-Zip 時，我們需要對輸入掃描兩遍，第一遍計算 Value 的各種統計特徵，並且收集全域性字典，第二遍執行壓縮。RocksDB 使用 SSTBuilder 來構建 SST，構建過程中，對每條資料呼叫 SSTBuilder。Add（Key，Value），構建完成時，呼叫 SSTBuilder。Finish（），以這樣的方式，SSTBuilder 就只能對輸入序列掃描一次。如果要對輸入做第二次掃描，就需要付出一些努力。最初，我們在第一次掃描的過程中，把拿到的資料儲存到一個臨時檔案中，第二遍掃描直接讀那個臨時檔案。實際上，第二遍掃描只是按第一遍掃描的順序，把 value 讀一遍，所以這個臨時檔案只需要儲存 value。記憶體控制-2建立 CO-Index 和 PA-Zip 都需要大量記憶體，所以進一步的記憶體限制是必須的。第一次掃描中，我們總是把 Key 寫到臨時檔案中，到執行 Index 建立時，我們再把這個臨時檔案讀進記憶體：只有記憶體不會超限時，我們才會把 Key 檔案讀進記憶體，去建立 CO-Index如果記憶體超限，CO-Index 的建立就必須排隊等待PA-Zip 也一樣，如果記憶體超限（字典需要大量記憶體），也必須排隊等待。排隊策略也需要仔細設計：SST Flush 是把 MemTable 壓縮成 SST，這些 SST 的尺寸很小，建立時需要的記憶體也小，但優先順序最高Compaction 產生的 SST 大小各異，一般都很大，建立時需要的記憶體也很大，優先順序較低按照小作業優先的原則，大 SST 應該降低優先順序，但不能無限等待（大作業被餓死）不需要臨時檔案的兩遍掃描透過臨時檔案的方式實現兩遍掃描，需要不少磁碟空間，特別是對於我們，Terark SST 的尺寸都很大（尺寸越大，壓縮率越高，大多在 GB 級別），磁碟空間的需求就太多了。在官方版 RocksDB 的框架內，實現兩遍掃描沒有別的辦法，所以我們只有自己去魔改 RocksDB，魔改的過程充滿了各種曲折……最終，我們還是找到了辦法：建立一個專用的 Iterator 進行第二遍掃描，這個 Iterator 實際上是 RocksDB 自身第一遍掃描用的那個 Iterator 的深複製，所有相關的輔助物件，例如 Merger， RangeDelAggregator 。。。 都需要為第二遍掃描的 Iterator 建立一個副本，但CompactionFilter 不能深複製，兩個 Iterator 必須用同一個 CompactionFilter。Iterator 太慢貌似所有的問題都已經解決，我們只需要一點磁碟臨時空間，和很小的記憶體，就可以創建出 Terark SST，各項指標非常優異：SST 檔案尺寸非常小，比 RocksDB 原生的 SST 小得多，因為我們的壓縮率很高SST 記憶體佔用非常小，因為使用全域性壓縮演算法，記憶體用量的上限就是 SST 檔案尺寸SST 隨機訪問非常快，直接在壓縮的資料上進行定點訪問，省去了雙快取等不必要的開銷直到有一天，我們在 MyRocks 中碰到一個數據插入非常慢的問題，好日子忽然到頭了……在 MyRocks 中，如果某個 table 有 n 個索引（包括主鍵索引），對每一條 SQL 資料，在 RocksDB 儲存層就有 n 條 KeyValue 資料，每個索引佔一條，其中，輔助索引（Secondary Index）的 value 是空的。如果某個 table 有很多個輔助索引，就會產生很多條 value 為空的資料，這就是 Compact 效能殺手，下面我們解釋原因：Compact 相當於對多路（按 Key）有序的輸入序列進行歸併，產生一個有序的輸出序列，其中，可以把多路輸入和歸併演算法封裝起來，對外抽象成 MergeIterator，歸併的過程相當慢，RocksDB 的歸併演算法用 Heap，但即使用 LoserTree，也快不到哪裡去。這裡的主要問題在於：如果資料的總量（KeyValue 的總位元組數）相同當 value 很長的時候，KeyValue 的條目數就很小，整體的效能取決於 value 的解壓速度，MergeIterator 慢一點無所謂當 value 很短的時候，KeyValue 的條目數就很大，整體的效能取決於 MergeIteratorMyRocks 輔助索引的 value 甚至短到了 0，MergeIterator 就幾乎完全決定了總體的效能第二遍掃描（歸併）的行為和第一遍掃描完全一樣，這樣就又慢了一倍。省略 短 value 的第二遍掃描我們首先需要精確定義什麼是“短 value”，最簡單的定義就是：平均長度小於某個值SVL（Short Value Length）。SVL可以是個定值，但更合理的方案是使用相對值，相對於 Key 的長度。在我們的實現中，SVL = 2 * avg（KeyLen）。接下來，就是如何識別“短 value”識別“短 value”要識別“短 value”，最簡單直接的方法就是計算出它的平均長度：在第一遍掃描中累加長度，在 Finish 中計算出平均長度。但是這樣做，我們只有在 Finish 時才能知道是否需要第二遍掃描，這時已經太晚了……好在，我們知道，有一種策略叫做“Speculation”，也就是“投機”，或者“冒險”：在第一遍掃描開始的時候，將 value 寫入臨時檔案，直到寫入的尺寸大於某個預設值（例如 5M） 並且 當前的平均長度大於 SLV。粗體部分詮釋了“冒險”二字，因為 value 的長度分佈可能並不均勻，只有一定數量的 value 才有統計意義，5M 是一個拍腦袋值，應該足夠。這樣，在絕大多數情況，我們的冒險都會成功！非常簡單的策略，但是非常有效！給 CompactionIterator 增加 Seek（） 功能在大多數情況下，單個 SST 只有單個物理的 map 物件，上面的這些策略足以應付。但是，存在一些更復雜的情況：首先，因為 RocksDB 作為 KeyValue 儲存，是按 Key 有序的，從而，字首相同的 Key 集合，在邏輯上是相鄰的，在 RocksDB API 上就體現在：透過 Iterator。Seek 搜尋一個字首 P，會將 Iterator 定位到以 P 為字首的 Key （有序）集合的第一個（最小的） KeyValue 所在的位置，接著呼叫 Iterator。Next，遍歷就可以得到所有以 P 為字首的 KeyValue 集合。利用這個特性，可以實現更多的以 P 為字首的搜尋功能：Range 搜尋，字首搜尋，等等。 MyRocks 和 MongoRocks （以及其它一些基於 RocksDB 的資料庫） 就利用這個特性實現所有需要跨表跨庫跨索引的功能：每個 Key 包含一個字首，該字首用來區分一個 KeyValue 子集每個 KeyValue 子集就是一個 表/索引 的實現每個 SST 可以包含多個不同的字首 P，從而包括多個 表/索引在 SSTBuilder 的第一遍掃描中，如果 KeyValue 的 subset1 已掃描結束（碰到了下一個大一點的字首，對應 subset2），並且 subset1 滿足 短 Value 條件，在掃描 subset2 的過程中，發現 subset2 不滿足 短 Value 條件。到此為止，我們知道 subset1 在前，subset2 在後，其中 subset1 不需要第二遍掃描，subset2 需要第二遍掃描。所以，我們就需要在第二遍掃描的 CompactionIterator 中 跳過 subset1 對應的那個 Key Range。我們透過 Seek 來實現這個 跳過 的功能（一般而言，功能越強大，需要的代價越大，在這裡 Seek 的功能比 跳過 更強大，但實際上 Seek 的實現難度和效能和 跳過 都差不多）。Seek 需要的演算法並不難，但其中需要處理很多繁瑣的細節，比如需要正確處理 UserKey， MVCC SeqNum 等等。併發的 Index 構建在 SSTBuilder 的第一遍掃描中，在 KeyValue 的 subset1 掃描結束時（碰到了下一個 大一點的 字首，對應 subset2），如果此時記憶體用量沒有超限，subset1 的 Index 構建就可以立即在另一個執行緒中開始，而當前執行緒同時接著掃描 subset2， subset3 。。。更進一步，如果 subset1 不需要第二遍掃描，它的 PA-Zip（Value 儲存） 也可以併發構建。不能併發構建 PA-Zip 的情況理論上講，subset1 的 PA-Zip 是否可以併發構建與它是否需要第二遍掃描並沒有關係，只要記憶體、CPU 夠用，就應該儘量併發執行更多的工作：我們知道第一遍掃描用的是 Iterator1，第二遍掃描用的是 Iterator2，並且，Iterator1 （的位置）領先於 Iterator2如果 subset1 的第一遍已經掃描完成，並且 subset1 也需要第二遍掃描，那麼仍然可以立刻併發執行 subset1 的第二遍掃描和 subset2 的第一遍掃描現實是 RocksDB 支援插拔式的 CompactionFilter，我們無法預測這個 CompactionFilter 會有什麼陷阱，前面講到，Iterator2 不會對 CompactionFilter 進行深複製，這就是原因——我們在 MyRocks 和 MongoRocks 中的 CompactionFilter 中發現了這一點……
