（一）背景
MyTopling 是基于?ToplingDB?的?MySQL，分叉自 MyRocks，ToplingDB 則分叉自 RocksDB，兼容 RocksDB 接口，從而 MyTopling 可以復(fù)用 MyRocks 的大部分成果。
ToplingDB?早已開源，MyTopling 也會(huì)于近期開源。
（二）rocords_in_range
MySQL 查詢規(guī)劃（Query Plan）中有一個(gè)操作：預(yù)估待查詢的范圍中有多少條數(shù)據(jù)。這個(gè)操作下推到存儲(chǔ)引擎：
1.在 InnoDB 這樣的 BTree 中，只需要看一下靠近根部的結(jié)點(diǎn)就可以了。
2.RocksDB 中，通過 ApproximateSize(startKey, endKey) 來實(shí)現(xiàn)，得到 size 之后，再除以 KV 的平均尺寸就可以了，這個(gè)信息在 BlockBasedTable 通過二分搜索 SST 中的 BlockIndex 就可以得到
在 ToplingDB 中，只要兼容 RocksDB API，對(duì)我們自己的 SST 類型，就要實(shí)現(xiàn)自己的 ApproximateSize，然后所有上層代碼就不用任何改動(dòng)，從而復(fù)用整個(gè) RocksDB 的生態(tài)系統(tǒng)。
ToplingDB 有兩種 SST 必須實(shí)現(xiàn) ApproximateSize：
2.1 Topling Fast Table
對(duì) Fast Table，它使用的 CSPP 索引不是 BTree，CSPP 為了結(jié)構(gòu)的緊湊和并發(fā)性能，其結(jié)點(diǎn)沒有存儲(chǔ)任何冗余信息，從而不能象 BTree 一樣，僅通過靠近根部的結(jié)點(diǎn)就能得到近似的信息，好在 CSPP 的搜索極快，所以能快速地定位到具體的 Key，然后得到其中存儲(chǔ)的 ValueOffset，就能計(jì)算出 Value 的 ApproximateSize 了，為了更準(zhǔn)確，我們還得把 CSPP 索引所占的空間平攤到每條 KV 上，總體上還是比較簡單的。
2.2 Topling Zip Table
對(duì)于 Topling Zip Table，情況稍微復(fù)雜一些，實(shí)際上，Topling Zip Table 的 ApproximateSize 是 (approximate)rocords_in_range 語義，只是因?yàn)?RocksDB 沒有 rocords_in_range API，而整個(gè) RocksDB 生態(tài)系統(tǒng)都用 ApproximateSize 來模擬 (approximate)rocords_in_range 語義，所以在 Topling Zip Table 中，為兼容 RocksDB 生態(tài)而實(shí)現(xiàn)的 ApproximateSize，饒了一個(gè)圈，又回到了應(yīng)用更關(guān)心的 (approximate)rocords_in_range 語義……
Topling Zip Table 有多種索引類型，每種索引都支持 Key 的 Bytewise Order Rank，我們簡稱為 KeyRank：
1.對(duì) NLT 索引，它支持精確的 KeyRank 操作，但這個(gè)操作很慢，比搜索還要慢 3 倍左右
2.對(duì)?UintIndex，它能以最簡單快捷的方式，支持精確的 KeyRank 操作
3.對(duì)?帶有 雙數(shù)組 DoubleArray Trie Cache 的 FixLenKeyIndex
? ?1.第一時(shí)間想到的方案是僅搜索?DoubleArray Trie?Cache，這也是極快的操作，大多數(shù)情況下，只有 3~5 次（在 Cache 中隨機(jī)的）內(nèi)存訪問
? ?2.但是?DoubleArray Trie?Cache 在不同路徑上的深度可能不同，導(dǎo)致這樣計(jì)算的(Approximate)KeyRank 不是按 Key 單調(diào)遞增的
所以 NLT 和?FixLenKeyIndex?都需要優(yōu)化 KeyRank，我們的處理方式也非常簡單直接：對(duì) Index Key 按一定比例（默認(rèn)0.1%）等間隔采樣，然后放到一個(gè)定長 Key 數(shù)組中，當(dāng)然這個(gè)數(shù)組不需要保存每條完整的 Key，只需要保存最短可區(qū)分前綴就可以了。
（三）拖后腿的調(diào)用鏈開銷
在 ToplingDB 中，性能墻最終總會(huì)收斂到 RocksDB，但是，要兼容復(fù)用 RocksDB 生態(tài)，這是必須付出的代價(jià)，哪怕是 ApproximateSize 這樣的 API，也不例外。我們?cè)诨鹧鎴D中發(fā)現(xiàn)：
藍(lán)框中的代碼，竟然不可思議地是這兩行：
它占的時(shí)間，竟然比真正干活的代碼還要多！好在這個(gè)問題很好解決，代碼改動(dòng)也不大，所以，我在 ToplingDB 中修改并驗(yàn)證后，順便給 RocksDB 提了一個(gè)?Pull Request: Optimize.db impl.get approximate sizes by rockeet · Pull Request #10634。
這個(gè)改進(jìn)，把 GetApproximateSize 的時(shí)間占比，從?7.01%降到了?5.91%， 降幅?16%?:
（四）把?去虛擬化?進(jìn)行到底
在上面那個(gè)火焰圖中我們還可以看到，Compare 虛函數(shù)的調(diào)用開銷也挺大的，這個(gè)問題我們之前通過去虛擬化(devirtualization)?得到了數(shù)量級(jí)的性能提升。以之前的去虛擬化為基礎(chǔ)，在這里直接套用一下就行，然后我們看新的火焰圖：
GetApproximateSize 的時(shí)間占比，從?5.91%?降到了?4.88%?，降幅?17%，跟初始版本相比，是從 7.01% 降到?4.88%?，降幅?30%！
ToplingDB 的核心競爭力，不光是云原生架構(gòu)和算法的創(chuàng)新，還有這些看似不起眼的點(diǎn)點(diǎn)滴滴……
