/Q-calculator

高性能优惠叠加计算框架

Primary LanguageJavaApache License 2.0Apache-2.0

License

Stateless高性能优惠叠加计算框架

RT:

背景:

优惠是营销转化链路的重要抓手,对刺激用户消费起到至关重要的作用,目前市场上的优惠主要包含活动(如拼多多的砍一刀、天猫农场、新用户首购、复购、积分等)和券(如折扣券、代金券、商品券、买A赠B等),复杂的优惠规则让用户很难自行计算优惠叠加的顺序,或许用户在复杂的优惠规则中降低购买商品的欲望,对于参加了多个活动、有多个优惠券情况尤为明显。

优惠的计算顺序可以分为平行式和渐进式,其中平行式优惠之间没有依赖关系,而渐进式优惠之间则存在依赖关系,即下一个优惠取决于上一步的优惠结果,假设小明消费了100元,有一个8折优惠券和一个满100-20的优惠券,则这2个优惠的使用顺序有以下两种情况:

Q-calculator采用很多新颖的算法实现了高性能求解优惠最优排列。

核心计算类 Permutation<T extends GoodsItem>

Permutation是一个抽象类,是Q-calculator的核心,在Permutation中使用了很多优化策略来保证性能,这些策略包括:

  • 预存的排列数结果集

这么设计的原因是在业务场景中需要频繁的计算排列,对于某个长度的序列,其排列结果是固定的。在Permutation类中的PERMUTATIONS属性存放了7以内的排列数结果集,这里使用了Byte来存储,因此占用的内存空间非常小。

private final static Map<Integer,Collection<List<Byte>>> PERMUTATIONS = Maps.newHashMap();

这个动作在类加载即完成,如果对7不满意,可以调整SUPPORTEDSIZE的大小,7是我们在实现中摸出来的兼顾业务和性能的参数,大家可以根据自己的需要来调整。

public final static int SUPPORTEDSIZE = 7;

static{
      //前置计算 1-SUPPORTEDSIZE 之间所有排列组合
    for(byte i=1;i<=SUPPORTEDSIZE;i++){
       PERMUTATIONS.put((int)i,Collections2.permutations(IntStream.range(0,i).boxed().map(x->(byte)x.intValue()).collect(Collectors.toList())));
      }
  }
  • $A_n^3$ 级别缓存

相对于传统的Key-Value结构,求解 $A_n^n$ 问题的缓存需要特殊设计,对一个优惠集合而言 $A_n^3$ 意味着缓存 n x (n-1) x (n-2) 条数据,默认n为7则需要缓存210条数据,兼顾内存大小和缓存带来的性能收益, $A_n^3$ 是最为合适的。

Permutation的成员变量cache来实现高性能缓存。

private final Map<Integer, CalcState<T>> cache = Maps.newHashMap();

可能你已经注意到,cache的键是Integer类型的,的确,通常String会更常用,然而在万次计算的场景下,String的拼接已经成了瓶颈。 为了实现高性能的键,Permutation通过位移对Byte数组的前3位进行扰动,确保键的唯一性和性能。

private static Integer calcKey(List<Byte> a){
       return  a.size()>=3?(a.get(0) << 6)+ (a.get(1) << 3) + a.get(2):0;
}

Permutation提供了保存点来实现 $A_n^3$ 级别缓存,CalcState 记录了计算到第3步的状态,包括当前订单优惠金额和计算过程、已享用优惠的商品等,这些属性的保存和回放Permutation已经帮你做好了,Permutation额外提供了抽象的保存和回放方法来满足你的个性化诉求。

   /**
     * 业务将状态记录到保存点
     * @param state 保存点对象
     */
    protected abstract void makeSnapshot(CalcState<T> state,DiscountContext<T> context);

    /**
     * 业务返回保存点状态
     * @param state 保存点对象
     */
    protected abstract void backToSnapshot(CalcState<T> state,DiscountContext<T> context);

优惠计算是有优先级的,必须保证属性calculateGroup值小的在前面运算,当backToSnapshot发生时,需要额外判断缓存中最后一个优惠和当前准备计算优惠之间的关系,若不满足则直接跳出。checkIfWakeUpJump方法将在缓存被使用后立刻判断是否需要继续下去。

上下文类 DiscountContext<T extends GoodsItem>

DiscountContext是上下文,也是Permutation的成员变量,DiscountContext同样包含很多优化策略:

  • CalcStage数组

在变更最频繁也是最重要的计算步骤对象CalcStage使用数组存储,该数组随着上下文创建而创建,在Permutation中使用

Arrays.fill(arr,null);

将该数组清空并让它投入下一次计算,这样一次全排列过程中,数组只会被创建一次,避免了频繁创建数组带来的性能损耗。

  • 预计算

DiscountContext的初始化方法是静态的create方法,该方法将商品和优惠进行绑定,同时执行一些用户自定义的逻辑,我们称之为预计算,预计算的结果会被保存在DiscountContextpreCompute属性,可以在后续的计算中直接取用,一劳永逸,避免了在后续的高速迭代中做相同的事情,比如商品分组、求和等等。

预计算 PreCompute<T extends GoodsItem>

预计算提供了接口,要使用预计算首先需要实现PreCompute接口

public interface PreCompute<T extends GoodsItem> {
    /**
     * 判断符合条件的活动类型,符合才会执行preComputeItems
     */
    Set<String> matchTypes();

    /**
     * 对商品做一些复杂集合操作
     * @param items 当前参与优惠的商品
     * @param discount 当前优惠
     * @param preCompute 存储计算的结果
     */
     void preComputeItems(List<T> items, DiscountWrapper discount, Map<String,Object> preCompute);
}

此外需要在资源目录下建立calculator-core.properties文件,配置内容如下

precompute.path=你要扫描的包

PreComputeHolder将处理所有的PreCompute实现类,只有matchTypes匹配的情况下preComputeItems方法才会被执行。

public class PreComputeHolder {
    public static Set<PreCompute> COMPUTES= Sets.newHashSet();
    private final static String PATH = "precompute.path";

    static{
        Properties properties = new Properties();
        try {
              properties = PropertiesLoaderUtils.loadProperties(new FileSystemResource(Objects.requireNonNull(PreComputeHolder.class.getClassLoader().getResource("calculator-core.properties")).getPath()));
        } catch (Exception ignore) {
        }
        String path = properties.getProperty(PATH);
        if(StringUtils.isNotBlank(path)){
            Reflections reflections = new Reflections(path);
            Set<Class<? extends PreCompute>> subTypes = reflections.getSubTypesOf(PreCompute.class);
            for(Class<? extends PreCompute> clazz:subTypes){
                try {
                    COMPUTES.add(clazz.newInstance());
                } catch (Exception ignore) {
                }
            }
        }
    }
}

计算器 Calculator

Calculator是单个优惠的计算接口,它有calcWrap一个方法,负责具体的优惠计算,但calcWarp需要承担一些内部的事情,因此我们提供了抽象类AbstractCalculator实现了calcWrap,并最终暴露了一个更简单的calc方法给使用者。

AbstractCalculator的内容如下,calcWrap方法负责创建CalcStage,维护CalcStage数组等内部工作,这对使用者来说是透明的,使用者实现calc就好。

public abstract class AbstractCalculator<T extends GoodsItem> implements Calculator<T> {
    public long calcWrap(DiscountContext<T> context, DiscountWrapper discountWrapper, Map<Long, T> records, byte idx, int i) {
        CalcStage stage = new CalcStage();
        CalcResult cr = context.getCalcResult();
        long price= cr.getCurPrice();
        stage.setBeforeCalcPrice(price);
        price = calc(context, discountWrapper,records, price, stage);
        if(price<0){
            return price;
        }
        stage.setAfterCalcPrice(price);
        stage.setIndex(idx);
        stage.setStageType(discountWrapper.getType());
        cr.setCurPrice(price);
        if(stage.getBeforeCalcPrice()>stage.getAfterCalcPrice()) {
            cr.getCurStages()[i] = stage;
        }
        return price;
    }

    /**
     * 返回该优惠下的最终要支付的金额,若不符合则返回 prevStagePrice
     * @param context 上下文
     * @param discountWrapper 优惠信息
     * @param records 记录享受过优惠的单品,key是calculateId,这里只提供容器,添加和判断规则由使用者自行决定
     * @param prevStagePrice 上一步计算的订单的价格
     * @param curStage 当前stage
     * @return
     */
    public abstract  long calc(DiscountContext<T> context, DiscountWrapper discountWrapper, Map<Long,T> records, long prevStagePrice, CalcStage curStage);

}

最终用户继承AbstractCalculator,需要在Component注解中指定一个值,而CalculatorRouter将通过这个值来路由到具体的优惠计算器。这个值和DiscountWrapper中的type属性是对应的。

@Component("manjian")
public class ManjianCalc extends AbstractCalculator<GoodsItem> {
......
}

共享互斥协议 DiscountGroup

共享互斥协议是一个数组,数组中最多有2个对象,最少1个对象,若只有1个对象,则该对象必然为共享组,即组内优惠可以叠加使用

[
    {
        "relation": "share",
        "items":
        [
            {
                "type": "activity0",
                "id": "11"
            }
            ,
            {
                "type": "activity4",
                "id": "13"
            } 
            ,
            {
                "type": "coupon1",
                 "id": "14"
            }
        ]
    }]

相应地,数组中包含2个对象,则第1个对象的relation可以为share或者exclude,第二个对象的relation必须为exclude

[
    {
        "relation": "share",
        "items":
        [
            {
                "type": "activity0",
                "id": "11"
            },
            {
                "type": "card3",
                "id":"12"
            }
        ]
    },
    {
        "relation": "exclude",
        "items":
        [
            {
                "type": "card1",
                "id": "18"
            },
            {
                "type": "coupon1",
                "id": "22"
            }
        ]
    }
]

最终将转化为共享组,比如上面的协议将转化为下面2个共享组

activity0-card3-card1
activity0-card3-coupon1

工具类 DiscountGroupUtil 提供了协议转共享组的方法,由于共享组可能很长,所以先和用户当前订单可享的优惠进行一个交叉过滤,为了提升过滤的性能,要将当前可用优惠转成二级Map,这个Map的外层键是协议中的type,第二层键是协议中的id

public static List<Pair<Set<DiscountWrapper>,Set<DiscountWrapper>>> transform(List<List<DiscountGroup>> groups, Map<String, Map<String,DiscountWrapper>> inMap);

为了保证算力,我们将用户本单可享的优惠分别装在2个集合中,左侧集合的大小为SUPPORTEDSIZE,也就是算力之内的、重点保障的优惠,而右侧的集合则尽力而为去叠加即可。
从稳定性角度来讲,我们需要给计算次数做一个统计,并在压测中摸清楚阈值,我们提供了LimitingUtil.count统计进入calc方法的次数,显然在没有开启缓存的情况下,计算次数为 $A_n^n$ x n,在开启缓存的情况下,计算次数为 $A_n^n$ x (n-3) + $A_n^3$

CASE

可以在com.github.qcalculator.discount.demo找到调用的具体case