使用高斯Redis實現二級索引
摘要：高斯Redis 搭建業務二級索引，低成本，高效能，實現效能與成本的雙贏。
本文分享自華為雲社群《華為雲GaussDB(for Redis)揭祕第21期：使用高斯Redis實現二級索引》，作者：高斯Redis官方部落格。
一、背景
提起索引，第一印象就是資料庫的名詞，但是，高斯Redis也可以實現二級索引！！！高斯Redis中的二級索引一般利用zset來實現。高斯Redis相比開源Redis有著更高的穩定性、以及成本優勢，使用高斯Redis zset實現業務二級索引，可以獲得效能與成本的雙贏。
索引的本質就是利用有序結構來加速查詢，因而通過Zset結構高斯Redis可以輕鬆實現數值型別以及字元型別索引。
• 數值型別索引（zset按分數排序）：
• 字元型別索引（分數相同時zset按字典序排序）：
下面讓我們切入兩類經典業務場景，看看如何使用高斯Redis來構建穩定可靠的二級索引系統。
二、場景一：詞典補全
當在瀏覽器中鍵入查詢時，瀏覽器通常會按照可能性推薦相同字首的搜尋，這種場景可以用高斯Redis二級索引功能實現。
2.1 基本方案
最簡單的方法是將使用者的每個查詢新增到索引中。當需要進行使用者輸入補全推薦時，使用ZRANGEBYLEX執行範圍查詢即可。如果不希望返回太多條目，高斯Redis還支援使用LIMIT選項來減少結果數量。
• 將使用者搜尋banana新增進索引：
ZADD myindex 0 banana:1
• 假設使用者在搜尋表單中輸入「bit」，並且我們想提供可能以「bit」開頭的搜尋鍵碼。
ZRANGEBYLEX myindex "[bit" "[bit\xff"
即使用ZRANGEBYLEX進行範圍查詢，查詢的區間為使用者現在輸入的字串，以及相同的字串加上一個尾隨位元組255（\xff）。通過這種方式，我們可以獲得以使用者鍵入字串為字首的所有字串。
2.2 與頻率相關的詞典補全
實際應用中通常希望按照出現頻率自動排序補全詞條，同時可以清除不再流行的詞條，並自動適應未來的輸入。我們依然可以使用高斯Redis的ZSet結構實現這一目標，只是在索引結構中，不僅需要儲存搜尋詞，還需要儲存與之關聯的頻率。
• 將使用者搜尋banana新增進索引
• 判斷banana是否存在
ZRANGEBYLEX myindex "[banana:" + LIMIT 0 1
• 假設banana不存在，新增banana:1，其中1是頻率
ZADD myindex 0 banana:1
• 假設banana存在，需要遞增頻率
若ZRANGEBYLEX myindex "[banana:" + LIMIT 0 1 中返回的頻率為1
1）刪除舊條目：
ZREM myindex 0 banana:1
2）頻率加一重新加入：
ZADD myindex 0 banana:2
請注意，由於可能存在並行更新，因此應通過Lua指令碼傳送上述三個命令，用Lua script自動獲得舊計數並增加分數後重新新增條目。
• 假設使用者在搜尋表單中輸入「banana」，並且我們想提供相似的搜尋鍵碼。通過ZRANGEBYLEX獲得結果後按頻率排序。
ZRANGEBYLEX myindex "[banana:" + LIMIT 0 10 1) "banana:123" 2) "banaooo:1" 3) "banned user:49" 4) "banning:89"
• 使用流演演算法清除不常用輸入。從返回的條目中隨機選擇一個條目，將其分數減1，然後將其與新分數重新新增。但是，如果新分數為0，我們需從列表中刪除該條目。
• 若隨機挑選的條目頻率是1，如banaooo:1
ZREM myindex 0 banaooo:1
• 若隨機挑選的條目頻率大於1，如banana:123
ZREM myindex 0 banana:123 ZADD myindex 0 banana:122
從長遠來看，該索引會包含熱門搜尋，如果熱門搜尋隨時間變化，它還會自動適應。
三、場景二：多維索引
除了單一維度上的查詢，高斯Redis同樣支援在多維資料中的檢索。例如，檢索所有年齡在50至55歲之間，同時薪水在70000至85000之間的人。實現多維二級索引的關鍵是通過編碼將二維的資料轉化為一維資料，再基於高斯Redis zset儲存。
從視覺化視角表示二維索引。下圖空間中有一些點，它們代表我們的資料樣本，其中x和y是兩個變數，其最大值均為400。圖片中的藍色框代表我們的查詢。我們希望查詢x介於50和100之間，y介於100和300之間的所有點。
3.1 資料編碼
若插入資料點為x = 75和y = 200
1） 填充0（資料最大為400，故填充3位）
x = 075
y = 200
2） 交織數位，以x表示最左邊的數位，以y表示最左邊的數位，依此類推，以便建立一個編碼
027050
若使用00和99替換最後兩位，即027000 to 027099，map回x和y，即：
x = 70-79
y = 200-209
因此，針對x=70-79和y = 200-209的二維查詢，可以通過編碼map成027000 to 027099的一維查詢，這可以通過高斯Redis的Zset結構輕鬆實現。
同理，我們可以針對後四/六/etc位數位進行相同操作，從而獲得更大範圍。
3） 使用二進位制
為獲得更細的粒度，可以將資料用二進位制表示，這樣在替換數位時，每次會得到比原來大二倍的搜尋範圍。假設我們每個變數僅需要9位（以表示最多400個值的數位），我們採用二進位制形式的數位將是：
x = 75 -> 001001011
y = 200 -> 011001000
交織後，000111000011001010
讓我們看看在交錯表示中用0s ad 1s替換最後的2、4、6、8，...位時我們的範圍是什麼：
3.2 新增新元素
若插入資料點為x = 75和y = 200
x = 75和y = 200二進位制交織編碼後為000111000011001010，
ZADD myindex 0 000111000011001010
3.3 查詢
查詢：x介於50和100之間，y介於100和300之間的所有點
從索引中替換N位會給我們邊長為2^(N/2)的搜尋方塊。因此，我們要做的是檢查搜尋方塊較小的尺寸，並檢查與該數位最接近的2的冪，並不斷切分剩餘空間，隨後用ZRANGEBYLEX進行搜尋。
下面是範例程式碼：
def spacequery(x0,y0,x1,y1,exp) bits=exp*2 x_start = x0/(2**exp) x_end = x1/(2**exp) y_start = y0/(2**exp) y_end = y1/(2**exp) (x_start..x_end).each{|x| (y_start..y_end).each{|y| x_range_start = x*(2**exp) x_range_end = x_range_start | ((2**exp)-1) y_range_start = y*(2**exp) y_range_end = y_range_start | ((2**exp)-1) puts "#{x},#{y} x from #{x_range_start} to #{x_range_end}, y from #{y_range_start} to #{y_range_end}" # Turn it into interleaved form for ZRANGEBYLEX query. # We assume we need 9 bits for each integer, so the final # interleaved representation will be 18 bits. xbin = x_range_start.to_s(2).rjust(9,'0') ybin = y_range_start.to_s(2).rjust(9,'0') s = xbin.split("").zip(ybin.split("")).flatten.compact.join("") # Now that we have the start of the range, calculate the end # by replacing the specified number of bits from 0 to 1. e = s[0..-(bits+1)]+("1"*bits) puts "ZRANGEBYLEX myindex [#{s} [#{e}" } } end spacequery(50,100,100,300,6)
四、總結
本文介紹瞭如何通過高斯Redis搭建二級索引，二級索引在電商、圖（hexastore）、遊戲等領域具有廣泛的應用場景，高斯redis現網亦有很多類似應用。高斯Redis基於存算分離架構，依託分散式儲存池確保資料強一致，可方便的支援二級索引功能，為企業客戶提供穩定可靠、超高並行，且能夠極速彈性擴容的核心資料儲存服務。
附錄
- 本文作者：華為雲資料庫GaussDB(for Redis)團隊
- 杭州/西安/深圳簡歷投遞：[email protected]
- 更多產品資訊，歡迎存取官方部落格：bbs.huaweicloud.com/blogs/248875