基于 RocksDB 的索引數(shù)據(jù)存儲

-8-基于RocksDB的索引數(shù)據(jù)存儲NewSQL技術近幾年進展非常迅猛，國內外都有了較成熟的系統(tǒng)。在業(yè)界一些開源系統(tǒng)的實現(xiàn)中，Rocksdb起到了核心的存儲和查詢功能。其中的一個核心設計需求，就是把結構化的表數(shù)據(jù)以及索引數(shù)據(jù)轉換為kv數(shù)據(jù)存儲到Rocksdb中。本文就該需求的設計方案進行了介紹，以供大家參考。NewSQL技術近幾年進展非常迅猛，國內外都有了較成熟的系統(tǒng)。在業(yè)界一些開源系統(tǒng)的實現(xiàn)中，Rocksdb起到了核心的存儲和查詢功能。其中的一個核心設計需求，就是把結構化的表數(shù)據(jù)以及索引數(shù)據(jù)轉換為kv數(shù)據(jù)存儲到Rocksdb中。本文就該需求的設計方案進行了介紹，以供大家參考。

我們知道Rocksdb是一個kv形式的存儲引擎，就像一個有序的大map，map的key,value都是字節(jié)數(shù)組，其排序挨次就由key這個二進制字節(jié)數(shù)組打算。Rocksdb除了供應隨機讀寫kv的接口，還供應了創(chuàng)建一個迭代器，從大于等于某個key開頭的位置向下掃描數(shù)據(jù)的接口。

利用上述兩種接口，結合設計良好的數(shù)據(jù)存儲格式，Rocksdb就可以作為結構化數(shù)據(jù)存儲和查詢的引擎。

比如我們有如下數(shù)據(jù)表結構：

一、構造主鍵索引

首先為每一行記錄生成一條kv數(shù)據(jù)，k是temp表id字段，value是其他幾個字段序列化后的二進制字節(jié)數(shù)組。序列化協(xié)議可以自定義，也可以使用protobuf協(xié)議。

由于id字段是主鍵索引，當查詢條件是whereid=101或者whereidin(101,105,108)的時候，可以依據(jù)Rocksdb的get或者mget接口，高效的獵取某一條和某幾條數(shù)據(jù)。

當查詢條件是whereid-100andid200這樣的range查詢的時候，我們可以創(chuàng)建一個迭代器，指向第一個大于等于-100的記錄，然后向下掃描至200的記錄。這個操作需要一個seek隨機讀和一個scan挨次讀操作，也有很高的讀取性能。

要支持上述的range查詢，需要保證表數(shù)據(jù)在Rocksdb中，根據(jù)id字段的字節(jié)序遞增存儲。

假如直接將id字段的二進制位作為key存儲到Rocksdb中呢？我們知道整數(shù)在計算機中時根據(jù)補碼進行存儲，正數(shù)最高位是0，負數(shù)最高位是1，直接存儲就會造成負數(shù)存儲在正數(shù)的下面，造成規(guī)律挨次不全都的現(xiàn)象。

因此只要把非負數(shù)的最高位變成1，負數(shù)的最高位變成0，就可以保證key的二進制挨次和其代表的整數(shù)的數(shù)值挨次是全都的。如下圖：

就有了下面的轉換函數(shù)：

主鍵索引采納大端法進行存儲，下面介紹的各個索引也都采納大端法存儲。

二、構造整數(shù)字段索引

構造完了主鍵字段，接下來看第一個索引KEY`i_index`(`i`)。首先這是一個非唯一索引，因此Rocksdb的key字段，必需同時包含i字段和主鍵id字段，Rocksdb的value為空即可。

key的格式可以是2字節(jié)的i字段和2字節(jié)的id字段。i字段和id字段仍舊根據(jù)上述的最高位取反原則進行處理。這樣可以保證i_index先根據(jù)i字段排序，i字段相同的記錄再根據(jù)id字段排序。

在查詢wherei=100或者wherei-100andi200的時候，都可以轉換為Rocksdb的迭代器seek加scan操作。在獵取了滿意條件的主鍵id集合之后，可以從主鍵索引數(shù)據(jù)中，通過mget操作獵取id集合的完整數(shù)據(jù)。

假如i_index是一個唯一性索引，Rocksdb的key字段只需要包含i字段即可，value字段存儲id字段。

三、構造浮點數(shù)字段索引

接下來看其次個索引KEY`f_index`(`f`)。首先這個也是非唯一索引，構造的key中也需要包含f字段和id字段。id字段仍舊采納最高位取反的規(guī)律。對于f字段，由于其是一個浮點數(shù)，首先了解一下浮點數(shù)的存儲格式。

我們知道浮點數(shù)的二進制格式跟整數(shù)是不同的。比如float類型，由1個bit的符號位，8個bit的指數(shù)部分，23個bit的尾數(shù)部分組成。

回顧一下varffloat=10.75的二進制位是怎么存儲的呢？

把十進制小數(shù)轉換成為二進制小數(shù)，整數(shù)部分10轉換成二進制得到1010，小數(shù)部分0.75轉換成二進制得到0.11,所以10.75的二進制小數(shù)表示為1010.11；

對其做規(guī)格化處理，小數(shù)點向左移動3位，得到1.01011*2的3次方；

于是，8bit的指數(shù)部分由指數(shù)值3+127=130得到，130的二進制位是10000010(加127是固有的換算規(guī)律)；

23bit的尾數(shù)部分：由于二進制小數(shù)規(guī)格化處理之后(1.01011)，小數(shù)點之前總是1，因此只存儲小數(shù)點之后的01011五個bit；

最高位是符號位：正數(shù)為0；

最終的二進制表示為:01000001001011000000000000000000，16進制表示0x412c0000。

假如浮點數(shù)是-10.75呢，只是把最高位變成1即可。其16進制表示：0xc12c0000。

簡潔驗證一下結果：

我們發(fā)覺肯定值相同的兩個浮點數(shù)，只是最高位符號位的不同而已，其余各個bit都相同。

連續(xù)分析浮點數(shù)的二進制位。由于對二進制小數(shù)做了規(guī)格化，都變成了1.xxx*2的n次方這種格式。

在8bit指數(shù)部分相同的狀況下，23bit尾數(shù)越大，其浮點數(shù)值越大。例如1.01011*2的3次方(十進制10.75)大于1.01001*2的3次方(十進制10.25),其二進制表示也恰好滿意字節(jié)序的大于關系。

8bit指數(shù)部分二進制位越大的浮點數(shù)其值也越大。例如1.000*2的3次方(十進制8.0)大于全部的1.xxx*2的2次方數(shù)。

有了上述兩個規(guī)律：我們就能知道浮點數(shù)0的狀況，其二進制挨次就能代表其數(shù)值挨次。小于0的浮點數(shù)僅僅是最高符號位為1,其余各位跟其肯定值小數(shù)相同。

于是我們采納如下規(guī)章：

大于等于0的浮點數(shù)，最高位設為1。小于0的浮點數(shù)，其最高位設置為0。這條可以保證：負數(shù)的二進制字節(jié)序都小于正數(shù)的字節(jié)序，正數(shù)的字節(jié)序滿意字節(jié)序跟數(shù)值挨次全都。

負數(shù)的最高位設置為0以后，對其它位進行取反。

由于負數(shù)的字節(jié)序列是原碼表示，對原碼進行取反即可保證字節(jié)序和數(shù)值序全都。

得到最終的轉換函數(shù)：

因此，其次個索引KEY`f_index`(`f`),其寫入Rocksdb的key格式，可以是4字節(jié)經過浮點處理的f字段和2字節(jié)的經過整數(shù)處理的id字段，value為空。

四、構造字符串字段索引

接下來看第三個索引KEY`c_index`(`c`)，也是非唯一性索引，所以key中必需包含字符串c和id字段，value為空即可。

由于c字段是不定長的字符串，id字段直接放在其后會導致排序字段錯亂。

比如下面兩條索引數(shù)據(jù)：

可以看到，第一條索引的id=1006，其二進制由兩個字節(jié)組成，會參加跟其次條索引的de兩個字符構成的二進制位的比較。1006的二進制最高位取反后大于de兩個字符的二進制位，就會導致排序挨次不正確。而且字符串本身也需要一個長度字段，也會影響到整體的排序正確性。

Facebook利用Rocksdb，為mysql實現(xiàn)了一版存儲引擎，其中創(chuàng)建字符串索引部分采納了以下算法。(該算法在tidb中也得到了應用)

首先將字符串根據(jù)8字節(jié)為一組，分成若干組，group_num=len(str)/8+1。

最終一組不夠8字節(jié)，對其補足若干個二進制0。

對每一組末尾添加一個字節(jié)，字節(jié)的值是255減去該組填充的0字節(jié)的個數(shù)。

比如有下面幾個字符串的轉換示例：

這樣構造完成c字段的編碼字節(jié)數(shù)組，在其后接上兩字節(jié)的經過最高位取反的id字段，組成一個key寫入Rocksdb中即可。

簡潔分析一下該算法：

在兩條記錄的c字段字符串長度都小于8的狀況下，由于都補齊了8字節(jié)，后面id字段并不會導致排序錯亂。比如有下面三條index數(shù)據(jù)。

在一條記錄的c字段小于8字節(jié)，另一條記錄的c字段大于8字節(jié)的時候，比如有下面兩條index數(shù)據(jù)：

由于c字段為abc的短字符串，其后添加了5個0，已然小于下面的長字符串，其后的字符串長度字段或id字段，再也沒有機會影響短字符串跟長字符串的比較了。

五、構造聯(lián)合索引

接下來我們看一個聯(lián)合索引KEY`i_f_index`(`i`,`f`)，這個是一個整數(shù)加一個浮點數(shù)。由于是非唯一索引，所以寫入Rocksdb的key由兩字節(jié)的i字段(最高位取反)+4字節(jié)的f字段(最高位取反+負數(shù)其他位也取反)+2字節(jié)的主鍵id字段(最高位取反)，value為空即可。

最終一個聯(lián)合索引KEY`i_c_f_index`(`i`,`c`,`f`)，key中包含四種數(shù)據(jù)類型：整數(shù)，字符串，浮點數(shù)和主鍵id。只需要根據(jù)上述介紹的算法，依次處理每種數(shù)據(jù)類型拼接出key即可。

六、總結

我們有了索引，就可以像mysql一樣，依據(jù)索引快速定位數(shù)據(jù)。假