.NET高效能開發-點陣圖索引（一）
首先來假設這樣一個業務場景，大家對於飛機票應該不陌生，大家在購買機票時，首先是選擇您期望的起抵城市和時間，然後選擇艙等(公務艙、經濟艙)，點選查詢以後就會出現航班列表，隨意的點選一個航班，可以發現有非常多組價格，因為機票和火車票不一樣，它的權益、規則更加的複雜，比如有機票中有針對年齡段的優惠票，有針對學生的專享票，有不同的免託執行李額、餐食、有不同的退改簽規則，甚至買機票還能送茅臺返現等等。
在中國有幾十個航司、幾百個機場、幾千條航線、幾萬個航班，每個航班有幾十上百種產品型別，這是一天的資料，機票可以提前一年購買，總計應該有數十億，而且它們在實時的變動，沒有任何一種資料庫能解決這樣量級下高並行進行實時搜尋的問題。
業內的解決方案都是載入資料到記憶體進行計算，但是記憶體計算也是有挑戰的，如何在短短的幾十毫秒內處理數十億資料將搜尋結果呈現在客戶面前呢？
其中有很多可以聊的地方，今天主要聊大規模實時搜尋引擎技術的一個小的優化點；通過這個簡單的場景，看如何使用.NET構建記憶體點陣圖索引優化搜尋引擎計算速度。
宣告：為簡化知識和方便理解，本文場景與解決方案均為虛構，如有雷同純屬巧合。
由於篇幅問題，本系列文章一共分為四篇：
-
介紹什麼是點陣圖索引，如何在.NET中構建和使用點陣圖索引
-
點陣圖索引的效能，.NET BCL庫原始碼解析，如何通過SIMD加速點陣圖索引的計算
-
CPU SIMD就走到盡頭了嗎？下一步方向是什麼？
-
構建高效的Bitmap記憶體索引庫並實現可觀測性（待定，現在沒有那麼多時間整理）
什麼是點陣圖索引
要回答這樣一個問題，我們首先來假設一個案例，我們將航班規則抽象成下面的record型別，然後有如下這樣一些航班的規則資料被載入到了記憶體中：
/// <summary>
/// 艙等
/// </summary>
public enum CabinClass {
// 頭等艙
F,
// 經濟艙
Y
}
/// <summary>
/// 航班規則
/// </summary>
/// <param name="Airline">航司</param>
/// <param name="Class">艙等</param>
/// <param name="Origin">起飛機場</param>
/// <param name="Destination">抵達機場</param>
/// <param name="DepartureTime">起飛時間</param>
public record FlightRule(string Airline, CabinClass Class, string Origin, string Destination, string FlightNo, DateTime DepartureTime);
var flightRules = new FlightRule[]
{
new ("A6", CabinClass.F, "PEK", "SHA", "A61234", DateTime.Parse("2023-10-11 08:00:00")),
new ("CA", CabinClass.Y, "SHA", "PEK", "CA1234", DateTime.Parse("2023-10-13 08:00:00")),
new ("CA", CabinClass.Y, "SHA", "PEK", "CA1234", DateTime.Parse("2023-10-14 08:00:00")),
new ("CA", CabinClass.Y, "SHA", "PEK", "CA1234", DateTime.Parse("2023-10-15 08:00:00")),
new ("CA", CabinClass.F, "SHA", "PEK", "CA1234", DateTime.Parse("2023-10-15 08:00:00")),
new ("MU", CabinClass.F, "PEK", "CSX", "MU1234", DateTime.Parse("2023-10-16 08:00:00")),
new ("9C", CabinClass.Y, "PEK", "CSX", "9C1234", DateTime.Parse("2023-10-17 08:00:00")),
};
然後有一個搜尋表單record型別，如果說要針對這個record編寫一個搜尋方法，用於過濾得出搜尋結果，相信大家很快就能實現一個程式碼，比如下方就是使用簡單的for迴圈來實現這一切。
// 搜尋方法 condition為搜尋條件
FlightRule[] SearchRule(FlightRuleSearchCondition condition)
{
var matchRules = new List<FlightRule>();
foreach (var rule in flightRules)
{
if (rule.Airline == condition.Airline &&
rule.Class == condition.Class &&
rule.Origin == condition.Origin &&
rule.Destination == condition.Destination &&
rule.DepartureTime.Date == condition.DepartureTime.Date)
{
matchRules.Add(rule);
}
}
return matchRules.ToArray();
}
這個解決方案的話再資料量小的時候非常完美，不過它的時間複雜度是O(N)，大家可以回憶之前文章如何快速遍歷List集合的結論，我們知道就算是空迴圈，面對動輒十幾萬、上百萬的資料量時，也需要幾秒鐘的時間。
資料庫引擎在面對這個問題的時候，就通過各種各樣的索引演演算法來解決這個問題，比如B+樹、雜湊、倒排、跳錶等等，當然還有我們今天要提到的點陣圖索引。
我們先來看一下點陣圖索引的定義：點陣圖索引是一種資料庫索引方式，針對每個可能的列值，建立一個位向量。每個位代表一行，如果該行的列值等於位向量的值，位為1，否則為0。特別適用於處理具有少量可能值的列。聽起來比較抽象是嘛？沒有關係，我們通過後面的例子大家就能知道它是一個什麼了。
構建點陣圖索引
還是上面提到的航班規則資料，比如第一個Bit陣列就是航司為CA的行，那麼第0位就代表航班規則陣列中的第0個元素，它的航司是CA，所以這個Bit位就為True，賦值為1；同樣的，第1位就代表航班規則資料中的第1個元素，它航司不是CA，所以就賦值為0。
new ("A6", CabinClass.F, "PEK", "SHA", "A61234", DateTime.Parse("2023-10-11 08:00:00")),
new ("CA", CabinClass.Y, "SHA", "PEK", "CA1234", DateTime.Parse("2023-10-13 08:00:00")),
new ("CA", CabinClass.Y, "SHA", "PEK", "CA1234", DateTime.Parse("2023-10-14 08:00:00")),
new ("CA", CabinClass.Y, "SHA", "PEK", "CA1234", DateTime.Parse("2023-10-15 08:00:00")),
new ("CA", CabinClass.F, "SHA", "PEK", "CA1234", DateTime.Parse("2023-10-15 08:00:00")),
new ("MU", CabinClass.F, "PEK", "CSX", "MU1234", DateTime.Parse("2023-10-16 08:00:00")),
new ("9C", CabinClass.Y, "PEK", "CSX", "9C1234", DateTime.Parse("2023-10-17 08:00:00")),
| 特徵 | 規則0 | 規則1 | 規則2 | 規則3 | 規則4 | 規則5 | 規則6 |
|---|---|---|---|---|---|---|---|
| 航司CA | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
根據這個規則，我們可以根據它的不同維度，構建出好幾個不同維度如下幾個Bit陣列，這些陣列組合到一起，就是一個Bitmap。
| 規則序號 | 航司CA | 航司A6 | 航司MU | 航司9C | 經濟艙 | 起飛機場PEK | 起飛機場SHA | 起飛機場CSX | 抵達機場PEK | 抵達機場SHA | 抵達機場CSX |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 2 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 3 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 4 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
| 5 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 6 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
現代CPU的字長都是64bit，它能在一次迴圈中處理64bit的資料，按照一個不嚴謹的演演算法，它比直接for搜尋要快64倍（當然這並不是極限，在後面的文章中會解釋原因）。
點陣圖索引邏輯運算
點陣圖索引已經構建出來了，那麼如何進行搜尋操作呢？
與運算
比如我們需要查詢航司為CA，起飛機機場為SHA到PEK的航班，就可以通過AND運運算元，分別對它們進行AND操作。
就能得出如下的Bit陣列，而這個Bit陣列中為1的位對應的位下標就是符合條件的規則，可以看到下標1~4都是符合條件的規則。
| 規則序號 | 航司CA | 起飛機場SHA | 抵達機場PEK | AND結果 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 1 | 1 |
| 3 | 1 | 1 | 1 | 1 |
| 4 | 1 | 1 | 1 | 1 |
| 5 | 0 | 0 | 0 | 0 |
| 6 | 0 | 0 | 0 | 0 |
或運算
如果想搜尋10月13號和10月15號起飛的航班，那應該怎麼做呢？其實也很簡單，就是通過OR運運算元，先得出在10月13號和10月15號的規則（請注意，在實際專案中對於時間這種高基數的資料不會對每一天建立索引，而是會使用BSI、REBSI等方式建立；或者使用B+ Tree這種更高效的索引演演算法）：
| 規則序號 | 起飛日期10月13日 | 起飛日期10月15日 | OR結果 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 |
| 2 | 0 | 0 | 0 |
| 3 | 0 | 1 | 1 |
| 4 | 0 | 1 | 1 |
| 5 | 0 | 0 | 0 |
| 6 | 0 | 0 | 0 |
然後再AND上文中的出的結果陣列即可，可以看到只有規則1、3和4符合要求了。
| 規則序號 | 上次運算結果 | OR結果 | 本次結果 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
| 2 | 1 | 0 | 0 |
| 3 | 1 | 1 | 1 |
| 4 | 1 | 1 | 1 |
| 5 | 0 | 0 | 0 |
| 6 | 0 | 0 | 0 |
非運算
那麼使用者不想坐經濟艙應該怎麼辦？我們這裡沒有構建非經濟艙的Bit陣列；解決其實很簡單，我們對經濟艙進行NOT操作：
| 規則序號 | 經濟艙 | NOT結果 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
| 2 | 1 | 0 |
| 3 | 1 | 0 |
| 4 | 0 | 1 |
| 5 | 0 | 1 |
| 6 | 1 | 0 |
然後AND上文中的結果即可，就可以得出符合上面條件，但不是經濟艙的航班列表，可以發現僅剩下規則4可以滿足需求：
| 規則序號 | 上次運算結果 | NOT結果 | 本次結果 |
|---|---|---|---|
| 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 2 | 0 | 0 | 0 |
| 3 | 1 | 0 | 0 |
| 4 | 1 | 1 | 1 |
| 5 | 0 | 1 | 0 |
| 6 | 0 | 0 | 0 |
程式碼實現
請注意，本文中程式碼為AI生成，僅供演示和參考，不可用於實際生產環境，請使用其它更成熟實現（如：BitArray）。
那麼如何實現一個Bitmap索引呢？其實非常的簡單，在.NET中已經自帶了BitArray類，將多個BitArray使用Dictionary組合在一起就可以實現Bitmap索引。
在這裡為了詳細的講述原理，我們不使用官方提供的BitArray，自己實現一個簡單的，其實就是一個存放的陣列和簡單的位運算。
public class MyBitArray
{
private long[] _data;
// 每個long型別有64位元
private const int BitsPerLong = 64;
public int Length { get; }
public MyBitArray(int length)
{
Length = length;
// 計算儲存所有位需要多少個long
_data = new long[(length + BitsPerLong - 1) / BitsPerLong];
}
public bool this[int index]
{
// 獲取指定位的值
get => (_data[index / BitsPerLong] & (1L << (index % BitsPerLong))) != 0;
set
{
// 設定指定位的值
if (value)
_data[index / BitsPerLong] |= (1L << (index % BitsPerLong));
else
_data[index / BitsPerLong] &= ~(1L << (index % BitsPerLong));
}
}
public void And(MyBitArray other, MyBitArray result)
{
// 對兩個MyBitArray進行AND操作
for (int i = 0; i < _data.Length; i++)
result._data[i] = _data[i] & other._data[i];
}
public void Or(MyBitArray other, MyBitArray result)
{
// 對兩個MyBitArray進行OR操作
for (int i = 0; i < _data.Length; i++)
result._data[i] = _data[i] | other._data[i];
}
public void Xor(MyBitArray other, MyBitArray result)
{
// 對兩個MyBitArray進行XOR操作
for (int i = 0; i < _data.Length; i++)
result._data[i] = _data[i] ^ other._data[i];
}
public void Not(MyBitArray result)
{
// 對MyBitArray進行NOT操作
for (int i = 0; i < _data.Length; i++)
result._data[i] = ~_data[i];
}
}
然後我們可以使用Dictionary<string, MyBitArray>來實現一個多維度的BitMap：
//定義一個名為MyBitmap的類
public class MyBitmap
{
//定義一個字典來儲存字串和MyBitArray的對映
private readonly Dictionary<string, MyBitArray> _bitmaps;
//定義一個整數來儲存點陣圖的長度
private readonly int _length;
//建構函式，接收一個整數作為引數，並初始化字典和長度
public MyBitmap(int length)
{
_bitmaps = new Dictionary<string, MyBitArray>();
_length = length;
}
//定義一個索引器，通過字串key來獲取或設定MyBitArray
public MyBitArray this[string key]
{
get
{
//如果字典中存在key，則返回對應的MyBitArray
//如果不存在，則建立一個新的MyBitArray，新增到字典中，並返回
if (_bitmaps.TryGetValue(key, out MyBitArray? value)) return value;
value = new MyBitArray(_length);
_bitmaps[key] = value;
return value;
}
set
{
//設定字典中key對應的MyBitArray
_bitmaps[key] = value;
}
}
//定義一個And方法，接收一個字串key，一個MyBitArray和一個結果MyBitArray作為引數
//將key對應的MyBitArray和傳入的MyBitArray進行And操作，結果存入結果MyBitArray
public void And(string key, MyBitArray bitArray, MyBitArray result)
{
this[key].And(bitArray, result);
}
//定義一個Or方法，接收一個字串key，一個MyBitArray和一個結果MyBitArray作為引數
//將key對應的MyBitArray和傳入的MyBitArray進行Or操作，結果存入結果MyBitArray
public void Or(string key, MyBitArray bitArray, MyBitArray result)
{
this[key].Or(bitArray, result);
}
//定義一個Xor方法，接收一個字串key，一個MyBitArray和一個結果MyBitArray作為引數
//將key對應的MyBitArray和傳入的MyBitArray進行Xor操作，結果存入結果MyBitArray
public void Xor(string key, MyBitArray bitArray, MyBitArray result)
{
this[key].Xor(bitArray, result);
}
//定義一個Not方法，接收一個字串key和一個結果MyBitArray作為引數
//將key對應的MyBitArray進行Not操作，結果存入結果MyBitArray
public void Not(string key, MyBitArray result)
{
this[key].Not(result);
}
}
然後寫一個Build方法，用於將FlightRule[]建立成MyBitmap，這一過程可以採用程式碼生成自動去做，無需手動編寫，我們這裡演示一下：
MyBitmap Build(FlightRule[] rules)
{
var bitmap = new MyBitmap(rules.Length);
for (int i = 0; i < rules.Length; i++)
{
// 將bitmap索引維度構建
// 在實際專案中不用這麼寫，可以使用程式碼生成技術自動構建，這裡只是舉例
bitmap["Airline-A6"][i] = rules[i].Airline == "A6";
bitmap["Airline-CA"][i] = rules[i].Airline == "CA";
bitmap["Airline-MU"][i] = rules[i].Airline == "MU";
bitmap["Airline-9C"][i] = rules[i].Airline == "9C";
bitmap["CabinClass-F"][i] = rules[i].Class == CabinClass.F;
bitmap["CabinClass-Y"][i] = rules[i].Class == CabinClass.Y;
bitmap["Origin-PEK"][i] = rules[i].Origin == "PEK";
bitmap["Origin-SHA"][i] = rules[i].Origin == "SHA";
bitmap["Destination-CSX"][i] = rules[i].Destination == "CSX";
bitmap["Destination-PEK"][i] = rules[i].Destination == "PEK";
// ....... 其它維度
}
return bitmap;
}
呼叫Build方法，簡單的進行一下運算查詢（航司為CA、頭等艙），程式碼和執行結果如下所示：
var flightRuleBitmap = Build(flightRules);
// 搜尋CA 頭等艙航班
var result = new MyBitArray(flightRules.Length);
flightRuleBitmap.And("Airline-CA", flightRuleBitmap["CabinClass-F"], result);
// 輸出result中為true的索引
for (int i = 0; i < result.Length; i++)
{
if (result[i])
Console.WriteLine(i);
}
在實際專案中，大多數位段都可以建立Bitmap索引，對於那些不能建立的也沒有關係，可以在Bitmap索引初篩以後，再使用for迴圈遍歷精細篩選想要的資料。
點陣圖索引的優劣
當然點陣圖索引有它自身的優劣勢，我們要在合適的場景使用它，把它的優勢發揮到最大，儘量避免它的劣勢。
優勢
- 高效的集合操作：點陣圖索引可以使用位運算（如AND、OR和NOT等）高效地處理複雜的查詢條件，這在其他型別的索引中往往難以實現。
- 空間效率：對於低基數的資料，點陣圖索引通常比其他型別的索引更加空間有效。因為每一行只需要一個位，而不是一個完整的鍵值和指標（可以很簡單的算一下，一個維度1億資料只需要12MB的空間，就算有300個維度，那也僅僅3.5GB的空間。另外有很多點陣圖索引壓縮演演算法（如BBC、RLE、Roaring等），空間佔用會變得更低。）。
- 範圍查詢：點陣圖索引可以高效地處理範圍查詢，只需要對相關的點陣圖進行OR運算即可（比如上文中提到的幾種構建方法，BSI、REBSI等）。
劣勢
- 更新開銷：如果資料經常變動，維護點陣圖索引的成本可能會很高。每次資料變動都可能需要更新多個點陣圖。因此，點陣圖索引通常用於資料倉儲和其他主要用於讀取的環境，而不是用於需要頻繁更新的線上事務處理（OLTP）環境。
- 高基數資料：對於高基數的資料，即可能的值很多的資料，點陣圖索引可能會佔用大量的空間。每個可能的值都需要一個點陣圖，因此如果資料的可能值非常多，點陣圖索引可能不是最好的選擇。
- 並行問題：點陣圖索引在處理大量並行寫入時可能會遇到問題，因為每次更新都需要鎖定和修改點陣圖。這在高並行的OLTP環境中可能會成為效能瓶頸（一般會使用Copy On Write解決）。
總結
在本次的分享中，我們通過一個機票搜尋的業務場景，探討了點陣圖索引的原理與應用。點陣圖索引作為一種高效的資料索引方式，能夠在大規模資料量下優化搜尋引擎的計算速度，降低記憶體佔用並提升效能。我們詳細介紹了點陣圖索引的構建，以及如何通過邏輯運算進行搜尋操作。同時，我們也實現了一個簡單的點陣圖索引，並通過範例進行了演示。最後，我們還探討了點陣圖索引的優劣，讓我們更全面地瞭解了點陣圖索引的特性和適用場景。
儘管點陣圖索引在處理大規模資料時具有顯著的優勢，但在資料頻繁更新、高基數資料以及並行寫入的場景下可能存在問題。因此，如何在這些場景下優化點陣圖索引，使其更好地適應不同的業務需求，將是我們未來需要進一步探討的問題。此外，如何結合其他的索引演演算法，如B+樹、雜湊、倒排、跳錶等，以及如何利用現代CPU的特性，如SIMD，以進一步提升點陣圖索引的效能，也是我們未來的研究方向。
下一期預告
在下一期中，我們將深入探討點陣圖索引的效能問題，包括.NET BCL庫原始碼的解析，以及如何通過SIMD加速點陣圖索引的計算。希望大家能夠繼續關注後面的分享，一起探討.NET高效能開發的相關知識。