NewSQL技術近幾年發展十分迅猛，國內外都有了較成熟的系統。在業界一些開源系統的實現中，Rocksdb起到了核心的存儲和查詢功能。其中的一個核心設計需求，就是把結構化的表數據以及索引數據轉換為kv數據存儲到Rocksdb中。本文就該需求的設計方案進行了介紹，以供大家參考。

我們知道Rocksdb是一個kv形式的存儲引擎，就像一個有序的大map，map的key,value都是字節數組，其排序順序就由key這個二進制字節數組決定。Rocksdb除了提供隨機讀寫kv的接口，還提供了創建一個迭代器，從大於等於某個key開始的位置向下掃描數據的接口。

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

比如我們有如下數據表結構：

TABLE `temp` (
 `id` smallint(6) NOT NULL,
 `i` smallint(6) NOT NULL,
 `f` float NOT NULL,
 `c` char(60) NOT NULL,
 `msg` char(120) DEFAULT NULL,
 PRIMARY KEY (`id`),
 KEY `i_index` (`i`),
 KEY `f_index` (`f`),
 KEY `c_index` (`c`),
 KEY `i_f_index` (`i`,`f`),
 KEY `i_c_f_index` (`i`,`c`,`f`)
)

一、構造主鍵索引

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

因為id字段是主鍵索引，當查詢條件是 where id = 101 或者where id in ( 101,105,108)的時候，可以根據Rocksdb的get或者mget接口，高效的獲取某一條和某幾條數據。

當查詢條件是 where id > -100 and id < 200 這樣的range查詢的時候，我們可以創建一個迭代器，指向第一個大於等於-100的記錄，然後向下掃描至200的記錄。這個操作需要一個seek隨機讀和一個scan順序讀操作，也有很高的讀取性能。

要支持上述的range查詢，需要保證表數據在Rocksdb中，按照id字段的字節序遞增存儲。

如果直接將id字段的二進制位作為key存儲到Rocksdb中呢？我們知道整數在計算機中時按照補碼進行存儲，正數最高位是0，負數最高位是1，直接存儲就會造成負數存儲在正數的下面，造成邏輯順序不一致的現象。

因此只要把非負數的最高位變成1，負數的最高位變成0，就可以保證key的二進制順序和其代表的整數的數值順序是一致的。如下圖：

就有了下面的轉換函數：

var N uint16 = 0x8000
func encodeInt16(i int16) []byte {
 u := uint16(i) + N
 buf := make([]byte, 2)
 binary.BigEndian.PutUint16(buf, u)
 return buf
}
func decodeToInt16(buf []byte) (int16, error) {
 if len(buf) < 2 {
 return 0, fmt.Errorf("invalid buf")
 }
 u := binary.BigEndian.Uint16(buf)
 i := int16(u - N)
 return i, nil
}

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

二、構造整數字段索引

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

key的格式可以是2字節的i字段和2字節的id字段。i字段和id字段仍然按照上述的最高位取反原則進行處理。這樣可以保證i_index先按照i字段排序，i字段相同的記錄再按照id字段排序。

在查詢 where i = 100 或者where i > -100 and i < 200的時候，都可以轉換為Rocksdb的迭代器seek加scan操作。在獲取了滿足條件的主鍵id集合之後，可以從主鍵索引數據中，通過mget操作獲取id集合的完整數據。

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

三、構造浮點數字段索引

接下來看第二個索引KEY `f_index` (`f`) 。首先這個也是非唯一索引，構造的key中也需要包含f 字段和id字段。id字段仍然採用最高位取反的邏輯。對於f字段，因為其是一個浮點數，首先了解一下浮點數的存儲格式。

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

回顧一下 var f float =10.75 的二進制位是怎麼存儲的呢？

1. 把十進制小數轉換成為二進制小數，整數部分10轉換成二進制得到 1010，小數部分0.75轉換成二進制得到0.11, 所以10.75的二進制小數表示為1010.11；
2. 對其做規格化處理，小數點向左移動3位，得到1.01011 * 2的3次方；
3. 於是，8bit的指數部分由指數值3+127=130得到，130的二進制位是10000010(加127是固有的換算邏輯)；
4. 23bit的尾數部分：因為二進制小數規格化處理之後(1.01011)，小數點之前總是1，因此只存儲小數點之後的01011五個bit；
5. 最高位是符號位：正數為0；
6. 最終的二進制表示為:0 10000010 01011000000000000000000，16進製表示0x412c0000。

如果浮點數是-10.75呢，只是把最高位變成1即可。其16進製表示：0xc12c0000。

簡單驗證一下結果：

func print(u uint32) {
 f := *(*float32)(unsafe.Pointer(&u))
 fmt.Printf("%f ", f)
}
func main() {
 print(0x412c0000)
 print(0xc12c0000)
}
10.750000 -10.750000 
Process finished with exit code 0

我們發現絕對值相同的兩個浮點數，只是最高位符號位的不同而已，其餘各個bit都相同。

繼續分析浮點數的二進制位。由於對二進制小數做了規格化，都變成了1.xxx * 2的n次方這種格式。

1. 在8bit指數部分相同的情況下，23bit尾數越大，其浮點數值越大。例如 1.01011 *2的3次方 (十進制10.75) 大於 1.01001*2的3次方(十進制10.25), 其二進制表示也恰好滿足字節序的大於關係。
2. 8bit指數部分二進制位越大的浮點數其值也越大。例如 1.000*2的3次方 (十進制8.0) 大於所有的1.xxx*2的2次方數。

有了上述兩個規律：我們就能知道浮點數>0的情況，其二進制順序就能代表其數值順序。小於0的浮點數僅僅是最高符號位為1,其餘各位跟其絕對值小數相同。

於是我們採用如下規則：

1. 大於等於0的浮點數，最高位設為1。小於0的浮點數，其最高位設置為0。這條可以保證：負數的二進制字節序都小於正數的字節序，正數的字節序滿足字節序跟數值順序一致。
2. 負數的最高位設置為0以後，對其它位進行取反。

因為負數的字節序列是原碼錶示，對原碼進行取反即可保證字節序和數值序一致。

得到最終的轉換函數：

func encodeFloat(f float32) []byte {
​
 u := *(*uint32)(unsafe.Pointer(&f))
 if f >= 0 {
 u |= 0x80000000
 } else {
 u = ^u
 }
 buf := make([]byte, 4)
 binary.BigEndian.PutUint32(buf, u)
 return buf
}
​
func decodeToFloat(buf []byte) (float32, error) {
​
 if len(buf) < 2 {
 return 0, fmt.Errorf("invalid buf")
 }
 u := binary.BigEndian.Uint32(buf)
 if u >= 0x80000000 {
 u += 0x80000000
 } else {
 u = ^u
 }
 f := *(*float32)(unsafe.Pointer(&u))
 return f, nil
}

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

四、構造字符串字段索引

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

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

比如下面兩條索引數據：

abc 1006 (代表記錄 id=1006 c=abc) 
abcdefgh 1005 (代表記錄 id=1005 c=abcdefgh) 

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

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

1. 首先將字符串按照8字節為一組，分成若干組，group_num= len(str)/8 + 1。
2. 最後一組不夠8字節，對其補足若干個二進制0。
3. 對每一組末尾添加一個字節，字節的值是 255減去該組填充的0字節的個數。

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

[] -> [0,0,0,0,0,0,0,0,247] (空字符串) 
[1,2,3] -> [1,2,3,0,0,0,0,0,250] (字符串123)
[1,2,3,0] -> [1,2,3,0,0,0,0,0,251] (字符串123\0)
[1,2,3,4,5,6,7,8]->[1,2,3,4,5,6,7,8,255,0,0,0,0,0,0,0,0,247] 
(字符串12345678)
[1,2,3,4,5,6,7,8,9]->[1,2,3,4,5,6,7,8,255,9,0,0,0,0,0,0,0,248]
(字符串123456789)

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

簡單分析一下該算法：

在兩條記錄的c字段字符串長度都小於8的情況下，由於都補齊了8字節，後面id字段並不會導致排序錯亂。比如有下面三條index數據。

abc00000,250,1001 ( 代表記錄 id=1001, c=abc )
abcdef00,253,1002 ( 代表記錄 id=1002, c=abcdef )
ad000000,249,1003 ( 代表記錄 id=1003, c=ad )

在一條記錄的c字段小於8字節，另一條記錄的c字段大於8字節的時候，比如有下面兩條index數據：

abc00000,250,1001 ( 代表記錄 id=1001, c=abc )
abcdefgh,255,abc00000,250, 1004 ( 代表記錄 id=1004, c=abcdefghabc)

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

五、構造聯合索引

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

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

六、總結

我們有了索引，就可以像mysql一樣，根據索引快速定位數據。如果一個查詢語句有很多個過濾條件，涉及多個索引字段，選擇不同的索引進行查詢，得到的性能是不一樣的。因此，也需要像mysql一樣根據一些統計信息構造出一個查詢計劃，選擇合適的索引列進行查詢。感興趣的同學可以繼續關注一下直方圖以及Count-Min Sketch等數據結構。另外，也需要深入瞭解Rocksdb的get mget seek scan等操作的原理和性能，結合數據庫的統計信息才能更好的構造查詢計劃。

歡迎大家關注“58架構師”微信公眾號，定期分享雲計算、AI、區塊鏈、大數據、搜索、推薦、存儲、中間件、移動、前端、運維等方面的前沿技術和實踐經驗。

閱讀更多 58架構師 的文章

關鍵字: 存儲 NewSql 數據