百万并发场景中倒排索引与位图计算的实践

京东云开发者
• 阅读 78
作者:京东物流 郎元辉

背景

Promise时效控单系统作为时效域的控制系统,在用户下单前、下单后等多个节点均提供服务,是用户下单黄金链路上的重要节点;控单系统主要逻辑是针对用户请求从规则库中找出符合条件的最优规则,并将该规则的时效控制结果返回客户端,比如因为临时疫情等原因针对仓、配、商家、客户四级地址等不同维度进行精细粒度的时效控制。

该系统也是Promise侧并发量最大的系统,双11高峰集群流量TPS在百万级别,对系统的性能要求非常高,SLA要求在5ms以内,因此对海量请求在规则库(几十万)中如何快速正确匹配规则是该系统的技术挑战点

朴素的解决方案

按照朴素的思想,在工程建设上,通过异步方式将规则库逐行缓存到Redis,Key为规则条件,Value为规则对应结果;当用户请求过来时,对请求Request(a,b,c,d..)中的参数做全组合,根据全组合出的Key尝试找出所有可能命中的规则,再从中筛选出最优的规则。如下图所示

百万并发场景中倒排索引与位图计算的实践 

该方案面临的问题是全组合的时间复杂度是2n,n≈12;算法的时间复杂度高且算法稳定性差**,最差情况一次请求需要4096次计算和读取操作。当然在工程上我们可以使用本地缓存做一些优化,但是无法解决最根本的性能问题。架构简图如下所示:

百万并发场景中倒排索引与位图计算的实践 

新的解决方案

上面方案是从行的角度看待匹配定位的,能够命中的行的每一列必然也是符合条件的,这里面存在某种隐约的内在联系。能否反过来思考这个问题,为此我们尝试进行新的方案,当然架构简图依然如上图所示,核心优化的是命中算法。

新的方案整体采用列的倒排索引和倒排索引位运算的方式,使得计算复杂度由原来的2n降至n**,且算法稳定性有非常好的保证。其中列的倒排索引是对每列的值和所分布的行ID(即Posting List)建立KV关系,倒排索引位运算是对符合条件的列倒排索引进行列间的位运算,即通过联合查询以便快速找到符合条件的规则行。

算法详细设计

1.预计算生成列的倒排索引和位图

通过对每列的值进行分组合并生成Posting List,建立列值和Posting List的KV关系。以下图为例,列A可生成的倒排索引为:301={1},201={2,3,4,5}等,需要说明的一点,空值也是一种候选项,也需要生成KV关系,如nil={7}。


百万并发场景中倒排索引与位图计算的实践

2.生成列的倒排索引对应位图

将步骤1的倒排索引转成成位图,方便后续的位图计算,转换规则为行ID对应位图的下标位(步骤1、2可以合并操作)。



百万并发场景中倒排索引与位图计算的实践 

3.根据用户请求查找列位图,通过位图计算生成候选规则集

将用户请求中的入参作为Key,查找符合条件的位图,对每一列进行列内和空值做||运算,最后列间位图做&运算,得到的结果是候选规则集,如下图所示:

百万并发场景中倒排索引与位图计算的实践



4.从候选规则库中,根据业务优先级排序,查找最优的规则

以候选规则为基点,按照业务优先级排序,进行逐级位运算&,当遍历完或位运算为0时,找到最后不为空的即为最优规则,该过程是从候选规则库逐渐缩小最优范围的过程。需要说明某列当用户请求位图不存在时,需要使用对应的空位图进行参与,以B列为例,入参B_1102不存在,需要使用B_nil参与&。

百万并发场景中倒排索引与位图计算的实践 

复杂度分析

通过上面的例子我们可以看到,在时间复杂度方面查找候选规则集时,进行一轮||运算,一轮&运算;在查找最优规则时进行一轮&运算,所以整体复杂度是3n≈n

在空间复杂度方面,相比原来的行式存储,倒排索引的存储方式,每列都需要存储行ID,相当于多了 (n-1)*Posting List存储空间,当然这是粗略计算,因为实际上行ID的存储最终转换为位图存储,在空间上有非常大的压缩空间。

工程问题-压缩位图

如果倒排索引位图非常稀疏,系统会存在非常大的空间浪费。我们举一个极端case,若千万规则库中命中的行ID是第1000万位,按照传统方式BitSet进行存储,需要消耗1.2MB空间,在内存中占用存在严重浪费,有没有压缩优化方案,在RoaringBitMap压缩位图方案中我们找到,相同场景在压缩位图方式下仅占144bytes;即使在1000万的位图空间,我们随机存储1万个值,两者比也是在31K vs 2MB,近100倍的差距,总的来说RoaringBitMap压缩率非常大。

RoaringBitMap本质上是将大块的bitmap拆分成各个小块,其中每个小块在需要存储数据的时候才会存在,所以当进行交集或并集运算的时候,RoaringBitMap只需要去计算存在的块而不需要像bitmap那样对整个大块进行计算,既做到了压缩的存储又做到计算性能的提升。

以下图821697800为例,对应的16进制数为30FA1D08, 其中高16 位为30FA,低16位为1D08。先用二分查找从一级索引(即Container Array)中找到数值为 30FA 的容器,该容器是一个Bitmap容器,然后在该容器查找低16位的数值1D08,即十进制下7432,在Bitmap中找到相应的位置,将其置为1即可。

 百万并发场景中倒排索引与位图计算的实践 



适用场景分析

回顾上面的设计方案我们可以看到,这种方式仅适用于PostingList简单如行ID的形式,如果是复杂对象就不适合用位图来存储。另外仅适用于等值查询,不适用于like、in的范围查询,为什么有这种局限性?因为这种方式依赖于搜索条件的空间,在方案中我们将值的条件作为搜索的Key,值的条件空间希望尽可能是一个有限的、方便穷举的、小的空间。而范围查询导致这个空间变成难以穷举、近乎无限扩张的、所以不适用。

其他优化方式

除了使用位运算的方式对倒排索引加速,考虑到Posting List的有序性,还有其他的方式比如使用跳表、Hash表等方式,以ES中采用的跳表为例,进行&运算实际就是在查找两个有序Posting List公共部分,以相互二分查找的形式,将时间复杂度控制在log(n)的级别。

具体参见工业界如何利用跳表、哈希表、位图进行倒排索引加速?

百万并发场景中倒排索引与位图计算的实践

点赞
收藏
评论区
推荐文章
Wesley13 Wesley13
1年前
PID控制器开发笔记之十三:单神经元PID控制器的实现
神经网络是模拟人脑思维方式的数学模型。神经网络是智能控制的一个重要分支,人们针对控制过程提供了各种实现方式,在本节我们主要讨论一下采用单神经元实现PID控制器的方式。1、单神经元的基本原理  单神经元作为构成神经网络的基本单位,具有自学习和自适应能力,且结构简单而易于计算。接下来我们讨论一下单神经元模型的基本原理。(1)、单神经元模
Stella981 Stella981
1年前
RuleEngine
规则引擎是嵌入在应用程序中的组件,实现了决策逻辑和业务系统的分离功能。在现实业务场景中,决策逻辑的复杂性和可变性,使得决策引擎的应用越来越多,把决策逻辑单独分离出来也显得越来越重要了。目前市场上常用的规则引擎有IlogJRules,Drools,Jess,VisualRules等。IlogJRules是最有名的商用BRMS;Drools是最活跃
Easter79 Easter79
1年前
SpringCloud微服务(05):Zuul组件,实现路由网关控制
一、Zuul组件简介1、基础概念Zuul网关主要提供动态路由,监控,弹性,安全管控等功能。在分布式的微服务系统中,系统被拆为了多个微服务模块,通过zuul网关对用户的请求进行路由,转发到具体的后微服务模块中。2、Zuul的作用1)按照不同策略,将请求转发到不同的服务上去;
Easter79 Easter79
1年前
thinkcmf+jsapi 实现微信支付
首先从小程序端接收订单号、金额等参数,然后后台进行统一下单,把微信支付的订单号返回,在把订单号发送给前台,前台拉起支付,返回参数后更改支付状态。。。回调publicfunctionnotify(){$wechatDb::name('wechat')where('status',1)find();
Wesley13 Wesley13
1年前
java中饿汉与懒汉的故事(单例设计模式)
java中的单例设计模式关于设计模式,这其实是单独存在的东西,它不属于java,但是在java中使用较多,所以今天我就给大家介绍下单例设计模式中的饿汉和懒汉这俩朴素的打工人。首先我先说明下单例设计模式是啥(如果不想了解,可以直接划下去看饿汉和懒汉):类的单例设计模式就是采用一定的方法保证在整个软件系统中,对某个类只能存在一
Stella981 Stella981
1年前
Spring Cloud系列教程(十九)
一、前言在Ribbon组件中,一共提供了7种负载均衡策略规则,默认使用轮训规则RoundRobinRule:最低并发策略BestAvailableRule:选择最小请求数可用过滤策略(AvailabilityFilteringRule):过滤掉连接失败的服务节点,并且过滤掉高并发的服务
Wesley13 Wesley13
1年前
Oracle学习笔记(一)——并发与锁
1并发多用户数据库管理系统的一个主要任务是对并发(concurrency)进行控制,即对多个用户同时访问同一数据进行控制。当缺乏有效的并发控制时,修改数据的操作就不能保证正常,从而危害数据完整性。管理数据并发的方法是让每个用户轮流操作数据。而数据库管理系统的目标就是减少每个用户的等待时间,即让用户无需等待或使等待难以察觉。为保证数据库性能
Stella981 Stella981
1年前
ELK学习笔记之ElasticSearch的索引详解
0x00ElasticSearch的索引和MySQL的索引方式对比Elasticsearch是通过Lucene的倒排索引技术实现比关系型数据库更快的过滤。特别是它对多条件的过滤支持非常好,比如年龄在18和30之间,性别为女性这样的组合查询。倒排索引很多地方都有介绍,但是其比关系型
Wesley13 Wesley13
1年前
MySQL 分区表原理及使用详解
1\.什么是表分区?表分区,是指根据一定规则,将数据库中的一张表分解成多个更小的,容易管理的部分。从逻辑上看,只有一张表,但是底层却是由多个物理分区组成。2\.表分区与分表的区别分表:指的是通过一定规则,将一张表分解成多张不同的表。比如将用户订单记录根据时间成多个表。分表与分区的区别在于:
胖大海 胖大海
5个月前
Linux centos7 firewalld详细用法
iptables与firewalld的区别1.firewalld可以动态修改单条规则,动态管理规则集,允许更新规则而不破坏现有会话和连接。而iptables,在修改了规则后必须得全部刷新才可以生效;2.firewalld使用区域和服务而不是链式规则;3.firewalld默认是拒绝的,需要设置以后才能放行。而iptables默认是允许的,需要拒绝的才去限制;