NewSQL技術近幾年發(fā)展十分迅猛，國內外都有了較成熟的系統(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字段是主鍵索引，當查詢條件是 where id = 101 或者where id in ( 101,105,108)的時候，可以根據(jù)Rocksdb的get或者mget接口，高效的獲取某一條和某幾條數(shù)據(jù)。
當查詢條件是 where id > -100 and id < 200 這樣的range查詢的時候，我們可以創(chuàng)建一個迭代器，指向第一個大于等于-100的記錄，然后向下掃描至200的記錄。這個操作需要一個seek隨機讀和一個scan順序讀操作，也有很高的讀取性能。
要支持上述的range查詢，需要保證表數(shù)據(jù)在Rocksdb中，按照id字段的字節(jié)序遞增存儲。
如果直接將id字段的二進制位作為key存儲到Rocksdb中呢？我們知道整數(shù)在計算機中時按照補碼進行存儲，正數(shù)最高位是0，負數(shù)最高位是1，直接存儲就會造成負數(shù)存儲在正數(shù)的下面，造成邏輯順序不一致的現(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字段仍然按照上述的最高位取反原則進行處理。這樣可以保證i_index先按照i字段排序，i字段相同的記錄再按照id字段排序。
在查詢 where i = 100 或者where i > -100 and i < 200的時候，都可以轉換為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字段仍然采用最高位取反的邏輯。對于f字段，因為其是一個浮點數(shù)，首先了解一下浮點數(shù)的存儲格式。
我們知道浮點數(shù)的二進制格式跟整數(shù)是不同的。比如float類型，由1個bit的符號位，8個bit的指數(shù)部分，23個bit的尾數(shù)部分組成。
回顧一下 var f float =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是固有的換算邏輯)；
23bit的尾數(shù)部分：因為二進制小數(shù)規(guī)格化處理之后(1.01011)，小數(shù)點之前總是1，因此只存儲小數(shù)點之后的01011五個bit；
最高位是符號位：正數(shù)為0；
最終的二進制表示為:0 10000010 01011000000000000000000，16進制表示0x412c0000。
如果浮點數(shù)是-10.75呢，只是把最高位變成1即可。其16進制表示：0xc12c0000。
簡單驗證一下結果：
我們發(fā)現(xiàn)絕對值相同的兩個浮點數(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中也得到了應用)
首先將字符串按照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。只需要按照上述介紹的算法，依次處理每種數(shù)據(jù)類型拼接出key即可。
六、總結
我們有了索引，就可以像mysql一樣，根據(jù)索引快速定位數(shù)據(jù)。如果一個查詢語句有很多個過濾條件，涉及多個索引字段，選擇不同的索引進行查詢，得到的性能是不一樣的。因此，也需要像mysql一樣根據(jù)一些統(tǒng)計信息構造出一個查詢計劃，選擇合適的索引列進行查詢。感興趣的同學可以繼續(xù)關注一下直方圖以及Count-Min Sketch等數(shù)據(jù)結構。另外，也需要深入了解Rocksdb的get mget seek scan等操作的原理和性能，結合數(shù)據(jù)庫的統(tǒng)計信息才能更好的構造查詢計劃。
