超大數據下大批量隨機鍵值的查詢優化方案

一、問題描述

鍵值查詢是很常見的查詢場景，在數據表上建有索引后，即使表中數據記錄數巨大（幾億甚至幾十億行），用鍵值查詢出單條記錄也會很快，因為建立索引后的復雜度只有 logN（以 2 為底）次， 10 億行數據也只要比較 30 次（10 億約等于 2^30），在現代計算機上也只需要數十毫秒而已。

不過，如果需要查詢的鍵值很多，比如多達幾千甚至幾萬的時候，如果每次都獨立查找，那讀取和比較也會累積到幾萬甚至幾十萬次，時間延遲由此也會漲到幾十分鐘甚至小時級別，這時候簡單地使用數據庫索引對于用戶體驗必然是難以容忍的了。

二、場景舉例

下面我們要介紹的集算器組表功能，基于高性能索引和批量鍵值查找，可以有效地應對這種場景。我們會按照以下幾種順序逐步深入討論：

1）單字段鍵

2）多字段鍵

3）多線程查詢

4）數據追加的處理

需要說明的，本文只研討單機的情況，后續還有文章會繼續深入討論基于集群的方案。

2.1 單字段鍵

我們以下表這種比較典型的數據結構為例：

2.1.1創建組表

首先我們創建一個組表，把源數據導入組表：

A1：建立并打開指定文件對象，這里的 single.ctx 是將要創建的組表文件，擴展名用 ctx。關于組表的詳細定義和使用方法可以參考集算器教程。

A2：創建組表的數據結構為（id，data）。其中，# 開頭的字段稱為維字段，組表將假定數據按該字段有序，也就是組表 A2 將對鍵字段 id 有序。組表默認使用列存方式。

A3：假定源數據以文本方式存儲，A3 打開數據文件。這個 txt 文件的數據表頭以及前幾行部分數據如下圖所示。當然，源數據也可以來自數據庫等其它類型的數據源。

A4：針對源數據生成游標。其中 @t 選項指明文件中第一行記錄是字段名。

A5：將游標 A4 中的記錄追加寫入組表。

上面的腳本假定主鍵 id 在原始數據中已經是有序的了，如果實際情況的主鍵并非有序，那就需要先將主鍵排序后再建為組表。這時可以使用cs.sortx()函數排序，具體方法詳見函數參考。

在集算器的設計器中，通過三行代碼，可以直觀看到其中前十條數據，代碼和截圖如下所示：

A1：打開指定文件名的組表文件對象。

A2：f.create()，函數中無參數時則直接打開組表。

A3：使用游標訪問 A2 中的前十條數據，如下圖。

2.1.2 創建索引

接下來，我們為組表文件建立索引，以提升檢索性能：

A1：打開指定文件名的組表文件對象。

A2：使用無參數的 create 函數打開組表。

A3：建立索引。在函數 T.index() 中，參數 id_idx 是索引名稱，id 是維，data 是數據列。一般情況下，建索引并不需要使用數據列，在用索引查找時會到原數據表中再去找數據。不過，本例在建立索引時將數據列也包含進了索引，這樣查找時就不再引用數據列了，雖然占用的空間會大一些，但是查找的也會更快一些。

按維字段建索引時會利用組表已經有序的特點不再排序。如果開始建組表時沒有使用 #，那么這時建索引時就會重新排序。

2.1.3查詢

使用主、子程序調用的方式來完成查詢：

查詢子程序腳本 search.dfx：

A3：keys 是參數，由下面的主程序在調用時傳遞。

A4：在組表的 icursor()這個函數中，使用索引 id_idx，以條件 A3.contain(id) 來過濾組表。集算器會自動識別出 A3.contain(id) 這個條件可以使用索引，并會自動將 A3 的內容排序后從前向后查找。

A5：將 A4 中查詢出的結果導出至 result.txt。這里 @t 選項指定導出時將輸出字段名。

主程序腳本：

A1：從keys.txt獲取查詢鍵值序列，因為只有一列結果，可以使用 @i 選項，將結果返回成序列：

這個序列就是需要進行查詢的隨機鍵值集。例子中使用 keys.txt 來預先存好隨機的鍵值，實際應用中，也可以用其他數據源來存儲。

A2：調用子程序 serach.dfx，把 A1 獲得的鍵值集作為參數傳遞給子程序。

下面就是結果文件 result.txt 中的部分內容：

另外，我們還可以將集算器嵌入到 Java 應用程序中，從而為 Java 應用提供靈活、簡便的數據查詢能力。嵌入時可以像用 JDBC 訪問數據庫那樣訪問集算器腳本。具體的寫法可以參閱教程《被 JAVA 調用》一節。

本例的單字段鍵查詢示例，在數據結構上較為簡單。其中查詢的鍵值字段為 id，需要獲取的數據為單列的 data，如果還有其它列，例如：

那么在建立索引步驟時，就應該包含多個數據列字段，數據列參數的寫法如下所示：

在接下來要討論的多字段鍵情況中，建索引時需要建立多個索引字段，對應參數部分也有類似的寫法：index(id_idx;id1,id2,…,idN;data1,data2,…,dataN)。

2.2多字段鍵

多字段健指的是聯合主鍵的情況，例如：

其中 type 和 id 兩個字段作為聯合主鍵確定一條記錄。

2.2.1 方法一（通用方法）

2.2.1.1 創建組表

本例中 A2 需要指定兩個維，type和 id，代碼其它部分與單字段鍵一致。

2.2.1.2 創建索引

由于本例中有兩個維，建立索引時需要包含 type 和 id 兩個維，如 A3 所示。

2.2.1.3 查詢

A3準備了兩條數據，是由 type 和 id 構成的二元組，作為查找的建值集，結構如下圖所示：

A4：A3.contain([type,id])，基于二元組的序列進行數據的篩選，所以需要將 contain 函數中的參數也變為二元組。

最終導出的結果文件內容如下：

2.2.2 方法二（合并主鍵）

雖然多字段鍵可以直接使用，但是涉及到集合的存儲和比較都要慢一些。為了獲取高性能，更常用的辦法是把多字段鍵拼成單字段鍵。

觀察本例數據結構，雖然 type 是個串，但卻是可枚舉的，因此可以將 type 數字化后，與 id 合并為一個新的主鍵字段。而 long 類型最大值為 2^63-1，完全可以容納 id 和 type 數字化后的合并結果。我們把 type 和 id 合并后的新主鍵叫做 nid，可以按數據的規模，確定 nid 中分別用幾位代表 type 和 id。

舉例來說，id 的范圍是 9 位數，type 的枚舉個數用 3 位數表示就夠了。因此對于 nid 而言，需要 13 位（為了避免前幾位是 0，看上去不整齊，我們把第一位數字設為 1）。這樣就可以把聯合主鍵變成單字段的唯一主鍵，去掉第一位后的 12 位數，前 3 位代表數字化后的 type，后 9 位就是原來的 id。

代碼如下：

A1：type 的枚舉值組成的序列。在實際情況中，枚舉列表可能來自文件或者數據庫數據源。。

A2：給枚舉值序列中每個 type 一個 tid。為后續的數字化主鍵合并做準備。

A3~A6：從 multi_source.txt 文件中獲取數據，并按照 A2 中的對應關系，把 type 列的枚舉串變成數字，然后將 type 和 id 進行合并后，生成新的主鍵 nid。

A7~A8：查看一下合并逐漸后的數據情況，跳過游標 A4 的前 99999995 條記錄后，取 10 條記錄，結果如下：

這樣就得到了新的“單字段建”的數據結構：

接下來按照 "單字段鍵" 中的做法就可以處理了，當然還要注意確保 nid 有序。

2.3 多線程查詢

在上述方法的基礎上，我們還可以采用多線程并行方式來進一步提高性能。

所謂多線程并行，就是把數據分成 N 份，用 N 個線程查詢。但如果只是隨意地將數據分成 N 份，很可能無法真正地提高性能。因為將要查詢的鍵值集是未知的，所以理論上也無法確保希望查找的數據能夠均勻分布在每一份組表文件中。比較好的處理方式是先觀察鍵值集的特征，從而盡可能地進行數據的均勻拆分。

比如說，繼續使用上文中多字段鍵拼成單字段鍵的例子，將合并后的主鍵 nid 對 4 取模，余數相同的數據存在同一個組表中，最終由 4 個組表文件裝載現有全部數據。這樣的文件拆分方法，可以使被查詢的數據分布的相對更加均勻一些。

如果鍵值數據有比較明顯的業務特征，我們可以考慮按照實際業務場景使用日期、部門之類的字段來處理文件拆分。如：將屬于部門 A 的 1000 條記錄均分在 10 個文件中，每個文件就有 100 條記錄。在利用多線程查詢屬于部門 A 的記錄時，每個線程就會從各自對應的文件中取數相應的這 100 條記錄了。

下面我們來看個實際的例子。

2.3.1 創建組表

A1~A6：與多字段鍵的方法二一致。

A7：使用循環函數，創建名為“鍵值名 _ 鍵值取 N 的余數 _T.ctx”的組表文件，其結構同為 (#nid,data)。

A8：用循環函數將游標數據分別追加到 N 個原組表上。比如當 N=1 時，拼出的 eval 函數參數為：channel(A4).select(nid%4==0).attach(A7(1).append(~.cursor()))。意思是對游標 A4 創建管道，將管道中記錄按鍵值 nid 取 4 的余數，將余數值等于 0 的記錄過濾出來。attach 是對當前管道的附加運算，表示取和當前余數值對應的原組表，將當前管道中篩選過濾出的記錄，以游標記錄的方式追加到 A7(1)，即第 1 個組表。

A9：循環游標 A6，每次獲取 50 萬條記錄，直至 A6 游標中的數據取完。

執行后，產出 4（這時例子取 N=4）個獨立的組表文件：

2.3.2 創建建索引

A1：列出滿足 nid*T.ctx 的文件名（這里 * 為通配符），這里 @p 選項代表需要返回帶有完整路徑信息的文件名。使用 fork 執行多線程時，需要注意環境中的并行限制數是否設置合理。這里用了 4 個線程，設計器中對應的設置如下：

B2：每個線程為各個組表建立對應的索引文件，最終結果如下：

2.3.3 查詢

A1：從 keys.txt 獲取查詢鍵值序列，因為只有一列結果，使用 @i 選項，將結果返回成序列：

A2：把 A1 的序列按 4 的余數進行等值分組：

A3、B3~B5：用 fork 函數，按等值分組后的鍵值對各個組表分別并行查詢。這里的 fork 后面分別寫了兩個參數，第一個是循環函數 N.(~-1)，第二個是 A2。在接下來的 B3、B4 中分別使用 A3(2) 和 A3(1) 來獲取 fork 后面這兩個對應順序的參數，B4：對組表文件進行根據 B3 中的鍵值集進行數據篩選，B5：返回游標。由于 A3 中是多個線程返回的游標序列，所以 A6 中需要使用 conjx 對多個游標進行縱向連接。

A6~A7：將多個線程返回的游標進行縱向連接后，導出游標記錄至文本文件，前幾行內容如下。

2.4 數據追加

前面我們已經解決了針對大數據的批量隨機鍵值查詢問題，不過，我們不能假定數據永遠不變。尤其是對于大數據來說，新數據的追加是必然要面對的。在將新數據追加到原有組表文件中時，我們需要討論三種情況：有序鍵值追加、無序鍵值追加，以及數據量很大時的數據追加。

2.4.1 有序鍵值追加

單個文件時，如果鍵值有序，追加的代碼如下：

A1：single.ctx 是已有的組表文件，結構為 (#id,data)，其中 id 為自增鍵值。

A3~A5：新數據文件與已有文件結構相同，其 id 加入原組表后，對于整體數據也是有序的。這種情況可以直接追加到原組表，組表會自動更新索引。

如果按按多線程的方法拆分為多個文件，代碼如下：

A1、A2：用游標方式獲取新增數據。

A3：滿足通配符串："id*T.ctx"，現有 N 份組表文件的序列。

A4、A5：與前面方法中的代碼一致。

2.4.2 無序鍵值追加

同樣先來看一下單個文件的追加方法，以單字段鍵為例，代碼如下：

A2：游標方式打開現有組表。

A4：游標方式獲取新增數據。

A5：建個新的組表文件。

A6：在新的組表中存放現有組表數據和新增數據歸并后的結果。這里要注意的是，用 cs.mergex(x) 進行歸并操作，需要 cs 序列對 x 有序，也就是要求組表文件 A1 和新增數據文件 A3 中的數據對于 id 都分別有序。若不滿足 cs 對 x 有序，程序雖然不會報錯，但是歸并出來的結果也是無序的。

當這段代碼執行完后，還需要進行舊組表、舊索引的清理以及對新組表的建立索引等操作：

前三行是文件操作，詳見函數參考：movefile。A4 為組表建立索引，不再詳述。

下面再看看多個文件的追加方法，以多字段鍵轉單字段鍵后的數據結構 (nid,data) 為例，代碼如下：

A3：multi_source_add.txt 是新增數據來源。

A7：假設原組表已存在，列出原組表的文件名，依次獲取組表游標，返回成序列。

A8：建立新的組表文件，用來存放舊組表數據和新增數據，在原有文件名后加上 "_temp"，以示區別。

A9：對新增數據使用管道，將管道中的 N 份游標記錄與對應的 N 個舊份組表中游標記錄進行歸并，追加到新 N 份組表中。上文已有詳細的解釋。

當這段代碼執行完后，還需要進行舊組表、舊索引的清理以及對新組表的索引建立等操作，如下：

代碼中幾乎全是循環函數與簡單的文件操作。詳見函數參考《文件》。最后一行建立索引，前文中也已多次解釋。

2.4.3 數據量很大時的數據追加

隨著新數據不斷增加，每次新追加數據與全量歷史數據歸并的時間成本將會越來越高。這時需要把每份組表文件分為新、舊兩份，新的一份是最近一段時間內積累的追加數據，舊的是之前的歷史數據。每當有新數據需要追加時，還是按 2.4.2 的處理思路操作，但只對新的那份組表文件進行處理。當新份數據文件超過一定大小閾值（如 100G），再和舊數據合并。這樣的做法不僅可以減少歸并的時間成本，另一方面也可以降低對磁盤的損耗。

列舉的數據結構還是以 (nid,data) 為例，這次我們從頭開始完整地看一遍代碼：

首先定義新、舊組表文件，命名規則如下：

新份組表：鍵值名 _ 鍵值取 N 的余數 _T.ctx；舊份組表：鍵值名 _ 鍵值取 N 的余數 _H.ctx。

1、 建立新、舊組表，本例中 N=4，代表建立 4 份組表：

N  取 4，生成的歷史和臨時組表文件如下：  

2、   在新組表上追加新數據。  

3、   新組表合并后，清理原來的新組表和索引，然后重建新組表索引。  

4、   對新數據大小進行判斷，如果超過參數 B（單位是字節數）則與舊份組表數據合并。  

5、   舊組表與新組表合并后，清理原來的舊組表和索引，然后重建舊組表索引。清理已合并的新組表，并重建空的新組表。  

6、   對新、舊組表文件分別利用多線程進行查詢  

這里需要注意 A7 中寫法，因為 B6 中返回 B4|B5，所以導致 A3 的結果為多個游標序列的序列，因此在對 A3 進行縱向連接時，應該使用序列的 conj，而不是游標的 conjx。

至此，基于本文的 6 個集算器腳本文件，在第三方定時任務調度工具的合理調用下，可以實現單機情況下大數據量數據的追加，以及針對批量隨機鍵值的查詢工作。