526互联

.NET高性能开发-位图索引

发布时间 2023-10-18 13:39:10作者: 那年十八岁

原文：.NET高性能开发-位图索引 (qq.com)

首先来假设这样一个业务场景，大家对于飞机票应该不陌生，大家在购买机票时，首先是选择您期望的 起抵城市和时间，然后选择舱等(公务舱、经济舱) ，点击查询以后就会出现航班列表，随意的点击一个航班，可以发现有非常多组价格，因为机票和火车票不一样，它的权益、规则更加的复杂，比如有机票中有针对年龄段的优惠票，有针对学生的专享票，有不同的免托运行李额、餐食、有不同的退改签规则，甚至买机票还能送茅台返现等等。

 

在中国有几十个航司、几百个机场、几千条航线、几万个航班，每个航班有几十上百种产品类型，这是一天的数据，机票可以提前一年购买，总计应该有数十亿，而且它们在实时的变动，没有任何一种数据库能解决这样量级下高并发进行实时搜索的问题。

业内的解决方案都是加载数据到内存进行计算，但是内存计算也是有挑战的，如何在短短的几十毫秒内处理数十亿数据将搜索结果呈现在客户面前呢？

其中有很多可以聊的地方，今天主要聊大规模实时搜索引擎技术的一个小的优化点；通过这个简单的场景，看如何使用.NET构建内存位图索引优化搜索引擎计算速度。

声明：为简化知识和方便理解，本文场景与解决方案均为虚构，如有雷同纯属巧合。

由于篇幅问题，本系列文章一共分为四篇：

  1. 介绍什么是位图索引，如何在.NET中构建和使用位图索引

  2. 位图索引的性能，.NET BCL库源码解析，如何通过SIMD加速位图索引的计算

  3. CPU SIMD就走到尽头了吗？下一步方向是什么？

  4. 构建高效的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集合的结论，我们知道就算是空循环，面对动辄十几万、上百万的数据量时，也需要几秒钟的时间。

 

image-20231015155730785

数据库引擎在面对这个问题的时候，就通过各种各样的索引算法来解决这个问题，比如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抵达机场PEKAND结果
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循环遍历精细筛选想要的数据。

位图索引的优劣

当然位图索引有它自身的优劣势，我们要在合适的场景使用它，把它的优势发挥到最大，尽量避免它的劣势。

优势

  1. 高效的集合操作：位图索引可以使用位运算（如AND、OR和NOT等）高效地处理复杂的查询条件，这在其他类型的索引中往往难以实现。
  2. 空间效率：对于低基数的数据，位图索引通常比其他类型的索引更加空间有效。因为每一行只需要一个位，而不是一个完整的键值和指针（可以很简单的算一下，一个维度1亿数据只需要12MB的空间，就算有300个维度，那也仅仅3.5GB的空间。另外有很多位图索引压缩算法（如BBC、RLE、Roaring等），空间占用会变得更低。）。
  3. 范围查询：位图索引可以高效地处理范围查询，只需要对相关的位图进行OR运算即可（比如上文中提到的几种构建方法，BSI、REBSI等）。

劣势

  1. 更新开销：如果数据经常变动，维护位图索引的成本可能会很高。每次数据变动都可能需要更新多个位图。因此，位图索引通常用于数据仓库和其他主要用于读取的环境，而不是用于需要频繁更新的在线事务处理（OLTP）环境。
  2. 高基数数据：对于高基数的数据，即可能的值很多的数据，位图索引可能会占用大量的空间。每个可能的值都需要一个位图，因此如果数据的可能值非常多，位图索引可能不是最好的选择。
  3. 并发问题：位图索引在处理大量并发写入时可能会遇到问题，因为每次更新都需要锁定和修改位图。这在高并发的OLTP环境中可能会成为性能瓶颈（一般会使用Copy On Write解决）。

总结

在本次的分享中，我们通过一个机票搜索的业务场景，探讨了位图索引的原理与应用。位图索引作为一种高效的数据索引方式，能够在大规模数据量下优化搜索引擎的计算速度，降低内存占用并提升性能。我们详细介绍了位图索引的构建，以及如何通过逻辑运算进行搜索操作。同时，我们也实现了一个简单的位图索引，并通过实例进行了演示。最后，我们还探讨了位图索引的优劣，让我们更全面地了解了位图索引的特性和适用场景。

尽管位图索引在处理大规模数据时具有显著的优势，但在数据频繁更新、高基数数据以及并发写入的场景下可能存在问题。因此，如何在这些场景下优化位图索引，使其更好地适应不同的业务需求，将是我们未来需要进一步探讨的问题。此外，如何结合其他的索引算法，如B+树、哈希、倒排、跳表等，以及如何利用现代CPU的特性，如SIMD，以进一步提升位图索引的性能，也是我们未来的研究方向。