深入浅出话DB｜RapidsDB高性能解密 肆——并发查询

RapidsDB在底层存储、工作负载、分布式服务3个层面并发查询上优化。

RapidsDB的存储引擎使用使用无锁跳表，使得RapidsDB以非常高吞吐量进行高度并发的读写。

那么无锁跳表索引又有什么不同，它是怎么体现优势？

无锁跳表索引：又称跳表索引，它是RapidsDB中的默认索引类，对比其他大多数数据库（比如MySQL）使用的B-Tree索引。跳表索引被RapidsDB优化为在内存中运行，它不仅可以实现无锁并提供极快的插入性能。而且它提供Btree类似的O(log(n))查找性能，非常适合顺序遍历。

但跳表索引也有与B-trees不同的地方，RapidsDB中的跳表索引是单向的（也就是单链表）。混合跳表索引中的每一列都可以指定为升序（ASC）或降序（DESC），默认值为升序。选择哪一个不会影响查找性能，但会影响数据扫描性能，具体取决于索引的数据扫描的方向。反向扫描跳表索引的成本大约是正向扫描的两倍。因此，如果用户有一个升序索引，并且运行一个按降序遍历该索引的查询（例如按ORDER BY DESC的顺序），那么该查询将需要比索引DESC更高昂的迭代。

比如对于数据增删改等写入操作。传统的关系型数据库管理系统使用磁盘作为数据的主要存储，使用内存作为缓存。管理这个缓存层时会增加开销并引发资源争用，从而降低吞吐量和并发性。这些限制导致随机读写I/O，这会给旋转和固态磁盘带来了巨大的压力。RapidsDB主要将数据存储在内存中，并以压缩格式备份到磁盘。因此，RapidsDB只使用顺序I/O，并且事务日志的大小会小很多。这种I/O模式针对旋转磁盘和固态磁盘进行了优化。此外，RapidsDB中的读取可以使用内存优化的无锁跳表和哈希表，这些都不会被在缓存池中管理。

在内存中运行的跳表在这种样的设计下，可以自由地直接使用指向行的指针，而无需像传统数据库那样，检索行需要通过其他方式而不是指向内存的指针来寻址，因为传统数据库的数据主要存储位置在磁盘上。这种间接访问通常采用内存驻留页面缓存（通常称为缓冲池）的形式，查询该缓存是为了找到特定行的内存地址，或者在需要使用时先将数据从磁盘读入内存。

这种间接检索方式对系统开支很昂贵，并且通常在页面级别完成（例如，在 SQL Server中一次 8K）。而RapidsDB没有这种计算开销。取消引用指针的跳表索引比在缓冲池中查找页面要节省资源得多。

无锁（或者叫非阻塞）算法是RapidsDB索引的另外一个特点：数据库线程始终可以运行，完全适应操作系统对线程的调度执行。这也是RapidsDB支持在多核CPU硬件上运行的高并发工作负载的原因。它还摆脱了Btrees需要使用复杂的锁定方案来实现线程安全的困局。对比较新的无锁索引数据结构，例如BWtree，虽然可以避免这个问题。但同样，BWTree数据结构的复杂性远远超过了跳表甚至传统的Btree本身。因此跳表的简单性使其非常适合无锁实现。

使用无锁数据结构来优化对表的其他数据库中的B-trees有相似的功能和性能特征。跳表是为有序数据优化的数据结构，它将行存储在越来越小的有序列表集合中。查询可以通过使用不同大小的列表进行二进制搜索来快速查找数据，并且可以通过遍历最大的列表来快速扫描数据范围。对于多列索引，查询筛选器必须匹配索引列列表的前缀，以便能利用该索引。

遇到需要跨分片数据移动的查询，即涉及表数据进行广播和重新分区的查询，通常比其他查询请求更多的连接和线程。这类查询的并发性由工作负载管理自动管理。在大多数情况下，工作负载管理的默认设置将适当地安排用户的工作负载，以利用集群资源，而不会耗尽连接和线程限制。

分布式查询优化器通过平均分配处理大量工作，以最大限度地提高CPU使用效率。查询计划被编译为机器代码并且被缓存，来加速后续的查询，这些经过编译的查询计划的一个关键特征是它们并没有预先设定的参数值。这个机制允许RapidsDB能根据不同的请求来替换这些值，这使得相同查询结构的后续查询能够快速的执行，大大提高并发执行的效率，尤其是同类查询的效率。